Second-Order Algorithms for Generalized Finite and Semi-Infinite Min-Max Problems.
We present two second-order algorithms, one for solving a class of finite generalized min-max problems and one for solving semi-infinite generalized min-max problems.  Our algorithms make use of optimality functions based on second-order approximations to the cost function and of corresponding search direction functions.  Under reasonable assumptions we prove that both of these algorithms converge Q-superlinearly, with rate at least 3/2.This paper is a continuation of  [E. Polak, L. Qi, and D. Sun,  Comput. Optim. Appl., 13 (1999), pp. 137--161].
Introduction
As is also the case with ordinary min-max problems, generalized min-max problems can
be either finite or semi-infinite. Both are of the form
where
# is a smooth function and # n
# m is a nonsmooth, vector-valued
function. In the case of finite min-max problems, the components of #(-) are of the form 2
where the functions f
are continuously di#erentiable and
the sets q j := {1, 2, ., q j } are of finite cardinality 3 .
In semi-infinite generalized min-max problems the components of #(-) are of the form
where the functions
Finite generalized min-max problems are obviously a special case of semi-infinite generalized
min-max problems, since when the sets
we can define the functions f j,k (x) by
The best known generalized minimax problem occurs when an optimization problem
with a max function cost and equality and inequality constraints is set up for solution
using exact penalty functions, which results in an unconstrained optimization problem
with f 0 (x) in (1.1) of the form:
r
where # e and # i are two positive penalty parameters.
Another simple example occurs in a least squares problem involving max functions, in
which case
We denote components of a vector by superscripts and elements of a sequence or a set by subscripts.
3 Given any positive integer q, we use the notation q := {1, 2, ., q}.
where each # j (x) is as in (1.3).
As a last example, in trying to approximate a structural optimization problem the aim
of which was to minimize the sum of the probability of failure 4 plus the cost of the steel
in the structure, using linearizations of a state-limit function, we obtained a cost function
of the form
u#B#
# is a ball of radius #, centered at the origin in the space of the random variables u, and
g(x, u) is a smooth state-limit function which defined the boundary between outcomes
that result in structural failure from those that do not.
Functions of the form f 0 with #(-) as in (1.4), are the best known example
of quasidi#erentiable functions and are treated in depth in [4]. Hence generalized min-max
problems can be solved using algorithms developed for quasi-di#erentiable functions,
see, e.g., [2, 3, 6, 7, 8, 9, 11, 21]. Under the additional assumption that #F (y)/#y j > 0
for all y # m and generalized min-max problems can be solved using
transformations 5 into a smooth, constrained nonlinear programming problem (see e.g.,
[1, 5, 12]). Direct methods that depend on the assumption that #F (y)/#y j > 0 for all
can be found, for example, in [6, 9] and in [20].
We will consider semi-infinite generalized min-max problems under the following hypotheses

