Quadratic Programming

Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs

  • Immanuel M. Bomze
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , ,

    We study non-convex quadratic minimization problems under (possibly non-convex) quadratic and linear constraints, and characterize both Lagrangian and Semi-Lagrangian dual bounds in terms of conic optimization. While the Lagrangian dual is equivalent to the SDP relaxation (which has been known for quite a while, although the presented form, incorporating explicitly linear constraints, seems to be … Read more

    A Two-Variable Approach to the Two-Trust-Region Subproblem

  • Samuel Burer
  • Boshi Yang
    • Categories Quadratic Programming, Semi-definite Programming Tags , ,

    The trust-region subproblem minimizes a general quadratic function over an ellipsoid and can be solved in polynomial time using a semidefinite-programming (SDP) relaxation. Intersecting the feasible set with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing algorithms do not use SDP. In this paper, … Read more

    Narrowing the difficulty gap for the Celis-Dennis-Tapia problem

  • Immanuel M. Bomze
  • Michael L. Overton
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Quadratic Programming Tags , , , ,

    We study the {\em Celis-Dennis-Tapia (CDT) problem}: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that … Read more

    A Parallel Quadratic Programming Method for Dynamic Optimization Problems

  • Moritz Diehl
  • Sebastian Sager
  • Janick V Frasch
    • Categories Control Applications, Quadratic Programming Tags , , ,

    Quadratic programming problems (QPs) that arise from dynamic optimization problems typically exhibit a very particular structure. We address the ubiquitous case where these QPs are strictly convex and propose a dual Newton strategy that exploits the block-bandedness similarly to an interior-point method. Still, the proposed method features warmstarting capabilities of active-set methods. We give details … Read more

    An efficient gradient method using the Yuan steplength

  • Roberta De Asmundis
  • Daniela di Serafino
  • William W. Hager
  • Gerardo Toraldo
  • Hongchao Zhang
    • Categories Nonlinear Optimization, Quadratic Programming, Unconstrained Optimization Tags , ,

    We propose a new gradient method for quadratic programming, named SDC, which alternates some SD iterates with some gradient iterates that use a constant steplength computed through the Yuan formula. The SDC method exploits the asymptotic spectral behaviour of the Yuan steplength to foster a selective elimination of the components of the gradient along the … Read more

    A feasible active set method for strictly convex problems with simple bounds

  • Philipp Hungerländer
  • Franz Rendl
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    A primal-dual active set method for quadratic problems with bound constraints is presented which extends the infeasible active set approach of [K. Kunisch and F. Rendl. An infeasible active set method for convex problems with simple bounds. SIAM Journal on Optimization, 14(1):35-52, 2003]. Based on a guess of the active set, a primal-dual pair (x,α) … Read more

    An Active-Set Quadratic Programming Method Based On Sequential Hot-Starts

  • Travis C. Johnson
  • Christian Kirches
  • Andreas Wächter
    • Categories Quadratic Programming Tags , , , , , , ,

    A new method for solving sequences of quadratic programs (QPs) is presented. For each new QP in the sequence, the method utilizes hot-starts that employ information computed by an active-set QP solver during the solution of the first QP. This avoids the computation and factorization of the full matrices for all but the first problem … Read more

    A Lagrangian-DNN Relaxation: a Fast Method for Computing Tight Lower Bounds for a Class of Quadratic Optimization Problems

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified Lagrangian-CPP relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012 takes one of the simplest forms, an unconstrained conic linear optimization problem … Read more

    Trust-Region Problems with Linear Inequality Constraints: Exact SDP Relaxation, Global Optimality and Robust Optimization

  • V. Jeyakumar
  • Guoyin Li
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

    The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having … Read more

    Analysis of Copositive Optimization Based Linear Programming Bounds on Standard Quadratic Optimization

  • Gizem Sagol
  • E. Alper Yildirim
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    The problem of minimizing a quadratic form over the unit simplex, referred to as a standard quadratic optimization problem, admits an exact reformulation as a linear optimization problem over the convex cone of completely positive matrices. This computationally intractable cone can be approximated from the inside and from the outside by two sequences of nested … Read more