Florian Jarre The goal of this paper is an easy and self-contained presentation of optimality conditions for nonlinear semidefinite programs concentrating on the differences between nonlinear semidefinite programs and nonlinear programs. CitationTechnical Report, Department of Mathematics, Universit\”at D\”usseldorf.ArticleDownload View PDF
Copositive optimization problems are particular conic programs: extremize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone … Read more
In an important paper, Burer recently showed how to reformulate general mixed-binary quadratic optimization problems (QPs) into copositive programs where a linear functional is minimized over a linearly constrained subset of the cone of completely positive matrices. In this note we interpret the implication from a topological point of view, showing that the Minkowski sum … Read more
This paper explores generalizations of the Goemans-Williamson randomization technique. It establishes a simple equivalence of binary linear feasibility problems and max-cut problems and presents an analysis of the semidefinite max-cut relaxation for the case of a single linear equation. Numerical examples for feasible random binary problems indicate that the randomization technique is efficient when the … Read more
Semidefinite relaxations often provide excellent starting points for nonconvex problems with multiple local minimizers. This work aims to find a local minimizer within a certain neighborhood of the starting point and with a small objective value. Several approaches are motivated and compared with each other. CitationReport, Mathematisches Institut, Universitaet Duesseldorf, August 2008.ArticleDownload View PDF
The cone of completely positive matrices $C^*$ is the convex hull of all symmetric rank-1-matrices $xx^T$ with nonnegative entries. Determining whether a given matrix $B$ is completely positive is an $\cal NP$-complete problem. We examine a simple algorithm which — for a given input $B$ — either determines a certificate proving that $B\in C^*$ or … Read more
We examine the local convergence of a sequential semidefinite programming approach for solving nonlinear programs with nonlinear semidefiniteness constraints. Known convergence results are extended to slightly weaker second order sufficient conditions and the resulting subproblems are shown to have local convexity properties that imply a weak form of self-concordance of the barrier subproblems. CitationPreprint, Mathematisches … Read more
We propose a new iterative approach for solving linear programs over convex cones. Assuming that Slaters condition is satisfied, the conic problem is transformed to the minimization of a convex differentiable function. This “agumented primal-dual function” or “apd-function” is restricted to an affine set in the primal-dual space. The evaluation of the function and its … Read more
In the context of SQP methods or, more recently, of sequential semidefinite programming methods, it is common practice to construct a positive semidefinite approximation of the Hessian of the Lagrangian. The Hessian of the augmented Lagrangian is a suitable approximation as it maintains local superlinear convergence under appropriate assumptions. In this note we give a … Read more