interior point methods

A Polynomial-Time Affine-Scaling Method for Semidefinite and Hyperbolic Programming

  • James Renegar
  • Mutiara Sondjaja
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We develop a natural variant of Dikin’s affine-scaling method, first for semidefinite programming and then for hyperbolic programming in general. We match the best complexity bounds known for interior-point methods. All previous polynomial-time affine-scaling algorithms have been for conic optimization problems in which the underlying cone is symmetric. Hyperbolicity cones, however, need not be symmetric. … Read more

    Sufficient weighted complementarity problems

  • Florian A. Potra
    • Categories Complementarity and Variational Inequalities Tags , , ,

    This paper presents some fundamental results about sufficient linear weighted complementarity problems. Such a problem depends on a nonnegative weight vector. If the weight vector is zero, the problem reduces to a sufficient linear complementarity problem that has been extensively studied. The introduction of the more general notion of a weighted complementarity problem (wCP) was … Read more

    A Feasible Direction Algorithm for Nonlinear Second-Order Cone Optimization Problems

  • Alfredo Canelas
  • Miguel Carrasco
  • Julio López
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications Tags , , ,

    In this work we present a new feasible direction algorithm for solving smooth nonlinear second-order cone programs. These problems consist of minimizing a nonlinear di erentiable objective function subject to some nonlinear second-order cone constraints. Given a point interior to the feasible set de nfined by the nonlinear constraints, the proposed approach computes a feasible and descent … Read more

    A tight iteration-complexity upper bound for the MTY predictor-corrector algorithm via redundant Klee-Minty cubes

  • Murat Mut
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , , ,

    It is an open question whether there is an interior-point algorithm for linear optimization problems with a lower iteration-complexity than the classical bound $\mathcal{O}(\sqrt{n} \log(\frac{\mu_1}{\mu_0}))$. This paper provides a negative answer to that question for a variant of the Mizuno-Todd-Ye predictor-corrector algorithm. In fact, we prove that for any $\epsilon >0$, there is a redundant … Read more

    A comparison of reduced and unreduced KKT systems arising from Interior Point methods

  • Benedetta Morini
  • Valeria Simoncini
  • Mattia Tani
    • Categories Quadratic Programming Tags , , ,

    We address the iterative solution of symmetric KKT systems arising in the solution of convex quadratic programming problems. Two strictly related and well established formulations for such systems are studied with particular emphasis on the effect of preconditioning strategies on their relation. Constraint and augmented preconditioners are considered, and the choice of the augmentation Matrix … Read more

    Active-set prediction for interior point methods using controlled perturbations

  • Coralia Cartis
  • Yiming Yan
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    We propose the use of controlled perturbations to address the challenging question of optimal active-set prediction for interior point methods. Namely, in the context of linear programming, we consider perturbing the inequality constraints/bounds so as to enlarge the feasible set. We show that if the perturbations are chosen appropriately, the solution of the original problem … Read more

    Spectral estimates for unreduced symmetric KKT systems arising from Interior Point methods

  • Benedetta Morini
  • Valeria Simoncini
  • Mattia Tani
    • Categories Quadratic Programming Tags , , , ,

    We consider symmetrized KKT systems arising in the solution of convex quadratic programming problems in standard form by Interior Point methods. Their coefficient matrices usually have 3×3 block structure and, under suitable conditions on both the quadratic programming problem and the solution, they are nonsingular in the limit. We present new spectral estimates for these … Read more

    An Interior-Point Method for Nonlinear Optimization Problems with Locatable and Separable Nonsmoothness

  • Martin Schmidt
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    A lot of real-world optimization models comprise nonconvex and nonlinear as well as nonsmooth functions leading to very hard classes of optimization models. In this article a new interior-point method for the special but practically relevant class of optimization problems with locatable and separable nonsmooth aspects is presented. After motivating and formalizing the problems under … Read more

    On the update of constraint preconditioners for regularized KKT systems

  • Stefania Bellavia
  • Valentina De Simone
  • Daniela di Serafino
  • Benedetta Morini
    • Categories Nonlinear Optimization, Quadratic Programming Tags , , ,

    We address the problem of preconditioning sequences of regularized KKT systems, such as those arising in Interior Point methods for convex quadratic programming. In this case, Constraint Preconditioners (CPs) are very effective and widely used; however, when solving large-scale problems, the computational cost for their factorization may be high, and techniques for approximating them appear … Read more

    An improved and simplified full-Newton step O(n) infeasible interior-point method for Linear Optimization

  • Cornelis Roos
    • Categories Linear Programming Tags , , , ,

    We present an improved version of an infeasible interior-point method for linear optimization published in 2006. In the earlier version each iteration consisted of one so-called infeasibility step and a few – at most three – centering steps. In this paper each iteration consists of only a infeasibility step, whereas the iteration bound improves the … Read more