INTRODUCTION
The minimax optimization problem can be stated as
where f_{j}(j=1~m) are realvalued functions defined on R^{n}.
The objective function M_{f}(x) has discontinuous first partial derivatives at points where two or more of the functions f_{j}(x) are equal to M_{f} even if f_{j}(x)(j=1~m) have continuous first partial derivatives. Thus we can not use directly the well known gradient methods to minimizeFor excellent works on this topic and its applications was reported^{[27]}.
The minimax problem (1) is equivalent to the following nonlinear programming:
According to (2), the KT condition of (1) is obtained as follows:
where:
The active set is denoted as follows:
A lot of approaches have been proposed for solving the problem (1), most of them transform the minimax problem into the nonlinear programming problem (2) and solves it by wellestablished methods. Vardi^{[8]} uses some slack variables to handle inequality constraints of (2), then solves only equalityconstrained minimization problem taking advantage of trustregion strategy.
Charalambous and Conn^{[9]} propose an algorithm to solve the minimax
problem directly, in which two distinct search directions are necessary to compute:
The first, the horizontal direction, attempts to reduce M_{f}(x)
whilst, at the same time, keeping those functions whose values are close to
M_{f}(x), approximately equal. The second, the vertical direction,
amounts to attempting to decrease the error to within which those functions
are equal to M_{f}(x) by means of linearization. Then, under assumptions
that the minimax solution is unique, that f_{j}(j=1~m) are convex and
twice differentiable and that the strict complementarity condition is satisfied,
global convergence is proven. However, computational effort is large and the
rate of convergence is at most linear.
Due to its superlinear convergence rate, the sequential quadratic programming
(SQP) methods are considered among the most effective methods for solving nonlinear
programming problems. A new algorithm is proposed by Zhou and Tits^{[10]}
with taking advantage of the idea of SQP algorithms to solve the problem (1).
There, in order to avoid the Maratos effect, it takes a nonmonotone line search
along a direction d which is obtained by solving a QP subproblem. However, it
is observed that, with such a line search and the direction d, it may not ensure
that the full step of one is accepted. For this reason, it is necessary to perform
a nonmonotone arc search along based
on a correction which is obtained by solving another QP subproblem. Moreover,
its convergence rate is twostep supperlinear.
A SQP type algorithm is proposed by Xue^{[11]} to solve the problem (1). However, in order to obtain the onestep superlinear convergence rate, there it is necessary to make two additional assumptions which are too strong: Firstly, the entire sequence generated by the algorithm converges to the KT point of (1); Secondly, the stepsize is always equal to one after finite iterations.
In this paper, a new SQP algorithm is proposed to solve the problem (1) directly according to the KT condition (3). This algorithm overcomes the shortcomings just pointed out. It performs a monotone line search along a direction which is obtained by solving only one QP subproblem. With such a particular line search, we point out, because of the intrinsic properties of the minimax problem (1) in contrast with the nonlinear programming, unlike^{[10]} there does not exist any Maratoslike effect and the search direction is not necessary to revise any more. Global convergence is obtained without the abovementioned strong assumptions in^{[9]}. Under some suitable conditions which are weaker than those in^{[11]} onestep superlinear convergence rate is proven.
Description of algorithm: The following algorithm is proposed for solving problem (1).
Algorithm A
Step 1Initialization and date: x^{0} ∈ R^{n},
B_{0} ∈ R^{nxn} a symmetric positive definite matrix.
Step 2Computation of the main search direction d^{k}: Compute (z^{k},d^{k}) by solving the following quadratic problem at x^{k}:
Let λ^{k} be the corresponding multipliers vector. If (z^{k},d^{k})= (0, 0), STOP;
Step 3The line search: Compute t_{k}, the first number t of the sequence {1,½,¼,.....} satisfying
Step 4Updates: Compute a new symmetric definite positive matrix B_{k+1}. Like Vardi^{[8]} we use Powell's modification^{[12]}
where:
Let x^{k+1} = x^{k} + t_{k}d^{k},k
= k+1. Go back to step 2.
Global convergence of algorithm: It is first shown that Algorithm A is well defined. The following general assumptions are true throughout the paper.
A1: f_{j}(j=1~m) are continuously differentiable.
A2: For all x∈R^{n}, the vectors are
linearly independent.
A3: There exist two constants 0<a≤b, such that ad^{2}≤d^{T}B_{k}d≤bd^{2}, for all k, for all d∈R^{n}.
Lemma 1: The solution (z^{k},d^{k}) of the quadratic subproblem (5) is unique and z^{k}+½(d^{k})^{T} B_{k}d^{k}≤0.
Proof: Since (0,0) is a feasible point of (5) and B_{k} is positive definite, it is clear that the claim holds.
Lemma 2: Let (z^{k},d^{k}) be the solution of the QP (5) at x^{k}, the following are equivalent:
(i) 
(z^{k},d^{k})=(0,0);

