pith. sign in

arxiv: 2604.04376 · v2 · pith:GKEAZPBInew · submitted 2026-04-06 · 🧮 math.OC

Polynomial iteration complexity of a path-following smoothing Newton method for symmetric cone programming

Yu-Hong Dai , Ruoyu Diao , Xin-Wei Liu , Rui-Jin Zhang This is my paper

Pith reviewed 2026-05-22 11:19 UTC · model grok-4.3

classification 🧮 math.OC
keywords symmetric cone programmingsmoothing Newton methodspath-following methodsiteration complexityself-concordant convex-concaveaugmented Lagrangianinterior-point methods
0
0 comments X

The pith

A path-following smoothing Newton method for symmetric cone programming achieves O(√ν ln(1/ε)) iteration complexity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper resolves an open question by showing that smoothing Newton methods for symmetric cone programming admit polynomial iteration complexity. It introduces a reduced barrier augmented Lagrangian function and proves this function is self-concordant convex-concave. This allows the smooth system to be interpreted as optimality conditions for a minimax problem, inducing a central path that supports a path-following analysis. The analysis yields an iteration bound of O(√ν ln(1/ε)), which matches the best short-step interior-point methods.

Core claim

The reduced barrier augmented Lagrangian function is self-concordant convex-concave. The parameterized smooth system in the smoothing Newton method coincides with the first-order optimality conditions of the associated minimax problem. This equivalence induces a central path and neighborhood for which the Newton decrement can be bounded, delivering the O(√ν ln(1/ε)) iteration complexity.

What carries the argument

The reduced barrier augmented Lagrangian function, proven self-concordant convex-concave, which induces the central path and enables the path-following Newton analysis.

Load-bearing premise

The reduced barrier augmented Lagrangian function is self-concordant convex-concave.

What would settle it

A symmetric cone programming problem where the path-following smoothing Newton method requires substantially more than O(√ν ln(1/ε)) iterations to achieve ε accuracy.

Figures

Figures reproduced from arXiv: 2604.04376 by Rui-Jin Zhang, Ruoyu Diao, Xin-Wei Liu, Yu-Hong Dai.

