Journal of Convex Analysis Volume 2 (1995), No.1/2, 263–276

Lagrangian Stability and Global Optimality in Nonconvex Quadratic Minimization Over Euclidean Balls and Spheres

Pham Dinh Tao, Le Thi Hoai An

Mathematical Modelling and Applied Optimization Group, LMI, INSA Rouen, CNRS, URA 1378. BP 8, 76131 Mont Saint Aignan Cedex, France.

Received 19 July 1994 Revised manuscript received 28 November 1994

Dedicated to R. T. Rockafellar on his 60th Birthday

We prove in this paper the stability of the Lagrangian duality in nonconvex quadratic minimization over Euclidean balls and spheres. As direct consequences we state both global optimality conditions in these problems and detailed descriptions of the structure of their solution sets. These results are essential for devising solution algorithms.

Keywords : nonconvex quadratic minimization, stability of Lagrangian duality, global optimality conditions.

1. Introduction

In this paper we shall be concerned with the following nonconvex quadratic optimization problems

(Q_{1}) min\{\frac{1}{2}x^{T} Ax + b^{T} x : ∥x∥ ≤ r\}

(Q_{2}) min\{\frac{1}{2}x^{T} Ax + b^{T} x : ∥x∥ = r\}

where A is an n × n real symmetric matrix, b ∈ IR^{n}, r is a positive number. If A is positive semi-definite then (Q_{1}) is a convex quadratic problem. In general (Q_{1}) is nonconvex. Problem (Q_{2}), whose feasible domain is a sphere, is always nonconvex even if A is positive semi-definite. These are among the few nonconvex optimization problems which possess a complete characterization of their optimal solutions. These problems play an important role in optimization and numerical analysis ([1], [4], [8], [9], [11], [12], [16]). Golub et al. studied (Q_{2}) from both theoretical and computational viewpoints. In [3] the sensitivity of the solutions to primal problem was discussed.

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

264 P. D. Tao, L. T. H. An / Lagrangian stability in non convex quadratic minimization

Very recently, a characterization of local-nonglobal minimizers of (Q_{1}) and (Q_{2}) are investigated in [7]. In this paper we study the stability of the Lagrangian duality and global optimality relative to (Q_{1}) and (Q_{2}) in the case where their respective constraints are analytically expressed as \{x ∈ IR^{n} : \frac{1}{2}∥x∥^{2} ≤ \frac{1}{2}r^{2}\} and \{x ∈ IR^{n} : \frac{1}{2}∥x∥^{2} = \frac{1}{2}r^{2}\} (although these are one and the same problem). Their original analytical expressions will lead to a duality gap equal to infinity. By using Lagrangian duality we obtain some basic properties on the solutions of (Q_{1}), (Q_{2}) and their dual problems. We show that these nonconvex problems have no duality gap. The optimality conditions obtained by different ways in Gay [4], Moré-Sorensen [9], Fletcher ([2]) and Pham Dinh Tao et al. ([1], [10], [12]) immediately follow from these results. This paper constitutes the first part (Part I) of our work relative to nonconvex quadratic minimization over Euclidean balls and spheres. It is organized as follows. In the next section we collect some important problems which can be formulated in the forms of (Q_{1}) or (Q_{2}). The last section is dealing with the stability of Lagrangian duality and global optimality in (Q_{1}) and (Q_{2}). As direct consequences, complete characterizations of solutions for (Q_{1}) and (Q_{2}) are pointed out together with detailed descriptions of the structure of solution sets for (Q_{1}) and (Q_{2}). These results are essential for solution algorithms.

2. Examples

In this section we formulate the following problems in the forms of (Q_{1}) or (Q_{2}).

min\{\frac{1}{2}x^{T} Ax + b^{T} x : Bx = c, ∥x∥ = 1\} (Constrained Eigenvalue Problem, [3]) (2.1)

where B is (m × n) matrix (m < n) and c ∈ IR^{m},

min{∥Ax − b∥ :∥Cx − d∥ = r}
(Quadratically Constrained Least Squares Problem, [6])

(2.2)

min{∥Ax − b∥ : ∥Cx − d∥ ≤ r}  (2.3)

where A is a (m × n) matrix, C is a (p × n) matrix, b ∈ IR^{m} and d ∈ IR^{p},

min\{\frac{1}{2}x^{T} Ax + b^{T} x : \frac{1}{2}x^{T} Cx + d^{T} x ≤ r^{2}\}  (2.4)

where A, C are (n × n) symmetric positive semi-definite matrices. For problem (2.1) we assume that it has at least one solution and that rank(B) = m. Let Z be an orthogonal basis of Ker(B). Let y ∈ Im(B^{T}) such that By = c (since rank(B) = m, such a point y always exists). Thus for each x ∈ IR^{n} there exists z ∈ IR^{m} such that x = y + Zz. By a simple calculation we can show that (2.1) is equivalent to the following problem of the form (Q_{2}):

min\{\frac{1}{2}z^{T} A′z + b^{′T} z : ∥z∥ = s\}

where A′ = Z^{T} AZ, b′ = Z^{T} (Ay + c) and s^{2} = 1 − ∥y∥^{2}. Note that, since (2.1) has at least one solution, ∥y∥ ≤ 1. Now we show that (2.4) is of the form of (Q_{1}). We distinguish two cases: Case 1. C is positive definite. In this case the equation Cx = −d has a unique solution w = −C^{−1}d which minimizes the function

\frac{1}{2}x^{T} Cx + d^{T} x.

By Cholesky’s factorization we have C = R^{T} R ([5]). Using the variable y = R(x − w) we can write (2.4) in the form

