ARGONNE NATIONAL LABORATORY 9700 South Cass Avenue Argonne, Illinois 60439

GENERALIZATIONS OF THE TRUST REGION PROBLEM

Jorge J. Moré

Mathematics and Computer Science Division

Preprint MCS-P349-0193

January 1993

This work was supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.

ABSTRACT

The trust region problem requires the global minimum of a general quadratic function subject to an ellipsoidal constraint. The development of algorithms for the solution of this problem has found applications in nonlinear and combinatorial optimization. In this paper we generalize the trust region problem by allowing a general quadratic constraint. The main results are a characterization of the global minimizer of the generalized trust region problem, and the development of an algorithm that finds an approximate global minimizer in a finite number of iterations.

GENERALIZATIONS OF THE TRUST REGION PROBLEM

Jorge J. Moré

1 Introduction

Trust region methods for the minimization of a function f : IR^{n} → IR require an approximate minimizer of a problem of the form

min{q(x) : ∥Dx∥_{2} ≤ Δ},  (1.1)

where q : IR^{n} → IR is a quadratic model of the function in a neighborhood of the current iterate, D is a nonsingular matrix that specifies the scaling of the variables, and Δ is determined by the trust region method. An interesting and surprising aspect of this problem is that it is possible to obtain a characterization of the global minimizer. This result, due to Gay [5] and Sorensen [17], is that x^{∗} is a global minimizer if and only if ∥Dx^{∗}∥ ≤ Δ, the Kuhn-Tucker condition

∇q(x^{∗}) + λ^{∗}D^{T} Dx^{∗} = 0

is satisfied, and the Hessian of the Lagrangian

∇^{2}q(x^{∗}) + λ^{∗}D^{T} D  (1.2)

is positive semidefinite for some λ^{∗} ≥ 0 such that λ^{∗} = 0 if ∥Dx^{∗}∥ < Δ. The surprising aspect of this result is that it holds for any quadratic q; there is no assumption of convexity.

Gay [5] and Sorensen [17] used this characterization result to develop an algorithm for the solution of (1.1) that paid special attention to the case where the Hessian of the Lagrangian (1.2) is nearly singular. Moré and Sorensen [15] developed an improved algorithm that produces approximate global minimizers in a finite number of steps.

The initial application of algorithms for the solution of (1.1) was to trust region methods for unconstrained minimization. See, for example, Gay [6] and Moré and Sorensen [15]. Recent application to other problems includes that by Coleman and Hempel [2] on constrained optimization, Ye [20] on quadratic programming, Pardalos, Ye, and Han [16] on quadratic knapsack problems, and Karmarkar, Resende, and Ramakrishnan [12] on covering problems.

Several extensions of the basic problem (1.1) are of interest. The simplest extension is to consider the problem

min{q(x) : c(x) ≤ 0},  (1.3)

Dedicated to Charles G. Broyden on the occasion of his 60th birthday. Work supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.

where q : IR^{n} → IR and c : IR^{n} → IR are quadratic functions defined on IR^{n}. Several special cases of this problem have been considered in the literature. For example, the problem where

min {∥Ax − b∥_{2} : ∥Cx − d∥_{2} ≤ α} ,  (1.4)

arises in the regularization of ill-posed problems and in the smoothing of noisy data. Note that this problem is a special case of (1.3) with both q and c convex. Gander [4] considered this problem as a special case of the problem with the equality constraint c(x) = 0, and characterized the solution in terms of the Lagrange multiplier. For recent work on this problem, see the work of Golub and von Matt [7].

Critchley [3] considered (1.3) with the equality constraint c(x) = 0, with q a strictly convex quadratic, but c a general quadratic. His interest in problem (1.3) derived from applications in the statistical literature. Our interest in (1.3) is motivated by a study of the general problem

min{q(x) : c_{i}(x) = 0, 1 ≤ i ≤ m},

where c_{i} : IR^{n} → IR are quadratic functions. This generalization is important because it includes, as a special case, integer programming problems. Indeed, if c_{i}(x) = x_{i}(1−x_{i}), then c_{i}(x) = 0 if and only if x_{i} ∈ {0, 1}. The case where m = 2 and the equality constraints are replaced by inequalities has attracted considerable interest in connection with trust region methods. For recent work on this problem, see Yuan [21, 22], Martínez and Santos [14], Zhang [23], and Heinkenschloß [9].

Our aim in this paper is to characterize the global minimizer of problem (1.3) and to develop an algorithm that determines approximate global minimizers in a finite number of steps. In our terminology, an approximate global minimizer is a vector x ∈ IR^{n} such that

q(x) ≤ q^{∗} + ϵ_{q}, |c(x)| ≤ ϵ_{c},

where ϵ_{q} > 0 and ϵ_{c} > 0 are tolerances, and q^{∗} ≡ min{q(x) : c(x) ≤ 0}.

We approach the inequality constrained problem (1.3) by first studying the equality constrained problem

min{q(x) : c(x) = 0},  (1.5)

and then showing that (1.3) can be treated as a special case. We begin with a brief look at a condition that guarantees the existence of a global minimizer for (1.5) and the connection of this condition with matrix pencils. The characterization result for a global minimizer of problems (1.3) and (1.5) appears in Section 3, while a uniqueness result for the minimizer x^{∗} appears in Section 4.

In Section 3 we also show that if the inequality constrained problem (1.3) is well-posed, then there is a global minimizer x^{∗} such that c(x^{∗}) = 0, or there is a unique minimizer x^{∗} with ∇^{2}q positive definite, ∇q(x^{∗}) = 0, and c(x^{∗}) < 0. This result shows that if we develop an algorithm for the equality constrained problem (1.5), then we can easily extend the algorithm to the inequality constrained problem (1.3).

The essential features of an algorithm for the solution of both (1.3) and (1.5) are developed in Section 3, while Section 5 contains a discussion of the termination criteria that guarantee an approximate global minimizer in a finite number of steps. These results extend and unify the theory associated with problems (1.1) and (1.4) to the general problem (1.3) and (1.5).

2 Preliminaries

We can guarantee that the minimization problem

min{q(x) : c(x) = 0},  (2.1)

where q : IR^{n} → IR and c : IR^{n} → IR are quadratic functions defined on IR^{n}, has a global minimizer by assuming that the Hessian of q is positive definite for any direction of zero curvature of c. In this section we explore the connection of this condition with work on matrix pencils.

The definition of a quadratic guarantees that the Hessian matrix is constant. We use the notation

∇^{2}q = A, ∇^{2}c = C,

for the Hessian matrices of q and c. The following result shows that the relationship between A and C is crucial to the existence of a global minimizer for problem (2.1).

Theorem 2.1 Let q : IR^{n} → IR and c : IR^{n} → IR be quadratics, and assume that

{x ∈ IR^{n} : c(x) = 0}

is not empty. If

w ≠ 0, w^{T} Cw = 0 ⟹ w^{T} Aw > 0,  (2.2)

then the optimization problem (2.1) has a global minimizer.

Proof. A standard compactness argument shows that (2.1) has a global minimizer if we prove that

