# A Simple SQP Algorithm for Constrained Finite Minimax Problems

Authors: Lirong Wang; Zhijun Luo
Journal: The Scientific World Journal
 (2014)

---

## Abstract

A simple sequential quadratic programming method is proposed to solve the constrained minimax problem. At each iteration, through introducing
an auxiliary variable, the descent direction is given by solving only one quadratic programming. By solving a corresponding quadratic programming, a high-order revised direction is obtained, which can avoid the Maratos effect. Furthermore, under some mild conditions, the global and superlinear convergence of the algorithm is achieved. Finally, some numerical results reported show that the algorithm in this paper is successful.


---

## Body

## 1. Introduction

Consider the following constrained minimax optimization problems:(1)min⁡x∈RnF(x),s.t.gj(x)≤0,j∈J={1,2,…,m1},hl(x)≤0,l∈L={1,2,…,m2},
where F(x)=max⁡{fi(x)∣i∈I={1,2,…,m}} and fi(x),gj(x),hl(x):Rn→R are continuously differentiable.Minimax problem is one of the most important non-differentiable optimization problems, and it can be widely applied in many fields (such as [1–4]). In real life, a lot of problems can be stated as a minimax problem, such as financial decision making, engineering design, and other fields which wants to obtain the objection functions minimum under conditions of the maximum of the functions. Since the objective function F(x) is non-differentiable, we cannot use the classical methods for smooth optimization problems directly to solve such constrained optimization problems.Generally speaking, a lot of the schemes have been proposed for solving minimax problems, by converting the problem (1) to a smooth constrained optimization problem as follows
(2)min⁡z,s.t.fi(x)≤z,i∈I,gj(x)≤0,j∈J,hl(x)=0,l∈L.
Obviously, from the problem (2), the KKT conditions of (1) can be stated as follows:
(3)∑i∈I‍λi∇fi(x)+∑j∈J‍μj∇gj(x)+∑j∈L‍νj∇hj(x)=0,λi≥0,fi(x)-F(x)≤0,λi(fi(x)-F(x))=0,i∈I,μj≥0,gj(x)≤0,μjgj(x)=0,j∈J,∑i∈I‍λi=1,hl(x)=0,l∈L,
where λi, μj, and νj are the corresponding vector. Based on the equivalent relationship between the K-T point of (2) and the stationary point of (1), a lot of methods focus on finding the K-T point of (1), namely, solving (3). And many algorithms have been proposed to solve minimax problem [5–15]. Such as [5–8], the minimax problems are discussed with nonmonotone line search, which can effectively avoid the Maratos effect. Combining the trust-region methods with the line-search methods and curve-search methods, Wang and Zhang [9] propose a hybrid algorithm for linearly constrained minimax problems. Many other effective algorithms for solving the minimax problems are presented, such as [11–15].Sequential quadratic programming (SQP) method is one of the efficient algorithms for solving smooth constrained optimization problems because of its fast convergence rate. Thus, it is studied deeply and widely (see, e.g., [16–20], etc.). For typical SQP method, the standard search direction d should be obtained by solving the following quadratic programming:
(4)min⁡∇F(x)Td+12dTHd,s.t.gj(x)+∇gj(x)Td≤0,j∈J,hl(xk)+∇hl(xk)Td=0,l∈L,
where H is a symmetric positive definite matrix. Since the objective function F(x) contains the max operator, it is continuous but non-differentiable even if every constrained function fi(x)(i∈I) is differentiable. Therefore this method may fail to reach an optimum for the minimax problem. In view of this and combining with (2), one considers the following quadratic programming through introducing an auxiliary variable z:
(5)min⁡z+12dTHd,s.t.fi(x)+∇fi(x)Td≤z,i∈I,gj(x)+∇gj(x)Td≤0,j∈J,hl(xk)+∇hl(xk)Td=0,l∈L.
However, it is well known that the solution d of (5) may not be a feasible descent direction and can not avoid the Maratos effect. Recently, many researches have extended the popular SQP scheme to the minimax problems (see [21–26], etc.). Jian et al. [22] and Q.-J. Hu and J.-Z. Hu [23] process pivoting operation to generate an ɛ-active constraint subset associated with the current iteration point. At each iteration of their proposed algorithm, a main search direction is obtained by solving a reduced quadratic program which always has a solution.The feasible direction method (MFD) (see [27, 28], etc.) is another effective way for solving smooth constrained optimization problems. An advantage of MFD over the classical SQP method is that a feasible direction of descent can be obtained by solving only one quadratic programming. In this paper, to obtain a feasible direction of descent and reduce the computational cost, we construct a new quadratic programming subproblem. Suppose xk is the current iteration point; at each iteration, the descent direction dk is obtained by solving the following quadratic programming subproblem:
(6)min⁡z+12dTHkd,s.t.fi(xk)+∇fi(xk)Td-F(xk)≤z,i∈I,gj(xk)+∇gj(xk)Td≤ηkz,j∈J,hl(xk)+∇hl(xk)Td=0,l∈L,
where Hk is a symmetric positive definite matrix and ηk is nonnegative auxiliary variable. In order to avoid the Maratos effect, a height-order correction direction is computed by the corresponding quadratic programming:
(7)min⁡z+12(dk+d)THk(dk+d),s.t.fi(xk+dk)+∇fi(xk+dk)Td-F(xk+dk)≤z,i∈I,gj(xk+dk)+∇gj(xk+dk)Td≤ηkz,j∈J,hl(xk+dk)+∇hl(xk+dk)Td=0,l∈L.
Under suitable conditions, the theoretical analysis shows that the convergence of our algorithm can be obtained.The plan of the paper is as follow. The algorithm is proposed in Section2. In Section 3, we show that the algorithm is globally convergent, while the superlinear convergence rate is analyzed in Section 4. Finally, some preliminary numerical tests are reported in Section 5.