min\{\frac{1}{2}y^{T} A′y + b′^{T} y : ∥y∥^{2} ≤ (1/2)s^{2}\}

where A′ = (R^{−1})^{T} AR, b′ = R^{−1}(Aw + b) and s^{2} = r^{2} + (1/2)w^{T} Cw. Case 2. C is positive semi-definite and d ∈ Im(C) = Ker(C^{T}). In this case we solve the equation Cx = −d by procedure QR ([5]). Suppose rank(C) = m, then we can find a submatrix C_{J} of rank m such that the equation Cx = −d is equivalent to C_{J}x = −d_{J}. This submatrix is given by

C_{J}^{T} = [Q̄_{1}, Q̄_{2}] [ \begin{matrix}R_{1} \\ 0 \end{matrix} ] = Q̄_{1}R_{1}

where R_{1} is an m × m upper-triangular matrix. Noting that Q̄_{1} is a basis of Im(C_{J}^{T}) and Q̄_{2} is basis of Ker(C_{J}) = Ker(C) we can write

x = Q̄_{1}y + Q̄_{2}z, y ∈ IR^{m}, z ∈ IR^{n−m}.

Let y^{∗} = R_{1}^{−T} d_{J}. Then it is clear that w = Q̄_{1}y^{∗} is a solution to the equation Cx = −d which minimizes the form

\frac{1}{2}x^{T} Cx + d^{T} x.

Moreover Q̄_{1}y^{∗} ∈ Im(C_{J}^{T}) has the minimal norm among the elements in Im(C_{J}^{T}). Problem (2.4) can thus be written as:

min\{q(y, z) = [\frac{1}{2}y^{T} Q̄_{1}^{T} AQ̄_{1}y + b^{T} Q̄_{1}y] + [\frac{1}{2}z^{T} Q̄_{2}^{T} AQ̄_{2}z + b^{T} Q̄_{2}z] + z^{T} Q̄_{2}^{T} AQ̄_{1}y\}

subject to

y ∈ U = {y ∈ IR^{m} : (y − y^{∗})^{T} Q̄_{1}^{T} CQ̄_{1}(y − y^{∗}) ≤ s^{2}}, z ∈ IR^{n−m},

where s^{2} = r^{2} + 1/2y^{∗}^{T} Q̄_{1}^{T} CQ̄_{1}y^{∗}. Note that Q̄_{1}^{T} CQ̄_{1} is positive definite and q(y, z) is a convex function of (y, z). Hence we have

min_{y∈U,z∈IR^{n−m}} q(y, z) = min_{y∈U} h(y)

where

h(y) = min{q(y, z) : z ∈ IR^{n−m}}  (2.5)

is a convex function. For each fixed y, z solves (2.5) if and only if

Q̄_{2}^{T} AQ̄_{2}z + Q̄_{2}^{T} b = −Q̄_{2}^{T} AQ̄_{1}y.  (2.6)

For simplicity we assume that A is positive definite (if A is positive semi- definite we can use the pseudo-inverse of A to obtain an analogous formula). In this case the solution of (2.5) takes the form

z = −(Q̄_{2}^{T} AQ̄_{2})^{−1}(Q̄_{2}^{T} b + Q̄_{2}^{T} AQ̄_{1}y).

Hence

h(y) = \frac{1}{2}y^{T} Gy + g^{T} y

where

\begin{matrix}G = & Q̄_{1}^{T} [A − AQ̄_{2}(Q̄_{2}^{T} AQ̄_{2})^{−1}Q̄_{2}^{T} A]Q̄_{1} \\ g = & [Q̄_{1}^{T} − \frac{1}{2}Q̄_{1}^{T} AQ̄_{2}(Q̄_{2}^{T} AQ̄_{2})^{−1}Q̄_{2}^{T}]b. \end{matrix}

Finally, setting u = y − y^{∗} it is easy to verify that (2.4) is equivalent to the problem given by

min\{\frac{1}{2}u^{T} A′u + b′^{T} u : u^{T} C′u ≤ s^{2}\}

where A′ is positive semi-definite and C′ is positive definite. The result then follows from case 1. Note that (2.3) is a special case of (2.4). In a similar way we can formulate problem (2.2) in the form of (Q_{2}).

3. Stability of the Lagrangian duality and global optimality conditions for Problems (Q_{1}) and (Q_{2})

3.1. Stability of the Lagrangian duality for problem (Q_{1})

In the first two parts of this section we study Lagrangian duality for Problems (Q_{1}) and (Q_{2}) by writing their constraints in the equivalent forms \{x ∈ IR^{n} : \frac{1}{2}∥x∥^{2} ≤ \frac{1}{2}r^{2}\} and \{x ∈ IR^{n} : \frac{1}{2}∥x∥^{2} = \frac{1}{2}r^{2}\}. We shall establish a characterization for the solutions of these problems and their duals. Stability of Lagrangian duality and optimality conditions can be easily derived from these results. Denote by λ_{1} ≤ λ_{2} ≤ … ≤ λ_{n} the eigenvalues of A and by u_{1}, u_{2} …, u_{n} their corresponding eigenvectors which constitute an orthogonal basis of IR^{n}. It is easy to see that for λ > −λ_{1} the solution to the linear equation

(A + λI)x = −b.  (3.1)

is given by

u_{i}^{T} x(λ) = \frac{−u_{i}^{T} b}{λ_{i} + λ} i = 1, …, n.  (3.2)

Let us describe now (Q_{1}) in the equivalent form which, for simplicity of notation, we also denote by (Q_{1})