lim_{k→∞} q(x_{k}) = +∞

for any unbounded {x_{k}} with c(x_{k}) = 0. Assume, on the contrary, that q(x_{k}) ≤ β. There is no loss of generality in assuming that

lim_{k→∞} \frac{x_{k}}{∥x_{k}∥} = w.

Clearly w ≠ 0. Since {x_{k}} is an unbounded sequence with c(x_{k}) = 0,

lim_{k→∞} \frac{c(x_{k})}{∥x_{k}∥^{2}} = w^{T} Cw = 0.

Similarly, since {x_{k}} is an unbounded sequence with q(x_{k}) ≤ β,

lim_{k→∞} \frac{q(x_{k})}{∥x_{k}∥^{2}} = w^{T} Aw ≤ 0.

Thus, w contradicts assumption (2.2) on A and C.

The converse of Theorem 2.1 does not hold in general; however, in Section 3 we show that if the optimization problem (2.1) has a global minimizer, then w^{T} Cw = 0 implies that w^{T} Aw ≥ 0. In the remainder of this section we consider the connection of condition (2.2) with the study of matrix pencils, that is, one-parameter families of matrices of the form A + λC.

Theorem 2.2 If A ∈ IR^{n×n} and C ∈ IR^{n×n} are symmetric matrices, then A+λC is positive definite for some λ ∈ IR if and only if (2.2) holds.

Theorem 2.2 is a classical result on quadratic forms. Hestenes [10, Theorem 6.1] gives an elementary, but somewhat lengthy proof of Theorem 2.2. We will give another proof of this result in Section 3. Uhlig [19] is an excellent source for additional information on results related to Theorem 2.2.

Theorem 2.2 arises in several areas. For example, in the analysis of augmented Lagrangian algorithms, A is the Hessian of the Lagrangian and C is a positive semidefinite matrix associated with the active constraint normals. The proof of Theorem 2.2 when C is semidefinite is short and elementary; see, for example, Bertsekas [1, Lemma 1.25]. Theorem 2.2 also arises in connection with the generalized eigenvalue problem Ax = λCx, because if we can find λ_{0} ∈ IR such that A + λ_{0}C is positive definite, then the eigenvalue problem Ax = λCx is equivalent to the positive definite eigenvalue problem

(λ_{0}A − C)x = ν(A + λ_{0}C)x.

This implies, in particular, that Ax = λCx has n real eigenvalues; some of the eigenvalues may be at infinity if C is singular. Golub and Van Loan [8, Section 8.7] provide additional information on generalized eigenvalue problems.

Theorem 2.3 Assume that A ∈ IR^{n×n} and C ∈ IR^{n×n} are symmetric matrices and that C is indefinite. Then

w^{T} Cw = 0 ⟹ w^{T} Aw ≥ 0

if and only if A + λC is positive semidefinite for some λ ∈ IR .

Proof. If we define A_{α} = A + αI for α ≥ 0, then (2.2) holds for A_{α}, and thus Theorem 2.2 guarantees that A_{α} + λ_{α}C is positive definite for some λ_{α} ∈ IR. In particular,

λ_{α}w^{T} Cw ≥ −w^{T} (A + αI)w

for all w ∈ IR^{n}. This inequality shows that if λ_{α} → +∞ as α → 0 then C is positive semidefinite. Similarly, we can rule out that λ_{α} → −∞ as α → 0. Since {λ_{α}} is bounded, a subsequence converges to some λ ∈ IR, and since A_{α} + λ_{α}C is positive definite, A + λC is positive semidefinite.

This result was established by Krein and Smuljan [13] for Hilbert spaces over the complex field by an entirely different argument. Note that our proof is valid for real vector spaces.

The assumption that C is indefinite is necessary in Theorem 2.3. For example, let

A = ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ) , C = ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) .

We can check that w^{T} Cw = 0 implies that w^{T} Aw = 0. However, A+λC is indefinite for all λ ∈ IR. Also note that Theorem 2.3 does not guarantee that A + λC is positive semidefinite for more than one value of λ. For example, if

A = ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ) , C = ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ) ,

then A is positive semidefinite, and thus the assumptions of Theorem 2.3 hold. However, A + λC is positive semidefinite only if λ = 0.

3 Global Minimizers

The main purpose of this section is to establish a characterization result for the global minimizer of the problem

min{q(x) : c(x) = 0},  (3.1)

where q : IR^{n} → IR and c : IR^{n} → IR are quadratic functions defined on IR^{n}. We conclude with the characterization result for the inequality constrained version of problem (3.1).

We follow the notational convention of the preceding section by using

∇^{2}q = A, ∇^{2}c = C,

for the Hessian matrices of q and c. We do not assume that either A or C is semidefinite. Interestingly enough, we need to assume that the constraint quadratic c is not a linear function; that is, we assume that C ≠ 0.

The analysis requires that we rule out certain special cases by assuming a constraint qualification. For (3.1) we assume that

min{c(x) : x ∈ IR^{n}} < 0 < max{c(x) : x ∈ IR^{n}}.  (3.2)

These assumptions guarantee, in particular, that the feasible set is not empty.

Lemma 3.1 Let c : IR^{n} → IR be a quadratic function defined on IR^{n}. If the feasible set {x ∈ IR^{n} : c(x) = 0} is not empty, then assumption (3.2) fails if and only if C is semidefinite and there is an x^{∗} such that c(x^{∗}) = 0 and ∇c(x^{∗}) = 0. Moreover, if ∇c(x) ≠ 0 for some feasible x ∈ IR^{n} then assumption (3.2) holds.

Proof. Assume that (3.2) fails because c(x) ≥ 0 for all x ∈ IR^{n}. Since the feasible set is not empty, we must have

min{c(x) : x ∈ IR^{n}} = 0.

Thus, the quadratic c is bounded below and achieves its minimum at some x^{∗}. Hence, C is positive semidefinite, c(x^{∗}) = 0, and ∇c(x^{∗}) = 0. A similar argument establishes the result if (3.2) fails because c(x) ≤ 0 for all x ∈ IR^{n}.

If ∇c(x) ≠ 0 for some feasible x ∈ IR^{n} but (3.2) fails because c(x) ≥ 0 for all x ∈ IR^{n} then the above argument shows that the quadratic c achieves its minimum at an x^{∗} such that c(x^{∗}) = 0. Hence, c achieves its minimum at any feasible x, and thus ∇c(x) = 0 for any feasible x.

This result implies that if assumption (3.2) fails, then the feasible set {x ∈ IR^{n} : c(x) = 0} is a subspace of IR^{n} with dimension less than n; if C is definite then only x^{∗} is feasible.

Theorem 3.2 Let q : IR^{n} → IR and c : IR^{n} → IR be quadratic functions defined on IR^{n}. Assume that (3.2) holds and that ∇^{2}c ≠ 0. A vector x^{∗} is a global minimizer of problem (3.1) if and only if c(x^{∗}) = 0 and there is a multiplier λ^{∗} ∈ IR such that the Kuhn-Tucker condition

∇q(x^{∗}) + λ^{∗}∇c(x^{∗}) = 0  (3.3)