## 2. Description of the Algorithm

Now we state our algorithm as follows.Algorithm 1.
j
d
j
h
j
k
Step
0. Given initial point x0∈Rn, define a symmetric positive definite matrix H0∈Rn×n. Choose parameters α∈(0,1/2), η0>0, and γ∈(0,1). Set k=0.
Step
1. Compute (dk,zk) by the quadratic problem (6) at xk. Let (λk,μk,νk) be the corresponding KKT multipliers vector. If dk=0, then STOP.
Step
2. Compute (d~k,z~k) by the quadratic problem (7).
Set(λ~k,μ~k,ν~k) as the corresponding KKT multipliers vector. If ∥d~k∥>∥dk∥, set d~k=0.
Step
3 (the line search). A merit function is defined as follows:
(8)w(x)=F(x)+rφ(x)+r∑l∈L‍|hl(x)|,
where φ(x)=max⁡{gj(x),j∈J;0} and r is a suitable large positive scalar.Computetk, the first number t in the sequence {1,1/2,1/4,1/8,…} satisfying
(9)w(xk+tdk+t2d~k)≤w(xk)-αt(dk)THkdk.Step
4 (update).   Obtain Hk+1 by updating the positive definite matrix Hk using some quasi-Newton formulas. Set xk+1=xk+tdk+t2d~k, ηk+1=min⁡{η0,∥dk∥γ}. Set k:=k+1. Go back to Step 1.


## 3. Global Convergence of the Algorithm

