...proposed, which not require at the current point the evaluation of the actual value of the objective function, namely, of all the component functions, thus extending to min-max problems the philosophy of the incremental approaches, widely adopted in the nonlinear least squares literature. Given the nonsmooth nature of the problem, we resort to the well-established machinery of "bundle methods" We provide global convergence analysis of our method, and in addition, we study a subgradient aggregation scheme aimed at simplifying the problem of finding a tentative step. This paper is completed by the numerical results obtained on a set of standard test problems.

Key words: unconstrained optimization; incremental methods; online algorithms; convex minimization; finite rain-max; cutting planes; nonsmooth optimization; bundle methods

MSC2000 subject classification: Primary: 90C25, 90C47

OR/MS subject classification: Primary: programming/nondifferentiable, nonlinear algorithms; secondary: mathematics/ convexity, piecewise linear

History: Received November 2, 2004; revised May 9, 2005.

1. Introduction. The practical need of solving min-max problems, i.e., the special type of minimization problems where the objective function is defined through a maximization operation, has provided the strongest motivations to the development of the nonsmooth optimization methods and of the related theory. We particularly refer the reader to the seminal book on the min-max theory and algorithms by Demyanov and Malozemov [3], and to the paper by Polak [16] where motivations for studying such problems are presented in details.

Min-max problems can be dealt with by adopting diverse approaches such as general-purpose nonsmooth optimization algorithms (see, for example, Makela and Neittaanmaki [14], Hiriart-Urruty and Lemartchal [10], Gaudioso [6], and the references therein), "ad hoc" algorithms (see, for example, Hald and Madsen [9]), and algorithms based on transformations into constrained optimization problems (see, for example, Di Pillo et al. [4, 5]).

In this paper, we focus our attention on the following convex finite min-max problem:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where we assume that each "component" function [f.sub.i]: [R.sup.n] [right arrow] R is convex and not necessarily differentiable.

Our approach belongs to the class of the "ad hoc" methods for tackling min-max problems. It is an iterative descent method strongly connected to the cutting plane (Cheney and Goldstein [2] and Kelley [11]) and the bundle approach (Hiriart-Urruty and Lemardchal [10]) to nonsmooth minimization problems.

Any iterative approach to rain-max problems is typically expected to require at each step the evaluation of the "max" function at the current point. Of course, evaluating such function at the current point requires, in turn, to evaluate every component function [f.sub.i] at the same point.

The latter remark gives us the main motivation for devising iterative methods working on the basis of incomplete knowledge of the "max" function. In fact, our aim is to design an algorithm that need not require the evaluation of all the component functions at the same point. From this point of view, our approach evokes the so-called "incremental" approach to minimize a function consisting of the sum of a (large) number of component functions, such problems usually arising in several fields of applied optimization like neural networks training, nonlinear least squares problems, and Lagrangian relaxations of integer programs. In fact, the term "incremental" is justified by the fact that in such methods, information related to just one component function is evaluated at each step (see, for example, Bertsekas and Tsitsiklis [1] for a general discussion on the online/incremental approaches, Grippo [8], and Nedic and Bertsekas [15] for the analysis of the convergence properties and for an extensive bibliography).

Focussing on convex nonsmooth problems, it seems worth noting that some interest has been recently devoted (see Nedic and Bertsekas [15] and the references therein) to devising incremental methods for solving problems where the objective function is the sum of several convex functions, each being individually nonsmooth. To this aim, incremental versions of the classical subgradient method (see Hiriart-Urruty and Lemartchal [10]) for nonsmooth optimization have been introduced. We refer the reader to an interesting study of the theoretical properties of some incremental subgradient methods, based on different stepsize update rules and possibly encompassing randomization techniques, which is presented in Nedic and Bertsekas [15].

However, apart from the common background philosophy of the online/incremental approaches, our paper, at the best of our knowledge, shares no further significant features with the existing literature on incremental optimization. First, we notice that in our case, the objective function is no longer the sum of many nonsmooth convex function, but the maximum over finitely many convex functions, and that the "max" operator typically induces nonsmoothness of such objective function, irrespective of possible smoothness of all the component functions. Furthermore, we will not make use of subgradient methods, and will rather prefer to focus on bundle-type approaches, trying to exploit their well-known enhanced feature in the field of nonsmooth optimization.

This paper is organized as follows. In [section] 2, we describe the main ideas of our approach; namely, we introduce a cutting plane framework based on the new concept of partial cutting plane function, particularly suitable to embed the incremental philosophy into the bundle approach to solving min-max problem. A formal description of the algorithm is provided in [section] 3, while global convergence analysis is discussed in [section] 4. A possible subgradient aggregation scheme is introduced in [section] 5, along with a brief discussion on the solution, in closed form, of the simple quadratic programming problem (QP) occurring when aggregation is adopted (a detailed description of a related algorithm is provided in the Appendix). Finally, numerical results are presented in [section] 6.

The following notations are adopted throughout this paper. We denote by [parallel] * [parallel] the Euclidean norm in [R.sup.n], and by [a.sup.T]b the inner product of the vectors a and b. The subdifferential of a convex function f: [R.sup.n] [right arrow] R at any point x is denoted by [differential]f(x), and the [epsilon]-subdifferential of f at x is denoted by [[differential].sub.[epsilon]]f(x).

2. An incremental cutting plane framework. We consider the following unconstrained minimization problem of the rain-max type:

(1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

where f: [R.sup.n] [right arrow] R is the pointwise maximum over all the functions [f.sub.i]: [R.sup.n] [right arrow] R, with i [member of] I [??] {1, ..., m}; that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

We assume that each function [f.sub.i] is convex and not necessarily differentiable. In the following, we will refer to the functions [f.sub.i]s as to the component functions, and to the set I as the function index set.

As previously outlined, our aim is to design an iterative method that need not require the evaluation of all the component functions of f at the same point, i.e., that works on the basis of "incomplete knowledge" of the objective function f.

Throughout this paper, we will make wide use of the main features of cutting plane approaches for the minimization of convex, possibly nondifferentiable functions. Indeed, the iterative methods we will introduce later in [subsection] 3 and 5, fall into the well-known class of bundle methods for nonsmooth optimization.

As usual in cutting plane methods for minimizing convex functions, suppose we are given any set of points [x.sub.k] [member of] [R.sup.n], k = 1, ..., j. Such points allow to generate a lower piecewise model of the objective function f, as the pointwise maximum over all the affine lower approximations f([x.sub.k]) + [g.sup.T.sub.k] (x - [x.sub.k]), once at each point [x.sub.k] the value f([x.sub.k]), and a corresponding subgradient [g.sub.k] [member of] [differential]f([x.sub.k]) are calculated. Such a model has the nice property to interpolate the function f at each point [x.sub.k]; any cutting plane method is then based on iteratively improving the model to obtain an approximation getting closer and...

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



More articles from Mathematics of Operations Research
Upward slopes and inf-convolutions.(axioms of cooperative production g..., February 01, 2006
Relative frequencies of generalized simulated annealing.(analysis of s..., February 01, 2006

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.