Full text of DOI:10.1007/PL00013279

Struct Multidisc Optim 21, 322–326  Springer-Verlag 2001
Elimination of inequality constraints in convex optimization and
application to yield design
S. Turgeman and B. Guessab
Abstract The problem of convex optimization under in-
equality constraints is considered. It is established, using
Slater’s hypothesis only, that this problem is equivalent to
an unconstrained optimization problem, independent of
any penalization coefficient. Aconsequence of this result
concerns operational determination of an upper bound of
the exterior penalty coefficient, from which the conven-
tional exterior penalty function is exact. The optimiza-
tion methods developed find a particularly propitious
field of application in yield design. Numerical determin-
ation of the tensile strength of a bar with cuts illustrates
this point.
The literature relating to solving problem (1) is abun-
dant and highlights two major families of methods: pri-
mal methods, operating directly on (1), and dual methods
which associate a succession of unconstrained optimiza-
tion problems to (1). From this standpoint, the study
presented here leads to solving methods based on this sec-
ond family.
Afunction H of IRn in IR is first exhibited admitting
a global minimum on IRn equal to µ∗. This result is ob-
tained using Slater’s hypothesis only, which appears as
a minimum condition in convex optimization.
We know that this hypothesis is sufficient for the
penalty function
Key words convex constrained optimization, exact
penalty function, minimax optimization, yield design,
limit analysis
P(x) := f(x)+Kꢀg+(x)ꢀ ,
(2)
[where g+(x) ∈ IRm has as components gi+(x) =
max{gi(x), 0} (i = 1, . . . , m) and ꢀ·ꢀ is a norm of IRm]
to be exact, i.e. for its minimum to be equal to µ∗ for
K sufficiently great but finite (K ≥ K0 ≥ 0). Studies
concerning penalty functions associated to convex or non-
convex problems are numerous and their purpose is in
general to establish sufficient conditions ensuring this
exactitude property (Pietrzykowski 1969; Conn 1973;
Fletcher 1973; Bertsekas 1975; Han and Mangasarian
1979; Coleman and Conn 1980; Di Pillio and Grippo 1986,
for example). They do not, on the other hand, enable an
upper bound of K0 to be a priori determined.
1
Introduction
The optimization problem considered is
µ∗ = min f(x) ,
The function H unlike the function P does not depend
on any penalization coefficient. It does however present
the drawback of being nonconvex, which makes seeking
its global minimum problematic.
This difficulty is overcome by considering the func-
tion H = max{H, f} whose global minimum on IRn is
also equal to µ∗. The function H, although nonconvex,
presents the advantage of not presenting local minima
strictly greater than µ∗. Solving (1) by direct minimiza-
tion of H can therefore be envisaged.
gi(x) ≤ 0 , (i = 1, . . . , m) ,
(1)
where f and gi (i = 1, . . . , m) are convex functions of IRn
in IR.
This problem concerns in particular yield design,
a field of application chosen to test the methods of solu-
tion presented in this paper.
Received February 11, 2000
Revised manuscript received October 10, 2000
The second point of this study has the purpose of ob-
taining an operational upper bound of K0. The function
H is in fact expressed naturally in the form (2), with the
S. Turgeman and B. Guessab
Laboratoire Sols, Solides, Structures, B.P. 53 X, 38401 Greno-
ble, France
e-mail: Sylvain.Turgeman@ujf-grenoble.fr
Benaceur.Guessab@ujf-grenoble.fr
˜
difference that K is to be replaced by a function K(x) of
IRn in IR. It is then shown that knowing a lower bound of
µ∗ (which can be determined by minimization of P with

323
(6)
K fixed at a positive value, even low) enables an upper
bound K1 of K0 to be effectively computed.
Finally this study leads to two methods of solving (1):
However:
ꢂ
ꢂ
ꢂ
+
ꢂ
gˆ(u) ≤ g (u)
,
∀u ∈ IRn ,
p
where ꢀg+(u)ꢀp designates the p-norm of the vector
g+(u) ∈ IRm.
It results from (5) and (6) that
– either by a direct minimization of H;
– or by a minimization of P, K being governed by K1.
These methods find a particularly propitious field of
application in the static yield design (or limit analysis)
method.
Firstly, a sufficient condition related to the yield cri-
teria can in fact be specified for which Slater’s hypothesis
is satisfied. Secondly, a point x˜ can be exhibited, without
prior computation, such that gi(x˜) < 0 (i = 1, . . . , m).
This enables the function H to be explicited and (1) to be
solved by minimization of H.
Furthermore, in numerous practical yield design ap-
plications, a lower bound of µ∗ can be obtained by sim-
ple mechanical reasonings. This lower bound of µ∗ then
leads, without prior optimization, to an upper bound
of K0. This is the case in the example considered by
Andersen et al. (1998), consisting in determining the ten-
sile strength of a bar with cuts, where it is shown that
K simply has to be taken equal to 0.5 (whereas µ∗ is
about one) for the associated penalty function P(x) to be
exact.
ꢀ
ꢁ
λgˆ(x˜)+ꢀg+(u)ꢀp
λ+1
λx˜ +u
λ+1
gˆ
≤
,
(7)
We note
ꢃ
ꢀ
ꢁ
ꢄ
λx˜ +u
λ+1
ꢂ
G1 = (λ, u) ∈ IR+ ×IRn/gˆ
≤ 0
,
(8)
(9)
ꢅ
ꢆ
ꢂ
+
n
+
ꢂ
ꢂ
G2 = (λ, u) ∈ IR ×IR / g (u) p = −λgˆ(x˜)
,
According to (7), these sets are such that
G2 ⊂ G1 .
(10)
We then have, due to convexity of f and according to (10),
ꢀ
ꢁ
λx˜ +u
λ+1
λf(x˜)+f(u)
(λ,u)∈G
λ+1
1
µ∗ = min
f
≤
min
≤
(λ,u)∈G
1
Numerical solution of this mechanical problem en-
ables a comparison of the performances of the methods of
solution presented.
λf(x˜)+f(u)
λ+1
min
.
(11)
(λ,u)∈G
2
Taking account of the definition of G2 [cf. (9)], the
variable λ can be eliminated in (11), whence
2
µ∗ ≤ min H(u) ,
(12)
n
u∈IR
Elimination of the inequality constraints in convex
optimization
with H the function of IRn in IR defined by
f(x˜) ꢀg+(u)ꢀp −gˆ(x˜)f(u)
The problem (1) is considered and the following is noted:
H(u) :=
.
(13)
ꢀg+(u)ꢀp −gˆ(x˜)
– gˆ(x) the convex function of IRn in IR defined by:
As H(x∗) = µ∗, it then follows:
gˆ(x) := max gi(x) ,
(3)
(4)
i=1,... ,m
Proposition 1. The function H(u) defined in (13) ad-
mits a global minimum on IRn equal to µ∗.
– G the domain of the possible solutions:
G = {x ∈ IRn such that gˆ(x) ≤ 0} .
It is clear that the function H is not convex which
makes µ∗ difficult to obtain by minimization of H. To
overcome this difficulty, we consider the function H of IRn
in IR defined by
It is assumed that:
ꢇ
H(u) if f(u) ≤ f(x˜) ,
A1: the problem (1) admits a solution µ∗ achieved in
x∗ ∈ G,
H(u) := max[H(u), f(u)] =
f(u)
if not.
(14)
A2: (Slater’s hypothesis): x˜ exists such that gˆ(x˜) < 0.
For any (λ, u) ∈ IR+ ×IRn we have:
Proposition 2. The function H defined in (14) admits
a global minimum on IRn equal to µ∗ and does not admit
local minima strictly greater than µ∗.
ꢀ
ꢁ
λx˜ +u
λ+1
λgˆ(x˜)+gˆ(u)
λ+1
gˆ
≤
,
(5)
Proof. It can be assumed, without any loss of generality,
that f(x˜) = 0 and that gˆ(x˜) = −1.
due to the convexity of gˆ.

