Second-order sufficient optimality conditions for local and global nonlinear programming

Arnold Neumaier

AT&T Bell Laboratories 600 Mountain Avenue Murray Hill, NJ 07974-0636 U.S.A. email: neum@cma.univie.ac.at

Abstract. This paper presents a new approach to the sufficient conditions of nonlinear programming. Main result is a sufficient condition for the global optimality of a Kuhn-Tucker point. This condition can be verified constructively, using a novel convexity test based on interval analysis, and is guaranteed to prove global optimality of strong local minimizers for sufficiently narrow bounds. Hence it is expected to be a useful tool within branch and bound algorithms for global optimization.

Keywords: global optimization, optimality condition, second-order sufficient condition, verification of convexity, interval analysis

1991 MSC Classification: primary 90C30, secondary 65G10 In this note we consider smooth nonlinear programs of the form

\begin{matrix}min & f(x) \\ s.t. & u ≤ x ≤ v , F (x) = 0 , \end{matrix}  (1)

where u, v ∈ IR^{n}(u < v) define the box

[u, v] := {x ∈ IR^{n} | u ≤ x ≤ v}

with nonempty interior, and f : [u, v] → IR, F : [u, v] → IR^{r} are continuously differentiable. Here (as always in the following) all inequalities involving vectors are interpreted componentwise. We shall allow some of the bounds to be infinite, u_{k} = −∞ or v_{k} = ∞, to allow for one-sided bounds and unbounded variables; but in practice it is advisable to add sensible bounds to all variables. By the introduction of slack variables, arbitrary nonlinear programs can be written in this form. In the following, g = ∇f denotes the gradient of f. If K is a set of indices, x_{K} denotes the subvector of a vector x obtained by discarding rows not indexed by K, A_{·K} (or A_{K·}) is the submatrix of a matrix A obtained by discarding columns (or rows) not indexed by K, and A_{KK} is the square submatrix of a square matrix A obtained by discarding rows and columns not indexed by K. A_{·k} denotes the kth column of a matrix A. Section 1 gives our main result in Theorem 1.2, and some additional remarks. In Section 2 we show that the sufficient global optimality condition derived in Theorem 1.2 is strong enough to deduce from it the standard second order sufficient conditions for local minimizers (Theorem 2.3) when the box constraint is narrowed to a small neighbourhood of a Kuhn-Tucker point. At the same time, our new proof of these conditions gives important hints for a constructively verifiable version of the global optimality condition that reduces the global optimality proof to one of verifying convexity of the generalized augmented Lagrangian. Section 3 shows that this can be done by means of interval analytic techniques.

1 Global optimality of Kuhn-Tucker points

For the nonlinear program (1), the most general necessary conditions for optimality, the Karush-John conditions, can be formulated as follows.

1.1. Theorem. (First order optimality conditions for nonlinear programs with two-sided bounds) Let x̂ ∈ IR^{n} be a solution of the nonlinear program (1) with u < v. Then there are multipliers κ ≥ 0 and ẑ ∈ IR^{r}, not both zero, such that the vector

ŷ:= κg(x̂) − F′(x̂)^{T} ẑ  (2)

satisfies the two-sided complementarity condition

\begin{matrix}ŷ_{k} ≥ 0  if x̂_{k} = u_{k} , \\ ŷ_{k} ≤ 0  if x̂_{k} = v_{k} , \\ ŷ_{k} = 0  otherwise. \end{matrix} \}  (3)

Moreover, if the constraint qualification

rk F′(x̂)_{·K_{0}} = r ,  where K_{0} = {k | u_{k} < x̂_{k} < v_{k}}  (4)

(or one of a number of similar constraint qualifications) holds, we can take κ = 1.

Proof. This follows easily from the corresponding conditions in the standard form with general inequalities (Karush [5], John [4]) by eliminating the multipliers corresponding to the bound constraints. _{□}

