Quadratic Programming

Generalized Conjugate Gradient Methods for $\ell_1$ Regularized Convex Quadratic Programming with Finite Convergence

  • Xiaojun Chen
  • Zhaosong Lu
    • Categories Convex Optimization, Nonsmooth Optimization, Quadratic Programming Tags , , , ,

    The conjugate gradient (CG) method is an efficient iterative method for solving large-scale strongly convex quadratic programming (QP). In this paper we propose some generalized CG (GCG) methods for solving the $\ell_1$-regularized (possibly not strongly) convex QP that terminate at an optimal solution in a finite number of iterations. At each iteration, our methods first … Read more

    Robust Sensitivity Analysis of the Optimal Value of Linear Programming

  • Samuel Burer
  • Guanglin Xu
    • Categories Quadratic Programming, Robust Optimization, Semi-definite Programming Tags , , , , ,

    We propose a framework for sensitivity analysis of linear programs (LPs) in minimiza- tion form, allowing for simultaneous perturbations in the objective coefficients and right-hand sides, where the perturbations are modeled in a compact, convex uncertainty set. This framework unifies and extends multiple approaches for LP sensitivity analysis in the literature and has close ties … Read more

    The Uncapacitated Single Allocation p-Hub Median Problem with Stepwise Cost Function

  • Christoph Buchheim
  • Borzou Rostami
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Quadratic Programming Tags , ,

    In this paper, we address a new version of the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP) in which transportation costs on each edge are given by piecewise constant cost functions. In the classical USApHMP, transportation costs are modelled as linear functions of the transport volume, where a fixed discount factor on hub-hub connections is … Read more

    Solving the Probabilistic Traveling Salesman Problem by Linearising a Quadratic Approximation

  • Uwe Clausen
  • J. Fabian Meier
    • Categories Integer Programming, Quadratic Programming, Transportation

    The Probabilistic Traveling Salesman Problem, introduced in 1985 by Jaillet, is one of the fundamental stochastic versions of the Traveling Salesman Problem: After the tour is chosen, each vertex is deleted with given probability 1-p. The eliminated vertices are bypassed which leads to shorter tours. The aim is to minimize the expected tour length. The … Read more

    A Binarisation Heuristic for Non-Convex Quadratic Programming with Box Constraints

  • Laura Galli
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming

    Non-convex quadratic programming with box constraints is a fundamental problem in the global optimization literature, being one of the simplest NP-hard nonlinear programs. We present a new heuristic for this problem, which enables one to obtain solutions of excellent quality in reasonable computing times. The heuristic consists of four phases: binarisation, convexification, branch-and-bound, and local … Read more

    Active-Set Methods for Convex Quadratic Programming

  • Anders Forsgren
  • Philip E. Gill
  • Elizabeth Wong
    • Categories Convex Optimization, Quadratic Programming Tags , , , , , ,

    Computational methods are proposed for solving a convex quadratic program (QP). Active-set methods are defined for a particular primal and dual formulation of a QP with general equality constraints and simple lower bounds on the variables. In the first part of the paper, two methods are proposed, one primal and one dual. These methods generate … Read more

    Solving Classical and New Single Allocation Hub Location Problems on Euclidean Data

  • Uwe Clausen
  • J. Fabian Meier
    • Categories (Mixed) Integer Linear Programming, Quadratic Programming, Transportation

    Transport networks with hub structure organise the exchange of shipments between many sources and sinks. All sources and sinks are connected to a small number of hubs which serve as transhipment points, so that only few, strongly consolidated transport relations exist. While hubs and detours lead to additional costs, the savings from bundling shipments, i.e. … Read more

    On the equivalence of the method of conjugate gradients and quasi-Newton methods on quadratic problems

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

    In this paper we state necessary and sufficient conditions for equivalence of the method of conjugate gradients and quasi-Newton methods on a quadratic problem. We show that the set of quasi-Newton schemes that generate parallel search directions to those of the method of conjugate gradients is strictly larger than the one-parameter Broyden family. In addition, … Read more

    Copositivity for second-order optimality conditions in general smooth optimization problems

  • Immanuel M. Bomze
    • Categories Constrained Nonlinear Optimization, Quadratic Programming Tags , , , ,

    Second-order local optimality conditions involving copositivity of the Hessian of the Lagrangian on the reduced linearization cone have the advantage that there is only a small gap between sufficient (the Hessian is strictly copositive) and necessary (the Hessian is copositive) conditions. In this respect, this is a proper generalization of convexity of the Lagrangian. We … Read more

    A Fast Branch-and-Bound Algorithm for Non-convex Quadratic Integer Optimization Subject To Linear Constraints Using Ellipsoidal Relaxations

  • Christoph Buchheim
  • Marianna De Santis
  • Laura Palagi
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming

    We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set. In the first approach, we intersect the ellipsoids with the feasible linear subspace. In the second approach we penalize exactly the linear constraints. We investigate the connection between … Read more