A NEW EXACT PENALTY FUNCTION

WALTRAUD HUYER^{†} AND ARNOLD NEUMAIER^{†}

Abstract. For constrained smooth or nonsmooth optimization problems, new continuously differentiable penalty functions are derived. They are proved exact in the sense that under some nondegeneracy assumption, local optimizers of a nonlinear program are precisely the optimizers of the associated penalty function. This is achieved by augmenting the dimension of the program by a variable that controls both the weight of the penalty terms and the regularization of the nonsmooth terms.

Key words. constrained optimization, nonlinear programming, nonsmooth optimization, exact penalty function, Mangasarian–Fromovitz condition, augmented Lagrangian

AMS subject classification. 90C30

1. Introduction. Smooth nonlinear programs are traditionally solved by augmenting the objective function or a corresponding Lagrangian function using penalty or barrier terms to take account of the constraints (see, e.g., the surveys [3, 15]). The resulting merit function is then optimized using either standard unconstrained (or bound constrained) optimization software or sequential quadratic programming (SQP) techniques. Independently of the technique used, the merit function always depends on a small parameter ε (or a large parameter ρ = ε^{−1}); as ε → 0, minimizers of the merit function converge to the set of minimizers of the original problem. In some SQP approaches, one uses instead so-called exact penalty functions that produce exact optimizers already at sufficiently small positive values of ε. In return, these exact penalty functions have the disadvantage that the evaluation of the merit function either needs Jacobian information (to estimate multipliers), or (for l_{1} or l_{∞} penalties) it is no longer smooth. In addition, both kinds of penalty functions may be unbounded below even when the constrained problem is bounded, which may make it difficult or impossible to locate a minimizer.

For nonsmooth nonlinear programs, solution techniques are much less developed, and often restricted to the convex or unconstrained case; in the latter case, constraints are usually handled by an l_{∞} exact penalty function (e.g. in Solvopt [6]). The various approaches are based on combinations of subgradient methods (e.g., [13, 4]), Moreau-Yosida regularization (e.g., [8, 9, 14]), or bundle techniques (e.g., [5, 7, 10]). The regularization again depends on a small smoothing parameter ε > 0 such that for ε → 0 the original nonsmooth functions are recovered.

In the following, we discuss a new merit function for smooth or nonsmooth optimization problems with equality, inequality and bound constraints that

• has good smoothness and exactness properties,

• remains bounded below under reasonable conditions,

• combines regularization with penalty techniques, and

• is flexible enough to give enough freedom for incorporating available Lagrange

multiplier estimates. The most important new idea is that the merit function is considered as a function of x and ε simultaneously, with the property that under appropriate assumptions, the

†Institut für Mathematik, Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria (Waltraud.Huyer@univie.ac.at, Arnold.Neumaier@univie.ac.at).

minimizer (x^{∗}, ε^{∗}) of the merit function satisfies ε^{∗} = 0, so that x^{∗} solves the original problem.

This paper is organized as follows. In §2, the case of a smooth constrained optimization problem with equality constraints and bound constraints is considered. A penalty function is introduced and it is proved that under certain assumptions, all local minimizers of this penalty function have the form (x, ε) with ε = 0 and x a solution of the original problem. A converse of this can be proved in much greater generality, namely for nonsmooth functions that are suitably regularized. Therefore, in §3, a nonsmooth objective function and nonsmooth constraints are replaced by regularized functions and regularization recipes for some common nonsmooth functions are given. As a preparation for the exactness proof, §4 proves some results involving regular zeros of a not necessarily smooth function. In §5 the penalty function is generalized to the regularized problem and it is proved that, for a solution x^{∗} of the constrained optimization problem, (x^{∗}, 0) is a minimizer of the penalty function. In §6 we illustrate our theory with an example, where the traditional penalty functions are unbounded. Finally, in §7 our penalty function is generalized to problems involving in addition inequality constraints; analogous results to those for equality constraints are shown to hold by reducing this case to the previous one with the aid of slack variables.

Notation. In the following, the absolute value of a vector is defined componentwise, |x| := (|x_{1}|, …, |x_{n}|)^{T}. Similarly, vector inequalities are understood componentwise. The norm used throughout is the Euclidean norm ∥x∥ = \sqrt{∑ x_{k}^{2}}, and B[x_{0}; r] denotes a closed Euclidean ball around x_{0} with radius r. The subvector of x indexed by the indices in J is denoted by x_{J}, and A_{:J} denotes the matrix consisting of the columns of a matrix A indexed by the indices in J. Sets of the form

x = [\underline{x}, \overline{x}] := \{x ∈ ℝ^{n} | \underline{x} ≤ x ≤ \overline{x}\},

where the lower bound \underline{x} ∈ (ℝ ∪ \{−∞\})^{n} and the upper bound \overline{x} ∈ (ℝ ∪ \{∞\})^{n} are vectors containing proper or infinite bounds on the components of x and \underline{x} ≤ \overline{x}, are referred to as n-dimensional boxes.

2. The smooth case. In this section we propose a class of penalty functions for the smooth constrained nonlinear optimization problem

\begin{matrix}min & f(x) \\ s.t. & x ∈ [u, v], F (x) = 0, \end{matrix} (2.1)

where [u, v] is a box in ℝ^{n} with nonempty interior, f : D → ℝ and F : D → ℝ^{m} are continuously differentiable in an open set D containing [u, v]. We fix w ∈ ℝ^{m} and consider the equivalent problem

\begin{aligned}min & f(x) \\ s.t. & F_{i}(x) = εw_{i} (i = 1, …, m), \\ & x ∈ [u, v], ε = 0. \end{aligned} (2.2)

This motivates the definition of the penalty function f_{σ} on D × [0, ε̄] by

