interior point methods

Worst-case convergence analysis of gradient and Newton methods through semidefinite programming performance estimation

  • Etienne de Klerk
  • François Glineur
  • Adrien B. Taylor
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    We provide new tools for worst-case performance analysis of the gradient (or steepest descent) method of Cauchy for smooth strongly convex functions, and Newton’s method for self-concordant functions. The analysis uses semidefinite programming performance estimation, as pioneered by Drori en Teboulle [Mathematical Programming, 145(1-2):451–482, 2014], and extends recent performance estimation results for the method of … Read more

    On the behavior of Lagrange multipliers in convex and non-convex infeasible interior point methods

  • Gabriel Haeser
  • Yinyu Ye
  • Oliver Hinder
    • Categories Nonlinear Optimization Tags , , , ,

    This paper analyzes sequences generated by infeasible interior point methods. In convex and non-convex settings, we prove that moving the primal feasibility at the same rate as complementarity will ensure that the Lagrange multiplier sequence will remain bounded, provided the limit point of the primal sequence has a Lagrange multiplier, without constraint qualification assumptions. We … Read more

    A rounding procedure for semidefinite optimization

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Semi-definite Programming Tags , , ,

    Recently, Mohammad-Nezhad and Terlaky studied the identification of the optimal partition for semidefinite optimization. An approximation of the optimal partition was obtained from a bounded sequence of solutions on, or in a neighborhood of the central path. Here, we use the approximation of the optimal partition in a rounding procedure to generate an approximate maximally … Read more

    A logarithmic barrier interior-point method based on majorant functions for second-order cone programming

  • Baha Alzalg
    • Categories Second-Order Cone Programming Tags , , , ,

    We present a logarithmic barrier interior-point method for solving a second-order cone programming problem. Newton’s method is used to compute the descent direction, and majorant functions are used as an efficient alternative to line search methods to determine the displacement step along the direction. The efficiency of our method is shown by presenting numerical experiments. … Read more

    A primal-dual interior-point method based on various selections of displacement step for second-order cone programming

  • Baha Alzalg
    • Categories Second-Order Cone Programming Tags , , , ,

    In this paper, a primal-dual interior-point method equipped with various selections of the displacement step are derived for solving second-order cone programming problems. We first establish the existence and uniqueness of the optimal solution of the corresponding perturbed problem and then demonstrate its convergence to the optimal solution of the original problem. Next, we present … Read more

    Warm-start of interior point methods for second order cone optimization via rounding over optimal Jordan frames

  • Sertalp B. Çay
  • Imre Pólik
  • Tamás Terlaky
    • Categories Branch and Cut Algorithms, Second-Order Cone Programming Tags , , , ,

    Interior point methods (IPM) are the most popular approaches to solve Second Order Cone Optimization (SOCO) problems, due to their theoretical polynomial complexity and practical performance. In this paper, we present a warm-start method for primal-dual IPMs to reduce the number of IPM steps needed to solve SOCO problems that appear in a Branch and … Read more

    Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary

  • Gabriel Haeser
  • Yinyu Ye
  • Hongcheng Liu
    • Categories Nonlinear Optimization Tags , , , ,

    In this paper we consider the minimization of a continuous function that is potentially not differentiable or not twice differentiable on the boundary of the feasible region. By exploiting an interior point technique, we present first- and second-order optimality conditions for this problem that reduces to classical ones when the derivative on the boundary is … Read more

    Optimization Techniques for Tree-Structured Nonlinear Problems

  • Jens Hübner
  • Martin Schmidt
  • Marc C. Steinbach
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , ,

    Robust model predictive control approaches and other applications lead to nonlinear optimization problems defined on (scenario) trees. We present structure-preserving Quasi-Newton update formulas as well as structured inertia correction techniques that allow to solve these problems by interior-point methods with specialized KKT solvers for tree-structured optimization problems. The same type of KKT solvers could be … Read more

    BFGS-like updates of constraint preconditioners for sequences of KKT linear systems

  • Luca Bergamaschi
  • Valentina De Simone
  • Daniela di Serafino
  • Angeles Martinez
    • Categories Nonlinear Optimization, Quadratic Programming Tags

    We focus on efficient preconditioning techniques for sequences of KKT linear systems arising from the interior point solution of large convex quadratic programming problems. Constraint Preconditioners (CPs), though very effective in accelerating Krylov methods in the solution of KKT systems, have a very high computational cost in some instances, because their factorization may be the … Read more

    An inexact potential reduction method for linear programming

  • Jacek Gondzio
  • Lukas Schork
    • Categories Linear Programming Tags , ,

    A class of interior point methods using inexact directions is analysed. The linear system arising in interior point methods for linear programming is reformulated such that the solution is less sensitive to perturbations in the right-hand side. For the new system an implementable condition is formulated that controls the relative error in the solution. Based … Read more