α_{1} = min\{f(x) = \frac{1}{2}x^{T} Ax + b^{T} x : \frac{1}{2}∥x∥^{2} ≤ \frac{1}{2}r^{2}\}.  (Q_{1})

The Lagrangian function for this problem is defined by

L_{1}(x, λ) = \{ \begin{matrix}\frac{1}{2}x^{T} Ax + b^{T} x + \frac{λ}{2}(∥x∥^{2} − r^{2}) & if λ ≥ 0 \\ −∞ & otherwise . \end{matrix}

For each fixed λ ≥ 0 we define the problem

g_{1}(λ) = inf_{x∈IR^{n}}\{\frac{1}{2}x^{T} (A + λI)x + b^{T} x − \frac{λ}{2}r^{2}\}.  (Q_{λ}^{1})

Clearly, g_{1} is concave. The dual problem of (Q_{1}) is given as

β_{1} = sup{g_{1}(λ) : λ ≥ 0}.  (D_{1})

We denote by Q_{1}, Q_{λ}^{1},D_{1} the solution sets of (Q_{1}), (Q_{λ}^{1}),(D_{1}) respectively. First observe the following:

• If λ > −λ_{1} then (3.1) admits a unique solution given by

x(λ)^{T} u_{i} = −\frac{b^{T} u_{i}}{λ + λ_{i}} , i = 1, …, n and ∥x(λ)∥^{2} = ∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ + λ_{i})^{2}}  (3.3)

• If λ = −λ_{1} and b ∈ Ker(A − λ_{1}I)^{⊥} then P_{λ}^{1} = x^{+} + Ker(A − λ_{1}I) where x^{+} = −(A − λ_{1}I)^{+}b given by ((A − λ_{1}I)^{+} stands for the pseudo-inverse of (A − λ_{1}I))

(i) If b = 0 then x^{+} = −(A − λ_{1}I)^{+}b = 0. (ii) If b ≠ 0 then the complement in {1, …, n} of J_{1} = {i = 1, …, n : λ_{i} = λ_{1}} is

nonempty and

x^{+}^{T} u_{i} = −\frac{b^{T} u_{i}}{λ + λ_{i}} , i ∉ J_{1} and ∥x^{+}∥^{2} = ∑_{i∉J_{1}} \frac{(b^{T} u_{i})^{2}}{(λ + λ_{i})^{2}} .  (3.4)

Proposition 3.1.

(i) dom g_{1} = {λ ∈ IR : λ ≥ 0, λ + λ_{1} ≥ 0 and b ∈ Ker(A + λI)^{⊥}}. (ii)

g_{1}(λ) = \frac{1}{2}b^{T} x − \frac{r^{2}}{2} λ = −\frac{1}{2}b^{T} (A + λI)^{+}b − \frac{r^{2}}{2} λ, ∀x ∈ Q_{λ}^{1}, ∀λ ∈ dom g_{1}.

Proof. dom g_{1} := {λ ≥ 0 : g_{1}(λ) > −∞} .

(i) If λ + λ_{1} < 0 then λ ∉ dom g_{1}. Indeed x̄ ∈ Ker(A − λ_{1}I) implies

lim_{∥x̄∥→∞}⟨(A + λI)x̄, x̄⟩ + ⟨b, x̄⟩ = lim_{∥x̄∥→∞}(λ + λ_{1})∥x̄∥^{2} + ⟨b, x̄⟩ = −∞.

Hence g_{1}(λ) = −∞. If λ ≥ 0 and λ + λ_{1} ≥ 0, then (Q_{λ}^{1}) is a convex problem and x̄ ∈ Q_{λ}^{1} ⇔ (A + λI)x̄ = −b. Thus λ ∈ dom g_{1} if and only if (3.1) has a solution, i.e., b ∈ Ker(A + λI)^{⊥}. (ii) This is immediate from the definition of g_{1} and the fact

∀λ ∈ dom g_{1} : Q_{λ}^{1} = (A + λI)^{+}b + Ker(A + λI).

Set g̃_{1}(λ) = −g_{1}(λ). Clearly g̃_{1} is convex and dom g̃_{1} = dom g_{1}.

The following proposition is a direct consequence of Proposition 3.1 and (3.3), (3.4):

Proposition 3.2.

(i) If λ ≥ 0 and λ + λ_{1} > 0 then λ ∈ dom g̃_{1}, and

g̃_{1}(λ) = \frac{1}{2} ∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{λ_{i} + λ} + \frac{r^{2}}{2} λ.  (3.5)

In this case g̃_{1} is differentiable for every λ > 0, and

g̃′_{1}(λ) = −\frac{1}{2}∥x(λ)∥^{2} + \frac{r^{2}}{2} .  (3.6)

In particular, if λ_{1} > 0 then dom g̃_{1} = [0, ∞[ and (3.5) is satisfied for every λ ∈ dom g̃_{1}. In this case g̃_{1} is subdifferentiable at 0, and

∂g̃_{1}(0) =] − ∞, −\frac{1}{2}∥x(0)∥^{2} + \frac{r^{2}}{2} ].

(ii) If λ_{1} ≤ 0 and b ∈ Ker(A−λ_{1}I)^{⊥} then dom g̃_{1} = [−λ_{1}, +∞[, and for every λ ∈ dom g̃_{1} we have:

• If b = 0 then g̃_{1}(λ) = \frac{r^{2}}{2} λ.

• If b ≠ 0 then {1, …, n}\J_{1} is nonempty and

g̃_{1}(λ) = \frac{1}{2} ∑_{i∉J_{1}} \frac{(b^{T} u_{i})^{2}}{λ_{i} + λ} + \frac{r^{2}}{2} λ.

In this case g̃_{1} is subdifferentiable at −λ_{1}, and

∂g̃_{1}(−λ_{1}) =] − ∞, −\frac{1}{2}∥x^{+}∥^{2} + \frac{r^{2}}{2} ].