is satisfied with

∇^{2}q(x^{∗}) + λ^{∗}∇^{2}c(x^{∗})  (3.4)

positive semidefinite.

Proof. We first show that if x^{∗} is a global minimizer, then condition (3.3) holds and (3.4) is positive semidefinite. The proof requires consideration of two cases.

If ∇c(x^{∗}) ≠ 0, then the Kuhn-Tucker condition (3.3) holds, so we need to establish that (3.4) is positive semidefinite. In terms of the Lagrangian function

L(x, λ) = q(x) + λc(x),

the Kuhn-Tucker condition guarantees that ∇_{x}L(x^{∗}, λ^{∗}) = 0, and thus

L(x, λ^{∗}) = L(x^{∗}, λ^{∗}) + \frac{1}{2}(x − x^{∗})^{T} ∇_{x}^{2}L(x^{∗}, λ^{∗})(x − x^{∗}).

Since L(x, λ^{∗}) = q(x) if c(x) = 0, we obtain that

c(x^{∗} + w) = 0 ⟹ w^{T} ∇_{x}^{2}L(x^{∗}, λ^{∗})w ≥ 0.

We use this implication to show that ∇_{x}^{2}L(x^{∗}, λ^{∗}) is positive semidefinite. The proof requires that we partition IR^{n} into four different sets and show that

w^{T} ∇_{x}^{2}L(x^{∗}, λ^{∗})w ≥ 0  (3.5)

holds for vectors in each of these sets. Consider the set

S_{1} = {w ∈ IR^{n} : ∇c(x^{∗})^{T} w ≠ 0, w^{T} Cw ≠ 0} .

If w ∈ S_{1}, then c(x^{∗} + αw) = 0 for some α ≠ 0, and thus (3.5) holds. Similarly, if

S_{2} = {w ∈ IR^{n} : ∇c(x^{∗})^{T} w = 0, w^{T} Cw = 0} ,

then c(x^{∗} + w) = 0 for w ∈ S_{2}, and thus (3.5) holds. Now consider the set

S_{3} = {w ∈ IR^{n} : ∇c(x^{∗})^{T} w = 0, w^{T} Cw ≠ 0} .

If w ∈ S_{3}, define w_{α} = w+αv, where ∇c(x^{∗})^{T} v ≠ 0. The existence of the vector v is guaranteed by the assumption that ∇c(x^{∗}) ≠ 0. A short computation shows that ∇c(x^{∗})^{T} w_{α} ≠ 0 and that w_{α}^{T} Cw_{α} ≠ 0 for all α ≠ 0 sufficiently small. Hence w_{α} ∈ S_{1}, and thus

w_{α}^{T} ∇_{x}^{2}L(x^{∗}, λ^{∗})w_{α} ≥ 0.  (3.6)

Since {w_{α}} converges to w as α converges to zero, (3.5) holds for w ∈ S_{3}. A similar argument show that (3.5) holds if w belongs to the set

S_{4} = {w ∈ IR^{n} : ∇c(x^{∗})^{T} w ≠ 0, w^{T} Cw = 0} .

If w ∈ S_{4}, we now define w_{α} = w + αv, where v^{T} Cv ≠ 0. In this case the existence of the vector v is guaranteed by the assumption that ∇^{2}c ≠ 0, since we can choose v to be an eigenvector of C corresponding to a nonzero eigenvalue. A computation shows that w_{α} ∈ S_{1} for all α ≠ 0 sufficiently small, and thus (3.6) holds. Since {w_{α}} converges to w as α converges to zero, (3.5) holds for w ∈ S_{4}.

We have shown that (3.5) holds for all w ∈ IR^{n}, and thus (3.3) holds if ∇c(x^{∗}) ≠ 0. Note that assumptions (3.2) have not been needed so far in the proof.

The proof for the case where ∇c(x^{∗}) = 0 requires that we first show that ∇q(x^{∗}) = 0. We first claim that q(x^{∗} + αw) ≥ q(x^{∗}) for all α and w ∈ IR^{n} such that w^{T} Cw = 0. This claim is easy to establish because c(x^{∗}) = 0 and ∇c(x^{∗}) = 0 implies that

c(x^{∗} + αw) = \frac{1}{2}α^{2}w^{T} Cw = 0.

Hence, x^{∗} + αw is feasible, and thus q(x^{∗} + αw) ≥ q(x^{∗}) because x^{∗} is a global minimizer.

Since q(x^{∗} + αw) ≥ q(x^{∗}) for all α and w ∈ IR^{n}, we must have ∇q(x^{∗})^{T} w = 0 whenever w^{T} Cw = 0. We now show that ∇q(x^{∗})^{T} v = 0 for all eigenvectors v of C. Note that since x^{∗} satisfies c(x^{∗}) = 0 and ∇c(x^{∗}) = 0, assumptions (3.2) imply that C is indefinite.

If v is an eigenvector of C corresponding to a zero eigenvalue, then v^{T} Cv = 0, and thus ∇q(x^{∗})^{T} v = 0. Let v_{1} and v_{2} be eigenvectors of C corresponding to positive and negative eigenvalues, respectively. We choose the directions of v_{1} and v_{2} so that ∇q(x^{∗})^{T} v_{i} ≥ 0 for i = 1, 2, and we choose an α < 0 so that

(v_{1} − αv_{2})^{T} C(v_{1} − αv_{2}) = 0.

Hence, ∇q(x^{∗})^{T} (v_{1} − αv_{2}) = 0, and since ∇q(x^{∗})^{T} v_{i} ≥ 0 and α < 0, we must have ∇q(x^{∗})^{T} v_{i} = 0 for i = 1, 2. We have shown that ∇q(x^{∗})^{T} v = 0 for all eigenvectors v of C. Since C has a complete set of eigenvectors, ∇q(x^{∗}) = 0.

We now show that w^{T} Cw = 0 implies that w^{T} Aw ≥ 0. If w^{T} Cw = 0, then

c(x^{∗} + w) = c(x^{∗}) + ∇c(x^{∗})^{T} w + \frac{1}{2}w^{T} Cw = 0,

since c(x^{∗}) = 0 and ∇c(x^{∗}) = 0. Hence, x^{∗} + w is feasible, and since ∇q(x^{∗}) = 0 and x^{∗} is the global minimizer,

q(x^{∗} + w) − q(x^{∗}) = \frac{1}{2}w^{T} Aw ≥ 0.

Thus, we have shown that w^{T} Cw = 0 implies that w^{T} Aw ≥ 0. Theorem 2.3 now shows that A+λ^{∗}C is positive semidefinite for some λ^{∗} ∈ IR, that is, ∇_{x}^{2}L(x^{∗}, λ^{∗}) is positive semidefinite. Moreover, the pair (x^{∗}, λ^{∗}) trivially satisfies the Kuhn-Tucker condition because ∇q(x^{∗}) = 0 and ∇c(x^{∗}) = 0.