Assumption 1.1 We will assume that
(a) The functions F (-) and # j (-, y), j # m, y # Y j , are at least once continuously di#er-
(b) There exists a positive number c F > 0 such that #F (y)/#y j
(c) The sets Y j are either compact sets of infinite cardinality, or sets of finite cardinality,
of the form given in (1.5). 2
Parts (a) and (b) of Assumption 1.1 ensure that when both the F (-) and the # j (-)
are convex, the function f 0 (-) is also convex. In addition, as we will see, when all parts
of Assumption 1.1 hold, the function f 0 (-) has a subgradient. In [20], this fact was used
in defining an optimality function and an associated descent direction for the problem
4 The probability of failure was given by # g(x,u)#0
#(u)du, with #(-) the normal probability density
function.
5 These transformations result in a smooth problem with more variables than in the nonsmooth prob-
lem. There is a fair bit of anecdotal evidence that they can induce considerable ill-conditioning in the
smooth problem because they introduce arbitrary scaling. In general, solving nonsmooth problems using
transformation techniques appears to be less e#cient than using algorithms that exploit problem
structure.
P, and in extending the Pshenichnyi-Pironneau-Polak (PPP) Algorithm 4.1 in [17] (see
also [22, 13, 14]) to finite generalized min-max problems, and the Polak-He PPP Rate-
Preserving Algorithm 3.4.9 in [17] (see also [15]) to semi-infinite generalized min-max
problems.
In this paper we show that techniques used in [18] and [19] for constructing Q-
superlinearly converging algorithms for solving finite and semi-infinite min-max problems,
of the form (1.1) and (1.2), can be extended to construct Q-superlinearly converging algorithms
for the solution of both finite and semi-infinite generalized min-max problems.
In Section 2, we present a continuous optimality function and its associated search
direction function which, together with a backstepping rule, constitute the backbone of
our algorithms. In Section 3, we extend the Polak-Mayne-Higgins Newton's method [18],
for solving finite min-max problems, to generalized finite min-max problems. We prove
the Q-superlinear convergence of this extention in Section 4. In Section 5, we make use of
the theory of consistent approximations developed in [17] and the algorithm presented in
Section 3 to develop an algorithm for solving generalized semi-infinite min-max problems
and prove its convergence and Q-superlinear convergence. Section 6 is devoted to some
numerical results to demonstrate the behavior of the proposed algorithms. We sum up in
the concluding Section 7.
2. Optimality Conditions
We will now present optimality conditions for the semi-infinite generalized min-max problem
problem, defined in (1.1), (1.2), (1.4), both in "classical" form and in terms of an
optimality function which leads to a superlinearly converging second-order algorithm.
Lemma 2.1 [20] Suppose that F
# is continuously di#erentiable and that # :
# m is a locally Lipschitz continuous function that has directional derivatives at
every x # n . Let f
# be defined by
Then, given any x # n , and any direction vector h # n , the function f 0 (-) has a
directional derivative df 0 (x; h) which is given by
Suppose that Assumption 1.1 is satisfied. Then it follows from Lemma 2.1 that the
directional derivative of f 0 (-), at a point x # n in the direction h, is given by
#F
#F
where
When all the sets Y j are as in (1.5), (2.3) assumes the form
#F
where the functions f j,k (-) are defined by
and the sets - q j (x) by
Hence the following result is obvious.
Theorem 2.2 Suppose that -
x is a local minimizer for the problem (1.1), (1.2), (1.4).
Then for all h # n ,
#F
#F
Furthermore, (2.8) holds if and only if 0 #f 0 (-x), where the subgradient #f 0 (-x) is given
by
#F
Since (2.8) is a necessary condition of optimality, any point - x # n that satisfies (2.8)
will be called stationary.
When all the sets Y j are of the form (1.5), the expressions (2.8) and (2.9) assume the
following
#F
#F
(#(-x))#f j,k (-x) # . (2.11)
Definition 2.3 We will say that
# is an optimality function for problem (1.1),
(1.2),
(a) #(-) is upper semi-continuous,
(c) for any -
holds if and only if
Assumption 2.4 We will assume that
(a) the functions # in (1.1), (1.2), (1.4), are twice
Lipschitz continuously di#erentiable on bounded sets,
(b) the functions #
are locally Lipschitz continuous,
(c) there exist constants 0 < c # C < #, such that for all j # m, y
and
. (2.13)For the sake of convenience, for any x, h # n and w # m , we define
u(x, h, w) := #F (#(x)), -
and
v(x, h, w) := 1
The reason for the introduction of the artificial variable w is as follows. The function
is a perfectly good second-order approximation to F (#(x + h)), but unfortunately, it is
not always convex and hence leads to problems in developing an algorithm for solving
semi-infinite generalized min-max problems. By introducing the artificial variable w, we
can define the function
which, as we will later see, is a convex second-order approximation to F (#(x
hence much more useful in algorithm construction.
We define the function # n
# and the associated search direction function
# n by
{ min
and
{ min
h, w))} . (2.20)
Note that
We will shortly see that the function #(-) is an optimality function for the problem
(1.1), (1.2), (1.4). For any y, #y # m , let
Lemma 2.5 Suppose that Assumptions 1.1 and 2.4 are satisfied. For any y, #y # m , let
(y, #y) be the solution set of (2.22).
Then# (y, #y) is non-empty and compact and for
any w #
(y, #y), we have
Proof. Since #F (y) > 0 and # 2 F (y) is positive semi-definite, for any w # 0 and
#w# we have
(y, #y) is nonempty and compact.
Suppose that w #
# (y, #y). Then w # satisfies the following first-order optimality
conditions which follow directly from (and are equivalent to) the KKT conditions:
i.e.,
#w #F (y) +# 2 F (y)(#y
Clearly, (2.26) implies that for any w #
(y, #y), we have
#F (y) +# 2 F (y)#y +# 2 F (y)w # 0. (2.27)Lemma 2.6 Suppose that Assumptions 1.1 and 2.4 are satisfied. Then for any z # n
there exists an # > 0 such that for all h # n with #h# and for all x # n with
#x - z# we have
i.e.,
defined by (2.17).
Proof. Since h, -) is a convex quadratic function, any w # m
satisfying the following first-order conditions
#w, #F (#(x)) +# 2 F (#(x))( -
is a solution of (2.18). Then, because #F (y)/#y j # c F , for every
#(-) is uniformly continuous on any compact set and -
we see that for
any z # n there exists an # > 0 such that for all h # n with #h# and for all x # n
with #x - z#, This implies that for all those h and x, we have
Hence our proof is complete. 2
The above lemma shows that -
is identical to -
su#ciently small.
This fact will be used in proving our superlinear convergence results.
In general, -
not convex in h. We will now show that -
is convex in h.
Lemma 2.7 Suppose that Assumptions 1.1 and 2.4 are satisfied. Then for any fixed
is a convex function. Moreover, -
f 0 (-) is continuous.
Proof. First we will show that -
is a convex function. For any y # m and #y # m ,
we have
where
It is easy to verify that S(#y) is a concave function and that its subgradient is given by
# (y, #y)}, (2.34)
(y, #y) is the solution set of (2.33). It now follows from (2.32) that -
locally Lipschitz continuous in #y and that its subgradient gradient at #y is given by
# (y, #y)}. (2.35)
Since, by Lemma 2.5, for any w #
# (y, #y)
we conclude that for any s # -
every
is convex in
(because it is the composition of a convex function with positive elements in the
subgradient and a vector function whose components are convex).
Next, we will prove that -
continuous. First, since #F (y)/#y j # c F > 0 and
positive semi-definite for all j # {1, - , m} and y # m , it follows from (2.22)
(y, #y) is uniformly bounded in a neighborhood of given point (z,
It now follows from Corollary 5.4.2 in Polak [17] that -
F (-) is continuous. Hence
which implies that -
is continuous on # n
with y := #(x) and #y := -
The following theorem shows that #(-) is indeed an optimality function for the problem
(1.1), (1.2), (1.4) and that the set-valued function H(-) is a descent direction function for
Theorem 2.8 Suppose that Assumptions 1.1 and 2.4 are satisfied. Consider the functions
#(-) and H(-) defined by (2.19) and (2.20), respectively. Then
(i) For all x # n ,
(ii) For all x # n ,
where df 0 (x; h) is the directional derivative of f 0 at x in the direction h and # =2
(iii) For any x # n , 0 #f 0 (x) if and only if is the subgradient
of f 0 (-) at x, defined in (2.9). Moreover, for any x # n such that
have
(iv) The set valued map H(-) is (a) bounded on bounded sets, (b) compact valued, and (c)
outer-semicontinuous, i.e., for any x # n , H(x) is closed and, for every compact
set S such that H(x) # there exists a # > 0 such that H(z) #
z # B(x, #) := {y # n
|#y - x#}.
(v) The function #(-) is continuous.
Proof. (i) admissible in (2.19) that #(x) # 0 for all x # n .
directly from the definition of #(x) in (2.19) that for
any h # H(x),
#F
Thus we have shown that (2.40) holds.
(iii) For any x # n , let
min
u(x, h,
u(x, h, 0) . (2.42)
We will first prove that
It is easy to see that Hence we
only need to show that
Suppose that there exists an h # n such that
For any j # {1, - , m}, we have
and
Thus, there exists a constant C 0 such that
which further implies that there exists a constant C 1 such that
Since u(x, -, 0) is a convex function and u(x, 0, su#ciently small we have
which contradicts that
Next, with #f 0 (x) the subgradient of f 0 (-) at x, defined in (2.9), by emulating the
proof of Lemma 2.5.5 in [17], we can prove that for any x # n , 0 #f 0 (x) if and only if
therefore if and only if
Finally we will show that for any x # n such that
For the sake of contradiction, suppose that there exists an x # n such that
{0}. Then there exist 0
such that
u(x, h, w)
which, together with the fact that v(x, h, w) # 0 implies that u(x, h, w) # 0. Hence
we conclude that both u(x, h,
u(x, h, w) < 0, which contradicts (2.43). However, implies that
h, 0) is strongly convex in h and u(x, 0,
(iv) According to our definition, for each h # n there exists a w(h) # m
such that
which, together with the facts that #F (y) > 0, y # m and v(x, h, w(h)) # 0, implies
that
Since for each j # {1, - , m} and h # n ,
it follows from (2.51) that for all y in any bounded neighborhood of x,
Consequently, for any x # n , H(x) is nonempty and bounded and H(-) is bounded on
bounded sets. Since -
continuous (Lemma 2.7), it follows that H(x) is closed.
Next we will prove that for every x # n and every compact set S such that
there exists a # > 0 such that H(z) # not, then there
exists an x # n and a compact set S such that H(x) # and a sequence {x i }
converging to x such that H(x i ) # S #. Hence there exists a sequence {h i } such that
is a compact set, without loss of generality, we can assume that
By definition of H(x i ),
f 0 (-) is continuous, it follows from (2.55), that
which implies that - h # H(x). This contradicts that H(x) # Thus, we have shown
that H(-) is outer-semicontinuous.
(v) Finally, it follows from Corollary 5.4.2 in Polak [17] that # is continuous. 2
By introducing an additional variable, we can rewrite the expression for #(x), defined
in (2.19), as follows
Problem (2.57) is a quadratic problem with quadratic constraints. Under suitable assump-
tions, (2.57) is actually a convex quadratic problem with convex quadratic constraints,
and hence provides a convenient means for computing the optimality function value #(x)
and an associated search direction h # H(x).
Theorem 2.9 Suppose that Assumptions 1.1 and 2.4 are satisfied and the sets Y j are as
in (1.5). For any x # n , let #(x) be the solution set of (2.57), i.e., any (p, h) #(x)
solves (2.57). Then
(i) Problem (2.57) is a convex quadratic problem with convex quadratic constraints.
(ii) For x # n , #(x) is nonempty and compact and #(-) is outer-semicontinuous and
bounded on bounded sets.
(iii) If z # n is such that there exist a neighborhood
N(z) of z and an # > 0 such that for any (p, h) #(x), x # N(z), we have
Proof. (i) Under the conditions of Assumptions 1.1 and 2.4, # 2 F (#(x)) is positive
semidefinite and for each j # {1, 2, - , m}, -
strongly convex. Hence (2.57) is a
convex quadratic problem with convex quadratic constraints.
(ii) Since for all y in a bounded neighborhood N(x) of x and j # {1, 2, - , m},
it follows that for all y # N(x) and (p,
#(y,
we have
# as #(p, h)#. (2.61)
Hence, for all x # n , #(x) is nonempty and compact, and #(-) is bounded on bounded
sets.
The outer-semicontinuity of #(-) follows from the fact that #(-) is continuous and the
constraint set in (2.57) is outer-semicontinuous.
(iii) Since z # n is such that #(z). For any x # n , the KKT
conditions for (2.57) are
is the subgradient of -
with respect to h.
Suppose that (p, h) #(z). By (iii) of Theorem 2.8, we have Hence it follows
from (2.62) and the fact that -
which implies that positive
semidefinite. Thus, we have proved that since #(-) is outer-
semicontinuous, it follows that if x # z and (p, h) #(x), then
It now follows from (2.62), (2.64), and the fact that for any y # m , #F (y)/#y j
m}, that there exists a neighborhood N(z) of z such that for all x # N(z),
the multiplier # in the KKT (2.62) must have all components positive and hence for all
x # N(z), the KKT conditions for (2.57) become
Thus, for any x # N(z) and j # {1, 2, - , m}, there exist nonnegative numbers - j,k
satisfying # k#q j
such that for any (p, h) #(x),
where
and for any k # q j such that
we have
We conclude from (2.65), (2.66) and (2.67) that for all x # N(z) and (p, h) #(x),
#, p#
where the last inequality follows from the fact that f j,k (x) # j (x) for all k # q j and
m. By shrinking N(z) if necessary, we conclude from (2.67), (2.70) and Assumptions
1.1 and 2.4 that there exists a positive number # > 0 such that for all x # N(z) and
3. An Algorithm for Solving Generalized
Finite Min-Max Problems
An algorithm for solving generalized finite min-max problems is obviously of interest in
its own right. However, we will also need it as a subroutine for our algorithms for solving
generalized semi-infinite min-max problems. Hence, for the time being, we will assume
that the sets Y j are of the form (1.5) and that the functions f j,k (-) are as in (2.6). As a
result, our generalized finite min-max problem assumes the form (1.1), (1.2), (1.4), with
min
where, in view of Assumption 1.1, the functions F (-) and f j,k (-), j # m, k # q j are all
continuously di#erentiable, where f j,k (-) are defined by (2.6).
We are now ready to state an algorithm for solving generalized finite min-max prob-
lems. This algorithm is a generalization of the Polak-Mayne-Higgins Newton's algorithm
for solving finite min-max problems [18].
Algorithm 3.1 (Solves Problem (3.1))
Parameters. # (0, 1), # (0, 1), and # > 0.
Step
Step 1. Compute the optimality function value # i := #(x i ) and a search direction h i #
according to the formulae (2.19) and (2.20).
Step 2. If # Else, compute the step-size
where N := {0, 1, 2, .
Step 3. Set
replace i by to Step 1. 2
Lemma 3.2 [20] Suppose that Assumption 1.1 holds. Then for any y, y # m such that
y,
Lemma 3.3 [20] Suppose that Assumptions 1.1 and 2.4 are satisfied. Then there exists
a constant # > 0 such that for all x, x # n and # [0, 1],
Theorem 3.4 Suppose that Assumptions 1.1 and 2.4 are satisfied and that all the Y j ,
are of the form (1.5), so that problem (1.1), (1.2), (1.4) reduces to problem (3.1).
If {x i } # i=0 is an infinite sequence generated by Algorithm 3.1 and x # is the unique solution
of (3.1), then {x i } # i=0 converges to x # .
Proof. Suppose that {x i } # i=0 is an infinite sequence generated by Algorithm 3.1. Since
f(-) is strongly convex by Lemma 3.3, the sequence {x i } # i=0 is bounded. Suppose that -
x is
an accumulation point of this sequence. Since the cost function f 0 (-) is continuous, f 0 (-x)
is an accumulation point of the cost sequence. Hence, since, by construction, the cost
sequence {f 0
Now, for the sake of contradiction, suppose that #(-x) < 0. Since for any x # n ,
H(x) is compact, and H(-) is bounded on bounded sets and is outer-semicontinuous ((iv)
of Theorem 2.8), it follows from Theorem 5.3.7 (b) in Polak [17] that there exists a
subsequence {j i } # i=0 of the integers such that x
x and h j i # - h # H(-x), as i #. It
follows from (ii) and (iii) of Theorem 2.8 that -
be such that 0 < # < 1. Then it follows from the definition of the directional
derivative of f 0 (-) that there exists a k # N such that
Hence,
for all # > 0 such that
. (3.10)
# := 1# . Then, since f 0 (-) and #(-) are continuous and h j i # - h, as i #, there
exists a # > 0 such that for all x
which shows that for all x
. Next, since #(-) is continuous, there
exists -
# (0, #) such that for all x
It therefore follows from
the step-size rule (3.2) that for all x
#),
#(-x) . (3.12)
implies that f 0
contradicting the fact that f 0 Hence we conclude that
and therefore that -
strongly convex, the whole
sequence {x i } converges to x # . 2
4. Rate of Convergence of Algorithm 3.1
Proposition 4.1 Suppose that Assumptions 1.1 and 2.4 are satisfied and that - x is the
unique solution of f 0 (-). Then for all x # n ,
Proof. By Lemma 3.3, f 0 (-) is a strongly convex function. Hence, for any x # n we
have
#F
#F
c
#F
c
where - q j (x) is defined by (2.7). It now follows from (2.5) and (4.2) that
Proposition 4.2 Suppose that Assumptions 1.1 and 2.4 are satisfied. Then for any
compact convex set S there exists a # > 0 such that for any x, z # S,
defined in (2.17).
Proof. First, it follows from Polak [17, Lemma 2.5.4] or [18], that there exists a constant
such that for any x, z # n ,
be a compact set, and let L 2 < # be a Lipschitz constant for # 2 F (-) on S,
such that for any z # S,
#F (#(z))# L 2 . (4.6)
Then for all x, z # S,
where L 3 := mL 2 L 1 /6. Since, by assumption, S is compact, it follows that there exists a
positive number L 4 such that for all x, z # S,
and
Hence for all x, z # S,
with
4 . (4.12)
Similarly, we can prove that for all x, z # S,
Thus we have shown that (4.4) holds. 2
Theorem 4.3 Suppose that Assumptions 1.1 and 2.4 are satisfied, that all the Y j ,
are of the form(1.5), so that problem (1.1), (1.2), (1.4) reduces to problem (3.1). If
is a sequence constructed by Algorithm 3.1, in solving problem (3.1), then, {x i } # i=0
converges superlinearly with Q-order at least 3/2.
Proof. First we will prove that after a finite number of iterations, the step-size # i
stabilizes to 1, so that eventually x holds for the sequence {x i } # i=0 . We will
then complete our proof by making use of results in [17, Corollary 2.5.8].
It follows from Theorem 3.4 that the sequence {x i } # i=0 converges to the unique minimizer
x of f 0 (-). Hence we conclude from Theorem 2.8 that
In view of this, we conclude from Lemma 2.6 that there exist a positive number # > 0
and a nonnegative integer i 0 such that for all
Suppose that i 0 is su#ciently large to ensure that for all
x# . (4.16)
Then, making use of (4.1), we find that, for
because -
by (4.15). It now follows from Proposition 4.2 that
there exists a # > 0 such that for all
Now, by Theorem 2.9, there exist a positive integer and an # 1 > 0 such that
for all
Next, Proposition 4.2 and (4.15), imply that for all
Hence, from (4.20) and (4.19), we have
It now follows from (4.21) and the fact that h i # 0 as i # that for all i su#ciently
large,
We therefore conclude from [17, Corollary 2.5.8] or [18], (4.18) and (4.19) that {x i } # i=0
converges to -
x superlinearly with Q-order at least 3/2. 2
5. An Algorithm for Solving Generalized
Semi-Infinite Min-Max Problems
We are now ready to tackle the generalized semi-infinite min-max problems defined in
(1.1), (1.2), (1.4). Such problems can be solved only by discretization techniques. We
will use discretizations that result in consistent approximations (as defined in Section 3.3
of [17]) and use them in conjunction with a master algorithm that calls Algorithm 3.1 as
a subroutine. We will see that under a reasonable assumption, the resulting algorithm
retains the rate of convergence of Algorithm 3.1.
5.1. Consistent Approximations
Let N 0 be a strictly positive integer, and, for N # N 0 := {N 0 ,
be finite cardinality subsets of Y j , j # m, such that Y j,N # Y j,N+1 for all N and the closure
of the set lim Y j,N is equal to Y j , j # m. Then we define the family of approximating
problems PN , N # N 0 , as follows:
PN min
where
N (x)), and for j # m,
It should be clear that the approximating problems PN are of the form (3.1) and that
one can define optimality functions # N (-) for them of the form (1.5). We will refer to the
original problem (1.1), (1.2), (1.4) as P.
Definition 5.1 [17] We will say that the pairs (PN , # N ), in the sequence {(PN , # N )} N#N0
are consistent approximations to the pair (P, #), if the problems PN epi-converge to P,
(i.e., the epigraphs of the f 0
N (-) converge to the epigraph of f 0 (-) in the sense defined in
Definition 5.3.6 in [17]), and for any infinite sequence {xN } N#K , K # N 0 , such that
Assumption 5.2 We will assume as follows:
(a) For every N # N 0 , the problem (5.1) has a solution.
(b) There exists a strictly positive valued, strictly monotone decreasing function # :
N #, such that #(N) # 0, as N #, and a K < #, such that for every
there exists a y # Y j,N such that
#y - y # K#(N). (5.4)For example, if for all j # m, Y j is the unit cube in # m j , i.e., Y
then we can define Y
I
with a(N) := 2 N-N 0 . In this case it is easy to see that
constructions can be obtained for other polyhedral sets.
For any x, h # n and w # m , we define
uN (x, h, w) := #F (#N (x)), -
and
where
and
We infer from (2.19) that the optimality functions # N (-), for the problems PN have
the following form:
{ min
h, w))}. (5.9)
Since the cardinality of the sets Y j,N is finite, it is obvious that the # N (x) can be evaluated.
As was also done in the Polak-Mayne-Higgins Rate-Preserving method [19] (see also
[20]), we use an alternative optimality function for the problems PN for precision adjustment
in our algorithm. This optimality function is defined by
#F
where
#F
with # > 0, a constant.
Similarly (as in [20]), we define an alternative optimality function for the problem P
by
#F
where
#F
with # > 0 the same constant as in (5.11).
Proposition 5.3 [20] Suppose that Assumptions 1.1 and 5.2 are satisfied, and that for
N (-) is defined by (5.2) and -
# N (-) by (5.10). Let S # n be a bounded subset
and let L < # be a Lipschitz constant valid for the functions # j (-) and # x # j (-) on
q. Then there exists a constant C S < # such that for all x # S, N # N 0 ,
and
| -
5.2. The Superlinear Rate Preserving Algorithm
Algorithm 5.4 (Solves Problem (1.1), (1.2), (1.4))
Parameters. # (0, 1), # > 0, D > 0, # > 3.
Step
Step 1. Compute the optimality function value -
according to (5.10) and (5.11), i.e.,
#F
where
#F
(#N
Step 2. If
go to Step 3. Else, replace N by N + 1, and go to Step 1.
Step 3. Compute the second optimality function value # N according to (5.9), i.e.,
{ min
and the corresponding search direction h i according to
{ min
Step 4. Compute the step-size
and go to Step 5.
Step 5. Set
to Step 1. 2
Remark.
(a) It follows from Proposition 5.3 that -
the loop consisting of Step 1 and Step 2 of Algorithm 5.4 yields a finite
discretization parameter N i . For simplicity, we will assume that Algorithm 5.4 does
not produce an iterate x i such that -
(b) Note that the work needed to compute x i by Algorithm 5.4 increases with the iteration
number i. 2
Lemma 5.5 Suppose that Assumptions 1.1, 2.4, and 5.2 are satisfied, and that Algorithm
5.4 has constructed a sequence {x i } # i=0 together with the corresponding sequence of
discretization parameters {N i } # i=0 . If the sequence {x i } # i=0 has at least one accumulation
point, then N i #, as i #.
Proof. For the sake of contradiction, suppose that the sequence {x i } # i=0 has an accumulation
point -
x and that the sequence {N i } # i=0 is bounded. Then, because {N i } # i=0 is a
monotonically increasing sequence of integers, there exists an i 0 # N , such that for all
. Hence for the construction of the sequence {x i } # i=0 is
carried out by Algorithm 3.1 applied to problem (5.1) with Furthermore, it
follows from (5.18) that there exists an # > 0, such that -
However, it follows from Theorem 3.4 that # N # and from the continuity of -
that - # N #(x i
where the infinite subsequence {x i } i#K ,
converges to -
which contradicts the previous finding, and hence completes our
proof. 2
Theorem 5.6 Suppose that Assumptions 1.1, 2.4, and 5.2 are satisfied, and that Algorithm
5.4 has constructed a bounded sequence {x i } # i=0 . Then every accumulation point -
x
of {x i } # i=0 satisfies -
Proof. By applying Theorem 3.3.23 of [17] or Theorems in Section 5 of [16] and Lemma
5.5 to Algorithm 5.4, we obtain the desired result. 2
Theorem 5.7 Suppose that Assumptions 1.1, 2.4, and 5.2 are satisfied, and that Algorithm
5.4 has constructed a bounded sequence {x i } # i=0 . Then {x i } converges to the unique
x of f 0 (-) with Q-order 3/2.
Proof. First, by Theorem 5.6 and the fact that f 0 (-) has a unique minimizer -
x, the whole
sequence {x i } converges to -
x. Hence, one can deduce from Theorem 4.3 and the proof of
[17, Theorem 3.4.20], that {x i } converges to - x with Q-order 3/2. Since the derivation is
straightforward, we omit the details here. 2
6. Some Numerical Results
We now present some numerical results that illustrate the behavior of the algorithm
proposed in Section 5 for generalized semi-infinite programming problems. The algorithm
was implemented in Matlab. Throughout the computational experiments, the parameters
used in the algorithm were 3.1. For both
examples, we used the starting point (1, 1). The iteration of the algorithm is stopped at x i
if for some N the meshsize #(N) < 0.005 and |# N developed
in [24], which was based on a smoothing Newton method [23] for variational inequalities,
was used to solve our search direction finding subproblem (2.57).
Example 1. In this case, f 0
with
and
Example 2. In this case, the functions f are also defined as in
Example 1, but F (-) is defined by
The numerical results are summarized in Table 1 and Table 2. In these two tables
the first column gives the residue ||x i -
x|| (we used the last iterate as a substitute for
x) and the discretization level (the meshsize at the present level is decreased to half of
the previous one) refined by the master algorithm at the i-th step. It is clear from the
numerical results that the rate of convergence is superlinear.
Iteration
Discretization level

Table

1: Numerical results for Example 1
Iteration
Discretization level

Table

2: Numerical results for Example 2
7. Conclusion
We have presented two superlinearly converging algorithms, one for solving finite generalized
min-max problems of the form (1.1), (1.2), (1.3) and one for solving generalized
semi-infinite min-max problems of the form (1.1), (1.2), (1.4). These algorithms were
obtained by making use of the concepts underlying the construction of the Polak-Mayne-
Higgins Newton's method [18] and the Polak-Mayne-Higgins Rate-Preserving method [19],
respectively. The construction of the algorithms depends on the cost unction having a
subgradient and their rate of convergence depends on convexity and second order smooth-
ness, and hence Assumption 2.4 is essential.
Our numerical results are consistent with our theoretical prediction that the algorithms
converge Q-superlineary.

Acknowledgement

. The authors wish to thank Prof. R. T. Rockafellar for suggesting
the function -
as a way to get around the possible non-convexity of the function
in h, as well as for the formula (2.57) which shows that our optimality function
is defined by a quadratically constrained quadratic programming problem.



--R

"Nondi#erentiable optimization via approximation,"
"Quasidi#erentiable functions: necessary conditions and descent directions,"
"An algorithm for minimizing a certain class of quasidi#erentiable functions,"

"A smooth transformation of the generalized minimax problem,"
"A quadratic approximation method for minimizing a class of qua- sidi#erentiable functions,"
"A linearization method for minimizing certain quasidi#erentiable functions,"
"Randomized search directions in descent methods for minimizing certain quasidi#erentiable functions,"
"Descent methods for quasidi#erentiable minimization,"
"Proximal control in bundle methods for convex nondi#erentiable minimization,"
"The method of common descent for a certain class of quasidi#erentiable functions,"
"Algorithms for a class of nondi#erentiable problems,"
"On the rate of convergence of certain methods of centers,"
"Basics of minimax algorithms,"
"Rate-preserving discretization strategies for semi-infinite programming and optimal control,"
"On the use of consistent approximations in the solution of semi-infinite optimization and optimal control problems,"
Optimization: Algorithms and Consistent Approximations
"A superlinearly convergent algorithm for min-max problems,"
"On the extension of Newton's method to semi-infinite for minimax problems,"
"First-Order algorithms for generalized finite and semi-infinite min-max problems,"
"On the minimization of a quasidi#erentiable function subject to equality-type quasidi#erentiable constraints,"
Numerical Methods in Extremal Problems (Chislennye Metody v Ekstremal'nykh Zadachakh)
"A new look at smoothing Newton methods for non-linear complementarity problems and box constrained variational inequalities,"
"Numerical experiments for a class of squared smoothing Newton methods for box constrained variational inequality problems"
--TR

--CTR
Huang , Defeng Sun , Gongyun Zhao, A Smoothing Newton-Type Algorithm of Stronger Convergence for the Quadratically Constrained Convex Quadratic Programming, Computational Optimization and Applications, v.35 n.2, p.199-237, October   2006
optimality functions;superlinear convergence;consistent approximations;generalized min-max problems;second-order methods