A Tight SDP Relaxation for the Cubic-Quartic Regularization Problem

Abstract

Abstract 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