A Tight SDP Relaxation for the Cubic-Quartic Regularization Problem

This paper studies how to compute global minimizers of the cubic-quartic regularization (CQR) problem min s ∈ Rⁿ f₀+gTs+1/2sTHs+β /6 s ³+ σ /4 s ⁴, min s ∈ R n f 0 + g T s + 1 2 s T H s + β 6 ‖ s ‖ 3 + σ 4 ‖ s ‖ 4 , where f₀ f 0 is a constant, g is an n -dimensional vector, H is an n -by- n symmetric matrix, and s ‖ s ‖ denotes the Euclidean norm of s . The parameter σ σ is nonnegative while β β 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 s^* ( β + 3 σ s^* ) ≥ 0 ‖ s ∗ ‖ ( β + 3 σ ‖ s ∗ ‖ ) ≥ 0 holds for a global minimizer