PaperlayerView exact revision on arXiv

Source-linked AI summary

A Faster Interior Point Method for Semidefinite Programming

Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, Zhao Song

arXiv:2009.10217v1cs.DSmath.OC

TL;DR

SDPs are a fundamental optimization problem where cutting-plane methods currently outperform existing interior-point solvers in common constraint regimes. This paper presents a faster interior-point method and proves it outperforms the fastest cutting-plane methods when m ≥ n.

  • Problem

    Existing interior-point methods are slower than cutting-plane methods for general SDPs in the common regime m ∈ [n, n^2], despite interior-point methods generally exploiting more structural information.

  • Method

    The paper presents a faster interior-point method for solving general semidefinite programs.

  • Results

    When m ≥ n, the proposed interior-point method solves general SDPs faster than the current best cutting-plane method across all input sparsity regimes.

  • Takeaways & Limitations

    The method reverses the prior runtime comparison between interior-point and cutting-plane approaches for SDPs when m ≥ n.

  • Takeaways & Limitations

    The costliest term is often mn^2 per iteration, corresponding to reading the entire input in each iteration.

Abstract

from arXiv · show

Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning. This paper presents a faster interior point method to solve generic SDPs with variable size $n \times n$ and $m$ constraints in time \begin{align*} \widetilde{O}(\sqrt{n}( mn^2 + m^ω+ n^ω) \log(1 / ε) ), \end{align*} where $ω$ is the exponent of matrix multiplication and $ε$ is the relative accuracy. In the predominant case of $m \geq n$, our runtime outperforms that of the previous fastest SDP solver, which is based on the cutting plane method of Jiang, Lee, Song, and Wong [JLSW20]. Our algorithm's runtime can be naturally interpreted as follows: $\widetilde{O}(\sqrt{n} \log (1/ε))$ is the number of iterations needed for our interior point method, $mn^2$ is the input size, and $m^ω+ n^ω$ is the time to invert the Hessian and slack matrix in each iteration. These constitute natural barriers to further improving the runtime of interior point methods for solving generic SDPs.

1 Introduction

This paper develops a faster interior point method for generic semidefinite programs, addressing a setting where existing interior point methods are slower than cutting plane methods. Its runtime matches natural costs for iterations, input processing, and matrix inversions, and improves on prior solvers when m ≥ n.

  • Motivation: SDPs optimize a linear objective over positive semidefinite matrices intersected with an affine space and support applications across optimization, control, and theoretical computer science.Applications include approximation algorithms, quantum complexity, and robust learning.
  • Motivation: Existing cutting plane methods solve general SDPs in time m(mn^2+m^2+n^ω), while prior interior point methods are slower when m ∈ [n,n^2].This gap motivates a faster interior point method.
  • Our results: √n iterations, mn^2 input processing, m^ω Hessian inversion, and n^ω slack-matrix inversion explain the principal runtime terms.The paper presents these terms as natural barriers to further speeding up generic SDP solvers.
  • Our results: When m ≥ n, the new interior point method is faster than the current fastest cutting plane method, including for dense and non-dense inputs.For non-dense SDPs, the comparison uses nnz(A) as the input size.
  • Our techniques: The method uses the log barrier and maintains an approximate slack matrix that is a spectral approximation of the true slack matrix and supports low-rank updates.These techniques address costly iterations associated with earlier barrier choices.

2 Preliminaries

This section establishes notation for symmetric, positive semidefinite, and positive definite matrices, matrix relations, inner products, Kronecker products, norms, and standard matrix facts.

  • Sn×n denotes the set of symmetric n × n matrices, with Sn×n≥0 and Sn×n>0 denoting positive semidefinite and positive definite matrices.
  • The Loewner relation A ⪯ B means that B − A is positive semidefinite.
  • Matrix inner products use the trace product, while diag(v) forms a diagonal matrix from a vector and A ⊗ B denotes the Kronecker product.
  • The paper fixes m as the number of primal constraints, n × n as the variable-matrix size, and nnz(A) as the total number of nonzero input entries.
  • It uses Frobenius and operator norms, similarity and eigenvalue facts, and standard generalized Lieb-Thirring, Hoffman-Wielandt, and Woodbury identities.

3 Matrix Multiplication

The section develops rectangular matrix-multiplication tools for the runtime analysis, including the exponent function ω(k), its convexity, and bounds for the two key products.

  • The runtime analysis centers on multiplying m × n^2 by n^2 × m matrices and n × mn by mn × n matrices.
  • Tmat(n, r, m) denotes the operation count for multiplying n × r and r × m matrices, while ω(k) characterizes Tmat(n, n^k, n).
  • ω(k) is convex, enabling interpolation and upper bounds for rectangular multiplication exponents.
  • ω(1.68568) ≤ 2.96370 provides a numerical exponent bound used in subsequent estimates.
  • For m ≥ n, the two target products admit comparable bounds, including Tmat(n, mn, n) ≤ O(Tmat(m, n^2, m)) and the reverse inequality.
  • The resulting bounds connect rectangular products to matrix-multiplication exponents and support the later runtime analysis.

