Proximal Minimization Methods with Generalized Bregman Functions.
We consider methods for minimizing a convex function f that generate a sequence {xk} by taking xk+1 to be an approximate minimizer of f(x)+Dh(x,xk)/ck, where ck > 0 and Dh is the D-function of a Bregman function h.  Extensions are made to B-functions that generalize Bregman functions and cover more applications.  Convergence is established under criteria amenable to implementation.  Applications are made to nonquadratic multiplier methods for nonlinear programs.
Introduction
We consider the convex minimization problem
is a closed proper convex function and X is a nonempty closed
convex set in IR n . One method for solving (1.1) is the proximal point algorithm (PPA)
[Mar70, Roc76b] which generates a sequence
starting from any point x is the Euclidean norm and fc k g is a sequence
of positive numbers. The convergence and applications of the PPA are discussed, e.g., in
[Aus86, CoL93, EcB92, GoT89, G-ul91, Lem89, Roc76a, Roc76b].
Several proposals have been made for replacing the quadratic term in (1.2) with other
distance-like functions [BeT94, CeZ92, ChT93, Eck93, Egg90, Ius95, IuT93, Teb92, TsB93].
In [CeZ92], (1.2) is replaced by
Research supported by the State Committee for Scientific Research under Grant 8S50502206.
Systems Research Institute, Newelska 6, 01-447 Warsaw, Poland (kiwiel@ibspan.waw.pl)
where D h (x; is the D-function of a Bregman function
h [Bre67, CeL81], which is continuous, strictly convex and differentiable in the interior of
its domain (see x2 for a full definition); here h\Delta; \Deltai is the usual inner product and rh is
the gradient of h. Accordingly, this is called Bregman proximal minimization (BPM). The
convergence of the BPM method is discussed in [CeZ92, ChT93, Eck93, Ius95, TsB93], a
generalization for finding zeros of monotone operators is given in [Eck93], and applications
to convex programming are presented in [Cha94, Eck93, Ius95, NiZ92, NiZ93a, NiZ93b,
This paper discusses convergence of the BPM method using the B-functions of [Kiw94]
that generalize Bregman functions, being possibly nondifferentiable and infinite on the
boundary of their domains (cf. x2). Then (1.3) involves D k
, where fl k is a subgradient of h at x k . We establish for the first time convergence
of versions of the BPM method that relax the requirement for exact minimization
in (1.3). (The alternative approach of [Fl-a94], being restricted to Bregman functions with
Lipschitz continuous gradients, cannot handle the applications of xx7-9.) We note that in
several important applications, strictly convex problems of the form (1.3) may be solved
by dual ascent methods; cf. references in [Kiw94, Tse90].
The application of the BPM method to the dual functional of a convex program yields
nonquadratic multiplier methods [Eck93, Teb92]. By allowing h to have singularities, we
extend this class of methods to include, e.g., shifted Frish and Carroll barrier function
methods [FiM68]. We show that our criteria for inexact minimization can be implemented
similarly as in the nonquadratic multiplier methods of [Ber82, Chap. 5]. Our convergence
results extend those in [Eck93, TsB93] to quite general shifted penalty functions, including
twice continuously differentiable ones.
We add that the continuing interest in nonquadratic modified Lagrangians stems from
the fact that, in contrast with the quadratic one, they are twice continuously differentiable,
and this facilitates their minimization [Ber82, BTYZ92, BrS93, BrS94, CGT92, CGT94,
GoT89, IST94, JeP94, Kiw96, NPS94, Pol92, PoT94, Teb92, TsB93]. By the way, our
convergence results seem stronger than ones in [IST94, PoT94] for modified barrier func-
tions, resulting from a dual application of (1.3) with D k
replaced by an entropy-like
OE-divergence.
The paper is organized as follows. In x2 we recall the definitions of B-functions and
Bregman functions and state their elementary properties. In x3 we present an inexact
BPM method. Its global convergence under various conditions is established in xx4-5.
In x6 we show that the exact BPM method converges finitely when (1.1) enjoys a sharp
minimum property. Applications to multiplier methods are given in x7. Convergence of
general multiplier methods is studied in x8, while x9 focuses on two classes of shifted
penalty methods. Additional aspects of multiplier methods are discussed in x10. The
Appendix contains proofs of certain technical results.
Our notation and terminology mostly follow [Roc70]. IR m
? are the nonnegative
and positive orthants of IR m respectively. For any set C in IR n , cl C, -
ri C and bd C
denote the closure, interior, relative interior and boundary of C respectively. ffi C is the
indicator function of C (ffi C xi is the
support function of C. For any closed proper convex function f on IR n and x in its effective
domain is the ffl-
subdifferential of f at x for each ffl - 0, is the ordinary subdifferential of f
at x and f 0 denotes the derivative of f in any direction
. By [Roc70, Thms 23.1-23.2], f 0 (x; d) - \Gammaf 0 (x; \Gammad) and
The domain and range of @f are denoted by C @f and im@f respectively. By [Roc70, Thm
ri C f ae C @f ae C f . f is called cofinite when its conjugate f
is real-valued. A proper convex function f is called essentially smooth if -
differentiable on -
C f . If f is closed
proper convex, its recession function f0
positively homogeneous [Roc70, Thm 8.5].
B-functions
We first recall the definitions of B-functions [Kiw94] and of Bregman functions [CeL81].
For any convex function h on IR n , we define its difference functions
By convexity (cf. (1.4)), h(x) - h(y)
h and D ]
h generalize the usual D-function of h [Bre67, CeL81], defined by
since
Definition 2.1. A closed proper (possibly nondifferentiable) convex function h is called
a B-function (generalized Bregman function) if
(a) h is strictly convex on C h .
(b) h is continuous on C h .
(c) For every ff 2 IR and x 2 C h , the set L 1
(d) For every ff 2 IR and x 2 C h , if fy k g ae L 1
h (x; ff) is a convergent sequence with limit
Definition 2.2. Let S be a nonempty open convex set in IR n . Then
cl S, is called a Bregman function with zone S, denoted by h 2 B(S), if
(i) h is continuously differentiable on S.
(ii) h is strictly convex on -
S.
(iii) h is continuous on -
S.
(iv) For every ff 2 IR, ~
S, the sets L 2
fy are bounded.
(v) If fy k g ae S is a convergent sequence with limit y   , then D h (y
(vi) If fy k g ae S converges to y   , fx k g ae -
S is bounded and D h
(Note that the extension e of h to IR n , defined by
is a B-function with C
ri C
e (\Delta;
e (\Delta;
h and D ]
h are used like distances, because for
and D [
strict convexity. Definition 2.2 (due
to [CeL81]), which requires that h be finite-valued on -
S, does not cover Burg's entropy
[CDPI91]. Our Definition 2.1 captures features of h essential for algorithmic purposes. As
shown in [Kiw94], condition (b) implies (c) if h is cofinite. Sometimes one may verify the
following stronger version of condition (d)
C @h oe fy k
by using the following three lemmas proven in [Kiw94].
Lemma 2.3. (a) Let h be a closed proper convex function on IR n , and let S 6= ; be a
compact subset of ri C h . Then there exists ff 2 IR s.t. joe @h(y)
(b) Let is the indicator function of a convex polyhedral set S 6= ; in IR n .
Then h satisfies condition (2.5).
(c) Let h be a proper polyhedral convex function on IR n . Then h satisfies condition (2.5).
(d) Let h be a closed proper convex function on IR. Then h is continuous on C h , and
fy k g ae C h .
Lemma 2.4. (a) Let
are closed proper convex functions
s.t. h are polyhedral and " j
condition (c) of Def. 2.1, then so does h. If condition (d) of Def.
2.1 or (2.5), then so does h. If h 1 is a B-function, h are continuous on C
and satisfy condition (d) of Def. 2.1, then h is a B-function. In particular, h
is a B-function if so are h
(b) Let h be B-functions s.t. " j
ri C h i 6= ;. Then
function.
(c) Let h 1 be a B-function and let h 2 be a closed proper convex function s.t. C h 1
ae ri C h 2
is a B-function.
(d) Let h closed proper strictly convex functions on IR s.t. L 1
(t; ff) is bounded
for any t; ff 2 IR,
Lemma 2.5. Let h be a proper convex function on IR. Then L 1
h (x; ff) is bounded for each
Lemma 2.6. (a) If / is a B-function on IR then /   is essentially smooth and C /
(b) If OE closed proper convex essentially smooth and C
C OE then OE
is a B-function with ri C OE   ae imrOE ae C OE   .
Proof. (a): This follows from Def. 2.1, Lem. 2.5 and [Roc70, Thm 26.3]. (b): By [Roc70,
Thms 23.4, 23.5 and 26.1], ri C OE   ae C @OE  strictly convex
on C @OE   , and hence on C OE   by an elementary argument. Since OE   is closed proper convex
and OE   Thm 12.2], the conclusion follows from Lems. 2.3(d) and 2.5.
Examples 2.7. Let
In each of the examples,
it can be verified that h is an essentially smooth B-function.
ff =ff. Then h
2.
ff =ff if
p. 106].
3 ('x log x'-entropy) [Bre67].
Kullback-Liebler entropy).
[Roc70, p. 105] and D h is the Kullback-Liebler entropy.
(1\Gammay 2
6 (Burg's entropy) [CDPI91].
3 The BPM method
We make the following standing assumptions about problem (1.1) and the algorithm.
Assumption 3.1. (i) f is a closed proper convex function.
(ii) X is a nonempty closed convex set.
(iii) h is a (possibly nonsmooth) B-function.
is the essential objective of (1.1).
is a sequence of positive numbers satisfying
is a sequence of nonnegative numbers satisfying lim l!1
Consider the following inexact BPM method. At iteration k - 1, having
find x k+1 , fl k+1 and p k+1 satisfying
We note that x k+1 - arg minffX +D k
with
by (2.1), (2.2), (3.2) and (3.3); in fact x k+1 is an ffl k -minimizer of
as shown after the following (well-known) technical result (cf. [Roc70, Thm 27.1]).
Lemma 3.2. A closed proper and strictly convex function OE on IR n has a unique minimizer
iff OE is inf-compact, i.e., the ff-level set L OE is bounded for any ff 2 IR,
and this holds iff L OE (ff) is nonempty and bounded for one ff 2 IR.
Proof. If x 2 Arg min OE then, by strict convexity of OE, L OE
is inf-compact (cf. [Roc70, Cor. 8.7.1]). If for some ff 2 IR, L OE (ff) 6= ; is bounded then it
is closed (cf. [Roc70, Thm 7.1]) and contains Arg min OE 6= ; because OE is closed.
Lemma 3.3. Under the above assumptions, we have:
(i) OE k is closed proper and strictly convex.
is cofinite. In particular, OE k is inf-compact if (fl ri C f
(v) If OE k is inf-compact and either ri C f X
ri C h 6= ;, or C f X
ri C h 6= ; and fX is
polyhedral, then there exist - x
if C @f X ae -
C h or C
essentially smooth.
(vi) The assumptions of (v) hold if either ri C f X
ae -
ae -
and
Proof. (i) Since f , ffi X and h are closed proper convex, so are
h (\Delta; x k )=c k (cf. [Roc70, Thm 9.3]), having nonempty domains C f " X, C h and
respectively (cf. Assumption 3.1(iv)). D k
are strictly convex, since
so is h (cf. Def. 2.1(a)).
(ii) For any x, add the inequality D k
(cf.
(3.3), (3.4)) divided by c k to fX (x) - fX
(cf. (3.6)) and use
(3.5) to get OE k (x) - OE k
(iii) By part (i),
closed proper strictly convex, and L / by
strict convexity of h (cf. Def. 2.1(a), (2.2) and (1.4)), so / is inf-compact (cf. Lem. 3.2).
(cf. (3.9)). The last set is bounded, since / is inf-compact, so OE k is inf-compact by part
(i) and Lem. 3.2.
~
closed proper and strictly convex (so is D k
cf. part (i)), and ~
Thm 23.8]). Hence ~
/ is inf-compact (cf. Lem. 3.2), and so is OE k , since OE k - ~
/ from
yi. To see that strict convexity of h (cf. Def. 2.1(a)) implies
C h   , we note that -
Thms 26.3 and 26.1], and @h
by [Roc70, Thm 23.5], so that C @h
is cofinite. The second assertion follows from ri C f
ae C @f
(v) By part (i) and Lem. 3.2, - x defined. The rest follows from
(cf. (3.8)), the fact due to
our assumptions on C f X
and ri C h (cf. [Roc70, Thm 23.8]), and [Roc70, Thm 26.1].
(vi) If inf is inf-compact by parts (iii)-(iv). If
ri
ri ri C ri C f X 6= ;, since C f X Assumption 3.1(iv)).
Remark 3.4. Lemma 3.3(v,vi) states conditions under which the exact BPM method
(with x
in (3.6)) is well defined. Our conditions are
slightly weaker than those in [Eck93, Thm 5], which correspond to ri C f X
ae -
cl
being finite, continuous and bounded below on X.
Example 3.5. Let
implies that -
x k+1 is well defined.
Example 3.6. Let
ri C f
ri C f   " -
const for c Although h is not a
Bregman function, this is a counterexample to [Teb92, Thm 3.1].
4 Convergence of the BPM method
We first derive a global convergence rate estimate for the BPM method. We follow the
analysis of [ChT93], which generalized that in [G-ul91]. Let s
Lemma 4.1. For all x 2 C h and k - l, we have
l
l
l
Proof. The equality in (4.1) follows from (3.3), and the inequality from
(cf. (3.5)) and p k+1 2 @ ffl k fX
since c k ? 0. (4.2) is a consequence of (4.1). Summing (4.1) over l we obtain
l
l
l
Use fX in (4.5) to get (4.3). (4.4) follows from (4.3)
and the fact D k
We shall need the following two results proven in [TsB91].
Lemma 4.2 ([TsB91, Lem. 1]). Let h : be a closed proper convex function
continuous on C h . Then:
(a) For any y 2 C h , there exists ffl ? 0 s.t. closed.
(b) For any y 2 C h and z s.t. y any sequences y k ! y and z k ! z s.t.
Lemma 4.3. Let h : be a closed proper convex function continuous on
C h . If fy k g ae C h is a bounded sequence s.t., for some y 2 C h , fh(y k
bounded from below, then fh(y k )g is bounded and any limit point of fy k g is in C h .
Proof. Use the final paragraph of the proof of [TsB91, Lem. 2].
Lemmas 4.2-4.3 could be expressed in terms of the following analogue of (2.1)
Lemma 4.4. Let h : be a closed proper strictly convex function continuous
on C h . If y   2 C h and fy k g is a bounded sequence in C h s.t. D 0
Proof. Let y 1 be the limit of a subsequence fy k g k2K . Since h(y k
h(y
by Lem. 4.3 and h(y k ) K
\Gamma! h(y 1 ) by continuity of h
on C h . Then by Lem. 4.2(b),
yields strict convexity of h. Hence
By (1.4), (3.2), (3.3), (2.2) and (4.6), for all k
Lemma 4.5. If
is bounded and fx k g ae L 1
(ii) Every limit point of fx k g is in C h .
converges to some x
Proof. (i) We have D l
ae C @h (cf. (3.1)), so fx k g ae L 1
h (x; ff), a bounded set (cf. Def. 2.1(c)).
(4.6), (4.7)), so the desired conclusion follows from continuity of h on C h (cf. Def. 2.1(b)),
being bounded in C h (cf. (3.1) and part (i)) and Lem. 4.3.
(iii) By parts (i)-(ii), a subsequence fx l j g converges to some x
But fX and fX is
closed (cf. Assumption 3.1(i,ii)). Hence for l ? l j , D l
(cf. (4.2)) with
Finally, if x does
not converge, it has a limit point x 0 6= x 1 (cf. parts (i)-(ii)), and replacing x and x 1 by
respectively in the preceding argument yields a contradiction.
We may now prove our main result for the inexact BPM descent method (3.1)-(3.7).
Theorem 4.6. Suppose Assumption 3.1(i-ii,iv-v) holds with h closed proper convex.
(a) If lim l!1
Hence
ae C h . If ri C h " ri C f X
cl C h fX . If ri C f X
ae cl C h (e.g., C @f X
ae cl C h ) then
cl C h oe cl C f X
and Arg min X f ae cl C h .
(b) If h is a B-function, fX
fX is
nonempty then fx k g converges to some x
(c) If fX
Proof. (a) For any x 2 C h , taking the limit in (4.4) yields lim l!1 fX using
Assumption 3.1(v)) and
Hence fX
7.3.2]). If ri C h "
ri
(cf. [Roc70, Thm 6.5]) and inf C h cl C h fX , so
cl C h fX . If ri C f X
ae cl C h then cl C f X
ae cl C h (cf. [Roc70, Thm 6.5]).
(b) If x 2 X   then fX
(c) If jx k j 6! 1, fx k g has a limit point x with fX (x) - inf C h fX / fX
closed; cf. Assumption 3.1(i,ii)), so C f
Remark 4.7. For the exact BPM method (with ffl k j 0), Thm 4.6(a,b) subsumes [ChT93,
Thm 3.4], which assumes ri C f X
ae -
C h and C cl C h . Thm 4.6(b,c) strengthens [Eck93,
Thm 5], which only shows that fx k g is unbounded if cl C f X
ae -
and Lem. 3.3 subsume [Ius95, Thm 4.1], which assumes that h is essentially smooth, f is
continuous on C f ,
cl C h , Arg min X f
For choosing fffl k g (cf. Assumption 3.1(vi)), one may use the following simple result.
Lemma 4.8. (i) If ffl k ! 0 then
(ii) If
Proof. (i) For any ffl ? 0, pick - k and - l ? - k s.t. ffl k - ffl for all k - k and
for all l - l; then
(ii) We have
5 Convergence of a nondescent BPM method
In certain applications (cf. x7) it may be difficult to satisfy the descent requirement (3.7).
Hence we now consider a nondescent BPM method, in which (3.7) is replaced by
By Lem. 3.3(ii), (5.1) holds automatically, since it means OE k
Lemma 5.1. For all x 2 C h and k - l, we have
l
l
l
Proof. (4.1)-(4.2) still hold. (5.2) follows from D k
. Multiplying this inequality by s
and summing over
l
l
l
s
Subtract (5.5) from (4.5) and rearrange, using s to get (5.3). (5.4) follows
from (5.3) and the fact D k
Theorem 5.2. Suppose Assumption 3.1(i-ii,iv-v) holds with h closed proper convex.
(a) If
5.3 for sufficient conditions), then fX
Hence the assertions of Theorem 4.6(a) hold.
(b) If h is a B-function, fX
fX is
nonempty then fx k g converges to some x
ae C h .
(c) If fX
ae C h and X
Proof. (a) The upper limit in (5.4) for any x 2 C h yields lim sup l!1 fX
using
(b) If x 2 X   then fX Assertions
(i)-(iii) of Lem. 4.5 still hold, since the proofs of (i)-(ii) remain valid, whereas in the proof
of (iii) we have x
and fX
(c) Use the proof of Thm 4.6(c).
Lemma 5.3. (i) Let fff k g, ffi k g and f" k g be sequences in IR s.t. 0 - ff
(ii) If
Proof. (i) See, e.g., [Pol83, Lem. 2.2.3].
(ii) Use part (i) with ff l =
(iii) Use part (ii) with c l =s l 2 [c min =lc
6 Finite termination for sharp minima
We now extend to the exact BPM method the finite convergence property of the PPA in
the case of sharp minima (cf. [Fer91, Roc76b] and [BuF93]).
Theorem 6.1. Let f have a sharp minimum on X, i.e., X  there
exists
x. Consider the exact BPM
method applied to (1.1) with a B-function h s.t. C f X
ae Crh , ffl k j 0 and inf k c k ? 0. Then
there exists k s.t.
Proof. By Thm 4.6, x
continuity of rh on Crh [Roc70, Thm 25.5]) and @fX
(cf. (3.5)-(3.6)). But if
for
Hence for some k, jp
We note that piecewise linear programs have sharp minima, if any (cf. [Ber82, x5.4]).
7 Inexact multiplier methods
Following [Eck93, Teb92], this section considers the application of the BPM method to
dual formulations of convex programs of the form presented in [Roc70, x28]:
minimize f(x); subject to g i (x) - 0;
under the following
Assumption 7.1. f , are closed proper convex functions on IR n with C f ae
and ri C f ae
ri C g i
Letting we define the Lagrangian of (7.1)
and the dual functional
. Assume that
-. The dual problem to (7.1) is to maximize d, or equivalently to
minimize q(-) over - 0, where \Gammad is a closed proper convex function. We will apply
the BPM method to this problem, using some B-function h on IR m .
We assume that IR m
is a B-function (cf. Lem. 2.4(a)). The
monotone conjugate of h (cf. [Roc70, p. 111]) defined by h
nondecreasing (i.e., h coincides
with the convex conjugate h
of h+ , since h
(\Delta). We need
the following variation on [Eck93, Lem. A3]. Its proof is given in the Appendix.
Lemma 7.2. If h is a closed proper essentially strictly convex function on IR m with
ri C h 6= ;, then h + is closed proper convex and essentially smooth, @h
all is continuous on C @h
where I is the identity operator and N IR m
is the normal cone operator of IR m
i.e.,
additionally
im@h oe IR m
? then h+ is cofinite, C continuously differentiable.
, to find inf 0 q(-) via the BPM method we replace in (3.1)-
our inexact multiplier method requires finding - k+1 and x k+1 s.t.
with
for some p k+1 and fl k+1 . Note that (7.2) implies
since
\Delta; g(x k+1 )
\Gammag(x
and
(7.6), (7.4)-(7.5) hold if we take p
since then
Using (7.3) and (@h+ (Lem. 7.2), we have
so we may take ~ fl choices will be discussed later.
Further insight may be gained as follows. Rewrite (7.3) as
where
Let
cf. Assumption 7.1), L k
Lemma 7.3. Suppose inf C f
e.g., the feasible set C
of (7.1) is nonempty. Then L k is a proper convex function and
If -
(g(-x)). The preceding assertions
hold when inf C f
(cf. Lem. 7.2).
Proof. Using
? and ~
u. Then, since P k is nondecreasing (so is
ri C f ae
ri C g i (cf. Assumption 7.1), Lem. A.1 in the Appendix yields im@P k ae IR m
and
(7.13), using @P (cf. Lem. 7.2). Hence if @L k (x)
so ri C f ae
ri C g i
implies (cf. [Roc70, Thm 23.8]) @ x L(x;
-). Finally, when C then for any ~ x 2 C f we may pick ~
with
u, since C f ae
(Assumption 7.1) and C
The exact multiplier method of [Eck93, Thm 7] takes x
assuming h is smooth, -
? and imrh oe IR m
? . Then (7.2) holds with
Our inexact method only requires that x k+1 ~
in the
sense that (7.2) holds for a given ffl k - 0. Thus we have derived the following
Algorithm 7.4. At iteration k - 1, having
ae
oe
s.t. (7.2) holds, choose fl k+1 satisfying (7.7) and set p
To find x k+1 as in [Ber82, x5.3], suppose f is strongly convex, i.e., for some - ff ? 0
Adding subgradient inequalities of g i , using (7.14) yields for all x
7.3). Minimization in (7.16) yields
so (7.2) holds if
Thus, as in the multiplier methods of [Ber82, x5.3], one may use any algorithm for minimizing
L k that generates a sequence fz j g such that lim inf j!1 setting
ff is unknown, it may be replaced in (7.18) by any fixed
ff ? 0; this only scales fffl k g.) Of course, the strong convexity assumption is not necessary
if one can employ the direct criterion (7.2), i.e., L(z
(cf. (7.10)), where d(-) may be computed with an error that can be absorbed in ffl k .
Some examples are now in order.
Example 7.5. Suppose
are B-functions on IR with C h i
oe
2.4(d)). For each i, let -
so that (cf. [Eck93, Ex. 6]) h
Using (7.9) and "maximal" fl k+1 in (7.7), Alg. 7.4 may be written as
Remark 7.6. To justify (7.19c), note that if we had
would
not penalize constraint violations
An ordinary penalty method
(cf. [Ber82, p. 354]) would use (7.19a,b) with
u and c k " 1. Thus (7.19) is a shifted
penalty method, in which the shifts fl k should ensure convergence even for sup k c k ! 1,
thus avoiding the ill-conditioning of ordinary penalty methods.
Example 7.7. Suppose C @h "
, so that
from IR m
(cf. [Roc70, Thms 23.8 and 25.1]). Then we may use since the
maximal shift due to (7.9). Thus Alg. 7.4 becomes
ae
oe
In the separable case of Ex. 7.5, the formulae specialize to
Example 7.8. Let
a B-function on IR with Cr/ oe IR ? .
Using (7.7) and (7.9) as in Ex.
7.5, we may let fl k+1
m. Thus Alg. 7.4 becomes
Example 7.9. For
becomes
Even if f and all g i are smooth, for the objective of (7.21a) is, in general, only
once continuously differentiable. This is a well-known drawback of quadratic augmented
Lagrangians (cf. [Ber82, TsB93]). However, for we obtain a cubic multiplier method
[Kiw96] with a twice continuously differentiable objective.
Example 7.10 ([Eck93, Ex. 7]). For reduces to
i.e., to an inexact exponential multiplier method (cf. [Ber82, x5.1.2], [TsB93]).
Example 7.11. For reduces to
i.e., to an inexact shifted logarithm barrier method (which was also derived heuristically
in [Cha94, Ex. 4.2]). This method is related, but not indentical, to ones in [CGT92,
GMSW88]; cf. [CGT94].
Example 7.12. If reduces to
corresponds to a shifted Carroll barier method.
8 Convergence of multiplier methods
In addition to Assumption 7.1, we make the following standing assumptions.
Assumption 8.1. (i) h+ is a B-function s.t. C h+ oe IR m
(e.g., so is h; cf. Lem. 2.4(a)).
is a sequence of positive numbers s.t. s
Remark 8.2. Under Assumption 8.1, q is closed proper convex, -
cl C
cl
q. Hence
for the BPM method applied to the dual problem sup with a B-function h+ we
may invoke the results of xx3-6 (replacing f , X and h by q, IR m and h+ respectively).
Theorem 8.3. If
Proof. This follows from Rem. 8.2 and Thm 5.2, since C h+ "Arg maxd ae Arg
Theorem 8.4. Let Crh oe IR m
and if inf k c k ? 0 then
lim sup
d(-) and lim sup
and every limit point of fx k g solves (7.1). If
Proof. Since C h oe Crh oe IR m
, the assertions about f- k g follow from Thm 8.3. Suppose
7.7), we have (cf. Lem. 7.2)
and
is continuous on IR m
Hence
(cf. (7.2)) means f(x
any x, in the limit
some x 1 and K ae are closed),
so by weak duality, f(x 1
Remark 8.5. Let C   denote the optimal solution set for (7.1). If (7.1) is consistent (i.e.,
is nonempty and compact iff f and g i ,
direction of recession [Ber82, x5.3], in which case (8.1) implies that fx k g is bounded, and
hence has limit points. In particular, if C  in Thm 8.4.
Remark 8.6. Theorems 8.3-8.4 subsume [Eck93, Thm 7], which additionally requires
that ffl k j 0, imrh oe IR m
? and each g i is continuous on C f .
Theorem 8.7. Let (7.1) be s.t. \Gammad has a sharp minimum. Let Crh oe IR m
k. Then there exists k s.t.
Proof. Using the proof of Thm 6.1 with
the conclusion follows
from the proof of Thm 8.4.
Remark 8.8. Results on finite convergence of other multiplier methods are restricted to
only once continuously differentiable augmented Lagrangians [Ber82, x5.4], whereas Thm
8.7 covers Ex. 7.9 also with fi ? 2. Applications include polyhedral programs.
We shall need the following result, similar to ones in [Ber82, x5.3] and [TsB93].
Lemma 8.9. With u k+1 := g(x k+1 ), for each k, we have
Proof. As for (8.2), use (7.12), (7.3), (2.3) and convexity of h + to develop
yields (8.3), and (8.4) holds with
by the
convexity of h + . (8.5) follows from (8.2)-(8.4) and (7.2).
Theorem 8.4 only covers methods with Crh oe IR m
, such as Exs. 7.7 and 7.9. To handle
other examples in x9, we shall use the following abstraction of the ergodic framework of
[TsB93]. For each k, define the aggregate primal solution
Since g is convex and c j g(x j+1
Lemma 8.10. Suppose sup i;k fl k
Then
lim sup
If f-x k g has a limit point x 1 (e.g., C   6= ; is bounded; cf. Rem. 8.11), then x 1 solves
and each limit point of f- k g maximizes d.
Proof. By 1. By (8.6) and convexity of f ,
d 1 from (8.5), so
are closed). Hence by weak duality,
solves (7.1). Since d(- k and d is closed, each cluster of f- k g maximizes d.
Remark 8.11. If C   6= ; is bounded then (8.8) implies that f-x k g is bounded (cf. Rem.
8.5). In particular, if C
9 Classes of penalty functions
Examples 7.10-7.12 stem from B-functions of the form
B-function on IR s.t. Since may also be derived by
choosing suitable penalty functions OE on IR and letting 2.6). We now
define two classes of penalty functions and study their relations with B-functions.
Definition 9.1. We say OE closed proper convex essentially
smooth, -
t, t 0
strictly convexg and \Phi strictly convex on (t 0
\Gamma1g.
Remark 9.2. If OE 2 \Phi then OE is nondecreasing (imrOE ae
is increasing on (t 0
closed proper convex,
. (For the "if" part, note that rOE(t k
and rOE is nondecreasing.)
Lemma 9.3. If OE 2 \Phi then OE   is a B-function with
lim
. If OE 2 \Phi s then OE   is
essentially smooth, C @OE
Proof. By Def. 9.1 and Lem. 2.6, IR ? ae imrOE ae IR + and OE   is a B-function with
ri C OE   ae imrOE ae C OE   , so
and rOE is nondecreasing, lim
Since OE is closed and proper, OE0
[Roc70, Thm 13.3] with oe C OE
cl C OE
and
cl C OE
and closedness of OE; otherwise lim t"t OE
[Roc70, Thm 8.5]. By [Roc70, Thm 26.1],
C OE . If OE 2 \Phi s then OE
is essentially smooth [Roc70, Thm 26.3], so @OE  and CrOE
[Roc70, Thm 26.1]. If OE 2 \Phi 0 then @OE
is increasing on (t 0
is single-valued on IR
and hence @OE
Lemma 9.4. Let / be a B-function on IR s.t. C / oe IR ? . Then
Cr/ oe IR ? . If
then /+ is essentially smooth
there exists a B-function -
Proof.
is a B-function (Lem. 2.4(a)) and
2.6(a)). Also / + is nondecreasing and essentially smooth (Lem. 7.2), so imr/
By strict convexity of / (cf. Def. 2.1(a)), is increasing on IR ? , so r/
is increasing on (t strictly
convex on (t
essentially smooth [Roc70, Thm 26.3]. Otherwise, t
be a strictly convex quadratic function s.t. -
Corollary 9.5. If OE 2 \Phi 0 then the method of Ex. 7.8 with coincides with the
method of Ex. 7.7 with
/ is the smooth extension of / described
in Lem. 9.4, so that Crh oe IR m
and Thms 8.4 and 8.7 apply.
Proof. We have
OE
so
OE and / 0 (t;
Remark 9.6. In terms of OE 2 \Phi 0 , the method of Ex. 7.8 with
OE
where OE   0
In view of Cor. 9.5, we restrict attention to methods generated by OE 2 \Phi s .
Example 9.7. Choosing OE 2 \Phi s and in Ex. 7.8 yields the method
OE
with
and /
(rOE) \Gamma1 by Def. 9.1 and [Roc70, Thms 26.3 and 26.5].) Note that
The following results will ensure that
0, as required in Lem. 8.10.
Definition 9.8. We say OE 2 \Phi is forcing on [t 0
sequences ft 0
Lemma 9.9. If OE 2 \Phi s ,
then OE is forcing on [\Gamma1; t 00
Proof. Replace OE by OE \Gamma inf OE, so that inf positive and increasing
(cf. Rem. 9.2), so is OE. Let [OE
OE . If
\Gamma! 1.
\Gamma! 1.
Therefore,
Lemma 9.10. The following functions are forcing on [\Gamma1; t 00
Proof. Let
forcing. Invoke Lem. 9.9 for OE 1 and OE 3 .
Example 9.11. Let OE 2 \Phi s be s.t.
OE is not forcing on [\Gamma1; \Gamma1], although lim
Lemma 9.12. Consider Ex. 9.7 with OE 2 \Phi s , t
t and t
. Then
1). In general, t is bounded.
Proof. This follows from the facts - k
1 and strict monotonicity of rOE; cf. Rem. 9.2, Lem. 9.3 and Ex. 9.7.
Lemma 9.13. Suppose in Ex. 9.7 OE 2 \Phi s is forcing on (\Gamma1; t fl ] with t
Proof. Since rOE is nondecreasing and h
we deduce from (8.4) that
and [OE 0 (fl k
(cf. Ex. 9.7) yields sup i;k ffl k
so the preceding relation and the forcing
property of OE give - k
Theorem 9.14. Consider Ex. 9.7 with OE 2 \Phi s s.t. inf OE ? \Gamma1. Suppose Arg maxd 6= ;,
holds. If f-x k g has a limit point x 1 (e.g., C   6= ; is bounded; cf.
Rem. 8.11), then x 1 solves (7.1) and f(x 1
Proof. Let We have
, so the assertions about f- k g follow from Thm 8.3. Then t
by Lem. 9.12 (f- k g is bounded), so OE is forcing on [\Gamma1; t fl
9.13. The conclusion follows from Lem. 8.10.
Remark 9.15. For the exponential multiplier method (Ex. 7.10 with
8.3 and 9.14 subsume [TsB93, Prop. 3.1] (in which Arg maxd 6= ;, C   6= ; is bounded,
Theorem 9.16. Consider Ex. 9.7 with OE 2 \Phi s forcing on (\Gamma1; t OE ) 6= IR (e.g.,
holds. If f-x k g has a limit point x 1 (e.g., C   6= ; is bounded; cf. Rem. 8.11), then
and each limit point of f- k g maximizes d.
Proof. By Lem. 9.12, t
so OE is forcing on (\Gamma1; t fl ]. Since d(- k
9.13. Since t fl - t OE ! 1, the conclusion follows from Lem. 8.10.
Remark 9.17. Suppose
2.2.3]). If d duality. If
is bounded iff so is Arg maxd
This observation may be used in Lem. 8.10 and Thm 9.16.
Theorem 9.18. Consider Ex. 9.7 with OE 2 \Phi s s.t. inf OE ? \Gamma1. Suppose
some x 2 C f ,
holds.
If f-x k g has a limit point x 1 (e.g., C   6= ; is bounded; cf. Rem. 8.11), then x 1 solves
and each limit point of f- k g maximizes d. If d
Proof. Since and Arg maxd 6= ; are bounded (Rem.
9.17), we get, as in the proof of Thm 9.14, C
Hence
the first two assertions follow from Lem. 8.10, and the third one from Thm 8.3.
Theorem 9.19. Consider Ex. 9.7 with OE 2 \Phi s forcing on (\Gamma1; t 00
and holds. If f-x k g has a limit point x 1 (e.g., C   6= ; is bounded; cf. Rem. 8.11),
and each limit point of f- k g maximizes d. If
Proof. Use the proof of Thm 9.18, without asserting that C
.
Remark 9.20. It is easy to see that we may replace OE 2 \Phi s by OE 2 \Phi 0 and Ex. 9.7
by Ex. 7.8 with Lems. 9.9, 9.12, 9.13 and Thms 9.14, 9.16, 9.18, 9.19. (In
the proof of Lem. 9.9,
OE , since OE 0 and OE are positive and increasing on
proving Lem. 9.12, recall the proof of Cor. 9.5; in the proof of Lem. 9.13, use
Such results complement Thms 8.4 and 8.7; cf. Cor. 9.5.
Additional aspects of multiplier methods
Modified barrier functions can be extrapolated quadratically to facilitate their minimiza-
tion; cf. [BTYZ92, BrS93, BrS94, NPS94, PoT94]. We now extend such techniques to our
penalty functions, starting with a technical result.
Lemma 10.1. Let OE 1 ; OE 2 2 \Phi be s.t. for some t s 2 (t 0
is forcing on (\Gamma1; t s ] and OE 2 is forcing on
is forcing on (\Gamma1; t 00
Proof. Suppose
(other cases being
trivial). Since OE 0
1 and OE 0
are nondecreasing, so is OE 0 ; therefore, all terms in
are nonnegative and tend to zero. Thus OE 0
Hence t 0
yield the first assertion. For the second one, use Def. 9.1 and Rem. 9.2.
Examples 10.2. Using the notation of Lem. 10.1, we add the condition OE 00
to make OE twice continuously differentiable. In each example, OE 2 \Phi s [ \Phi 0 is forcing on
Lems. 9.9-9.10 and Rem. 9.20.
12ts
only grows as fast as OE 2 in Ex. 7.9 with but is smoother.
b. This OE does not grow as fast as e t in Ex. 7.10.
3 (log-quadratic).
This OE allows arbitrarily large infeasibilities, in contrast to OE 1 in Ex. 7.11.
Again, this OE has C in contrast to OE 1 in Ex. 7.12.
s
Remark 10.3. Other smooth penalty functions (e.g., cubic-log-quadratic) are easy to
derive. Such functions are covered by the various results of x9. Their properties, e.g.,
may also have practical significance; this should be verified experimentally.
The following result (inspired by [Ber82, Prop. 5.7]) shows that minimizing L k (cf.
in Alg. 7.4 is well posed under mild conditions (see the Appendix for its proof).
Lemma 10.4. Let
is a B-function with C / oe IR ? . Suppose
is nonempty and compact iff f and
have no common direction of recession, and if C 0 6= ; then this is equivalent to
having a nonempty and compact set of solutions.
We now consider a variant of condition (7.18), inspired by one in [Ber82, p. 328].
Lemma 10.5. Under the strong convexity assumption (7.15), consider (7.17) with
replacing (7.18), where
ff
Next, suppose
is bounded.
Proof. By (7.17) and (10.1), (10.2) holds with L(x
follows from (8.5). Similarly, L(x
ff yields L(x
ff
(Lem. 4.8(i)).
Remark 10.6. In view of Lem. 10.5, suppose in the strongly convex case of (7.15), (10.1)
is used with (cf. (10.3)), the results of xx8-9
may invoke, instead of Thm 5.2 with
The latter condition holds automatically if lim k!1 d(- k 1. Thus we
may drop the conditions:
Thms 8.3, 8.4, 9.14, ffl k ! 0 from Lem.
8.10 and Thm 9.16, and
Thms 9.18-9.19. Instead of
we may assume that fc k j k g is bounded in Thms 8.3, 8.4, 9.14 and 9.18-9.19.
Condition (10.1) can be implemented as in [Ber82, Prop. 5.7(b)].
Lemma 10.7. Suppose f is strongly convex, inf C f
is continuous on
C f . Consider iteration k of Ex. 7.5 with
is a B-function
s.t. Cr/ oe IR ? . If is not a Lagrange multiplier of (7.1), fz j g is a sequence
converging to -
satisfying the stopping criterion (10.1).
Proof. By Lemmas 9.3-9.4, Ex. 7.5 has -
u).
Then, as in (8.2),
Suppose (-x). By (10.5), (2.3) and convexity of h
m. Therefore, since OE is strictly convex on [t 0
with
OE (Def. 9.1), and fl k
OE , for each i, either fl k
h-
Combining this with
-) (Lem. 7.3), we see (cf. [Roc70, Thm 28.3]) that - k is a Lagrange
multiplier, a contradiction. Therefore, we must have strict inequality in (10.5). Since
the stopping criterion will be satisfied for sufficiently large j.
A

Appendix


Proof of Lemma 7.2. IR m
(cf. [Roc70, Thm 23.8]),
so
and h+ is essentially strictly convex (cf. [Roc70, p. 253]). Hence (cf.
is closed proper essentially smooth, so @h
by [Roc70, Thm 26.1] and rh + is continuous on -
by [Roc70,
Thm 25.5]. By [Roc70, Thm 23.5], @h
nondecreasing,
as the union of open sets. That
and ~
(-) then
and
and ~
Hence OE is inf-compact and
We need the following slightly sharpened version of [GoT89, Thm 1.5.4].
Lemma A.1 (subdifferential chain rule). Let f be proper convex functions on
ri C f i 6= ;. Let
OE be a
proper convex nondecreasing function on IR m s.t.
y for some ~
, and for each -
f
Proof. For any x 1
and hence
is convex. Since /(x) ? \Gamma1 for all x, / is proper. Let
. For any x, f(x) - f(-x)
yields
To prove the opposite inclusion, let - fl 2 @/(-x). Consider the convex program
By the monotonicity of OE and the definition of subdifferential, (-x; -
solves (A.2), which
satisfies Slater's condition (cf. f(~x) ! ~
y), so (cf. [Roc70, Cor. 28.2.1]) it has a Kuhn-Tucker
point -
xi 8x yields -
ri C f i
Thm 23.8]). Thus @/(-x) ae Q, i.e., To see that im@OE ae IR m
, note that if
Proof of Lemma 10.4. Let OE i
m. Each OE i is closed: for any ff 2 IR,
is closed nondecreasing and lim t"t /
is closed (so is g i ). We have
and OE i closed proper and L k 6j 1, so L k is closed and L k
Thm 9.3]. Suppose Lem. 9.4 and Def.
9.1) and g i is closed, there is x 2 ri C
Hence
(cf. Lemmas 9.3-9.4) yield
ff
t. Then
from
. Thus OE
Therefore, otherwise. The
proof may be finished as in [Ber82, x5.3].



--R

Numerical methods for nondifferentiable convex optimization
New York
Partial proximal minimization algorithms for convex program- ming
The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming
Computational experience with modified log-barrier methods for nonlinear programming

Penalty/barrier multiplier methods for minimax and constrained smooth convex programs
Weak sharp minima in mathematical programming
Optimization of Burg's entropy over linear constraints
An iterative row action method for interval convex programming
Proximal minimization algorithm with D-functions
A globally convergent Lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds

Nouvelles m'ethodes s'equentielles et parall'eles pour l'optimisation de r'eseaux 'a co-ots lin'eaires et convexes
Convergence analysis of a proximal-like minimization algorithm using Bregman functions
Convergence of some algorithms for convex minimization
On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
Nonlinear proximal point algorithms using Bregman functions
Multiplicative iterative algorithms for convex programming
Finite termination of the proximal point algorithm
Sequential Unconstrained Minimization Techniques
Equilibrium programming using proximal-like algorithms
Shifted barrier methods for linear programming
Theory and Optimization Methods
On the convergence of the proximal point algorithm for convex minimization

On some properties of generalized proximal point methods for quadratic and linear programming
On the convergence rate of entropic proximal optimization algorithms
The convergence of a modified barrier method for convex programming


The proximal algorithm
R'egularisation d'in'equations variationelles par approximations successives
Massively parallel algorithms for singly constrained convex programs


A numerical comparison of barrier and modified barrier methods for large-scale bound-constrained optimization
English transl.

Nonlinear rescaling and proximal-like methods in convex opti- mization
Convex Analysis


Entropic proximal mappings with applications to nonlinear programming
Relaxation methods for problems with strictly convex costs and linear constraints

Dual ascent methods for problems with strictly convex costs and linear constraints: A unified approach
--TR

--CTR
Lin He , Martin Burger , Stanley J. Osher, Iterative Total Variation Regularization with Non-Quadratic Fidelity, Journal of Mathematical Imaging and Vision, v.26 n.1-2, p.167-184, November  2006
Hatem Ben Amor , Jacques Desrosiers, A proximal trust-region algorithm for column generation stabilization, Computers and Operations Research, v.33 n.4, p.910-927, April 2006
G. Birgin , R. A. Castillo , J. M. Martnez, Numerical Comparison of Augmented Lagrangian Algorithms for Nonconvex Problems, Computational Optimization and Applications, v.31 n.1, p.31-55, May       2005
Krzysztof C. Kiwiel , P. O. Lindberg , Andreas Nu, Bregman Proximal Relaxation of Large-Scale 01 Problems, Computational Optimization and Applications, v.15 n.1, p.33-44, Jan. 2000
A. B. Juditsky , A. V. Nazin , A. B. Tsybakov , N. Vayatis, Recursive Aggregation of Estimators by the Mirror Descent Algorithm with Averaging, Problems of Information Transmission, v.41 n.4, p.368-384, October   2005
N. H. Xiu , J. Z. Zhang, Local convergence analysis of projection-type algorithms: unified approach, Journal of Optimization Theory and Applications, v.115 n.1, p.211-230, October 2002
Naihua Xiu , Jianzhong Zhang, Some recent advances in projection-type methods for variational inequalities, Journal of Computational and Applied Mathematics, v.152 n.1-2, p.559-585, 1 March
convex programming;nondifferentiable optimization;b-functions;bregman functions;proximal methods