(2.3) f_{σ}(x, ε) = \{ \begin{matrix}f(x) & if ε = Δ(x, ε) = 0, \\ f(x) + \frac{1}{2ε} · \frac{Δ(x, ε)}{1 − qΔ(x, ε)} + σβ(ε) & if ε > 0, Δ(x, ε) < q^{−1}, \\ ∞ & otherwise, \end{matrix}

with the constraint violation measure

Δ(x, ε) := ∥εw − F (x)∥^{2}, (2.4)

where, in addition, ε̄ > 0 and q > 0 are fixed and β : [0, ε̄] → [0, ∞) is continuous and continuously differentiable on (0, ε̄] with β(0) = 0. The surrogate optimization problem then reads

\begin{matrix}min & f_{σ}(x, ε) \\ s.t. & (x, ε) ∈ [u, v] × [0, ε̄]. \end{matrix} (2.5)

Note that f_{σ}(x, ε) is continuously differentiable in

D_{σ} = {(x, ε) ∈ D × (0, ε̄) | Δ(x, ε) < q^{−1}},

with continuous limits at the part of the boundary where the limit values are finite, in particular at (x, 0) with feasible x. Moreover,

f_{σ}(x, ε) = f(x) + \frac{ε}{2} · \frac{∥w∥^{2}}{1 − q∥w∥^{2}ε^{2}} + σβ(ε) ≥ f(x) = f_{σ}(x, 0) if F (x) = 0. (2.6)

The shift by εw in the definition of the constraint violation measure allows one to incorporate Lagrange multiplier estimates (that serve to be able to work with better conditioned Hessians; see the remark at the end of this section).

The denominator 1 − qΔ(x, ε) is included since it forces the level sets of f_{σ} to remain in the set {(x, ε) ∈ ℝ^{n} | Δ(x, ε) < q^{−1}} and hence in some sense close to the feasible set of (2.1). In particular, in many cases where the traditional quadratic penalty function (where w = 0 and q = 0) is unbounded below, moderate positive values for q give a well-behaved penalty problem (cf. the example in §6). Indeed, f_{σ} is bounded below on [u, v] × [0, ε̄] whenever f(x) is bounded below on the set

D′ = {x ∈ [u, v] | ∥F (x)∥ ≤ q^{−1/2} + ε̄∥w∥}. (2.7)

This is a reasonable condition since it always holds when f is bounded below on the feasible set, ε̄ is small enough, and q is large enough.

The term σβ(ε) is included since it allows to optimize simultaneously on x and ε, thus automatizing the adaptation of the penalty factor 1/2ε. Intuitively, many slices with different, fixed values of ε that are optimized in traditional quadratic penalty methods are arranged consecutively, and translated by the term σβ(ε) in such a way that the minimizers form a curve with decreasing function values as ε → 0. Therefore, simultaneous optimization over both x and ε automatically leads to a local minimum at ε = 0. Of course, we need conditions guaranteeing that the term σβ(ε) is enough to cause this behavior of the penalty function. As we shall see in §5, β(ε) = \sqrt{ε} is an appropriate (but not the only possible) choice.

We say that the Mangasarian–Fromovitz condition (see [11]) for (2.1) holds at x ∈ [u, v] if F′(x) has full rank and there is a p ∈ ℝ^{n} with F′(x)p = 0 and

p_{i} \{ \begin{matrix}> 0 & if x_{i} = u_{i}, \\ < 0 & if x_{i} = v_{i}. \end{matrix}

Theorem 2.1. In addition to the general assumptions mentioned after (2.1) and after (2.4), assume that the set (2.7) is bounded, that each x ∈ D′ satisfies the Mangasarian–Fromovitz condition, and that

β′(ε) ≥ β_{1} > 0 for 0 < ε < ε̄. (2.8)

If σ is sufficiently large, there is no Kuhn–Tucker point (x, ε) of (2.5) with ε > 0.

In particular, for sufficiently large σ, every local minimizer (x^{∗}, ε^{∗}) of the penalty problem (2.5) with finite f_{σ}(x^{∗}, ε^{∗}) has the form (x^{∗}, 0), where x^{∗} is a local minimizer of the original problem (2.1).

Proof. If (x, ε) is a Kuhn–Tucker point of (2.5) with ε > 0, then there exist vectors y, z ∈ ℝ^{n+1} such that

∇f_{σ}(x, ε) = y − z,
inf(y_{i}, x_{i} − u_{i}) = inf(z_{i}, v_{i} − x_{i}) = 0, i = 1, …, n,
y_{n+1} = inf(z_{n+1}, ε̄− ε) = 0,

where ∇f_{σ}(x, ε) is the gradient of f_{σ} with respect to (x, ε). The assertion of the theorem is proved by contradiction. Assume that there exists a sequence (x^{k}, ε_{k}, σ_{k}), ε_{k} ≠ 0 for all k, σ_{k} → ∞ as k → ∞, where (x^{k}, ε_{k}) is a Kuhn–Tucker point of f_{σ_{k}}. We use the abbreviation Δ_{k} := Δ(x^{k}, ε_{k}). The point x^{k} satisfies

∥F (x^{k})∥ ≤ Δ_{k}^{1/2} + ε_{k}∥w∥ ≤ q^{−1/2} + ε̄∥w∥;

hence x^{k} ∈ D′. Since D′ is closed and bounded, we may restrict to a subsequence if necessary, and assume that

(2.9)  lim_{k→∞} ε_{k} = ε^{∗} ∈ [0, ε̄] and lim_{k→∞} x^{k} = x^{∗} ∈ D′.

The condition \frac{∂}{∂ε}f_{σ_{k}}(x^{k}, ε_{k}) ≤ 0 yields

qΔ_{k}^{2} + ε_{k}^{2}∥w∥^{2} + 2ε_{k}^{2}(1 − qΔ_{k})^{2}σ_{k}β′(ε_{k}) ≤ ∥F (x^{k})∥^{2}, (2.10)

with equality in the case ε_{k} ≠ ε̄. Since the right-hand side is bounded and σ_{k} → ∞, this yields (in view of (2.8) and (2.9))

ε^{∗} = 0 or Δ^{∗} = q^{−1}, (2.11)

where Δ^{∗} := Δ(x^{∗}, ε^{∗}). The derivatives with respect to x give

f_{x_{i}}(x^{k}) + \frac{1}{(1 − qΔ_{k})^{2}ε_{k}} (F′(x^{k})^{T} (F (x^{k}) − ε_{k}w))_{i} \{ \begin{matrix}≥ 0 & if x_{i}^{k} = u_{i}, \\ = 0 & if u_{i} < x_{i}^{k} < v_{i}, \\ ≤ 0 & if x_{i}^{k} = v_{i}, \end{matrix} (2.12)

or

(F′(x^{k})^{T} (F (x^{k}) − ε_{k}w))_{i} + (1 − qΔ_{k})^{2}ε_{k}f_{x_{i}}(x^{k}) \{ \begin{matrix}≥ 0 & if x_{i}^{k} = u_{i}, \\ = 0 & if u_{i} < x_{i}^{k} < v_{i}, \\ ≤ 0 & if x_{i}^{k} = v_{i}, \end{matrix}

where f_{x_{i}} denotes the partial derivative of f with respect to x_{i}. By passing to the limit, using (2.9) and (2.11), we obtain

(F′(x^{∗})^{T} (F (x^{∗}) − ε^{∗}w))_{i} \{ \begin{matrix}≥ 0 & if x_{i}^{∗} = u_{i}, \\ = 0 & if u_{i} < x_{i}^{∗} < v_{i}, \\ ≤ 0 & if x_{i}^{∗} = v_{i}. \end{matrix} (2.13)

Since x^{∗} ∈ D′, the Mangasarian–Fromovitz condition holds for x = x^{∗} and some vector p ∈ ℝ^{n}. Let I_{1} := {i | x_{i}^{∗} = u_{i}}, I_{2} := {i | x_{i}^{∗} = v_{i}} and w^{∗} := F (x^{∗}) − ε^{∗}w. Then

0 = (F′(x^{∗})p)^{T} w^{∗} = ∑_{i∈I_{1}} p_{i}(F′(x^{∗})^{T} w^{∗})_{i} + ∑_{i∈I_{2}} p_{i}(F′(x^{∗})^{T} w^{∗})_{i},

and the Mangasarian–Fromovitz condition and (2.13) imply (F′(x^{∗})^{T} w^{∗})_{i} = 0 for i ∈ I_{1} ∪ I_{2} and thus F′(x^{∗})^{T} w^{∗} = 0. Now the fact that F′(x^{∗}) has full rank yields w^{∗} = 0, giving

F (x^{∗}) − ε^{∗}w = 0. (2.14)

Hence Δ^{∗} = 0, and by (2.11) we must have ε^{∗} = 0; therefore F (x^{∗}) = 0 by (2.14). Now (2.10) and (2.8) yield

\frac{q}{ε_{k}^{2}} Δ_{k}^{2} + ∥w∥^{2} + 2(1 − qΔ_{k})^{2}σ_{k}β_{1} ≤ \frac{1}{ε_{k}^{2}} ∥F (x^{k})∥^{2}.

Since β_{1} > 0, the last term on the left-hand side tends to ∞ as k → ∞. Thus the vectors y^{k} := ε_{k}^{−1}F (x^{k}) satisfy ∥y^{k}∥ → ∞, the vectors z^{k} := y^{k}/∥y^{k}∥ have norm 1, and (2.12) implies that the numbers μ_{i}^{k} (i = 1, …, n), defined by

μ_{i}^{k} := \frac{1}{∥y^{k}∥}f_{x_{i}}(x^{k}) + \frac{1}{(1 − qΔ_{k})^{2}} (F′(x^{k})^{T} z^{k})_{i} − \frac{1}{(1 − qΔ_{k})^{2}∥y^{k}∥}(F′(x^{k})^{T} w)_{i},

satisfy

μ_{i}^{k} \{ \begin{matrix}≥ 0 & if x_{i}^{k} = u_{i}, \\ = 0 & if u_{i} < x_{i}^{k} < v_{i}, \\ ≤ 0 & if x_{i}^{k} = v_{i}. \end{matrix}

If we pick a convergent subsequence z^{k_{l}} with limit z^{∗} and pass to the limit we obtain

(F′(x^{∗})^{T} z^{∗})_{i} \{ \begin{matrix}≥ 0 & if x_{i}^{∗} = u_{i}, \\ = 0 & if u_{i} < x_{i}^{∗} < v_{i}, \\ ≤ 0 & if x_{i}^{∗} = v_{i}. \end{matrix}

Now similarly as above this yields z^{∗} = 0, which is a contradiction to ∥z^{∗}∥ = 1. Thus such a sequence (x^{k}, ε_{k}, σ_{k}) cannot exist, and for sufficiently large σ all Kuhn–Tucker points of f_{σ} are of the form (x, 0).

Now let (x^{∗}, ε^{∗}) be a local minimizer of f_{σ} with finite f_{σ}(x^{∗}, ε^{∗}). If ε^{∗} > 0 then (x^{∗}, ε^{∗}) must be a Kuhn–Tucker point, contradiction. Therefore, ε^{∗} = 0, and since f_{σ}(x^{∗}, ε^{∗}) is finite, Δ(x^{∗}, ε^{∗}) = 0. Now (2.4) implies F (x^{∗}) = 0, so that x^{∗} is a feasible point of (2.1). Thus (2.6) implies that there is a neighborhood of x^{∗} where f(x) ≥ f(x^{∗}) for feasible x. Therefore x^{∗} is a local minimizer of (2.1).

We conclude that under the stated assumptions, minimizing the penalty function f_{σ} for sufficiently large σ yields a minimizer of the original problem. Conversely, as we shall prove in §5 in a more general setting, a minimizer x^{∗} of (2.1) yields a minimizer (x^{∗}, 0) of f_{σ} for sufficiently large σ and slightly stronger conditions on β(ε).

Remark. If w_{i} ≠ 0 for i = 1, …, n, we can write w_{i} = λ_{i}^{−1} and rewrite (2.2) as

min f(x)
s.t. λ_{i}F_{i}(x) = ε (i = 1, …, m),
x ∈ [u, v], ε = 0.

This is again of the form (2.2) with F_{i} replaced by λ_{i}F_{i} and w_{i} replaced by 1. There-

fore, the theorem also holds with Δ(x, ε) = ∑_{i=1}^{m}(ε−λ_{i}F_{i}(x, ε))^{2} in the penalty function (2.3). Now the penalty function has an augmented Lagrangian interpretation. Indeed, for (x, ε) with small Δ(x, ε) we obtain

f_{σ}(x) = f(x) + \frac{1}{2ε} · \frac{Δ(x, ε)}{1 − qΔ(x, ε)} + σβ(ε)
= f(x) + \frac{1}{2ε}Δ(x, ε) + σβ(ε) + O(Δ(x, ε)^{2})
= f(x) + \frac{1}{2ε} ∑_{i=1}^{m}(λ_{i}F_{i}(x) − ε)^{2} + σβ(ε) + O(Δ(x, ε)^{2})

= f(x) − ∑ λ_{i}F_{i}(x) + \frac{1}{2ε} ∑ λ_{i}^{2}F_{i}(x)^{2} + \frac{mε}{2} + σβ(ε) + O(Δ(x, ε)^{2}).

Thus, for fixed ε and up to constant additive terms and higher order terms, f_{σ} is an augmented Lagrangian, and the λ_{i} play the role of (fixed, initial) Lagrange multiplier estimates.

In particular, as in traditional multiplier penalty functions [1], if the λ_{i} are close to the Lagrange multipliers at the optimizer x^{∗} then f_{σ}(x, ε) is nearly stationary at x^{∗} for arbitrary fixed ε > 0. Therefore, numerical schemes for the minimization of f_{σ}(x, ε) get close to the minimizer already when ε is not very small, and hence when the Hessian of f_{σ} (which gets more and more ill-conditioned as ε → 0) is still well-conditioned.

3. Regularization of nonsmooth and ill-conditioned problems. In order to regularize the optimization problem (2.1) with not necessarily smooth functions f and F, we assume that we can embed f and F into a family of regularized functions f(x, ε) and F (x, ε) that are twice continuously differentiable in (x, ε) when ε > 0 and satisfy

f(x) = f(x, 0) = lim_{ε→0} f(x, ε), F (x) = F (x, 0) = lim_{ε→0} F (x, ε).

Of course, the case where the objective function and the constraints are already wellbehaved needs no modification, and in this case we simply put f(x, ε) = f(x) and F (x, ε) = F (x) for all ε.

Nonsmooth functions arising in practice are often factorable, i.e., composed of a finite sequence of elementary operations. Most elementary operations are smooth; the nonsmoothness arises through a small number of nonsmooth elementary functions. A natural regularization approach for factorable functions is to write each nonsmooth elementary function N(x) as a limit of smooth functions N(x, ε) that are twice continuously differentiable in (x, ε) when ε > 0,

N(x) = lim_{ε→0} N(x, ε).

Assuming that the objective and constraint functions are factorable, we may replace each occurrence N(r_{i}) of a nonsmooth elementary function in the definition of the objective and constraint functions with N(r_{i}, ερ_{i}) depending on an intermediate result r_{i} and a suitable scaling constant ρ_{i}. Then we end up with regularized functions f(x, ε) and F (x, ε) with the required properties. Possible forms of N(x, ε) for the most important nonsmooth N(x) are given in Table 3.1. Note that the first two formulas are independent of ξ; the particular choice indicated is numerically stable and allows to restrict the sum to those terms where the exponent is > log macheps, where macheps is the machine accuracy.

Some smooth nonlinear programs are very difficult to solve since the Hessian matrix of the Lagrangian is severely ill-conditioned everywhere. Often, the reason for this is that the objective function or some constraint contains subexpressions involving some huge or tiny constants. Such constants can be regularized, too, by adapting them according to the last two lines of Table 3.1.

Table 3.1 Some regularization recipes

N(x)  N(x, ε)  condition
max_{k} x_{k}  ξ + ε log ∑ exp ((x_{k} − ξ)/ε) ξ = max_{k} x_{k}
min_{k} x_{k}  ξ − ε log ∑ exp ((ξ − x_{k})/ε) ξ = min_{k} x_{k}
x^{t} (x ≥ 0, t < 2)  (x + ε)^{t}  t ≠ 0, 1
x^{t} log x (x ≥ 0, t ≤ 2) x^{t} log(x + ε)  t = 0, 1, 2
(x + ε)^{t} log(x + ε)  t ≠ 0, 1, 2
|x|^{t} (t < 2) |x^{t+k}|/(|x|^{k} + ε^{k}) k = ⌈2 − t⌉
|x|^{t} log |x| (0 < t ≤ 2) |x^{t+k}| log |x|/(|x|^{k} + ε^{k})  k = 1 + ⌊2 − t⌋
c (huge constant)  c/(1 + ε|c|)
c (tiny constant)  c + ε sign c

To approximate elementary functions with step discontinuities, such as

pos(x) = \{ \begin{matrix}1 & if x > 0, \\ 0 & if x ≤ 0, \end{matrix} nneg(x) = \{ \begin{matrix}1 & if x ≥ 0, \\ 0 & if x < 0, \end{matrix}

sign(x) = \{ \begin{matrix}1 & if x > 0, \\ 0 & if x = 0, \\ −1 & if x < 0, \end{matrix}

one may use the regularizations given in Table 3.2 (using x_{+} = max(x, 0)). However, no accompanying theory is available since the results presented in §5 require the Lipschitz continuity of the functions involved.

Table 3.2 Regularization of functions with step discontinuities

N(x)  N(x, ε)  condition
pos(x)  x_{+}^{3}/(x_{+}^{3} + ε^{3})
nneg(x)  x_{+}^{3}/(x_{+}^{3} + ε^{3})
sign(x)  x^{3}/(|x^{3}| + ε^{3})
\{ \begin{matrix}p & if x ≥ 0(> 0), \\ q & otherwise \end{matrix}

\{ \begin{matrix}px^{3}/(x^{3} + ε^{3}) & if x ≥ 0, \\ qx^{3}/(x^{3} − ε^{3}) & otherwise \end{matrix} pq ≤ 0

4. Regular zeros of nonsmooth functions. In this section we derive some technical results that are needed for the successful analysis of nonsmooth equality constraints.

Definition 4.1. A point x^{∗} ∈ ℝ^{n} is called a regular zero of a function H : D ⊆ ℝ^{n} → ℝ^{m}, m ≤ n, if x^{∗} is in the interior of D, satisfies H(x^{∗}) = 0, and there are a closed, convex and bounded set A of m × n-matrices and a matrix B ∈ ℝ^{(n−m)×n} such that the augmented matrix \binom{A}{B} is nonsingular for all A ∈ A and for every x, y

in some neighborhood N ⊆ D of x^{∗} there exists a matrix A ∈ A with

H(x) − H(y) = A(x − y). (4.1)

The regularity of a zero can be verified under quite general circumstances.

Proposition 4.2. A point x^{∗} ∈ ℝ^{n} is a regular zero of H if H is continuously differentiable in a neighborhood of x^{∗} and H′(x^{∗}) has full rank.

Proof. If H′(x^{∗}) has full rank, there is a matrix B such that \binom{H′(x^{∗})}{B} is square

and nonsingular. By continuity, there exists a convex neighborhood N of x^{∗} such that

\binom{H′(x)}{B} is nonsingular for x ∈ N and, as in the proof of [12, Proposition 5.1.4], (4.1)

is satisfied if we take for A the closed convex hull of {H′(x) | x ∈ N}.

The preceding result generalizes to certain piecewise differentiable functions if the nonsmoothness is not too severe. For example, we have

Proposition 4.3. A point x^{∗} ∈ ℝ^{n} is a regular zero of H(x) = G(x, |x − x^{∗}|) if G is continuously differentiable in a neighborhood of (x^{∗}, 0) with G(x^{∗}, 0) = 0, and if there exists a matrix B such that, for all diagonal matrices Σ ∈ ℝ^{n×n} with |Σ_{ii}| ≤ 1

for i = 1, …, n, the matrix \binom{∂_{1}G(x^{∗}, 0) + ∂_{2}G(x^{∗}, 0)Σ}{B} is nonsingular.

Proof. We mimic the proof of Neumaier [12, Proposition 5.1.4]. Without loss of generality, x^{∗} = 0. There is a ball N = B[0; δ] such that G(x, z) is continuously dif-

ferentiable for (x, z) ∈ N and every matrix \binom{∂_{1}G(x, z) + ∂_{2}G(x, z)Σ}{B} is nonsingular.

Let x, y ∈ N. By a version of the mean value theorem we have

G(x, |x|) − G(y, |y|) = ∫_{0}^{1} ∂_{1}G(y + s(x − y), |x|)(x − y) ds
+ ∫_{0}^{1} ∂_{2}G(y, |y| + s(|x| − |y|))(|x| − |y|) ds
= A(x − y),

where

A = ∫_{0}^{1} ∂_{1}G(y + s(x − y), |x|) ds + ∫_{0}^{1} ∂_{2}G(y, |y| + s(|x| − |y|))Σ ds

and Σ is the diagonal matrix with the diagonal entries

Σ_{ii} := \{ \begin{matrix}(|x_{i}| − |y_{i}|)/(x_{i} − y_{i}) & if x_{i} ≠ y_{i}, \\ 0 & otherwise. \end{matrix}

Since N is convex, A is contained in the closed convex hull A of the set of expressions ∂_{1}G(x, |x′|) + ∂_{2}G(y, |y′|)Σ, where x, x′, y, y′ ∈ N and Σ is a diagonal matrix with

|Σ_{ii}| ≤ 1 for i = 1, …, n. If N is chosen sufficiently small, \binom{A}{B} is nonsingular for all

A ∈ A.

In particular, this applies to H(x) = G(x) + δG_{1}(x, |x|) if G and G_{1} are continuously differentiable near 0, G′(0) has full rank, and δ is sufficiently small.

With a similar argument but now involving generalized derivatives (essentially the convex hull of the limit set of gradients of nicely approximating smooth functions; see, e.g., [2, 12]), the following result can be proved.

Proposition 4.4. A point x^{∗} ∈ ℝ^{n} is a regular zero of H(x) if H is Lipschitz continuous in a neighborhood of x^{∗} with H(x^{∗}) = 0, and if there exists a matrix B such that, for all matrices H′ contained in the generalized derivative of H at x^{∗}, the

matrix \binom{H′}{B} is nonsingular.

For x near a regular zero of H and an arbitrary set J of indices, one can find a small perturbation of the order of O(∥H_{J}(x)∥) such that the perturbed vector y satisfies H_{J}(y) = 0 and H_{i}(y) = H_{i}(x) for all i ∉ J.

Theorem 4.5. Let x^{∗} be a regular zero of H : D ⊆ ℝ^{n} → ℝ^{m}, m ≤ n. Then there are a neighborhood N_{0} ⊆ N of x^{∗} and a constant γ_{0} > 0 such that for each x ∈ N_{0} and each subset J of {1, …, m} there exists a vector y = y(x) ∈ N with H_{i}(y) = 0 for i ∈ J and H_{i}(y) = H_{i}(x) for i ∉ J such that

∥x − y∥ ≤ γ_{0}∥H_{J}(x)∥.

Proof. We define the neighborhood N_{0} := B[x^{∗}; (2γ_{0}(L + ∥B∥))^{−1}r] ∩ N, where r > 0 is such that the closed ball N_{1} := B[x^{∗}; r] is contained in the neighborhood N of x^{∗}, and

L := sup_{A∈A} ∥A∥ < ∞, γ_{0} := sup_{A∈A} ∥\binom{A}{B}^{−1}∥ < ∞

by assumption. By (4.1), the constant L is a Lipschitz constant for H. We fix a vector x ∈ N_{0} and a subset J of {1, …, m}, and put K := {1, …, m} \ J.

To find y, we want to apply the nonsmooth inverse function theorem given in Neumaier [12, Theorem 5.1.6(iv)] to the mapping F : N → ℝ^{n} defined by

F (z) := \binom{H(z)}{B(z − x^{∗})} for z ∈ N,

with the right-hand side

b^{∗} = \binom{b}{B(x − x^{∗})}, (4.2)

where b_{i} = 0 for i ∈ J and b_{i} = H_{i}(x) for i ∈ K, and x̃^{0} = x^{∗}. Since H(x^{∗}) = 0 implies F (x^{∗}) = 0, this requires that we show

F (z) ≠ sb^{∗} for all z ∈ ∂N_{1}, s ∈ [0, 1). (4.3)

If this holds, [12, Theorem 5.1.6(iv)] implies that there is a unique y ∈ N_{1} with F (y) = b^{∗}, hence H_{i}(y) = 0 for i ∈ J and H_{i}(y) = H_{i}(x) for i ∈ K. Moreover,

F (x) − F (y) = \binom{A}{B}(x − y)

for some A ∈ A and

∥F (x) − F (y)∥ = ∥H_{J}(x)∥,

hence

∥x − y∥ ≤ ∥\binom{A}{B}^{−1}∥ ∥H_{J}(x)∥ ≤ γ_{0}∥H_{J}(x)∥.

Thus y has the required properties.

To show (4.3), we suppose that F (z) = sb^{∗} for some z ∈ N_{1}, s ∈ [0, 1). Since N_{1} is contained in N, there exists an A ∈ A such that

sb^{∗} = F (z) = F (z) − F (x^{∗}) = \binom{A}{B}(z − x^{∗}),

and we obtain

∥z − x^{∗}∥ = ∥s\binom{A}{B}^{−1}b^{∗}∥ ≤ sγ_{0}∥b^{∗}∥.

Since H(x^{∗}) = 0, (4.2) implies ∥b^{∗}∥ ≤ ∥H_{K}(x) − H_{K}(x^{∗})∥ + ∥B(x − x^{∗})∥ ≤ (L + ∥B∥)∥x − x^{∗}∥, and we conclude

∥z − x^{∗}∥ ≤ sγ_{0}(L + ∥B∥)∥x − x^{∗}∥. (4.4)

Hence z ∈ B[x^{∗}; r/2] cannot lie on the boundary of N_{1}; in particular, (4.3) holds. This proves the theorem.

5. The local exactness proof. We now consider the optimization problem (2.1), where we now allow f and F to be nonsmooth functions. Clearly, with the embedding of §3 and a fixed w ∈ ℝ^{m}, (2.1) is equivalent to

\begin{aligned}min & f(x, ε) \\ s.t. & F_{i}(x, ε) = εw_{i} (i = 1, …, m), \\ & x ∈ [u, v], ε = 0. \end{aligned} (5.1)

We assume that f and F are continuous on D×[0, ε̄], where D is an open set containing [u, v] and ε̄ > 0, and twice continuously differentiable on its interior.

We use again the expression (2.3) for the penalty function but with f(x, ε) in place of f(x) and the regularized constraint violation measure

Δ(x, ε) := ∥εw − F (x, ε)∥^{2}. (5.2)

If, in addition to the assumptions mentioned after (2.4), β is twice continuously differentiable for ε > 0, the function f_{σ} is twice continuously differentiable for (x, ε) ∈ (0, ε̄) × [u, v] with Δ(x, ε) < q^{−1}.

It is conceivable that for this penalty function, a suitable analogue of Theorem 2.1 holds even in the nonsmooth case, but this requires an extension of the Kuhn– Tucker optimality conditions to nonsmooth problems, and we have not tried to handle the technicalities associated with this. On the other hand, we show here (after some preparation) that a converse of Theorem 2.1 can be proved in the nonsmooth case.

Assumptions. For the formal analysis, we shall suppose that, in addition to the general assumptions made above, the following assumptions (H_{f}), (H_{F}) and (H_{ε}) are satisfied in a neighborhood of some local (or global) minimizer x = x^{∗} of (5.1). Let I := {i | u_{i} < x_{i}^{∗} < v_{i}}; to simplify notation we assume that I = {1, …, p} with m ≤ p ≤ n.

(H_{f}) f(·, 0) is Lipschitz continuous with the Lipschitz constant k. (H_{F}) x^{∗} is a regular zero of F (·, 0) and x_{I}^{∗} is a regular zero of G : D_{1} ⊆ ℝ^{p} → ℝ^{m},

defined by G(x̃) := F (x, 0), where x_{i} = x̃_{i} for i = 1, …, p and x_{i} = x_{i}^{∗} for i = p + 1, …, n and D_{1} is an appropriate open set containing [u_{I}, v_{I}]. N is a neighborhood of x^{∗} according to Definition 4.1 such that, in addition, F (·, 0) is Lipschitz continuous in N and x_{I} ∈ [u_{I}, v_{I}] for x ∈ N.

(H_{ε}) There are positive constants ε̄ and K such that for all x ∈ N and all ε ∈ [0, ε̄],

∥F (x, 0) − F (x, ε)∥_{∞} ≤ Kε, |f(x, 0) − f(x, ε)| ≤ Kε.

(H_{β}) β satisfies lim inf_{ε→0} β(ε)/\sqrt{ε} > 0.

Lemma 5.1. x^{∗} is a regular zero of H : D ⊆ ℝ^{n} → ℝ^{m+n−p}, defined by H_{i}(x) := F_{i}(x, 0) for i = 1, …, m and H_{i}(x) := x_{i−m+p} − x_{i−m+p}^{∗} for i = m + 1, …, m + n − p, if and only if x^{∗} is a regular zero of F (·, 0) and x_{I}^{∗} is a regular zero of the mapping G defined in (H_{F}).

Proof. Let x, y ∈ N, where N is an appropriate neighborhood of x^{∗} according to Definition 4.1. In both cases we have F (x, 0) − F (y, 0) = A(x − y) for a matrix A ∈ A, where A is a closed, convex and bounded set of m × n-matrices such that the

augmented matrix \binom{A}{B} is nonsingular for all A ∈ A for some matrix B ∈ ℝ^{(n−m)×n}.

Then

H(x) − H(y) = \binom{A}{A′}(x − y),

where A′ := (0 I_{n−p}) ∈ ℝ^{(n−p)×n}, and

G(x_{I}) − G(y_{I}) = A_{:I}(x_{I} − y_{I}).

Let x^{∗} be a regular zero of H and let B′ ∈ ℝ^{(p−m)×n} be such that ( \begin{matrix}A \\ A′ \\ B′ \end{matrix} ) is

nonsingular for all A ∈ A. Then \binom{A_{:I}}{B′_{:I}} is nonsingular, i.e., x_{I}^{∗} is a regular zero

of G. Conversely, let x_{I}^{∗} be a regular zero of G and let B′_{:I} be such that \binom{A_{:I}}{B′_{:I}} is

nonsingular. Then ( \begin{matrix}A \\ A′ \\ B′′ \end{matrix} ) is nonsingular with B′′ = (B′_{:I} 0) ∈ ℝ^{(p−m)×n}. Therefore

x^{∗} is a regular zero of H.

Lemma 5.2. If (H_{f}) and (H_{F}) hold, there are a neighborhood N_{0} ⊆ N of x^{∗} and a constant γ_{1} > 0 such that

f(x, 0) ≥ f(x^{∗}, 0) − γ_{1}∥F (x, 0)∥ for all x ∈ N_{0} ∩ [u, v].

Proof. By (H_{F}), x^{∗} is a regular zero of the mapping H defined in Lemma 5.1. Let N_{0} ⊆ N and γ_{0} be as in Theorem 4.5, and let x ∈ N_{0}. Then by Theorem 4.5 with J := {i | F_{i}(x, 0) ≠ 0} there exists a y = y(x) with H(y) = 0 such that

∥x − y∥ ≤ γ_{0}∥H_{J}(x)∥ = γ_{0}∥F (x, 0)∥.

The fact that y_{i} = x_{i}^{∗} for i = p + 1, …, n and the choice of N in (H_{F}) imply that y ∈ [u, v], i.e., y is a feasible point. We therefore have f(y, 0) ≥ f(x^{∗}, 0) by assumption, and

f(x, 0) = f(x, 0) − f(y, 0) + f(y, 0) ≥ f(x^{∗}, 0) − k∥x − y∥
≥ f(x^{∗}, 0) − kγ_{0}∥F (x, 0)∥,

which finishes the proof.

Now we can prove the main theorem of this section.

Theorem 5.3. Under the above assumptions and for sufficiently large σ, there are a neighborhood N′ of x^{∗} and an ε′ ∈ (0, ε̄] such that

f_{σ}(x, ε) > f_{σ}(x^{∗}, 0) = f(x^{∗}, 0) for all (x, ε) ∈ N′ × (0, ε′].

In particular, (x^{∗}, 0) is a local minimizer of f_{σ}.

Proof. Let the neighborhood N′ ⊆ N_{0} of x^{∗} (N_{0} as in Lemma 5.2) be sufficiently small such that

sup_{x∈N′}(f(x^{∗}, 0) − f(x, 0)) ≤ \frac{1}{2}, (5.3)

let ε′ ∈ (0, ε̄], ε′ ≤ 1 be sufficiently small such that

β(ε) ≥ β_{2}\sqrt{ε} (5.4)

for 0 ≤ ε ≤ ε′ and a β_{2} > 0, and let

σ ≥ \frac{1}{β_{2}} (K(γ_{1} + 1) + γ_{1}(∥w∥ + 1)). (5.5)

For (x, ε) ∈ N′ × (0, ε′] we distinguish two cases.

Case 1. Let Δ(x, ε) ≥ ε. Then

f_{σ}(x, ε) ≥ f(x, ε) + \frac{1}{2} + σβ(ε)
≥ f(x^{∗}, 0) − \frac{1}{2} − Kε + \frac{1}{2} + σβ(ε)
≥ f(x^{∗}, 0) − K\sqrt{ε} + σβ_{2}\sqrt{ε} > f(x^{∗}, 0),

where we have used (H_{ε}), (5.3), (5.4), (5.5) and the fact that ε ≤ ε′ ≤ 1.

Case 2. If Δ(x, ε) < ε, then ∥F (x, ε)∥ < ε∥w∥ + ∥εw − F (x, ε)∥ ≤ ε∥w∥ + \sqrt{ε}, hence by Lemma 5.2 and (H_{ε}),

f(x^{∗}, 0) ≤ f(x, 0) + γ_{1}∥F (x, 0)∥
≤ f(x, ε) + Kε + γ_{1}(∥F (x, ε)∥ + Kε)
< f(x, ε) + K(γ_{1} + 1)ε + γ_{1}(\sqrt{ε} + ε∥w∥).

Therefore f_{σ}(x, ε) ≥ f(x, ε) + σβ(ε) > f(x^{∗}, 0) by (5.4), (5.5) and ε ≤ ε′ ≤ 1.

6. An example. To illustrate the theory developed, we consider the simple smooth nonlinear optimization problem

\begin{matrix}min & x_{1}^{3}x_{2}^{3} \\ s.t. & x_{1}^{2} + x_{2}^{2} = 1. \end{matrix}

It has a bounded feasible domain, two global minimizers at x^{∗} = (\frac{1}{2} \sqrt{2}, −\frac{1}{2} \sqrt{2})^{T} and x^{∗∗} = (−\frac{1}{2} \sqrt{2}, \frac{1}{2} \sqrt{2})^{T} with f(x^{∗}) = f(x^{∗∗}) = −\frac{1}{8}, and no other local minima. The traditional quadratic penalty function for this problem,

p(x) = x_{1}^{3}x_{2}^{3} + \frac{1}{2ε}(x_{1}^{2} + x_{2}^{2} − 1)^{2},

is unbounded below for all ε > 0 since, e.g., p(x) → −∞ for x = (s, −s)^{T}, s → ∞. This is also the case for traditional exact penalty functions, including multiplier penalty functions [1] that use an additional term +λ(x_{1}^{2} + x_{2}^{2} − 1). On the other hand, our new penalty function is bounded below. For w = 1 it reads

f_{σ}(x, ε) = \{ \begin{matrix}x_{1}^{3}x_{2}^{3} & for ε = Δ(x, ε) = 0, \\ x_{1}^{3}x_{2}^{3} + \frac{1}{2ε} · \frac{r^{2}}{1 − qr^{2}} + σβ(ε) & for ε > 0, |r| < q^{−1/2}, \\ ∞ & otherwise, \end{matrix}

where r := 1 + ε − x_{1}^{2} − x_{2}^{2}. Since f_{σ}(x, ε) = ∞ if ∥x∥ ≥ \sqrt{q^{−1/2} + 1 + ε}, the boundedness of our penalty function below is trivial. The Mangasarian–Fromovitz condition holds for all x ≠ 0, hence the assumptions of Theorem 2.1 are satisfied if q^{−1/2} + ε̄ < 1 and (2.8) holds; in this case, every local minimizer of the penalty function with a sufficiently large σ gives a solution of the original constrained problem.

In this particular example we can give an explicit analysis, and find that in fact weaker assumptions than those given in Theorem 2.1 suffice to get the conclusions, since ε̄ can be chosen arbitrarily large. To show this, let (x, ε) be a Kuhn–Tucker point of f_{σ} with ε > 0 and |r| < q^{−1/2}. Then ∂f_{σ}/∂x_{1} and ∂f_{σ}/∂x_{2} vanish at (x, ε), and ∂f_{σ}(x, ε)/∂ε ≤ 0, with equality if ε < ε̄. We have

\frac{∂f_{σ}}{∂x_{1}} (x, ε) = x_{1}(3x_{1}x_{2}^{3} − \frac{2r}{ε(1 − qr^{2})^{2}} ),
\frac{∂f_{σ}}{∂x_{2}} (x, ε) = x_{2}(3x_{1}^{3}x_{2} − \frac{2r}{ε(1 − qr^{2})^{2}} ),
\frac{∂f_{σ}}{∂ε} (x, ε) = \frac{r(2ε − r + qr^{3})}{2ε^{2}(1 − qr^{2})^{2}} + σβ′(ε).

Since σβ′(ε) > 0, ∂f_{σ}/∂ε ≤ 0 implies

r(2ε − r + qr^{3}) < 0; (6.1)

in particular r ≠ 0. Under this condition, the other partial derivatives vanish iff either x_{1} = x_{2} = 0 or

3x_{1}x_{2}^{3} = 3x_{1}^{3}x_{2} = \frac{2r}{ε(1 − qr^{2})^{2}} . (6.2)

If (6.2) holds then x_{1} = ±x_{2}, the definition of r gives 1 + ε − r = 2x_{1}^{2}, and (6.2) simplifies to

8|r| = 3ε(1 − qr^{2})^{2}(1 + ε − r)^{2}. (6.3)

If r > 0 then r > 2ε + qr^{3} > 2ε by (6.1), giving 0 ≤ 1 + ε − r < 1 − ε < 1. Now (6.3) implies 8r ≤ 3ε, contradicting r > 2ε. And if r < 0 then (6.3) and qr^{2} < 1 imply for q ≥ 1 that

\frac{−r}{2ε(1 − qr^{2})^{2}} = \frac{3}{16}(1 + ε + |r|)^{2} ≤ \frac{3}{16}(2 + ε̄) =: t

and

2ε − r + qr^{3} ≤ 2ε − r ≤ (2 + 2t)ε.

Now ∂f_{σ}/∂ε ≤ 0 gives σβ′(ε) ≤ t(2 + 2t). If (2.8) holds and σ > 2t(t + 1)/β_{1}, this is violated, (6.2) is impossible, and the only Kuhn-Tucker point of f_{σ} with ε > 0 can be at x_{1} = x_{2} = 0. But then r = 1 + ε and (6.1) requires q < (1 − ε)/(1 + ε)^{3}, again impossible if q ≥ 1.

Thus, for this example, the conclusion of Theorem 2.1 is valid for arbitrary ε̄ > 0 if (2.8) holds and q ≥ 1, provided that σ is sufficiently large. Note that for q ≥ 1 we have Δ(0, ε) = (1 + ε)^{2} > q^{−1}, so that the only point violating the Mangasarian–Fromovitz condition does not satisfy Δ(x, ε) < q^{−1}.

We now look at the converse. Theorem 5.3 gives conditions guaranteeing that every solution of the constrained problem is a local minimizer of f_{σ}. To verify this explicitly we need to investigate when it is possible that f_{σ} is below the common value −\frac{1}{8} of f_{σ}(x^{∗}, 0) and f_{σ}(x^{∗∗}, 0). Thus suppose that f_{σ}(x, ε) ≤ −\frac{1}{8}, (x, ε) ≠ (x^{∗}, 0), (x^{∗∗}, 0). Then ε > 0. Since

x_{1}^{3}x_{2}^{3} ≥ −\frac{1}{8}(x_{1}^{2} + x_{2}^{2})^{3} = −\frac{1}{8}(1 + ε − r)^{3} ≥ −\frac{1}{8}(1 + ε + |r|)^{3},

we find

8σβ(ε) ≤ −1 + (1 + ε + |r|)^{3} − 4r^{2}/ε =: p(|r|), |r| < q^{−1/2}. (6.4)

Now p(r) is a cubic polynomial. If ε < ε_{0} := \frac{1}{6}(−3 + \sqrt{33}) = 0.45742 …, the positive solution of ε_{0}(1 + ε_{0}) = \frac{2}{3}, then δ := 2 − 3ε(1 + ε) > 0, and p(r) has a unique local maximum at

r_{0} = \frac{3ε(1 + ε)^{2}}{2 + δ + \sqrt{8δ}} ≤ \frac{3}{2}ε(1 + ε)^{2} ≤ \frac{3}{2}ε(1 + ε_{0})^{2} = ε(1 + ε_{0}^{−1})

with function value

p(r_{0}) ≤ −1 + (1 + ε + r_{0})^{3} ≤ −1 + (1 + ε(2 + ε_{0}^{−1}))^{3} ≤ \frac{−1 + (2 + 2ε_{0})^{3}}{ε_{0}} ε < 52ε.

Here we used the fact that (−1 + (1 + ε(2 + ε_{0}^{−1}))^{3})/ε is monotone increasing. Now

p(|r|) ≤ max(p(r_{0}), p(q^{−1/2})) < 52ε for |r| < q^{−1/2}

if p(q^{−1/2}) < 0, which holds for any fixed q if ε is small enough. Thus (6.4) is violated if σβ(ε) > 6.5ε and ε is small enough. If (H_{β}) holds, this is the case for arbitrary σ and sufficiently small ε > 0. Thus we have a contradiction, and the conclusion of Theorem 5.3 holds for arbitrary σ. We also see that in this example the conclusion of Theorem 5.3 still holds if the condition lim inf_{ε→0} β(ε)/\sqrt{ε} > 0 in (H_{β}) is relaxed to

lim inf_{ε→0} β(ε)/ε > 0 and σ is chosen sufficiently large.

7. More general constraints. In this section we extend our theory to the more general constrained optimization problem

\begin{matrix}min & f(x) \\ s.t. & x ∈ [u, v], F_{l} ≤ F (x) ≤ F_{u}, \end{matrix} (7.1)

where F_{l} ∈ (ℝ ∪ {−∞})^{m} and F_{u} ∈ (ℝ ∪ {∞})^{m} are vectors containing proper or infinite bounds on the constraint functions and F_{l} ≤ F_{u}. This formulation is quite general since equality constraints are allowed by taking equal lower and upper bounds, and one-sided inequalities by taking infinite lower or upper bounds. Thus we treat equality constraints and one- or two-sided inequality constraints on the same footing. Moreover, we again assume that f and F are embedded into families of regularized functions f(x, ε) and F (x, ε) with f(x, 0) = f(x) and F (x, 0) = F (x).

For the one-dimensional boxes (which are just the closed intervals) we define the mignitude [12]

⟨x⟩ := min\{|x| | x ∈ x\} = \{ \begin{matrix}\underline{x} & if \underline{x} > 0, \\ −\overline{x} & if \overline{x} < 0, \\ 0 & otherwise. \end{matrix}

We also need the simple interval operations

α + βx = \{α + βx | x ∈ x\} = \{ \begin{matrix}[α + β\underline{x}, α + β\overline{x}] & if β ≥ 0, \\ [α + β\overline{x}, α + β\underline{x}] & if β ≤ 0. \end{matrix}

Using this interval notation, we introduce a box-valued function E on [u, v]×[0, ε̄] by

E : (x, ε) → E(x, ε) := F (x, ε) − [F_{l}, F_{u}], (7.2)

where we assume that (H_{ε}) is satisfied, and consider the following optimization problem in inclusion form,

\begin{aligned}min & f(x, ε) \\ s.t. & εw_{i} ∈ E_{i}(x, ε) (i = 1, …, m), \\ & x ∈ [u, v], ε = 0, \end{aligned} (7.3)

where again w ∈ ℝ^{m} is fixed. Clearly, this formulation is equivalent to the optimization problem (7.1). The usefulness of this particular formulation will become apparent when we look at the associated penalty function.

The penalty function is again defined by (2.3) with f(x, ε) in place of f(x), but now the constraint violation measure Δ(x, ε) is of the form

Δ(x, ε) := ∑_{i=1}^{m} Δ_{i}(x, ε) (7.4)

with

Δ_{i}(x, ε) := ⟨εw_{i} − E_{i}(x, ε)⟩^{2}, (7.5)

the squared distance of εw_{i} from the interval E_{i}(x, ε). Without loss of generality we assume that the constraints are inequality constraints for i = 1, …, r and equality constraints for i = r + 1, …, m, where 1 ≤ r ≤ m. Then

Δ_{i}(x, ε) = (εw_{i} − (F_{i}(x, ε) − F_{li}))^{2} for i = r + 1, …, m

16 Arnold Neumaier and Waltraud Huyer

and Δ_{i}(x, ε) = (εw_{i} − (F_{i}(x, ε) − y_{i}))^{2} for i = 1, …, r, (7.6) where

y_{i} = \{ \begin{matrix}F_{i}(x, ε) − εw_{i} & if F_{i}(x, ε) − εw_{i} ∈ [F_{li}, F_{ui}], \\ F_{li} & if F_{i}(x, ε) − εw_{i} < F_{li}, \\ F_{ui} & if F_{i}(x, ε) − εw_{i} > F_{ui}. \end{matrix} (7.7)

Moreover, Δ(x, ε) is continuously differentiable for ε > 0, with

\frac{∂}{∂x}Δ_{i}(x, ε) = −2(εw_{i} − F_{i}(x, ε) + y_{i})\frac{∂F_{i}}{∂x} (x, ε)

and

\frac{∂}{∂ε}Δ_{i}(x, ε) = 2(εw_{i} − F_{i}(x, ε) + y_{i})(w_{i} − \frac{∂F_{i}}{∂ε} (x, ε))

for i = 1, …, r.

We reduce this more general situation to the previous one with the aid of slack variables and use the abbreviations J := {1, …, r} and J′ := {r + 1, …, m}. By introducing the slack variables y_{i} := F_{i}(x, ε) for i = 1, …, r we obtain the problem

\begin{aligned}min & f(x, ε) \\ s.t. & x ∈ [u, v], y ∈ [F_{lJ}, F_{uJ}], ε = 0, \\ & F_{J}(x, ε) − y = εw_{J}, F_{J′}(x, ε) − F_{lJ′}(= F_{J′}(x, ε) − F_{uJ′}) = εw_{J′}, \end{aligned} (7.8)

which is of the form (5.1). The penalty function for this problem is given by

f̃_{σ}(x, y, ε) = \{ \begin{matrix}f(x) & for ε = Δ̃(x, y, ε) = 0, \\ f(x, ε) + \frac{1}{2ε} · \frac{Δ̃(x, y, ε)}{1 − qΔ̃(x, y, ε)} + σβ(ε) & for ε > 0, Δ̃(x, y, ε) < q^{−1}, \\ ∞ & otherwise, \end{matrix}

where

Δ̃(x, y, ε) = ∑_{i=1}^{r}(εw_{i} − (F_{i}(x, ε) − y_{i}))^{2} + ∑_{i=r+1}^{m}(εw_{i} − (F_{i}(x, ε) − F_{li}))^{2}.

Let Ẽ_{i}(x, y) := F_{i}(x)−y_{i}, i = 1, …, r, and Ẽ_{i}(x, y) := F_{i}(x)−F_{li}, i = r+1, …, m. Then

Ẽ′(x, y) = ( \begin{matrix}F′_{J}(x) & −I_{r} \\ F′_{J′}(x) & 0 \end{matrix} ) ,

and, for m ≤ n + r, Ẽ′(x, y) has full rank if and only if F′_{J′}(x) has full rank.

Lemma 7.1. Let (x, ε) ∈ [u, v] × [0, ε̄] with Δ(x, ε) < q^{−1}. Then

Δ(x, ε) = min_{y∈[F_{lJ} ,F_{uJ}]} Δ̃(x, y, ε) (7.9)

and thus

f_{σ}(x, ε) = min_{y∈[F_{lJ} ,F_{uJ}]} f̃_{σ}(x, y, ε).

Moreover, if (x, ε) is a Kuhn–Tucker point of f_{σ} then there exists a vector y ∈ [F_{lJ}, F_{uJ}] such that (x, y, ε) is a Kuhn–Tucker point of f̃_{σ}.

Proof. Let (x, ε) ∈ [u, v] × [0, ε̄] with Δ(x, ε) < q^{−1}, and let y be defined by (7.7). Then, for i = r + 1, …, m we have Δ_{i}(x, ε) = (εw_{i} − (F_{i}(x, ε) − F_{li}))^{2}, and Δ_{i}(x, ε) is given by (7.6) and (7.7) for i = 1, …, r, i.e., Δ(x, ε) = Δ̃(x, y, ε) for y defined by (7.7) and clearly (7.9) holds. Moreover, \frac{∂}{∂x}Δ(x, ε) = \frac{∂}{∂x} Δ̃(x, y, ε) and \frac{∂}{∂ε}Δ(x, ε) = Δ̃(x, y, ε). If (x, ε) is a Kuhn–Tucker point of f_{σ}, (x, y, ε) thus fulfils the Kuhn–Tucker conditions for x and ε, and due to the definition of y and the fact that

\frac{∂f̃_{σ}}{∂y_{i}} (x, y, ε) = \frac{1}{ε(1 − qΔ̃(x, y, ε))^{2}} (εw_{i} − F_{i}(x, ε) + y_{i})

it also satisfies the Kuhn–Tucker conditions with respect to y.

The Mangasarian–Fromovitz condition for this problem holds for (x, y) ∈ [u, v] × [F_{lJ}, F_{uJ}] if

F′_{J′}(x) has full rank, and there is a p ∈ ℝ^{n} with F′_{J′}(x)p = 0,

p_{i} \{ \begin{matrix}> 0 & if x_{i} = u_{i}, \\ < 0 & if x_{i} = v_{i}, \end{matrix}

(F′_{J}(x)p)_{i} \{ \begin{matrix}> 0 & if y_{i} = F_{li}, \\ < 0 & if y_{i} = F_{ui}. \end{matrix}

Let I := {i | u_{i} < x_{i}^{∗} < v_{i}} and J_{1} := {i ∈ J | F_{i}(x^{∗}, 0) = F_{il} or F_{i}(x^{∗}, 0) = F_{iu}}; without loss of generality I := {1, …, p}. Moreover, let E(x) := F (x, 0) − F (x^{∗}, 0), x ∈ D. Then (H_{F}) is replaced by (H_{E}) E is Lipschitz continuous in a neighborhood of x^{∗}, x^{∗} is a regular zero of E_{J′} :

D ⊆ ℝ^{n} → ℝ^{m−r}, and x_{I}^{∗} is a regular zero of G : D_{1} ⊆ ℝ^{p} → ℝ^{m−r+r_{1}}, r_{1} := |J_{1}|, defined by G(x̃) := E_{J_{1}∪J′}(x) with x_{i} := x̃_{i} for i = 1, …, p and x_{i} := x_{i}^{∗} for i = p + 1, …, n, where D_{1} is an appropriate open set containing [u_{I}, v_{I}].

Theorem 7.2. If the above Mangasarian–Fromovitz condition holds for all (x, y) ∈ [u, v] × [F_{lJ}, F_{uJ}] with

∑_{i=1}^{r}(F_{i}(x) − y_{i})^{2} + ∑_{i=r+1}^{m}(F_{i}(x) − F_{li})^{2} ≤ (q^{−1/2} + ε̄∥w∥)^{2},

the set of these (x, y) is bounded and (2.8) is satisfied, the conclusions of Theorem 2.1 hold for the smooth case of the penalty function defined in this section. Moreover, under the assumptions (H_{f}), (H_{E}), (H_{ε}) and (H_{β}) the conclusions of Theorem 5.3 are satisfied for the penalty function defined by (2.3) with f(x) replaced by f(x, ε) and Δ defined by (7.4) and (7.5).

Acknowledgment. The authors gratefully acknowledge partial support by the Austrian Fonds zur Förderung der wissenschaftlichen Forschung (FWF) under grant P11516-MAT.

REFERENCES

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

[2] F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983.

[3] A. R. Conn, N. I. M. Gould, and Ph. L. Toint, Methods for nonlinear constraints in optimization calculations, in The State of the Art in Numerical Analysis, I. S. Duff and G. A. Watson, eds., Clarendon Press, Oxford, 1997, pp. 363–390.

[4] Y. M. Ermoliev, A. V. Kryazhimskii, and A. Ruszczyńskii, Constraint aggregation principle in convex optimization, Math. Progamming, 76 (1997), pp. 353–372.

[5] K. Kiwiel, Proximity control in bundle methods for convex nondifferentiable minimization, Math. Programming, 46 (1990), pp. 105–122.

[6] A. V. Kuntsevich and F. Kappel, SolvOpt – The Solver for Local Nonlinear Optimization Problems (Version 1.1, Matlab, C, FORTRAN), University of Graz, Graz, 1997, WWW

document, http://www.uni-graz.at/imawww/kuntsevich/solvopt/.

[7] C. Lemaréchal, A. Nemirovskii, and Y. Nesterov, New variants of bundle methods, Math. Programming, 69 (1995), pp. 111–147.

[8] C. Lemaréchal and C. Sagastizábal, Variable metric bundle methods: From conceptual to implementable forms, Math. Programming, 76 (1997), pp. 393–410.

[9] , Practical aspects of the Moreau–Yosida regularization: Theoretical preliminaries, SIAM J. Optim., 7 (1997), pp. 367–385.

[10] C. Lemaréchal, J. J. Strodiot and A. Bihain, On a bundle method for nonsmooth optimization, in Nonlinear Programming 4, O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, eds., Academic Press, New York, 1981, pp. 245–282.

[11] O. L. Mangasarian and S. Fromovitz, The Fritz John necessary optimality conditions in the presence of equality and inequality constraints, J. Math. Anal. Appl., 17 (1967), pp. 37–47.

[12] A. Neumaier, Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, 1990.

[13] B. T. Polyak, A general method of solving extremum problems, Sov. Math., Dokl., 8 (1967), pp. 593–597 (transl. from Dokl. Akad. Nauk SSSR, 174 (1967), pp. 33–36).

[14] L. Qi and X. Chen, A preconditioning proximal Newton method for nondifferentiable convex optimization, Math. Programming, 76 (1997), pp. 411–429.

[15] D. F. Shanno and E. M. Simantiraki, Interior point methods for linear and nonlinear programming, in The State of the Art in Numerical Analysis, I. S. Duff and G. A. Watson, eds., Clarendon Press, Oxford, 1997, pp. 339–362.