For convenience, we denote(10)I(x)={i∈I∣fi(x)=F(x)},J(x)={j∈J∣gj(x)=φ(x)}.In this section, we analyze the convergence of the algorithm. The following general assumptions are true throughout this paper.(H  3.1)
The functionsfi(x), i∈I, gj(x), j∈J, and hl(x), l∈L, are continuously differentiable.(H  3.2)
∀x∈Rn; the set of vectors(11){(-1∇fi(x)),i∈I(x);(0∇gj(x)),j∈J(x);(0∇hl(x)),l∈L}is linearly independent.
(H  3.3)
There exista,b>0, such that a∥d∥2≤dTHkd≤b∥d∥2, for all k∈R and d∈Rn.Lemma 2.
Suppose that (H 3.1)–(H 3.3) hold, matrixHk is symmetric positive definite, and (dk,zk) is an optimal solution of (6). Then(1)
zk+(1/2)(dk)THkdk≤0, zk≤0,(2)
ifdk=0, then xk is a K-T point of problem (1).Proof.
(1) For(0,0)∈Rn+1 is a feasible solution of (6) and Hk is positive definite, one has
(12)zk+12(dk)THkdk≤0,zk≤-12(dk)THkdk≤0.
Further, if dk≠0, then zk<0.
(2) Firstly, we provedk=0⇔zk=0. If zk=0, then (1/2)(dk)THkdk=(1/2)(dk)THkdk+zk≤0. For the positive definite property of Hk, it has dk=0. On the other hand, if dk=0, in view of the constraints
(13)fi(xk)+∇fi(xk)Tdk-F(xk)≤zk,i∈I(xk),
we have zk≥0. Combining zk≤0, we have zk=0.
Secondly, we show thatxk is a K-T point of problem (1) when dk=0. From the problem (6), the K-T condition at xk is defined as follows:
(14)Hkdk+∑i∈I‍λik∇fi(xk)+∑j∈J‍μjk∇gj(xk)+∑l∈L‍νlk∇hl(xk)=0,∑i∈I‍λik+ηk∑j∈J‍μjk=1,λi≥0,0≤λik⊥(fi(xk)+∇fi(xk)Tdk-F(xk)-zk)≤0,i∈I,μj≥0,0≤μjk⊥(gj(xk)+∇gj(xk)Tdk-ηkzk)≤0,j∈J,hl(xk)+∇hl(xk)Tdk=0,l∈L.
If dk=0, then zk=0, and according to the definition of ηk in   Step 4, we have ηk=0. Furthermore, it holds that
(15)∑i∈I‍λi∇fi(x)+∑j∈J‍μj∇gj(x)=0,∑i∈I‍λi=1,λi≥0,fi(x)-F(x)≤0,λi(fi(x)-F(x))=0,i∈I,μj≥0,gj(x)≤0,μjgj(x)=0,j∈J,hl(xk)=0,l∈L.
That is to see that the results hold.From Lemma2, it is obvious, if dk≠0, that the line search in Step 3 yields is always completed.Lemma 3.
Ifdk≠0 and if r satisfies r≥∥μ∥∞ and r≥∥ν∥∞, the line search in Step 3 of the algorithm is well defined.Proof.
Firstly, we consider the functionsfi(x+tdk+t2d~), i∈I, gj(x+td+t2d~), j∈J, and hl(x+td+t2d~), l∈L, of the Taylor expansion at x. Then, we obtain
(16)w(x+td+t2d~)=w~(x;td)+o(t),
where
(17)w~(x;td)=t{max⁡i∈I{fi(x)+∇fi(x)Td}∑l∈L|hl(x)+∇hl(x)Td|+r∑j∈Jmax⁡⁡{gj(x)+∇gj(x)Td,0}+r∑l∈L|hl(x)+∇hl(x)Td|}.w~(x;d) is convex as a function of d, and thus we have
(18)w~(x;td)-w(x)≤t{w~(x;d)-w(x)},∀t∈[0,1].
From the definition of w(x), w~(x;d) and (1), it is easy to obtain
(19)w~(x;d)-w(x)=max⁡i∈I{fi(x)+∇fi(x)Td}-max⁡i∈Ifi(x)-r∑j∈J‍max⁡⁡{gj(x),0}-r∑l∈L‍|hl(x)|.
On the other hand, from the first equation of (14) we can get
(20)dTHd+∑i∈I‍λi∇fi(x)Td+∑j∈J‍μj∇gj(x)Td+∑l∈L‍νl∇hl(x)Td=0.
Let If(x;d)={i;fi(x)+∇fi(x)Td=max⁡l∈I⁡{fl(x)+∇fl(x)Td},i∈{1,2,…,m}}. Since the third formula of (14) implies
(21)λi=0,∀i∈{1,2,…,m}∖If(x;d),
then
(22)dTHd+∑i∈If(x;d)‍λi∇fi(x)Td+∑j∈J‍μj∇gj(x)Td+∑l∈L‍νl∇hl(x)Td=0.
For i∈If(x;d), we get
(23)∇fi(x)Td=max⁡l∈I{fl(x)+∇fl(x)Td}-fi(x),∑i∈I‍λi=1⟹∑i∈If(x;d)‍λi=1.
Thus, (22) implies
(24)max⁡i∈I{fi(x)+∇fi(x)Td}=∑i∈If(x;d)‍λifi(x)-dTHd-∑j∈J‍μj∇gj(x)Td-∑l∈L‍νl∇hl(x)Td.
Substituting the above equality in (19), we can obtain
(25)w~(x;d)-w(x)≤-{dTHd+∑j∈J‍μj∇gj(x)Td+r∑j∈J‍max⁡⁡{gj(x);0}dTHd+∑j∈J‍μj∇gj(x)Td+∑l∈L‍νl∇hl(x)Td+r∑l∈L‍|hl(x)|}.
It follows from (14) that
(26)w~(x;td)-w(x)≤-t{dTHd-∑j∈J‍μjgj(x)+r∑j∈J‍max⁡{gj(x);0}dTHd-∑j∈J‍μjgj(x)-∑l∈L‍νlhl(x)+r∑l∈L‍|hl(x)|}.
Considering r satisfies r≥∥μ∥∞ and r≥∥ν∥∞, then we have
(27)w~(x;td)-w(x)≤-tdTHd<0,∀t∈[0,1].
Then, at xk, we have
(28)w(xk+tdk+t2d~k)-w(xk)=w~(xk;tdk)-w(xk)+o(t).
Since α∈(0,1/2), for t small enough, it holds that
(29)w(xk+tdk+t2d~k)-w(xk)≤α(w~(xk;tdk)-w(xk))≤-αtdkTHkdk.
That is, the line search condition (9) is satisfied.In the following of this section, we will show the global convergence of the algorithm. Since{dk,zk,λk,μk} is bounded under all the above-mentioned assumptions, we can assume without loss of generality that there exist an infinite index set K and a constant η* such that
(30)xk⟶x*,Hk⟶H*,ηk⟶η*,dk⟶d*,zk⟶z*,λk⟶λ*,μk⟶μ*,k∈K.Theorem 4.
The algorithm either stops at the KKT pointxk of the problem (1) in finite number of steps or generates an infinite sequence {xk} any accumulation point x* of which is a KKT point of the problem (1).Proof.
The first statement is obvious, the only stopping point being in Step  1. Thus, assume that the algorithm generates an infinite sequence{xk} and (30) holds. The cases η*=0 and η*>0 are considered separately.
Case A(η*=0). By Step 4, there exists an infinite index set K1⊆K, such that dk-1→0, k∈K1, while, by Step 3, it holds that
(31)lim⁡k∈K1∥xk-xk-1∥=lim⁡k∈K1∥tk-1dk-1+tk-12d~k-1∥≤lim⁡k∈K1(∥dk-1∥+∥d~k-1∥)=0.
So, the fact that xk-1→k∈K1x* implies that dk-1→k∈K10. So, from Lemma 2, it is clear that x* is a K-T point of (1).
Case B(η*>0). Obviously, it only needs to prove that dk→0, k∈K. Suppose by contradiction that d*≠0. Since
(32)fi(xk)+∇fi(xk)Tdk-F(xk)≤zk,i∈I,gj(xk)+∇gj(xk)Tdk≤ηkzk,j∈J,hl(xk)+∇hl(xk)Td=0,l∈L,
in view of k∈K, k→∞, we have
(33)fi(x*)+∇fi(x*)Td*-F(x*)≤z*,i∈I,gj(x*)+∇gj(x*)Td*≤η*z*,j∈J,hl(x*)+∇hl(x*)Td=0,l∈L.
So, the following corresponding QP subproblem (6) at x*(34)min⁡(d,z)∈Rn+1z+12dTH*d,s.t.fi(x*)+∇fi(x*)Td-F(x*)≤z,i∈I,gj(x*)+∇gj(x*)Td≤η*z,j∈J,hl(x*)+∇hl(x*)Td=0,l∈L,
has a nonempty feasible set. Moreover, it is not difficult to show that (z*,d*) is the unique solution of (34). So, it holds that
(35)z*<0,∇fi(x*)Td*≤z*<0,i∈I(x*),∇gj(x*)Td*≤η*z*<0,j∈J(x*).
For xk→x*, dk→d*, k∈K, it is clear, for k∈K, k large enough, that
(36)∇fi(xk)Tdk≤12∇fi(x*)Td*<0,i∈I(x*),∇gj(xk)Tdk≤12∇gj(x*)Td*<0,j∈J(x*).
From (36), by imitating the proof of [17, Proposition 3.2], we know that the stepsize tk obtained by the line search is bounded away from zero on K; that is,
(37)tk≥t*=inf⁡{tk,k∈K}>0.
In addition, from (9) and Lemma 2, it follows that {f(xk)} is monotonous decreasing. So, considering {xk}K→x* and the hypothesis (H 3.1), one holds that
(38)fi(xk)⟶fi(x*),k∈K,i∈I(x*).
Hence, from (9) and (36)–(38), we get
(39)0=lim⁡k∈K(fi(xk+1)-fi(xk))≤lim⁡k∈Kαtk∇fi(xk)Tdk≤12αt*∇fi(x*)Td*<0.
It is a contradiction. So, d*=0. Thereby, according to Lemma 2, x* is a KKT point of problem (1).


