Relaxations of KKT Conditions do not Strengthen Finite RLT and SDP-RLT Bounds for Nonconvex Quadratic Programs

We consider linear and semidefinite programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT relaxation), and the Shor relaxation combined with the RLT relaxation (SDP-RLT relaxation). By incorporating the first-order optimality conditions, a quadratic program can be formulated as an optimization problem with complementarity constraints. We investigate the effect of incorporating optimality … Read more

Sparse Polynomial Matrix Optimization

A polynomial matrix inequality is a statement that a symmetric polynomial matrix is positive semidefinite over a given constraint set. Polynomial matrix optimization concerns minimizing the smallest eigenvalue of a symmetric polynomial matrix subject to a tuple of polynomial matrix inequalities. This work explores the use of sparsity methods in reducing the complexity of sum-of-squares … Read more

Exploiting Sign Symmetries in Minimizing Sums of Rational Functions

This paper is devoted to the problem of minimizing a sum of rational functions over a basic semialgebraic set. We provide a hierarchy of sum of squares (SOS) relaxations that is dual to the generalized moment problem approach due to Bugarin, Henrion, and Lasserre. The investigation of the dual SOS aspect offers two benefits: 1) … Read more

Sparse Polynomial Optimization with Unbounded Sets

This paper considers sparse polynomial optimization with unbounded sets. When the problem possesses correlative sparsity, we propose a sparse homogenized Moment-SOS hierarchy with perturbations to solve it. The new hierarchy introduces one extra auxiliary variable for each variable clique according to the correlative sparsity pattern. Under the running intersection property, we prove that this hierarchy … Read more

A real moment-HSOS hierarchy for complex polynomial optimization with real coefficients

This paper proposes a real moment-HSOS hierarchy for complex polynomial optimization problems with real coefficients. We show that this hierarchy provides the same sequence of lower bounds as the complex analogue, yet is much cheaper to solve. In addition, we prove that global optimality is achieved when the ranks of the moment matrix and certain … Read more

On Exact and Inexact RLT and SDP-RLT Relaxations of Quadratic Programs with Box Constraints

Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the RLT (Reformulation-Linearization Technique) relaxation and the SDP-RLT relaxation obtained by adding semidefinite constraints to … Read more

An SDP Relaxation for the Sparse Integer Least Squares Problem

In this paper, we study the sparse integer least squares problem (SILS), an NP-hard variant of least squares with sparse {0, 1, -1}-vectors. We propose an l1-based SDP relaxation, and a randomized algorithm for SILS, which computes feasible solutions with high probability with an asymptotic approximation ratio 1/T^2 as long as the sparsity constant σ … Read more

Partial Lasserre relaxation for sparse Max-Cut

A common approach to solve or find bounds of polynomial optimization problems like Max-Cut is to use the first level of the Lasserre hierarchy. Higher levels of the Lasserre hierarchy provide tighter bounds, but solving these relaxations is usually computationally intractable. We propose to strengthen the first level relaxation for sparse Max-Cut problems using constraints … Read more

A Restricted Dual Peaceman-Rachford Splitting Method for QAP

We revisit and strengthen splitting methods for solving doubly nonnegative, DNN, relaxations of the quadratic assignment problem, QAP. We use a modified restricted contractive splitting method, rPRSM, approach. Our strengthened bounds and new dual multiplier estimates improve on the bounds and convergence results in the literature. CitationDepartment of Combinatorics & Optimization, University of Waterloo, Canada,06/2019ArticleDownload … Read more

A Strictly Contractive Peaceman-Rachford Splitting Method for the Doubly Nonnegative Relaxation of the Minimum Cut Problem

The minimum cut problem, MC, and the special case of the vertex separator problem, consists in partitioning the set of nodes of a graph G into k subsets of given sizes in order to minimize the number of edges cut after removing the k-th set. Previous work on this topic uses eigenvalue, semidefinite programming, SDP, … Read more