large neighborhood

A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with (\sqrt{n}\log{\frac{{\rm Tr}(X^0S^0)}{\epsilon}})$ iteration complexity

  • Yang Li
  • Tamás Terlaky
    • Categories Semi-definite Programming Tags , , ,

    In this paper, we extend the Ai-Zhang direction to the class of semidefinite optimization problems. We define a new wide neighborhood $\N(\tau_1,\tau_2,\eta)$ and, as usual, we utilize symmetric directions by scaling the Newton equation with special matrices. After defining the “positive part” and the “negative part” of a symmetric matrix, we solve the Newton equation … 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. Citationsubmitted to Mathematical ProgrammingArticleDownload View PDF

    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. Citationsubmitted to Optimization Methods and SoftwareArticleDownload View PDF

    Adaptive Large Neighborhood Self-Regular Predictor-Corrector IPMs for LO

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

    It is known that predictor-corrector methods in a large neighborhood of the central path are among the most efficient interior point methods (IPMs) for linear optimization (LO) problems. The best iteration bound based on the classical logarithmic barrier function is $O\left(n\log{\frac{n}{\epsilon}}\right)$. In this paper we propose a family of self-regular proximity based predictor-corrector (SR-PC) IPM … Read more

    A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function

  • Jiming Peng
  • Tamás Terlaky
  • Yun-Bin Zhao
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    It is well known that the so-called first-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior-point methods (IPMs) for linear optimization (LO) problems. However, the best known iteration complexity of this type of methods is $O\br{n \log\frac{(x^0)^Ts^0}{\varepsilon}}$. It is of interests to investigate whether the complexity … Read more