Quadratic Programming

A quasi-Newton strategy for the sSQP method for variational inequality and optimization problems

  • Damián Fernández
    • Categories Constrained Nonlinear Optimization, Quadratic Programming Tags , , ,

    The quasi-Newton strategy presented in this paper preserves one of the most important features of the stabilized Sequential Quadratic Programming method, the local convergence without constraint qualifications assumptions. It is known that the primal-dual sequence converges quadratically assuming only the second-order sufficient condition. In this work, we show that if the matrices are updated by … Read more

    Methods for Convex and General Quadratic Programming

  • Philip E. Gill
  • Elizabeth Wong
    • Categories Quadratic Programming Tags , , , , ,

    Computational methods are considered for finding a point that satisfies the second-order necessary conditions for a general (possibly nonconvex) quadratic program (QP). The first part of the paper considers the formulation and analysis of an active-set method for a generic QP with both equality and inequality constraints. The method uses a search direction that is … Read more

    Burer’s Key Assumption for Semidefinite and Doubly Nonnegative Relaxations

  • Florian Jarre
    • Categories Approximation Algorithms, Quadratic Programming, Semi-definite Programming Tags , ,

    Burer has shown that completely positive relaxations of nonconvex quadratic programs with nonnegative and binary variables are exact when the binary variables satisfy a so-called key assumption. Here we show that introducing binary variables to obtain an equivalent problem that satisfies the key assumption will not improve the semidefinite relaxation, and only marginally improve the … Read more

    Semidefinite Relaxations for Non-Convex Quadratic Mixed-Integer Programming

  • Christoph Buchheim
  • Angelika Wiegele
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

    We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this … Read more

    An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming

  • Christoph Buchheim
  • Alberto Caprara
  • Andrea Lodi
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Quadratic Programming Tags ,

    We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound … Read more

    On Doubly Positive Semidefinite Programming Relaxations

  • Dongdong Ge
  • Yinyu Ye
    • Categories Quadratic Programming, Semi-definite Programming Tags ,

    Recently, researchers have been interested in studying the semidefinite programming (SDP) relaxation model, where the matrix is both positive semidefinite and entry-wise nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing to the basic SDP relaxation, this doubly-positive SDP model possesses additional O(n2) constraints, which makes the SDP solution complexity substantially higher than that for the … Read more

    On convex relaxations for quadratically constrained quadratic programming

  • Kurt M. Anstreicher
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , ,

    We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let F denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on F is dominated by an alternative … Read more

    Fast population game dynamics for dominant sets and other quadratic optimization problems

  • Immanuel M. Bomze
  • Marcello Pelillo
  • Samuel Rota-Bulo
    • Categories Data-Mining, Game Theory, Quadratic Programming Tags ,

    We propose a fast population game dynamics, motivated by the analogy with infection and immunization processes within a population of “players,” for finding dominant sets, a powerful graph-theoretical notion of a cluster. Each step of the proposed dynamics is shown to have a linear time/space complexity and we show that, under the assumption of symmetric … Read more

    Separation and Relaxation for cones of quadratic forms

  • Samuel Burer
  • Hongbo Dong
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , ,

    Let P be a pointed, polyhedral cone in R_n. In this paper, we study the cone C = cone{xx^T: x \in P} of quadratic forms. Understanding the structure of C is important for globally solving NP-hard quadratic programs over P. We establish key characteristics of C and construct a separation algorithm for C provided one … Read more

    Newton–Picard-Based Preconditioning for Linear-Quadratic Optimization Problems with Time-Periodic Parabolic PDE Constraints

  • Hans Georg Bock
  • Andreas Potschka
  • M.S. Mommer
  • Johannes P. Schlöder
    • Categories Optimization of Systems modeled by PDEs, Quadratic Programming Tags , , , ,

    We develop and investigate two preconditioners for a basic linear iterative splitting method for the numerical solution of linear-quadratic optimization problems with time-periodic parabolic PDE constraints. The resulting real-valued linear system to be solved is symmetric indefinite. We propose all-at-once symmetric indefinite preconditioners based on a Newton–Picard approach which divides the variable space into slow … Read more