4 Main Theorem

The main theorem gives an interior point method for general SDPs with n × n variables and m constraints, under bounded feasible solutions and a small error parameter.

  • The SDP maximizes ⟨C, X⟩ subject to X ⪰ 0 and ⟨Ai, X⟩ = bi for all i ∈ [m].
  • The theorem assumes no redundant constraints and that every feasible solution has operator norm at most R.
  • For 0 < δ ≤ 0.01, the method runs in O*(√n(mn^2 + m^ω + n^ω) log(n/δ)) time.
  • Here, ω is the matrix-multiplication exponent, X* is an optimal solution, and ∥Ai∥1 is the Schatten 1-norm.

5 Approximate Central Path via Approximate Hessian

The algorithm maintains an approximate central path using approximate slack and Hessian matrices, with controlled updates that preserve the Newton-step invariant and yield the stated approximation guarantees.

  • Approximate central path: The approximate central-path theorem assumes bounded feasible solutions and specifies error and Newton-step parameters for maintaining the method’s invariant.
  • Approximate central path: An initial dual solution is constructed near the dual central path, and the invariant is preserved throughout the algorithm’s iterations.
  • Approximate central path: After the prescribed iterations, the duality gap is at most δ^2 for the modified SDP, and the procedure recovers an approximate solution to the original SDP.
  • Approximate slack update: Approximate slack updates use spectral decomposition and run in O(n^ω+o(1)) time while producing a positive definite updated slack matrix.
  • Approximate Hessian: The approximate Hessian remains a spectral approximation of the true Hessian, which suffices to approximately follow the central path.
  • Approximate Hessian: Standard Newton-step invariance and approximate-optimality lemmas connect the maintained invariant to progress toward an optimal dual solution.

6 Low-rank Update

The section controls approximate-slack updates through low-rank changes and proves that their ranks remain small in aggregate over the algorithm’s iterations.

  • Rank bound: Theorem 6.1 bounds the cumulative ranks of approximate-slack updates over T iterations by O(T log^1.5 n).The bound is obtained by tracking a potential function for the slack-matrix error.
  • Error representation: The error matrix compares the approximate slack matrix with the true slack matrix after normalization by the true slack matrix.The proof defines Z from the true and approximate slack matrices and uses its eigenvalues to measure error.
  • Potential analysis: When the true slack matrix changes, Lemma 6.2 bounds the resulting potential increase under Frobenius and operator-norm assumptions.The stated conditions are ||S^-1/2 Snew S^-1/2 − I||F ≤ 0.02 and ||S^-1/2 eS S^-1/2 − I||op ≤ 0.01.
  • Potential analysis: When the approximate slack matrix changes, Lemma 6.3 analyzes the eigenvalue changes and relates them to the potential decrease.The proof separates cases according to the magnitudes and spacing of ordered absolute eigenvalues.
  • Rank bound: Summing the per-iteration potential changes proves the rank inequality because the initial potential is zero and the potential is non-negative.This connects the local potential-decrease argument to the global cumulative rank bound.

7 Runtime Analysis

The runtime analysis decomposes each iteration into approximate-Hessian computation and other operations, then uses the low-rank update bound to obtain the total runtime bound.

  • Runtime bound: Theorem 7.1 gives the total runtime for solving an SDP with variable size n × n and m constraints.The theorem’s displayed bound is further simplified using the matrix multiplication exponent ω.
  • Iteration complexity: The algorithm runs for T = O~(√n) iterations, with the total cost expressed using rectangular matrix multiplication times and update ranks r_i.The rank sequence satisfies the aggregate bound established in Theorem 6.1.
  • Runtime bound: The total-cost lemmas combine both runtime parts and simplify the resulting expression using properties of fast rectangular matrix multiplication.The proof applies Lemma 7.4 to the rank sequence and then concludes Theorem 7.1.
  • Hessian computation: Approximate-Hessian computation is split into first-iteration initialization and low-rank updates accumulated across later iterations.Initialization forms the approximate Hessian by stacking vectorized matrices, while later updates exploit rank-r_i changes.
  • Other operations: Other per-iteration operations include gradient computation, approximate-Hessian inversion, dual-variable updates, slack-matrix construction, and approximate-slack updates.Their costs include O(m^ω+o(1)) for approximate-Hessian inversion and O(n^ω+o(1)) for approximate-slack updating.

8 Comparison with Cutting Plane Method