(iii) If λ_{1} ≤ 0 and b ∉ Ker(A − λ_{1}I)^{⊥}, then dom g̃_{1} =] − λ_{1}, +∞[ and for each λ ∈ dom g̃_{1} the function g̃_{1}(λ) is defined by (3.5). In this case g̃_{1} is differentiable at every λ ∈ dom g̃_{1}, and g̃′_{1} is defined by (3.6).

Now we give some results concerning the characterizations of the solution to the dual problem.

Theorem 3.3.

(i) D_{1} is a singleton. (ii) Let λ^{∗} ≥ 0, λ^{∗} > −λ_{1}. Then λ^{∗} ∈ D_{1} if and only if ∥x(λ^{∗})∥ = r. In particuliar, if

λ_{1} > 0 then 0 ∈ D_{1} if and only if ∥x(0)∥ ≤ r. (iii) Let λ^{∗} = −λ_{1} ≥ 0. Then λ^{∗} ∈ D_{1} if and only if b ∈ Ker(A − λ_{1}I)^{⊥} and ∥x^{+}∥ ≤ r.

Proof. First we remark that (D_{1}) is a convex program having always one solution, since g̃_{1} is coercive. In fact

(D_{1}) ⇔ (D̃_{1})  inf_{λ≥0} g̃_{1}(λ) = inf_{λ∈dom g̃_{1}} g̃_{1}(λ)

and by (3.5), lim_{λ→+∞} g̃_{1}(λ) = +∞. Again by (3.5): g̃′′_{1}(λ) > 0, ∀λ > −λ_{1}, i.e., g̃_{1} is strictly convex in ] − λ_{1}, +∞[, consequently (D_{1}) contains one element. Hence (i). (ii) and (iii) are immediate from Proposition 3.2 and from the fact λ^{∗} ∈ D_{1} ⇔ 0 ∈ ∂g̃_{1}(λ^{∗}).

The following corollary shows the stability of the duality for (Q_{1}):

Corollary 3.4. α_{1} = β_{1} and

Q_{1} = {x^{∗} ∈ Q_{λ^{∗}}^{1} : λ^{∗}(∥x^{∗}∥ − r) = 0, ∥x^{∗}∥ ≤ r}, D_{1} = {λ^{∗}}.

Proof. Let E = {x ∈ X : ∥x∥ ≤ r} and χ_{E} be its indicator function, i.e. χ_{E}(x) = 0 if x ∈ E, χ_{E}(x) = +∞ otherwise. From the definition of L_{1}(x, λ) we have sup{L_{1}(x, λ) : λ ≥ 0} = (f + χ_{E})(x). Hence

α_{1} = inf_{x∈X}(f + χ_{E})(x) = inf_{x∈X} sup_{λ≥0} L_{1}(x, λ) ≥ sup_{λ≥0} inf_{x∈X} L(x, λ) = sup_{λ≥0} g_{1}(λ) = β_{1}.

Therefore to prove the Corollary it is sufficient to point out a point (x^{∗}, λ^{∗}) ∈ IR^{n} × IR satisfying L_{1}(x^{∗}, λ) ≤ L_{1}(x^{∗}, λ^{∗}) ≤ L_{1}(x, λ^{∗}), ∀(x, λ) ∈ X × IR, i.e. (x^{∗}, λ^{∗}) is a saddle point of L_{1}. Let λ^{∗} ∈ D_{1}. If λ^{∗} > −λ_{1} we have from Theorem 3.3 ∥x(λ^{∗})∥ = r (or ∥x(λ^{∗})∥ ≤ r if λ^{∗} = 0). Thus in this case Q_{λ^{∗}}^{1} contains a unique point x^{∗} which satisfies the complementarity condition (CP) λ^{∗}(∥x^{∗}∥ − r) = 0. If λ^{∗} = −λ_{1}, again by Theorem 3.3, ∥x^{+}∥ ≤ r and b ∈ Ker(A − λ_{1}I)^{⊥} which implies

Q_{λ^{∗}}^{1} = x^{+} + Ker(A − λ_{1}I).

Hence we can choose x^{∗} ∈ Q_{λ^{∗}}^{1}, ∥x^{∗}∥ = r which implies λ^{∗}(∥x^{∗}∥ − r) = 0.

Consequently, in both cases we have

α_{1} ≤ \frac{1}{2}x^{∗}^{T} Ax^{∗} + b^{T} x^{∗} = \frac{1}{2}x^{∗}^{T} Ax^{∗} + b^{T} x^{∗} + \frac{λ^{∗}}{2} (∥x^{∗}∥^{2} − r^{2}) = β_{1}.

Remark 3.5. We remark that in the above presentation the form \{x ∈ IR^{n} : \frac{1}{2}∥x∥^{2} ≤ \frac{1}{2}r^{2}\} is essential. If we take the equivalent constraint \{x ∈ IR^{n} : ∥x∥ ≤ r\} the dual optimal value will be −∞ if λ_{1} < 0. Indeed, in this case the function g_{1}(λ) is defined by

g_{1}(λ) = inf_{x∈IR^{n}}\{\frac{1}{2}⟨x, Ax⟩ + ⟨x, b⟩ + \frac{1}{2}λ(∥x∥ − r)\}, for λ ≥ 0.

Then if x̄ ∈ Ker(A − λ_{1}I) we have

lim_{∥x̄∥→+∞} \frac{1}{2}⟨x̄, Ax̄⟩ + ⟨x̄, b⟩ + \frac{1}{2}λ(∥x̄∥ − r) = lim_{∥x̄∥→+∞} \frac{1}{2}λ_{1}∥x̄∥^{2} + ⟨x̄, b⟩ + \frac{1}{2}λ(∥x̄∥ − r) = −∞

and therefore g_{1}(λ) = −∞ for every λ ≥ 0. Hence β_{1} = −∞.

3.2. Stability of the Lagrangian duality for Problem (Q_{2})

The Lagrangian function of the problem

α_{2} = min\{\frac{1}{2}x^{T} Ax + b^{T} x : \frac{1}{2}∥x∥^{2} = \frac{1}{2}r^{2}\}  (Q_{2})

is

L_{2}(x, λ) = \frac{1}{2}x^{T} Ax + b^{T} x + \frac{λ}{2}(∥x∥^{2} − r^{2}), λ ∈ IR.

Let g_{2}(λ) be the function on IR given by

g_{2}(λ) = inf{L_{2}(x, λ) : x ∈ IR^{n}}.  (Q_{λ}^{2})

Then the dual problem of (Q_{2}) takes the form

β_{2} = sup{g_{2}(λ) : λ ∈ IR}.  (D_{2})

As before we denote by Q_{2}, Q_{λ}^{2} and D_{2} the solution sets of problems (Q_{2}), (Q_{λ}^{2}) and (D_{2}) respectively. Let g̃_{2}(λ) = −g_{2}(λ), ∀λ ∈ IR. In a similar way one can show the following results concerning the stability of the Lagrangian duality for problem (Q_{2}). The first ones correspond to Proposition 3.1 and 3.2.

Proposition 3.6.

(i) dom g_{2} = {λ ∈ IR : λ ≥ −λ_{1}, and b ∈ Ker(A + λI)^{⊥}}. (ii)

g_{2}(λ) = \frac{1}{2}b^{T} x − \frac{r^{2}}{2} λ = −\frac{1}{2}b^{T} (A + λI)^{+}b − \frac{r^{2}}{2} λ, ∀x ∈ Q_{λ}^{2}.

Proposition 3.7.

(i) If b ∉ Ker(A − λ_{1}I)^{⊥} then dom g̃_{2} =] − λ_{1}, +∞[, and ∀λ ∈ dom g̃_{2}

g̃_{2}(λ) = \frac{1}{2} ∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{λ_{i} + λ} + \frac{r^{2}}{2} λ.

(ii) If b ∈ Ker(A − λ_{1}I)^{⊥} then dom g̃_{2} = [−λ_{1}, +∞[ and for every λ ∈ dom g̃_{2} we have:

• If b = 0 then g̃_{2}(λ) = \frac{r^{2}}{2} .

• If b ≠ 0 then {1, …, n}\J_{1} is nonempty and

g̃_{2}(λ) = \frac{1}{2} ∑_{i∉J_{1}} \frac{(b^{T} u_{i})^{2}}{λ_{i} + λ} + \frac{r^{2}}{2} λ.

In this case g̃_{2} is subdifferentiable at −λ_{1}, and

∂g̃_{2}(λ_{1}) =] − ∞, −\frac{1}{2}∥(A − λ_{1}I)^{+}b∥^{2} + \frac{r^{2}}{2} ].

(iii) ∀λ > −λ_{1} we have λ ∈ dom g̃_{2}, g̃_{2} is differentiable at λ, and

g̃′_{2}(λ) = −\frac{1}{2}∥x(λ)∥^{2} + \frac{r^{2}}{2} .

Finally we state below the analogues of Theorem 3.3 and its Corollary.

Theorem 3.8.

(i) D_{2} is a singleton. (ii) Let λ^{∗} > −λ_{1}. Then λ^{∗} ∈ D_{2} if and only if ∥x(λ^{∗})∥ = r. (iii) Let λ^{∗} = −λ_{1}. Then λ^{∗} ∈ D_{2} if and only if b ∈ Ker(A − λ_{1}I)^{⊥} and ∥x^{∗}∥ ≤ r

Corollary 3.9. α_{2} = β_{2}; Q_{2} = {x^{∗} ∈ Q_{λ^{∗}}^{2} : ∥x^{∗}∥ = r}, D_{2} = {λ^{∗}}.

3.3. Global optimality conditions for (Q_{1}) and (Q_{2})

The preceding results concerning the stability of Lagrangian duality relative to (Q_{1}) and (Q_{2}) imply, as direct consequences, the following two theorems on global optimality conditions for these problems.

Theorem 3.10. ([4]) x^{∗} is an optimal solution to Problem (Q_{1}) if and only if there exists λ^{∗} ≥ 0 such that

(i) (A + λ^{∗}I) is positive semi-definite, (ii) (A + λ^{∗}I)x^{∗} = −b, (iii) λ^{∗}(∥x^{∗}∥ − r) = 0, ∥x^{∗}∥ ≤ r. This λ^{∗} is unique.

We note that (Q_{2}) is equivalent to the following problem of the form (Q_{1}):

min\{\frac{1}{2}x^{T} (A + γI)x + b^{T} x : ∥x∥ ≤ r\},  (3.8)

where γ is a real number so that A + γI is nonpositive semi- definite. Indeed, (Q_{2}) is equivalent to

min\{\frac{1}{2}x^{T} (A + γI)x + b^{T} x : ∥x∥ = r\}  (3.9)

because ⟨x, γx⟩ = γr^{2} if ∥x∥ = r. On the other hand, if A + γI is nonpositive semi-definite, then the solution set of (3.1) is necessarily contained in the boundary {x : ∥x∥ = r}, according to Theorem 3.10. It implies the equivalence of Problems (3.1) and (3.2). In [16] Sorensen gave a sufficient condition for optimality to problem (Q_{2}). In [10] Pham Dinh Tao proved that this condition is necessary and sufficient. This result was also given partly in Fletcher ([2]) by using the optimality condition for (Q_{1}).

Theorem 3.11. ([10], [2], [12]) x^{∗} is an optimal solution to (Q_{2}) if and only if there exists λ^{∗} such that

(i) (A + λ^{∗}I) is positive semi-definite (ii) (A + λ^{∗}I)x^{∗} = −b, (iii) ∥x^{∗}∥ = r. This number λ^{∗} is unique.

3.4. More on the structure of solution sets for (Q_{1}) and (Q_{2})

Let us consider now the following two functions ϕ and ψ definied on IR\{−λ_{i} : i = 1, …, n}

ϕ(λ) = ∥x(λ)∥

where x(λ) is the solution of (A + λI)x = −b,

ψ(λ) = \frac{1}{r} − \frac{1}{ϕ(λ)} if b ≠ 0.

Numerical approaches by Moré & Sorensen [9], Pham Dinh Tao [10] – [12] and Golub et al [6] for solving (Q_{1}) and (Q_{2}) involve the following equation (referred to as secular equation by Golub et al. [6] in case there is λ^{o} ≥ 0, λ^{o} > −λ_{1} such that ϕ(λ^{o}) ≥ r (such a case implies b ≠ 0):

ϕ(λ) = r.  (3.10)

The Safeguarding by Moré & Sorensen and the Dichotomy algorithm use, for solving (3.10), an adapted Newton-like algorithm (called Hebden algorithm) which is nothing else than the Newton method applied to solving

ψ(λ) = 0.

The hard case corresponds to the situation where λ^{∗} = −λ_{1}. One must then adapt other techniques to compute primal and dual solutions. The stability of Lagrangian duality relative to (Q_{1}) and the main properties of ϕ, ψ given below show that solving (3.10) amounts to computing the dual solution λ^{∗} (of (D_{1})) and the corresponding primal solution x(λ^{∗}) (of (Q_{1})). Moreover in the hard case, ϕ is multivalued at λ^{∗} = −λ_{1} since g̃_{1} is no longer differentiable at −λ_{1}.

Proposition 3.12. Assume that b ≠ 0, then

(i) ϕ ∈ C^{∞}(IR\{−λ_{i} : i = 1, …, n}) is strictly convex on each open interval contained in IR\{−λ_{i} : i = 1, …, n} and strictly decreasing on (−λ_{1}, +∞). More precisely one has, for λ ∉ {−λ_{i} : i = 1, …, n},

ϕ′(λ) = −\frac{1}{ϕ(λ)} ∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{3}}  (3.11)

ϕ′′(λ) = \frac{2}{ϕ(λ)} ∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{3}} + \frac{1}{ϕ(λ)} \{∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{4}} − \frac{1}{ϕ^{2}(λ)} [∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{3}} ]^{2}\} (3.12)

