# A QP-Free Algorithm for Finite Minimax Problems

Authors: Daolan Han; Jinbao Jian; Qinfeng Zhang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

The nonlinear minimax problems without constraints are discussed. Due to the expensive computation for solving QP subproblems with inequality constraints of SQP algorithms, in this paper, a QP-free algorithm which is also called sequential systems of linear equations algorithm is presented. At each iteration, only two systems of linear equations with the same coefficient matrix need to be solved, and the dimension of each subproblem is not of full dimension. The proposed algorithm does not need any penalty parameters and barrier parameters, and it has small computation cost. In addition, the parameters in the proposed algorithm are few, and the stability of the algorithm is well. Convergence property is described and some numerical results are provided.


---

## Body

## 1. Introduction

We consider the nonlinear minimax problems of the form(1)min⁡x∈Rnmax⁡j∈Ifj(x),
where I={1,2,…,m} and fj(j∈I):Rn→R are continuously differentiable. Denote
(2)F(x)=max⁡{fj(x),j∈I},I(x)={j∈I∣fj(x)=F(x)},gj(x)=∇fj(x),j∈I.
By introducing an auxiliary variable s∈R, the problem (1) can be represented as the following standard nonlinear program (see [1]):
(3)min⁡x∈Rn,s∈R{s∣fj(x)-s≤0,j∈I}.
It is obvious that the KKT conditions of (3) are equivalent to
(4)∑j∈I‍λjgj(x)=0,∑j∈I‍λj=1;λj[fj(x)-F(x)]=0,λj≥0,j∈I.
So, a point x is called the stationary point (see [2]) of (1), if there exists a vector λ=(λj,j∈I) such that (4) holds, where λ is called the multiplier vector.


### 1.1. Related Work

Some algorithms have been proposed to solve the minimax problems (1) and can be grouped into three classes. The first one is the direct nonsmooth method. The problem (1) is viewed as an unconstrained nonsmooth optimization problem, which can be solved by some nonsmooth methods, such as bundle methods, gradient sampling methods, and cutting plane methods; see, for example, [3–5].Secondly, a variety of regularization approaches have been used to obtain smooth approximations to the problem (1); see, for example, [6–10]. The main advantage of the smoothing techniques is that the minimax problems are converted into smooth unconstrained optimization problems that can be solved by a standard unconstrained minimization solver. However, when the approximation accuracy is high, the smooth approximating problems become significantly ill-conditioned. Hence, the unconstrained optimization solver may experience numerical difficulty and slow convergence. Consequently, the simple use of smoothing techniques is complicated by the need of trading-off accuracy of approximation against problem ill-conditioning.The third one is based on solving the equivalent smooth nonlinear programming problem (3), such as the sequential quadratic programming (SQP) methods (see [11–16]), the trust-region strategies (see [17, 18]), sequential quadratically constrained quadratic programming (SQCQP) method (see [19]), gradient projection method (see [20]), and the interior point (IP) methods (see [21–23]). The advantage of this class method is that the nondifferentiable optimization problem (1) can be transformed into an equivalent smooth constrained nonlinear programming problem which can be solved by well-established methods.It is well known that the SQP method is one of the efficient methods for solving the smooth nonlinear program due to its fast convergence rate. Jian et al. [14], Hu et al. [15], and Zhu et al. [16] present some new SQP type algorithms for unconstrained minimax problems, respectively. For an iterative point xk, a new quadratic program (QP) subproblem is given by
(5)min⁡z+12dTHkds.t.hihfj(xk)+gj(xk)Td-F(xk)≤z,j∈Ik,
where Hk is a symmetric positive matrix and Ik is the ε active constraints set. The descent direction of F(x) can be obtained by solving (5), and the algorithms have global and superlinear convergence by introducing another correction direction.In these SQP algorithms or SQCQP method, QP subproblems or quadratically constrained quadratic programming (QCQP) subproblems with inequality constraints are also required to be solved which are computationally expensive compared with system of linear equations. In addition, the IP methods and the second class smoothing techniques do not need to solve QP and QCQP subproblems, but they need the penalty parameter or barrier parameter which is difficult to deal with and causes numerical difficulty when the penalty parameter or barrier parameter is too large. Therefore, it is necessary to construct a new algorithm without solving any QP and QCQP subproblems and using penalty parameters and barrier parameters.


### 1.2. Division of the Systems of Linear Equations

