...onto hyperplane. The latter permits to consider a fixed relative error criterion for the proximal step. We provide various sets of conditions ensuring the global convergence of this algorithm. The analysis is valid for nonsmooth data in infinite-dimensional Hilbert spaces. Some examples are presented, focusing on penalty/barrier methods in convex programming. We also show that some results can be adapted to the zero-finding problem for a maximal monotone operator.

Key words: parametric approximation; diagonal iteration; proximal point; hybrid method; global convergence

MSC2000 subject classification: Primary: 90C25, 65K05; secondary: 49M30, 90C51

OR/MS subject classification: Primary: programming; secondary: nonlinear, algorithms

History: Received October 27, 2004; revised April 4, 2005.

1. Introduction. Throughout this paper, H stands for a real Hilbert space. The scalar product and norm in H are, respectively, denoted by and [parallel]*[parallel]. Let [[GAMMA].sub.0](H) be the class of all the extended-real-valued functions f: H [right arrow] [??] [union] {[infinity]} such that f is l.s.c. (lower semicontinuous), proper (i.e., f [not equivalent to] [infinity]) and convex. If f [member of] [[GAMMA].sub.0](H), the effective domain of f is given by dom f = {x [member of] H | f(x) [less than or equal to] f(y) + [delta]}, where [delta] [greater than or equal to] 0.

Let [bar.f] [member of] [[GAMMA].sub.0](H) and suppose that Argmin [bar.f], the set of all the minimizers of [bar.f], is nonempty. Given a sequence [([f.sub.k]).sub.k [member of] [??]] [subset] {[GAMMA].sub.0](H) of functions converging, in a sense to be made precise later, to [bar.f] as k [right arrow] [infinity], we consider the sequences [([x.sup.k]).sub.k [member of] [??]] [subset] H which are generated by the following diagonal hybrid projection-proximal point algorithm (DHP-PPA):

** Proximal step. Given [x.sup.k] [member of] H, [[lambda].sub.k > 0, [[delta].sub.k] [greater than or equal to] and [[rho].sub.k] [member of] (0, 2), find [z.sup.k] [member of] H such that

([z.sup.k] - [x.sup.k])/[[lambda].sub.k] + [g.sup.k] = [[xi].sup.k] for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], (1)

where

[z.sup.k.sub.[rho]] = [z.sup.k]/[[rho].sub.k] + (1 - 1/[[rho].sub.k])[x.sup.k], (2)

and the residue [[xi].sup.k] [member of] H is required to satisfy the following condition:

[parallel][[xi].sup.k][parallel] [less than or equal to] [sigma][square root of [[parallel][z.sup.k] - [x.sup.k][parallel].sup.2]/[[lambda].sup.2.sub.k] + [[parallel][g.sup.k][parallel].sup.2]], (3)

where [sigma] [member of] [0, 1) is a fixed relative error tolerance.

** Projection step. If [g.sup.k] = then set [x.sup.k+1] = [x.sup.k]; otherwise, take

[x.sup.k+1] = [x.sup.k] - [[beta].sub.k]][g.sup.k] with [[beta].sub.k] = /[[parallel][g.sup.k][parallel].sup.2]. (4)

Let k [left arrow] k + 1 and return to the proximal step.

The algorithm could be called an "inexact" HPPA, but we prefer to name this algorithm "diagonal" because a single hybrid projection-proximal iteration is applied to [f.sub.k], and then the objective function is updated to [f.sub.k+1]. Because [f.sub.k] [right arrow] [bar.f] as k [right arrow] [infinity], this procedure is expected to approach the set Argmin f. In this paper, we focus our attention on obtaining general conditions ensuring the convergence of [([x.sup.k]).sub.k [member of] [??]] toward a minimizer of [bar.f], under the following hypotheses on the parameters:

[summation][[lambda].sub.k][[delta].sub.k] < [infinity], (5)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (6)

To motivate the DHP-PPA, we begin by noticing that if [[delta].sub.k] = then (1) and (2) amount to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (7)