## 4. Rate of Convergence

In this section, we show the convergence rate of the algorithm. For this purpose, we add the following some stronger regularity assumptions.(H 4.1)
The functionsfi(x)(i∈I), gj(x)(j∈J), and hl(x)(l∈L) are twice continuously differentiable.(H 4.2)
The sequencexk generated by the algorithm possesses an accumulation point x*, and Hk→H*, k→∞.(H  4.3)
The second-order sufficiency conditions with strict complementary slackness are satisfied at the KKT pointx*; that is, it holds that λi>0, i∈I(x*), μj>0, j∈J(x*), and(40)dT∇xx2L(x*,λ*,μ*,ν*)d>0,0≠d∈S*,where
(41)
∇
x
x
2
L
(
x
*
,
λ
*
,
μ
*
,
ν
*
)
=
∑
i
∈
I
‍
λ
i
*
∇
2
f
i
(
x
*
)
+
∑
j
∈
J
‍
μ
j
*
∇
2
g
j
(
x
*
)
+
∑
l
∈
L
‍
ν
l
*
∇
2
h
l
(
x
*
)
=
∑
i
∈
I
(
x
*
)
‍
λ
i
*
∇
2
f
i
(
x
*
)
+
∑
j
∈
J
(
x
*
)
‍
μ
j
*
∇
2
g
j
(
x
*
)
+
∑
l
∈
L
‍
ν
l
*
∇
2
h
l
(
x
*
)
,
S
*
=
{
d
∈
R
n
∣
∇
f
i
(
x
*
)
T
d
=
∇
f
i
k
(
x
*
)
T
d
,
∀
i
∈
I
(
x
*
)
,
i
k
∈
I
(
x
*
)
,
∇
g
j
(
x
*
)
T
d
=
0
,
∀
j
∈
J
(
x
*
)
,
∇
h
l
(
x
*
)
T
d
=
0
,
∀
i
∈
I
(
x
*
)
}
.According to the all stated assumptions (H 4.1)–(H 4.3) and [21, Theorem 2], we have the following results.Lemma 5.
The KKT pointx* of problem (1) is isolated.Lemma 6.
The entire sequence{xk} converges to x*; that is, xk→x*, k→∞.Proof.
The result of this lemma is similar to the proof of [19, Lemma 4.1].Lemma 7.
Fork large enough, it holds that(1)
dk→0 and zk→0,(2)
λk→λ*, μk→μ*, and νk→ν*.Lemma 8.
Fork large enough, d~k obtained by Step 2 satisfies(1)
(42)∥d~k∥=O(∥dk∥2),(2)
(43)hl(xk+dk+d~k)=O(∥dk∥3),∀l∈L,gj(xk+dk+d~k)=O(∥dk∥3),∀j∈J(x).Proof.
(1) The result can be proven similarly to the proof of [5, Proposition 3.1] or [19, Lemma 4.3].
(2) We have(44)hl(xk+dk+d~k)=hl(xk+dk)+∇hl(xk+dk)Td~k+O(∥d~k∥2)=hl(xk+dk)+(∇hl(xk)+O∥dk∥)Td~k+O(∥d~k∥2)=hl(xk+dk)+∇hl(xk)Td~k+O(∥dk∥3)=O(∥dk∥3),l∈L.
Analogously, the other result is not difficult to be shown.To get the superlinearly convergent rate of the above proposed algorithm, the following additional assumption is necessary.(H 4.4)
The matrix sequenceHk satisfies that(45)∥Pk(Hk-∇xx2L(xk,λk,μk,νk))dk∥=o(∥dk∥),
where
(46)Pk=In-Ak(AkTAk)-1AkT,Ak=Ak(xk)=((∇fi(xk)-∇fik(xk)),∇gj(xk),∇hl(xk)),(i∈I(xk)∖{ik},j∈J(xk),l∈L(xk)).According to Lemmas6 and 8, it is easy to know
(47)∥Pk(Hk-∇xx2L(xk,λk,μk,νk))dk∥=o(∥dk∥)⟺∥Pk(Hk-∇xx2L(x*,λ*,μ*,ν*))dk∥=o(∥dk∥).Lemma 9.
Fork large enough, under the above-mentioned assumptions, tk≡1.Proof.
It is only necessary to prove that(48)w(xk+dk+d~k)≤w(xk)-αdkTHkdk.
From (6) and (14), we have
(49)fi(xk+dk)=fi(xk)+∇fi(xk)Tdk+O(∥dk∥2)=f(xk)+zk+O(∥dk∥2),i∈I(X*),fj(xk+dk)=fj(xk)+∇fj(xk)Tdk+O(∥dk∥2)=f(xk)+zk+O(∥dk∥2),j∈I(X*).
Hence,
(50)fi(xk+dk)=fj(xk+dk)+O(∥dk∥2),∀i,j∈I(x*).
Similarly, together with ∥d~k∥=O(∥dk∥2), it is easy to get
(51)fi(xk+dk+d~k)=fj(xk+dk+d~k)+O(∥dk∥3),∀i,j∈I(x*).
On the other hand, the facts that dk→0 and d~k→0 imply that I(xk+dk+d~k)⊆I(x*) (k large enough). Thus, for jk∈I(xk+dk+d~k)⊆I(x*), we have
(52)F(xk+dk+d~k)=max⁡l∈I{fl(xk+dk+d~k)}=fjk(xk+dk+d~k)=fj(xk+dk+d~k)+O(∥dk∥3),∀j∈I(x*).
By the definition of w(x) and Lemma 8, we have
(53)w(xk+dk+d~k)=max⁡l∈I{fl(xk+dk+d~k)}+O(∥dk∥3).
Multiplying both sides of (52) by λik and adding them, combining ∑l∈I(x*)λik=1 with (53), we get
(54)w(xk+dk+d~k)=max⁡i∈I(x*){fi(xk+dk+d~k)}+O(∥dk∥3).
In addition, for k large enough, we have
(55)L(xk+dk+d~k,λik,μjk,νlk)=∑i∈I‍λikfi(xk+dk+d~k)+∑j∈J‍μjkgj(xk+dk+d~k)+∑l∈L‍νlkhl(xk+dk+d~k)=∑i∈I(x*)‍λikfi(xk+dk+d~k)+∑j∈Jg(x*)‍μjkgj(xk+dk+d~k)+∑l∈L‍νlkhl(xk+dk+d~k)=∑i∈I(x*)‍λikfi(xk+dk+d~k)+O(∥dk∥3).
Combining the above equation with (54) we can obtain
(56)w(xk+dk+d~k)=L(xk+dk+d~k,λik,μjk,νlk)+O(∥dk∥3)=L(xk,λik,μjk,νlk)+∇xL(xk,λik,μjk,νlk)T(dk+d~k)+12(dk+d~k)T∇xx2L(xk,λik,μjk,νlk)×(dk+d~k)+o(∥dk∥2)=L(xk,λik,μjk,νlk)+∇xL(xk,λik,μjk,νlk)T(dk+d~k)+12(dk)T∇xx2L(xk,λik,μjk,νlk)(dk)+o(∥dk∥2).
From the KKT condition (14) implies ∇xL(xk,λik,μjk,νlk)=-Hkdk; then we get
(57)∇xL(xk,λik,μjk,νlk)T(dk+d~k)=-dkTHkdk+o(∥dk∥2),∑i∈I(x*)‍λik=1.
Thus,
(58)w(xk+dk+d~k)=L(xk,λik,μjk,νlk)-dkTHkdk+12(dk)T∇xx2L(xk,λik,μjk,νlk)×(dk)+o(∥dk∥2)=w(xk)-αdkTHkdk+12(dk)T×(∇xx2L(xk,λik,μjk,νlk)-Hk)(dk)-12dkTHkdk+αdkTHkdk+L(xk,λik,μjk,νlk)-w(xk)+o(∥dk∥2)≤w(xk)-αdkTHkdk-(12-α)dkTHkdk+o(∥dk∥2).
For k large enough, according to α∈(0,1/2), it holds that
(59)w(xk+dk+d~k)≤w(xk)-αdkTHkdk.From Lemma9 and the method of [29, Theorem 5.2], we can get the following.Theorem 10.
Under all stated assumptions, the algorithm is superlinearly convergent; that is, the sequence{xk} generated by the algorithm satisfies ∥xk+1-x*∥=o(∥xk-x*∥).