If b ∉ IN(A − λ_{1}I)^{⊥} then lim_{λ↓−λ_{1}} ϕ(λ) = +∞. If b ∈ IN(A − λ_{1}I)^{⊥} then ϕ(λ) = ∥(A − λ_{1}I)^{+}b∥ for λ > −λ_{1} and lim_{λ↓−λ_{1}} ϕ(λ) = ∥(A − λ_{1}I)^{+}b∥. (ii) ψ ∈ C^{∞}(IR\{−λ_{i} : i = 1, …, n}) is strictly convex on each open interval contained in IR\{−λ_{i} : i = 1, …, n} and strictly decreasing on (−λ_{1}, +∞). More precisely, if θ(λ) = −1/ϕ(λ) = ψ(λ) − (1/r) then one has for λ ∉ {−λ_{i} : i = 1, …, n}

θ′(λ) = ϕ(λ)^{−2}ϕ′(λ),  (3.13)

θ′′(λ) = \frac{3}{ϕ(λ)^{3}} \{∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{4}} − \frac{1}{ϕ(λ)^{2}} [∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{3}} ]^{2}\} .  (3.14)

(iii) For λ ∈ dom g̃_{1} such that λ ≥ −λ_{1}, one has

ϕ^{2}(λ) = \frac{r^{2}}{2} − g̃_{1}(λ), if λ > −λ_{1}.

