47

数理解析研究所講究録
第2011巻 2016年 47-56

On global minimization for general p ‐regularized

subproblems with p>2
Reuy‐Lin Sheu1
1.

Department of Mathematics, National Cheng Kung University, Tainan, Taiwan

Abstract
The p‐‐regularized subproblem(p‐RS) is a regularizing term for computing a

Newton‐like step for unconstrained

regularization term \displaystyle \frac{ $\sigma$}{p}\Vert x\Vert^{p}.

optimization, which incorporates a weighted

In this article, we resolve the global minimizers of (\mathrm{p}-RS) for p>2 with necessary and sufficient optimality conditions.
Key Words: Thrust‐region subproblem; Local minimizer; Extended Trust‐region sub‐problem.

1

Introduction
For an unconstrained optimization problem to minimize f over \mathbb{R}^{n} , Newtons method

has an attractive local convergence property near a second order critical point.

Ensuring

the global convergence for Newtons method with an analyzable computational complex‐

ity, however, requires modifications to guarantee a sufficient descent at each step. Unlike
the Levenberg‐Marquardt type of methods or most quasi‐Newton methods which always
maintain a positive‐definite approximate Hessian of f , the p‐‐regularized subproblem min‐imizes globally the second order Taylors polynomial of f plus a weighted (by $\sigma$ ) higher

48

order regularization term. The subproblem takes the following model(p‐RS)\displaystyle \min_{x\in \mathb {R}^{n} \{g(x)=\frac{1}{2}x^{T}Hx+c^{T}x+\frac{ $\sigma$}{p}\Vert x\Vert^{p}\},where $\sigma$>0, p>2 , and H is the Hessian of f at any iterate, regardless of its definiteness.
It is often assumed that f is smooth enough to have a symmetric Hessian and to obtain

the desired global convergence. If the global minimizer of (p‐RS) renders a satisfactory

decrease in the value of f it is accepted; but rejected otherwise with an increase in $\sigma$ to,enhance the regularization force.

(p‐RS) with p=3 is known as the cubic regularization which is the

In literature,mostcommonchoice among all others.

The idea of the cubic regularization was first

due to Griewank[9] and later was considered by many authors with thorough global

convergence andcomplexity analysis. See Nesterov and Polyak [15]; Weiser Deuflhard

and Erdmann [17]; and Cartis, Gould and Toint [2]. When p=4 ,(p‐RS) reduces to aform of the double well potential function which has many applications in solid mechanics
and quantum mechanics[5, 18]. Gould, Robinson and Thorne [8] studied (p‐RS) for ageneral p>2 in comparison with the the trust‐region subproblem(TRS)\displaystyle \min\displaystyle \frac{1}{2}x^{T}Hx+c^{T}x\mathrm{s}. \mathrm{t}. \Vert x\Vert^{2}\leq\triangle, x\in \mathbb{R}^{n}.
In this article, we characterize (p‐RS) completely for any p>2 by (i) extending thenecessary and sufficient global optimality conditions for p=3 in [2] and (ii) the analysis

using the secular function (to be specified later) for p=4 in [18].
Notations.

Let vdenote the optimal value of problem

For any symmetricmatrix P\in \mathbb{R}^{n\times n}, P\succ(\succeq)0 means that P is positive (semi)definite. The determinant of

P is denoted by \det(P) whereas the identity matrix of order n by I For a vector x\in \mathbb{R}^{n},.

Diag (x) is a diagonal matrix with diagonal components being x_{1},\cdots

,

x_{n}

.

For a number$\beta$\in \mathbb{R}, \displaystyle \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}( $\beta$)=\frac{ $\beta$}{| $\beta$|} if $\beta$\neq 0 otherwise \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}( $\beta$)=0 Finally, $\lambda$_{i}(P) is the ith smallest,

eigenvalue of P.

.

49

2Main results for global minimization
We first observe that the objective function g(x) of (p‐RS) is coercive, i.e.,\displaystyle \lim g(x)=+\infty.

| x\Vert\rightarrow+\infty

Consequently, the global minimizer of (p‐RS) always exists.

The starting point of theanalysis is the first order and the second order necessary conditions for any local minimizerof g.

Lemma 1 Assume that \underline{x} is a local minimizer of (p‐RS), p>2\nabla g(\underline{x})=(H+ $\sigma$\Vert\underline{x}\Vert^{p-2}I)\underline{x}+c=0.

It holds that(1),\nabla^{2}g(\underline{x})=(H+ $\sigma$\Vert\underline{x}\Vert^{p-2}I)+ $\sigma$(p-2)\Vert\underline{x}\Vert^{p-4}\underline{xx}^{T}\succeq 0,(2)where \nabla g, \nabla^{2}g denote the gradient and the Hessian of g(x) , respectively.

