interior point methods

An interior Newton-like method for nonnegative least-squares problems with degenerate solution

  • Stefania Bellavia
  • Benedetta Morini
  • Maria Macconi
    • Categories Nonlinear Optimization Tags , , , ,

    An interior point approach for medium and large nonnegative linear least-squares problems is proposed. Global and locally quadratic convergence is shown even if a degenerate solution is approached. Viable approaches for implementation are discussed and numerical results are provided. CitationTechnical Report 1/2005, Dipartimento di Energetica ‘S. Stecco’, Universita di Firenze, ItaliaArticleDownload View PDF

    A conic interior point decomposition approach for large scale semidefinite programming

  • Gema Plaza
  • Kartik Krishnan Sivaramakrishnan
  • Tamás Terlaky
    • Categories Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    We describe a conic interior point decomposition approach for solving a large scale semidefinite programs (SDP) whose primal feasible set is bounded. The idea is to solve such an SDP using existing primal-dual interior point methods, in an iterative fashion between a {\em master problem} and a {\em subproblem}. In our case, the master problem … Read more

    Interior-Point Methods for Nonconvex Nonlinear Programming: Regularization and Warmstarts

  • Hande Benson
  • David F. Shanno
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper, we investigate the use of an exact primal-dual penalty approach within the framework of an interior-point method for nonconvex nonlinear programming. This approach provides regularization and relaxation, which can aid in solving ill-behaved problems and in warmstarting the algorithm. We present details of our implementation within the LOQO algorithm and provide extensive … Read more

    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