So ϕ(λ) can be extended at λ = −λ_{1} ∈ dom g̃_{1} by

ϕ^{2}(−λ_{1}) = [∥(A − λ_{1}I)^{+}b∥^{2}, +∞).

Proof. It suffices to prove that ϕ′′(λ) ≥ 0 and θ′′(λ) ≥ 0 for λ ∉ {−λ_{i} : i = 1, …, n}. The other results are either direct computational derivatives or direct consequences of Proposition 2. For this we shall prove that

∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{4}} − \frac{1}{ϕ^{2}(λ)}[∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{3}} ]^{2} ≥ 0

for λ ∉ {−λ_{i} : i = 1, …, n}. We can write for such a λ

∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{3}} = ∑_{i=1}^{n} \frac{b^{T} u_{i}}{(λ_{i} + λ)^{2}} \frac{b^{T} u_{i}}{λ_{i} + λ}

So by Schwarz’s inequality we obtain

∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{3}} ≤ [∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{4}} ]^{1/2}[∑_{i=1}^{n} \frac{(b^{T} u_{i})^{2}}{(λ_{i} + λ)^{2}} ]^{1/2}

that is equivalent to the above inequality.

Remark 3.13. If b = 0 then ϕ(λ) = 0 for every λ ∉ {−λ_{i} : i = 1, …, n} and ψ(λ) is no longer defined for such λ. In this case the solution set of (Q_{1}) will be given in Proposition 3.14 Now let us deduce from the preceding results some direct consequences about the structure of primal and dual solutions of (Q_{1}) (resp. (Q_{2})) and (D_{1}) (resp. (D_{2})). These properties are of great usefulness for their solution methods.