A feasible point x such that (2) and (3) hold for κ = 1 and suitable ẑ is generally referred to as a Kuhn-Tucker point (after Kuhn & Tucker [6]), with associated Lagrange multiplier ẑ (after Lagrange [7], Part II, Ch. XI, Sec. 58). Except for convex programs, the first order conditions are usually not sufficient for optimality, and Kuhn-Tucker points need not be local minima. However, we shall show that it is possible to modify the original objective function in such a way that convexity of the modification still provides optimality for the original problem. This modification can often be achieved locally, and suffices to derive a semilocal version of well-known sufficient conditions for local optimality. Here the adjective semilocal refers to the fact that the new sufficient condition actually verifies not only local optimality but in fact global optimality within a pre-specified local region around the local minimum. This fact allows our new condition to be employed as a natural stopping criterion guaranteeing finite termination in branch and bound algorithms for global constrained optimization, at least in the absence of degeneracy. Indeed, this can be achieved in a similar way as a more specialized sufficient condition for concave optimization is used in Horst & Tuy [2] (Theorem V.1). But algorithmic aspects will not be considered in the present paper.

1.2. Theorem. Let x̂ be a Kuhn-Tucker point for the nonlinear program (1), with associated multiplier ẑ, and let

ŷ:= g(x̂) − F′(x̂)^{T} ẑ,  (5)

D = Diag (\sqrt{\frac{2|ŷ_{1}|}{v_{1} − u_{1}}} , …, \sqrt{\frac{2|ŷ_{n}|}{v_{n} − u_{n}}} ) .  (6)

If, for some continuously differentiable function φ : IR^{m} → IR with

φ(0) = 0, φ′(0) = ẑ^{T} ,  (7)

the generalized augmented Lagrangian

L̂(x) := f(x) − φ(F (x)) + \frac{1}{2}∥D(x − x̂)∥_{2}^{2}  (8)

is convex in [u, v], then x̂ is a global solution of (1). Moreover, if L̂(x) is strictly convex in [u, v], this solution is unique.

Proof. Clearly, L̂(x̂) = f(x̂) − φ(0), and since

L̂′(x) = g(x)^{T} − φ′(F (x))F′(x) + (x − x̂)^{T} D^{T} D

we have

L̂′(x̂) = g(x̂)^{T} − φ′(0)F′(x̂) = g(x̂)^{T} − ẑ^{T} F′(x̂) = ŷ^{T} .

Therefore, for any x ∈ [u, v], convexity yields

L̂(x) ≥ L̂(x̂) + L̂′(x̂)(x − x̂) = f(x̂) + ŷ^{T} (x − x̂).

If x is feasible then F (x) = 0, so that

f(x) = L̂(x)+φ(0)− \frac{1}{2}∥D(x−x̂)∥_{2}^{2} ≥ f(x̂)+ŷ^{T} (x−x̂)− \frac{1}{2}∥D(x−x̂)∥_{2}^{2}. (9)

Since D is diagonal, this implies that

f(x) ≥ f(x̂) + \frac{1}{2} ∑_{k} (2ŷ_{k}(x_{k} − x̂_{k}) − D_{kk}^{2}(x_{k} − x̂_{k})^{2}) .  (10)

The complementarity condition together with the definition of D now implies that each term in the sum is nonnegative: If ŷ_{k} = 0 then D_{kk} = 0 and D_{kk}^{2}(x_{k} − x̂_{k})^{2} = 0 = 2ŷ_{k}(x_{k} − x̂_{k}). If ŷ_{k} > 0 then x̂_{k} = u_{k} and D_{kk}^{2}(x_{k} − x̂_{k})^{2} ≤ D_{kk}^{2}(v_{k} − u_{k})(x_{k} − x̂_{k}) = 2ŷ_{k}(x_{k} − x̂_{k}). And if ŷ_{k} < 0 then x̂_{k} = v_{k} and D_{kk}^{2}(x_{k} − x̂_{k})^{2} = D_{kk}^{2}(x̂_{k} − x_{k})^{2} ≤ D_{kk}^{2}(v_{k} − u_{k})(x̂_{k} − x_{k}) = 2|ŷ_{k}|(x̂_{k} − x_{k}) = 2ŷ_{k}(x_{k} − x̂_{k}). Therefore, (10) implies that f(x) ≥ f(x̂) for all x ∈ [u, v] with F (x) = 0. Thus, x̂ is a global solution of (1). Uniqueness follows along the same line by observing that strict convexity excludes equality except for x = x̂. _{□}