The converse is easy to prove. If c(x^{∗}) = 0 and there is a multiplier λ^{∗} ∈ IR such that (3.3) holds and (3.4) is positive semidefinite, then the Kuhn-Tucker condition guarantees that ∇_{x}L(x^{∗}, λ^{∗}) = 0, and thus

L(x, λ^{∗}) = L(x^{∗}, λ^{∗}) + \frac{1}{2}(x − x^{∗})^{T} ∇_{x}^{2}L(x^{∗}, λ^{∗})(x − x^{∗}) ≥ L(x^{∗}, λ^{∗}).

Since L(x, λ^{∗}) = q(x) if c(x) = 0, we obtain that q(x^{∗}) ≤ q(x) if c(x) = 0. Thus, x^{∗} is a global minimizer.

The assumption that ∇^{2}c ≠ 0 in Theorem 3.2 is necessary. For example, the problem

min{ξ_{1}^{2} − ξ_{2}^{2} : ξ_{2} = 0}

has x^{∗} = (0, 0) for a global minimizer and λ^{∗} = 0 as the unique multiplier. However,

∇_{x}^{2}L(x^{∗}, λ^{∗}) = ( \begin{matrix}2 & 0 \\ 0 & −2 \end{matrix} )

is not positive semidefinite. Also note that assumption (3.2) is necessary. For example, the problem

min{ξ_{1}^{2} + ξ_{2} : ξ_{2}^{2} = 0}

has x^{∗} = (0, 0) for a global minimizer, but the Kuhn-Tucker condition (3.3) does not hold for any λ^{∗} ∈ IR.

An interesting aspect of the proof of Theorem 3.2 is that it can be used to give a short proof of Theorem 2.2. We need the part of the proof where it is assumed that ∇c(x^{∗}) ≠ 0. For this proof, first note that if (2.2) holds, then there is an ϵ > 0 such that

w ≠ 0, w^{T} Cw = 0 ⟹ w^{T} Aw ≥ ϵ∥w∥^{2}.

If we consider the optimization problem

min\{x^{T} (A − \frac{1}{2}ϵI)x : x^{T} Cx = x_{0}^{T} Cx_{0}\},

for some x_{0} ∈ IR^{n} such that x_{0}^{T} Cx_{0} ≠ 0, then Theorem 2.1 shows that this problem has a global minimizer x^{∗}. Moreover, if c(x) = x^{T} Cx−x_{0}^{T} Cx_{0}, it is clear that ∇c(x^{∗}) = 2Cx^{∗} ≠ 0. Hence, the proof of Theorem 3.2 shows that there is a multiplier λ^{∗} such that

A − \frac{1}{2}ϵI + λ^{∗}C

is positive semidefinite. Hence, A + λ^{∗}C is positive definite as desired.

We have obtained Theorem 3.2 under minimal assumptions. Algorithmic developments, however, require the stability assumption that the set I_{PD} defined by

I_{PD} = {λ ∈ IR : A + λC positive definite }  (3.7)

is not empty. We justify this assumption by proving that if I_{PD} is empty, then a small perturbation of problem (3.1) leads to a similar problem without a global minimizer. Theorem 2.2 shows that if I_{PD} is empty, then there is a w ∈ IR^{n} such that

w ≠ 0, w^{T} Cw = 0, w^{T} Aw ≤ 0.

Now consider the minimization problem

min{q_{ϵ}(x) : c(x) = 0},

where

q_{ϵ}(x) = q(x) − \frac{1}{2}ϵ(v^{T} x)^{2}

for any vector v ∈ IR^{n} such that v^{T} w ≠ 0, and any ϵ > 0. The Hessian of the Lagrangian of this problem is not positive semidefinite, and thus Theorem 3.2 implies that this problem does not have a global minimizer. Since ∇^{2}q_{ϵ} is arbitrarily close to ∇^{2}q, this proves our claim that if I_{PD} is empty, then a small perturbation of problem (3.1) leads to a similar problem without a global minimizer.

The analogous stability assumption for the inequality constrained version of problem (3.1) is that

w ≠ 0, w^{T} Cw ≤ 0 ⟹ w^{T} Aw > 0.  (3.8)

We do not elaborate on this assumption; we need (3.8) only to show that the inequality constrained version is essentially a special case of (3.1).

Theorem 3.3 Let q : IR^{n} → IR and c : IR^{n} → IR be quadratic functions defined on IR^{n}, and assume that (3.8) holds. If the problem

min{q(x) : c(x) ≤ 0}  (3.9)

is feasible, then there is a global minimizer x^{∗} such that c(x^{∗}) = 0, or there is a unique minimizer x^{∗} with A positive definite, ∇q(x^{∗}) = 0, and c(x^{∗}) < 0.

Proof. A minor modification of the proof of Theorem 2.1 shows that if (3.8) holds, then the optimization problem (3.9) has a global minimizer. If no global minimizer x^{∗} satisfies c(x^{∗}) = 0, then there must be a global minimizer x^{∗} with c(x^{∗}) < 0. Hence, ∇q(x^{∗}) = 0 and A must be positive semidefinite. If, on the contrary, A is not positive definite, then there is a v ≠ 0 with Av = 0. Thus, q(x^{∗} + αv) = q(x^{∗}) for all α ∈ IR. We complete the proof by showing that c(x^{∗} + αv) = 0 for some α ∈ IR. Since v^{T} Av = 0 and (3.8) holds, we must have v^{T} Cv > 0. Thus, c(x^{∗} + αv) → +∞ as α → ∞. The continuity of c and the assumption that c(x^{∗}) < 0 now show that there is some α ∈ IR with c(x^{∗} + αv) = 0, as desired.

Theorem 3.3 shows that if we develop an algorithm for the equality constrained problem (3.1), then we can easily extend the algorithm to the inequality constrained problem (3.9). We conclude this section with the characterization result for (3.9).

Theorem 3.4 Let q : IR^{n} → IR and c : IR^{n} → IR be quadratic functions defined on IR^{n}, and assume that

min{c(x) : x ∈ IR^{n}} < 0  (3.10)

and that ∇^{2}c ≠ 0. A vector x^{∗} is a global minimizer of (3.9) if and only if c(x^{∗}) ≤ 0, the Kuhn-Tucker condition (3.3) is satisfied, and the Hessian of the Lagrangian (3.4) is positive semidefinite for some λ^{∗} ≥ 0 with λ^{∗} = 0 if c(x^{∗}) < 0.

Proof. First of all, note that (3.2) can fail only if c(x) ≤ 0 for all x ∈ IR^{n}. However, in this case the optimization problem is unconstrained, and the result holds.

If x^{∗} is a global minimizer and c(x^{∗}) < 0, then x^{∗} is an unconstrained minimizer, and thus ∇^{2}q(x^{∗}) is positive semidefinite as desired. If c(x^{∗}) = 0, the result follows from Theorem 3.2.

The converse follows as in Theorem 3.2. If (3.3) holds and (3.4) is positive semidefinite for some λ^{∗} ≥ 0, then ∇_{x}L(x^{∗}, λ^{∗}) = 0 and

