Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
To eliminate the bottleneck of dual KKT factorizations in predictor-corrector arc-search for semidefinite programming (SDP), the authors design a homogeneous self-dual interior-point framework (OFAS) and a curvature-amplified variant (CA-OFAS) requiring only a single matrix factorization per iteration. By deriving a three-term decomposition of the complementarity mismatch, the method evaluates the corrector using linear systems from the base iterate while retaining worst-case $O(n \log(1/\varepsilon))$ iteration complexity across a wide long-step neighborhood. Empirically, CA-OFAS outperforms standard Mehrotra-type solvers, cutting geometric-mean solve times by 17% on SDPLIB benchmarks and 13% on certified neural network verification SDPs.
Second-order arc-search SDP solvers no longer require two expensive KKT factorizations per step: a clever three-term complementarity decomposition slashes neural network verification solve times by 13% while preserving global $O(n \log(1/\varepsilon))$ convergence.
In a predictor-corrector arc-search method, a point on the predictor arc is first selected and a corrector is then computed at that point. Since the Karush-Kuhn-Tucker (KKT) matrix changes with the selected point, this correction may require a second factorization in each iteration. We propose a one-factorization arc-search method (OFAS) for semidefinite programming (SDP) that avoids this second factorization, retains the corrector after the arc step, and uses only one KKT factorization per iteration. The key is a three-term decomposition of the complementarity mismatch at the selected point on the arc, which allows the correction to be assembled from linear-system solutions using the factorization at the current iterate. We also propose a curvature-amplified variant (CA-OFAS) that amplifies the second-order arc term. The proposed methods are formulated with a homogeneous self-dual embedding. For a wide long-step neighborhood, we prove that both methods reduce the homogeneous complementarity and residuals below $\varepsilon$ in $O(n \log(1/\varepsilon))$ iterations for an $n$-by-$n$ SDP matrix variable. Numerical experiments show that the one-factorization structure and the correction after the arc step are associated with reductions in computation time. Compared with the Mehrotra-type method, CA-OFAS reduces the geometric-mean computation time by 17% on SDPLIB and 13% on neural network verification SDP problems.