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. A descent algorithm is proposed, which need 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.

An incremental method for solving convex finite min-max problems

GAUDIOSO, Manlio;GIALLOMBARDO, Giovanni;Miglionico G.
2006-01-01

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. A descent algorithm is proposed, which need 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.
2006
unconstrained optimization; incremental methods; online algorithms; convex minimization; finite min-max; nonsmooth optimization
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/139757
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 36
  • ???jsp.display-item.citation.isi??? 34
social impact