L(x, λ^{∗}) = L(x^{∗}, λ^{∗}) + \frac{1}{2}(x − x^{∗})^{T} ∇_{x}^{2}L(x^{∗}, λ^{∗})(x − x^{∗}) ≥ L(x^{∗}, λ^{∗}).

Since λ^{∗} ≥ 0, this implies that

q(x) ≥ q(x) + λ^{∗}c(x) = L(x, λ^{∗}) ≥ L(x^{∗}, λ^{∗}) = q(x^{∗})

for all x such that c(x) ≤ 0. Thus, x^{∗} is a global minimizer of problem (3.9).

4 Uniqueness

We only consider conditions that guarantee the uniqueness of x^{∗} since the uniqueness of λ^{∗} is not needed for the developments that follow.

Theorem 4.1 Let q : IR^{n} → IR and c : IR^{n} → IR be quadratic functions defined on IR^{n}, and assume that the Kuhn-Tucker condition (3.3) is satisfied and that the Hessian of the Lagrangian (3.4) is positive definite. If c(x^{∗}) = 0, then x^{∗} is the unique global minimizer of problem (3.1). If λ^{∗} ≥ 0 and c(x^{∗}) ≤ 0, then x^{∗} is the unique global minimizer of problem (3.9).

Proof. We only prove this result for problem (3.9) since the proof for problem (3.1) is similar. If (3.3) holds, then ∇_{x}L(x^{∗}, λ^{∗}) = 0. Thus, since (3.4) is positive definite,

L(x, λ^{∗}) = L(x^{∗}, λ^{∗}) + \frac{1}{2}(x − x^{∗})^{T} ∇_{x}^{2}L(x^{∗}, λ^{∗})(x − x^{∗}) > L(x^{∗}, λ^{∗})

for all x ≠ x^{∗}. Now use the assumptions that λ^{∗} ≥ 0 and that c(x^{∗}) ≤ 0 to obtain that

q(x) ≥ q(x) + λ^{∗}c(x) = L(x, λ^{∗}) > L(x^{∗}, λ^{∗}) = q(x^{∗})

for all x ≠ x^{∗} such that c(x) ≤ 0. Thus, x^{∗} is the unique global minimizer of problem (3.9).

5 Algorithms

We propose an algorithm for the solution of the optimization problem (3.1) that requires the solution of a sequence of positive definite systems of linear equations. The algorithm is based on a search for the Lagrange multiplier λ^{∗} guaranteed by Theorem 3.2.

Consider the optimization problem (3.1) where q : IR^{n} → IR and c : IR^{n} → IR are quadratic functions defined on IR^{n}. For algorithmic purposes, we assume that the quadratics q and c are defined by

q(x) = \frac{1}{2}x^{T} Ax + b^{T} x,  c(x) = \frac{1}{2}x^{T} Cx + d^{T} x − δ.  (5.1)

We also assume that the set I_{PD} defined by (3.7) is not empty. This is a reasonable assumption because the argument in Section 3 showed that if I_{PD} was empty, then the optimization problem (3.1) was not well-posed.

Given λ ∈ I_{PD}, we define x(λ) ∈ IR^{n} as the solution to the system of linear equations

∇q[x(λ)] + λ∇c[x(λ)] = 0.  (5.2)

In terms of the Lagrangian function, x(λ) is the unique solution of ∇_{x}L[x(λ), λ] = 0; in view of (5.1) we can also think of x(λ) as the solution of the system of linear equations

(A + λC)x(λ) = −(b + λd).

The algorithm that we propose in this section is based on finding λ ∈ I_{PD} such that

c[x(λ)] = 0.

Theorem 3.2 shows that if this is possible, then x(λ) is the global minimizer of the optimization problem (3.1).

Theorem 5.1 If A ∈ IR^{n×n} and C ∈ IR^{n×n} are symmetric matrices, then I_{PD} is an interval.

Proof. We show that I_{PD} is convex and thus an interval. Assume that λ_{1} and λ_{2} belong to I_{PD} and that λ_{1} < λ_{2}. Since w^{T} (A + θC)w is linear in θ for any w ∈ IR^{n},

w^{T} (A + θC)w ≥ min{w^{T} (A + λ_{i})w : i = 1, 2}, θ ∈ (λ_{1}, λ_{2}),

and thus A + θC is positive definite. Hence, θ ∈ I_{PD} as desired.

Theorem 2.2 gives necessary and sufficient conditions for I_{PD} to be nonempty. Under these conditions Theorem 5.1 shows that I_{PD} is a nonempty open interval. I_{PD} is a finite interval (λ_{l}, λ_{u}) if C is indefinite. We can see this by noting that

λw^{T} Cw ≥ −w^{T} Aw, w ∈ IR^{n}

for λ ∈ I_{PD}. In a similar manner we can prove that I_{PD} is of the form (λ_{l}, +∞) if C is positive definite, while I_{PD} = (−∞, λ_{u}) if C is negative definite.

For several of our results it will be important to note that each component of x(·) is a rational function for λ ∈ I_{PD}. This result can be established by first recalling the classical result that since I_{PD} is not empty, there is a nonsingular similarity transformation that diagonalizes A and C. For a proof of this result, see Horn and Johnson [11, Theorem 7.6.1]. Thus, there is a nonsingular P ∈ IR^{n×n} such that

P^{T} AP = D_{a}, P^{T} CP = D_{c},

where both D_{a} and D_{c} are diagonal matrices. If we use P to change variables, then

x(λ) = P^{−T} (D_{a} + λD_{c})^{−1} P^{T} (b + λd).

It is now clear that each component of x(·) is a rational function for λ ∈ I_{PD}.

Theorem 5.2 Let q : IR^{n} → IR and c : IR^{n} → IR be the quadratic functions defined on IR^{n} by (5.1), and assume that I_{PD} is not empty. If x(λ) ∈ IR^{n} is the solution of (5.2), and if the function ϕ : IR → IR is defined on I_{PD} by

ϕ(λ) = c[x(λ)],

then ϕ is strictly decreasing on I_{PD} unless x(·) is constant on I_{PD} with

∇q[x(λ)] = 0, ∇c[x(λ)] = 0,

for all λ in I_{PD}.

Proof. We first need expressions for ϕ′(λ) and x′(λ). The expression

ϕ′(λ) = ∇c[x(λ)]^{T} x′(λ)

for ϕ′(λ) follows from the definition of ϕ, while an expression for x′(λ) is obtained by noting that since x(λ) satisfies (5.2),

(A + λC)x′(λ) = −∇c[x(λ)].  (5.3)

Thus, using the expression for ϕ′(λ), we obtain that

ϕ′(λ) = −x′(λ)^{T} (A + λC)x′(λ).

Hence, ϕ′(λ) ≤ 0 for λ ∈ I_{PD}. If ϕ is not strictly decreasing on I_{PD}, then ϕ′(λ) = 0 for λ in some subinterval I if I_{PD}. The above expression for ϕ′(λ) then shows that x′(λ) = 0 on I.

We now wish to conclude that x′(λ) ≡ 0 on I_{PD}. The easiest way to prove this is to note that since each component of x(·) is a rational function for λ ∈ I_{PD}, we can have x′(λ) = 0 on a subinterval I of I_{PD} only if x′(λ) ≡ 0 on I_{PD}.