The next theorem shows that, a local minimizer \underline{x} becomes global if and only if H+$\sigma$\Vert\underline{x}\Vert^{p-2}I\succeq O. The necessity has been shown by Theorem 2 in [8]. We only prove thesufficiency here.
Theorem 1

The point x^{*} is a global minimizer of (p‐RS) for p>2 if and only if it is a

critical point satisfy ing \nabla g(x^{*})=0 and H+ $\sigma$\Vert x^{*}\Vert^{p-2}I\succeq 0

Moreover, the P_{2} norms of.

all the global minimizers are equal.

Proof

If x^{*}=0_{n}

,

then

$\sigma$\Vert x^{*}\Vert^{p-2}=0 so that c=-(H+ $\sigma$\Vert x^{*}\Vert^{p-2}I)x^{*}=0 and

H=H+ $\sigma$\Vert x^{*}\Vert^{p-2}I\succeq 0 Consequently, x^{T}Hx\geq 0, \forall x\in \mathbb{R}^{n} It follows that x^{*}=0_{n} is a.

.

global minimizer sinceg(x)=\displaystyle \frac{1}{2}x^{T}Hx+c^{T}x+\frac{ $\sigma$}{p}\Vert x\Vert^{p}\geq\frac{ $\sigma$}{p}\Vert x\Vert^{p}>0=g(0) , \foral x\neq 0_{n}=x^{*}.

50

Now we assume x^{*}\neq 0_{n} , i.e.,\Vert x^{*}\Vert> O. Define Q=H+ $\sigma$\Vert x^{*}\Vert^{p-2}I According to the.

assumption, Q\succeq 0 Then, for any x\in \mathbb{R}^{n} and x\neq x^{*}.