1.3. Remark. The same result holds if we use in place of (6) an arbitrary (not necessarily diagonal) matrix D with

∥D_{·k}∥_{2}^{2} ≤ 2ŷ_{k}^{2}/σ (k = 1, …, n),  (11)

where

σ = sup {ŷ^{T} (x − x̂) | u ≤ x ≤ v, F (x) = 0}

(or any computable upper bound). Indeed, in this case (9) implies

f(x) ≥ f(x̂) + \frac{1}{2} min \{2|ŷ|^{T} s − ∥Cs∥_{2}^{2} | s ≥ 0, |ŷ|^{T} s ≤ σ\} ,  (12)

where s = Σ(x − x̂), C = DΣ with Σ = Diag(sgn ŷ_{1}, …, sgn ŷ_{n}). But (11) implies that the minimum in (12) is zero, as a consequence of the following result (similar to Proposition 1 of Neumaier [9], used to derive sufficient conditions for global quadratic programs), applied for a = 2|ŷ|, b = |ŷ|/σ:

1.4. Proposition. Let a, b ∈ IR^{n} be nonnegative, and suppose that C ∈ IR^{m×n} satisfies

∥C_{·k}∥_{2}^{2} ≤ a_{k}b_{k} (k = 1, …, n).

Then

∥Cx∥_{2}^{2} ≤ a^{T} x for all x ≥ 0 with b^{T} x ≤ 1.  (13)

Proof. We may assume that all components b_{k} are positive since the general case follows from this by continuity. The function f defined by f(x) := a^{T} x − ∥Cx∥_{2}^{2} is concave, hence assumes its minimum over the simplex {x ≥ 0 | b^{T} x ≤ 1} at a vertex. Thus the minimum is either at x = 0 (where f = 0), or at a scaled unit vector x = b_{k}^{−1}e^{(k)} (where f = a_{k}b_{k}^{−1} − ∥C_{·k}∥_{2}^{2}b_{k}^{−2} ≥ 0 by assumption). Thus f(x) ≥ 0 on the simplex, giving the desired bound (13).

□

2 Local second order optimality conditions

To discuss second-order optimality conditions we shall assume for the following that f and F are twice continuously differentiable in the box [u, v]. For the simplest choice conforming with (7), namely φ(s) = ẑ^{T} s, Theorem 1.2 implies that x̂ is a local solution of (1) if the Hessian

Ĝ := L′′(x̂) = f′′(x̂) − ∑_{j} ẑ_{j}F′′_{j}(x̂)  (14)

at x̂ of the Lagrangian

L(x) := f(x) − ẑ^{T} F (x)  (15)

is positive definite. Indeed, if Ĝ = L′′(x̂) is positive definite then so is L̂′′(x̂) = L′′(x̂) + D^{T} D. Therefore L̂(x) is strictly convex in a neighborhood of x̂, and we can apply Theorem 1.2 in this neighborhood. Hence x̂ is a local solution. However, the simple univariate example

min −x^{2} s.t. − 1 ≤ x ≤ 1

shows that, at a local solution, the Hessian of the Lagrangian need not even be positive semidefinite. Thus the definiteness condition on the Hessian is too restrictive; necessary conditions only provide semidefiniteness of Ĝ on a subspace:

2.1. Theorem. (Second order necessary optimality conditions for nonlinear programs with two-sided bounds) Let x̂ be a local solution of (1), and let

J_{0} = {k | x̂_{k} = u_{k} or x̂_{k} = v_{k}}.  (16)

With the above notation, if the constraint qualification (4) is satisfied then the following, equivalent conditions hold:

