Quadratic Programming

Newton–Picard-Based Preconditioning for Linear-Quadratic Optimization Problems with Time-Periodic Parabolic PDE Constraints

  • Hans Georg Bock
  • Andreas Potschka
  • M.S. Mommer
  • Johannes P. Schlöder
    • Categories Optimization of Systems modeled by PDEs, Quadratic Programming Tags , , , ,

    We develop and investigate two preconditioners for a basic linear iterative splitting method for the numerical solution of linear-quadratic optimization problems with time-periodic parabolic PDE constraints. The resulting real-valued linear system to be solved is symmetric indefinite. We propose all-at-once symmetric indefinite preconditioners based on a Newton–Picard approach which divides the variable space into slow … Read more

    On Duality Gap in Binary Quadratic Programming

  • Jianjun Gao
  • Duan Li
  • Chunli Liu
  • Xiaoling Sun
    • Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming

    We present in this paper new results on the duality gap between the binary quadratic optimization problem and its Lagrangian dual or semidefinite programming relaxation. We first derive a necessary and sufficient condition for the zero duality gap and discuss its relationship with the polynomial solvability of the primal problem. We then characterize the zeroness … Read more

    A Factorization with Update Procedures for a KKT Matrix Arising in Direct Optimal Control

  • Hans Georg Bock
  • Christian Kirches
  • Sebastian Sager
  • Johannes P. Schlöder
    • Categories Quadratic Programming, Systems governed by Differential Equations Optimization Tags , ,

    Quadratic programs obtained for optimal control problems of dynamic or discrete–time processes usually involve highly block structured Hessian and constraints matrices. Efficient numerical methods for the solution of such QPs have to respect and exploit this block structure. In interior point methods, this is elegantly achieved by the widespread availability of advanced sparse symmetric indefinite … Read more

    Matrix-Free Interior Point Method

  • Jacek Gondzio
    • Categories Linear Programming, Quadratic Programming Tags , , , , ,

    In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods … Read more

    Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides

  • Osman Y. Ozaltin
  • Oleg A. Prokopyev
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Stochastic Programming Tags , , ,

    We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We fi rst derive some basic properties of value functions of quadratic integer programs. We then propose a two-phase solution approach. The first phase constructs the value functions of quadratic integer programs in both stages. The second phase … Read more

    Block Structured Quadratic Programming for the Direct Multiple Shooting Method for Optimal Control

  • Hans Georg Bock
  • Christian Kirches
  • Sebastian Sager
  • Johannes P. Schlöder
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Systems governed by Differential Equations Optimization Tags , ,

    In this contribution we address the efficient solution of optimal control problems of dynamic processes with many controls. Such problems arise, e.g., from the outer convexification of integer control decisions. We treat this optimal control problem class using the direct multiple shooting method to discretize the optimal control problem. The resulting nonlinear problems are solved … Read more

    Starting-Point Strategies for an Infeasible Potential Reduction Method

  • Marco D'Apuzzo
  • Valentina De Simone
  • Daniela di Serafino
    • Categories Quadratic Programming Tags , ,

    We present two strategies for choosing a “hot” starting-point in the context of an infeasible Potential Reduction (PR) method for convex Quadratic Programming. The basic idea of both strategies is to select a preliminary point and to suitably scale it in order to obtain a starting point such that its nonnegative entries are sufficiently bounded … Read more

    A practical method for solving large-scale TRS

  • Marianna S. Apostolopoulou
  • C.A. Botsaris
  • Panagiotis Pintelas
  • Dimitris G. Sotiropoulos
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Quadratic Programming Tags , , , , ,

    We present a nearly-exact method for the large scale trust region subproblem (TRS) based on the properties of the minimal-memory BFGS method. Our study in concentrated in the case where the initial BFGS matrix can be any scaled identity matrix. The proposed method is a variant of the Mor\'{e}-Sorensen method that exploits the eigenstructure of … Read more

    On solving trust-region and other regularised subproblems in optimization

  • Sue Dollar
  • Nicholas I. M. Gould
  • Daniel P. Robinson
    • Categories Optimization Software and Modeling Systems, Quadratic Programming, Unconstrained Optimization Tags , ,

    The solution of trust-region and regularisation subproblems which arise in unconstrained optimization is considered. Building on the pioneering work of Gay, More’ and Sorensen, methods which obtain the solution of a sequence of parametrized linear systems by factorization are used. Enhancements using high-order polynomial approximation and inverse iteration ensure that the resulting method is both … Read more

    Hybrid MPI/OpenMP parallel support vector machine training

  • Jacek Gondzio
  • Kristian Woodsend
    • Categories Data-Mining, Parallel Algorithms, Quadratic Programming Tags , , ,

    Support Vector Machines are a powerful machine learning technology, but the training process involves a dense quadratic optimization problem and is computationally challenging. A parallel implementation of Support Vector Machine training has been developed, using a combination of MPI and OpenMP. Using an interior point method for the optimization and a reformulation that avoids the … Read more