An inexact infeasible arc-search interior-point method for linear optimization problems

Technical Summary: An Inexact Infeasible Arc-Search Interior-Point Method for Linear Optimization Problems

Problem Statement
The paper addresses the solution of Linear Optimization Problems (LOPs) using Interior-Point Methods (IPMs). Specifically, it focuses on inexact infeasible IPMs (II-IPMs), which are variants designed to solve LOPs starting from an infeasible initial point and solving the Newton systems inexactly (e.g., via iterative solvers like Conjugate Gradient). While inexact solvers reduce the computational cost per iteration for large-scale problems, existing inexact infeasible line-search methods suffer from a significant drawback: the accumulation of linearization errors (from approximating the central path) and inexactness errors (from the solver) along a straight search direction. This accumulation forces the algorithm to take very small step sizes, resulting in a relatively loose worst-case iteration complexity bound of $O(n^2 L)$, where $n$ is the number of variables and $L$ is the binary length of the input data.

Methodology
The authors propose a novel method termed II-arc (Inexact Infeasible Arc-Search Interior-Point Method). The core innovation lies in replacing the standard straight-line search with an ellipsoidal arc-search strategy.

1. Arc-Search Framework: Instead of moving along a straight line, the method approximates the central path using an ellipsoidal arc defined by a second-order Taylor expansion. The next iterate $(x_{k+1}, y_{k+1}, s_{k+1})$ is computed as:
   $$x(\alpha) = x_k - \dot{x} \sin(\alpha) + \ddot{x}(1 - \cos(\alpha))$$
   (and similarly for $y$ and $s$), where $\dot{x}, \ddot{x}$ are the first and second derivatives of the central path.
2. Inexact Solving: The method solves the Newton systems for the first derivative ($\dot{x}, \dot{y}, \dot{s}$) and the second derivative ($\ddot{x}, \ddot{y}, \ddot{s}$) inexactly. The authors utilize the Modified Normal Equation System (MNES) formulation for theoretical analysis to relax residual requirements, though numerical experiments employ the standard Normal Equation System (NES) with a Jacobi preconditioner due to observed numerical instability in MNES implementations for large-scale problems.
3. Step Size Selection: The step size $\alpha$ is chosen to satisfy specific neighborhood conditions (ensuring the iterate remains within a specific region of the central path) and an Armijo-like condition to ensure sufficient reduction in the duality gap.
4. Theoretical Analysis: The authors prove that the curved trajectory of the arc-search suppresses the linearization error more effectively than a straight line. This allows the step size to remain larger even when the Newton systems are solved with significant inexactness.

Key Contributions

• First Inexact Arc-Search IPM: To the authors' knowledge, this is the first paper to discuss an inexact IPM within the arc-search framework.
• Improved Complexity Bound: The paper establishes a polynomial iteration complexity bound of $O(n^{1.5} L)$ for the proposed II-arc method. This represents a theoretical improvement over the best-known bound for existing inexact infeasible line-search methods ($O(n^2 L)$) by a factor of $n^{0.5}$.
• Mitigation of Error Accumulation: The authors demonstrate that the arc-search strategy mitigates the accumulation of linearization and inexactness errors, which is the primary bottleneck in existing infeasible inexact methods.

Numerical Results
The authors conducted numerical experiments on large-scale problems from the NETLIB benchmark collection (including DFL001, QAP15, STOCFOR3, and Kennington problems) using a Python implementation with Preconditioned Conjugate Gradient (CG) as the linear solver.

• Comparison: The proposed II-arc method (specifically the variant using Yang's heuristic initial point, "II-arc-Yang") was compared against an existing inexact infeasible line-search method ("II-line-Yang").
• Performance:
  • Iterations: II-arc-Yang consistently required fewer iterations than II-line-Yang. For nearly 25% of the test problems, the line-search method required twice or more iterations than the arc-search method.
  • Computation Time: II-arc-Yang reduced the total computation time for 75% of the problems. The reduction in iterations compensated for the additional cost of solving the second derivative system.
  • Robustness: The method successfully solved 17 out of 18 test problems, demonstrating numerical stability.
• Initial Points: The study also compared a constant initial point against Yang's heuristic initial point, finding that the heuristic approach (II-arc-Yang) generally yielded better performance in terms of both iterations and time.

Significance and Claims
The paper claims that the proposed II-arc method offers a provably tighter worst-case iteration bound than existing inexact infeasible line-search methods. The significance of this work lies in bridging the gap between the theoretical benefits of arc-search (better central path approximation) and the practical necessity of inexact solvers for large-scale problems.

The authors modestly note that while the theoretical complexity is improved, the primary goal was to propose the framework and discuss its convergence. They acknowledge that the numerical performance could be further improved by:

• Implementing the method in faster languages (e.g., C++, Julia).
• Investigating more advanced inexact linear system solvers and preconditioners.
• Exploring combinations with Nesterov's restarting strategy or feasible IPMs.

The paper concludes that the ellipsoidal arc approximation allows for larger step sizes in the presence of inexactness, leading to both a theoretical reduction in iteration complexity and practical improvements in solving large-scale linear optimization problems.