Quadratic factorization heuristics for copositive programming

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

A note on Burer’s copositive representation of mixed-binary QPs

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

Relating max-cut problems and binary linear feasibility problems

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

Descent heuristics for unconstrained minimization

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. Citation Report, Mathematisches Institut, Universitaet Duesseldorf, August 2008. Article Download … Read more

On the computation of $C^*$ certificates

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

Two theoretical results for sequential semidefinite programming

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. Citation Preprint, … Read more

An Augmented Primal-Dual Method for Linear Conic Programs

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

On an Approximation of the Hessian of the Lagrangian

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