For SDPs with m ≥ n, the paper proves that its interior point method is faster than the current best cutting plane method across all input-sparsity regimes.

  • Main comparison: When m ≥ n, the interior point method solves SDPs with n × n matrices and m constraints faster than the current best cutting plane method over all nnz(A) regimes.This is the stated comparison theorem against the cutting plane method of LSW15 and JLSW20.
  • Dense case: In the dense case nnz(A) = Θ(mn^2), the algorithm is faster than the cutting plane method whenever m ≥ √n.The dense-case threshold is stated separately as a direct consequence of the runtime comparison.
  • Baseline: The comparison uses the cutting-plane runtime TCP = O*(m · nnz(A) + mn^2.372927 + m^3) as its baseline.The exponent 2.372927 is identified as the current best upper bound on the matrix multiplication exponent in this analysis.
  • Main comparison: Under m ≥ n, each term in the interior point runtime is upper bounded by the cutting-plane baseline, yielding the strict asymptotic comparison.The proof specifically invokes bounds for nm^ω and rectangular matrix multiplication terms.

9 Initialization

The initialization section modifies the SDP and establishes feasible primal and dual solutions together with an approximate-solution guarantee under bounded-diameter assumptions.

  • Assumption: The initialization lemma assumes bounded diameter: every feasible primal matrix satisfies ||X||op ≤ R.This assumption provides a norm bound used in the initialization analysis.
  • Modified SDP: For any 0 < δ ≤ 1, the paper constructs a modified semidefinite program with stated feasible primal and dual solutions.The construction is introduced as a modified SDP and its feasibility properties are listed in the lemma.
  • Guarantee: The constructed solutions have duality gap at most δ^2.This gives the initialization a quantitative accuracy guarantee for the modified program.
  • Approximation guarantee: A feasible solution to the modified SDP is treated as an approximate solution to the original SDP in the stated sense.The guarantee is expressed relative to an optimal solution of the original SDP and uses the Schatten 1-norm.
  • Proof strategy: The proof uses norm and objective-value bounds to relate solutions of the modified SDP back to the original problem.It also exploits the feasibility and positive-semidefinite structure of the constructed matrices.

A Matrix Multiplication: A Tensor Approach

This section uses tensors to rederive technical results bounding two rectangular matrix multiplication tasks. The authors hope these techniques will support further runtime improvements.

  • The tensor approach bounds multiplying m × n^2 by n^2 × m matrices.
  • It also bounds multiplying n × mn by mn × n matrices.
  • The techniques are intended to contribute to future improvements of the paper’s results.

A.1 Exponent of matrix multiplication

This section defines the cost of rectangular matrix multiplication and the associated matrix-multiplication exponents. It recalls properties used to characterize these costs.

  • Tmat(n, r, m) denotes the operations needed to multiply an n × r matrix by an r × m matrix.
  • The rectangular exponent ω(k) is defined through Tmat(n, n^k, n) = n^ω(k)+o(1).
  • The notation specializes to ω(1) = ω for square matrix multiplication and ω(α) = 2 for the dual exponent α.
  • The section recalls additional lemmas giving properties and bounds for these matrix multiplication costs.

A.2 Matrix multiplication tensor

This section introduces tensor rank, tensor comparison, and matrix-multiplication tensors as tools for relating tensor structure to matrix multiplication cost.

  • Tensor rank R(T) is the minimum number of simple tensors whose sum equals T.
  • The relation S ≤ T holds when S can be obtained from T through multiplication by three appropriately sized matrices.
  • The matrix-multiplication tensor represents multiplying an a × b matrix by a b × c matrix.
  • Tensor rank is monotone under the tensor relation and sub-multiplicative across tensors.
  • For matrix-multiplication tensors, tensor rank equals the corresponding matrix multiplication cost up to a constant factor.

A.3 Implication of matrix multiplication technique

The tensor framework yields convexity and transfer inequalities for rectangular matrix multiplication exponents, enabling bounds on the two multiplication tasks relevant to the runtime analysis.

  • Exponent bounds: The rectangular exponent ω(k) is convex in k.
  • Tensor implications: Tmat(a, bk, c) ≤ O(Tmat(ak, b, ck)) transfers one rectangular multiplication cost into another.
  • Rectangular products: When m ≥ n, Tmat(n, mn, n) ≤ O(Tmat(m, n^2, m)) and the reverse inequality also holds.
  • Rectangular products: These bounds are crucial for analyzing the runtime terms Tmat(m, n^2, m) and Tmat(n, mn, n).
  • Rectangular products: Lemma A.13 derives upper bounds for Tmat(m, n^2, m) when m ≥ n and Tmat(n, mn, n) when m < n.
  • Exponent bounds: The proof establishes the exponent inequality ω(b) < max(1 + 5b/4, ω(1) + b/4) for all positive b.
Loading 2009.10217v1…