(i) F′(x̂)s = 0 , s_{J_{0}} = 0 ⇒ s^{T} Ĝs ≥ 0. (ii) For some matrix (and hence all matrices) Z_{0} whose columns form a basis of the subspace defined by the left-hand side of (i), Z_{0}^{T} ĜZ_{0} is positive semidefinite.

Proof. This is well-known but for the sake of completeness we give a short proof.

(i) The constraint qualification (4) and the implicit function theorem imply that in a neighborhood of x̂, the manifold of solutions of F (x) = 0, x_{J_{0}} = x̂_{J_{0}} can be parametrized as {x(s) | s ∈ S}, where

S = {s ∈ IR^{n} | F′(x̂)s = 0, s_{J_{0}} = 0},

in such a way that x(s) = x̂ + s + o(∥s∥). Hence, for sufficiently small s ∈ S, we have 0 ≤ f(x(s)) − f(x̂) = L(x(s)) − L(x̂) = L′(x̂)(x(s) − x̂) + \frac{1}{2}(x(s) − x̂)^{T} L′′(x̂)(x(s) − x̂) + o((∥s∥^{2}) = s^{T} Ĝs + o((∥s∥^{2}). If we now replace s by ϵs, divide by ϵ^{2}, and take the limit ϵ → 0, we arrive at s^{T} Ĝs ≥ 0.

(i) ⇔ (ii): If (i) holds then s = Z_{0}p satisfies the hypothesis of (i) so that 0 ≤ s^{T} Ĝs = p^{T} Z_{0}^{T} ĜZ_{0}p. Thus Z_{0}^{T} ĜZ_{0} is positive semidefinite, and (ii) holds. Conversely, any s satisfying the hypothesis of (i) can be written as s := Z_{0}p. Hence, if Z_{0}^{T} ĜZ_{0} is positive semidefinite, s^{T} Ĝs = p^{T} Z_{0}^{T} ĜZ_{0}p ≥ 0, and (i) holds. _{□}

2.2. Remarks. (i) Generally, the Hessian of the Lagrangian agrees with the Hessian of the objective function only when all constraints are linear (F′′_{i}(x) = 0). Thus the curvature of the constraints enters the second order conditions in an essential way. (ii) A slightly more careful argument shows that one can strengthen the necessary condition in Theorem 2.1(i) to (i’) If F′(x̂)s = 0 and

s_{k} = 0 if ŷ_{k} ≠ 0,
s_{k} ≥ 0 if ŷ_{k} = 0, x̂_{k} = u_{k},
s_{k} ≤ 0 if ŷ_{k} = 0, x̂_{k} = v_{k},

then s^{T} Ĝs ≥ 0. However, this condition is much more difficult to check, and is the reason that deciding local optimality (in the absense of strict complementarity) is NP-hard (cf. Pardalos & Schnitger [10] and the recent book by Horst et al. [3]).

We show now that, with a more sophisticated choice of φ, we can get sufficient optimality conditions where – as in the unconstrained case – the gap to the necessary conditions is only slight. Of course, these sufficient conditions can also be derived from the traditional sufficient conditions for problems with arbitrary equality and inequality constraints, see e.g., Fletcher [1], Section 9.3. The present proof is given to show that the new global sufficient condition is indeed strong enough to imply the local result. Moreover, details in the proof are needed in Section 3 to motivate a constructively verifiable version of the global optimality condition.

2.3. Theorem. (Second order sufficient optimality conditions for nonlinear programs with two-sided bounds) With the above notation, let

J = {k | ŷ_{k} ≠ 0}, K = {k | ŷ_{k} = 0}.

A sufficient condition for a local minimizer is that any of the following, equivalent conditions holds:

(i) F′(x̂)s = 0 , s_{J} = 0 ⇒ s^{T} Ĝs > 0 or s = 0. (ii) For some matrix (and hence all matrices) Z whose columns form a basis of the subspace defined by the left-hand side of (i), Z^{T} ĜZ is positive definite. (iii) For some matrix (and hence all matrices) A whose rows form a basis of the row space of F′(x̂)_{·K},

Ĝ_{KK} + βA^{T} A is positive definite for some β ≥ 0.  (17)

A Kuhn-Tucker point satisfying the above sufficient conditions for optimality is called a strong local minimizer of (1). Both matrices Z^{T} ĜZ and Z_{0}^{T} ĜZ_{0} are referred to as reduced Hessians of the Lagrangian. If we compare with (16) and (4) we see that J ⊆ J_{0} and K ⊇ K_{0} by the complementarity condition (3), hence the condition in Theorem 2.3(i) is a little more restrictive than that in Theorem 2.1(i). However, in practice we usually have strict complementarity, i.e., the condition J = J_{0} (equivalently K = K_{0}) holds at least for some choice of the multiplier vector ẑ, and then the difference between Theorem 2.1(i) and Theorem 2.3(i) is only marginal.

Proof. We first prove that (iii) implies local optimality. The construction of A implies that there is a matrix B such that A = BF′(x̂)_{·K}. If we define

φ(s) := ẑ^{T} s − \frac{β}{2} ∥Bs∥^{2}  (18)

then the generalized augmented Lagrangian (8) satisfies

L̂′′(x̂) = H + D^{T} D,  (19)

where H = Ĝ + βF′(x̂)^{T} B^{T} BF′(x̂). By assumption, the matrix H_{KK} = Ĝ_{KK} + βA^{T} A is positive definite. Since, for u_{k}, v_{k} sufficiently close to x̂_{k}, the diagonal entries D_{kk}^{2} (k ∈ J) become arbitrarily large by (6), we conclude from (19) and continuity that L̂′′(x) is positive definite in every sufficiently narrow box around x̂_{k}. Local optimality therefore follows from Theorem 1.2. It remains to prove the equivalence of (i) – (iii). (iii) ⇒ (i): If (17) holds then the hypothesis of (i) implies As_{K} = 0, hence s^{T} Ĝs = s_{K}^{T} Ĝ_{KK}s_{K} = s_{K}^{T}(Ĝ_{KK} + βA^{T} A)s_{K} > 0 unless s = 0. Thus (i) is valid.

(i) ⇒ (ii): If (i) holds then p ≠ 0 implies s := Zp ≠ 0, hence 0 < s^{T} Ĝs = p^{T} Z^{T} ĜZp. Thus Z^{T} ĜZ is positive definite, and (ii) holds. (ii) ⇒ (iii): Since the rows of A are linearly independent we can find a matrix P such that AP = I. If (ii) holds, the Cholesky factorization LL^{T} of Z^{T} ĜZ produces a nonsingular L, and we may define the matrices

N := ĜZL^{−T} ,
M := P^{T} (Ĝ − NN^{T})_{KK}P.

Now let x ∈ IR^{n} be arbitrary and w := Ax_{K}. The vector s with s_{J} = 0 and s_{K} := x_{K} − P w satisfies As_{K} = w − AP w = 0 and hence the hypothesis of (i). Hence s = Zp for some p, and we find

x_{K}^{T} Ĝ_{KK}x_{K} = (s_{K} + P w)^{T} Ĝ_{KK}(s_{K} + P w)
= s_{K}^{T} Ĝ_{KK}s_{K} + 2(P w)^{T} Ĝ_{KK}s_{K} + (P w)^{T} Ĝ_{KK}P w. (20)

Using

s_{K}^{T} Ĝ_{KK}s_{K} = s^{T} Ĝs = p^{T} Z^{T} ĜZp = p^{T} L^{T} Lp

and

Ĝ_{KK}s_{K} = Ĝ_{K·}s = Ĝ_{K·}Zp = N_{K·}L^{T} p,

we can rewrite (20) as

x_{K}^{T} Ĝ_{KK}x_{K} = p^{T} L^{T} Lp + 2(P w)^{T} N_{K·}L^{T} p + (P w)^{T} Ĝ_{KK}P w
= ∥L^{T} p + N_{K·}^{T}P w∥_{2}^{2} + w^{T} Mw.  (21)

If β is larger than the spectral radius of M (or only of the negative of its smallest eigenvalue) we can deduce that

x_{K}^{T}(Ĝ_{KK} + βA^{T} A)x_{K} = x_{K}^{T} Ĝ_{KK}x_{K} + βw^{T} w
= ∥L^{T} p + N_{K·}^{T}P w∥_{2}^{2} + w^{T} (M + βI)w ≥ 0.

Equality is possible only when w = 0 and the norm vanishes, leading to L^{T} p = 0, p = 0, s = Zp = 0 and hence to x_{K} = 0. This shows that Ĝ_{KK} + βA^{T} A is positive definite. _{□}

3 Verifiable sufficient conditions for global optimality

In the previous section we showed that, in principle, Theorem 1.2 can be used to verify global optimality in any sufficiently narrow box around a Kuhn-Tucker point satisfying the local second-order sufficient conditions. Within a branch and bound framework, this ensures that no infinitely fine subdivision is needed near the global optimizer, thus removing a serious problem from current branch and bound implementations.

However, to be useful for algorithmic applications, all steps in the verification process must be made fully constructive. Standard algorithms for local optimization generally provide, together with a Kuhn-Tucker point, also an associated Lagrange multiplier. Second order methods often provide a basis Z of the relevant null space, too, and a Cholesky factor of the reduced Hessian of the Lagrangian at x̂. To verify the hypothesis of Theorem 1.2, we must first choose a suitable functional φ. The proof of Theorem 2.3 shows that (18) is a sufficiently general choice. Since A is most easily produced as a submatrix of F′(x̂)_{·K}, B in (18) will be a monomial matrix, with exactly one nonzero per row. A suitable value for β can be found by calculating the smallest eigenvalue of the matrix M defined in the proof. The construction of M given in the proof only uses simple linear algebra; the right inverse P of A needed is typically available implicitly through the factorization which also provides Z; explicit Z and P are not needed when the computation is suitably arranged. This leaves the convexity check of the generalized augmented Lagrangian as the only nontrivial part of the global optimality verification procedure. And indeed, this causes some problems, since φ(x) as given by (18) is concave so that convex and concave parts in (8) may partially cancel. A general method for checking convexity of arbitrary C^{1} functions in a box using finitely many function values is impossible since convexity over a given box is no longer a local property. Therefore we can only hope to get a working method by restricting the kind of objective functions and constraints admitted. For quadratic programs, the generalized augmented Lagrangian is a quadratic function, and convexity is simply checked by attempting a Cholesky factorization of its Hessian. (This gives a much simpler sufficient condition than my previous result in [9].) For nonquadratic programs, we must use more sophisticated techniques. It turns out that a useful black box convexity check is possible with methods of interval analysis, at least in the case where all nonlinearities are given by arithmetic expressions and the boxes are not too wide. The basic paradigm is that with interval arithmetic and automatic differentiation, it is possible to calculate intervals containing the ranges of a function and its partial derivatives when the argument ranges over a box. The computed intervals usually overestimate the precise ranges; however, under very mild conditions on the form of the expressions, the width of the computed interval is of the order O(r) when the width of all components of the box is of order O(r). See, e.g., Neumaier [8], where the relevant background can be found. In particular, if G is a matrix of intervals (usually simply called an interval matrix), calculated as an enclosure of L̂′′(x) for x ∈ [u, v], then, with r = max{v_{k} − u_{k} | k = 1, …, n}, we generally have

|G − Ĝ| = O(r).

Such a statement implies a corresponding statement for all individual matrices G̃ ∈ G, with absolute values taken component-wise. In particular, if Ĝ is positive definite then all matrices in G are definite, too, provided the underlying box is not too wide. This was precisely the kind of argument used in the proof of Theorem 2.3, and it shows that the information provided by interval analysis is precisely what is needed to make the present results fully constructive. The only task remaining is to give a constructive criterion for simultaneously checking the definiteness of all members of an interval matrix. We give just one such result, showing that it can be done; various refinements are possible, using more of the machinery of interval analysis. However, since the methods are so different, details will be discussed elsewhere.

3.1. Theorem. (Sufficient conditions for convexity) Let f : [u, v] → IR be twice continuously differentiable on the compact box [u, v], and suppose that G is a symmetric interval matrix such that

f′′(x) ∈ G for all x ∈ [u, v].  (22)

(i) If some symmetric matrix G_{0} ∈ G is positive definite and all symmetric matrices in G are nonsingular then they are all positive definite, and f is uniformly convex in [u, v]. (ii) In particular, this holds if the midpoint matrix

Ǧ = (sup G + inf G)/2

is positive definite with inverse C, and the preconditioned radius matrix

Δ = |C| rad G,

where rad G = (sup G − inf G)/2,

satisfies the condition

∥Δ∥ < 1  (23)

(in an arbitrary norm).

Proof. (i) Since the eigenvalues are continuous functions of the matrix entries and the product of the eigenvalues (the determinant) cannot vanish, no eigenvalue changes sign. Hence the eigenvalues of all matrices in G are positive, since this is the case for the positive definite member. Thus all matrices in G are positive definite. By well-known results, uniform convexity of f now follows from (22). (ii) G_{0} = Ǧ belongs to G, and condition (23) implies strong regularity of the interval matrix G ([8], Section 4.1) and hence nonsingularity of all matrices in G. Thus (i) applies. _{□}

3.2. Remark. In many cases, the Hessian of the augmented Lagrangian can be shown to have the form

f′′(x) = ∑ u_{i}A_{i} with u_{i} ∈ u_{i},

for suitable constructively available real matrices A_{i} and intervals u_{i}. In this case, the above result can be strengthened (with virtually the same proof) by replacing Ǧ and Δ with

Ǧ = ∑ ǔ_{i}A_{i}

and

Δ′ = ∑ rad u_{i}|CA_{i}|,

respectively, where ǔ = (sup u + inf u)/2

and rad u = (sup u − inf u)/2.

Indeed, it is not difficult to see that for G = ∑ u_{i}A_{i}, we always have 0 ≤ Δ′ ≤ |Δ|, so that the refined test is easier to satisfy.

By applying this convexity test to the generalized augmented Lagrangian in place of f, we have a criterion which verifies the convexity of L̂(x) for x ∈ [u, v] in arbitrary sufficiently narrow boxes [u, v] around a strong local minimizer x̂, and thus proves that x̂ is the unique global minimizer within such a box.

References

1. R. Fletcher, Practical Methods of Optimization, 2nd ed., Wiley, Chichester 1987.

2. R. Horst and H. Tuy, Global Optimization: Deterministic Approaches, 2nd ed., Springer, Berlin, 1990.

3. R. Horst, P.M. Pardalos and N.V. Thoai, Introduction to Global Optimization Kluwer, Dordrecht 1995.

4. F. John, pp. 543–560 in: Fritz John, Collected Papers, Vol.2, Extremum problems with inequalities as subsidiary conditions, (J. Moser, ed.), Birkhäuser, Boston, 543–560, 1985.

5. W. Karush, Minima of Functions of Several Variables with Inequalitis as Side Constraints, M.Sc. Dissertation, Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois, 1939.

6. H. W. Kuhn and A. W. Tucker, pp. 481–492 in: Nonlinear programming, Proc. 2nd Berkeley Symp. Math. Stat. Prob., (J. Neyman, ed.), Univ. of California Press, Berkeley, California, 1951.

7. J.L. Lagrange, Théorie des fonctions analytiques, Impr. de la République, Paris 1797.

8. A. Neumaier, Interval Methods for Systems of Equations, Cambridge Univ. Press, Cambridge, 1990.

9. A. Neumaier, An optimality criterion for global quadratic optimization, J. Global Optimization 2 (1992), 201-208.

10. P.M. Pardalos and G. Schnitger, Checking local optimality in constrained quadratic programming is NP-hard, Oper. Res. Lett. 7 (1988), 33-35.