quadratic programming

Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs

  • Michael P. Friedlander
  • Sven Leyffer
    • Categories Quadratic Programming Tags , , , , ,

    We present a two-phase algorithm for solving large-scale quadratic programs (QPs). In the first phase, gradient-projection iterations approximately minimize an augmented Lagrangian function and provide an estimate of the optimal active set. In the second phase, an equality-constrained QP defined by the current inactive variables is approximately minimized in order to generate a second-order search … Read more

    Steplength Selection in Interior-Point Methods for Quadratic Programming

  • Frank E. Curtis
  • Jorge Nocedal
    • Categories Convex Optimization Tags , , , ,

    We present a new strategy for choosing primal and dual steplengths in a primal-dual interior-point algorithm for convex quadratic programming. Current implementations often scale steps equally to avoid increases in dual infeasibility between iterations. We propose that this method can be too conservative, while safeguarding an unequally-scaled steplength approach will often require fewer steps toward … Read more

    Further Development of Multiple Centrality Correctors for Interior Point Methods

  • Marco Colombo
  • Jacek Gondzio
    • Categories Linear Programming Tags , , ,

    This paper addresses the role of centrality in the implementation of interior point methods. Theoretical arguments are provided to justify the use of a symmetric neighbourhood. These are translated into computational practice leading to a new insight into the role of re-centering in the implementation of interior point methods. Arguments are provided to show that … Read more

    Complex Matrix Decomposition and Quadratic Programming

  • Yongwei Huang
  • Shuzhong Zhang
    • Categories Semi-definite Programming Tags , , ,

    This paper studies the possibilities of the Linear Matrix Inequality (LMI) characterization of the matrix cones formed by nonnegative complex Hermitian quadratic functions over specific domains in the complex space. In its real case analog, such studies were conducted in Sturm and Zhang in 2003. In this paper it is shown that stronger results can … Read more

    Efficient and cheap bounds for (standard) quadratic optimization

  • Immanuel M. Bomze
  • Marco Locatelli
  • F. Tardella
    • Categories Global Optimization Applications, Quadratic Programming Tags , , , ,

    A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. A number of problems can be transformed into a StQP, including the general quadratic problem over a polytope and the maximum clique problem in a graph. In this paper we present several polynomial-time bounds for StQP ranging from very simple … Read more

    Sensitivity analysis in convex quadratic optimization: simultaneous perturbation of the objective and right-hand-side vectors

  • Alireza Ghaffari Hadigheh
  • Oleksandr Romanko
  • Tamás Terlaky
    • Categories Finance and Economics, Linear Programming, Quadratic Programming Tags , , , , , ,

    In this paper we study the behavior of Convex Quadratic Optimization problems when variation occurs simultaneously in the right-hand side vector of the constraints and in the coefficient vector of the linear term in the objective function. It is proven that the optimal value function is piecewise-quadratic. The concepts of transition point and invariancy interval … Read more

    A branch and cut algorithm for solving the linear and quadratic integer programming problems

  • Fei Pusheng
  • Yan Zizong
  • Wan Zhongping
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Integer Programming Tags , , , ,

    This paper first presents an improve cutting plane method for solving the linear programming problems, based on the primal simplex method with the current equivalent facet technique, in which the increment of objection function is allowed as a pivot variable to decide the search step size. We obtain a strong valid inequality from the objective … Read more

    Set Intersection Theorems and Existence of Optimal Solutions

  • Dimitri Bertsekas
  • Paul Tseng
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , ,

    The question of nonemptiness of the intersection of a nested sequence of closed sets is fundamental in a number of important optimization topics, including the existence of optimal solutions, the validity of the minimax inequality in zero sum games, and the absence of a duality gap in constrained optimization. We introduce the new notion of … Read more

    Recovering Risk-Neutral Probability Density Functions from Options Prices using Cubic Splines

  • Ana M. Monteiro
  • Reha H. Tütüncü
  • Luis Nunes Vicente
    • Categories Finance and Economics, Quadratic Programming, Semi-definite Programming Tags , , , ,

    We present a new approach to estimate the risk-neutral probability density function (pdf) of the future prices of an underlying asset from the prices of options written on the asset. The estimation is carried out in the space of cubic spline functions, yielding appropriate smoothness. The resulting optimization problem, used to invert the data and … Read more