Quadratic Programming

HIPAD – A Hybrid Interior-Point Alternating Direction algorithm for knowledge-based SVM and feature selection

  • Ioannis G. Akrotirianakis
  • Zhiwei (Tony) Qin
  • Amit Chakraborty
  • Xiaocheng Tang
    • Categories Convex and Nonsmooth Optimization, Data-Mining, Quadratic Programming Tags , , , ,

    We consider classification tasks in the regime of scarce labeled training data in high dimensional feature space, where specific expert knowledge is also available. We propose a new hybrid optimization algorithm that solves the elastic-net support vector machine (SVM) through an alternating direction method of multipliers in the first phase, followed by an interior-point method … Read more

    Globally Convergent Primal-Dual Active-Set Methods with Inexact Subproblem Solves

  • Frank E. Curtis
  • Zheng Han
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Quadratic Programming Tags , , , , ,

    We propose primal-dual active-set (PDAS) methods for solving large-scale instances of an important class of convex quadratic optimization problems (QPs). The iterates of the algorithms are partitions of the index set of variables, where corresponding to each partition there exist unique primal-dual variables that can be obtained by solving a (reduced) linear system. Algorithms of … Read more

    Lower Bounds for the Quadratic Minimum Spanning Tree Problem Based on Reduced Cost Computation

  • Federico Malucelli
  • Borzou Rostami
    • Categories Combinatorial Optimization, Quadratic Programming Tags , , , , ,

    The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MST whose cost considers also the interaction between every pair … Read more

    On fast trust region methods for quadratic models with linear constraints

  • M.J.D. Powell
    • Categories Constrained Nonlinear Optimization, Quadratic Programming

    Quadratic models Q_k(.) of the objective function F(.) are used by many successful iterative algorithms for minimization, where k is the iteration number. Given the vector of variables x_k, a new vector x_{k+1} may be calculated that satisfies Q_k(x_{k+1}) < Q_k(x_k), in the hope that it provides the reduction F(x_{k+1}) < F(x_k). Trust region methods ... Read more

    On a new class of matrix support functionals with applications

  • James V. Burke
  • Tim Hoheisel
    • Categories Convex and Nonsmooth Optimization, Quadratic Programming, Semi-definite Programming Tags , , , , , ,

    A new class of matrix support functionals is presented which establish a connection between optimal value functions for quadratic optimization problems, the matrix-fractional function, the pseudo matrix-fractional function, and the nuclear norm. The support function is based on the graph of the product of a matrix with its transpose. Closed form expressions for the support … Read more

    How the augmented Lagrangian algorithm can deal with an infeasible convex quadratic optimization problem

  • Alice Chiche
  • Jean Charles Gilbert
    • Categories Convex and Nonsmooth Optimization, Quadratic Programming Tags , , , , , , , , ,

    This paper analyses the behavior of the augmented Lagrangian algorithm when it deals with an infeasible convex quadratic optimization problem. It is shown that the algorithm finds a point that, on the one hand, satisfies the constraints shifted by the smallest possible shift that makes them feasible and, on the other hand, minimizes the objective … Read more

    A Branch-and-Bound Algorithm for Instrumental Variable Quantile Regression

  • Samuel Burer
  • Guanglin Xu
    • Categories Nonlinear Optimization, Quadratic Programming, Statistics

    This paper studies a statistical problem called instrumental variable quantile regres- sion (IVQR). We model IVQR as a convex quadratic program with complementarity constraints and—although this type of program is generally NP-hard—we develop a branch-and-bound algorithm to solve it globally. We also derive bounds on key vari- ables in the problem, which are valid asymptotically … Read more

    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