An incremental method for solving convex finite min‐max problems

An incremental method for solving convex finite min‐max problems

0.00 Avg rating0 Votes
Article ID: iaor200928576
Country: United States
Volume: 31
Issue: 1
Start Page Number: 173
End Page Number: 187
Publication Date: Feb 2006
Journal: Mathematics of Operations Research
Authors: , ,
Keywords: minimax problem
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.

Reviews

Required fields are marked *. Your email address will not be published.