Pareto Robust Optimization on Euclidean Vector Spaces

Pareto efficiency for robust linear programs was introduced by Iancu and Trichakis. We generalize their approach and theoretical results to robust optimization problems in Euclidean spaces with affine uncertainty. Additionally, we demonstrate the value of this approach in an exemplary manner in the area of robust semidefinite programming (SDP). In particular, we prove that computing … Read more

SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs

We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of … Read more

Dealing with inequality constraints in large scale semidefinite relaxations for graph coloring and maximum clique problems

Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods. However, when the dimension of the problem gets large, interior point methods become impractical both in terms of computational time and memory requirements. First order methods, such as Alternating Direction Methods of Multipliers (ADMMs), turned out to be suitable algorithms to deal … Read more

Sequential constant rank constraint qualifications for nonlinear semidefinite programming with applications

We present new constraint qualification conditions for nonlinear semidefinite programming that extend some of the constant rank-type conditions from nonlinear programming. As an application of these conditions, we provide a unified global convergence proof of a class of algorithms to stationary points without assuming neither uniqueness of the Lagrange multiplier nor boundedness of the Lagrange … Read more

Convex Hull Results on Quadratic Programs with Non-Intersecting Constraints

Let F be a set defined by quadratic constraints. Understanding the structure of the closed convex hull cl(C(F)) := cl(conv{xx’ | x in F}) is crucial to solve quadratically constrained quadratic programs related to F. A set G with complicated structure can be constructed by intersecting simple sets. This paper discusses the relationship between cl(C(F)) … Read more

Sums of Separable and Quadratic Polynomials

We study separable plus quadratic (SPQ) polynomials, i.e., polynomials that are the sum of univariate polynomials in different variables and a quadratic polynomial. Motivated by the fact that nonnegative separable and nonnegative quadratic polynomials are sums of squares, we study whether nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative … Read more

A Strengthened Barvinok-Pataki Bound on SDP Rank

The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e., on the algebra of the problem. Specifically, the triangular number of the rank r is upper bounded by the number of affine constraints. We revisit … Read more

Robust Interior Point Method for Quantum Key Distribution Rate Computation

While the security proof method for quantum key distribution, QKD, based on the numerical key rate calculation problem, is powerful in principle, the practicality of the method is limited by computational resources and the efficiency of the underlying algorithm for convex optimization. We derive a stable reformulation of the convex nonlinear semidefinite programming, SDP, model … Read more

Finite convergence of sum-of-squares hierarchies for the stability number of a graph

We investigate a hierarchy of semidefinite bounds $\vartheta^{(r)}(G)$ for the stability number $\alpha(G)$ of a graph $G$, based on its copositive programming formulation and introduced by de Klerk and Pasechnik [SIAM J. Optim. 12 (2002), pp.875–892], who conjectured convergence to $\alpha(G)$ in $r=\alpha(G) -1$ steps. Even the weaker conjecture claiming finite convergence is still open. … Read more

Weak notions of nondegeneracy in nonlinear semidefinite programming

The constraint nondegeneracy condition is one of the most relevant and useful constraint qualifications in nonlinear semidefinite programming. It can be characterized in terms of any fixed orthonormal basis of the, let us say, $\ell$-dimensional kernel of the constraint matrix, by the linear independence of a set of $\ell(\ell+1)/2$ derivative vectors. We show that this … Read more