interior point methods

SDPT3 – a MATLAB software package for semidefinite-quadratic-linear programming, version 3.0

  • Michael J. Todd
  • Kim-Chuan Toh
  • Reha H. Tütüncü
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , ,

    This software package is a MATLAB implementation of infeasible path-following algorithms for solving conic programming problems whose constraint cone is a product of semidefinite cones, second-order cones, and/or nonnegative orthants. It employs a predictor-corrector primal-dual path-following method, with either the HKM or the NT search direction. The basic code is written in Matlab, but key … Read more

    Global and Local Convergence of Line Search Filter Methods for Nonlinear Programming

  • Lorenz T. Biegler
  • Andreas Wächter
    • Categories Constrained Nonlinear Optimization Tags , , , , , , , , , ,

    Line search methods for nonlinear programming using Fletcher and Leyffer’s filter method, which replaces the traditional merit function, are proposed and their global and local convergence properties are analyzed. Previous theoretical work on filter methods has considered trust region algorithms and only the question of global convergence. The presented framework is applied to barrier interior … Read more

    On the Riemannian Geometry Defined by Self-Concordant Barriers and Interior-Point Methods

  • Yurii Nesterov
  • Michael J. Todd
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We consider the Riemannian geometry defined on a convex set by the Hessian of a self-concordant barrier function, and its associated geodesic curves. These provide guidance for the construction of efficient interior-point methods for optimizing a linear function over the intersection of the set with an affine manifold. We show that algorithms that follow the … Read more

    Polynomial interior point cutting plane methods

  • John E. Mitchell
    • Categories Cutting Plane Approaches, Linear Programming, Nonsmooth Optimization Tags , , ,

    Polynomial cutting plane methods based on the logarithmic barrier function and on the volumetric center are surveyed. These algorithms construct a linear programming relaxation of the feasible region, find an appropriate approximate center of the region, and call a separation oracle at this approximate center to determine whether additional constraints should be added to the … Read more

    On the convergence of the central path in semidefinite optimization

  • Etienne de Klerk
  • Margaréta Halická
  • Cornelis Roos
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    The central path in linear optimization always converges to the analytic center of the optimal set. This result was extended to semidefinite programming by Goldfarb and Scheinberg (SIAM J. Optim. 8: 871-886, 1998). In this paper we show that this latter result is not correct in the absence of strict complementarity. We provide a counterexample, … Read more

    An Interior-Point Perspective on Sensitivity Analysis in Semidefinite Programming

  • E. Alper Yildirim
    • Categories Semi-definite Programming Tags , ,

    We study the asymptotic behavior of the interior-point bounds arising from the work of Yildirim and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. For perturbations of the right-hand side vector and the cost matrix, we show that the interior-point bounds evaluated on the central path using the Monteiro-Zhang … Read more

    A Computational Study of a Gradient-Based Log-Barrier Algorithm for a Class of Large-Scale SDPs

  • Samuel Burer
  • Renato D.C. Monteiro
  • Yin Zhang
    • Categories Combinatorial Optimization, Semi-definite Programming, Unconstrained Optimization Tags , , , ,

    The authors of this paper recently introduced a transformation \cite{BuMoZh99-1} that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based … Read more

    Properties of the Log-Barrier Function on Degenerate Nonlinear Programs

  • Dominique Orban
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization Tags , , ,

    We examine the sequence of local minimizers of the log-barrier function for a nonlinear program near a solution at which second-order sufficient conditions and the Mangasarian-Fromovitz constraint qualifications are satisfied, but the active constraint gradients are not necessarily linearly independent. When a strict complementarity condition is satisfied, we show uniqueness of the local minimizer of … Read more

    On the Convergence of Newton Iterations to Non-Stationary Points

  • Richard H. Byrd
  • Marcelo Marazzi
  • Jorge Nocedal
    • Categories Nonlinear Optimization, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , ,

    We study conditions under which line search Newton methods for nonlinear systems of equations and optimization fail due to the presence of singular non-stationary points. These points are not solutions of the problem and are characterized by the fact that Jacobian or Hessian matrices are singular. It is shown that, for systems of nonlinear equations, … Read more

    Analyticity of the central path at the boundary point in semidefinite programming

  • Margaréta Halická
    • Categories Semi-definite Programming Tags , ,

    In this paper we study the limiting behavior of the central path for semidefinite programming. We show that the central path is an analytic function of the barrier parameter even at the limit point, provided that the semidefinite program has a strictly complementary solution. A consequence of this property is that the derivatives – of … Read more