We have shown that x(·) is constant on I_{PD}. Hence, (5.3) shows that ∇c[x(λ)] = 0 on I_{PD}, and thus (5.2) yields that ∇q[x(λ)] = 0 on I_{PD}.

The possibility in Theorem 5.2 that x(·) is constant on I_{PD} cannot be ruled out. For example, if A and C are two matrices such that I_{PD} is not empty, and we define b and d by

Ax_{0} = −b, Cx_{0} = −d

for some x_{0} ∈ IR^{n}, then x(λ) ≡ x_{0} for λ ∈ I_{PD}. We can reverse this construction because if x(λ) ≡ x_{0} for λ ∈ I_{PD}, then x_{0} satisfies Ax_{0} = −b and Cx_{0} = −d. This argument shows that small perturbations on the data that defines q and c lead to a case where x(·) is not constant.

Theorem 5.2 can be used to find a global minimizer x^{∗} of (3.1) in the case where A+λ^{∗}C is positive definite because in this case λ^{∗} ∈ I_{PD} is a solution of ϕ(λ) = 0. We now outline an algorithm for finding λ^{∗} in this case.

In the search for λ^{∗} we first need to decide whether I_{PD} is empty or determine λ_{0} ∈ I_{PD}. We start with bounds λ_{l} and λ_{u} such that I_{PD} ⊂ (λ_{l}, λ_{u}). For example, the bounds

λ_{l} = max \{−\frac{a_{i,i}}{c_{i,i}} : c_{i,i} > 0\} , λ_{u} = min \{−\frac{a_{i,i}}{c_{i,i}} : c_{i,i} < 0\} ,

could be used, where λ_{l} = −∞ if c_{i,i} ≤ 0 for all i, and λ_{u} = ∞ if c_{i,i} ≥ 0 for all i. We now show how to update (λ_{l}, λ_{u}) given λ_{0} ∈ (λ_{l}, λ_{u}).

If λ_{0} ∉ I_{PD}, then A + λ_{0}C is not positive definite, and thus we can compute an x ∈ IR^{n} such that

x^{T} (A + λ_{0}C)x ≤ 0,  x ≠ 0.  (5.4)

A vector x that satisfies (5.4) can be computed, as in the algorithms of Gay [5] and Moré and Sorensen [15], by noting that during the Cholesky decomposition of A + λ_{0}C it is possible to find δ ≥ 0 such that the leading submatrix of order l ≤ n of

A + λ_{0}C + δe_{l}e_{l}^{T}

is singular, and x ∈ IR^{n} such that (A + λ_{0}C + δe_{l}e_{l}^{T})x = 0 with x_{l} = 1 and x_{i} = 0 for i > l. Clearly, x satisfies (5.4).

Given a vector x ∈ IR^{n} that satisfies (5.4), note that if x^{T} Cx < 0, then

x^{T} (A + λC)x ≤ x^{T} (A + λ_{0}C)x ≤ 0

for λ > λ_{0}. Thus we can set λ_{u} = λ_{0}. Similarly, if x^{T} Cx > 0, then λ_{l} = λ_{0}. Given a tolerance ϵ > 0, we can use this updating procedure to reduce the length of (λ_{l}, λ_{u}) until we determine some λ_{0} ∈ I_{PD}, or we determine that the length of I_{PD} is less than ϵ.

Once we determine λ_{0} ∈ I_{PD}, we can continue to isolate λ^{∗} by updating λ_{l} and λ_{u} such that λ^{∗} ∈ (λ_{l}, λ_{u}). This is easily done because if λ_{0} ∈ I_{PD} and ϕ(λ_{0}) < 0, then we set λ_{u} = λ_{0}, but if ϕ(λ_{0}) > 0, then λ_{l} = λ_{0}. This procedure is valid even if x(·) is constant for λ ∈ I_{PD}.

The algorithm that we have outlined can be used to generate a sequence {λ_{k}} that converges to λ^{∗}. Moreover, if A + λ^{∗}C is positive definite, then {x(λ_{k})} converges to x(λ^{∗}) with ϕ(λ^{∗}) = 0. Hence, x(λ^{∗}) is the global solution of (3.1).

We have not specified any particular algorithm to generate the sequence {λ_{k}}. If C is positive (negative) semidefinite, it is not difficult to show that ϕ is convex (concave) on I_{PD}, and thus a safeguarded version of Newton’s method is a reasonable choice. This is the approach used by Gay [5] and Moré and Sorensen [15]. If C is indefinite, then ϕ may not be convex or concave, so extra care is needed. For example, if

A = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) ,  C = ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ) ,  b = ( \begin{matrix}1 \\ 1 \end{matrix} ) ,  d = 0,

then I_{PD} = (−1, 1), but ϕ′′ changes sign in (−1, 1).

The situation where A + λ^{∗}C is singular is more delicate. In this case ϕ(λ) = 0 may not have a solution in I_{PD}, and {x(λ_{k})} may not converge to the solution of (3.1); this is the reason why Moré and Sorensen [15], in their study of the problem with C = I, called this case the hard case.

Theorem 5.3 Let A and C be symmetric matrices, and assume that I_{PD} is not empty. If an endpoint λ^{∗} of I_{PD} is finite, then A+λ^{∗}C is positive semidefinite and singular. Moreover, if I_{PD} = (λ_{l}^{∗}, λ_{u}^{∗}), then

[λ_{l}^{∗}, λ_{u}^{∗}] = I_{PSD} ≡ {λ ∈ IR : A + λC positive semidefinite } .

Proof. If λ^{∗} is an endpoint of I, then it is clear that A + λ^{∗}C is positive semidefinite. If A + λ^{∗}C is not singular, then it must be positive definite. However, then A + λC is also positive definite in a neighborhood of λ^{∗}. This conclusion is not possible because it contradicts the definition of I_{PD}.

We now show that if I_{PD} = (λ_{l}^{∗}, λ_{u}^{∗}), then I_{PSD} = [λ_{l}^{∗}, λ_{u}^{∗}]. Clearly, I_{PD} ⊂ I_{PSD}. Moreover, just as in Theorem 5.1, we can prove that I_{PSD} is an interval. Thus, if I_{PSD} ≠ [λ_{l}^{∗}, λ_{u}^{∗}], then A + λC must be positive semidefinite and singular on a nontrivial interval. This conclusion implies that the polynomial

p(λ) = det(A + λC)

vanishes in a nontrivial interval. Hence, p(λ) ≡ 0, and thus A + λC is singular for all λ, contradicting the assumption that I_{PD} is not empty.

Theorem 5.3 shows that if A + λ^{∗}C is singular, then λ^{∗} must be an endpoint of I_{PD}. We now prove that λ^{∗} is an endpoint of I_{PD} such that the limit

lim_{λ→λ^{∗}} ϕ(λ)

exists. We are certainly guaranteed the existence of this limit for one of the endpoints of I_{PD}. In fact, since we are assuming that ϕ(λ) = 0 does not have a solution in I_{PD}, the function ϕ does not change sign in I_{PD}. Hence, if ϕ(λ) > 0 on I_{PD}, then