## 5. Numerical Experiments

In this section, we select several problems to show the efficiency of the algorithm in Section2. Some preliminary numerical experiments are tested on an Intel(R) Celeron(R) CPU 2.40 GHz computer. The code of the proposed algorithm is written by using MATLAB 7.0 and utilized the optimization toolbox to solve the quadratic programmings (6) and (7). The results show that the proposed algorithm is efficient.During the numerical experiments, are chosen at random some parameters as follows:α=0.25, η0=1, γ=0.5, and H0=I, the n×n unit matrix. Hk is updated by the BFGS formula [16]. In the implementation, the stopping criterion of Step 1 is changed to If ∥d0k∥≤10-6, STOP.This algorithm has been tested on some problems from [10, 11, 26]. The results are summarized in Table 1. The columns of this table have the following meanings:Number: the number of the test problem in [10, 11] or [26];n: the dimension of the problem;m: the number of objective functions;m1: the number of inequality constraints;m2: the number of equality constraints;NT: the number of iterations;IP: the initial point;FV: the final value of the objective function.Table 1
Numerical results of Algorithm1.
Number
n, m, m1, m2
NT
IP
FV
1 ([10, Problem 1])
2, 3, 0, 0
11
(
1
,
5
)
T
1.952224
2 ([10, Problem 4])
2, 3, 0, 0
10
(
3
,
1
)
T
0.616234
3 ([11, Problem 1])
2, 3, 2, 0
7
(
0
,
0
)
T
1.952224
4 ([11, Problem 2])
2, 6, 2, 0
12
(
1
,
3
)
T
0.616432
5 ([11, Problem 4])
2, 3, 2, 0
10
(
4
,
2
)
T
2.250000
6 ([11, Problem 5])
4, 4, 3, 0
32
(
0
,
1
,
1
,
0
)
T
−44.000000
7 ([11, Problem 6])
2, 3, 2, 0
4
(
0
,
1
)
T
2.000000
8 ([26, Problem 5])
2, 2, 0, 1
12
(
0
,
4
)
T
−5.875407
9 ([26, Problem 6])
3, 3, 1, 2
5
(
2
,
3
,
2
)
T
−3.934502
10 ([26, Problem 7])
10, 8, 0, 3
54
(
0
,
1
,
1
,
1
,
0
,
0
,
0
,
1
,
1
,
1
,
0
)
T
2.3339
e
+
003


## 6. Concluding Remarks

In this paper, we propose a simple feasible sequential quadratic programming algorithm for inequality constrained minimax problems. With the help of the technique of method of feasible direction, at each iteration, a main search direction is obtained by solving only one reduced quadratic programming subproblem. Then, a correction direction is yielded by solving another quadratic programming to avoid Maratos effect and guarantee the superlinear convergence under mild conditions. The preliminary numerical results also show that the proposed algorithm is effective.As further work, we can get the main search direction by other techniques, for example, sequential systems of linear equations technique. And we can also consider removing the strict complementarity.



---

*Source: 159754-2014-02-10.xml*