,it holds thatg(x) = \displaystyle \frac{1}{2}x^{T}Hx+c^{T}x+\frac{ $\sigma$}{p}\Vert x\Vert^{p}= \displaystyle \frac{1}{2}x^{T}Qx+c^{T}x-\frac{1}{2}( $\sigma$\Vert x^{*}\Vert^{p-2})x^{T}x+\frac{ $\sigma$}{p}\Vert x\Vert^{p}=\displaystyle\frac{1}{2}x^{T}Qx+c^{T_{X} +\frac{$\sigma$}{p}\Vertx^{*}\Vert^{p}( \frac{|x\Vert^{2} {\Vertx^{*}\Vert^{2} )^{2}e-\frac{p}{2}\frac{|x ^{2} {\Vertx^{*}|^{2} )Define(3)f(t)=t^{2}2, p>2 It is strictly convex for t>0 Therefore,.

.

f(t)=t^{B}2\displaystyle \geq f(1)+f'(1)(t-1)=1+\frac{p}{2}(t-1) , \forall t>0.
By substituting t with\displaystle\frac{|x\Vert^{2} \Vertx^{*}\Vert^{2}

,

we

have

(\displaystyle\frac{|x|^{2} {\Vertx^{*}|^{2} )^{2}-\frac{p}{2}\frac{|x|^{2} {\Vertx^{*}|^{2} \geq21-\frac{p}{2}.
Then,g(x) \displaystyle \geq \frac{1}{2}x^{T}Qx+c^{T}x+\frac{ $\sigma$}{p}\Vert x^{*}\Vert^{p}(1-\frac{p}{2})
By Q\succeq 0

,

(4)

.

the lower bounding function of g in the right hand side of (4) is convex

quadratic in terms of x Since x^{*} satisfies (H+ $\sigma$\Vert x^{*}\Vert^{p-2}I)x^{*}=Qx^{*}=-c, x^{*} is a global.

minimizer of the convex function in the right hand side of (4). As a consequence,

g(x)\displaystyle \geq\frac{1}{2}(x^{*})^{T}Qx^{*}+c^{T}x^{*}+\frac{ $\sigma$}{p}\Vert x^{*}\Vert^{p}(1-\frac{p}{2})=g(x^{*})and x^{*} is a global minimizer of (p‐RS).

Finally, from (3), if \hat{x} is also a global minimizer of (p‐RS), \hat{x} must minimize both\displaystyle \frac{1}{2}x^{T}Qx+c^{T}x and(\displaystyle\frac{|x\Vert^{2} {\Vertx^{*}|^{2} )^{2}B-2\Vertx\Vert^{2} simultaneously.
2\overline{\Vert x^{*}| ^{2}This can happen if and only if

Qx=-c and \Vert\hat{x}\Vert=\Vert x^{*}\Vert.
Remark 1

When p=3 , two other proofs of the necessary and sufficient condition can befound in Theorem 3.1 in l2J and Theorem 10 in [15J respectively.
,

We notice that the proof

51

in [2] is inherited from that of the necessary and sufficient condition for the trust‐region

subproblem l37 and the proof in l15\displaystyle \int highly relies on the special structure of the case p=3.
Our proof is much easier in understanding, since it is simply based on a direct comparison
between g(x) and g(x^{*}).

To characterize the set of global minimizers of (p‐RS),

we

may

assumethat H is

diagonal, i.e.,

H=\mathrm{D}\mathrm{i}\mathrm{a}\mathrm{g}(\mathrm{a}_{1}, \ldots, $\alpha$_{n})

(5)

,

where

$\alpha$_{1}=\ldots=$\alpha$_{k}<$\alpha$_{k+1}\leq\ldots\leq$\alpha$_{n}and k is the multiplicity of the smallest eigenvalue $\alpha$_{1}eigenvalue decomposition of Ha.

Let y=U^{T}x.

Otherwise, let H=U $\Sigma$ U^{T} be the.

Then \Vert y\Vert=\Vert U^{T}x\Vert=\Vert x\Vert and we obtain

diagonal version of (p‐RS) in terms of y.

Theorem 2 The set of global minimizers of (p‐RS) is either a singleton or a k ‐dimensional

Proof

Let x^{*} be any global minimizer of (p‐RS) and define t^{*}=\Vert x^{*}\Vert^{p-2}\geq 0.

Noticethat t^{*} is independent of the choice of x^{*} since the \ell_{2} norms of all the global minimizers areequal. By Theorem 1, $\alpha$_{i}+ $\sigma$ t^{*}\geq 0, \forall i=1 2,
,

.

.

.

n

,

.

That is, t^{*}\displaystyle \in(\max\{- $\alpha \Delta \sigma$, 0\}, +\infty).

Moreover, the solutions x^{*} satisfying (H+ $\sigma$ t^{*}I)x^{*}=-c define the set of the global
minimizers. If H+ $\sigma$ t^{*}I is invertible, the global minimizer x^{*} is uniquely defined by (thestill unknown t^{*} that)x_{i}^{*}=\underline{-c_{i}}i=1$\alpha$_{i}+ $\sigma$ t^{*}


,

..

.

,

n.

By summing all (x_{i}^{*})^{2}, t^{*} is necessarily a nonnegative root of the following secular function
on aspecific open interval:h(t)=\displaystyle \sum_{i=1}^{n}\frac{c_{i}^{2} {($\alpha$_{i}+ $\sigma$ t)^{2} -t\frac{2}{\mathrm{p}-2}, t\in I_{g}=(\max\{-\frac{$\alpha$_{1} { $\sigma$},0\}, +\infty)

.

(6)

52

Since

\displaystyle \lim_{t\rightar ow\max\{-\lrcorner^{$\alpha$_{0\}} $\sigma$},h(t)>0, \displaystyle \lim_{t\rightar ow+\infty}h(t)=-\infty and h(t) is strictly decreasingon

I_{g} the,secular function h(t) has a unique root on I_{g} , which must be t^{*}.

On the other hand, H+ $\sigma$ t^{*}I is singular in which case t^{*}=\displaystyle \frac{- $\alpha$ 1}{ $\sigma$}can not.

(Obviously, this casehappen for $\alpha$_{1}>0. ) Then, c_{1}^{2}+\ldots+c_{k}^{2}=0 and $\alpha$_{i}+ $\sigma$ t^{*}>0, i=k+1, k+2
,

,

..

.

,

n

such that\displaystyle \hat{x}^{*}=(0, \ldots, 0, \frac{-c_{k+1} {$\alpha$_{k+1}-$\alpha$_{1} , \ldots, \frac{-c_{ $\eta$} {$\alpha$_{n}-$\alpha$_{1} )^{T}

is one trivial solution to (H-$\alpha$_{1}I)x^{*}=-c.

(7)

By summing all (\hat{x}_{i}^{*})^{2} in (7), we again obtaina secular function\displaystyle\hat{h}(t)=\sum_{i=k+1}^{n}\frac{ _{i}^{2} {($\alpha$_{i}+$\sigma$t)^{2} -t\frac{2}{p-2},t\inI_{\hat{g} =[-\frac{$\alpha$_{1} {$\sigma$},+\infty)(8).

\hat{h}(t) is also strictly decreasing on I_{\hat{g} and \displaystyle \lim_{t\rightar ow+\infty}\hat{h}(t)=-\infty If \hat{h} (-\displaystyle \frac{ $\alpha$ 1}{ $\sigma$})=0,
then t^{*}=- $\alpha$\lrcorner $\sigma$ is the unique root of \hat{h}(t)I_{\overline{g} Thus, \hat{x}^{*} defined by (7) is the unique global
Notice that

.

on

.

minimizer of (p‐RS).

If \hat{h}(-\displaystyle \frac{ $\alpha$ 1}{ $\sigma$})<0 then (8) has no solution and the trivial solution \hat{x}^{*} to (H-$\alpha$_{1}I)x^{*}=-c
does not satisfy t^{*}=\displaystyle \frac{- $\alpha$ 1}{ $\sigma$}=\Vert\hat{x}^{*}\Vert^{p-2} Then, any x^{*} satisfying,.

(x_{1}^{*})^{2}+\displaystyle\ldots+(x_{k}^{*})^{2}+\sum_{i=k+1}^{n}\frac{ _{i}^{2} {($\alpha$_{i}-$\alpha$_{1})^{2} =(\frac{-$\alpha$_{1} {$\sigma$})^{\frac{2}{p-2}is a global minimizer of (p‐RS).

dimensional sphere centered at(9)Namely, the global minimum solution set forms a k‐(0, \displaystyle \cdots, 0, -\frac{\mathrm{C}k+1}{$\alpha$_{k+1- $\alpha$ 1} , \cdots, -\frac{\mathrm{c}_{n} {$\sigma$_{n}- $\sigma$ 1}) with the radius\sqrt{(\frac{$\alpha$_{1}{$\sigma$})^{\frac{2}p-2} \sum_{i-k+1}^{n}\frac{ _i}^{2}{($\alpha$_{i}-$\alpha$_{1})^{2} .
Otherwise, \hat{h} (-\displaystyle \frac{ $\alpha$ 1}{ $\sigma$})>0 then (8) has no solution and (9) cannot hold for any x^{*}
,

.

We

obtain a contradiction that (p‐RS) has no global minimizer. The proof is thus complete.

Finally, we show that (p‐RS) possesses some hidden convexity that its global minimizer
canbe obtained by solving an equivalently reformulated convex programming. We first

have

53

Proposition 1 Suppose H is diagonal. Let x^{*} be any global minimizer of (p‐RS), thenc_{t}x_{i}^{*}\leq 0, i=1
Proof

,

.

.

.

,

n.

Comparing x^{*} with \overline{x}=(-x_{1}^{*}, x_{2}^{*}, x_{3}^{*}, \ldots, x_{n}^{*}),

we

immediately have0\geq g(x^{*})-g(\overline{x})=c_{1}(x_{1}^{*}-\overline{x}_{1})=2c_{1}x_{1}^{*}.
A similar argument applying to all other components yields the result. This completes
the proof.

By Proposition 1, (p‐RS) and (10) below share the same optimal solution set.

\displaystyle\min\sum_{i=1}^{n}\{-$\alpha$_{2^{X_{i}^{2} $\Delta$+c_{$\eta$}x_{i}\+\frac{$\sigma$}{p}(\sum_{i=1}^{n}x_{i}^{2})^{2}$\epsilon$\mathrm{s}.

\mathrm{t}.

c_{t}x_{i}\leq 0,

i=1 ,

..

.

,

(10)

n.

Introducing the nonlinear one‐to‐one map:x_{i}=\left\{ begin{ar y}{l \sqrt{z_i},\mathrm{i}\mathrm{f}c_{\dot{$\tau$}\leq0,\ i=1,. n,\ -\sqrt{z_i},\mathrm{i}\mathrm{f}c_{\dot{$\tau$}>0, \end{ar y}\right.

(11)

the problem (10) becomes the following convex program:min\mathrm{s}.

\mathrm{t}.

-\displaystyle\sum_{i=1}^{n}|c_{$\eta$}|\sqrt{z_{i}+\frac{1}{2}\sum_{i=1}^{n}$\alpha$_{i}z_{i}+\frac{$\sigma$}{p}(\sum_{i=1}^{n}z_{i})^{2}$\epsilon$

z_{i}\geq 0,

i=1 ,

..

.

(12)

n.
,

The global optimal solution of (12) can be converted to generate x^{*} through the transfor‐
mation (11).

Remark 2 The first two derivatives of the secular function h(t)h'(t)=\displaystyle\sum_{i=1}^{n}\frac{-2$\sigma$c_{i}^{2}{($\alpha$_{i}+$\sigma$t)^{3}-\frac{2}{p-2}t^{\frac{4-}{p-}f_{2}andh'(t)=\displaystyle\sum_{i=1}^{n}\frac{6$\sigma$^{2}c_{i}^{2}{($\alpha$_{i}+$\sigma$t)^{4}-\frac{2(4-p)}{(p-2)^{2}t^{\frac{6-}{\mathrm{p}\text{∽}2-2.

are

54

h(t) is strictly decreasing on I_{g} and convex only for p\geq 4
ensures.

For p=3 ,if H\not\geq 0 (whichthat c\neq 0 ) and h is restricted to a finite subinterval of I_{g} covering t^{*} , by properly

choosing the regularization parameter $\sigma$, h(t) can be made convex. Notice that the secularfunction for (TRS) is always convex though.

3

Conclusions
Since the cubic regularization subproblem can be used to modify Newtons method

for solving unconstrained optimization problems, it is generally believed that the cubic

regularization subproblem is very close to (TRS) in spirit. Our comprehensive analysisonthe p‐‐regularized subproblems for general p>2 gives the most detailed comparison

between the two types of subproblems and confirms thatthey do share many similarfeatures.

References[1] D. Bienstock and A. Michalka, Polynomial Solvability of Variants of the Tmst‐Region
Subproblem, ACM‐SIAM Symposium on Discrete Algorithms (2014), pp. 380‐390.

[2] C. Cartis, N. I. M. Gould, Ph. L. Toint, Adaptive cubic regularisation methods forunconstrained optimization. Part I: motivation, convergence and numerical results,

Mathematical Programming, 127 (2011), pp. 245‐295.

[3] A. R. Conn, N. I. M. Gould, Ph. L. Toint, Trust‐Region Methods, Number 01 MPS‐
SIAM Series on optimization, Philadelphia, SIAM, 2000.

[4] E. Erkut, The discrete p ‐dispersion problem, European Journal of Operational Re‐
search 46 (1990), pp. 48−60

55[5] S. C. Fang, D. Gao, G. X. Lin, R. L. Sheu, W. Xing, Double Well Potential Function
and Its 0ptimization in The n ‐dimensional Real Space‐ Part I, to appear in Math.
Mech. Solids (2014) arXiv: 1410.5925[6] M. R. GAREY, D. S. JOHNSON, Computers and Intractability: A guide to the theoryof NP‐completeness, Freeman, San Francisco, 1979.

[7] D. M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comput.,2(1981), pp. 186‐197.

[8] N. I. M. Gould, D. P. Robinson, H. Sue Thorne, On solving trust‐region and otherregularised subproblems in optimization, Mathematical Programming Computation,2(2010), pp. 21‐57.
[9] A. Griewank, The modification of Newton^{\mathrm{Z}}s method for unconstrained optimization
by bounding cubic terms, Technical Report \mathrm{D}\mathrm{A}\mathrm{M}\mathrm{T}\mathrm{P}/\mathrm{N}\mathrm{A}12 Department of Applied,

Mathematics and Theoretical Physics, Cambridge University, Cambridge, UK, 1981.

[10] P. Hansen,

I.

Moon, Dispersing facilities

ona

network, Presentation

at

the

TIMS/ORSA Joint National Meeting, Washington, D.C. (1988)[11] Y. Hsia, R. L. Sheu, Trust Region Subproblem with a Fixed Number of Additional
Linear Inequality Constraints has Polynomial Complexity, arXiv:1312.1398, 2013[12] R. A. Horn, C. R. Johnson, Matrix Analysis, Cambridge: Cambridge University
Press, 1985.

[13] J. M. Martínez,Local minimizers

of quadratic function on Euclidean balls andspheres, SIAM J. optimization, 4(1994), pp. 159‐176.

[14] J. J. Moré, D. C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist.
COMpUt., 4(1983), pp. 553‐572.

56[15] Y. Nesterov, B. T. Polyak, Cubic regularization of Newton method and its global
performance, Math. Program., 108(2006), pp. 177‐205.

[16] D. C. Sorensen, Newtons method with a model trust region modification, SIAM J.
Numer. Anal., 19(1982), pp. 409‐426.

[17] M. Weiser, P. Deuflhard, B. Erdmann, Affine conjugate adaptive Newton methods fornonlinear elastomechanics, Optim. Methods Softw., 22(2007), pp. 413‐431.

[18] Y. Xia, S. C. Fang, R. L. Sheu, W. Xing, Double Well Potential Function and Its
optimization in The n‐dimensional Real Space— Part II, to appear in Math. Mech.
Solids (2014) arXiv: 1404. 1963