Quadratic Programming

A Feasible Active Set Method with Reoptimization for Convex Quadratic Mixed-Integer Programming

  • Christoph Buchheim
  • Marianna De Santis
  • Stefano Lucidi
  • Francesco Rinaldi
  • Long Trieu
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

    We propose a feasible active set method for convex quadratic programming problems with non-negativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed integer programming problems. The branch-and-bound algorithm generalizes the approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara and Lodi to the presence … Read more

    Directed modified Cholesky factorizations and convex quadratic relaxations

  • Ferenc Domes
  • Arnold Neumaier
    • Categories Global Optimization, Quadratic Programming Tags , , , , , , ,

    A directed Cholesky factorization of a symmetric interval matrix \A consists of a permuted upper triangular matrix R such that for all symmetric A \in \A, the residual matrix A – R^T R is positive semidefinite with tiny entries. This must holds with full mathematical rigor, although the computations are done in floating-point arithmetic. Similarly, … Read more

    A comparison of reduced and unreduced KKT systems arising from Interior Point methods

  • Benedetta Morini
  • Valeria Simoncini
  • Mattia Tani
    • Categories Quadratic Programming Tags , , ,

    We address the iterative solution of symmetric KKT systems arising in the solution of convex quadratic programming problems. Two strictly related and well established formulations for such systems are studied with particular emphasis on the effect of preconditioning strategies on their relation. Constraint and augmented preconditioners are considered, and the choice of the augmentation Matrix … Read more

    Spectral estimates for unreduced symmetric KKT systems arising from Interior Point methods

  • Benedetta Morini
  • Valeria Simoncini
  • Mattia Tani
    • Categories Quadratic Programming Tags , , , ,

    We consider symmetrized KKT systems arising in the solution of convex quadratic programming problems in standard form by Interior Point methods. Their coefficient matrices usually have 3×3 block structure and, under suitable conditions on both the quadratic programming problem and the solution, they are nonsingular in the limit. We present new spectral estimates for these … Read more

    On the update of constraint preconditioners for regularized KKT systems

  • Stefania Bellavia
  • Valentina De Simone
  • Daniela di Serafino
  • Benedetta Morini
    • Categories Nonlinear Optimization, Quadratic Programming Tags , , ,

    We address the problem of preconditioning sequences of regularized KKT systems, such as those arising in Interior Point methods for convex quadratic programming. In this case, Constraint Preconditioners (CPs) are very effective and widely used; however, when solving large-scale problems, the computational cost for their factorization may be high, and techniques for approximating them appear … Read more

    On solving symmetric systems of linear equations in an unnormalized Krylov subspace framework

  • Anders Forsgren
  • Tove Odland
    • Categories Quadratic Programming, Unconstrained Optimization Tags , , ,

    In an unnormalized Krylov subspace framework for solving symmetric systems of linear equations, the orthogonal vectors that are generated by a Lanczos process are not necessarily on the form of gradients. Associating each orthogonal vector with a triple, and using only the three-term recurrences of the triples, we give conditions on whether a symmetric system … Read more

    Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations

  • Hongbo Dong
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming

    The current bottleneck of globally solving mixed-integer (nonconvex) quadratically constrained problem (MIQCP) is still to construct strong but computationally cheap convex relaxations, especially when dense quadratic functions are present. We pro- pose a cutting surface procedure based on multiple diagonal perturbations to derive strong convex quadratic relaxations for nonconvex quadratic problem with separable constraints. Our … Read more

    Distributed Optimization Methods for Large Scale Optimal Control

  • Attila Kozma
    • Categories Optimization of Simulated Systems, Quadratic Programming Tags , , , , ,

    This thesis aims to develop and implement both nonlinear and linear distributed optimization methods that are applicable, but not restricted to the optimal control of distributed systems. Such systems are typically large scale, thus the well-established centralized solution strategies may be computationally overly expensive or impossible and the application of alternative control algorithms becomes necessary. … Read more

    Subset Selection by Mallows’ Cp: A Mixed Integer Programming Approach

  • Ryuhei Miyashiro
  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Statistics Tags , , ,

    This paper concerns a method of selecting the best subset of explanatory variables for a linear regression model. Employing Mallows’ C_p as a goodness-of-fit measure, we formulate the subset selection problem as a mixed integer quadratic programming problem. Computational results demonstrate that our method provides the best subset of variables in a few seconds when … Read more