Quadratic Programming

Solution of monotone complementarity and general convex programming problems using modified potential reduction interior point method

  • Kuo-Ling Huang
  • Sanjay Mehrotra
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , ,

    We present a homogeneous algorithm equipped with a modified potential function for the monotone complementarity problem. We show that this potential function is reduced by at least a constant amount if a scaled Lipschitz condition is satis ed. A practical algorithm based on this potential function is implemented in a software package named iOptimize. The implementation … Read more

    Solving Mixed-Integer Nonlinear Programs by QP-Diving

  • Christian Kirches
  • Sven Leyffer
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

    We present a new tree-search algorithm for solving mixed-integer nonlinear programs (MINLPs). Rather than relying on computationally expensive nonlinear solves at every node of the branch-and-bound tree, our algorithm solves a quadratic approximation at every node. We show that the resulting algorithm retains global convergence properties for convex MINLPs, and we present numerical results on … Read more

    Numerical Optimization of Eigenvalues of Hermitian Matrix Functions

  • Mustafa Kilic
  • E. Alper Yildirim
  • Emre Mengi
    • Categories Global Optimization Applications, Quadratic Programming Tags , , , ,

    The eigenvalues of a Hermitian matrix function that depends on one parameter analytically can be ordered so that each eigenvalue is an analytic function of the parameter. Ordering these analytic eigenvalues from the largest to the smallest yields continuous and piece-wise analytic functions. For multi-variate Hermitian matrix functions that depend on $d$ parameters analytically, the … Read more

    On spectral properties of steepest descent methods

  • Roberta De Asmundis
  • Daniela di Serafino
  • Gerardo Toraldo
  • Filippo Riccio
    • Categories Nonlinear Optimization, Quadratic Programming Tags , ,

    In recent years it has been made more and more clear that the critical issue in gradient methods is the choice of the step length, whereas using the gradient as search direction may lead to very effective algorithms, whose surprising behaviour has been only partially explained, mostly in terms of the spectrum of the Hessian … Read more

    Constraint Reduction with Exact Penalization for Model-Predictive Rotorcraft Control

  • Aaron L. Greenfield
  • Meiyun Y. He
  • Vineet Sahasrabudhe
  • AndrĂ© L. Tits
    • Categories Applications - Science and Engineering, Control Applications, Quadratic Programming Tags , , , , , , , , ,

    Model Predictive Control (also known as Receding Horizon Control (RHC)) has been highly successful in process control applications. Its use for aerospace applications has been hindered by its high computational requirements. In the present paper, we propose using enhanced primal-dual interior-point optimization techniques in the convex-quadratic-program-based RHC control of a rotorcraft. Our enhancements include a … Read more

    Reformulation of a model for hierarchical divisive graph modularity maximization

  • Sonia Cafieri
  • Alberto Costa
  • Pierre Hansen
    • Categories Convex Optimization, Network Optimization, Quadratic Programming Tags , , ,

    Finding clusters, or communities, in a graph, or network is a very important problem which arises in many domains. Several models were proposed for its solution. One of the most studied and exploited is the maximization of the so called modularity, which represents the sum over all communities of the fraction of edges within these … Read more

    Unbounded Convex Sets for Non-Convex Mixed-Integer Quadratic Programming

  • Samuel Burer
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Polyhedra, Quadratic Programming Tags , , ,

    This paper introduces a fundamental family of unbounded convex sets that arises in the context of non-convex mixed-integer quadratic programming. It is shown that any mixed-integer quadratic program with linear constraints can be reduced to the minimisation of a linear function over a set in the family. Some fundamental properties of the convex sets are … Read more

    Trajectory-following methods for large-scale degenerate convex quadratic programming

  • Nicholas I. M. Gould
  • Dominique Orban
  • Daniel P. Robinson
    • Categories Optimization Software and Modeling Systems, Quadratic Programming Tags , ,

    We consider a class of infeasible, path-following methods for convex quadratric programming. Our methods are designed to be effective for solving both nondegerate and degenerate problems, where degeneracy is understood to mean the failure of strict complementarity at a solution. Global convergence and a polynomial bound on the number of iterations required is given. An … Read more

    Representing quadratically constrained quadratic programs as generalized copositive programs

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

    We show that any nonconvex quadratically constrained quadratic program(QCQP) can be represented as a generalized copositive program. In fact,we provide two representations. The first is based on the concept of completely positive (CP) matrices over second order cones, while the second is based on CP matrices over the positive semidefinte cone. Our analysis assumes that … Read more

    On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets

  • Gabriele Eichfelder
  • Janez Povh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , ,

    In the paper we prove that any nonconvex quadratic problem over some set $K\subset \mathbb{R}^n$ with additional linear and binary constraints can be rewritten as linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and … Read more