interior point methods

Erratum: A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with (\sqrt{n}L)hBciteration complexity

  • Florian A. Potra
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , ,

    We correct an error in Algorithm 2 from the paper with the same name that was published in Mathematical Programming, Ser. A, 100, 2(2004), 317–337. Citation submitted to Mathematical Programming Article Download View Erratum: A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with (sqrt{n}L)hBciteration complexity

    Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path

  • Xing Liu
  • Florian A. Potra
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , , ,

    Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path Citation Technical Report UMBC, TR2006-22, January 2005, Revised: March 2006. Article Download View Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path

    Constructing self-concordant barriers for convex cones

  • Yurii Nesterov
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we develop a technique for constructing self-concordant barriers for convex cones. We start from a simple proof for a variant of standard result on transformation of a $\nu$-self-concordant barrier for a set into a self-concordant barrier for its conic hull with parameter $(3.08 \sqrt{\nu} + 3.57)^2$. Further, we develop a convenient composition … Read more

    Towards nonsymmetric conic optimization

  • Yurii Nesterov
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper we propose a new interior-point method, which is based on an extension of the ideas of self-scaled optimization to the general cones. We suggest using the primal correction process to find a {\em scaling point}. This point is used to compute a strictly feasible primal-dual pair by simple projection. Then, we define … Read more

    Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path

  • Florian A. Potra
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming Tags , , ,

    Two corrector-predictor interior point algorithms are proposed for solving mono\-tone linear complementarity problems. The algorithms produce a sequence of iterates in the $\caln_{\infty}^{-}$ neighborhood of the central path. The first algorithm uses line search schemes requiring the solution of higher order polynomial equations in one variable, while the line search procedures of the second algorithm … Read more

    A local convergence property of primal-dual methods for nonlinear programming

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

    We prove a new local convergence property of a primal-dual method for solving nonlinear optimization problem. Following a standard interior point approach, the complementarity conditions of the original primal-dual system are perturbed by a parameter which is driven to zero during the iterations. The sequence of iterates is generated by a linearization of the perturbed … Read more

    Steplength Selection in Interior-Point Methods for Quadratic Programming

  • Frank E. Curtis
  • Jorge Nocedal
    • Categories Convex Optimization Tags , , , ,

    We present a new strategy for choosing primal and dual steplengths in a primal-dual interior-point algorithm for convex quadratic programming. Current implementations often scale steps equally to avoid increases in dual infeasibility between iterations. We propose that this method can be too conservative, while safeguarding an unequally-scaled steplength approach will often require fewer steps toward … Read more

    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. Citation Technical Report 1/2005, Dipartimento di Energetica ‘S. Stecco’, Universita di Firenze, Italia Article Download View … Read more

    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