interior point methods

On the Implementation of Interior Point Decomposition Algorithms for Two-Stage Stochastic Conic

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Finance and Economics, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    In this paper we develop a practical primal interior decomposition algorithm for two-stage stochastic programming problems. The framework of this algorithm is similar to the framework in Mehrotra and \”{Ozevin} \cite{MO04a,MO04b} and Zhao \cite{GZ01}, however their algorithm is altered in a simple yet fundamental way to achieve practical performance. In particular, this new algorithm weighs … 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

    Dynamic updates of the barrier parameter in primal-dual methods for nonlinear programming

  • Paul Armand
  • Dominique Orban
  • Joël Benoist
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    We introduce a framework in which updating rules for the barrier parameter in primal-dual interior-point methods become dynamic. The original primal-dual system is augmented to incorporate explicitly an updating function. A Newton step for the augmented system gives a primal-dual Newton step and also a step in the barrier parameter. Based on local information and … Read more

    A strong bound on the integral of the central path curvature and its relationship with the iteration complexity of primal-dual path-following LP algorithms

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , , , , , , , ,

    The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and … Read more

    A Homogeneous Model for Mixed Complementarity Problems over Symmetric Cones

  • Yedong Lin
  • Akiko Yoshise
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , , ,

    In this paper, we propose a homogeneous model for solving monotone mixed complementarity problems over symmetric cones, by extending the results in \cite{YOSHISE04} for standard form of the problems. We show that the extended model inherits the following desirable features: (a) A path exists, is bounded and has a trivial starting point without any regularity … Read more

    An Exact Primal-Dual Penalty Method Approach to Warmstarting Interior-Point Methods for Linear Programming

  • Hande Benson
  • David F. Shanno
    • Categories Linear Programming Tags , , ,

    One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal-dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set … Read more

    Knitro: An Integrated Package for Nonlinear Optimization

  • Richard H. Byrd
  • Jorge Nocedal
  • Richard A. Waltz
    • Categories Nonlinear Optimization, Optimization Software and Modeling Systems Tags , ,

    This paper describes Knitro 5.0, a C-package for nonlinear optimization that combines complementary approaches to nonlinear optimization to achieve robust performance over a wide range of application requirements. The package is designed for solving large-scale, smooth nonlinear programming problems, and it is also effective for the following special cases: unconstrained optimization, nonlinear systems of equations, … Read more

    Generalized Support Set Invariancy Sensitivity Analysis

  • Alireza Ghaffari Hadigheh
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , , , ,

    Support set invariancy sensitivity analysis deals with finding the range of the parameter variation where there are optimal solutions with the same positive variables for all parameter values throughout this range. This approach to sensitivity analysis has been studied for Linear Optimization (LO) and Convex Quadratic Optimization (CQO) problems, when they are in standard form. … Read more

    An Iterative Solver-Based Long-Step Infeasible Primal-Dual Path-Following Algorithm for Convex QP Based on a Class of Preconditioners

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Jerome W. O'Neal
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , , ,

    In this paper we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors’ previous paper \cite{ONE04}, we propose a new linear system, which we refer to as the \emph{hybrid augmented normal equation} (HANE), to … Read more

    Enlarging Neighborhoods of Interior-Point Algorithms for Linear Programming via Least Values of Proximity measure Functions

  • Yun-Bin Zhao
    • Categories Linear Programming Tags , , ,

    It is well known that a wide-neighborhood interior-point algorithm for linear programming performs much better in implementation than those small-neighborhood counterparts. In this paper, we provide a unified way to enlarge the neighborhoods of predictor-corrector interior-point algorithms for linear programming. We prove that our methods not only enlarge the neighborhoods but also retain the so-far … Read more