Mathematical Programming 54 (1992) 155-176 North-Holland
155
A barrier function method for minimax problems E. Polak a...
12 downloads
549 Views
1MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Mathematical Programming 54 (1992) 155-176 North-Holland
155
A barrier function method for minimax problems E. Polak and J.E.
Higgins
Department of Electrical Engineering and Computer Sciences and the Electronics Research Laboratory, University of California, Berkeley, CA 94720, USA
D.Q.
Mayne
Department of Electrical Engineering, Imperial College, London SW7 2BT, UK
Received 25 October 1988 Revised manuscript received 14 March 1990
This paper presents an algorithm based on barrier functions for solving semi-infinite minimax problems which arise in an engineering design setting. The algorithm bears a resemblance to some of the current interior penalty function methods used to solve constrained minimization problems. Global convergence is proven, and numerical results are reported which show that the algorithm is exceptionally robust, and that its performance is comparable, while its structure is simpler than that of current first-order minimax algorithms. Key' words: Barrier function methods, interior penalty methods, minimax algorithms, engineering design, nondifferentiable optimization.
I. Introduction F o l l o w i n g K a r m a r k a r ' s s p e c t a c u l a r success in utilizing a b a r r i e r f u n c t i o n t e c h n i q u e in his l i n e a r p r o g r a m m i n g a l g o r i t h m [ 17] there has b e e n a flutter o f activity r e e v a l u a t ing h o m o t o p y a n d b a r r i e r f u n c t i o n m e t h o d s for b o t h l i n e a r a n d n o n l i n e a r p r o g r a m m i n g (see, e.g., [8, 9, 14, 15, 30, 31, 35]). Barrier f u n c t i o n m e t h o d s have c o n s i d e r a b l e p o t e n t i a l for solving m i n i m a x p r o b l e m s arising in e n g i n e e r i n g design (see, e.g., [24] for a d i s c u s s i o n o f these p r o b l e m s ) . These p r o b l e m s are often semi-infinite; in a d d i t i o n , b e c a u s e o f their c o m p l e x i t y , c o m p u t a t i o n o f the g r a d i e n t s o f the c o m p o n e n t f u n c t i o n s (of the m a x f u n c t i o n ) is expensive, while c o m p u t a t i o n o f H e s s i a n s is often i m p r a c t i c a l . F r e q u e n t l y , only feasibility is r e q u i r e d , in w h i c h case the a d v a n t a g e s o f h i g h e r o r d e r m e t h o d s over first-order m e t h o d s are s u b s t a n t i a l l y r e d u c e d . In c o m p u t e r - a i d e d - d e s i g n a p p l i c a t i o n s , run times o f over 100 h o u r s are not i n f r e q u e n t ; h e n c e a l g o r i t h m s w h i c h m a y fail to converge, even to a l o c a l solution, are d e e m e d This research was supported by the National Science Foundation grant ECS-8517362, the Air Force Office Scientific Research grant 86-0116, the California State MICRO program, and the United Kingdom Science and Engineering Research Council.
E. Polak et al. / A barrier function method for minimax problems
156
undesirable. Ondine applications are increasingly more common, for example, optimization for control of batch processes (see, e.g. [25]). In such applications, algorithms must be implemented using microprocessors or dedicated VLSI chips, and hence there is a premium on algorithms that are simple and that do not call massive subroutines. Very few algorithms successfully address these engineering problems. We present in this paper a barrier function method which constructs solutions to semi-infinite minimax problems under hypotheses which are much less restrictive than those required by nearly all existing algorithms. The new algorithm has a simple structure and it requires small memory (it does not utilize, for example, linear or quadratic programming subroutines). Furthermore, it has very strong theoretical and experimental convergence properties. Hence it meets the major criteria for engineering applications. The numerical performance of the new algorithm is, in most of the examples studied, superior or comparable to that of the only other first-order algorithm (Algorithm 5.2 in [24]) which can solve semi-infinite minimax problems of the same generality. Significantly, it is less affected by ill-conditioning than Algorithm 5.2 in [24]: it computes solutions for problems on which Algorithm 5.2 in [24] fails because of ill-conditioning. When applied to finite minimax problems, it is again distinguished by exceptional robustness: it does not fail on many problems which cause several excellent competing algorithms to fail. On more benign problems its performance is either comparable or not significantly inferior to that of other first-order minimax algorithms. We address the minimax problem: MMP:
min 0(x),
(1.1a)
XE~ n
where the function ~O: ~ ~ ~ is defined by
tO(x)&max(fl(x)'''" ' fro(x)' max, cEo.ll q~l(x' t)
. . . .
'
4)t(x,t)),
,c[o,llmax
(1.1b)
and the component functions f i :N,, ~ R and 4)j :R n x [0, 1] -~ ~ satisfy certain continuity hypotheses. Engineering design problems often have at least one max-function ( 4 / ( . , . ) ) , arising from, for example, constraints on time or frequency responses. In addition, in many cases the presence of measurement and modeling inaccuracies often means that it is not worthwhile obtaining accurate solutions. The essential features of the barrier function algorithm can be explained by considering the case of MMP where O(" ) is defined in terms of a single function, i.e., O(x)& max qS(x, t).
(1.2a)
tc[O,l]
The barrier function employed in our algorithm is defined by
p(x, ~) ~ JEo,ll ( (c~ -
1
&(x, t)) dt,
(1.2b)
E. Polak et al. / A barrierfunction methodfor minimax problems
157
where a > ~(x). For such a, the function p ( - , a ) is continuously differentiable on the set C ( ~ ) a {x ~ 0~" I ~(x ) < 4 .
(1.3)
It is shown later that p ( . , a ) is a barrier function for the set C(cQ, so that, if {cei} is a monotone decreasing sequence which converges to minx~e- g,(x), then the sets argminx,_,,p(x, ai) must converge to argminx~0~, O(x). The conceptual algorithm which, at iteration i, sets ai = 4'(xi) and selects Xi+l as any element in argminx~- p(x, o~) generates such a sequence. Our algorithm is a practical version of the conceptual algorithm, in which, inter alia, exact minimization of p(x, ~ ) is replaced by approximate minimization. Under mild continuity assumptions, all accumulation points generated by the algorithm satisfy first order optimality conditions. The early literature on semi-infinite optimization was devoted to linear problems. A conceptual algorithm for solving nonlinear semi-infinite optimation problems is presented in [23]. The first implementable algorithm for solving nonlinear, nonconvex semi-infinite programs, such as m i n { f ( x ) lO(x) <~w} (with ~p(. ) defined as above, and w = 0), appears in [27], where a first order algorithm is described and global convergence established (all accumulation points satisfy first order conditions of optimality). An improved version of the algorithm [10] has been extensively used in complex control design problems. The algorithm can be used to solve minimax problems by re.placing f ( x ) by w, i.e., determining (x, w) to solve min{w I #J(x)~< w}. However, in our experience, probably because the transcribed problem is not as well conditioned, it often takes more time to solve a minimax problem in transcribed form than in original form. A basic assumption, in all the above implemerltable algorithms, is that the sets T j A {tl~J(x *, t) = ~h(x*)}, j c J __a{1, 2 , . . . , l}, are finite at any local solution x* to MMP. ~ With additional assumptions (4~J,(x *, t ) < 0 for all t c T -j, all jc_l), it is possible to obtain quadratically convergent algorithms [13, 20, 28]. Similar results have been independently obtained by Coope and Watson [6], Conn and Gould [5], and others. The only algorithms which dispense with the assumption that the sets T j (of maximizers of qSJ(x*, • )) are finite for all j c_/appear to be Algorithm 5.2 in [24] (a first order method which uses a proximity algorithm to generate search directions) and the algorithm presented in this paper. Global convergence has been established for these algorithms. The literature dealing with the finite minimax problem (#~(x)Aminj~,, f J ( x ) ) is, of course, much more extensive--see, for example, [4, 11, 12, 22, 24, 29, 34] and the references contained therein. Both first and second order algorithms have been proposed; some of the first order algorithms achieve superlinear convergence if the Haar condition is satisfied. However, it is not clear how often this condition is i This assumption is not always valid for engineering design problems with constraints on dynamic responses. For example,it does not hold in the design of obstacle avoidancepaths for robot manipulators.
158
E. Polak et al./ A barrier function method for minimax problems
satisfied in practice. Finally, by transcription into the form min{w IfJ(x) - w <~0, j ~ m},
(1.4a)
one can solve the finite minimax problem using many nonlinear programming algorithms. One can generate a barrier function method for solving (1.4a), which is quite close to our minimax algorithm for the finite minimax problem, by combining the parameter free Fiacco-McCormick penalty function [7], /~(x, w, a) &
1
+ ~
1
ol-w j=lw-fJ(x)'
(l.4b)
with the Mifflin truncation rule [21], IIV/~(xk, Wk, C~k-l)ll ~< K,
(1.4c)
and with the Tremolieres penalty adjustment rule [33], 1 OLk ~- a k - l - ~ - 2 [ W k - I - Olk 1]"
(1.4d)
However, our numerical results in Section 5 show that this method computes considerably slower than our direct minimax algorithm. As we have already mentioned, the performance of our algorithm on finite minimax problems is mainly distinguished by robustness: it is to be used on problems that cause other algorithms to fail. Nevertheless, we expect that the main use for our algorithm will be in solving semi-infinite engineering optimization problems, where it offers advantages of reliability, speed, and ease of on-line implementation. In the next section we describe the conceptual and implementable algorithms and prove that the conceptual algorithm constructs a minimizing sequence. In Section 3, we establish global convergence of the implementable algorithm. The results of our numerical experiments, on both finite and semi-infinite minimax problems, are presented in Section 4. We draw a few conclusions in Section 5.
2. The algorithm We associate with the problem MMP the barrier function
p(x,~) ~-j~m E (a -fJ(x)) l 1 t)) dt, ~-k~, fE0,11(Ce--qSk(X,
(2.1)
where a > ~O(x). However, to simplify the exposition we note that, without loss of generality, we may assume that all the functions in (1.1b) are max-functions, and that ~b(.) is given by O(x) & max(\,~to,umax&l(x,t),... ' ,~[o.ljmax&'(x,t)).
(2.2)
E. Polak et aL / A barrier function method for minimax problems
159
This follows since any "ordinary" function f : R" ~ ~ may be trivally converted into a max-function by defining ~b:~" × [0, 1] ~ to be ~b(x, t ) A f ( x ) . In this case, the barrier function simplifies out to the form p(x, a ) A Z f[ kcl
0,1]
1 (a_q~k(x, t)) dt.
(2.3a)
We will assume that the following hypothesis holds: Assumption 1. For each k ~/, the function ~hk : R" × [0, 1] ~ 0~ is continuous, and has a continuous first derivative V~&k( • , • ). In addition, for each compact S c/~", there exists a finite Ls such that for each x c S, the function ~bk(x, • ) is Lipschitz continuous on [0, 1], with constant Ls. It should be clear that under the above assumptions, the function p(., a) is continuously differentiable on C(o~) for any a such that C ( a ) ~ 0. For any such o~, the derivative of p(., a), is given by Vxp(x, a ) A ~
kcl
It
V~4~(x,t)
0,1]
(a -4~k(x, t)) 2dt"
(2.3b)
For "ordinary" functions, Assumption 1 is equivalent to requiring continuous differentiability. It is straightforward to see, in the finite case, that the function (2.1) is a barrier function for the set C ( a ) . The fact that the function (2.3a) is also a barrier function follows from the following lemma. Some additional notation is necessary at this point. Define the set C by C~={(x, a) c ~"+'/~0(x) < a},
(2.4)
and let the e-active sets Ak(x) c [0, 1], k c / , be defined by A~(x) A {t c[O, 1]lOk(x, t)>~ ~ , ( x ) - e } ,
(2.5)
Lemma 2.1. Suppose that Assumption 1 holds, and that Co is a bounded subset of C. Then there exists a constant L > O, such that for all (x, a ) c Co,
p(x,
L ~)~Z 1 log( 1-~ (~ --~(x)))"
(2.6)
Proof. Since Co is bounded, so is the projection H of Co onto ~". Hence by assumption there exists a Lipschitz constant, L ~ a - f J ( x ) , for all ( x , a ) ~ C o . Let k 6 J be such that Ako(X) is nonempty, let t~ c Ako(x) be given and let t c [0, 1]. Then we have that ~k(x, t)/> ~k(X, t~) -- Lit - txl = tb(x) - Lit - t×[.
(2.7)
160
E. Polak et al. / A barrier function method for minimax problems
Consequently, we have
p(x,~)>~[
1
(2.8)
~ ~o,,~ ( ~ - 6 ~ ( x , t)) dt
o,~l (o, - 4 , ( x ) + L [ t -
i log(( -
1 (
I>-L log
(2.9)
t~l) at
+
+ L(I-
(2.10)
L )
1~
(~ -7(x)}
(2.11)
'
where (2.11) is obtained by minimizing (2.10) with respect to tx.
[]
Consequently, if ~ c R is such that C ( a ) # 0 and {x~}~:~oc C ( a ) is a bounded sequence such that 4,(x~)-+ c~ as i-+oo, then p(xi, c~)-+oo as i-+oo, i.e., p ( . , a ) is indeed a barrier function for C ( a ) . We now establish our conjecture, made in Section 1, that the following conceptual algorithm constructs a minimizing sequence.
Algorithm 1 (Minimizes q,(.)). Data: xo c ~". Step O. Set i = 0. Step 1. Set c~i & q,(x~). Step 2. Compute x~+~e arg minx~c(~,) p(x, c~). Step 3. Replace i by i + 1 and go to Step 1. Let G ~ arg minx~u,, g,(x). We see that Algorithm 1 defines the iteration function A : N" ~ 2 u", defined on the complement of G as follows: A(x)=arg
min
x'EC(4,(x))
p(x',O(x))
ifx~G.
(2.12)
To complete the definition of A(. ), we set
a(x) = d
if x ~ d.
(2.13)
Now suppose that the set C(O(xo)) is bounded, and consider the sequence {xi}~'-o constructed by Algorithm 1. Then, there is an infinite subset K c N and vectors x*, x**, such that xi K_~X* and xi+l ~ x** as i-->co. Since the sequence {O(x~)}~o is monotone decreasing, and since #/(- ) is continuous, we must have that g,(xi) -+ q,(x*), as i-+ co, and hence that q,(x*) = O(x**). For the sake of contradiction, suppose that x * ~ G . Then the set C(O(x*)) is nonempty, and hence for any x'eA(x*), ~(x') < ~0(x*) must hold. Let x'~ A(x*), then it follows that x'c C(~O(xi)) for all i. By construction, p(x~+l, qJ(xi))<~p(x', q,(x~)). Continuity implies that p(x', q,(x~))--> p(x', O(x*)). However, L e m m a 2.1 implies that p(x~+~, q,(x~))-+oo, which yields a contradiction. Hence we must have that x* < G.
E. Polak et al. / A barrier function method for minimax problems
161
To convert Algorithm 1 into an implementable form, we introduce two modifications. First, we relax Step 2, which requires that x~+lc arg minx~c(~0 p(x, cq), by accepting any x~+lc C(a~) which satisfies IIVxp(&+l, ai)[[ ~< K, for some fixed K > 0. Clearly, such an xi+l can be computed in a finite number of operations by means of any number of descent algorithms. Next, because x ~ C(c~) and since an initial point in C(a~) is needed for the computation of x~+l by means of a descent method, we replace the construction in A1 Step 1 by setting ai =~(0(x/ 1) -k- ~b(xi)), and using either xi or xi 1 (whichever has the smaller qJ(. ) value) as an initial point for the routine that computes &+l. It is still possible that 0(x~ 1) = ~b(x~), in which case we increase a~ by a suitably small amount. The resulting implementable algorithm is as follows: Algorithm 2 (Minimizes 0 ( . ) ) . Data: x ~, XoC~ ~, K ~ O , {T~k}kC°=0 such that T / k > 0 , and ~oo k=o Step O. Set i = 0. Step 1. Set
~l(qJ(xi 1) + ~b(x~)) ai =[½(0(xi 1)+ ~b(x,))+ r/i
if q/(Xg_l) ~ tk(xi), if 0 ( x , - 0 = tp(xi),
{x~ if 0(xi-1) I> 0(xi), Yg~ xg_, if ~l(X i 1) ( ~ / ( x i ) "
~ k ~ OO.
(2.14)
(2.15)
Step 2. Using y~ as an initial point, use any method to generate a x~+~c C ( a i ) satisfying IlV~p(x~+,, a~)ll <~ K.
(2.16)
Step 3. Replace i by i + 1 and go to Step 1. Before proceeding with the proofs of convergence, we make the following observations: (i) Step 2, of Algorithm 2, may require a few iterations of a descent method. In an effort to simplify the algorithm, one is tempted to hypothesize that a single iteration of the method of steepest descent (with exact line search restricted to C(ai)), applied to p ( . , cq), instead of the full Step 2, might suffice. Unfortunately, it is possible to show that this strategy does not work, by applying this "one-inneriteration" algorithm to the simple problem min~cR2 max{2x ~+ x 2, -xl}. Note that the function max{2xl+ x 2, - x 1} has no stationary points; in fact, it is unbounded from below. Yet, when initialized with x 1 = (1, 1) v and x0 = (0, 0) T, the "simplified" algorithm constructs a sequence {xi}~o which converges to the point (0.0311889, -0.09555667). (ii) The convergence properties of Algorithm 2 are unaffected when the term ~(tP(xi l)+ O(xi)) in (2.14) is replaced by the term ( ( 1 - p ) O ( x i - l ) +p~b(xi)) for any fixed p ~ (0, 1). However, the proofs of convergence are slightly simpler for the case p =51 and hence we use that value in our analysis.
162
E. Polak et al. / A barrierfunction method for minimax problems
(iii) Because the evaluation of the barrier function may be quite expensive, conjugate gradient methods with an exact line search seem to be unsatisfactory for computing an x~+~ satisfying (2.16). Hence, a reasonable approach seems to be to use an algorithm of the G a u s s - N e w t o n type, which does not require second order derivatives. This algorithm is described in the Appendix. (iv) It is possible, due to the nature of the function p ( . , . ) , that as the iterates (x~, c~_1) approach a solution, the number of inner steps required to satisfy (2.16) grow rapidly. By briefly examining the p r o o f of convergence in Section 3, it can be seen that the test (2.16) in Step 2 can be replaced by the following test which increases precision more slowly than (2.16): Step 2: Use any method to generate an xi+l c C(c~) satisfying
IlVxp(X~+,, ~,)11 ~< K
{
,
}
max 1, ( c ~ - 0 ( x i + 0 ) ~ '
(2.17)
where 6 ~ [0, 1) (in fact, if only "ordinary" functions are present, this condition may be relaxed to requiring that 6 c [0, 2)). (v) The sequence {~/k}k~0 need not be specified completely at the outset. An essential requirement is that whenever 0 ( X i - l ) = O(xi), we have 7h> 0, so that a usable starting point for Step 2 is generated. With this in mind, the sequence {*/k}k°°_-0 may be generated in the following manner. Initially choose some l'0 > 0. In iteration i, if O(x~-l) ~ O(xi), then set 7h = 0 and u~+~= ~,f,otherwise set Th = vi and u~+l = ~,~/1.1. Clearly, the resulting sequence {~/k}k~0 has a convergent sum. (vi) Rather than using y~ as an initial point in Step 2, a variant of a h o m o t o p y method can be used to generate an alternative starting point. Ideally, we would like to compute a new starting point x ' c C ( a i ) such that IlVxP( x', ~)ll ~< K.
(2.18)
In this case, Step 2 would require zero iterations to satisfy (2.16). Since at the previous iteration, we have computed a pair (xi, ~ - 1 ) satisfying
nVxp(xi,
1)11 K.
(2.19)
a sufficient condition which guarantees satisfaction of (2.18) is that x' satisfies V x p ( x ' , c~i)= Vxp(x~, c~ 1).
(2.20)
Using Taylor's Theorem (under suitable differentiability hypotheses and ignoring higher order terms) we expand the function Vxp( ", • ) about the point (x~, c~_1) to get
VxP( xt, O£i)~Vxp(Xi, 0£i 1)~-Pxx(Xi, Oli--1)(Xt--Xi)~-Pax(Xi, O[i 1)(OLi--O(i 1)" (2.21) This suggests that x ' & x~-(px~(xi, c~ 1 ) ) a P ~ ( x ~ , c ~ i)(c~-c~_1)
(2.22)
163
E. Polak et al. / A barrier function method for minimax problems
might be a reasonable starting point for Step 2 (assuming that x ' c C(~i)). A straightforward computation shows that (under smoothness assumptions) the Hessian (with respect to x) of the barrier function is given by
px~(x,
t)Vx0k(x, t) T _~"x(x,t)_ ] o~)a~!It o.,j FL2 Vx0k(x, (-~a~--~,t~ ~(a-Ok(x,t))2Jdt,
(2.23)
Since we wish to avoid computing Hessian information (and making an additional smoothness hypothesis), we approximate the Hessian p~x(xi, ~_~) in expression (2.22) by the positive definite matrix /4(x,
T a)~ Z f[[Vxcbk(x,t)VxOk(x,t) 2 ~ k~,
o.1]
( a - 0 k ( x , t)) 3
~rl] ( a - 0 k ( x , t)) 2
dt,
(2.24)
where cr > 0 is some fixed constant. This yields the following formula X' ~ X i -- ( I~I ( x i , Oli--1) )--l poex(X,, Ogi--' )( 0l i -- a~i_l).
(2.25)
Before using the x' estimated by this calculation, we must, of course, verify that similar type of initialization may be obtained by replacing (2.20) by
x'~ C(a~). A
V~p(x', a~)~ hV~p(x~,
a~ 0,
(2.26)
where h c [0, 1), and repeating the above expansions. We have found empirically that using h = 0 does not yield as good results as using a value of h close to one. Another possible approach would be to use extrapolation based on the past points {(xi-k, ai ,-k)}k~,~, for some m > 0. In [16], an analysis of extrapolation methods for a specific barrier function arising in constrained optimization is presented. However, in [16], the desired final value of the extrapolation parameter (i.e. a) is known, whereas for problem MMP, the final value is unknown. Before concluding this section, we note that we have tacitly assumed that 4:(" ), p ( . , . ) and V~p(.,-) can be evaluated exactly. Consequently, Algorithm 2 should be viewed as a conceptual algorithm. An implementable algorithm may be developed in a manner similar to that presented in [18], by adopting a suitable discretization scheme for the interval [0, 1].
3. Proof of convergence The main theorem of this section shows that any accumulation point ~, of a sequence produced by Algorithm 2 satisfies 0 c 00(~) (where 04:(~) denotes the Clarke generalized gradient [3] of 0(" ) at ~). Our proof requires the following definition of the set valued function G4: : R" -->2~"+1:
k~J \
tc[0,1]
vx&k(x, t)
"
(3.1)
164
E. Polak et aL / A barrierfunction methodfor minimax problems
It is straightforward to show that Gq~(.) is an a u g m e n t e d convergent direction finding (a.c.d.f.) m a p for 6 ( . ) (see [24, Definition 5.1]). In particular, we use two properties of ( 3 6 ( . ) : (i) ( 3 6 ( . ) is u p p e r semi-continuous (see [2]), and (ii) 0 6 (36(~) if and only if 0 ~ Oq,(~). The p r o o f of convergence d e p e n d s on the following two technical lemmas, which generalize the fact that a decreasing sequence either converges or diverges p r o p e r l y to -oo. L e m m a 3.1. Suppose that the sequences o f real numbers {/3i}~o and {~}~-o satisfy the following conditions: (i) rh/> Of o r all i c N, (ii) Y ~o rh < co, and (iii)/3~+1 ~35 + rh, f o r all i ~ N. Then either the sequence {fli}~o converges, or fl~ ~ - e o as i ~ oo.
Proof. It is clear from the assumptions that the following holds: n 1
c~
/ 3 , - / 3 0 = Z (/3,+1-/3~) <~ Y, rh. i=0
i =0
(3.2)
Hence,/3i is b o u n d e d from above, and therefore fi A lim s u p ~ / 3 ~ < oo. Obviously, if/3 = -co, then/3~ ~ - o o as i ~ oo. N o w s u p p o s e that f i > - o o . To prove convergence of the sequence {/3~}i~0, we will show by contradiction that lira inf~oo/3~ t>/3. Thus, let e > 0 be arbitrary, and suppose that there is no io such that/3~ > fi - e for all i > i0. Clearly, there exists an co il such that Yk=~ *lk<½e for all i>~il . It follows from our hypothesis that there exists an i2 >i i~, such that/3i2 ~< fi - e. It follows from (3.2) that for i > i2, i 1 /3i--/3i2 A
v---" ~ k~i 2
(/3k+1--/3k)~
co ~, '?~k~/e.
(3.3)
k=i 2
1
Hence /3~ ~< 13-~e for all i sufficiently large, which contradicts the definition of ft. It follows that lim~oo/3~ = ft. [] Lemma 3.2. Suppose that the sequences o f real numbers (%}i~_j and {~7i}i°~o satisfy the following conditions: (i) ~7~~> 0, f o r all i c N, (ii) ~o~ i=o ~i < oc, and (iii) %+1 <~ ½(Yi + Yi 1) + rh f o r all i c N. Then either { %} ~ _ ~ converges, or Y~~ -oo as i ~ oo. Proof. Let/3i & m a x { y / , Yi 1}" Clearly, %+1 ~ max{ %, ")/i--I } -~- T]i = /3i -~- 97i,
(3.4)
which shows that/3i+1 ~3i + rh. Making use of L e m m a 3.1, we conclude that either /3i ~ -oo, or else fi & limi_,oo/3~ exists. If/3i ~ -oo, then so does the sequence {7i}~ 1. We will show by contradiction that l i m i ~ y~ =/3. Let e > 0 be arbitrary, and suppose that there is no io such that % > f i - e for all i ~> io. Clearly, there exists an il such oo that ~k:~ ~k <~e, and I/3~-ill < l e , for all i ~> i 1 . By assumption, there exists an i ~> il, such that T~~< f i - e. Hence, by definition of/3i, we must have that 7~-1 =/3~. H e n c e we obtain that ')/i+1 ~ 2( 'Yi -~- ")/i 1) -[- T]i ~ 2(/3 -- E -[- ~ -~-IE) -]-IE ~ ~ --~6 E.
(3.5)
E. Polak et al. / A barrier function method for minimax problems
165
Since Y~~~- e, it follows from (3.4) that/3~+, ~~ - ~6e. Next, for any j > i + 1, j I ~j--~i+l =
oo
E ( f l k + l -- J~k) ( ~" '~/c ~ ~ 8" k~i+l k=i+l
(3.6)
Combining (3.5) and (3.6), we obtain that for all j > i + 1, /3J ~3 - 3 e ,
(3.7)
which contradicts the definition of/3. It follows that limi~o~ y~ -/3.
[]
The following lemmas derive inequalities which are used in Theorem 3.5: Lemma 3.3. Suppose that Assumption l holds, that e > O, and that (x, ee) c C. Then for each t ~ A ~ ( x ) , with t c [ 0 , 1] and k~J,
~-O(x) (c~
1
4,k~x, t))2 ~ (a - O(x)) ~ 5
(3.8)
Proof. Since t~ A~(x), we have that &k(x, t) < O(x) - e. Hence,
-,~(x, t)> ~-0(x)+~
>
~,
from which the desired inequality follows.
(3.9) []
Lemma 3.4. Suppose that Assumption 1 holds, and that Co is a bounded subset of C.
Then there exists a constant A > O, such that jor all ( x, a ) c Co,
(o, -
O(x))
Y f[
k~J
0,1]
(,~ - ~ ( 1 x,
t)) 2dt~>A>0"
(3.10)
Proof. Since Co is bounded, so is the projection H of Co onto R". Hence by assumption there exists a Lipschitz constant, L < e c , such that each &k(x,.) is uniformly Lipschitz in t on [0, 1], for all x c H. Without loss of generality, we may assume (since C o is bounded) that L>~ c e - O ( x ) , for all (x, c~)6 Co. Let k ~ l be such that A~(x) is nonempty, let t~ c A~(x) he given and let t c [0, 1]. Then we have that &k(x, t) >~& k(x, tx) - Lit - tx] = O(x) - Lit - t~l.
(3.11)
Now suppose that O<e<~L. Then { t ~ [ O , l ] l l t - t x [ < ~ e / L } c A ~ ( x ) , and hence m ( A ) ( x ) ) > ~ e / L , where m ( . ) denotes the Lebesgue measure on N. Hence we conclude that
~"
k~l
fr o,1]
e~--O(X) " >- fA c~-O(X) dt>-e c~-O(x) (c~-&k(x,t)) 2dt~ )(x)-(c~ &k(x,t))2 ~L(c~y~-~+e)
Setting e = c~- 0(x), and A =¼L, we obtain the desired result.
2.
(3.12t
[Y
The essence of the proof of Theorem 3.5 is to show that, if xi ~ )~, there exist elements ~:i c GO(x~) such that ~ & 0. Upper semi-continuity of G0(" ) allows us to conclude that 0 ~ G0(~), which is equivalent to 0 ~ 00()~).
E. Polak et al. / A barrier function method for minimax problems
166
oo Theorem 3.5. Suppose that Assumption 1 holds. I f {X i}i=-i is any seque~ce produced by Algorithm 2, when applied to problem M M P , then any accumulation point ~, of { xi } i~- l , satisfies 0 c a~(~).
Proof. Suppose that x~ s> ~, as i-> ~ for some infinite subset S c N. By construction x,+~ e C(a,) for all i e N, and hence it follows that I~(Xi+I) < O/i ~ l(I/t (X,-1) -~- ~ ( X i ) ) ~- T~i.
(3.13)
Therefore the sequence {qJ(x,)}~ ~ satisfies the conditions of L e m m a 3.2. Since ~ ( . ) is continuous, we must have that 0(x,) s_~ tp(~), and hence, because of L e m m a 3.2, the whole sequence {q~(x,)},~-i converges to tp(~). As a consequence, the sequence {ai};~0 also converges to ~0(~). By construction, we have for all i • N, i > 0, IlVxp(x,, oh-011 ~< g .
(3.14)
Since (~, 1 - q J ( x , ) ) ~ 0 as i ~ o o , it follows that lim (ai_l - O(x,))V~p(x,, cq ,) = 0. ,-~cO
(3.15)
For each k e J , define pk:[0, 1 ] ~ N by
pki(t) A= cei_,--tP(Xi) (a,_x - Ok(x,, t) ) 2"
(3.16)
Since {(~,-1, x,)}i~s is contained in some b o u n d e d subset of C, we conclude from L e m m a 3.4 that there exists a A > 0 such that for all i • S,
~',
2
pk(t) dt ~ A.
k~l
(3.17)
0,1]
It follows from (3.15) and (3.17) that -
1 2
pk(t)Vxc~k(x, t) dt--~ O.
1)i kEI
(3.18)
0,1]
Furthermore, since {x,},~s is b o u n d e d , there exists some constant B such that 6(xi) - 4~k(x~, t) <~B, for all t • [0, 1], and for all i • S. Consequently, for any e > 0,
2 [
pk(t)(qs(X,)-- chk(xi, t)) dt
(3.19)
k~l J[0,1]
I
A~(xi)
+fA~(x;)c P)(t)(O(Xi)-c~k(xi't))dt) <~e~,;+ (a, 1- tb(x,)) 1 lB. E
(3.20) (3.21)
It follows from (3.19)-(3.21) that
1 E f /"i /eel 3[0,13
pk(t)(~(X,)--chk(x,, t)) dtS-~ O.
(3.22)
E. Polak et al. / A barrierfunction methodfor minimax problems Since
p~(t)> 0 for ~ & t'--~k~!l ~
167
all i, k, t, convexity of 6 0 ( " ) implies
ft o.1] Dik.(t)~ ,/O(Xi)--~)k(xi, t)) dt c G0(xi). XT~chk(x,,t)
(3.23)
Since (3.18) and (3.22) imply ~ s_~ 0, upper semi-continuity of Gq,(.) implies 0 c G~O(£). This completes the proof. []
4. Numerical results
We will now present a number of numerical examples which illustrate the performance of Algorithm 2. Since there is a scarcity of semi-infinite minimax test problems in the literature, we have (i) constructed three semi-infinite minimax problems by converting three constrained problems in [32] into semi-infinite minimax problems using l~ exact penalty functions, and (ii) we took from the control literature two semi-infinite minimax problems which correspond to the very important task of constructing a stabilizing compensator for a multivariable linear feedback system. Finally, to determine if our algorithm has any advantages in solving finite dimensional minimax problems, we have applied it to a few problems of varying degree of difficulty and compared its performance to existing algorithms. In our experiments, the computations in Step 2 of Algorithm 2 were carried out using Algorithm A (presented in the Appendix). To improve performance, we used the homotopy type initialization described in observation (vi) of Section 2. All the computations were performed in double precision on a Sun 3 microcomputer with a floating point accelerator. For each of the problems below, the Armijo step size parameters in Algorithm A were set to a = 0.0001,/3 = 0.01. The parameters ~r (of Algorithm A) and K were chosen in ad hoc fashion. The algorithm performance was reasonably insensitive to moderate changes of these parameters. The heuristic used for choosing these parameters was as follows: (i) Choose K so that initially, the number of inner iterations is approximately one or two, and (ii) choose o- to be small, with the proviso that the Armijo procedure (Step 3) of Algorithm A should not repeatedly choose points in C(ce) c. A potential numerical problem with Algorithm 2 arises from the fact that if the sequence {xi}~_-i which it constructs converges, then limioo~ p(Xi+l, Oli)=00. In practice however, this did not create any difficulties. For semi-infinite problems, we compared Algorithm 2 with a modified version of Algorithm 5.2 in [24] (see Example 5.1 and Corollary 5.1 in [24] for details), since it seems to be the only other first-order minimax algorithm in the literature which can be proved to be globally convergent under equally weak assumptions. Our test problems were as follows: Problem TFI1. This is a modification of Problem 1 of [32]. In this problem, and in Problems TFI2, TFI3, the exact penalty has been adjusted so that the minimax
168
E. Polak et al. / A barrier function method for minimax problems
p r o b l e m has the same solution as the original problem. Here 4 ' ( x ) = m a x { f ~ ( x ) , max,~Eo,~ l ~b~(x, t)}, where f l ( . ), g ( . , . ) (defined in [32]) and &~(.,. ) are given by
fl(x) & (xl)2+ (x2)2 + (x3) 2,
(4.1)
g(x, t) & x I + x 2 e ~ ' + e 2' - 2 sin(4t),
(4.2)
ch~(x, t)&f'(x)+ 100g(x, t).
(4.3)
Initial point: 1.853 547) T.
x ~ = x 0 = ( 1 , 1, 1) T.
Solution:
~=(-0.213
313,
-1.361 450,
Problem TFI2. In this p r o b l e m ~b(x) = m a x { f ' (x), max,~lO.11 ~bl(x, t)}, where ~h'(x, t) is defined as above (4.3), but using the functions f l ( . ), and g ( . , • ) of Problem 2(a) [32] defined by
fl(x) & x' +½x2+½x 3, g(x, t) & tan(t) - x 1 - (x 2) t - (x 3) t 2.
(4.4) (4.5)
Initial points: x_~ = Xo = (0, 0, 0) T. Solution: ~ = (0.089 096, 0.423 052, 1.045 260) T. Problem TFI3. In this p r o b l e m 0 ( x ) = m a x { f l ( x ) , max,~to,13 ~bl(x, t)}, where (~I(x, t) is defined as above (4.3), but using the functions f ~ ( . ), and g ( . , . ) of Problem 3 [32] defined by f l ( x ) & e " + eX2+ eX3,
(4.6)
1
g(x, t) = l + t 2 xl-(x2)t-(x3)t 2. Initial points: -0.379 725) "r.
x _ ~ = x o = ( 1 , 0 . 5 , 0 ) m.
(4.7)
Solution:
~=(1.006605,
-0.126 880,
In [26], we find a m e t h o d for designing stabilizing c o m p e n s a t o r s for linear multi-variable f e e d b a c k systems via semi-infinite optimization. We use this m e t h o d here to c o m p u t e a p a r a m e t e r vector x c ~ 3 (with c o m p o n e n t s denoted by superscripts) which results in all the eigenvalues of the following matrix 2 having strictly negative real parts: 0
A(x) & [
7
0
--X 3 --2X 4 - 4X 3 --3X 4 - 3X 3
x6
-3
-4
-2
0 X8
1 0
0 -2
0 -4
(4.8)
As is shown in [26], the eigenvalues of the matrix A(x) have strictly negative real parts if q,(x) ~ 0, where 0 ( x ) = max{maxj~5 f i(x), max,o~EO,ll ~bl(x, w)}, with
fi(x) &-xJ+S+O.O01, j c 5,
(4.9)
2 For the purpose of testing our algorithm, we deliberately overspecified the number of design variables to make the resulting minimization problem ill-conditioned.
169
E. Polak et aL / A barrier function method for minimax problems
and , ~ .....
[
det(j(6Ow)l-A(x))
4,L(x, ~o)=o.ov, --Ke[((j60w)Z+xg(j60~o)+x~+~Ow)+x12)((j60~o)+x13)J.
]
(4.10)
Note that in this problem we do not need to find a minimizer, only a point x which makes ~0(x) negative. We used two different initial points, as stated below: Problem M O D N Y Q I . Determine x ~ ~]~13 such that 0(x) ~ 0.
Initial points: x l = x 0 = (10, 9.9, 9.8, 9.7, -9.6, -9.5, -9.4, -9.3, 1, 1, 3.7341, 3.4561, 37.642) x. Our solution: ~ = (2.643, 6.422 75, 1.759 68, 6.401 45, -4.762 99, -5.110 22, 3.734 25, 2.962 87, 0.968 426, 0.725 671, 2.663 47, 8.160 53, 32.5577) x. At the solution point 2 A0()~) contains only one point w. Problem MODNYQ2. Determine x c ~13 such that 0(x)~< 0.
Initial points: X_l=X0= ( - 1 , 0, 0, - 1 , 1, 0, 0, 1, 2, 1, 6.2055, 9.1530, 2) T. Our solution: ~ = (-0.122 783, -0786 55, 0.939 792, -0.281 968, 0.068 8075, 0.997 245, -0.879 12l, 0.088 0097, 1.033 45, 1.694 49, 3.164 19, 9.4826, 0.775 611) T. At the solution point ~ Ao()~) contains only one point w. Table 1 summarizes the results in terms of the number of function evaluations (NF) and gradient evaluations (NG) required to achieve the specified accuracy. For the Problems TFI1-TFI3, we terminated computation at the first iterate xi which satisfies the test [Ixi - 2112< 10 4, where ~ is the corresponding solution. We compared the performance of Algorithm 2 with that of the linearization method, Algorithm 5.2 in [24]. On Problems TFI1 and TFI3, both algorithms performed similarly, while the linearization method [24] fails to achieve the required accuracy on Problem TFI2. The linearization method [24] fails to obtain a solution to Problem MODNYQ1 in 200 iterations (and over 5 hours!). In this case, Algorithm 2 obtained a solution reasonably quickly. Figure 1 plots the function 4'(" ) versus iteration number of both of these algorithms when applied to Problem MODNYQ1. The difference in performance of the two algorithms on Problem MODNYQ2 is not as dramatic, but is nonetheless substantial. For the purposes of illustration, Figure 2 shows the semiinfinite function (4.10) at various iterations for Problem MODNYQ2. Table 1 Performance on semi-infinite problems Problem
Algorithm 2 (NF/NG)
[24] (NF/NG)
TFI1 TFI2 TFI3 MODNYQ1 MODNYQ2
70/37 122/74 34/25 63/42 6/6
147/27 FAILS 63/13 FAILS 55/14
170
E. Polak et al. / A barrier function method for minimax problems k[/(xi) 30
20
10
i
.......i 0'''" '20 "'''30 40
" "150" 160
70
'80"" " '90'''''11 O0
Fig. 1. ~h(x~)versus iteration (i) for Problem MODNYQ1.
¢l(xi,~)
3
iteration 5
Fig. 2. cht(xi, w) for various iterations for Problem MODNYQ2.
To illustrate the behavior of Algorithm 2 on finite minimax problems, we begin by applying it to the following particularly difficult problem with spiral level sets, as shown in Figure 3. Problem SPIRAL. In this problem, n = 2, m = 2 and the functions f j :B~ 2--> ~;~,j ~- 1, 2, are defined by
ft(x) ~ (X 1 --~/(xl)2-~ (X2) 2 COS(~/(X1)2-~ (X2)2))2"~- 0.005((XI)2"~ (X2)2),
(4.11)
/ 2 ( x ) & (x 2 _ x/(x ~)2 + (x2)2 sin(~/(xl)2 + (x2)2))2 + 0.005((x t)2 + (x2)2).
(4.12)
The solution of this problem is ~ = (0, 0) T, and we used the initial points x-1 = x0 = (1.41831, - 4 . 7 9 4 62) T.
E. Polak et aL / A barrier function method Jbr minimax problems
171
~J-~({1,3,5,7,9})n[-5,5]x[-5,5]
Fig. 3. Contours of ~h(. ).
Table 2 gives the number of iterations (I), the time in seconds (T), and the number of function evaluations (NF) and gradient evaluations (NG) required to satisfy I[xi-.~ll2<~e, for various values of e. We present figures for Algorithm 2, the linearization method of [24] (Algorithm 5.2), and the exceptionally effective combined LP/Quasi-Newton method of [11]. The behavior of Algorithm 2 on Problem SPIRAL highlights a number of points. Algorithm 2 quickly achieves a reasonable level of accuracy with relatively few function and gradient evaluations. On this difficult problem, it outperforms the methods of [24] and [11], both in terms of evaluations and time (the method of Table 2 Performance on problem SPIRAL e
Algorithm 2 I
5 4 3 2 1 1 e -02 1 e -04 1 e -07 1 e - 10
T
o 29 29 30 31 32 33 33 34
o 9.56 9.56 11.32 15.08 16.82 17.68 17.68 19
[24]
NF/NG
o/o 469/176 469/176 562/210 782/290 890/321 940/335 940/335 1032/356
I
T
o 224 398 640 732 811 876 894 912
o 18.7 32.58 47.48 53.32 57.98 61.92 63.58 65.18
[11] NF/NG
o/o 2306/224 3904/398 5592/640 6247/732 6717/811 7069/876 7270/894 7469/912
I
NF/NG
o 1743 3903 5005 5248 5325 5337 5344 5357
o/o 1743 /1743 3903 /3903 5005 /5005 5248 /5248 5325 /5325 5337 /5337 5344 /5344 5357 /5357
E. Polak et al. / A barrierfunction methodfor minimax problems
172
inner iterations
100
;:::::::::l:,
0
10
,,,
,,tiI
, ,::-
,
20
,
l ,
I
,
,
30
iteration
Fig. 4. Inner iterations versus iteration for Problem SPIRAL. [11] required significantly more time than the other algorithms). As would be expected, the number of inner iterations (required by Algorithm A to satisfy Step 2) grows as a solution is approached. Figure 4 illustrates this by plotting the number of inner iterations versus the iteration number. For reasonable levels of accuracy, however, this growth is not too severe. Furthermore, this may be alleviated somewhat by replacing the Step 2 acceptance criterion by that of remark (iv) of Section 2. Next we applied Algorithm 2 to the finite minimax problems below. These problems are considerably less difficult than SPIRAL. Problem WF. This is the example in [34, p. 512] on which the algorithm of [34] fails to converge. Here O(x)A maxj~3~ i f ( x ) , where
f ' ( x ) = ~1/ ~x
f2(x)&
14 (x 1lOx' ) + 0.1) + 2(x2)2 '
,0 1
)
-x~4 - (x~+0.1) t-2(x2) 2 ,
A1[ ~ 10x 1 f 3 ( x ) = 2 ~ x (xl+0.1) Initial points: x
Problem M.
1 = X0 =
(3,
1) T.
2(x2)2).
(4.13) (4.14) (4.15)
Solution: ~ = (0, 0) v.
This is the second problem of [19]. Here t#(x)&maxjc_6 fJ(x), where
fl(x)&(x')Z+(x2)2+xlx2,
f2(x)~-fl(x),
(4.16)
f 3 ( x ) A sin(x1),
f4(x) ~ -f3(x),
(4.17)
f S ( x ) A cos(x2),
/6(x) & -fS(x).
(4.18)
Initial points: x 1= x0 = (3, 1) x. Solution: ~ = (0.453 296, -0.906 592) v.
E. Polaket al. / A barrierfunction methodfor minimaxproblems
173
Problem RB. This is E x a m p l e 1 from [11]. Here g,(x)&maXi~a_fi(x), where
f l ( x ) & lO(x2-(x')2, f3(x)& l-xl,
fe(x)&-f~(x),
(4.19)
f4(x)&-f3(x).
(4.20)
Initial points: x_~ = Xo = (-1.2, 1) v. Solution: ~ = (1, 1) T. Problem CB2. This is Problem CB2 of [34]. Here O(x) & maxi~3- fJ(x), where
f l ( x ) & (x')2+ (x2) 4,
(4.21)
f 2 ( x ) =A(2 - x~) 2 + (2 - x2) 2,
(4.22)
f 3 ( x ) &2 e -x'+x2.
(4.23)
Initial points: x ~ = xo = (2, 2) T. Solution: ~ = (1.139 037 652, 0.899 553 84) T. Problem CB3. This is Problem CB3 of [34]. Here ~9(x)& maxiQ3 f J ( x ) , where
f ' ( x ) & ( x ' ) 4 + (X2) 2,
(4.24)
f 2 ( x ) & (2 - x ' )2 _~_(2 - x2) 2,
(4.25)
f 3 ( x ) & 2 e-X'+*:.
(4.26)
Initial points: x_~ = x 0 = (2, 2) T. Solution: ~ = (1, 1) T.
The results obtained (and c o m p a r a b l e results from the literature) are presented in Table 3. It should be pointed out that each algorithm has a different stopping criterion, and so care must be taken when interpreting the results. We executed both Algorithm 2 and Algorithm 5.2 [24] until the first iteration which satisfied the test Ilxi - xll2 < 10-4, where ~ is the solution. In addition, we have c o m p a r e d our algorithm with the F i a c c o - M c C o r m i c k - M i t t t i n - T r e m o l i e r e s ( F M M T ) algorithm m e n t i o n e d in the introduction (1.4a-c). To provide a fair comparison, we have a u g m e n t e d the F M M T scheme by adding a h o m o t o p y type initialization, similar to that presented in remark (vi) of Section 2. As in previous tables, N F refers to the n u m b e r of function evaluations, and N G to the n u m b e r of gradient evaluations. If these n u m b e r s are not explicitly given in the literature, we indicate this by (-). Table 3 Evaluation count for finite minimax problems
WF M RB CB2 CB3
Algorithm2 NF/NG
[24] NF/NG
25/25 42/25 87/41 24/14 33/21
FAILS 58/11 56/10 150/25 40/8
[22] NF/NG
[34] NF/NG
[4] NF/NG
[11] NF/NG
FMMT Problem NF/NG
21/8/-
FAILS 22/22 21/21 11/11 9/9
149/88 187/115 249/145 109/72 181/114
FAILS 19/6/-
37/29 12/7 10/6
E. Polak et al. / A barrier function method for minimax problems
174
It is clear from our experimental results that Algorithm 2 is exceptionally robust and that it is quite effective on semi-infinite minimax problems for which it was primarily intended. When applied to finite minimax problems, its performance is only fair on easy to moderately difficult problems. However, on severely ill-conditioned problems, such as SPIRAL and WF, it has considerable advantages since it computes results when other methods fail. Finally, we note that the related constrained nonlinear programming algorithm F M M T performs poorly in comparison with Algorithm 2.
5. Conclusion We have presented a first-order minimax algorithm based on barrier function techniques which resemble parameter-free interior penalty function methods used in constrained optimization. The use of an Armijo-Gauss-Newton type routine which is initialized by means of a primitive homotopy approach appears to mitigate the scaling difficulties caused by the barrier functions in the inner problem. Theoretically, our algorithm can be generalized to solve problems where the "max-parameter" is an element of [0, 1] k (for some integer k > 1) rather than [0, 1]. This generalization requires raising the denominators of (2.1) to a suitable power. However, the problem of implementation of this new algorithm, as well as of any other currently known semi-infinite minimax algorithm, is bound to become more severe. Our new algorithm offers two major advantages. The first is that no special purpose search direction routine is required (such as a quadratic program solver) which makes it particularly suitable for dedicated VLSI implementation in on-line applications where computing speed and component reliability are essential. The second advantage is that of robustness combined with reasonable speed: limited numerical experiments indicate that our algorithm does not fail when others do, that it converges linearly (with respect to the outer iterations), and that its computing times are comparable to those of other first-order minimax algorithms.
6. Appendix: A procedure for solving the inner problem The inner problem, defined by Step 2 of Algorithm 2, requires the computation of a point Xi+l ~ C(ai) which satisfies
IlVxp(x,+,, <)IL ~ K,
(A.I)
for a given K > 0 and a given initial point Yi c C(a~). Clearly, in general, such a point can be obtained in a finite number of iterations by means of any number of descent algorithms, including the Armijo gradient method [1].
E. Polak et al. / A barrier function method for minimax problems
175
H o w e v e r , as a s o l u t i o n o f P r o b l e m ( M M P ) is a p p r o a c h e d , s o m e o f the terms in (2.1), b e c o m e very large a n d h e n c e the p e n a l t y f u n c t i o n p ( . , ai), defined by (2.1) t e n d s to b e c o m e b a d l y scaled. A f t e r s o m e e x p e r i m e n t a t i o n with alternatives, we h a v e c o n c l u d e d that an effective w a y to d e a l with this difficulty, as well as with the fact that the p e n a l t y f u n c t i o n can be quite e x p e n s i v e to e v a l u a t e (which d i s c o u r a g e s c o m p l e x step size calculations, as well as c o m p u t a t i o n o f s e c o n d o r d e r derivatives), is to solve the i n n e r p r o b l e m b y m e a n s o f the f o l l o w i n g A r m i j o - G a u s s - N e w t o n variant. In this variant, we a p p r o x i m a t e the H e s s i a n o f p ( - , ce), defined b y (2.23), b y the e x p r e s s i o n (2.24). The resulting p r o c e d u r e is as follows: A l g o r i t h m A (Solve Step 2 o f A l g o r i t h m 2). A fokloo D a t a : (yo, c e ) c C , K>~O, 7, f l c ( 0 , 1 ) , S = t ~ , Jk=0, t r > 0 . Step O. Set i = 0.
Step 1. If IlVxp(yi, c~)[[<~ K, set xi+, =Yi and stop. Step 2. Set hi = -17t(yi, a ) - ' V x p ( y i , Step 3. C o m p u t e the step size:
a).
Z i & max{ Z c S ]Yi + Z hi c C ( c~), p (Yi + Z hi, a ) - p 0 % a ) <~ yZ (hi, V xP (Yi, a ))}. Step 4. Set Yi+l = Yi + )tihi. Step 5. R e p l a c e i by i + 1 a n d go to Step 1. It is s t r a i g h t f o r w a r d to p r o v e that A l g o r i t h m A either finds a p o i n t xi+l satisfying (A.1) in a finite n u m b e r o f iterations, o f ]]YiU-~oo as i ~ o o .
References [1] L. Armijo, "Minimization of functions having continuous partial derivatives," Pacific Journal of Mathematics 16 (1966) 1-3. [2] C. Berge, Topological Spaces (Macmillan, New York, 1963). [3] F.H. Clarke, Optimization and Nonsmooth Analysis (Wiley, New York, 1983). [4] C. Charalambous and A.R. Conn, "An efficient method to solve the minimax problem directly," SIAM Journal of Numerical Analysis 15 (1978) 162-187. [5] A.R. Conn and N.I.M. Gould, "An exact penalty function for semi-infinite programming," Mathematical Programming 37 (1987) 19-40. [6] I.D. Coope and G.A. Watson, "A projected Lagrangian algorithm for semi-infinite programming," Mathematical Programming 32 (1985) 337-356. [7] A.V. Fiacco and G.P. McCormick, "The Sequential unconstrained minimization technique without parameters," Operations Research 15 (1967) 820-227. [8] D. Goldfarb, S. Mehrotra, "Relaxed variants of Karmarkar's algorithm for linear programs with unknown objective value," Mathematical Programming 40 (1988) 183-195. [9] C.C. Gonzaga, "An algorithm for solving linear programming problems in o(n3L) operations," Memo No. UCB/ERL M87/10, Electronics Research Laboratory, University of California at Berkeley (Berkeley, CA, 1987). [10] C. Gonzaga, E. Polak and R. Trahan, "An improved algorithm for optimization problems with functional inequality constraints," IEEE Transactions on Automatic Control AC-25 (1980) 49-54. [11] J. Hald and K. Madsen, "Combined LP and quasi-Newton methods for minimax optimization," Mathematical Programming 20 (1981) 49-62. [12] S.P. Han, "Variable metric methods for minimizing a class of nondifferentiable functions," Mathematical Programming 20 (1981) 1-13.
176
E. Polak et al. / A barrier function method for minimax problems
[13] R. Hettich and W. Van Honstede, "On quadratically convergent methods for semi-infinite programming," in: R. Hettich, ed., Semi-Infinite Programming, Lecture Notes in Control and Information Science No. 15 (Springer, New York, 1979) pp. 97-111. [ 14] F. Jarre, "Convergence of the method of analytic centers for generalized convex programs," Report No. 67, Schwerpunktprogramm der Deutschen Forschungsgemeinschaft-Anwendungsbezogene Optimierung und Steurerung, Institut fur Angewandte Mathematik und Statistik, Universitat Wurzburg (Wurzburg, 1988). [15] F. Jarre, "An implementation of the method of analytic centers," 8th Conference on Analysis and Optimization of Systems (INRIA, Antibes, France, June 1988). [16] K. Jittorntrum and M.R. Osborne, "Trajectory analysis and extrapolation in barrier function methods," Australian Mathematical Society Journal Series B 20 (1978) 352-369. [17] N. Karmarkar, "A new polynomial-time algorithm for linear programming," Combinatorica 4 (1984) 373-395. [18] R. Klessig and E. Polak, "A method of feasible directions using function approximations, with applications to rain max problems," Journal of Mathematical Analysis and Applications 41 (1973) 583-602. [19] K. Madsen, "An algorithm for minimax solution of overdetermined systems of non-linear equations," Journal of the Institute of Mathematics and its Applications 16 (1975) 321-328. [20] D.Q. Mayne and E. Polak, "A quadratically convergent algorithm for solving infinite dimensional inequalities," Applied Mathematics and Optimization 9 (1982) 25-40. [21] R. Mifflin, "Rates of convergence for a method of centers algorithm," Journal of Optimization Theory and Applications 18 (1976) 199-228. [22] W. Murray and M.L. Overton, "A projected lagrangian algorithm for nonlinear minimax optimization," S l A M Journal on Scientific and Statistical Computing 1 (1980) 201-223. [23] W. Oettli, "The method of feasible Directions for continuous minimax problems," in: A. Prekopa, ed., Survey of Mathematical Programming, VoL 1 (North-Holland, Amsterdam, 1979). [24] E. Polak, "On the mathematical foundations of nondifferentiable optimization in engineering design," S I A M Review 29 (1987) 21-89. [25] E. Polak, S. Salcudean and D.Q. Mayne, "Adaptive control of ARMA plants using worst case design by semi-infinite optimization," IEEE Transactions on Automatic Control AC-32 (1987) 388-397. [26] E. Polak and T.S. Wuu, "On the design of stabilizing compensators via semi-infinite optimization," IEEE Transactions on Automatic Control AC-34 (1989) 196-200. [27] E. Polak and D.Q. Mayne, "An algorithm for optimization problems with functional inequality constraints," IEEE Transactions on Automatic Control AC-21 (1976) 184-193. [28] E. Polak and A.L. Tits, "A recursive quadratic programming algorithm for semi-infinite optimization problems," Applied Mathematics and Optimization 8 (1982) 325-349. [29] B.N. Pshenichnyi and Yu.M. Danilin, Numerical Methods" in Extremal Problems (Nauka, Moscow, 1975). [In Russian.] [30] G. Sonnevend and J. Stoer, "Global ellipsoidal approximations and homotopy methods for solving convex analytic programs," Report No. 40, Schwerpunktprogramm der Deutschen Forschungsgemeinschaft-Anwendungsbezogene Optimierung und Steurerung, Institut fur Angewandte Mathematik und Statistik, Universitat Wurzburg (Wurzburg 1988). [31] G. Sonnevend, "New algorithms in convex programming based on a notion of center (for systems of analytic inequalities) and on rational extrapolation," in: K.-H. Hoffmann et al., eds., Trends in Mathematical Optimization, ISNM, Vol. 84 (Birkhauser, Stuttgart, 1987) pp. 311-327. [32] Y. Tanaka, M. Fukushima and T. Ibaraki, "'A comparative study of several semi-infinite nonlinear programming algorithms," European Journal of Operational Research 36 (1988) 92-100. [33] R. Tremolieres, "La method des centres a troncature variable," PhD Thesis, University of Paris (Paris, 1968). [34] R.S. Womersley and R. Fletcher, "An algorithm for composite nonsmooth optimization problems," Journal of Optimization Theory and Applications 48 (1986) 493-523. [35] Y. Ye, "Interior algorithms for linear, quadratic, and linearly constrained convex programming," PhD Thesis, Department of Engineering - Economic Systems, Stanford University (Stanford, CA, 1987).