Proposition 3.14.

1. Assume that b ≠ 0.

(i) If λ_{1} > 0 (i.e. A is positive definite) one has

• If ∥A^{−1}b∥ ≤ r then D_{1} = {λ^{∗} = 0} and Q_{1} = {x(0) = −A^{−1}b}.

• If ∥A^{−1}b∥ = r then D_{1} = D_{2} = {λ^{∗} = 0} and Q_{1} = Q_{2} = {x(0) = −A^{−1}b}.

• If ∥A^{−1}b∥ < r then

(a) If b ∉ Ker(A−λ_{1}I)^{⊥} or b ∈ Ker(A−λ_{1}I)^{⊥} and ∥(A−λ_{1}I)^{+}b∥ > r then D_{2} = {λ^{∗}} with −λ_{1} < λ^{∗} < 0 and Q_{2} = {x(λ^{∗}) = −(A + λ^{∗}I)^{−1}b}, where λ^{∗} is the unique solution of the equation

ϕ(λ) = r.  (3.15)

(b) If b ∈ Ker(A − λ_{1}I)^{⊥} and ∥(A − λ_{1}I)^{+}b∥ ≤ r then D_{2} = {λ^{∗} = −λ_{1}} and

Q_{2} = {x = −x^{+} + u : ∥x∥^{2} = ∥x^{+}∥^{2} + ∥u∥^{2} = r^{2}}.

• If ∥A^{−1}b∥ > r then D_{1} = D_{2} = {λ^{∗} > 0} where λ^{∗} is the unique solution of (3.15) and Q_{1} = Q_{2} = {x(λ^{∗}) = −(A + λ^{∗}I)^{−1}b}. (ii) If λ_{1} = 0 (i.e. A is positive semi-definite ) one has

• If ∥A^{+}b∥ ≤ r and b ∈ Ker(A)^{⊥} then D_{1} = D_{2} = {0}

Q_{1} = {x = −x^{+} + u, u ∈ Ker(A) such that ∥x∥^{2} = ∥x^{+}∥^{2} + ∥u∥^{2} ≤ r^{2}},

Q_{2} = {x = −x^{+} + u, u ∈ Ker(A) such that ∥x∥^{2} = ∥x^{+}∥^{2} + ∥u∥^{2} = r^{2}}.

• If b ∉ Ker(A)^{⊥} or b ∈ Ker(A)^{⊥} and ∥A^{+}b∥ > r then D_{1} = D_{2} = {λ^{∗} > 0} where λ^{∗} is the unique solution of (3.15) and Q_{1} = Q_{2} = {x(λ^{∗}) = −(A + λ^{∗}I)^{−1}b}. (iii) If λ_{1} < 0 (i.e. A is nonpositive semi-definite) then

• If ∥(A − λ_{1}I)^{+}b∥ ≤ r and b ∈ Ker(A − λ_{1}I)^{⊥} then D_{1} = D_{2} = {−λ_{1}} and

Q_{1} = Q_{2} = {x = −x^{+} + u, u ∈ Ker(A − λ_{1}I), such that ∥x∥^{2} = ∥x^{+}∥^{2} + ∥u∥^{2} = r^{2}}

• If b ∉ Ker(A − λ_{1}I)^{⊥} or b ∈ Ker(A − λ_{1}I)^{⊥} and ∥(A − λ_{1}I)^{+}b∥ > r then D_{1} = D_{2} = {λ^{∗} > 0} where λ^{∗} is the unique solution of (3.15) and Q_{1} = Q_{2} = {x(λ^{∗}) = −(A + λ^{∗}I)^{−1}b}.

2. Assume that b = 0.

(i) If λ_{1} > 0 then D_{1} = {0}, Q_{1} = {0}, D_{2} = {−λ_{1}} and Q_{2} = {x ∈ Ker(A − λ_{1}I) : ∥x∥ = r} .

(ii) If λ_{1} = 0 then D_{1} = {0}, Q_{1} = {x ∈ Ker(A) : ∥x∥ ≤ r}, D_{2} = {0}, Q_{2} = {x ∈

Ker(A) : ∥x∥ = r}. (iii) If λ_{1} < 0 then Q_{1} = Q_{2} = {x ∈ N (A − λ_{1}I) : ∥x∥ = r}.

Remark 3.15. It is worth noting that (A−λ_{1}I)(A−λ_{1}I)^{+}b = b ⇔ b ∈ Ker(A−λ_{1}I)^{⊥}. The following result concerning finiteness of the solution set to (Q_{1}) is very useful for proving the convergence of the whole sequence {x^{k}} (generated by DCA) to a solution of (Q_{1}).

Corollary 3.16. Q_{1} is finite if and only if Q_{1} is a singleton. More precisely Q_{1} is finite if and only if ∥(A + λ^{∗}I)^{+}b∥ = r where D_{1} = {λ^{∗}}. In this case we have

Q_{1} = {−(A + λ^{∗}I)^{+}b}  (3.16)

