A Tight SDP Relaxation for the Cubic-Quartic Regularization Problem

Résumé

Nous étudions le calcul des minimiseurs globaux du problème de régularisation cubique-quartique (CQR). Ce problème constitue un sous-problème essentiel pour l'obtention de méthodes de régularisation efficaces en optimisation non linéaire sans contraintes. Nous proposons une méthode de relaxation par programmation semi-définie structurée (SDP) pour résoudre globalement le problème CQR. Dans le cas d'un problème CQR à n variables, la relaxation SDP utilise seulement trois variables matricielles symétriques semi-définies positives de dimensions respectives (n+1)×(n+1), 3×3 et 2×2. Nous démontrons que notre relaxation SDP est optimale si et seulement si la condition suffisante d'optimalité globale est vérifiée pour tous les minimiseurs globaux non nuls. Plus précisément, si le paramètre de régularisation cubique est non négatif, ou si la matrice associée au terme quadratique possède une valeur propre non positive, alors la relaxation SDP est optimale. De plus, nous montrons que, dans ce cas optimal, tous les minimiseurs globaux non nuls ont la même norme euclidienne. Troisièmement, nous proposons un algorithme permettant de détecter la compacité et d'obtenir l'ensemble de tous les minimiseurs globaux. Des expériences numériques démontrent que notre méthode de relaxation SDP est à la fois efficace et performante en termes de calcul. On obtient ainsi un algorithme polynomial pour résoudre globalement le problème CQR, sous la condition suffisante d'optimalité globale.

Abstract

We study how to compute global minimizers of the cubic-quartic regularization (CQR) problem. The CQR problem arises as a critical subproblem for getting efficient regularization methods for solving unconstrained nonlinear optimization. We propose a structured semidefinite programming (SDP) relaxation method for solving the CQR problem globally. For the CQR problem with n variables, the SDP relaxation has only three symmetric positive semidefinite matrix variables of sizes (n+1)-by-(n+1), 3-by-3 and 2-by-2 respectively. We show that our SDP relaxation is tight if and only if the sufficient global optimality condition holds for all nonzero global minimizers. In particular, if either the cubic regularization parameter is nonnegative, or the matrix that gives the quadratic term 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 gives a polynomial time algorithm for solving the CQR problem globally, under the sufficient global optimality condition.