An incremental method for solving convex finite minmax problems

Manlio Gaudioso (gaudiosodeis.unical.it)
Giovanni Giallombardo (giallodeis.unical.it)
Giovanna Miglionico (gmiglionicodeis.unical.it)

Abstract: We introduce a new approach to minimizing a function defined as the pointwise maximum over finitely many convex real functions (next referred to as the "component functions"), with the aim of working on the basis of "incomplete knowledge" of the objective function. In fact, a descent algorithm is proposed which does not necessarily require at the current point the evaluation of the actual value of the objective function, i.e., of all the component functions, thus extending to minmax problems the philosophy of the incremental and the online approaches, widely adopted in the nonlinear least squares literature. Since the finite minmax optimization problem is of the nonsmooth type, we resort to the well established machinery of the "bundle methods." We provide global convergence analysis of our method and in addition we study a subgradient aggregation scheme which allows us to provide a version of the method where the problem of finding a tentative step is drastically simplified. The paper is completed by the numerical results obtained on a set of standard test problems.

Keywords: Unconstrained optimization, online algorithms, convex minimization, finite minmax, cutting planes, nonsmooth optimization, bundle methods

Category 1: Convex and Nonsmooth Optimization

Citation: Mathematics of Operations Research, 31(1), 173-187, 2006.

Download:

Entry Submitted: 12/14/2004
Entry Accepted: 12/14/2004
Entry Last Modified: 03/20/2006

Modify/Update this entry