An incremental method for solving convex finite min-max problems

• 成果类型: Article
• 署名作者: Gaudioso, M; Giallombardo, G; Miglionico, G
• 署名单位: University of Calabria
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0175
• 发表日期: 2006
• 页码: 173-187
• 关键词: minimax problem; optimization; PROGRAMS

摘要

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.