where the single-valued function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: is the resolvent of [differential][f.sub.k] of parameter [lambda] Brezis [17]. If in addition [[xi].sup.k] = then, by (4), [x.sup.k+1] = [z.sup.k], and it follows from (7) that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Taking [[rho].sub.k] [equivalent to] 1 we recover an exact iteration of the standard PPA, introduced in Martinet [44] for solving some variational inequalities. When [[rho].sub.k] [member of] (0, 2), this becomes an iteration of the relaxed PPA that was introduced in Gol'shtein [31] (see also Gol'shtein [32, 33] for more details) for speeding up convergence; see Bertsekas [15, pp. 129-131] and Eckstein and Ferris [26] for some illustrations of such an accelerating effect in the case of over-relaxation, that is, when [[rho].sub.k] [member of] (1, 2). In the case where the approximate subdifferential [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is replaced by A: H ?? H, a fixed maximal monotone operator (see Brezis [17, [section]5]), global convergence of the standard PPA toward a solution to [member of] A(x) was established in Rockafellar [53], permitting some inexact iterations under summability conditions on the errors. Similar results were obtained in Eckstein and Bertsekas [25] for the relaxed PPA. Specific convergence results for convex minimization, where one is interested in solving the stationary point condition [member of] [differential][bar.f](x), were investigated in Correa and Lemarechal [24], Guler [35], and Rockafellar [54]. In this minimization context, finite bundle methods to find approximate PPA iterates have been studied for nonsmooth data Auslender [9], Bonnans et al. [16], and Hiriart-Urruty and Lemarechal [36].

On the other hand, (4) is a projection step because it can be written as [x.sup.k+1] = [P.sub.k][x.sup.k], where [P.sub.k]: H [right arrow] H is the orthogonal projection operator onto the hyperplane {x [member of] H | = 0}. By monotonicity and Lemma 2.2(ii) below, the latter separates the current iterate [x.sup.k] from the stationary set [S.sub.k] = {x [member of] H | [member of] [differential][f.sub.k](x)}. Thus, in this algorithm the proximal iteration is used to construct this separating hyperplane, the next iterate [x.sup.k+1] is then obtained by a trivial projection of [x.sup.k], which is not expensive at all from a numerical point of view. The hyperplane projection method was first proposed in Konnov [40] with the name "combined relaxation"; see also Konnov [41] and Facchinei and Pang [28, Chap. 12] for more details. Taking ([[delta].sub.k] = and [[rho].sub.k] = 1, (1)-(4) corresponds to one iteration of the hybrid projection-proximal point algorithm (HP-PPA) proposed in Solodov and Svaiter [55] for the maximal and monotone inclusion problem [member of] A(x). It is shown in Solodov and Svaiter [55] that HP-PPA has the remarkable property of permitting the fixed relative error tolerance [parallel][[xi].sup.k][parallel][less than or equal to] [sigma] max{[parallel] [z.sup.k] - [x.sup.k][parallel]/[[lambda].sub.k],[parallel][g.sup.k][parallel]}, a less stringent condition than summability of errors, without affecting the global convergence of the algorithm. This result was improved in Solodov and Svaiter [56] by considering (3) as the error tolerance. Under such fixed relative error tolerances, the hyperplane projection is in general necessary to ensure the boundedness of the iterates Solodov and Svaiter [55, p. 62], even for minimization problems in which A = [differential][bar.f] Garciga et al. [30].

In Alvarez [3] it is shown that some accelerating techniques, including relaxation, can be combined with HP-PPA iterations to obtain a globally convergent scheme for the inclusion problem [member of] A(x). In particular, the results of Alvarez [3] and Solodov and Svaiter [55] can be used to solve directly the stationary point condition [member of] [differential][bar.f](x). However, when [bar.f] is not strongly convex, when it has an irregular behavior due to nonsmooth data, or when there are implicit constraints in its definition, it is a common practice to approximate [bar.f] by a sequence [([f.sub.k]).sub.k [member of] [??]] [subset] [[GAMMA].sub.0](H) of better behaved functions (e.g., viscosity methods, Tikhonov's regularization, smoothing techniques, penalty/barrier methods). Relying on such an approximating sequence, diagonal algorithms perform a prescribed number of iterations of an optimization method applied to [f.sub.k] and then update the objective function to [f.sub.k+1], which is expected to be closer to [bar.f]. This is the case of (1)-(4), where a single iteration of the HP-PPA is applied to [f.sub.k], then we continue with [f.sub.k+1].

The diagonal approach has already been considered by several authors through purely proximal iterations. The first work in this direction seems to be Kaplan [38], where the author investigates the combination of the PPA iteration with a class of interior penalties; see Kaplan [39] for more recent results. See Auslender et al. [11] for some exterior penalties, and Alart and Lemaire [1], Bahraoui and Lemaire [12], and Lemaire [42, 43] for extensions via variational convergence methods. See Mouallif [47] for different regularization-penalty methods and Moudafi [50] for some results on Tikhonov's regularization. A two-parameter exponential penalty-PPA for convex programs can be found in Mouallif and Tossings [48, 49]. See Cominetti [20] for general results exploiting the existence of "central/optimal paths" together with applications to the log-barrier and the exponential penalty in linear programming. For improvements, extensions, and primal-dual convergence results, see Alvarez and Cominetti [4] and Cominetti and Courdourier [22]. Although some of these works consider a residual error [[xi].sup.k] as in (1), they all require the sequence of errors to satisfy a summability condition (cf. (20)), a rather restrictive hypothesis for practical implementations. As already mentioned, the advantage of DHP-PPA is the fixed relative error criterium (3).

This paper is organized as follows. In [section] 2, we discuss the well-definedness of the sequences [([x.sup.k]).sub.k [member of] [??]] generated by (1)-(4) and establish some preliminary lemmas. In [section] 3, we prove a general convergence result, whose potential applications as well as its drawbacks are illustrated through some examples. In [section] 4, we investigated the special case of one-parameter approximation schemes, providing convergence results under "fast" or "slow" parametrization conditions that complete and improve the general result of [section] 3; examples are given for penalty/barrier methods in convex programming. Finally, in [section] 5, we briefly discuss some extensions to the zero-finding problem for maximal monotone operators.

2. Preliminaries. Consider a family of functions [([x.sup.k]).sub.k [member of] [??]] [subset] [[GAMMA].sub.0](H). Let us begin with a brief discussion on the well-definiteness of the sequences [([x.sup.k]).sub.k [member of] [??]] generated by (1)-(4).

Given k [greater than or equal to] 0, let us introduce the auxiliary objective function

[[phi].sub.k](x) = [1/[2[[lambda].sub.k]]][[parallel]x - [x.sup.k][parallel].sup.2] + [[rho].sup.2.sub.k][f.sub.k](x/[[rho].sub.k] + (1 - 1/[[rho].sub.k])[x.sup.k]),

which is strongly convex and coercive. Therefore, [[??].sub.k] admits a unique global minimizer, which we denote by [y.sub.k] and is characterized by the stationary condition [member...

NOTE: All illustrations and photos have been removed from this article.



More articles from Mathematics of Operations Research
Some P-properties for nonlinear transformations on Euclidean Jordan al..., November 01, 2005
Single-machine scheduling with precedence constraints., November 01, 2005
Expected residual minimization method for stochastic linear complement..., November 01, 2005

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.