Q_{2} is finite if and only if either of the following properties holds:

(i) ∥A + λ^{∗}I)^{+}b∥ = r where D_{2} = {λ^{∗}}.

This condition is in fact necessary and sufficient for D_{2} to be a singleton:

Q_{2} = {−(A + λ^{∗}I)^{+}b}  (3.17)

(ii) ∥A + λ^{∗}I)^{+}b∥ < r where λ^{∗} ∈ D_{2} and Ker(A + λ^{∗}I) is a one dimensional subspace. This condition is in fact necessary and sufficient for | D_{2} | to be equal to 2. (| D_{2} | denotes the number of elements in D_{2}).

Finally the following nice result which has been stated very recently by Martinez [7] strengthens the ability for DCA to reach a solution (global minimum) of (Q_{1}):

Theorem 3.17.

(i) If x^{∗} is local-nonglobal minimum for (Q_{1}) or (Q_{2}) then (A + λ^{∗}I)x^{∗} = −b with λ^{∗} ∈] − λ_{2}, −λ_{1}[ and ϕ′(λ^{∗}) ≥ 0. If x^{∗} is a local-nonglobal minimum for (Q_{1}) then λ^{∗} ≥ 0.

(ii) There exists at most one local-nonglobal minimum for (Q_{1}) or (Q_{2}). (iii) If ∥x^{∗}∥ = r, (A + λ^{∗}I)x^{∗} = −b for some λ^{∗} ∈] − λ_{2}, −λ_{1}[ and ϕ′(λ^{∗}) > 0 then x^{∗} is

a strict local minimum for (Q_{2}).

If, in addition, λ^{∗} > 0, x^{∗} is also a strict local minimum for (Q_{1}). (iv) If b is orthogonal to some eigenvector associated with λ_{1}, then there are no local-

nonglobal minimum for (Q_{1}) and (Q_{2}).

Conclusion. We have completed a thorough study on the stability of Lagrangian duality and global optimality conditions for nonconvex quadratic minimization over Euclidean balls and spheres. These results, especially the main properties, in Proposition 3.12, of ϕ and ψ, the detailed description of solution sets for (Q_{1}) and (Q_{2}) in Proposition 3.14 and the finiteness of their solution sets in Corollary 3.16, should be essential for devising solution algorithms. This paper constitutes the theoretical part (Part I) of our work relative to nonconvex quadratic minimization over Euclidean balls and spheres.

276 P. D. Tao, L. T. H. An / Lagrangian stability in non convex quadratic minimization

Acknowledgment. We would like to thank Professors Hoang Tuy and Le Dung Muu for their careful reading and constructive criticism. Their useful comments substantially clarified the presentation and corrected some inaccuracies.

References

[1] J.R. Clermont, M.E de la Lande and Pham Dinh Tao: Analysis of plane and axisymmetric flows of incompressible fluids with the stream tube method: Numerical simulation by Trust region algorithm, Inter. J. for Numer. Method in Fluids, vol. 13, 371–399, 1991.

[2] R. Fletcher: Practical methods of optimization, A Wiley-Interscience publication, Second Edition, 1991.

[3] W. Gander, G.H. Golub and U. von Matt: A constrained eigenvalue problem, Linear Algebra and its Application, 114/115, 815–839, 1989.

[4] D.M. Gay: Computing optimal locally constrained steps, SIAM J. Sci. Stat. Comput., 2, 186–197, 1981.

[5] G.H Golub, C. van Loan: Matrix computation, North Oxford Academic, Oxford, 1989.

[6] G.H. Golub, U. von Matt: Quadratically constrained least squares and quadratic problems, Numer. Math. 59, 561–580, 1991.

[7] J. Martinez: Local minimizers of quadratic functions on euclidean balls and spheres, SIAM J. Optimization, Vol.4, No 1, 159–176, 1994.

[8] J.J. More: Recent developments in algorithm and software for Trust Region Methods. Mathematical Programming, The State of the Art, Springer, Berlin, 258–287, 1983.

[9] J.J. More, D.C. Sorensen: Computing a trust region step. SIAM J. Sci. Stat. Comput., 4, 553–572, 1983.

[10] Pham Dinh Tao: Méthodes numériques pour la minimisation globale d’une forme quadratique (convexe ou non convexe) sur une boule et une sphère euclidiennes. Rapport de recherche. Université Joseph-Fourier, Grenoble, 1989.

[11] Pham Dinh Tao, S.Wang: Training multi-layered neural network with a Trust region based algorithm, Math. Modell. Numer. Anal. (M^{2}AN), 24(4), 523–553, 1990.

[12] Pham Dinh Tao, Le Thi Hoai An: Minimisation globale d’une forme quadratique sur une boule et une sphère euclidiennes. Stabilité de la dualité lagrangienne. Optimalité globale. Méthodes numériques. Rapport de Recherche, L.M.I, CNRS URA 1378, INSA-Rouen, 1992.

[13] Pham Dinh Tao, Le Thi Hoai An and Thai Quynh Phong: Numerical methods for globally solving a class of nonconvex quadratic programming, Submitted

[14] B. Polyak: Introduction to Optimization. Optimization Software, Inc., Publication Division, New York, 1987.

[15] R.T. Rockafellar: Monotone operators and the proximal point algorithm in convex programming, SIAM J. on Control and Optim., 14, 877–898, 1976.

[16] D.C. Sorensen: Newton’s method with a model trust region modification, SIAM J. Numer. Anal., 19(2), 409–426, 1982.

[17] J.F. Toland: Duality in Nonconvex Optimization. J. Math. Anal. Appl., 66, 399–415, 1978.