superlinear convergence

Local Convergence of the Method of Multipliers for Variational and Optimization Problems under the Sole Noncriticality Assumption

  • Alexey F. Izmailov
  • A. S. Kurennoy
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , ,

    We present local convergence analysis of the method of multipliers for equality-constrained variational problems (in the special case of optimization, also called the augmented Lagrangian method) under the sole assumption that the dual starting point is close to a noncritical Lagrange multiplier (which is weaker than second-order sufficiency). Local superlinear convergence is established under the … Read more

    Hager-Zhang Active Set Algorithm for Large-Scale Continuous Knapsack Problems

  • Rouhollah Tavakoli
    • Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Nonlinear Optimization Tags , , , , , ,

    The structure of many real-world optimization problems includes minimization of a nonlinear (or quadratic) functional subject to bound and singly linear constraints (in the form of either equality or bilateral inequality) which are commonly called as continuous knapsack problems. Since there are efficient methods to solve large-scale bound constrained nonlinear programs, it is desirable to … Read more

    Switching stepsize strategies for PDIP

  • Berc Rustem
  • George Tzallas-Regas
    • Categories Constrained Nonlinear Optimization Tags , , , , , ,

    In this chapter we present a primal-dual interior point algorithm for solving constrained nonlinear programming problems. Switching rules are implemented that aim at exploiting the merits and avoiding the drawbacks of three different merit functions. The penalty parameter is determined using an adaptive penalty strategy that ensures a descent property for the merit function. The … Read more

    On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP

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

    A new class of infeasible interior point methods for solving sufficient linear complementarity problems requiring one matrix factorization and $m$ backsolves at each iteration is proposed and analyzed. The algorithms from this class use a large $(\caln_\infty^-$) neighborhood of an infeasible central path associated with the complementarity problem and an initial positive, but not necessarily … Read more

    Primal-dual affine scaling interior point methods for linear complementarity problems

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

    A first order affine scaling method and two $m$th order affine scaling methods for solving monotone linear complementarity problems (LCP) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has $O(nL^2(\log nL^2)(\log\log nL^2))$ iteration complexity. If the LCP admits a strict complementary solution then both … Read more

    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

    Erratum: Predictor-corrector 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 , , ,

    We correct an error in Algorithms 4.1 and 4.8 from the paper with the same title that was published in Optimization Methods and Software, 20, 1 (2005), 145–168. Citation submitted to Optimization Methods and Software Article Download View Erratum: Predictor-corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path,

    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

    Postponing the Choice of the Barrier Parameter in Mehrotra-Type Predictor-Corrector Algorithms

  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In \cite{SPT} the authors considered a variant of Mehrotra’s predictor-corrector algorithm that has been widely used in several IPMs based optimization packages. By an example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, that itself implies the inefficiency of … Read more

    On Mehrotra-Type Predictor-Corrector Algorithms

  • Jiming Peng
  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper we discuss the polynomiality of Mehrotra-type predictor-corrector algorithms. We consider a variant of the original prototype of the algorithm that has been widely used in several IPM based optimization packages, for which no complexity result is known to date. By an example we show that in this variant the usual Mehrotra-type adaptive … Read more