lim_{λ→λ_{u}^{∗}} ϕ(λ) = inf{ϕ(λ) : λ_{l}^{∗} < λ < λ_{u}^{∗}},

because ϕ is decreasing in I_{PD}. Similarly, if ϕ(λ) < 0 on I_{PD}, then

lim_{λ→λ_{l}^{∗}} ϕ(λ) = sup{ϕ(λ) : λ_{l}^{∗} < λ < λ_{u}^{∗}}.

These calculations suggest that λ^{∗} = λ_{u}^{∗} if ϕ(λ) > 0 on I_{PD}, and that λ^{∗} = λ_{l}^{∗} if ϕ(λ) < 0 on I_{PD}. We need the following result to establish this claim.

Theorem 5.4 Let A and C be symmetric matrices, and assume that I_{PD} is not empty. If an endpoint λ^{∗} of I_{PD} is finite and the limit

lim_{λ→λ^{∗}} ϕ(λ)  (5.5)

exists, then the limit

lim_{λ→λ^{∗}} x(λ)

also exists.

Proof. We have already noted that the function x(·) is a rational function for λ ∈ I_{PD} so we need to show that {x(λ_{k})} is bounded when {λ_{k}} is any sequence in I_{PD} converging to λ^{∗}; that is, we need to show that x(·) does not have a pole at λ^{∗}. Assume, on the contrary, that {∥x(λ_{k})∥} is unbounded, and define

z_{k} = \frac{x(λ_{k})}{∥x(λ_{k})∥}.

Then ∥z_{k}∥ = 1, so that we can assume, without loss of generality, that {z_{k}} converges to some vector z with ∥z∥ = 1.

Since {ϕ(λ_{k})} is bounded and ϕ(λ_{k}) = c[x(λ_{k})], we obtain that z^{T} Cz = 0. Moreover, since

(A + λ_{k}C)z_{k} = −\frac{(b + λ_{k}d)}{∥x(λ_{k})∥},

we also obtain that (A + λ^{∗}C)z = 0. We have already shown that z^{T} Cz = 0, so this yields that z^{T} Az = 0. However, this is not possible if I_{PD} is not empty.

We now prove that λ^{∗} = λ_{u}^{∗} if ϕ(λ) > 0 on I_{PD}, and that λ^{∗} = λ_{l}^{∗} if ϕ(λ) < 0 on I_{PD}. We have already shown that the limit (5.5) exists for this choice of λ^{∗}, and thus Theorem 5.4 shows that

lim_{λ→λ^{∗}} x(λ) = x^{∗}

for some x^{∗} ∈ IR^{n}, and hence

(A + λ^{∗}C)x^{∗} = −(b + λ^{∗}d).

Although we also have that A+λ^{∗}C is positive semidefinite, x^{∗} is not necessarily the solution of (3.1) because we cannot guarantee that c(x^{∗}) = 0. However, we claim that if z_{∗} is chosen so that

(A + λ^{∗}C)z_{∗} = 0, z_{∗} ≠ 0,

then x^{∗} + α^{∗}z_{∗} solves (3.1) for some α^{∗} ∈ IR.

First of all, note that we can obtain z_{∗} because A + λ^{∗}C is singular. Now assume, to be definite, that ϕ(λ) < 0 on I_{PD}, and thus λ^{∗} = λ_{l}^{∗} is the smallest endpoint of I_{PD}. Since

c(x^{∗} + αz_{∗}) = c(x^{∗}) + α∇c(x^{∗})^{T} z_{∗} + \frac{1}{2}α^{2}z_{∗}^{T} Cz_{∗},

it is clear that there is an α^{∗} ∈ IR such that c(x^{∗} + α^{∗}z_{∗}) = 0 if we can show that c(x^{∗}) ≤ 0 and that z_{∗}^{T} Cz_{∗} > 0. Since ϕ(λ) < 0 on I_{PD}, and {x(λ)} converges to x^{∗}, it is clear that c(x^{∗}) ≤ 0. If, on the contrary, z_{∗}^{T} Cz_{∗} ≤ 0, then

z_{∗}^{T} (A + λC)z_{∗} = z_{∗}^{T} (A + λ^{∗}C)z_{∗} + (λ − λ^{∗})z_{∗}^{T} Cz_{∗} ≤ 0

for λ > λ^{∗} = λ_{l}^{∗}. This is not possible because A + λC is positive definite for λ ∈ (λ_{l}^{∗}, λ_{u}^{∗}). Hence, z_{∗}^{T} Cz_{∗} > 0 as desired.

6 Approximate Global Minimizers

The results in Section 5 show how to generate a sequence {λ_{k}} in I_{PD} that converges to the Lagrange multiplier λ^{∗} of the optimization problem (3.1). Moreover, if A + λ^{∗}C is positive definite then {x(λ_{k})} converges to the solution x^{∗} of (3.1), while if A + λ^{∗}C is positive semidefinite and singular, then {x(λ_{k})} also converges to some x^{∗}, but now a solution of (3.1) is obtained by computing x^{∗} + α^{∗}z_{∗}, where

(A + λ^{∗}C)z_{∗} = 0, z_{∗} ≠ 0,

and α^{∗} ∈ IR satisfies c[x^{∗} + α^{∗}z_{∗}] = 0. In this section we address the question of how to determine approximate global minimizers x ∈ IR^{n} such that, given tolerances ϵ_{q} > 0 and ϵ_{c} > 0,

q(x) ≤ q^{∗} + ϵ_{q},  |c(x)| ≤ ϵ_{c},  (6.1)

where

q^{∗} ≡ min{q(x) : c(x) = 0}.

We first analyze the case where A + λ^{∗}C is positive definite.

Theorem 6.1 If λ ∈ I_{PD}, then

q[x(λ)] + λc[x(λ)] ≤ q^{∗}.

Proof. The proof is simple; just note that (5.2) implies that x(λ) is the global minimizer of the quadratic q + λc, and thus

q[x(λ)] + λc[x(λ)] = min{q(x) + λc(x) : x ∈ IR^{n}} ≤ min{q(x) : c(x) = 0} = q^{∗}.

If A + λ^{∗}C is positive definite, then we can compute λ ∈ I_{PD} such that ϕ(λ) = c[x(λ)] is small. Theorem 6.1 shows that x(λ) satisfies the termination criteria (6.1) if we determine λ ∈ I_{PD} such that

−λc[x(λ)] ≤ ϵ_{q}, |c[x(λ)]| ≤ ϵ_{c}.

These inequalities are satisfied for all λ ∈ I_{PD} sufficiently close to λ^{∗}.

Theorem 6.2 If λ ∈ I_{PD} and

c[x(λ) + α_{λ}z_{λ}] = 0,

then

q^{∗} ≤ q[x(λ) + α_{λ}z_{λ}] ≤ q^{∗} + \frac{1}{2}α_{λ}^{2}z_{λ}^{T} (A + λC)z_{λ}.

