Quadratic Programming

Trust your data or not – StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization

  • Immanuel M. Bomze
  • Michael Kahr
  • Markus Leitner
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

    We consider the Robust Standard Quadratic Optimization Problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is extremized over the standard simplex. Following most approaches, we model the uncertainty sets by ellipsoids, polyhedra, or spectrahedra, more precisely, by intersections of sub-cones of the copositive matrix cone. We show that the copositive relaxation gap of … Read more

    Solving Quadratic Programs to High Precision using Scaled Iterative Refinement

  • Ambros Gleixner
  • Sebastian Sager
  • Tobias Weber
    • Categories Quadratic Programming Tags , , ,

    Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement … Read more

    Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs

  • Samuel Burer
  • Yinyu Ye
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , ,

    We study a class of quadratically constrained quadratic programs (QCQPs), called {\em diagonal QCQPs\/}, which contain no off-diagonal terms $x_j x_k$ for $j \ne k$, and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature … Read more

    MILP feasibility by nonlinear programming

  • Leo Liberti
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Quadratic Programming Tags , ,

    We discuss a tightly feasible mixed-integer linear programs arising in the energy industry, for which branch-and-bound appears to be ineffective. We consider its hardness, measure the probability that randomly generated instances are feasible or almost feasible, and introduce heuristic solution methods based on relaxing different constraints of the problem. We show the computational efficiency of … Read more

    Efficient Convex Optimization for Linear MPC

  • Stephen Wright
    • Categories Control Applications, Quadratic Programming Tags ,

    Model predictive control (MPC) formulations with linear dynamics and quadratic objectives can be solved efficiently by using a primal-dual interior-point framework, with complexity proportional to the length of the horizon. An alternative, which is more able to exploit the similarity of the problems that are solved at each decision point of linear MPC, is to … Read more

    The extensions of Yuan’s lemma and applications in S-lemma

  • Qingzhi Yang
  • Wang Zhongwen
  • Yang Zhou
    • Categories Quadratic Programming

    In this paper we extend a lemma due to Yuan from several aspects. A new proof of Yuan’s lemma is given. A rank-one decomposition of positive semidefinite matrix is further developed. With the extended rank-one de- composition results, we generalize the Yuan’s lemma to general quadratic function systems, interval quadratic function systems and quadratic matrix … Read more

    Probabilistic Variational Formulation of Binary Programming

  • Juan Banda
  • Arturo Berrones
  • Jonás Velasco
    • Categories 0-1 Programming, Quadratic Programming Tags , ,

    A probabilistic framework for large classes of binary integer programming problems is constructed. The approach is given by a mean field annealing scheme where the annealing phase is substituted by the solution of a dual problem that gives a lower (upper) bound for the original minimization (maximization) integer task. This bound has an information theoretic … Read more

    From Estimation to Optimization via Shrinkage

  • Gérard Cornuéjols
  • Danial Davarnia
    • Categories Quadratic Programming, Statistics, Stochastic Programming Tags , , , ,

    We study a class of quadratic stochastic programs where the distribution of random variables has unknown parameters. A traditional approach is to estimate the parameters using a maximum likelihood estimator (MLE) and to use this as input in the optimization problem. For the unconstrained case, we show that an estimator that “shrinks” the MLE towards … Read more

    Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra

  • Alper Atamturk
  • Andrés Gómez
    • Categories Quadratic Programming, Robust Optimization, Second-Order Cone Programming Tags ,

    We consider minimizing a conic quadratic objective over a polyhedron. Such problems arise in parametric value-at-risk minimization, portfolio optimization, and robust optimization with ellipsoidal objective uncertainty; and they can be solved by polynomial interior point algorithms for conic quadratic optimization. However, interior point algorithms are not well-suited for branch-and-bound algorithms for the discrete counterparts of … Read more

    SDP-based Branch-and-Bound for Non-convex Quadratic Integer Optimization

  • Christoph Buchheim
  • Maribel Montenegro
  • Angelika Wiegele
    • Categories Quadratic Programming, Semi-definite Programming Tags , ,

    Semidefinite programming (SDP) relaxations have been intensively used for solving discrete quadratic optimization problems, in particular in the binary case. For the general non-convex integer case with box constraints, the branch-and-bound algorithm Q-MIST has been proposed [11], which is based on an extension of the well-known SDP-relaxation for max-cut. For solving the resulting SDPs, Q-MIST … Read more