Linear, Cone and Semidefinite Programming

Occupation measure relaxations in variational problems: the role of convexity

  • Didier Henrion
  • Milan Korda
  • Martin Kružík
  • Rodolfo Rios-Zertuche
    • Categories Linear, Cone and Semidefinite Programming Tags

    This work addresses the occupation measure relaxation of calculus of variations problems, which is an infinite-dimensional linear programming reformulation amenable to numerical approximation by a hierarchy of semidefinite optimization problems. We address the problem of equivalence of this relaxation to the original problem. Our main result provides sufficient conditions for this equivalence. These conditions, revolving … Read more

    An infeasible interior-point arc-search method with Nesterov’s restarting strategy for linear programming problems

  • Einosuke Iida
  • Makoto Yamashita
    • Categories Linear Programming Tags , , ,

    An arc-search interior-point method is a type of interior-point method that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and the computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov’s … Read more

    A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints

  • Samuel Burer
    • Categories Cone Programming, Global Optimization Theory, Quadratic Programming

    Globally optimizing a nonconvex quadratic over the intersection of $m$ balls in $\mathbb{R}^n$ is known to be polynomial-time solvable for fixed $m$. Moreover, when $m=1$, the standard semidefinite relaxation is exact. When $m=2$, it has been shown recently that an exact relaxation can be constructed using a disjunctive semidefinite formulation based essentially on two copies … Read more

    Semidefinite approximations for bicliques and biindependent pairs

  • Monique Laurent
  • Sven Polak
  • Luis Felipe Vargas
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , , , , ,

    We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $\alpha(G)$, well-known to be polynomial-time … Read more

    On solving the MAX-SAT using sum of squares

  • Lennart Sinjorgo
  • Renata Sotirov
    • Categories 0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming Tags , , , ,

    We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more

    Polynomial argmin for recovery and approximation of multivariate discontinuous functions

  • Didier Henrion
  • Milan Korda
  • Jean-Bernard Lasserre
    • Categories Basic Sciences Applications, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    We propose to approximate a (possibly discontinuous) multivariate function f(x) on a compact set by the partial minimizer arg min_y p(x,y) of an appropriate polynomial p whose construction can be cast in a univariate sum of squares (SOS) framework, resulting in a highly structured convex semidefinite program. In a number of non-trivial cases (e.g. when … Read more

    An easily computable upper bound on the Hoffman constant for homogeneous inequality systems

  • Javier F. Peña
    • Categories Linear Programming, Polyhedra, Second-Order Cone Programming Tags , ,

    Let $A\in \mathbb{R}^{m\times n}\setminus \{0\}$ and $P:=\{x:Ax\le 0\}$. This paper provides a procedure to compute an upper bound on the following {\em homogeneous Hoffman constant} \[ H_0(A) := \sup_{u\in \mathbb{R}^n \setminus P} \frac{\text{dist}(u,P)}{\text{dist}(Au, \mathbb{R}^m_-)}. \] In sharp contrast to the intractability of computing more general Hoffman constants, the procedure described in this paper is entirely … Read more

    A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization

  • Chuan He
  • Zhaosong Lu
    • Categories Cone Programming, Nonlinear Optimization Tags , , , , , ,

    In this paper we consider finding an approximate second-order stationary point (SOSP) of general nonconvex conic optimization that minimizes a twice differentiable function subject to nonlinear equality constraints and also a convex conic constraint. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier-augmented Lagrangian method for finding an approximate SOSP of this problem. Under … Read more