On the Conversion of Optimization Problems with Max-Min Constraints to Standard Optimization Problems

Abstract

We consider the problem of minimizing a real-valued function f 0 (x)subject to max-min constraints, i.e., constraints of the form ${\rm max}_{k\in{\bf r}}{\rm min}_{j\in{\bf q}_k} f_k^j(x) \le 0$, where for any integer r, ${\bf r} \mathrel{\buildrel\Delta\over={1,,...,r}, so that for any k \in {\bf r,\, q}_k ={1,...,qk }. Problems with this kind of constraint arise in a variety of applications, such as design of electronic circuits subject to manufacturing tolerances and postmanufacturing tuning and optimal steering of mobile robots in the presence of obstacles. An optimization problem with max-min constraints is equivalent to a collection of optimization problems with smooth inequality constraints. This collection can be very large, and hence solving an optimization problem with max-min constraints by solving each member of the collection can be exorbitantly expensive. We present a transcription of problems of this type into a single inequality constrained nonlinear programming problem with smooth constraints, which can be solved using readily available software. The transcription is based on the fact that a set of real numbers contains a nonpositive element if and only if its convex hull contains a nonpositive element. While this fact is fairly obvious, establishing a correspondence between the global and local minimizers of the original problem and those of the problem resulting from our transcription turned out to be quite difficult. The significant advantages of using our transcription are demonstrated by the numerical examples that are included in the paper to illustrate the effectiveness of our approach.