Adaptive Approximations and Exact Penalization for the Solution of Generalized Semi-Infinite Min-Max Problems

Johannes O. Royset1 and Armen Der Kiureghian2
(Professor Elijah Polak)
Norwegian Research Council, (NSF) ECS-9900985, and Space Sciences Laboratory-Lockheed Martin Mini-grant Program

We develop an implementable algorithm for the solution of a class of generalized semi-infinite min-max problems. To this end, first we use exact penalties to convert a generalized semi-infinite min-max problem into a finite family of semi-infinite min-max-min problems. Second, the inner min-function is smoothed and the semi-infinite max part is approximated, using discretization, to obtain a three-parameter family of finite min-max problems. Under a calmness assumption, we show that when the penalty is sufficiently large the semi-infinite min-max-min problems have the same solutions as the original problem, and that when the smoothing and discretization parameters go to infinity the solutions of the finite min-max problems converge to solutions of the original problem, provided the penalty parameter is sufficiently large.

Our algorithm combines tests for adjusting the penalty, the smoothing, and the discretization parameters and makes use of a min-max algorithm as a subroutine. In effect, the min-max algorithm is applied to a sequence of gradually better-approximating min-max problems, with the penalty parameter eventually ceasing to increase, but the smoothing and discretization parameters driven to infinity. A numerical example demonstrates the viability of the algorithm.

1Graduate Student (non-EECS)
2Outside Adviser (non-EECS)

Send mail to the author : (joroyset@ce.berkeley.edu)


Edit this abstract