Rescaling and Stepsize Selection in Proximal Methods Using Separable Generalized Distances.
This paper presents a convergence proof technique for a broad class of proximal algorithms in which the perturbation term is separable and may contain barriers enforcing interval constraints.  There are two key ingredients in the analysis: a mild regularity condition on the differential behavior of the barrier as one approaches an interval boundary and a lower stepsize limit that takes into account the curvature of the proximal term.  We give two applications of our approach.  First, we prove subsequential convergence of a very broad class of proximal minimization algorithms for convex optimization, where different stepsizes can be used for each coordinate.  Applying these methods to the dual of a convex program, we obtain a wide class of multiplier methods with subsequential convergence of both primal and dual iterates and independent adjustment of the penalty parameter for each constraint. The adjustment rules for the penalty parameters generalize a well-established scheme for the exponential method of multipliers. The results may also be viewed as a generalization of recent work by Ben-Tal and Zibulevsky [SIAM J. Optim, 7 (1997), pp. 347--366] and Auslender, Teboulle, and Ben-Tiba [ Comput. Optim. Appl., 12 (1999), pp. 31--40; Math. Oper. Res., 24 (1999), pp. 645--668] on methods derived from $\varphi$-divergences.  The second application established full convergence, under a novel stepsize condition, of Bregman-function-based proximal methods for general monotone operator problems over a box.  Prior results in this area required strong restrictive assumptions on the monotone operator.
Introduction
denote the possibly unbounded n-dimensional "box" ([a
This paper considers two closely-related
problems, the minimization problem
min f(x)
(1)
is a closed proper convex function, and the variational inequality
where T is a (possibly set-valued) maximal monotone operator, and NB (x) denotes the cone
of vectors normal to the set B at x. It is well known that, under mild regularity conditions,
(1) is the special case of (2) for which the subgradient mapping of f .
The last decade has seen considerable progress in the theory of proximal point methods
based on generalized distances [11, 13, 19, 5, 21, 31, 14, 2, 3, 17]. Such methods use a scalar-valued
regularization function to derive better-behaved versions of problems (1) and (2). In
this article, we consider separable regularization terms of the form
are scalar functions conforming to very general assumptions (see Assumption
2.1 below). In particular, we assume that as x 2 int B approaches the boundary of
B, kr 1 D(x; y)k !1, where r 1 denotes the gradient with respect to the first vector argu-
ment. The distance-like measure D can be, for example, the squared Euclidean distance, a
Bregman distance [8], or a '-divergence [19] (see Section 2.2 below).
Using these regularization terms, proximal methods for (1) take the form:
x
where ff k is a positive n-dimensional vector whose elements are called stepsizes. Note that
we allow different stepsizes for each coordinate, as suggested by a variety of computational
and theoretical studies [32, 5, 2, 3]. Moreover, since kr 1 D(x; x k )k !1 as x approaches the
boundary of B, the regularization acts not only as a stabilizing proximal term but also as a
kind of barrier function keeping the iterates within int B.
In the case of the variational inequality (2), (3) generalizes to finding x k+1 satisfying the
recursion
RRR
We derive some general results for these types of algorithms in Section 2, assuming that
the stepsizes conform to a special rule that takes into account the curvature of the proximal
term. This rule, although restrictive, appears to cover cases of the greatest practical interest;
as we shall see, it covers the stepsize/penalty selection rules proposed in [32, 5, 2, 3].
Section 3 uses the results of Section 2 to obtain subsequential convergence results for the
generalized proximal minimization algorithm (3).
A critical application of (3), considered in Section 3.2, is when f is minus the dual
function of a convex program such as
s.t.
where are differentiable convex functions. 1 We also assume that this
problem is feasible, i.e., there is - y Choosing B to be
any box containing the nonnegative orthant and f to be the negative of the dual function
of (5), we may implement (3) via a multiplier method in which a sequence of unconstrained
penalized versions of (5) must be solved. This construction leads to a class of multiplier methods
that is extremely broad, subsuming both the classical quadratic augmented Lagrangian
and the exponential method of multipliers [32, 6].
For these multiplier methods, our stepsize choice ensures that for indices i with x k
the corresponding penalty term is augmented so it does not become so "flat" as to permit
infeasibility of primal limit points. Empirically, the technique speeds convergence, and it
also appears in a convergence rate analysis in [32] for the exponential method of multipliers
case. Ben-Tal and Zibulevsky [5] have proved the optimality of the accumulation points
of the exponential method, together with a class of proximal terms closely related to '-
divergences, and their results are extended in [3]. Section 3 places such results in a broader
context that includes Bregman distances.
In Section 4, we restrict our attention to Bregman distances. It has been known for the
better part of a decade that, when D(\Delta; \Delta) is any Bregman distance and the stepsizes do not
vary by coordinate, the recursion (4) converges to a solution of the variational inequality (2)
in various special cases: when the subdifferential of a closed proper convex function
f , or when domT ' int B, meaning that all constraints must already be embedded in the
operator T . In [9], these results were extended to "paramonotone" operators T , a category
which includes as a special case. Unfortunately, many interesting practical cases,
such as the subdifferential maps of saddle functions, are not paramonotone. More recently,
Auslender et al. [2] have obtained strong results for general maximal monotone T , but only
for a specific '-divergence choice of D(\Delta; \Delta). As noted in [4], these results can be extended
to the (generally non-Bregman) case where D(\Delta; \Delta) is obtained by adding a quadratic to any
member of the class \Phi 2 of [3].
1 Actually, the results of Section 3.2 continue to hold [28] if one only supposes that
are closed proper convex and assumes appropriate conditions on the effective domains of the
objective and constraints, as in [24, Chapter 28]. However, this further generality makes the proofs more
convoluted and is dropped for the sake of simplicity in the exposition.
Page 4 RRR 35-99
Section 4 shows convergence, for general maximal monotone T , of the proximal method
(4), where D(\Delta; \Delta) is a Bregman distance, to a solution of (2). We do impose some additional
assumptions, derived from those of Section 2. First, we assume that the Bregman function
used to construct the distance is twice-differentiable, which is not part of the standard
Bregman function setup. Second, in addition to our general stepsize rule, we also require
that the stepsizes do not vary by coordinate, that is, ff
n for all k. The resulting
condition is stronger than the usual requirement that the stepsize is simply bounded away
from zero, but is crucial to the analysis, which blends the techniques of Section 2 with
traditional Fej'er monotonicity arguments. Still, we have managed to substitute conditions
on D(\Delta; \Delta) and ff k , which are parts of the algorithm, for conditions on T , which is part of the
problem to be solved.
Finally, we allow the calculations required for the recursions (3) and (4) to be performed
approximately, as is likely to be necessary in practice. For the rescaling minimization case
of Section 3, we adopt a constructive approximation criterion inspired by [17] and [29].
However, our criterion, which is tailored to the proximal minimization case, appears to be
new. In the variational inequality analysis of Section 4, we use the simple, verifiable criterion
of [14], although extension to the more sophisticated criterion of [29] may well be possible.
In summary, the primary contributions of this paper are:
ffl A novel convergence proof framework for a broad class of proximal algorithms.
ffl Using this framework to establish subsequential convergence of a wide range of proximal
minimization algorithms (3) with differing stepsize parameters for each coordinate; this
result in turn leads to subsequential convergence of a broad class of multiplier methods
with differing penalty parameters for each constraint.
ffl Using the framework to show convergence of "interior" Bregman proximal point algorithms
for maximal monotone operators, with a novel stepsize condition, but without
the usual restrictive assumptions on the operator T .
The new proximal minimization approximation criterion of Section 3 constitutes an additional
contribution.
Fundamental Analysis
This section develops the fundamental analysis necessary for our results. We concentrate
our attention on the variational problem (2), since it subsumes the minimization problem (1)
under mild assumptions.
In order to simplify the notation, we denote, for
d 00
RRR
We are now able to present the necessary assumptions on the functions d
Assumption 2.1 For has the following
properties:
2.1.1. For all y closed and strictly convex, with its minimum at y i .
Moreover, int dom d i (\Delta; y
2.1.2. d i is continuously differentiable over (a
exists and is strictly positive.
2.1.3. For all y essentially smooth [24, Chapter 26].
2.1.4. There exist ae; ffl ? 0 such that if either
The assumption of strict convexity is standard in generalized proximal methods. The
assumption of twice differentiability is also quite common, although many existing results
require only a once-differentiable d i . The essential smoothness assumption makes the distance
act like a barrier function, forcing the iterates defined by the recursion (4), and hence
its approximate version (6) below, to remain in the interior of the box B. In Section 2.2,
we specialize these assumptions to the case of Bregman distances and '-divergences, where
similar comments can be made.
Finally, the fourth part of the assumption is new to the theory of generalized proximal
methods, but is not very restrictive in practice. In particular, we show in Section 2.2 that, for
Bregman distances and '-divergences, this condition can be written in terms of the kernels
used to obtain the regularizations, and that it holds for most of the examples we are aware
of.
In addition, we make the following standard regularity assumption which, in view of the
barrier function properties of d i , is required for any sensible application of (4):
Assumption 2.2 domT " int B 6= ;.
We are now able to present the proximal minimization algorithm:
Rescaling Proximal Method for Variational Inequality (RPMVI)
1. Initialization: Let Choose a scalar c ? 0, and an initial iterate x 0 2 int B.
2. Iteration:
(a) Choose ff k 2 R n
such that ff k
\Phi
(b) Find x k+1 and e k+1 such that
Page 6 RRR 35-99
(c) Let repeat the iteration.
To guarantee the convergence of the RPMVI, we need additional assumptions on the
stepsizes fff k
and the error sequence fe k g; see Assumption 2.3 below.
We define
whence it is clear from (6) that
Assumption 2.3 Let ffi k g be a real sequence converging to zero. The error sequence, fe k g,
the regularization functions d and the stepsizes, fff k
must be chosen
in order to guarantee that:
2.3.1.
ff
2.3.2. If - x is an accumulation point of fx k g, i.e., there is an infinite set K ' N such that
x, then, for each
or there is an infinite set K 0 ' K
such that x
Assumption 2.3.2 may seem artificial at this point, but Sections 3 and 4 will describe
settings where it is easily verifiable.
2.1 Convergence Analysis
We assume throughout this section that Assumptions 2.1 and 2.2 hold, and that sequences
conforming to the recursions of the RPMVI algorithm and Assumption
2.3 exist. In Sections 3 and 4 we will present conditions which, in more specific settings,
guarantee the existence of such sequences.
Lemma 2.4 Let -
x 2 R n be a limit point of fx k g, i.e., x k !K -
x for some infinite set K ' N.
Then for
lim
lim inf
lim sup
Proof. For each i, we consider the three possible cases:
First, suppose i is such that -
For the sake of a contradiction, assume that
using Assumption 2.3.2, there is an infinite set K 0 ' K and a i ? 0 such
RRR
that for all k 2 K 0 , jfl k
x i . Therefore
-ff
ff
[Assumption 2.3.1]
[Choice of ff k
This result contradicts
Next, consider the case - x suppose that lim inf k!K1 fl k
using
Assumption 2.3.2, there must be a i ? 0 and an infinite set K 0 ' K such that for all k 2 K 0 ,
ff
-ff
-cd 00
Let ffl be as in Assumption 2.1.4. If there is an infinite set K 00 ' K 0 such that x
for all k 2 K 00 , we can conclude from the assumption that:
2d 00
aecd 00
since x
for sufficiently large k 2 K 0 .
Page 8 RRR 35-99
As d i (\Delta; x
its minimum at x k\Gamma1
implies that d 0
Hence
ff
for sufficiently large k 2 K 0 , a contradiction with
Finally, the case of -
is analogous to the case -
Lemma 2.5 Let -
x be a limit point of fx k g, i.e., x k !K - x for some infinite set K ' N.
Proof. By Assumption 2.2, there must exist some e
(ex). The
monotonicity of T implies that, for all k - 0,
We will show that unboundedness of ffl k gK would contradict this inequality for some sufficiently
large k.
is unbounded, there must exist an infinite K 0 ' K such that ffl k gK 0 converges in
, with at least one ffl k
implies that for each unbounded
coordinate i, either
or
Therefore, for each unbounded coordinate of ffl k gK 0 , we have
or
On the other hand, for coordinates such that ffl k
also bounded. Thus, for sufficiently large k 2 K must be negative,
contradicting (9). 2
Finally, the main convergence theorem for the RPMVI follows:
RRR
Theorem 2.6 If fx k g is a sequence generated by the RPMVI algorithm with Assumptions
2.1, 2.2, and 2.3 holding, then all the limit points of fx k g are solutions to the variational
inequality problem (2).
Proof. Let -
x be any limit point of fx k g, i.e., x k !K -
x, for some infinite set K ' N. From
Lemma 2.5, we know that the corresponding sequence
must exist some K 0 ' K with
must be outer semicontinuous [27,
12.8(b)], it follows that - fl 2 T (-x). Lemma 2.4 implies that
and these conditions are equivalent to
Incidentally, it is possible to eliminate the requirement of twice-differentiability of d i (\Delta; y i ),
at the cost of some additional complexity in the description of the method. Specifically,
consider replacing Assumption 2.1.4 with the condition that there exist functions
If the stepsizes are now selected so that for some scalar c ? 0, we have for all
and k - 0 that ff k
the conclusions of Theorem 2.6 continue to hold. We
may examine this variation of the analysis in subsequent research. The present approach is
equivalent to taking L i (y choice since d 00 (y
rate of change of d 0 (\Delta; y i ) around y i .
2.2 Some examples of d i
functions
We present some example of d i functions that conform with Assumption 2.1. In particu-
lar, we show that two classes of regularizations widely studied in the literature, Bregman
distances [11, 13] and '-divergences [19], conform to the assumption under very mild restrictions

2.2.1 Bregman distances
Bregman distances were introduced in [8] and have been studied in the context of proximal
methods in [11, 12, 13], as well as many subsequent works. To construct each regularization
one uses an auxiliary convex function h i and defines d i
Nonseparable distances can also be constructed in a similar way, but the
separable case is the most common.
The following properties guarantee that Assumption 2.1 holds for such
Assumption 2.7 For has the following
properties:
2.7.1. h i is closed, int continuously differentiable, with a
strictly positive second derivative throughout (a
2.7.2. h i is essentially smooth.
2.7.3. There exist ae ? 0 and ffl ? 0 such that if either
Note that Assumption 2.7.1 implies that each h i is strictly convex. Assumption 2.7.3 corresponds
to Assumption 2.1.4, since d 00
Fortunately, it is not very restrictive.
Consider the case of finite a i . Since lim x
we know that h 00
must be
unbounded above as x i & a i . To violate the assumption, h 00
would have to oscillate
unboundedly as x i & a i . As far as we are aware, every separable Bregman function proposed
so far conforms not only to Assumption 2.7.3, but to a more stringent, easier-to-verify
condition, as follows:
Lemma 2.8 If there is an ffl ? 0 such that for all x
i is non-increasing,
and for all x 2 (b
i is non-decreasing, then Assumption 2.7.3 holds.
Proof. Suppose that a
Therefore, Assumption 2.7.3 holds with 1. The case b i ! 1 is analogous. 2
Examples of functions h i where all these assumptions hold are:
log x, with a
with with a
Finally, we note that for finite a i we do not yet assume that h i must approach a finite
limit as x i & a i , nor similarly for x i Such an assumption is quite common in
the theory of Bregman distances [11, 13, 9, 29], but, similarly to [21], it is not needed for
the results of Section 3 below. We will use it, however, in the variational inequality analysis
of Section 4.
RRR 35-99 Page 11
2.2.2 '-divergences
The '-divergence regularizations have been studied in the context of proximal methods, for
example, in [19], and more recently in [5, 3]. In these works, the box considered is the
positive orthant, i.e.,
. An auxiliary strictly convex scalar function ' is used to
define the distance d i , but this time by:
The following hypotheses can be used to guarantee Assumption 2.1 when
Assumption 2.9 The function ' : R! (\Gamma1; +1] is such that:
2.9.1. ' is closed and convex, with int
2.9.2. ' is twice differentiable on (0; +1), with ' 00 (t) ? 0 for all t ? 0;
2.9.3.
2.9.4. ' is essentially smooth;
2.9.5. There exists a ae ? 0 such that ae' 0 (t) - ' 00
Slight variations on these assumptions appear, for example, in [5, 3], together with the
following examples:
The next lemma states that Assumption 2.9.5 above implies Assumption 2.1.4:
Lemma 2.10 Let (a be defined as in (10). Then Assumption 2.1.4
is equivalent to the existence of a ae ? 0 such that ae' 0 (t) - ' 00
Proof. First we observe that:
d 00
and so
d 00
Page 12 RRR 35-99
Therefore, Assumption 2.1.4 reduces to
Taking letting y i range over (0; x i ], and setting
Conversely, if (12) is true, (11) holds for an arbitrary choice of ffl ?
We note that in [5], one assumes that the iterations are of the form:
where each ff k
i is greater than c=x k
being a positive constant. In [2, 3], this property is
guaranteed by redefining the distance measure to be
~
~
and assuming stepsizes bounded away from zero. In this case, the iteration is
~
with lim inf k!1 e
rewriting the iteration with
respect to D, instead of ~
D, we recover the rule from [5].
It turns out that these techniques are a special case of our stepsize choice rule, which
gives in the case of a '-divergence that
which is identical if one redefines the constant factor c.
Thus, the reader should note that the class of '-divergences described by Assumption 2.9
encompasses the regularizations studied in [5, 2, 3]. In particular, it includes the classes \Phi 1
and \Phi 2 described in [3].
However, the stepsize rule in the RPMVI is more stringent than the one in [5, 2, 3],
as it also assumes that the stepsize is bounded away from zero. To overcome this slight
restriction, we point out that the assumption ff k
used here only in the first part
of the proof of Lemma 2.4, and it can be replaced by the assumption that d 00
continuous and strictly positive over (a This condition holds for '-divergences, since
d 00
In this sense, the results here can be seen as extensions of those in [5, 2, 3].
RRR
3 Proximal Minimization Methods with Rescaling
This section applies the analysis of the RPMVI method to the minimization problem (1).
We leave Assumption 2.1 as a standing assumption; we also make the following standard
regularity assumption, which in view of the barrier function properties of D, is required for
any sensible application of (3):
Assumption 3.1 dom f " int B 6= ;.
Note that, since int B is open, this assumption implies that ri dom f " int B 6= ;, which
implies that dom @f " int B 6= ;. Then, using [24, Theorem 23.8], one can show that the
minimization problem (1) is equivalent to the variational inequality problem (2) with
Moreover, Assumption 2.2 holds.
Then, we specialize the RPMVI to:
Rescaling Proximal Minimization Method (RPMM)
1. Initialization: Choose c ? 0 and oe 2 [0; 1]. Choose nonnegative scalar sequences fs k g
and fz k g with
2. Iteration:
(a) Choose ff k 2 R n
such that ff k
\Phi
(b) Find x
oe
ae s k+1
oe
with the standing convention that min
\Psi is z k+1 whenever
(c) Let repeat the iteration.
Note that if one chooses s k ; z reduces to the "constructive" criterion
reminiscent of [29].
Page 14 RRR 35-99
3.1 Convergence analysis
We start by showing that the iteration step is well defined if f is bounded below on B:
Lemma 3.2 If f is bounded below on B, then there is a unique point that solves the iteration
step of the RPMM with e a solution to (13)-(14) exists if f is bounded below
on B.
Proof. Let ' be a lower bound of f on B. Given i 2 R, the level set
This last set is a level set of
i ) on B, which must be bounded, since by
Assumption 2.1.1 this function attains its minimum at the unique point x k [24, Corollary
8.7.1]. Therefore, f(\Delta)
attains a minimum on B. The uniqueness of
the minimum follows from the strict convexity of D(\Delta; x k ). 2
To apply the convergence analysis of the previous section to the sequence fx k g computed
by the RPMM, it suffices to show that Assumption 2.3 holds. Verification of Assumption
2.3.1 is straightforward:
Lemma 3.3 With the definition
ae s k
oe
for all k - 1, Assumption 2.3.1 holds for the RPMM.
Proof. From the nonnegativity of fs k g and fz k g, it follows that ffi k g is also nonnegative.
one also has fi k ! 0. Moreover, since oe 2 [0; 1],
oe
ff
for all k, so Assumption 2.3.1 holds. 2
As in (7), we define for all k - 0 and
and let fl k 2 R n be the vector with elements
Lemma 3.4
RRR 35-99 Page 15
Proof. The claim that fl k 2 @f(x k ) follows from the definition of fl k . For the second claim,
we have, using the convexity of d i (\Delta; x
ff
Using (14), it then follows that
ff
ae s k
ae s k
oe fi fi x
ae s k
oe
\Gammas k :Before proving the next result, we state a helpful technical lemma:
Lemma 3.5 [22, Section 2.2] Suppose fa k g, ffl k g ae R are sequences such that fa k g is
bounded below,
exists and is finite, and the recursion a k+1 - a k holds for all k.
is convergent.
It is now possible to establish that Assumption 2.3.2 also holds:
Lemma 3.6 If f is bounded below on B, then ff(x k )g is convergent and
Hence Assumption 2.3.2 holds for the RPMM.
Proof. Using Lemma 3.4,
ns
Then, recalling that fs k g is summable, Lemma 3.5 implies that ff(x k )g is a convergent
sequence. For
Page
Using Lemma 3.4 once again, it follows that
Taking limits, we conclude that fl k
Thus, Theorem 2.6 implies the optimality of all accumulation points of the sequence
g. We strengthen this observation below:
Theorem 3.7 Suppose that Assumptions 2.1 and 3.1 hold, and that f is bounded below on
B. If fx k g has a limit point, then ff(x k )g converges to the infimum of f on B and all limit
points of fx k g will be minimizers of f on B. A condition that guarantees the existence of
limit points of fx k g is the boundedness of the solution set, or any other level set of f .
Proof. As just noted, Lemma 3.6 implies that Assumption 2.3.2 holds, and so Assumption
2.3 holds in its entirety. Assumption 2.1 holds by hypothesis, and, setting
Assumption 3.1 implies Assumption 2.2. Thus, the conclusions of Theorem 2.6 apply. Let
x be a limit point of fx k g, i.e. x k !K - x, for some infinite set K ' N. Theorem 2.6 asserts
that Assumption 3.1, -
x is a minimizer of f on B. Moreover, since
Lemma 2.5 states that ffl k gK is bounded, and since ff(x k )g is convergent by Lemma 3.6,
min
lim
Therefore, lim k!1 f(x k
Finally, the boundedness of any level set of a proper closed convex function implies
boundedness of all level sets [24, Corollary 8.7.1], and Lemma 3.6 states that ff(x k )g is
convergent, consequently it is bounded. So, fx k g is also bounded and has limit points. 2
3.2 Multiplier Methods
We now discuss applying the RPMM to the dual of the convex program (5) to obtain multiplier
methods. The use of proximal methods to derive multiplier methods for constrained
convex optimization is a now-classical subject and may be traced to the seminal paper [26].
In the context of generalized proximal methods, applications can be found, for example,
in [30, 13, 19, 21, 31, 3, 17]. In this section, we consider only the case in which the proximal
step is done exactly, i.e., we will let e as in [30, 13, 19, 17]. Unfortunately,
our approximate-step acceptance rule for the RPMM does not translate directly to an easily
verifiable acceptance criterion for an approximate solution of the penalized problem (17) be-
low. However, partial results in this direction may be obtained under stringent assumptions
on the original problem (5); see Appendix B. A criterion in the spirit of (14) that does not
depend on such assumptions is the subject of ongoing research [15]. We further observe that
the approximation criteria of [17, 29] also do not translate readily to a multiplier method
RRR 35-99 Page 17
setting. On the other hand, under the assumption that the primal objective function g 0
is strongly convex, [26, 21, 3] present some inexact multiplier methods based on a rather
different acceptance rule involving optimizing the augmented Lagrangian function to within
some tolerance ffl of its minimum value.
Consider the convex problem (5), and let ffi C denote the indicator function of a convex
set C. Then we define f to be minus the dual function associated with (5), plus
The dual problem to (5) is then equivalent to the minimization of f . Furthermore, we assume
Assumption 3.83.8.1. The primal problem (5) has a finite optimal value, and it conforms
to the Slater condition.
3.8.2. For all conform to Assumption 2.1 for a i -
3.8.3. There is an - x ? 0 such that - x 2 dom f , where f is as defined in (15).
This assumption has the following consequences: Assumption 3.8.1 implies that the dual
solution set is non-empty and bounded [16] and that there is no duality gap. Assumption
3.8.3 implies that Assumption 3.1 holds for f as defined by (15).
Under Assumption 3.8, if we fix e each iterate x k+1 of the RPMM applied
to the negative dual functional f may be calculated by the following multiplier method
whenever the unconstrained problems (17) have solutions:
\Phi
d \Phi
denotes the monotone conjugate [24, p. 111] with respect to the first argument,
that is, d \Phi
)g. 3 Theorem 3.10 below gives conditions guaranteeing
that a y k+1 satisfying (17) exists.
We relegate the technical aspects of the proof of the equivalence of (16)-(18) to the
RPMM applied to the f defined in (15) to Appendix A, since they are very similar to earlier
2 The case a is of interest because it includes the classical method of multipliers for problems with
inequality constraints [26], along with various extensions described in [13, 20].
3 The classical conjugate /   of a function / is defined [24, Chapter 12] via /
for any / : R n ! (1; +1]. The monotone conjugate of / is then the classical conjugate of
, that is,
Page
proofs for various special cases of (17)-(18), for example in [30, 13, 19, 21, 17]. In particular,
Corollary A.4 establishes the equivalence of the two calculations.
Given this equivalence, Theorem 3.7 asserts the subsequential convergence of the sequence
to a dual solution of (5). For the primal sequence, however, it has historically been
harder to prove good behavior. For example, in the case of Bregman distances, a guarantee of
feasibility of primal accumulation points has relied on stringent assumptions like R n
ae int B,
as in [13], or strict complementarity [18].
In the case of the RPMM, with its strong stepsize restrictions, the feasibility, and therefore
optimality, of accumulation points of fy k g is easily demonstrated.
Theorem 3.9 Suppose that Assumption 3.8 holds. Pick a scalar c ? 0, let x 0 2 R n
and
suppose that it is possible to obtain a sequence f(ff k that obeys the recursions (16)-
(18). Then, fx k g is bounded and all its accumulation points are solutions of the dual of (5).
Moreover,
lim sup
lim
and fg 0 (y k )g converges to the optimal value of the primal problem (5). Therefore, any
accumulation point of fy k g solves the primal problem.
Proof. As shown in Corollary A.4, the sequence fx k g is the same as would be computed
by using the RPMM to solve the dual problem, that is, to minimize f . In particular, fx k g
and all its limit points must be nonnegative. Moreover, the Slater condition implies that the
dual function has bounded level sets. Then, the boundedness of fx k g and the optimality of
its limit points follow from Theorem 3.7.
Let us analyze the primal sequence. For each
the same role as
in (7), with e k
Let fx k gK be any convergent subsequence of fx k g, and -
x the respective accumulation
point, x k !K - x. Lemma 2.4 implies that
As fx k g is bounded, the above relations imply that
RRR 35-99 Page 19
Now, suppose for the purposes of contradiction that (20) does not hold. Then, for some
must be an infinite set K ae N and an ffl ? 0 such that
is bounded, there exists a refined subsequence K 0 ' K such that fx k g K 0 is
convergent, with limit -
imply that g i (y k ) !K 0 \Gamma1. Since Lemma 2.5 asserts that fi k
is bounded, we can
conclude that i k
\Gamma1. However, this divergence would imply that x k
i should be 0 for
infinitely many k 2 K 0 ' K, once again a contradiction of (23). Therefore,
lim
and (20) holds.
Finally, we prove that fg 0 (y k )g converges to the optimal value. We may use (17), (18),
and the chain rule to see that y k minimizes the Lagrangian corresponding to the primal
problem with the fixed multiplier x k . Hence,
Let \Gammaf   denote the dual optimal value, which is equal to the primal optimal value since
there is no duality gap. Theorem 3.7 states that f(x k Taking limits in (25) and
using (24), it follows that
lim
The feasibility and optimality of the accumulation points of fy k g are then consequences of
the continuity of g i ,
Finally, it is natural to seek conditions under which the penalized subproblems (17) must
have solutions, and the primal sequence fy k g is bounded. The following result addresses
these questions under the standard assumption of a bounded solution set:
Theorem 3.10 Suppose that the primal solution set is bounded. Given any ff k ? 0 and
exist satisfying the recursions (17)-(18). Moreover, the primal
sequence fy k g is bounded.
Proof. For the first assertion, it suffices to show that the penalized problems (17) have
solutions. Given any closed proper convex function /, we define its recession function /1
via dom/ may be chosen arbitrarily [24,
Theorem 8.5]. The boundedness of the primal solution set is equivalent [7, Section 5.3] to:
Page 20 RRR 35-99
Thus, the existence of a solution to (17) is a corollary of Lemma A.5 in the appendix, along
with the sum rule for recession functions [24, Theorem 9.3].
We now prove that fy k g is bounded. Theorem 3.9 shows that the sequences fg i (y k )g,
above. From (27), unboundedness of fy k g would imply that
. But such unboundedness would contradict g 0 (y k )'s
convergence to the optimal value. 2
We remark that the penalty parameter adjustment rule (16), as discussed in Section
2.2.2, essentially subsumes, in a context broader than '-divergences, the corresponding rules
described in [32] for the exponential method of multipliers and in [5, 3, 4] for a general
'-divergence setting.
We end this section giving some examples of d \Phi
functions that may be derived from
separable Bregman distances (see Section 2.2.1). Further examples may be obtained from [21,
28]. For a Bregman-derived distance, we have d i
whence
d \Phi
where h \Phi denotes the standard monotone conjugate of h. Note that when such a d \Phi
used in the minimization operation in (17), the additive terms h i (w are constant
and may be discarded. The following examples may now be easily verified:
may be disregarded; this choice gives the classical quadratic method of multipliers for
inequality constraints.
where the \Gammaw i term may be
disregarded, yielding the exponentional method of multipliers.
4 Bregman Interior Point Proximal Methods for Variational
Inequalities
We now turn our attention to the box-constrained variational inequality problem (2), where
(possibly set-valued) maximal monotone operator. In this section, we
confine ourselves to Bregman distances, as defined in Section 2.2.
We augment Assumption 2.2 as follows:
RRR 35-99 Page 21
Assumption 4.1 T is maximal monotone, the solution set of (2) is non-empty, and there
exists some e
Our goal is to show convergence of an approximate version of the iteration (4), without
further conditions on T . We modify and extend Assumption 2.7 as follows:
Assumption 4.2 For have the same properties
specified in Assumption 2.7, and furthermore, h i is continuous on [a
defining
4.2.1. For all x 2 B and ff 2 R, the level set fy 2 int B j D h (x; y) - ff g is bounded.
4.2.2. If fx k g ae int B converges to x 2 R n , then lim k!1 D h (x; x k
4.2.3. rge h
Note that at finite a i 's and b i 's, the corresponding h i is now required to take a finite
value. The algorithm can now be stated:
Box Interior Proximal Point Algorithm (BIPPA)
1. Initialization: Let
2. Iteration: Choose ff k such that ff k - c maxf1; h 00(x
)g. Find vectors
repeat the iteration.
4.1 Convergence analysis
First, we cite a result showing that the iteration step of BIPPA is well defined:
Lemma 4.3 [13, Theorem 4(i)] Under Assumption 4.2, there is a unique point x k+1 that
solves the iteration step (28) of the BIPPA with e
We note that it is shown in the unpublished dissertation [28] that (28) has a unique exact
solution even if Assumption 4.2.3 does not hold. This result permits one to dispense completely
with Assumption 4.2.3. However, the proof, while essentially a minor modificiation
of that of [1, Theorem A.1], is quite involved, so we do not include it here.
To guarantee the convergence of the BIPPA, we must assume some vanishing behavior
for fe k g; we will use the assumptions of [14]. Although not as general as the criterion
used in RPMM, these conditions are better suited to our analysis, since they will permit
us to use properties associated with Fej'er monotonicity, and are still feasible to enforce
computationally.
Page 22 RRR 35-99
Assumption 4.4 [14] The error sequence fe k g conforms to:X
exists and is finite.
Note that this assumption implies that Assumption 2.3.1 holds
with k1 . We now state some necessary lemmas:
Lemma 4.6 If Assumption 4.4 holds, then the sequence fx k g is bounded and D h
Proof. The result will follow from [14, Lemma 3] once we show that, for z 2 (T +NB
E(z)
exists and is finite. But,X
and Assumption 4.4 implies that the right hand side of this relation is finite. Hence,
exists and is finite. Using Assumption 4.4 once more, we conclude that
E(z) exists and is finite. 2
We also use a key result from Solodov and Svaiter [29]:
Theorem 4.7 [29, Theorem 2.4] Let h i satisfy Assumption 4.2. Given two sequences fx k g ae
B and fy k g ae int B, either one of which is convergent, with lim k!1 D h
the other sequence also converges to the same limit.
This theorem implies that
Bregman function in the classical
sense [8, 10]. Using Theorem 4.7 and Lemma 4.6, we derive:
Corollary 4.8 Under Assumptions 4.1, 4.2, and 4.4, fx k g has at least one limit point.
Moreover, if for some infinite set K ' N, we have x k !K -
x, then x
x. Therefore,
Assumption 2.3.2 holds.
RRR
Before presenting the main convergence theorem for the BIPPA, we present a final technical
lemma that will help us to prove the uniqueness of the accumulations points of fx k g.
Lemma 4.9 Under Assumption 4.4, for all z converges to a
value in [0; +1) which we will denote by d(z).
Proof. Consider any z 2 (T implies that (29) holds. Using
Assumption 4.4 and D h the hypotheses of Lemma 3.5 are satisfied with
a converges, necessarily to
a nonnegative value. 2
Now, the main convergence theorem follows:
Theorem 4.10 Under Assumptions 4.1, 4.2, and 4.4, fx k g converges to a solution of
Proof. Let -
x be an accumulation point of fx k g, i.e. x k !K - x, for some infinite set K ' N.
Such a point exists by Lemma 4.6. From Theorem 2.6,
We now prove the uniqueness of the limit point: from Assumption 4.2.2, we know that
as defined in Lemma 4.9, is zero. Suppose that fx k g has
another accumulation point x k !K 0 x 0 for some infinite set K 0 ' N. We then have that
it follows from Theorem 4.7 that x
Another possible application of our fundamental analysis is to try to generalize the idea
of adding the square of the Euclidean norm and an arbitrary generalized distance to obtain
Fej'er monotonicity to solutions of (2), as in [2, 3] for the special case of '-divergences. The
difficulty here is to generalize the condition that defines the class \Phi 2 in [3]. This topic is the
subject of ongoing research.



--R

An interior-proximal methods for convex linearly constrained problems and its extension to variational problems
A logarithmic-quadratic proximal method for variational inequalities
Interior proximal and multiplier methods based on second order homogeneous kernels.
Modified Lagrangian Methods for Variational Inequality Problems.
Penalty/barrier multiplier methods for convex programming problems.
Nonlinear Programming
Constrained Optimization and Lagrange Multiplier Methods.
The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming.
An interior-point method with Bregman functions for the variational inequality problem with paramonotone operators
An iterative row-action method for interval convex program- ming
The proximal minimization algorithms with D-functions
A convergence analysis of proximal-like minimization algorithms using Bregman functions
Nonlinear proximal point algorithms using Bregman functions
Approximate iterations in Bregman-function-based proximal algorithms
A Practical General Approximation Criterion for Methods of Multipliers Based on Bregman Distances.
A necessary and sufficient condition to have bounded multipliers in nonconvex programming.
Strict convex regularizations
Augmented Lagrangian methods and proximal points methods for convex optimization.

On the twice differentiable cubic augmented Lagrangian.
Proximal minimization methods with generalized Bregman functions.
Introduction to Optimization.
Extension of Fenchel's duality theorem for convex functions.
Convex Analysis.
Conjugate Duality and Optimization.
Augmented Lagrangians and applications of the proximal point algorithm in convex programming.
Variational Analysis Springer-Verlag
T'opicos em M'etodos de Ponto Proximal.
An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions.
Entropic proximal mappings with applications to nonlinear programming.
Convergence of proximal-like algorithms
On the convergence of the exponential multiplier method for convex programming.
--TR

--CTR
Alfred Auslender , Paulo J. Silva , Marc Teboulle, Nonmonotone projected gradient methods based on barrier and Euclidean distances, Computational Optimization and Applications, v.38 n.3, p.305-327, December  2007
Paulo J. Silva , Jonathan Eckstein, Double-Regularization Proximal Methods, with Complementarity Applications, Computational Optimization and Applications, v.33 n.2-3, p.115-156, March     2006
convex programming;varphi-divergence;proximal algorithms;variational inequalities;bregman distances