This paper proposes a new semidefinite programming relaxation for the satisfiability problem. This relaxation is an extension of previous relaxations arising from the paradigm of partial semidefinite liftings for 0/1 ...
详细信息
This paper proposes a new semidefinite programming relaxation for the satisfiability problem. This relaxation is an extension of previous relaxations arising from the paradigm of partial semidefinite liftings for 0/1 optimization problems. The construction of the relaxation depends on a choice of permutations of the clauses, and different choices may lead to different relaxations. We then consider the Tseitin instances, a class of instances known to be hard for certain proof systems, and prove that for any choice of permutations, the proposed relaxation is exact for these instances, meaning that a Tseitin instance is unsatisfiable if and only if the corresponding semidefinite programming relaxation is infeasible.
In this work, different relaxations applicable to an MPC problem with binary control signals are compared. The relaxations considered are the QP relaxation, the standard SDP relaxation and an alternative equality cons...
详细信息
In this work, different relaxations applicable to an MPC problem with binary control signals are compared. The relaxations considered are the QP relaxation, the standard SDP relaxation and an alternative equality constrained SDP relaxation. The relaxations are related theoretically, and both the tightness of the bounds and the computational complexities are compared in numerical experiments. The result is that for long prediction horizons, the equality constrained SDP relaxation proposed in this paper provides a good trade-off between the quality of the relaxation and the computational time.
In this paper, we show that linear varieties of polynomials can be used to approximate linear varieties of the space of continuous functions. This property is important in applications where polynomial optimization is...
详细信息
In this paper, we show that linear varieties of polynomials can be used to approximate linear varieties of the space of continuous functions. This property is important in applications where polynomial optimization is used as it allows one to impose affine constraints on the decision variables with no loss of accuracy. In particular, construction of Lyapunov functionals for systems with delay is discussed.
Our approach to protein-protein docking includes three main steps. First we run PIPER, a new rigid body docking program. PIPER is based on the Fast Fourier Transform (FFT) correlation approach that has been extended t...
详细信息
Our approach to protein-protein docking includes three main steps. First we run PIPER, a new rigid body docking program. PIPER is based on the Fast Fourier Transform (FFT) correlation approach that has been extended to use pairwise interactions potentials, thereby substantially increasing the number of near-native structures generated. The interaction potential is also new, based on the DARS (Decoys As the Reference State) principle. In the second step, the 1000 best energy conformations are clustered, and the 30 largest clusters are retained for refinement. Third, the conformations are refined by a new medium-range optimization method SDU (Semi-Definite programming based Underestimation). SDU has been developed to locate global minima within regions of the conformational space in which the energy function is funnel-like. The method constructs a convex quadratic underestimator function based on a set of local energy minima, and uses this function to guide future sampling. The combined method performed reliably without the direct use of biological information in most CAPRI problems that did not require homology modeling, providing acceptable predictions for targets 21, and medium quality predictions for targets 25 and 26.
We present an overview of the essential elements of semidefinite programming as a computational tool for the analysis of systems and control problems. We make particular emphasis on general duality properties as provi...
详细信息
We present an overview of the essential elements of semidefinite programming as a computational tool for the analysis of systems and control problems. We make particular emphasis on general duality properties as providing suboptimality or infeasibility certificates. Our focus is on the exciting developments which have occured in the last few nears, including robust optimization, combinatorial optimization, and algebraic methods such as sum-of-squares. These developments are illustrated with examples of applications to control systems.
Let E be the Hilbert space of real symmetric matrices with block diagonal form diag(A, M), where A is n x n, and M is an l x l diagonal matrix, with the inner product (x, y) equivalent to Trace(xy). We assume n + l gr...
详细信息
Let E be the Hilbert space of real symmetric matrices with block diagonal form diag(A, M), where A is n x n, and M is an l x l diagonal matrix, with the inner product (x, y) equivalent to Trace(xy). We assume n + l greater than or equal to 1, i.e. allow n = 0 or l = 0. Given x epsilon E, we write x greater than or equal to 0 (x > 0) if it is positive semidefinite (positive definite). Let Q : E --> E be a symmetric positive semidefinite linear operator, and mu = min{phi(x) = 0.5 Trace(xQx) : parallel toxparallel to = 1, x greater than or equal to 0}. The problem of testing if mu = 0 is a significant problem called Homogeneous programming. On the one hand the feasibility problem in semidefinite programming (SDP) can be formulated as a Homogeneous programming problem. On the other hand it is related to the generalization of the classic problem of Matrix Scaling. Let epsilon is an element of (0, 1) be a given accuracy, u = Qe - e, e the identity matrix in E, and N = n + l. We describe a path-following algorithm that in case mu = 0, in O(rootN ln[Nparallel touparallel to/epsilon]) Newton iterations produces d greater than or equal to 0, parallel todparallel to = 1 such that phi(d) less than or equal to epsilon. If mu > 0, in O(rootN ln[Nparallel touparallel to/mu] + ln ln(1/epsilon)) Newton iterations the algorithm produces d > 0 such that parallel toDQDe - eparallel to less than or equal to epsilon, where D is the operator that maps w epsilon E to d(1/2)wd(1/2). Moreover, we use the algorithm to prove: mu > 0, if and only if there exists d > 0 such that DQDe = e, if and only if there exists d > 0 such that Qd > 0. Thus via this duality the Matrix Scaling problem is a natural dual to the feasibility problem in SDP. This duality also implies that in Blum et al. [Bull. AMS 21 (1989) 1] real number model of computation the decision problem of testing the solvability of Matrix Scaling is both in NP and Co-NP. Although the above complexities can be deduced from our path-follo
Several important problems in control theory can be reformulated as semidefinite programming problems, i.e., minimization of a linear objective subject to linear matrix inequality (LMI) constraints. From convex optimi...
详细信息
Several important problems in control theory can be reformulated as semidefinite programming problems, i.e., minimization of a linear objective subject to linear matrix inequality (LMI) constraints. From convex optimization duality theory, conditions for infeasibility of the LMIs, as well as dual optimization problems, can be formulated. These can in turn be reinterpreted in control or system theoretic terms, often yielding new results or new proofs for existing results from control theory. We explore such connections for a few problems associated with linear time-invariant systems.
作者：
Parrilo, PAETH
Swiss Fed Inst Technol Automat Control Lab CH-8092 Zurich Switzerland CALTECH
Control & Dynam Syst Dept Pasadena CA 91125 USA
A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polyn...
详细信息
A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide a constructive approach for finding bounded degree solutions to the Positivstellensatz, and are illustrated with examples from diverse application fields.
In this paper, based on the semidefinite programming relaxation of the CDMA maximum likelihood (ML) multiuser detection problem, a detection strategy by the successive quadratic programming algorithm is presented. Cou...
详细信息
In this paper, based on the semidefinite programming relaxation of the CDMA maximum likelihood (ML) multiuser detection problem, a detection strategy by the successive quadratic programming algorithm is presented. Coupled with the randomized cut generation scheme, we obtain the suboptimal solution of multiuser detection problem. Comparing with the reported interior point methods based on semidefinite programming, simulations demonstrate that the successive quadratic programming algorithm often yields the similar BER performances of the multiuser detection problem. But the average CPU time of this approach is significantly reduced.
In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by p...
详细信息
In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods. This framework is based on some results about positive semidefinite matrix completion, and it can be embodied in two different ways. One is by a conversion of a given sparse SDP having a large scale positive semidefinite matrix variable into an SDP having multiple but smaller positive semidefinite matrix variables. The other is by incorporating a positive definite matrix completion itself in a primal-dual interior-point method. The current article presents the details of their implementations. We introduce new techniques to deal with the sparsity through a clique tree in the former method and through new computational formulae in the latter one. Numerical results over different classes of SDPs show that these methods can be very efficient for some problems.
暂无评论