摘要 :
Examples of weakly infeasible semidefinite programs (SDP) are useful to test whether SDP solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre's ...
展开
Examples of weakly infeasible semidefinite programs (SDP) are useful to test whether SDP solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre's semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible SDP. Such examples could be used to test whether a SDP solver can detect weak infeasibility. In addition, in this note, we generate weakly infeasible SDP from an instance of polynomial optimization with nonempty feasible region and solve them by SDP solvers. Although all semidefinite programming relaxation problems are infeasible, we observe that SDP solvers do not detect the infeasibility and that values returned by SDP solvers are equal to the optimal value of the instance due to numerical round-off errors.
收起
摘要 :
A SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical optimization. SDP provides an effective computation framework for many research fields. Some applications, however, require solving a lar...
展开
A SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical optimization. SDP provides an effective computation framework for many research fields. Some applications, however, require solving a large-scale SDP whose size exceeds the capacity of a single processor both in terms of computation time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAl-lel package) [Yamashita et al. 2003b] was designed to solve such large-scale SDPs. Its parallel performance is outstanding for general SDPs in most cases. However, the parallel implementation is less successful for some sparse SDPs obtained from applications such as Polynomial Optimization Problems (POPs) or Sensor Network Localization (SNL) problems, since this version of SDPARA cannot directly handle sparse Schur Complement Matrices (SCMs). In this article we improve SDPARA by focusing on the sparsity of the SCM and we propose a new parallel implementation using the formula-cost-based distribution along with a replacement of the dense Cholesky factorization. We verify numerically that these features are key to solving SDPs with sparse SCMs more quickly on parallel computing systems. The performance is further enhanced by multithreading and the new SDPARA attains considerable scalability in general. It also finds solutions for extremely large-scale SDPs arising from POPs which cannot be obtained by other solvers.
收起
摘要 :
We propose a heuristic for 0/1 programs based on the recent "joint + marginal" approach of the first author for parametric polynomial optimization. The idea is to first consider the n-variable (x_1,… ,x_n) problem as a (n - Invar...
展开
We propose a heuristic for 0/1 programs based on the recent "joint + marginal" approach of the first author for parametric polynomial optimization. The idea is to first consider the n-variable (x_1,… ,x_n) problem as a (n - Invariable problem (x_2,…, x_n) with the variable x_1 being now a parameter taking value in {0, 1}. One then solves a hierarchy of what we call "joint + marginal" semidefinite relaxations whose duals provide a sequence of polynomial approximations x_1 → J_k(x_1) that converges to the optimal value function J(x_1) (as a function of the parameter x_1). One considers a fixed index k in the hierarchy and if J_k(1) > J_k(0) then one decides x_1 = 1 and x_1 = 0 otherwise. The quality of the approximation depends on how large k can be chosen (in general, for significant size problems, k = 1 is the only choice). One iterates the procedure with now a (n - 2)-variable problem with one parameter X_2 ∈ {0,1}, etc. Variants are also briefly described as well as some preliminary numerical experiments on the MAXCUT, k-cluster and 0/1 knapsack problems.
收起
摘要 :
SDPLIB is a collection of semidefinite programming (SDP) test problems. The problems are drawn from a variety of applications, including truss topology design, control systems engineering, and relaxations of combinatorial optimiza...
展开
SDPLIB is a collection of semidefinite programming (SDP) test problems. The problems are drawn from a variety of applications, including truss topology design, control systems engineering, and relaxations of combinatorial optimization problems. The current version of the library contains a total of 92 SDP problems encoded in a standard format. It is hoped that SDPLIB will stimulate the development of improved software for the solution of SDP problems.
收起
摘要 :
In this short note we consider a sequential quadratic programming (SQP) - type method with conic subproblems and compare this method with a standard SQP method in which the conic constraint is linearized at each step. For both app...
展开
In this short note we consider a sequential quadratic programming (SQP) - type method with conic subproblems and compare this method with a standard SQP method in which the conic constraint is linearized at each step. For both approaches we restrict our attention to convex subproblems since these are easy to solve and guarantee a certain global descent property. Using the example of a simple nonlinear program (NLP) and its conic reformulation we show that the SQP method with conic subproblems displays a slower rate of convergence than standard SQP methods. We then explain why an SQP subproblem that is based on a better approximation of the feasible set of the NLP results in a much slower algorithm.
收起
摘要 :
We consider the optimization problems max (z is an element of Omega) min (x is an element of K) p(z, x) and min (x is an element of K) max (z is an element of Omega) p(z, x) where the criterion p is a polynomial, linear in the var...
展开
We consider the optimization problems max (z is an element of Omega) min (x is an element of K) p(z, x) and min (x is an element of K) max (z is an element of Omega) p(z, x) where the criterion p is a polynomial, linear in the variables z, the set Omega can be described by LMIs, and K is a basic closed semi-algebraic set. The first problem is a robust analogue of the generic SDP problem max (z is an element of Omega) p(z), whereas the second problem is a robust analogue of the generic problem min (x is an element of K) p(x) of minimizing a polynomial over a semi-algebraic set. We show that the optimal values of both robust optimization problems can be approximated as closely as desired, by solving a hierarchy of SDP relaxations. We also relate and compare the SDP relaxations associated with the max-min and the min-max robust optimization problems.
收起
摘要 :
Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n * n matrix-valued function of a certain form...
展开
Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n * n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented.
收起
摘要 :
In this paper, we consider a binary quadratic program (BQP) with random objective coefficients. Given only information on the marginal distributions of the objective coefficients, we propose a tight bound on the expected optimal v...
展开
In this paper, we consider a binary quadratic program (BQP) with random objective coefficients. Given only information on the marginal distributions of the objective coefficients, we propose a tight bound on the expected optimal value of the random BQP. We show that the complexity of computing this bound does not increase substantially with respect to the complexity of solving the corresponding deterministic BQP. For the quadratic unconstrained binary optimization (QUBO) problem with nonnegative off-diagonal random entries, the bound is shown to be computable in polynomial time. We generalize the asymptotic bound for the random quadratic assignment problem from independent random variables to dependent random variables and propose a new closed-form bound on the expected optimal value of the quadratic k-cluster problem. We also provide polynomial time computable upper bounds on the expected optimal value for the NP-hard instances using the linear and semidefinite programming relaxation of the deterministic BQP. The semidefinite programming bound of the expected optimal value of the random MAX-CUT problem inherits the approximation ratio of 0.878 from the semidefinite relaxation of the deterministic MAX-CUT problem. Computational experiments on random QUBO problems and random quadratic knapsack problems provide evidence of the quality of the bounds. Overall, our results indicate that the new bound on the expected optimal value of the random BQP is attractive since it exploits many of the nice results and formulations of the deterministic BQP and is valid under limited distributional information.
收起
摘要 :
We consider semidefinite optimization problems that include constraints of the form G(x) >= 0 and H(x) >= 0, where the components of the symmetric matrices G(.) and H(.) are affine functions of x is an element of R-n. In such a ca...
展开
We consider semidefinite optimization problems that include constraints of the form G(x) >= 0 and H(x) >= 0, where the components of the symmetric matrices G(.) and H(.) are affine functions of x is an element of R-n. In such a case we obtain a new constraint K(x, X) >= 0, where the components of K(.,.) are affine functions of x and X, and X is an n x n matrix that is a relaxation of xx(T). The constraint K(x, X) >= 0 is based on the fact that G(x) circle times H(x) >= 0, where circle times denotes the Kronecker product. This construction of a constraint based on the Kronecker product generalizes the construction of a reformation-linearization technique (RLT) constraint from two linear inequality constraints, and also the construction of a second-order coneRLT constraint from one linear inequality constraint and a second-order cone constraint. We show how the Kronecker product constraint obtained from two second-order cone constraints can be efficiently used to computationally strengthen the semidefinite programming relaxation of the two-trust-region subproblem.
收起
摘要 :
Given a p x q nonnegative matrix M, the psd rank of M is the smallest integer k such that there exist k x k real symmetric positive semidefinite matrices A(1), ... ,A(p) and B-1, ... ,B-q such that M-ij = < A(i) , B-j > for i = 1, ... ,p and j ...
展开
Given a p x q nonnegative matrix M, the psd rank of M is the smallest integer k such that there exist k x k real symmetric positive semidefinite matrices A(1), ... ,A(p) and B-1, ... ,B-q such that M-ij = < A(i) , B-j > for i = 1, ... ,p and j = 1, ... ,q. When the entries of M are rational it is natural to consider the rational restricted psd rank of M, where the factors A(i) and B-i are required to have rational entries. It is clear that the rational-restricted psd rank is always an upper bound to the usual psd rank. We show that this inequality may be strict by exhibiting a matrix with psd rank four whose rational-restricted psd rank is strictly greater than four. (C) 2015 Elsevier B.V. All rights reserved.
收起
原文获取