Proof. The first inequality follows from the assumption that c[x(λ)+α_{λ}z_{λ}] = 0 and from the definition of q^{∗}. The proof of the second inequality is obtained in terms of the Lagrangian function

L(x, λ) = q(x) + λc(x).

Since the pair (x(λ), λ) satisfies (5.2), ∇_{x}L[x(λ), λ] = 0, and thus

L[x(λ) + α_{λ}z_{λ}, λ] = L[x(λ), λ] + \frac{1}{2}α_{λ}^{2}z_{λ}^{T} (A + λC)z_{λ}.

We now make use of the assumption that c[x(λ) + α_{λ}z_{λ}] = 0 to obtain

q[x(λ) + α_{λ}z_{λ}] = q[x(λ)] + λc[x(λ)] + \frac{1}{2}α_{λ}^{2}z_{λ}^{T} (A + λC)z_{λ}.

The result now follows from Theorem 6.1.

Theorem 6.2 is applicable if λ is sufficiently close to λ^{∗} and A + λ^{∗}C is positive semidefinite and singular. However, Theorem 6.2 is also applicable if we find λ ∈ I_{PD} and z_{λ} such that \frac{1}{2}z_{λ}^{T} (A + λC)z_{λ} is smaller than ϵ_{q}. Thus, if there is an α_{λ} ∈ IR such that c[x(λ) + α_{λ}z_{λ}] = 0, then the termination criteria (6.1) are satisfied for any ϵ_{c} > 0.

The theorems of this section extend results of Moré and Sorensen [15] to the case where the quadratic function c is arbitrary. Theorem 6.2 is an extension of Lemma 3.4 in that paper, while Theorem 6.1 is a generalization of Lemma 3.13.

7 Concluding Remarks

During the final stages of the preparation of this manuscript I attended the Panamerican Workshop on Applied and Computational Mathematics (Universidad Simon Bolivar, Caracas, January 10–15, 1993), where Henry Wolkowicz gave me a copy of his recently completed manuscript [18] with Ronald Stern on the problem

min{q(x) : c_{l} ≤ x^{T} Cx ≤ c_{u}},  (7.1)

and on the application of this problem to nonsymmetric eigenvalue perturbations. Although the two manuscripts are related, there are several differences in our approach and results.

If we consider the one-sided case of (7.1), then it is clear that (7.1) is a special case of (1.3); however, note that if ∇^{2}c = C is nonsingular, then a change of variables transforms (1.3) into (7.1).

The characterization result in [18] assumes that ∇c(x^{∗}) ≠ 0, or that c_{l} < 0 < c_{u}. As pointed out in Section 3, this assumption is stronger than (3.2) for the equality constrained case where c_{l} = c_{u}. Note, in particular, that if C is indefinite, then (3.2) is automatically satisfied, but that this is not the case for the assumptions in [18]. Similar remarks apply to the inequality constrained case where c_{l} = −∞.

The introduction of the two-sided bounds in (7.1) is an interesting variation. We can handle this variation, and the more general problem

min{q(x) : c_{l} ≤ c(x) ≤ c_{u}},

with the material in Sections 5 and 6. The main difference is that instead of looking for a solution of ϕ(λ) = 0, we would search for either a solution λ^{∗} ≥ 0 in I_{PD} of ϕ(λ^{∗}) = c_{u}, or a solution λ^{∗} ≤ 0 in I_{PD} of ϕ(λ^{∗}) = c_{l}. Since ϕ is either constant or strictly decreasing, we can update the interval (λ_{l}, λ_{u}) of Section 5 and isolate the appropriate solution.

Our treatments of the algorithm also differ. Stern and Wolkowicz [18] follow the development of Moré and Sorensen [15] and outline an algorithm that exploits the Cholesky factorization of A + λC, while our treatment in Sections 5 and 6 is independent of the method used to determine the solution x(λ) of the linear system (5.2). We also note that the application of their algorithm to (1.3) requires a change of variables to reduce the problem to the standard form (7.1). In our approach this change of variables is not needed. Acknowledgments. My enjoyable discussions with Henry Wolkowicz at the Panamerican Workshop on Applied and Computational Mathematics are gratefully acknowledged. Gail Pieper deserves special thanks for her careful reading of the manuscript.

References

[1] D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 1982.

[2] T. F. Coleman and C. Hempel, Computing a trust region step for a penalty function, SIAM J. Sci. Statist. Comput., 11 (1990), pp. 180–201.

[3] F. Critchley, On the minimization of a positive definite quadratic form under an arbitrary quadratic constraint, Technical Report, University of Warwick, Coventry, England, 1990.

[4] W. Gander, Least squares with a quadratic constraint, Numer. Math., 36 (1981), pp. 291–307.

[5] D. M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. Statist. Comput., 2 (1981), pp. 186–197.

[6] , Subroutines for unconstrained minimization using a model/trust region approach, ACM Trans. Math. Software, 9 (1983), pp. 503–524.

[7] G. Golub and U. von Matt, Quadratically constrained least squares and quadratic problems, Numer. Math., 59 (1991), pp. 561–580.

[8] G. H. Golub and C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, 1989.

[9] M. Heinkenschloß, On the solution of a two ball trust region subproblem, Technical Report 92-16, Universität Trier, Trier, Germany, 1992.

[10] M. R. Hestenes, Optimization Theory, John Wiley & Sons, 1975.

[11] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985.

[12] N. Karmarkar, M. G. C. Resende, and K. G. Ramakrishnan, An interior point algorithm to solve computationally difficult set covering problems, Math. Programming, 52 (1991), pp. 597–618.

[13] M. G. Krein and J. L. Smuljan, Plus-operators in a space with an indefinite metric, Amer. Math. Soc. Transl., 85 (1969), pp. 93–113.

[14] J. M. Martínez and S. A. Santos, A trust region method for minimization on arbitrary domains, Technical Report, State University of Campinas, Campinas, Brazil, 1991.

[15] J. J. Moré and D. C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Comput., 4 (1983), pp. 553–572.

[16] P. M. Pardalos, Y. Ye, and C.-G. Han, Algorithms for the solution of quadratic knapsack-problems, Linear Algebra Appl., 152 (1991), pp. 69–91.

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

[18] R. J. Stern and H. Wolkowicz, Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, Technical Report SOR 93-1, Princeton University, Princeton, New Jersey, 1993.

[19] F. Uhlig, A recurring theorem about pairs of quadratic forms and extensions: A survey, Linear Algebra Appl., 25 (1979), pp. 219–237.

[20] Y. Ye, On affine scaling algorithms for nonconvex quadratic programming, Math. Programming, 56 (1992), pp. 285–300.

[21] Y. Yuan, On a subproblem of trust region algorithms for constrained optimization, Math. Programming, 47 (1990), pp. 53–63.

[22] , A dual algorithm for minimizing a quadratic function with two quadratic constraints, J. Comput. Math., 9 (1991), pp. 348–359.

[23] Y. Zhang, Computing a Celis-Dennis-Tapia trust-region step for equality constrained optimization, Math. Programming, 55 (1992), pp. 109–124.