(ii) 
z^{k}=0; 
(iii) 
d^{k}=0; 
(iv) 
z^{k}+½(d^{k})^{T} B_{k}d^{k}=0. 
Proof: (i)⇒(ii). It is clear; (ii)⇒(iii) Since z^{k}=0,
then d^{k}=0 by Lemma 1; (iii)⇒(iv). Since I(x^{k})={jf_{j}(x^{k})=M_{f}(x^{k}),j∈I}is
nonempty, let j∈I(x^{k}), (5) implies that z^{k}≥0.
So, z^{k}+½(d^{k})^{T} B_{k}d^{k}≥0,
thereby, z^{k}+½(d^{k})^{T} B_{k}d^{k}=0;
(iv)⇒(i). Since z^{k}+½(d^{k})^{T} B_{k}d^{k}=0,
it is clear that(0,0) is unique solution of (5) by Lemma 1, that is to say (z^{k},d^{k})=(0,0).
Lemma 3: If (z^{k},d^{k})=(0,0), then x^{k} is a KT point of (1). If x^{k} is not a KT point of (1), then z^{k}<0, d^{k}≠0 and
Proof: From (5), we have
If (z^{k},d^{k})=(0,0), then
It shows that x^{k} is a KT point.
If x^{k} is not a KT point, then (z^{k},d^{k})≠(0,0).
So,
z^{k}+½(d^{k})^{T}
B_{k}d^{k}<0, z^{k}<½(d^{k})^{T}
B_{k}d^{k}≤0, 
and
The claim holds.
Lemma 4: Algorithm A is well defined.
Proof: We only need to show that the line search yields a step t_{k}=(½)^{i} for some finite i=i(k). Denote
For j∈I\I (x^{k}), since f_{j}(x^{k})<, M_{f}(x^{k})
continuity of f_{j} implies that there exists some ,
such that a_{k}≤0.
For j∈I (x^{k}), from (5), the fact α<1 implies that there
exists some ,
such that a_{k}≤0.
Define .
It is clear that the line search condition (6) is satisfied for all t in .
In the sequel, we'll prove that any accumulation point x^{*} of {x^{k}}generated by the algorithm must be a KT point of the problem (1). Since there are only finitely many choices for sets I(x^{k})⊆I, we might as well assume that there exists a subsequence K, such that
where I_{*} is a constant set.
Lemma 5: If x^{k}⇒x^{*}, B_{k}⇒B_{*}, k∈K, then d^{k}⇒0, k∈K.
Proof: First of all, in view of (6) and Lemma 3, it is evident that {M_{f}(x^{k})} is monotonous decreasing. Hence, considering to {x^{k}}_{k∈K} x*and continuity of M_{f}(x) it holds that
Suppose by contradiction that d^{*}≠0, then z^{*}<0.
Since
Let k∈K, k⇒∞, then
The corresponding QP problem (5) at x^{*} is
It is clear that (z^{*}, d^{*}) is a feasible solution of (13)
and B_{*} is positive definite. So, we might as well let
be the unique solution of (13). Since
as k∈K, k⇒∞ we obtain that
So, it can be seen that thereby,
and for k∈K, k large enough, we have
From (14), similar to Lemma 4, we can conclude that the stepsize t_{k}
obtained by the linear search is bounded away from zero on K, i.e.,
t_{k}≥t_{*} = inf{t_{k},
k∈K}, k∈K 
So, from (6), (12), we get
It is contradiction, which shows that d^{k}⇒0, k∈K.
According to Lemma 3, Lemma 5 and the fact that (z^{*}, d^{*}) is the solution of (13) , we can get the following convergent theorem.
Theorem 1: The algorithm A either stops at the KTpoint {x^{k}} of (1) in finite iteration, or generates an infinite sequence {x^{k}} whose all accumulation points are KT point of (1).
Rate of convergence: Now we strengthen the regularity assumptions on
the functions involved. Assumption A1 are replaced by:
A1^{’}: 
The functions f_{j}(j=1~m) are two times continuously
differentiable.
We also make the following additional assumptions: 
A4: 
The sequence generated by the algorithm possesses an accumulation point
a (in view of Theorem 1, a KT point). 
A5: 
B_{k}⇒B_{*}, k⇒∞ 
A6: 
The matrix s
nonsingular and it holds that 