Figure 1
Figure 1. Figure 1: Summary of equivalence relationships 4 A path-following smoothing Newton method This section proposes a path-following smoothing Newton method for symmetric cone programming. The method adopts a two-phase structure. In the first phase, an initial point within a well-defined neighborhood of the central path is efficiently constructed. Starting from this point, the second phase iteratively refines a solution… view at source ↗
Figure 2
Figure 2. Figure 2: Structure of the SOCP Schur complement in PFSNM [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Performance profiles of PFSNM, SDPT3, SeDuMi, ECOS, a [PITH_FULL_IMAGE:figures/full_fig_p035_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Performance profiles of PFSNM, SDPT3, SeDuMi, ECOS, a [PITH_FULL_IMAGE:figures/full_fig_p036_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Performance profiles of PFSNM, SDPT3, SeDuMi, ECOS, a [PITH_FULL_IMAGE:figures/full_fig_p037_5.png] view at source ↗
read the original abstract

It has long remained open whether smoothing Newton methods (SNMs) for symmetric cone programming (SCP) admit polynomial iteration complexity. A key difficulty lies in the lack of an analogue of the self-concordant convex framework underlying interior-point methods (IPMs). In this paper, inspired by Nemirovski's self-concordant convex-concave theory, we address this open problem by introducing a reduced barrier augmented Lagrangian (BAL) function. We prove that the reduced BAL function is self-concordant convex-concave and establish that the parameterized smooth system arising in SNMs coincides with the first-order optimality conditions of an associated minimax problem. Motivated by this equivalence, we propose a path-following smoothing Newton method (PFSNM). The reduced BAL function induces a central path and an associated neighborhood, which provide estimates for the Newton decrement needed for the path-following analysis. As a result, the method achieves an iteration complexity of $\mathcal{O}(\sqrt{\nu}\ln(1/\varepsilon))$, matching the best-known short-step complexity for IPMs. Numerical results on standard benchmarks show that PFSNM is competitive with several well-known interior-point solvers, and the observed performance is consistent with the theoretical development.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper resolves the open question of polynomial iteration complexity for smoothing Newton methods on symmetric cone programs. It introduces a reduced barrier augmented Lagrangian (BAL) function, proves that this function is self-concordant convex-concave, shows that the smooth system solved by SNMs coincides with the first-order conditions of an associated minimax problem, and constructs a path-following smoothing Newton method whose central path and neighborhood yield a Newton-decrement bound that establishes an O(√ν ln(1/ε)) iteration complexity, matching the best short-step IPM bounds. Numerical results on standard test sets indicate practical competitiveness with existing interior-point solvers.

Significance. If the self-concordance and central-path estimates hold, the work supplies the first rigorous polynomial-complexity guarantee for path-following smoothing Newton methods on symmetric cones, thereby closing a long-standing gap with interior-point theory. The construction of the reduced BAL function and its equivalence to a minimax problem constitute a technically substantive contribution that may extend to other smoothing or non-interior-point frameworks. The explicit matching of the short-step IPM complexity together with reproducible numerical benchmarks on standard instances strengthens the result.

major comments (2)
  1. [§3.2, Theorem 3.1] §3.2, Theorem 3.1: the self-concordance parameter ν of the reduced BAL function is asserted to be independent of the smoothing parameter; the proof sketch in the text relies on the Jordan-algebraic properties of the symmetric cone, but an explicit verification that the third-derivative bound remains uniform when the barrier is reduced by the augmented-Lagrangian term is needed to confirm that the subsequent Newton-decrement estimate in §4.3 does not acquire an extra factor.
  2. [§4.4, Lemma 4.3] §4.4, Lemma 4.3: the neighborhood radius around the central path is chosen so that the Newton decrement is bounded by a constant; the argument uses the self-concordance of the BAL function to control the quadratic term, yet the dependence of this constant on the cone rank r (or on ν) should be stated explicitly, because any hidden linear factor in r would alter the final O(√ν ln(1/ε)) claim.
minor comments (3)
  1. [§2] Notation for the symmetric cone and its associated Jordan algebra is introduced in §2 but used without repeated reminder in later sections; a short table collecting the key symbols (e.g., ν, r, the barrier parameter) would improve readability.
  2. [Numerical experiments] Figure 1 (convergence curves) lacks error bars or multiple random seeds; adding a brief statement on the number of runs and observed variance would strengthen the empirical support for the theoretical rate.
  3. [Introduction] The reference list omits a recent related work on self-concordant convex-concave functions for conic programs (e.g., the 2022 paper by Lu & Monteiro); a short comparison paragraph would clarify the novelty of the reduced BAL construction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation for minor revision. The two major comments concern the clarity of the self-concordance proof and the explicit dependence of constants on the cone rank. We address each point below and will incorporate the suggested clarifications.

read point-by-point responses

  1. Referee: [§3.2, Theorem 3.1] §3.2, Theorem 3.1: the self-concordance parameter ν of the reduced BAL function is asserted to be independent of the smoothing parameter; the proof sketch in the text relies on the Jordan-algebraic properties of the symmetric cone, but an explicit verification that the third-derivative bound remains uniform when the barrier is reduced by the augmented-Lagrangian term is needed to confirm that the subsequent Newton-decrement estimate in §4.3 does not acquire an extra factor.

    Authors: We agree that an explicit verification improves readability. The reduced BAL function is obtained from the standard self-concordant barrier by subtracting a linear term induced by the augmented-Lagrangian multiplier. Because the third derivative of any linear function is identically zero, the third-derivative bound for the reduced BAL function is identical to that of the original barrier and therefore remains independent of the smoothing parameter. We will add a short clarifying paragraph immediately after Theorem 3.1 that records this reduction step and confirms uniformity of the bound. revision: yes

  2. Referee: [§4.4, Lemma 4.3] §4.4, Lemma 4.3: the neighborhood radius around the central path is chosen so that the Newton decrement is bounded by a constant; the argument uses the self-concordance of the BAL function to control the quadratic term, yet the dependence of this constant on the cone rank r (or on ν) should be stated explicitly, because any hidden linear factor in r would alter the final O(√ν ln(1/ε)) claim.

    Authors: The neighborhood radius is chosen so that the Newton decrement satisfies λ ≤ 1/4. Self-concordance then yields a uniform quadratic-term bound whose constant depends only on the self-concordance parameter ν. For symmetric cones the parameter ν already encodes the rank r (typically ν = r or a small multiple thereof), so no additional linear factor in r appears beyond the √ν already present in the iteration bound. We will insert an explicit sentence in the proof of Lemma 4.3 stating that the constant is O(1) with respect to r when expressed in terms of ν. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation begins with the introduction of a reduced barrier augmented Lagrangian (BAL) function whose self-concordant convex-concave property is proved directly in the paper. This property is then used to establish equivalence between the parameterized smooth system and the first-order optimality conditions of an associated minimax problem. The induced central path and neighborhood supply the Newton-decrement bounds that yield the O(√ν ln(1/ε)) iteration complexity. All load-bearing steps rest on these internal proofs and the newly constructed BAL function rather than on fitted parameters, self-referential definitions, or chains of self-citations; the argument is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the introduction and verification of the reduced BAL function together with its self-concordant convex-concave property; these are the primary additions beyond the existing literature on interior-point and smoothing methods.

axioms (1)
  • domain assumption The reduced barrier augmented Lagrangian function is self-concordant convex-concave.
    This property is asserted and used to induce the central path and neighborhood estimates required for the path-following complexity analysis.
invented entities (1)
  • reduced barrier augmented Lagrangian (BAL) function no independent evidence
    purpose: To provide a self-concordant convex-concave function whose first-order optimality conditions coincide with the smoothed Newton system and whose central path supports the iteration-complexity bound.
    Newly defined in the paper to overcome the absence of a direct self-concordant framework for smoothing Newton methods.

pith-pipeline@v0.9.0 · 5756 in / 1427 out tokens · 64636 ms · 2026-05-22T11:19:15.666060+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    We prove that the reduced BAL function is self-concordant convex-concave and establish that the parameterized smooth system arising in SNMs coincides with the first-order optimality conditions of an associated minimax problem... iteration complexity of O(√ν ln(1/ε))

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

45 extracted references · 45 canonical work pages

  1. [1]

    Alizadeh, F., Goldfarb, D.: Second-order cone programmi ng. Math. Program. 95(1), 3–51 (2003)

    work page 2003

  2. [2]

    SIAM, Phi ladelphia (2017)

    Beck, A.: First-order methods in optimization. SIAM, Phi ladelphia (2017)

    work page 2017

  3. [3]

    Biometrika 98(4), 791–806 (2011)

    Belloni, A., Chernozhukov, V., W ang, L.: Square-root las so: pivotal recovery of sparse signals via conic programming. Biometrika 98(4), 791–806 (2011)

    work page 2011

  4. [4]

    Burke, J., Xu, S.: A non–interior predictor–corrector pa th following algorithm for the monotone linear complementarity problem. Math. Program. 87(1), 113–130 (2000)

    work page 2000

  5. [5]

    Burke, J.V., Xu, S.: The global linear convergence of a non interior path-following algorithm for linear complementarity problems. Math. Oper. Res. 23(3), 719–734 (1998)

    work page 1998

  6. [6]

    Chan, Z.X., Sun, D.: Constraint nondegeneracy, strong re gularity, and nonsingularity in semidefinite programming. SIAM J. Optim. 19(1), 370–396 (2008)

    work page 2008

  7. [7]

    Chen, B., Harker, P.T.: A non-interior-point continuati on method for linear complemen- tarity problems. SIAM J. Matrix Anal. Appl. 14(4), 1168–1190 (1993)

    work page 1993

  8. [8]

    Chen, X., Tseng, P.: Non-interior continuation methods f or solving semidefinite comple- mentarity problems. Math. Program. 95(3), 431–474 (2003)

    work page 2003

  9. [9]

    Dolan, E.D., Mor´ e, J.J.: Benchmarking optimization sof tware with performance profiles. Math. Program. 91, 201–213 (2002)

    work page 2002

  10. [10]

    In: 2013 European Control Conference (ECC), pp

    Domahidi, A., Chu, E., Boyd, S.: ECOS: An SOCP solver for e mbedded systems. In: 2013 European Control Conference (ECC), pp. 3071–3076. IEEE (20 13)

    work page 2013

  11. [11]

    Engelke, S., Kanzow, C.: Predictor-corrector smoothin g methods for linear programs with a more flexible update of the smoothing parameter. Comput. Op tim. Appl. 23(3), 299–320 (2002)

    work page 2002

  12. [12]

    Fukushima, M., Luo, Z.Q., Tseng, P.: Smoothing function s for second-order-cone comple- mentarity problems. SIAM J. Optim. 12(2), 436–460 (2002)

    work page 2002

  13. [13]

    arXiv preprint arXiv:2405.12762 (2 024)

    Goulart, P.J., Chen, Y.: Clarabel: An interior-point so lver for conic programs with quadratic objectives. arXiv preprint arXiv:2405.12762 (2 024)

    work page arXiv

  14. [14]

    Hauser, R.A., G¨ uler, O.: Self-scaled barrier function s on symmetric cones and their clas- sification. Found. Comput. Math. 2(2), 121–143 (2002)

    work page 2002

  15. [15]

    Hotta, K., Inaba, M., Yoshise, A.: A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity probl ems. Comput. Optim. Appl. 17(2), 183–201 (2000)

    work page 2000

  16. [16]

    Huang, Z.H., Qi, L.Q., Sun, D.F.: Sub-quadratic converg ence of a smoothing Newton algorithm for the P 0–and monotone LCP. Math. Program. 99(3), 423–441 (2004)

    work page 2004

  17. [17]

    Kanzow, C.: Some non-interior continuation methods for linear complementarity problems. SIAM J. Matrix Anal. Appl. 17(4), 851–868 (1996)

    work page 1996

  18. [18]

    Kanzow, C., Nagel, C.: Semidefinite programs: new search directions, smoothing-type methods, and numerical results. SIAM J. Optim. 13(1), 1–23 (2002)

    work page 2002

  19. [19]

    Kanzow, C., Pieper, H.: Jacobian smoothing methods for n onlinear complementarity prob- lems. SIAM J. Optim. 9(2), 342–373 (1999)

    work page 1999

  20. [20]

    Kluwer Academic Publishers, Dordrecht (200 2)

    de Klerk, E.: Aspects of semidefinite programming: inter ior point algorithms and selected applications. Kluwer Academic Publishers, Dordrecht (200 2)

    work page

  21. [21]

    de Klerk, E., Vallentin, F.: On the Turing model complexi ty of interior point methods for semidefinite programming. SIAM J. Optim. 26(3), 1944–1961 (2016)

    work page 1944

  22. [22]

    Kong, L.C., Sun, J., Xiu, N.H.: A regularized smoothing N ewton method for symmetric cone complementarity problems. SIAM J. Optim. 19(3), 1028–1047 (2008)

    work page 2008

  23. [23]

    Liang, L., Sun, D., Toh, K.C.: An inexact augmented Lagra ngian method for second-order cone programming with applications. SIAM J. Optim. 31(3), 1748–1773 (2021)

    work page 2021

  24. [24]

    Liang, L., Sun, D.F., Toh, K.C.: A squared smoothing Newt on method for semidefinite programming. Math. Oper. Res. 50(4), 2873–2908 (2024)

    work page 2024

  25. [25]

    Liu, Y.J., Zhang, L.W., W ang, Y.H.: Analysis of a smoothi ng method for symmetric conic linear programming. J. Appl. Math. Comput. 22(1), 133–148 (2006)

    work page 2006

  26. [26]

    Monteiro, R.D., Zhang, Y.: A unified analysis for a class o f long-step primal-dual path- following interior-point algorithms for semidefinite prog ramming. Math. Program. 81(3), 281–299 (1998)

    work page 1998

  27. [27]

    Nemirovski, A.: On self-concordant convex–concave fun ctions. Optim. Methods Softw. 11(1–4), 303–384 (1999)

    work page 1999

  28. [28]

    Nesterov, Y.: Long-step strategies in interior-point p rimal-dual methods. Math. Program. 76(1), 47–94 (1997) 40 Yu-Hong Dai et al

    work page 1997

  29. [29]

    SIAM, Philadelphia (1994)

    Nesterov, Y., Nemirovskii, A.: Interior-point polynom ial algorithms in convex program- ming. SIAM, Philadelphia (1994)

    work page 1994

  30. [30]

    Nesterov, Y.E., Todd, M.J.: Primal-dual interior-poin t methods for self-scaled cones. SIAM J. Optim. 8(2), 324–364 (1998)

    work page 1998

  31. [31]

    Spr inger, New York (2006)

    Nocedal, J., W right, S.J.: Numerical optimization. Spr inger, New York (2006)

    work page 2006

  32. [32]

    Peng, J.M., Lin, Z.H.: A non-interior continuation meth od for generalized linear comple- mentarity problems. Math. Program. 86(3), 533–563 (1999)

    work page 1999

  33. [33]

    Qi, L.Q., Sun, D.F., Zhou, G.L.: A new look at smoothing Ne wton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Program. 87(1), 1–35 (2000)

    work page 2000

  34. [34]

    Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior point algorithms to sym- metric cones. Math. Program. 96(3), 409–438 (2003)

    work page 2003

  35. [35]

    Smale, S.: Algorithms for solving equations. In: F. Cuck er, R.S.C. W ong (eds.) The Col- lected Papers of Stephen Smale, vol. 3, pp. 1263–1286. W orld Scientific, Singapore (2000)

    work page 2000

  36. [36]

    Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for opti mization over symmetric cones. Optim. Methods Softw. 11(1–4), 625–653 (1999)

    work page 1999

  37. [37]

    Sun, J., Sun, D.F., Qi, L.Q.: A squared smoothing Newton m ethod for nonsmooth matrix equations and its applications in semidefinite optimizatio n problems. SIAM J. Optim. 14(3), 783–806 (2004)

    work page 2004

  38. [38]

    T¨ ut¨ unc¨ u, R.H., Toh, K.C., Todd, M.J.: Solving semide finite-quadratic-linear programs using SDPT3. Math. Program. 95(2), 189–217 (2003)

    work page 2003

  39. [39]

    Vavasis, S.A., Ye, Y.Y.: A primal-dual interior point me thod whose running time depends only on the constraint matrix. Math. Program. 74(1), 79–120 (1996)

    work page 1996

  40. [40]

    Vieira, M.V.C.: Jordan algebraic approach to symmetric optimization. Ph.D. thesis, Delft University of Technology, Delft, The Netherlands (2007)

    work page 2007

  41. [41]

    SIA M, Philadelphia (1997)

    W right, S.J.: Primal-dual interior-point methods. SIA M, Philadelphia (1997)

    work page 1997

  42. [42]

    Xu, S., Burke, J.V.: A polynomial time interior-point pa th-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques. Math. P rogram. 86, 91–103 (1999)

    work page 1999

  43. [43]

    Zhang, R.J., Liu, X.W., Dai, Y.H.: IPRSDP: a primal-dual interior-point relaxation algo- rithm for semidefinite programming. Comput. Optim. Appl. 88(1), 1–36 (2024)

    work page 2024

  44. [44]

    Zhang, R.J., W ang, Z.W., Liu, X.W., Dai, Y.H.: IPRSOCP: a primal-dual interior-point relaxation algorithm for second-order cone programming. J . Oper. Res. Soc. China 14, 1–31 (2026)

    work page 2026

  45. [45]

    Zhao, Y.B., Li, D.: A globally and locally superlinearly convergent non–interior-point algorithm for P 0 LCPs. SIAM J. Optim. 13(4), 1195–1221 (2003)

    work page 2003