interior point methods

An Interior-Point Method for Nonlinear Optimization Problems with Locatable and Separable Nonsmoothness

  • Martin Schmidt
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    A lot of real-world optimization models comprise nonconvex and nonlinear as well as nonsmooth functions leading to very hard classes of optimization models. In this article a new interior-point method for the special but practically relevant class of optimization problems with locatable and separable nonsmooth aspects is presented. After motivating and formalizing the problems under … Read more

    On the update of constraint preconditioners for regularized KKT systems

  • Stefania Bellavia
  • Valentina De Simone
  • Daniela di Serafino
  • Benedetta Morini
    • Categories Nonlinear Optimization, Quadratic Programming Tags , , ,

    We address the problem of preconditioning sequences of regularized KKT systems, such as those arising in Interior Point methods for convex quadratic programming. In this case, Constraint Preconditioners (CPs) are very effective and widely used; however, when solving large-scale problems, the computational cost for their factorization may be high, and techniques for approximating them appear … Read more

    An improved and simplified full-Newton step O(n) infeasible interior-point method for Linear Optimization

  • Cornelis Roos
    • Categories Linear Programming Tags , , , ,

    We present an improved version of an infeasible interior-point method for linear optimization published in 2006. In the earlier version each iteration consisted of one so-called infeasibility step and a few – at most three – centering steps. In this paper each iteration consists of only a infeasibility step, whereas the iteration bound improves the … Read more

    An Interior-Point Trust-Funnel Algorithm for Nonlinear Optimization

  • Frank E. Curtis
  • Nicholas I. M. Gould
  • Daniel P. Robinson
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , ,

    We present an interior-point trust-funnel algorithm for solving large-scale nonlinear optimization problems. The method is based on an approach proposed by Gould and Toint (Math Prog 122(1):155–196, 2010) that focused on solving equality constrained problems. Our method is similar in that it achieves global convergence guarantees by combining a trust-region methodology with a funnel mechanism, … Read more

    Updating constraint preconditioners for KKT systems in quadratic programming via low-rank corrections

  • Stefania Bellavia
  • Valentina De Simone
  • Daniela di Serafino
  • Benedetta Morini
    • Categories Quadratic Programming Tags , , , ,

    This work focuses on the iterative solution of sequences of KKT linear systems arising in interior point methods applied to large convex quadratic programming problems. This task is the computational core of the interior point procedure and an efficient preconditioning strategy is crucial for the efficiency of the overall method. Constraint preconditioners are very effective … Read more

    Fast implementation for semidefinite programs with positive matrix completion

  • Kazuhide Nakata
  • Makoto Yamashita
    • Categories Parallel Algorithms, Semi-definite Programming Tags , , ,

    Solving semidefinite programs (SDP) in a short time is the key to managing various mathematical optimization problems in practical time. The matrix-completion primal-dual interior-point method (MC-PDIPM) extracts a structural sparsity of input SDP by factorizing the variable matrices, and it shrinks the computation time. In this paper, we propose a new factorization based on the … Read more

    Large-scale optimization with the primal-dual column generation method

  • Jacek Gondzio
  • Pedro Munari
  • Pablo Gonzalez-Brevis
    • Categories Convex Optimization, Linear Programming, Optimization Software and Modeling Systems Tags , , , , , ,

    The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation. A reduction in the number of calls … Read more

    A Polynomial Time Constraint-Reduced Algorithm for Semidefinite Optimization Problems, with Convergence Proofs

  • Dianne P. O'Leary
  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , , , , , , ,

    We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction … Read more

    A Primal-Dual Regularized Interior-Point Method for Semidefinite Programming

  • Ahad Dehghani
  • Jean-Louis Goffin
  • Dominique Orban
    • Categories Semi-definite Programming Tags , , , , ,

    Interior-point methods in semidefinite programming (SDP) require the solution of a sequence of linear systems which are used to derive the search directions. Safeguards are typically required in order to handle rank-deficient Jacobians and free variables. We generalize the primal-dual regularization of \cite{friedlander-orban-2012} to SDP and show that it is possible to recover an optimal … Read more

    Primal-dual relationship between Levenberg-Marquardt and central trajectories for linearly constrained convex optimization

  • Roger Behling
  • Clóvis Caesar Gonzaga
  • Gabriel Haeser
    • Categories Convex Optimization, Quadratic Programming Tags , , , , , ,

    We consider the minimization of a convex function on a compact polyhedron defined by linear equality constraints and nonnegative variables. We define the Levenberg-Marquardt (L-M) and central trajectories starting at the analytic center and using the same parameter, and show that they satisfy a primal-dual relationship, being close to each other for large values of … Read more