quadratic programming

Lagrangian-Conic Relaxations, Part I: A Unified Framework and Its Applications to Quadratic Optimization Problems

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In Part I of a series of study on Lagrangian-conic relaxations, we introduce a unified framework for conic and Lagrangian-conic relaxations of quadratic optimization problems (QOPs) and polynomial optimization problems (POPs). The framework is constructed with a linear conic optimization problem (COP) in a finite dimensional vector space endowed with an inner product, where the … 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

    Completely Positive Reformulations for Polynomial Optimization

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Global Optimization Theory Tags , , ,

    Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well stablished body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of … Read more

    A Polynomial Time Constraint-Reduced Algorithm for Semidefinite Optimization Problems, with Convergence Proofs

  • Dianne P. O'Leary
  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , , , , , , ,

    We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction … Read more

    Attraction of Newton method to critical Lagrange multipliers: fully quadratic case

  • Alexey F. Izmailov
  • E.I. Uskov
    • Categories Constrained Nonlinear Optimization Tags , , ,

    All previously known results concerned with attraction of Newton-type iterations for optimality systems to critical Lagrange multipliers were a posteriori by nature: they were showing that in case of convergence, the dual limit is in a sense unlikely to be noncritical. This paper suggests the first a priori result in this direction, showing that critical … Read more

    Quadratic Outer Approximation for Convex Integer Programming

  • Christoph Buchheim
  • Long Trieu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags , ,

    We present a quadratic outer approximation scheme for solving general convex integer programs, where suitable quadratic approximations are used to underestimate the objective function instead of classical linear approximations. As a resulting surrogate problem we consider the problem of minimizing a function given as the maximum of finitely many convex quadratic functions having the same … Read more

    Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic Programming

  • Jacek Gondzio
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper we will discuss two variants of an inexact feasible interior point algorithm for convex quadratic programming. We will consider two different neighbourhoods: a (small) one induced by the use of the Euclidean norm which yields a short-step algorithm and a symmetric one induced by the use of the infinity norm which yields … Read more