EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Tight SDP Relaxation for the Cubic-Quartic Regularization Problem

Jinling Zhou, Xin Liu, Jiawang Nie, Xindong Tang

Mathematical Programming · 21.08.2026

DOI: 10.1007/s10107-026-02413-6 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 21.08.2026. Verfasst von Jinling Zhou und 3 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper studies how to compute global minimizers of the cubic-quartic regularization (CQR) problem $$ \min _{s \in \mathbb {R}^n} \quad f_0+g^Ts+\frac{1}{2}s^THs+\frac{\beta }{6}\Vert s \Vert ^3+ \frac{\sigma }{4} \Vert s\Vert ^4, $$ min s ∈ R n f 0 + g T s + 1 2 s T H s + β 6 ‖ s ‖ 3 + σ 4 ‖ s ‖ 4 , where $$f_0$$ f 0 is a constant, g is an n -dimensional vector, H is an n -by- n symmetric matrix, and $$\Vert s \Vert $$ ‖ s ‖ denotes the Euclidean norm of s . The parameter $$\sigma $$ σ is nonnegative while $$\beta $$ β can have any sign. The CQR problem arises as a critical subproblem for getting efficient regularization methods for solving unconstrained nonlinear optimization. Its properties are recently well studied by Cartis and Zhu [cubic-quartic regularization models for solving polynomial subproblems in third-order tensor methods, Math. Program, 2025] . We propose a structured semidefinite programming (SDP) relaxation method for solving the CQR problem globally. The SDP relaxation has only three symmetric positive semidefinite matrix variables of sizes $$(n+1)$$ ( n + 1 ) -by- $$(n+1)$$ ( n + 1 ) , 3-by-3 and 2-by-2 respectively. We show that our SDP relaxation is tight if and only if $$\Vert s^* \Vert ( \beta + 3 \sigma \Vert s^* \Vert ) \ge 0$$ ‖ s ∗ ‖ ( β + 3 σ ‖ s ∗ ‖ ) ≥ 0 holds for a global minimizer $$s^*$$ s ∗ . When $$s^* \ne 0$$ s ∗ ≠ 0 , this aligns with the sufficient global optimality condition $$\beta + 3 \sigma \Vert s^* \Vert \ge 0$$ β + 3 σ ‖ s ∗ ‖ ≥ 0 given by Cartis and Zhu. In particular, if either $$\beta \ge 0$$ β ≥ 0 or H has a nonpositive eigenvalue, then the SDP relaxation is shown to be tight. Second, we show that all nonzero global minimizers have the same Euclidean norm for the tight case. Third, we give an algorithm to detect tightness and to obtain the set of all global minimizers. Numerical experiments demonstrate that our SDP relaxation method is both effective and computationally efficient. This paper gives a polynomial time algorithm for solving the CQR problem globally, under the sufficient global optimality condition.

Förderung

  • National Science Foundation

Zitieren

APA

Zhou, J., Liu, X., Nie, J., & Tang, X. (2026). A Tight SDP Relaxation for the Cubic-Quartic Regularization Problem. Mathematical Programming. https://doi.org/10.1007/s10107-026-02413-6

Vancouver

Zhou J, Liu X, Nie J, Tang X. A Tight SDP Relaxation for the Cubic-Quartic Regularization Problem. Mathematical Programming. 2026. doi:10.1007/s10107-026-02413-6

BibTeX
@article{Zhou2026,
  author = {Zhou, Jinling and Liu, Xin and Nie, Jiawang and Tang, Xindong},
  title = {A Tight SDP Relaxation for the Cubic-Quartic Regularization Problem},
  journal = {Mathematical Programming},
  year = {2026},
  doi = {10.1007/s10107-026-02413-6}
}
Kostenlos starten →