324
The function H is then such that
3
Exact penalty function
ꢇ
f(u)
H(u) =
f(u)
if f(u) ≤ 0 ,
if not .
+
g
(u) +1
ꢀ
ꢀp
H(u) =
(15)
The function H defined in (13) enables the function
P(x) := f(x)+Kꢀg+(x)ꢀp to be proved to be exact for
K ≥ K0 ≥ 0 and above all an operational upper bound of
K0 to be obtained. The function H can in fact be written
in the form
It obviously admits a global minimum on IRn equal
to µ∗ as it is greater than the function H and we have
H(x∗) = µ∗.
Let us assume that H admits in u˜ ∈ IRn a local min-
imum H(u˜) strictly greater than µ∗. Aneighbourhood
V (u˜) of u˜ therefore exists such that
+
˜
H(u) := f(u)+K(u)ꢀg (u)ꢀp ,
(19)
n
˜
with K, a function of IR in IR defined by
f(x˜)−f(u)
ꢀg+(u)ꢀp −gˆ(x˜)
H(u) ≥ H(u˜) , ∀u ∈ V (u˜) .
(16)
˜
K(u) :=
.
(20)
If f(u˜) > 0, (16) implies, taking account of the defin-
ition of H [cf. (15)]:
We obviously have, for any strict µ1 lower bound of µ∗:
ꢅ
ꢆ
+
µ∗ = min max[f(u), µ1]+K(u)ꢀg (u)ꢀp
.
(21)
˜
f(u) ≥ f(u˜) , ∀u ∈ V ꢀ(u˜) ,
(17)
n
u∈IR
Consequently, for any u ∈ F1 = {u ∈ IRn / f(u) ≥ µ1}, we
have
where V ꢀ(u˜) is a neighborhood of u˜.
This means that f admits in u˜ a local minimum
f(u˜) > µ∗ (since µ∗ ≤ 0), which is impossible due to the
convexity of f.
The assumption f(u˜) > 0 is therefore absurd and we
necessarily have f(u˜) ≤ 0, whence H(u˜) = H(u˜).
The points u˜ and x∗ both belong to the convex domain
F0 = {x ∈ IRn/f(x) ≤ 0}. A point u0 ∈]u˜, x∗]∩V (u˜)∩F0
consequently exists. This point u0 can be written as
µ∗ ≤ f(u)+K1ꢀg+(u)ꢀp ,
(22)
(23)
with
f(x˜)−µ1
K1 =
,
−gˆ(x˜)
˜
due to the fact that K1 ≥ maxu∈F1 K(u).
Let us assume that:
u˜ +λx∗
u0 =
,
λ > 0 .
(18)
∃u ∈ IRn
λ+1
It is such that
H(u0) ≥ H(u˜)
due to (16) and to the fact that u0 ∈ V (u˜),
H(u0) ≥ H(u˜)
due to the fact that u0 ∈ F0 and to (15),
such that
f(u)+K1ꢀg+(u)ꢀp < µ∗ .
(24)
We must have, according to (22), f(u) < µ1. The func-
tion f, continuous on the segment [u, x∗], takes any in-
termediate value between f(u) and f(x∗) = µ1 at at least
one point of this segment. As f(u) < µ1 < µ∗, u1 ∈]u, x∗[
therefore exists such that f(u1) = µ1. The point u1 =
αx∗ +(1−α)u can be written with α ∈]0, 1[. As u1 ∈ F1,
the inequality (22) holds in u1 and is written, due to the
convexity of f(u) and of ꢀg+(u)ꢀp, as
⇔
f(u˜)+λµ∗
f(u˜)
ꢀg+(u˜0)ꢀp +1
ꢈ
⇒
≥
(λ+1) ꢀg+(u0)ꢀp +1
ꢉ
The second member of (25) is however strictly smaller
ꢊ
µ∗ ≤ αf(x∗)+(1−α) f(u)+K1ꢀg+(u)ꢀp
.
(25)
due to the convexity of f and (18),
than µ∗, on account of (24).
The assumption (24) is therefore absurd and conse-
quently
f(u˜)+λµ∗
ꢀg+(u˜)ꢀp +λ+1 ꢀg+(u˜0)ꢀp +1
f(u˜)
⇒
≥
P(u) ≥ µ∗ , ∀u ∈ IRn , ∀K ≥ K1 .
Noting that P(x∗) = µ∗ for any K we have
µ∗ = min P(u) , ∀K ≥ K1 .
(26)
due to the convexity of ꢀg+(u)ꢀp and (18),
µ∗ ≥ H(u˜) ,
which is in contradiction with the assumption H(u˜) > µ∗.
⇔
(27)
n
u∈IR

325
Finally, by making µ1 tend to µ∗, the following result is
obtained:
this problem complies with Slater’s hypothesis as the con-
straints gi(x) of (1) are strictly satisfied for
x˜ = 0 ∈ IRn ,
(30)
Proposition 3. The penalty function P(u) is exact for
any K ≥ K0 with K0 = [f(x˜)−µ∗]/[−gˆ(x˜)].
and we have in addition f(x˜) = 0 whence [cf. (14)]
It should be emphasized that any lower bound µ1 of
µ∗ provides an upper bound K1 of K0, with K1 defined
in (23).
ꢃ
ꢄ
−gˆ(0)f(u)
ꢀg+(u)ꢀp −gˆ(0)
µ∗ = min max
, f(u)
.
(31)
n
u∈IR
This result justifies the following algorithm where (1)
is solved by minimization of P(u) with K governed by the
expression (23):
Let us note that the sufficient condition (29) is often sat-
isfied. This is the case when the constituent materials
comply for example with von Mises, Tresca or Coulomb
(with nonzero cohesion) criteria. Furthermore, for nu-
merous mechanical problems, an upper bound λ1 of λ∗
(i.e. a lower bound −λ1 of µ∗) can be obtained by simple
mechanical reasonings. This results, if (29) holds, in an
immediate upper bound K1 = −λ1/gˆ(0) of K0 [cf. (23)].
As an example, let us consider the plane strain test
problem, illustrated in Fig. 1 and described by Andersen
et al. (1998): uniform tensile strength of a bar with exter-
nal symmetric cuts.
1. We note K = K1 ≥ 0; α a real number different from 1.
2. We solve P(x1) = min P(x).
n
x∈IR
3. If ꢀg+(x1)ꢀp = 0 or if α = 1 then f(x1) = µ∗; if not,
we note K1 = [f(x˜)−f(x1)]/[−αgˆ(x˜)] with α ≥ 1 such
that K1 > K and we go back to step 2.
The role of the parameter α is to limit a variation of K
which may be too large from one iteration to the other.
4
Application to yield design
Solving problem (1) by minimization of H(u) or of P(u)
(cf. Sect. 3) requires a point x˜ to be previously deter-
mined such that gˆ(x˜) < 0. This point x˜ can be obtained
by solving the unconstrained discrete minimax problem
(Turgeman and Guessab 1999):
gˆ(x˜) = min max gi(x) =
n
x∈IR i=1,... ,m
ꢅ
ꢆ
ꢂ
ꢂ
ꢂ
+
ꢂ
min
η + [g(x)−η]
.
(28)
p
n
(η,x)∈IR×IR
Problem (28) can be interrupted as soon as the function
gˆ becomes strictly negative. We can also choose among
the iterates xk such as gˆ(xk) < 0 the one which minimizes
K1 [cf. (23)] if a lower bound µ1 of µ∗ is known. However,
for convex optimization problems arising from static for-
mulation of yield design (Salen¸con 1983) or limit analysis,
such a point x˜ can be exhibited without computation for
a large class of materials.
Fig. 1 Test problem: uniform tensile strength of a bar with
symmetric cuts (a = L/3)
ˆ
Let Ω be a mechanical system constituted by k mate-
rials characterized by strength convex criteria grk(σ) ≤ 0
ˆ
(k = 1, . . . , k), with σ the stress tensor. As this system
The bar is formed by a von Mises material of limit
shear strength c, i.e.
is subjected to a loading mode dependent on p parame-
ters, the extreme loading λ∗Q0 (λ∗ ≥ 0) in a fixed direc-
tion Q0 (Q0 ∈ IRp) is sought for. Numerical formulation
of the static yield design method by finite elements con-
sists in maximizing λ (and therefore in minimizing −λ)
with equality linear constraints (which result from static
admissibility) and convex inequality constraints (which
result from strength conditions). Elimination of the linear
constraints leads to solving of a problem of the form (1)
with µ∗ = −λ∗. If the strength criteria are such that
ꢀ
ꢁ
2
ꢈ
2
σtt −σvv
σtv
c
gr(σ) =
+4
−4 .
c
The loading parameter λ can be defined in adimensional
σ
manner by λ = tt . The extreme loading sought for λ∗ is
c
lower than the extreme loading λ1 of a bar without cuts.
As λ1 is known and equal to 2 and (29) holds (with in
addition gˆ(0) = −4), we have K1 = 0.5, whence
ꢉ
ꢊ
µ∗ = min f(u)+0.5ꢀg+(u)ꢀp
.
(32)
ˆ
grk(0) < 0 , k = 1, . . . , k ,
(29)
n
u∈IR

326
This example is not atypical. For a large number of
constituent materials of the mechanical system consid-
ered, a point x˜ can in fact be exhibited without compu-
tation. This condition, although it is not general, is very
often achieved. Moreover, simple mechanical reasonings
are sufficient, for a large number of problems, to deter-
mine lower bounds of µ∗ and subsequently to explicit
exact penalty functions (without having to perform iter-
ative computation of the penalty coefficient).
The example of determination of the tensile strength
of a bar with cuts is an illustration of this. For this prob-
lem, K simply has to be fixed at 0.5 for P to be exact.
Minimization of the functions H and P leads to identical
results the precision of which can be estimated by com-
parison with those of the literature resulting from a kine-
matic approach.
mechanical problems (in particular plasticity homoge-
nization problems), simple reasonings can lead to deter-
mination of an operational upper bound of K0 as in (32).
Problems (31) and (32) corresponding to a division
into triangular finite elements of the quarter OABC of the
volume V of the bar are solved, on account of the mate-
rial and loading symmetries. For a mesh with 5184 finite
elements the number of variables of problems (31) and
(32) is equal to 1214 (the stress fields considered are con-
stant on each finite element and discontinuous between
two adjacent finite elements). The corresponding approx-
imation λ∗− of λ∗ obtained is: λ∗− = 1.3790 for problem
(31); λ∗− = 1.3789 for problem (32). By Andersen and
Christiansen (1998), a computation of λ∗ is performed
using the kinematic limit analysis method which gives an
upper bound λ∗+ = 1.3894 of λ∗.
Problems (31) and (32) lead to very close λ∗− values
(which is not surprising) with however a large number of
iterations for (32). Comparison between the values λ∗−
and λ∗+ leads one to think that the optimization methods
developed, which present the advantage of simplicity, are
efficient at least for the type of problems considered.
References
Andersen, K.D. et al. 1998: Minimizing a sum of norms sub-
ject to linear equality constraints. Comput. Optimiz. Appl. 11,
65–79
Andersen, K.D. et al. 1998: Computing limit loads by mini-
mizing a sum of norms. SIAM J. Sci. Comput. 19, 1046–1062
5
Bertsekas, D.P. 1975: Necessary and sufficient conditions for
a penalty method to be exact. Math. Prog. 9, 87–99
Conclusions
Coleman, T.F.; Conn, A.R. 1980: Second-order conditions for
an exact penalty functions. Math. Prog. 19, 178–185
It has been shown that, using Slater’s hypothesis only,
the solution µ∗ of problem (1) is the unconstrained global
minimum of a function H or of a function H = max(H, f).
The functions H and H are independent of any penal-
ization coefficient and totally explicited when a point x˜
strictly verifying the inequality constraints of problem (1)
is known.
Conn, R. 1973: Constrained optimization using a nondifferen-
tiable penalty function. SIAM J. Numer. Anal. 10, 760–784
Di Pillio, G.; Grippo, L. 1986: An exact penalty function
method with global convergence properties for nonlinear pro-
gramming problems. Math. Prog. 36, 1–18
The function H presents the property of not admit-
ting local minima strictly greater than µ∗. This property
enables its global minimum to be effectively computed.
The function H enables an upper bound K1 of K0 to
be determined, a value starting from which the exterior
penalty function P is exact. The upper bound K1 can ef-
fectively be computed when x˜ and a lower bound µ1 of µ∗
are known.
Fletcher, R. 1973: An exact penalty function for nonlinear
programming with inequalities. Math. Prog. 5, 129–150
Han, S.P.; Mangasarian, O.L. 1979: Exact penalty functions
in nonlinear programming. Math. Prog. 17, 251–269
Pietrzykowski, T. 1969: An exact potential method for con-
strained maxima. SIAM J. Numer. Anal. 6, 269–304
Salenc¸on, J. 1983: Calcul ´a la rupture et analyse limite. Paris:
Presses de l’Ecole Nationale des Ponts et Chauss´ees
We therefore have two methods available for solving
(1) by minimization of H or of P with K governed by K1.
These methods find a particularly propitious field of
application in the static yield design method. If the zero
stress tensor strictly verifies the strength conditions of the
Turgeman, S.; Guessab, B. 1999: Unconstrained discret inf-
max problem solving applied to yield design. Struct. Optim.
18, 247–255