In this paper, we intend to replace the QP subproblem (5) used in [14–16] by two systems of linear equations with the same matrix so that the computation effort per iteration is much less and propose a QP-free algorithm, which does not need any penalty parameters and barrier parameters.For (5), in order to speed up the rate of convergence and construct the systems of linear equations conveniently, we select an index jk∈I(xk) and consider the following QP subproblem by introducing more parameters ηjk,j∈Ik∖{jk}, associated with the iterate xk:
(6)min⁡z+12dTHkds.t.hhhgjk(xk)Td≤z,hhhihhfj(xk)+gj(xk)Td-F(xk)≤ηjkz,hhhihhj∈I~k≜Ik∖{jk}.Since (6) is a convex program with linear constraints, its optimal solution is the KKT point; that is, (6) is equivalent to the following KKT system with the multiplier vector (μ,λj,j∈I~k):
(7)μ+∑j∈I~k‍ηjkλj=1,Hkd+μgjk(xk)+∑j∈I~k‍λjgj(xk)=0,0≤μ⊥(-gjk(xk)Td+z)≥0,0≤λj⊥(-fj(xk)+F(xk)-gj(xk)Td+ηjkz)≥0,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhij∈I~k.
Motivated by the KKT conditions above, we present the following system of linear equations (SLE):
(8)μ+∑j∈I~k‍ηjkλj=1,Hkd+μgjk(xk)+∑j∈I~k‍λjgj(xk)=0,gjk(xk)Td-z=0,gj(xk)Td-ηjkz=0,hhhhhhhhhhhhhhhhhhhhhhhhhhhj∈I~k.
The equation “gjk(xk)Td-z=0” comes from ηk=(ηjk,j∈I~k)→0(⇒μ→1). Obviously, the system above is equivalent to
(9)Hkd+∑j∈I~k‍(gj(xk)-ηjkgjk(xk))λj=-gjk(xk),(gj(xk)-ηjkgjk(xk))Td=0,j∈I~k.
Let (dk0,λI~kk0) be the solution of (9), and dk0 is taken as the first direction of our algorithm, which is not entirely suitable as the main search direction although it is a descent direction of F(x). In fact, the global convergence cannot be guaranteed, since the properties of the nonnegativity and complementarity of multiplier vector cannot be guaranteed at the point xk with dk0 and at the accumulation points of the infinite sequence {xk} generated by the proposed algorithm. Thus, we consider computing the second direction dk by another linear system:
(10)Hkd+∑j∈I~k‍(gj(xk)-ηjkgjk(xk))λj=-gjk(xk),(gj(xk)-ηjkgjk(xk))Td=vjk,j∈I~k,
where the right-hand parameters vjk,j∈I~k, are yielded by λI~kk0 and F(xk)-fj(xk), j∈I~k as follows:
(11)vjk={λjk0,ifλjk0<0;λjk0[F(xk)-fj(xk)],ifλjk0≥0.
Considering that the linear systems (10) and (9) have the same decomposed coefficient matrix, the computational cost is typically low. Lemma 8 shows that dk is still a descent direction of F(x), so dk can be taken as the main search direction to design the algorithm.The parametersηjk, j∈I~k, need to be devised deliberately to guarantee the nonsingularity of the coefficient matrix and global convergence. It is a difficult work throughout the whole research.


### 1.3. Properties of Our Algorithm

The proposed algorithm in this paper possesses the following properties.(i)
Only the constraints indexed by some subsetIk of I are considered which reduces the scale and computation cost of the subproblems to some extent.(ii)
At each iteration, only the solutions of two linear systems with the same coefficient matrix are required; that is, the new algorithm is completely QP-free.(iii)
It does not need any penalty parameters and barrier parameters. Therefore, the difficulty of choosing some suitable penalty parameters and barrier parameters is avoided.(iv)
It needs few parameters which are adjusted easily, and the algorithm is robust.(v)
It has weakly global convergence under some suitable assumptions.We conclude this section by giving some notation which is used throughout this paper. The symbol∥·∥ refers to the Euclidean norm. In addition, we denote by ∅ an empty set, the cardinality of any finite set J by |J|, and by det (M) the determinant of the matrix M. Furthermore, the directional derivation of F at the point x along with the direction d is denoted by F′(x;d). It is easy to know that
(12)F′(x;d)=max⁡{gj(x)Td,j∈I(x)}.


## 1.1. Related Work

Some algorithms have been proposed to solve the minimax problems (1) and can be grouped into three classes. The first one is the direct nonsmooth method. The problem (1) is viewed as an unconstrained nonsmooth optimization problem, which can be solved by some nonsmooth methods, such as bundle methods, gradient sampling methods, and cutting plane methods; see, for example, [3–5].Secondly, a variety of regularization approaches have been used to obtain smooth approximations to the problem (1); see, for example, [6–10]. The main advantage of the smoothing techniques is that the minimax problems are converted into smooth unconstrained optimization problems that can be solved by a standard unconstrained minimization solver. However, when the approximation accuracy is high, the smooth approximating problems become significantly ill-conditioned. Hence, the unconstrained optimization solver may experience numerical difficulty and slow convergence. Consequently, the simple use of smoothing techniques is complicated by the need of trading-off accuracy of approximation against problem ill-conditioning.The third one is based on solving the equivalent smooth nonlinear programming problem (3), such as the sequential quadratic programming (SQP) methods (see [11–16]), the trust-region strategies (see [17, 18]), sequential quadratically constrained quadratic programming (SQCQP) method (see [19]), gradient projection method (see [20]), and the interior point (IP) methods (see [21–23]). The advantage of this class method is that the nondifferentiable optimization problem (1) can be transformed into an equivalent smooth constrained nonlinear programming problem which can be solved by well-established methods.It is well known that the SQP method is one of the efficient methods for solving the smooth nonlinear program due to its fast convergence rate. Jian et al. [14], Hu et al. [15], and Zhu et al. [16] present some new SQP type algorithms for unconstrained minimax problems, respectively. For an iterative point xk, a new quadratic program (QP) subproblem is given by
(5)min⁡z+12dTHkds.t.hihfj(xk)+gj(xk)Td-F(xk)≤z,j∈Ik,
where Hk is a symmetric positive matrix and Ik is the ε active constraints set. The descent direction of F(x) can be obtained by solving (5), and the algorithms have global and superlinear convergence by introducing another correction direction.In these SQP algorithms or SQCQP method, QP subproblems or quadratically constrained quadratic programming (QCQP) subproblems with inequality constraints are also required to be solved which are computationally expensive compared with system of linear equations. In addition, the IP methods and the second class smoothing techniques do not need to solve QP and QCQP subproblems, but they need the penalty parameter or barrier parameter which is difficult to deal with and causes numerical difficulty when the penalty parameter or barrier parameter is too large. Therefore, it is necessary to construct a new algorithm without solving any QP and QCQP subproblems and using penalty parameters and barrier parameters.


## 1.2. Division of the Systems of Linear Equations

In this paper, we intend to replace the QP subproblem (5) used in [14–16] by two systems of linear equations with the same matrix so that the computation effort per iteration is much less and propose a QP-free algorithm, which does not need any penalty parameters and barrier parameters.For (5), in order to speed up the rate of convergence and construct the systems of linear equations conveniently, we select an index jk∈I(xk) and consider the following QP subproblem by introducing more parameters ηjk,j∈Ik∖{jk}, associated with the iterate xk:
(6)min⁡z+12dTHkds.t.hhhgjk(xk)Td≤z,hhhihhfj(xk)+gj(xk)Td-F(xk)≤ηjkz,hhhihhj∈I~k≜Ik∖{jk}.Since (6) is a convex program with linear constraints, its optimal solution is the KKT point; that is, (6) is equivalent to the following KKT system with the multiplier vector (μ,λj,j∈I~k):
(7)μ+∑j∈I~k‍ηjkλj=1,Hkd+μgjk(xk)+∑j∈I~k‍λjgj(xk)=0,0≤μ⊥(-gjk(xk)Td+z)≥0,0≤λj⊥(-fj(xk)+F(xk)-gj(xk)Td+ηjkz)≥0,hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhij∈I~k.
Motivated by the KKT conditions above, we present the following system of linear equations (SLE):
(8)μ+∑j∈I~k‍ηjkλj=1,Hkd+μgjk(xk)+∑j∈I~k‍λjgj(xk)=0,gjk(xk)Td-z=0,gj(xk)Td-ηjkz=0,hhhhhhhhhhhhhhhhhhhhhhhhhhhj∈I~k.
The equation “gjk(xk)Td-z=0” comes from ηk=(ηjk,j∈I~k)→0(⇒μ→1). Obviously, the system above is equivalent to
(9)Hkd+∑j∈I~k‍(gj(xk)-ηjkgjk(xk))λj=-gjk(xk),(gj(xk)-ηjkgjk(xk))Td=0,j∈I~k.
Let (dk0,λI~kk0) be the solution of (9), and dk0 is taken as the first direction of our algorithm, which is not entirely suitable as the main search direction although it is a descent direction of F(x). In fact, the global convergence cannot be guaranteed, since the properties of the nonnegativity and complementarity of multiplier vector cannot be guaranteed at the point xk with dk0 and at the accumulation points of the infinite sequence {xk} generated by the proposed algorithm. Thus, we consider computing the second direction dk by another linear system:
(10)Hkd+∑j∈I~k‍(gj(xk)-ηjkgjk(xk))λj=-gjk(xk),(gj(xk)-ηjkgjk(xk))Td=vjk,j∈I~k,
where the right-hand parameters vjk,j∈I~k, are yielded by λI~kk0 and F(xk)-fj(xk), j∈I~k as follows:
(11)vjk={λjk0,ifλjk0<0;λjk0[F(xk)-fj(xk)],ifλjk0≥0.
Considering that the linear systems (10) and (9) have the same decomposed coefficient matrix, the computational cost is typically low. Lemma 8 shows that dk is still a descent direction of F(x), so dk can be taken as the main search direction to design the algorithm.The parametersηjk, j∈I~k, need to be devised deliberately to guarantee the nonsingularity of the coefficient matrix and global convergence. It is a difficult work throughout the whole research.


## 1.3. Properties of Our Algorithm

The proposed algorithm in this paper possesses the following properties.(i)
Only the constraints indexed by some subsetIk of I are considered which reduces the scale and computation cost of the subproblems to some extent.(ii)
At each iteration, only the solutions of two linear systems with the same coefficient matrix are required; that is, the new algorithm is completely QP-free.(iii)
It does not need any penalty parameters and barrier parameters. Therefore, the difficulty of choosing some suitable penalty parameters and barrier parameters is avoided.(iv)
It needs few parameters which are adjusted easily, and the algorithm is robust.(v)
It has weakly global convergence under some suitable assumptions.We conclude this section by giving some notation which is used throughout this paper. The symbol∥·∥ refers to the Euclidean norm. In addition, we denote by ∅ an empty set, the cardinality of any finite set J by |J|, and by det (M) the determinant of the matrix M. Furthermore, the directional derivation of F at the point x along with the direction d is denoted by F′(x;d). It is easy to know that
(12)F′(x;d)=max⁡{gj(x)Td,j∈I(x)}.


## 2. Description of Algorithm

The new algorithm is based on the following assumption.(A1)
The vectors{gj(x),j∈I(x)∖{l}} are linearly independent for any l∈I(x) and each point x∈Rn.Lemma 1.
Suppose that the vectors{gj(x),j∈J} are linearly independent for x∈Rn and index set J⊆I. Then, for any given l∈I, there exists a constant ρJ(x)>0 such that {gj(x)-ζ∥gj(x)∥gl(x),j∈J} are linearly independent for each ζ∈[0,ρJ(x)].For a pointx∈Rn, an index l∈I, and a given index set J such that {gj(x),j∈J} are linearly independent, we introduce the following technique similar to [24] to generate the parameter ρJ(x) in Lemma 1. Define
(13)fJ(x)=(fj(x),j∈J),gJ(x)=(gj(x),j∈J),nj(x)=gj(x)∥gj(x)∥,NJ(x)=(nj(x),j∈J),(14)ρJ(x)=det⁡[NJ(x)TNJ(x)]e|J|∥gl(x)∥+1,(15)aj(x,ϵ)=nj(x)-ϵρJ(x)gl(x),
where e is Napierian base and the parameter ϵ≥0.Lemma 2 (see [24]).
Suppose that the vectors{gj(x),j∈J} are linearly independent. Then the vectors {aj(x,ϵ),j∈J} are also linearly independent for each ϵ∈[0,1].Letxk be a given iteration point. We denote jk=min⁡{j∣j∈I(xk)} and use the following pivoting operation to generate the index set I~k such that Rk≜gI~k(xk) has full column rank, so vectors {gj(xk),j∈I~k} are linearly independent.Pivoting Operation (POP)Step (i). Select an initial parameter ε=εk-1.Step (ii). Generate ε active constraint subset I(xk,ε) and matrix Gk by
(16)I(xk,ε)={j∈I∣-ε≤fj(xk)-F(xk)≤0},Gk=(gj(xk),j∈I(xk,ε)∖{jk}).Step (iii). If I(xk,ε)∖{jk}=∅ or det(GkTGk)≥ε, then set I~k:=I(xk,ε)∖{jk}, εk=ε, and stop; otherwise, set ε≔ε/2 and repeat Step (ii).For simplicity, denote(17)ρk≜ρI~k(xk),AJ(xk,ζ)=(gj(xk)-ζ∥gj(xk)∥gjk(xk),j∈J),hhhhhhhhhhhhhhhhhhhhhhiζ∈[0,ρk].
From the POP and Lemma 2 above, we know that (aj(xk,ϵ),j∈I~k) = (nj(xk)-ϵρI~k(xk)gjk(xk),j∈I~k) has full column rank for each ϵ∈[0,1]. Furthermore, it is easy to get the following lemma.Lemma 3.
Suppose that (A1) holds. Then the matrixAJ(xk,ζ) has full column rank for each J⊆I~k and ζ∈[0,ρk].To describe some beneficial properties of the POP above, which is helpful for discussing the convergence of our algorithm, we have the following results.Lemma 4.
Suppose that (A1) holds, and letxk∈Rn.(i)
The parameterεk can be obtained in a finite number of steps in the POP.(ii)
If a sequence{xk} is bounded, then there exist two constants ε-,ε~>0 such that
(18)inf⁡{εk}=ε-,det⁡(RkTRk)≥ε-,∀k,(19)det⁡[AJk(xk,ζ)TAJk(xk,ζ)]≥ε~,∀k,∀ζ∈[0,ρk],hhhhhhhhhhhh∀Jk⊆I~k.Proof.
Based on the assumption (A1), it is easy to get that (i) and (18) hold, so it is omitted here.
Now, we will prove that (19) holds. In view of I~k and Jk being the subsets of the fixed and finite set I and the boundedness of {xk}, we assume by contradiction without loss of generality that there exist an infinite index set K and ζk∈[0,ρk] such that
(20)I~k≡I~,Jk≡J⊆I~,jk≡j0,xk⟶x*,det⁡[AJ(xk,ζk)TAJ(xk,ζk)]⟶0,k∈K.
According to (14) and (A1), we can get ρk→k∈Kρ*=ρI~(x*). So, {ζk,k∈K} is bounded from ζk∈[0,ρk]; we may assume that there exists an infinite index set K′⊆K such that ζk→k∈K′ζ*∈[0,ρ*]. On the other hand, from (18) one knows that vectors {gj(x*),j∈I~} are linearly independent. Therefore, by Lemma 2, we know that {aj(x*,ϵ),j∈I~} are also linearly independent for each ϵ∈[0,1], which implies that vectors
(21){∥gj(x*)∥aj(x*,ϵ)ii=gj(x*)-ϵρ*∥gj(x*)∥gj0(x*),j∈I~}
are linearly independent for each ϵ∈[0,1]. So, {gj(x*)-ζ∥gj(x*)∥gj0(x*),j∈J⊆I~} are linearly independent for each ζ∈[0,ρ*]. Denote that A*=(gj(x*)-ζ*∥gj(x*)∥gj0(x*),j∈J),A*, has full column rank since ζ*∈[0,ρ*]. However,
(22)0=lim⁡k∈K′det⁡[AJ(xk,ζk)TAJ(xk,ζk)]=det⁡(A*TA*),
which contradicts the fact that A* has full column rank. So (19) holds.A detailed description of the algorithm for solving (1) is given below.Algorithm A.
Parameters:α∈(0,1/2), β∈(0,1), ε-1>0.
Step  0 (initialization). Consider x0∈Rn, an initial symmetric positive definite matrix H0. Set k∶=0.
Step  1 (generating
ε
active set). Set parameter ε=εk-1, generate the set I~k by the POP, and let εk be the corresponding termination parameter.
Step  2. Compute ρk=ρI~k(xk) according to (14), and adjust the parameter ζk by
(23)ζk={ρ0,ifk=0;min⁡{ρk,∥dk-1,0∥+∥vk-1∥,ζk-1},ifk>0.
Step  3. Compute the unique solution (dk0,λI~kk0) of the following linear system:
(24)(LS1)M(xk,Hk,ζk)(dλ)=(-gjk(xk)0),
with
(25)M(xk,Hk,ζk)=(HkAkAkT0),Ak≜AI~k(xk,ζk).
Step  4. Compute the unique solution (dk,λI~kk) of the following linear system:
(26)(LS2)M(xk,Hk,ζk)(dλ)=(-gjk(xk)vk),
where vk=(vjk,j∈I~k) is yielded by
(27)vjk={λjk0,ifλjk0<0;λjk0[F(xk)-fj(xk)],ifλjk0≥0.
If dk=0 and
(28)λjkk≜1-ζk∑j∈I~k‍λjk∥gj(xk)∥≥0,
then xk is a stationary point of (1), and stop.
Step  5 (doing line search). Compute the step size tk, the first number t of the sequence {1,β,β2,…} satisfying
(29)F(xk+tdk)≤F(xk)+αtF′(xk;dk).
Step  6. Set xk+1=xk+tkdk, and compute a new symmetric positive definite matrix Hk+1. Set k:=k+1, and go back to Step 1.Remark 5.
If the casedk=0, λjkk<0 arises; the algorithm will stop at iterate xk which is not a stationary point of (1). To avoid this pitfall, we will reset ζk∶=(1/2)ζk and solve (LS1) and (LS2) again.For convenience of analysis in the rest of this paper, we give the equivalent forms of (LS1)-(LS2):(30)(LS1)⟺{Hkdk0+∑j∈I~k‍λjk0(gj(xk)-ζk∥gj(xk)∥gjk(xk))=-gjk(xk),(gj(xk)-ζk∥gj(xk)∥gjk(xk))Tdk0=0,hhhhhhhhhhhhhhhhhhhhhhhhhhhj∈I~k;(31)(LS2)⟺{Hkdk+∑j∈I~k‍λjk(gj(xk)-ζk∥gj(xk)∥gjk(xk))=-gjk(xk),(gj(xk)-ζk∥gj(xk)∥gjk(xk))Tdk=vjk,hhhhhhhhhhhhhhhhhhhhhhhhhhhj∈I~k.
So, the parameters ηjk,j∈I~k, in (9)-(10) are selected as ηjk=ζk∥gj(xk)∥. From Algorithm A and (A1) as well as Lemma 3, we can get the following lemmas immediately.Lemma 6.
The matrixM(xk,Hk,ζ) is nonsingular for each ζ∈[0,ρk]. Therefore, the coefficient matrix M(xk,Hk,ζk) in systems (LS1)-(LS2) is nonsingular.Taking into account the inverse matrix ofMk≜M(xk,Hk,ζk) that can be expressed as Mk-1=(CkBkBkT-Dk-1), with
(32)Dk=AkTHk-1Ak,Bk=Hk-1AkDk-1,Ck=Hk-1-Hk-1AkBkT,
from (LS1)-(LS2) and (32), we have the following relations:
(33)dk0=-Ckgjk(xk),λI~kk0=-BkTgjk(xk);(34)dk=dk0+Bkvk,λI~kk=λI~kk0-Dk-1vk.Lemma 7.
If Algorithm A stops at an iteratexk with dk=0 and λjkk≥0, then xk is a stationary point of the problem (1).Proof.
If Algorithm A stops at an iteratexk with dk=0 and λjkk≥0, it follows from (31) that
(35)(1-ζk∑j∈I~k‍λjk∥gj(xk)∥)gjk(xk)+∑j∈I~k‍λjkgj(xk)=0,vk=0.
By the definition of vk, we have λI~kk0≥0, λjk0[fj(xk)-F(xk)]=0, j∈I~k, and hence, by (34),
(36)λI~kk=λI~kk0≥0,λjk[fj(xk)-F(xk)]=0,j∈I~k.
Since Rk has full column rank, from (35) it is easy to get λjkk=1-ζk∑j∈I~kλjk∥gj(xk)∥≠0 and λjkk>0. If one denotes uIkk=(ujk=λjk/∑j∈Ikλjk,j∈Ik), uk=(uIkk,0I∖Ik), then from (35)-(36) we can conclude that xk is a stationary point of (1) with the multiplier vector uk.Lemma 8.
Ifdk≠0, then(i)
gjk(xk)Tdk=-(dk0)THkdk0-∑λjk0<0(λjk0)2+∑λjk0≥0(λjk0)2[fj(xk)-F(xk)]<0;(ii)
gj(xk)Tdk≤ζk∥gj(xk)∥gjk(xk)Tdk<0,j∈I(xk)∖{jk};(iii)
dk is a descent direction of F(x) at the iterate xk, so the proposed algorithm is well defined.Proof.
(i) From (34), (30), (33), and (27), one gets
(37)gjk(xk)Tdk=gjk(xk)T(dk0+Bkvk)=-(dk0)THkdk0-(λI~kk0)TAkTdk0-(λI~kk0)Tvk=-(dk0)THkdk0-(λI~kk0)Tvk=-(dk0)THkdk0-∑λjk0<0‍(λjk0)2+∑λjk0≥0‍(λjk0)2[fj(xk)-F(xk)].
Furthermore, since dk≠0, from (34), we can get (dk0,vk)≠(0,0). This implies that (i) holds.
(ii) Ifj∈I(xk)∖{jk}, from I(xk)∖{jk}⊆I~k and (27), we have vjk≤0. From Remark 5, we can assume without loss of generality that dk-1≠0. Furthermore, it follows from (34) and (23) that ζk>0. Therefore, from the second formula of (31) and assumption (A1), it is easy to get
(38)gj(xk)Tdk=ζk∥gj(xk)∥gjk(xk)Tdk+vjk≤ζk∥gj(xk)∥gjk(xk)Tdk<0,hhhhhhhhhhj∈I(xk)∖{jk}.
(iii) From (12) and the above results (i)-(ii), one knows that F′(xk;dk)<0, which implies that dk is a descent direction of F(x) at xk. So the line search can be performed and the proposed algorithm is well defined.


## 3. Global Convergence

In this part, under mild assumptions, we show that Algorithm A is weak globally convergent; that is, there exists at least one accumulation point of the iterates{xk} yielded by Algorithm A such that it is a stationary point of (1). To this end, in addition to (A1), the following two assumptions are necessary.(A2)
The sequence{xk} generated by Algorithm A is bounded.(A3)
There exist two constantsa,b>0 such that
(39)a∥d∥2≤dTHkd≤b∥d∥2,∀d∈Rn,∀k.The following lemma establishes the boundedness of the associated sequences generated by the algorithm, and its proof is similar to Lemma  3.1 in [25], so it is omitted here.Lemma 9.
Suppose that (A1)–(A3) hold. Then, the sequences{ρk}, {ζk}, {Mk-1}, {dk0}, {λI~kk0}, {dk}, {λI~kk}, {Dk-1}, and {Bk} are all bounded.Lemma 10.
Suppose that (A1)–(A3) hold. If an infinite index setK satisfies
(40)xk⟶x*,jk≡j′,gj′(xk)Tdk⟶0,k∈K,
then x* is a stationary point of (1).Proof.
From Lemma9, we know there exists an infinite subset K′⊆K such that
(41)I~k≡I~,dk0⟶d*0,λI~k0⟶λI~*0,k∈K′.
Again, lim⁡k→∞⁡ζk=ζ* follows since {ζk} is monotone and bounded. In view of Lemma 8 (i) and (A3), we have
(42)0⟵gj′(xk)Tdk≤-a∥dk0∥2-∑λjk0<0‍(λjk0)2+∑λjk0≥0‍(λjk0)2[fj(xk)-F(xk)]<0.
This along with (40)-(41) shows that
(43)dk0⟶0,λI~*0≥0,k∈K′,(λj*0)2[fj(x*)-F(x*)]=0,j∈I~.
So, passing to the limit for k∈K′, k→∞, in (30), one gets
(44)(1-ζ*∑j∈I~‍λj*0∥gj(x*)∥)gj′(x*)+∑j∈I~‍λj*0gj(x*)=0;λj*0≥0,λj*0[fj(x*)-F(x*)]=0,i∈I~.
Furthermore, it follows from (23) and (27) that ζk+1→0, k∈K′. So, ζ*=0 and λj′*0≜1-ζ*∑j∈I~λj*0∥gj(x*)∥=1. If one denotes I′=I~∪{j′}, uI′*=(uj*=λj*0/∑j∈I′λj*0,j∈I′), and u*=(uI′*,0I∖I′), then (44) implies that x* is a stationary point with the multiplier vector u*.Theorem 11.
Suppose that (A1)–(A3) hold. Then Algorithm A either stops at a stationary point of (1) in a finite number of iterations or generates an infinite sequence {xk}, of which at least one accumulation point is a stationary point of (1). In such sense, Algorithm A is said to possess weakly global convergence.Proof.
The casesζ*=0 and ζ*>0 are discussed, respectively.
Case A. If ζ*=0, from (14), Lemma 4 (ii), and (A2), we know that there exists a constant ρ_>0 such that ρk≥ρ_ holds for all k large enough. Therefore, in view of (A2) and (23), there exists an infinite index K such that
(45)xk⟶x*,ζk=∥dk-1,0∥+∥vk-1∥⟶0,k∈K;
that is, dk-1,0→0, vk-1→0, k∈K. So, from (34) and the boundedness of {Bk}, we have lim⁡k∈K⁡dk-1=lim⁡k∈K(dk-1,0+Bk-1vk-1)=0. It further follows that ∥xk-xk-1∥=tk-1∥dk-1∥→0, k∈K. Thus, lim⁡k∈Kxk-1=x*. So, according to Lemma 10 and lim⁡k∈Kdk-1=0, it is easy to conclude that x* is a stationary point of (1).
Case B. If ζ*>0, then we have ζk≥(1/2)ζ* for all k∈K large enough. Suppose that x* is any given accumulation point of {xk}. Since I is a fixed and finite set, from Lemma 9, there always exists an infinite index set K such that
(46)I(xk)≡I*,I~k≡I~,jk≡j′,k∈K,(xk,dk0,dk,λI~k0,λI~k,ζk)⟶(x*,d*0,d*,λI~*0,λI~*,ζ*),hhhhhhhhhhhhhhhhhhk∈K.
Suppose by contradiction that x* is not a stationary point. We first show by contradiction that the given infinite index set K satisfies gj′(xk)Tdk→0, k∈K. Otherwise, since gj′(xk)Tdk<0 and gj′(xk)Tdk→gj′(x*)Td*, k∈K, there exists a constant c>0 such that
(47)gj′(xk)Tdk≤-c,k∈Klarge enough.
Consequently, we prove that the line search inequality (29) holds for all k∈K large enough and t>0 small enough. We denote
(48)ωk(t)=F(xk+tdk)-F(xk)-αtF′(xk,dk).
It follows from the boundedness of {dk} and Taylor expansion that
(49)ωk(t)=max⁡{fj(xk+tdk)-F(xk)-αtF′(xk,dk),j∈I}=max⁡{fj(xk)-F(xk)+tgj(xk)Tdkhhhhhhh-αtF′(xk,dk)+o(t),j∈Igj(xk)T}.
Denote akj(t)=fj(xk)-F(xk)+tgj(xk)Tdk-αtF′(xk,dk)+o(t). For j∈I*∖{j′}⊆I~, according to (18) in Lemma 4 (ii), it is easy to know that there exists a constant σ>0 such that ∥gj(xk)∥≥σ for all k∈K. From Lemma 8 (ii), one has for k∈K large enough and t>0 small enough
(50)akj(t)=tgj(xk)Tdk-αtF′(xk,dk)+o(t)≤(1-α)tgj(xk)Tdk+o(t)≤(1-α)tζk∥gj(xk)∥gj′(xk)Tdk+o(t)≤-12(1-α)ζ*σct+o(t)≤0.
For j=j′, one has for k∈K large enough and t>0 small enough akj(t)≤(1-α)tgj′(xk)Tdk+o(t)≤-(1-α)ct+o(t)≤0.
Forj∈I∖I*, from the POP and Lemma 4 (ii), we can obtain fj(xk)-F(xk)<-εk≤-ε-. So, akj(t)≤-ε-+O(t)≤0 holds for k∈K large enough and t>0 small enough.
Summarizing the analysis above, we know that there exists a constantt*>0 such that the step size tk≥t*,∀k∈K. Furthermore, for ∀j∈I*, gj(xk)Tdk≤-min⁡{(1/2)ζ*σ,1}c. So, F′(xk,dk)≤-min⁡{(1/2)ζ*σ,1}c. Combining (29), we have
(51)F(xk+1)-F(xk)≤αtkF′(xk,dk)≤-αt*min⁡{12ζ*σ,1}c,k∈K.
Since the whole sequence {F(xk)} is decreasing and lim⁡k∈KF(xk)=F(x*), we know that lim⁡k→∞⁡F(xk)=F(x*). So, passing to the limit for k∈K and k→∞ in inequality (51), one has -αt*min⁡{(1/2)ζ*σ,1}c≥0, which contradicts the fact that α>0, t*>0, ζ*>0, and c>0. The contradiction shows that (40) holds. Furthermore, one can conclude from Lemma 10 that x* is a stationary point of (1), which contradicts the assumption. The whole proof is completed.


## 4. Numerical Results

In this section, some preliminary numerical tests on 5 typical problems from [26] are reported, and the computation results show that Algorithm A is efficient. All the numerical experiments were implemented on MATLAB 7.0, under Windows XP and 2.2 GHz CPU. The BFGS formula with Powell’s modification [27] is adopted in the algorithm, and H0 is the identity matrix. The parameters were selected as α=0.2, β=0.6, and ε-1=1.2. In addition, execution is terminated if one of the following termination criteria is satisfied:(a)
∥dk∥≤10-5,(b)
∥xk+1-xk∥≤10-5.The computational results are reported in Table1, and the columns of Table 1 have the following meanings: IP: the initial point; n: the number of variables; m: the number of functions fj(x); ALG: the type of algorithm; NI: the number of iterations. “Algo A” represents Algorithm A in this paper, “J2006-1” and “J2006-2” represent the algorithms in [13], and “Hu2009” represents the algorithm in [15].Table 1
Numerical results of Algorithm A.
P
I
P
n
m
ALG
NI
Approximate solutionx*
F
(
x
*
)
∥
d
k
∥
1
(
1
,
-
0.01
)
T
2
3
Algo A
7
(
1.1390,0.8995
)
T
1.952
1.715
e
-
6
J2006-1
11
(1.1390,0.8995)T
1.952
3.462
e
-
7
J2006-2
19
(
1.1390,0.8995
)
T
1.952
2.457
e
-
6
Hu2009
8
—
1.952
4.248
e
-
6
2
(
0.01,0.01
)
T
2
3
Algo A
7
(
1.0000,0.9999
)
T
2.000
3.543
e
-
5
J2006-1
7
(
1.0000,1.0000
)
T
2.000
6.177
e
-
10
J2006-2
17
(
1.00000,1.00000
)
T
2.000
4.775
e
-
9
Hu2009
7
—
2.000
1.987
e
-
14
3
(
0.2
,
-
1,2.3
,
-
0.01
)
T
4
4
Algo A
12
(
0.0,1.0,2.0
,
-
1.0
)
T
-
44.00
2.206
e
-
5
J2006-1
38
(
0.0,1.0,2.0
,
-
1.0
)
T
-
44.00
3.087
e
-
6
J2006-2
74
(
0.0,1.0,2.0
,
-
1.0
)
T
-
44.00
7.733
e
-
6
Hu2009
11
—
-
44.00
8.294
e
-
6
4
(
3,1
)
T
2
3
Algo A
11
(
-
0.45330
,
0.90659
)
T
0.616
9.617
e
-
6
J2006-1
10
(
-
0.45329
,
0.90659
)
T
0.616
6.419
e
-
6
J2006-2
21
(
-
0.45329
,
0.90659
)
T
0.616
2.641
e
-
6
Hu2009
12
—
0.616
8.797
e
-
6
5
(
1,1
,
1
)
T   (1.01,0.9,1)T
3
6
Algo A
13
(
0.3282,0.0,0.1313
)
T
3.599
7.343
e
-
6
J2006-1
20
(
0.3282,0.0,0.1313
)
T
3.599
7.227
e
-
7
J2006-2
34
(
0.3282,0.0,0.1313
)
T
3.599
3.382
e
-
6
Hu2009
14
—
3.599
1.832
e
-
6From Table1, we can see that our algorithm can find the solutions of the test problems with a small number of iterations, and the computational results illustrate that our algorithm executes well for those problems. The numerical results are comparative with the algorithms in [13, 15]. Furthermore, we only need to solve two systems of linear equations with the same coefficient matrix per iteration. Considering that these linear systems have the same decomposed coefficient matrix, the computational cost per iteration of Algorithm A is typically low. This shows the potential advantage of our algorithm when applied to solving problems with large numbers of constraints. In addition, the parameters in the proposed algorithm are few, and the stability of the algorithm is very well.


## 5. Concluding Remarks

In this paper, a QP-free algorithm without solving any QP and QCQP subproblems is presented for unconstrained nonlinear finite minimax problems. At each iteration, only two systems of linear equations with the same coefficient matrix need to be solved. The proposed algorithm does not need any penalty parameters and barrier parameters which are difficult to deal with. Furthermore, under some mild assumptions, the global convergence is attained. As further work of this method, we think that there are still some problems worthy of discussing. For example, the assumption (A1) is different from the linearly independent assumption in common use, and any of them cannot derive the other. The discussion that the assumption (A1) is a constraint qualification needs further consideration. In addition, one should also take into account improving it to have superlinear convergence and generalizing it to solve minimax problems with inequality constraints.



---

*Source: 436415-2014-06-24.xml*