where ,
is the corresponding KT multipliers of x^{*} and 
A7: 
The strict complementary slackness are satisfied at the KT point pair
(x^{*}, u^{*}), i.e., 
Theorem 2: The KuhnTucker point x^{*} is isolated.
Proof: This proof is similar to that of^{[13]} but with some technical differences since assumption A2 about the linear independence constraint qualification is different with that of the nonlinear programming and the details are omitted.
Lemma 6: The entire sequence {x^{k}} converges to the KT point x^{*}, i.e., x^{k}⇒x^{*}, k⇒∞.
Proof: From (5) and (6), we have that
So, from (12), it holds that
Thereby, according to assumptions A6, A7, Theorem 2 and proposition by Painer and Tits^{[14]} we have x^{k}⇒x^{*}, K⇒∞
Lemma 7: For K⇒∞, we have
d^{k}⇒0,λ^{k}⇒u^{*},
L_{k}≡I(x^{*}), z^{k}=O (d^{k}) 
where:
Proof: According to Lemma 5 and x^{k}⇒x^{*}, B_{k}⇒B_{*}, K⇒∞, it holds that
d^{k} ⇒ 0, z^{k} ⇒ 0, k ⇒ ∞.
Since (x^{*}, u^{*}) is a KT point pair of (1), we have
Denote
From A2, it is clear that
and
At the same time, denote
From (9), we have
thereby,
it is obvious , for k large enough, that
So,
In addition, according to d^{k}⇒0, z^{k}⇒0 and (18), it is clear that L_{k}⊆I(x^{*}).
On the contrary, for j∈I(x^{*}), assumption A7 implies that u_{j}^{*}>0. So, λ^{k}_{j}>0 for k large enough, thereby, it holds that
f_{j}(x^{k})M_{f}(x^{k}) +∇f_{j}(x^{k})^{K}d^{k}z^{k}=0,i
.e., j∈L_{k}.
So, L_{k}≡I(x^{*}).
Thereby, from I(x^{k})⊆I_{*}≡L_{k} and A2, it is clear that Z^{k}=O(d^{k}).
In order to obtain superlinear convergence, we make the following assumption:
A8: 
∇^{2}f_{j}(x) (j=1~m) are Lipschitz
continuous on some ball B(x^{*}, ∈)of radius ε>0 about
x^{*}, i.e., there exist some v_{j}>0, such that 
Lemma 8: Under assumptions A1A8, x^{k}+d^{k}x^{*}=o(x^{k}x^{*})
if and only if the following condition holds:
A9: 
The sequence of matrices {B_{k}}satisfies 
Proof: This proof is similar to the proof of Theorem by Xue^{[11]}.
Lemma 9: If assumptions A1A9 are true, then, for k large enough, t_{k}≡1.
Proof: Firstly, we prove, for k large enough, that
Let
s_{j}=f_{j}(x^{k}+d^{k})M_{f}
(x^{k})αz^{k}=f_{j}(x^{k})M_{f}
(x^{k})+∇f_{j}(x^{k})^{T}d^{k}αz^{k}+o(d^{k}),
j∈I.
Denote
I((x^{k}+d^{k})={jf_{j}(x^{k}+d^{k})
= M_{f} (x^{k}+d^{k})}
it is obvious, for k large enough, that I(x^{k}+d^{k})⊆I_{*}.
For j∈I\I(x^{*}), the facts f_{j}(x^{*})<M_{f}(x^{*})
and d^{k}⇒0, z^{k}=O(d^{k})
imply that s_{j}≤0, ( for k large enough).
For j∈I\I_{*} (x^{k}+d^{k}), from (5), the facts
α<1, d^{k}⇒0, z^{k}=O(d^{k})
imply that s_{j}≤0, ( for k large enough).
From above analysis, in order to prove that (21) are true, we only prove, for
k large enough, that
f_{j}(x^{k}+d^{k}) = M_{f}(x^{k}+d^{k})≤M_{f}(x^{k})+αzx^{k},∀_{j}∈I(x^{k}+d^{k}).
i.e.,
While, it is always proven that
Thereby, it only needs to prove that
i.e.,
From (9) and L_{k}≡I(x^{*}), we have
Denote
from (22) and A8, we get
Since a∈(0,½), it holds that s≤0. So, (21) are true, for k large enough. Thereby, we have, for k large enough, that
M_{f}(x^{k}+d^{k})≤M_{f}(x^{k})+αz^{k}
i.e., t_{k}≡1 . The claim holds.
From Lemma 8 and Lemma 9, we can get the following theorem:
Theorem 3: Under all abovementioned assumptions, the algorithm is superlinearly convergent, i.e., x^{k+1}x^{*}=o(x^{k}x^{*}).
Numerical experiments: We carry out numerical experiments based on the algorithm. The results show that the algorithm is effective.
During the numerical experiments α=0.25 and B_{0}=I, the nxn unit matrix. B_{k} is updated by the BFGS formula (8). In following Tables, IP is the initial point, NIT is the number of iterations of algorithm, AS is the approximate solution.
Problem 1: (^{[9]}). Minimize the maximum of the following three
functions:
Problem 2: (^{[11]}). Minimize the maximum of the following
six functions:
Problem 3: RosenSuzuki Problem (^{[9,11]}). Minimize the maximum
of the following functions:
Problem 4: Wong problem 1 (^{[9,11]}). Minimize the maximum
of the following functions:
Problem 5: Wong problem 2 (^{[11]}). Minimize the maximum of
the following functions:
In this paper, detailed information about solutions to above mentioned problems is listed as follows:
Table 1: 
The information of the solution to Problem 1 

Table 2: 
The information of the solution to Problem 2 

Table 3: 
The information of the solution to Problem 3 

Table 4: 
The information of the solution to Problem 4 

Table 5: 
The information of the solution to Problem 5 

ACKNOWLEDGMENT
The author would like to thank the refree for his helpful comments. This work was supported in part by the NNSF (103G1003) and GIETSF (D20350) of China.