Home | About | Journals | Submit | Contact Us | Français |

**|**Springer Open Choice**|**PMC5329097

Formats

Article sections

- Abstract
- Introduction
- Description of algorithm
- Convergence analysis
- Numerical experiments
- Conclusions
- Results and discussion
- References

Authors

Related links

Journal of Inequalities and Applications

J Inequal Appl. 2017; 2017(1): 51.

Published online 2017 February 27. doi: 10.1186/s13660-017-1321-3

PMCID: PMC5329097

Guodong Ma, Email: moc.361@6002dgm.

Received 2016 December 20; Accepted 2017 February 12.

Copyright © The Author(s) 2017

Combining the techniques of the working set identification and generalized gradient projection, we present a new generalized gradient projection algorithm for minimax optimization problems with inequality constraints. In this paper, we propose a new optimal identification function, from which we provide a new working set. At each iteration, the improved search direction is generated by only one generalized gradient projection explicit formula, which is simple and could reduce the computational cost. Under some mild assumptions, the algorithm possesses the global and strong convergence. Finally, the numerical results show that the proposed algorithm is promising.

Minimax problem is an important class of nonsmooth optimization, since it has a broad application background. Numerous models in optimal control [1, 2], engineering problem [3], portfolio optimization [4] and many other situations [5] can be formulated as the following minimax optimization problems with inequality constraints:

min *F*(*x*), s.t. *f*_{j}(*x*) ≤ 0, *j* ∈ *J*,

1

where *F*(*x*) = max {*f*_{j}(*x*), *j* ∈ *I*} with *I* = {1, 2, …, *m*}, *j* ∈ *J* = {*l* + 1, *l* + 2, …, *l* + *m*}, *f*_{j}(*x*):*R*^{n} → *R* (*j* ∈ *I* ∪ *J*) are continuously differentiable functions. The objective function *F*(*x*) is not necessarily differentiable, even when all *f*_{j}(*x*), *j* ∈ {*I* ∪ *J*} are differentiable. Obviously, the non-differentiablity of the objective function *F*(*x*) is a main challenge for solving minimax problem, as the classical smooth methods cannot be applied directly. Over the past few decades, the minimax problem has attracted more and more researchers’ attention and many algorithms have been developed, which can be grouped into three classes in general.

The first class of algorithms views the problem (1) as the constrained nonsmooth optimization problem, which can be solved directly by several classical nonsmooth methods, such as subgradient methods, bundle methods, and cutting plane methods, Refs. [6–9]. The algorithms in [6–8] have a shortcoming that it is difficult to improve the numerical results. However, we have observed in [9] that a feasible descent bundle method for solving inequality constrained minimax problems is proposed, by using the subgradients of functions, the idea of bundle method and the technique of partial cutting planes model, to generate the new cutting plane and aggregate the subgradients in the bundle, so the difficulty of numerical calculation and storage is overcome.

The second one is the entropy function method [10–13]. First, it transforms the objective function minimax problem into a smooth function with parameters. Then the objective function is approximated by a parametric and smooth function. For example, the parametric and smooth function with the parameter *p*

$${F}_{p}(x)=\frac{1}{p}ln\{\sum _{i=1}^{l}exp[p{f}_{i}(x)]\}.$$

Since $0\le {F}_{p}(x)-F(x)\le \frac{1}{p}lnl$, so *p* → ∞, *F*_{p}(*x*) → *F*(*x*).

Due to the particular structure of the objective function, the third approach is that the problem (1) can be transformed into the following equivalent smooth constrained nonlinear programming by introducing an artificial variable *z*:

$$\underset{(x,z)\in {R}^{n+1}}{min}z,\phantom{\rule{1em}{0ex}}\text{s.t.}{f}_{i}(x)-z\le 0,\phantom{\rule{1em}{0ex}}i\in I;\phantom{\rule{2em}{0ex}}{f}_{j}(x)\le 0,\phantom{\rule{1em}{0ex}}j\in J.$$

Then, we can solve the above inequality constrained optimization by some well-established methods, such as the sequential quadratic programming type (SQP) methods [14–17], the sequential quadratically constrained quadratic programming type (SQCQP) methods [18, 19], the trust-region strategy [20, 21] and the interior-point method [22]. In [14], a SQP algorithm is proposed that incorporates the particular case of minimax problems, the global and local convergence is ensured. In order to improve the convergence properties and numerical performance, Jian and Zhu *et al*. developed improved SQP methods established in [15, 16] for solving unconstrained or constrained minimax problems, by means of solving one quadratic programming an improved direction is yielded and a second-order correction direction can also be at hand via one system of linear equations. Under mild conditions, we can ensure global and superlinear convergence. Jian *et al*. [17] developed the norm-Relaxed SQP method based on active set identification and new line search for constrained minimax problems, which the master direction and high-order correction direction are computed by solving a new type of norm-relaxed quadratic programming subproblem and a system of linear equations, respectively. Moreover, the step size is yielded by a new line search which combines the method of strongly sub-feasible direction with the penalty method.

Recently, several researchers have worked on the SQCQP, to solve unconstrained or constrained minimax problems. The authors provided the SQCQP method [18] and showed that their algorithm is faster than the SQP algorithm that is a well-known algorithm used for solving constrained minimization problems, which solved a subproblem that involves convex quadratic inequality constraints and a convex quadratic objective function. Jian *et al*. [19] also proposed the simple sequential quadratically constrained quadratic programming algorithm for smooth constrained optimization. Unlike the previous work, at each iteration, the main search direction is obtained by solving only one subprogram which is composed of a convex quadratic objective function and simple quadratic inequality constraints without the second derivatives of the constrained functions.

Although the SQP and SQCQP methods can effectively solve the minimax problem, this transformation may ignore the unique nature of the minimax problem and then increase the number of constraint functions. Moreover, these methods require the solution of one or two QP (QCQP) subproblems at each iteration, especially, some subproblems may be complex for the large-scale problems. In general, there are many cases where the subproblems cannot be solved easily, which will increase the amount of computations largely. Hence, (generalized) gradient projection method (GGPM) based on the Rosen gradient projection method [23] has been developed for solving inequality constrained optimization problems. The GGPM method has good properties that the search direction is only a gradient projection explicit formula and it has nice convergence and numerical results for middle-small-scale problems. These good natures cause widespread concern of many scholars [24–26]. In [25], Chapter II, there are more systematic and detailed study about generalized gradient projection algorithm for inequality constrained smooth optimization.

It is well established in the literature that, when the number of constraints is very large, the active set identification technique can improve the local convergence behavior and decrease the computation cost of the algorithms of nonlinear programming and minimax problems. An earlier study of the active set identification technique can be found in [27]. Many satisfactory results on the general nonlinear case were studied, *e.g.*, [28, 29]. Facchinei *et al*. [28] described a technique based on the algebraic representation of the constraint set, which identifies active constraints in a neighborhood of a solution. The extension to constrained minimax problems was also first presented in [30] without strict complementarity and linear independence. Moreover, the identification technique of active constraints for constrained minimax problems can be more suitable for infeasible algorithms, such as the strongly sub-feasible direction method and the penalty function method.

Despite GGPM’s importance and usefulness, there are no GGPM type method that are applied to solve minimax problems with inequality constraints. The aim of this paper is to propose such an algorithm, analyze its convergence properties, and report its numerical performance. Motivated by [26, 30], in this paper, we propose a generalized gradient projection algorithm directly on *R*^{n} with a new working set for the problem (1). The characteristics of our proposed algorithm can be summarized as follows:

- We propose a new optimal identification function for the stationary point, from which we provide a new working set.
- The search direction is generated by only one generalized gradient projection explicit formula, which is simple and could reduce the computational cost.
- Under some mild assumptions, the algorithm possesses the global and strong convergence.

The paper is organized as follows. The next section describes the algorithm. Section 3 discusses the convergence analysis. Section 4 contains numerical results. Finally, some conclusions are drawn in Section 5.

In this section, for the sake of simplicity, we introduce and use the following notations for the problem (1) in this paper:

2

3

According to the analysis of other projection algorithms, we need the following linear independence assumption.

The functions *f*_{j}(*x*) (*j* ∈ *I* ∪ *J*) are all first order continuously differentiable, and there exists an index *l*_{x} ∈ *I*(*x*) for each *x* ∈ *X* such that the gradient vectors {∇*f*_{i}(*x*)−∇*f*_{lx}(*x*), *i* ∈ *I*(*x*)∖{*l*_{x}}; ∇*f*_{j}(*x*), *j* ∈ *J*(*x*)} are linearly independent.

The vectors {∇*f*_{i}(*x*)−∇*f*_{t}(*x*), *i* ∈ *I*(*x*)∖{*t*}; ∇*f*_{j}(*x*), *j* ∈ *J*(*x*)} are linearly independent for arbitrarily *t* ∈ *I*(*x*).

For a given point *x*^{k} and the parameter *ε* ≥ 0, we use the following approximate active set in this paper:

$$\{\begin{array}{c}{I}_{k}=\{i\in I:-{\tilde{\varrho}}_{k}\le {f}_{i}({x}^{k})-F({x}^{k})\le 0\},\hfill \\ {J}_{k}=\{j\in J:-{\tilde{\varrho}}_{k}\le {f}_{j}({x}^{k})\le 0\},\hfill \end{array}$$

4

where ${\tilde{\varrho}}_{k}$ is taken by

$${\tilde{\varrho}}_{0}=\epsilon ,\phantom{\rule{2em}{0ex}}{\tilde{\varrho}}_{k}=min\{\epsilon ,{\varrho}_{k-1}\},\phantom{\rule{1em}{0ex}}k\ge 1,$$

5

*ϱ*_{k−1} ≥ 0 is the identification function corresponding to the last iteration point *x*^{k−1} and it can be calculated by (17). At each iteration, only *ϱ*_{k} need to be computed, since *ϱ*_{k−1} has already been calculated at the previous iteration, so the total computing capacity is not increase at each iteration.

For the current iteration point *x*^{k}, for convenience of statement, we define

$$\begin{array}{c}{F}^{k}:=F\left({x}^{k}\right),\phantom{\rule{2em}{0ex}}{f}_{i}^{k}:={f}_{i}\left({x}^{k}\right),\phantom{\rule{2em}{0ex}}{g}_{i}^{k}:=\mathrm{\nabla}{f}_{i}\left({x}^{k}\right),\phantom{\rule{1em}{0ex}}i\in I\cup J,\hfill \\ {l}_{k}\in I\left({x}^{k}\right),\phantom{\rule{2em}{0ex}}{I}_{k}^{0}:={I}_{k}\mathrm{\setminus}\{{l}_{k}\},\phantom{\rule{2em}{0ex}}{L}_{k}:={I}_{k}^{0}\cup {J}_{k}:=({I}_{k}\cup {J}_{k})\mathrm{\setminus}\{{l}_{k}\},\hfill \end{array}$$

where *l*_{k} ∈ *I*(*x*^{k}). In theory, the index *l*_{k} can be any component of the active set *I*(*x*^{k}) of Algorithm A, and all the theoretical analyses are the same. But we set *l*_{k} = *l*_{xk} = :min {*i*:*i* ∈ *I*(*x*^{k})} for convenience. We can easily find that *I*(*x*^{k}) ⊆ *I*_{k}, *J*(*x*^{k}) ⊆ *J*_{k}. Therefore, for the feasible point *x*^{k} of the problem (1), its stationary point (optimality conditions) can be described as

$$\{\begin{array}{c}{\sum}_{i\in {I}_{k}}{\lambda}_{i}^{k}{g}_{i}^{k}+{\sum}_{j\in {J}_{k}}{\lambda}_{j}^{k}{g}_{j}^{k}=0,{\sum}_{i\in {I}_{k}}{\lambda}_{i}^{k}=1,\hfill \\ {\lambda}_{i}^{k}\ge 0,{\lambda}_{i}^{k}({f}_{i}^{k}-{F}^{k})=0,i\in {I}_{k};{\lambda}_{j}^{k}\ge 0,{\lambda}_{j}^{k}{f}_{j}^{k}=0,j\in {J}_{k}.\hfill \end{array}$$

6

The foregoing conditions can be rewritten in the following equivalent form:

$$\{\begin{array}{c}{\sum}_{i\in {I}_{k}^{0}}{\lambda}_{i}^{k}({g}_{i}^{k}-{g}_{{l}_{k}}^{k})+{\sum}_{j\in {J}_{k}}{\lambda}_{j}^{k}{g}_{j}^{k}=-{g}_{{l}_{k}}^{k},\hfill \\ {\lambda}_{i}^{k}\ge 0,{\lambda}_{i}^{k}({f}_{i}^{k}-{F}^{k})=0,i\in {I}_{k}^{0};{\lambda}_{j}^{k}\ge 0,{\lambda}_{j}^{k}{f}_{j}^{k}=0,j\in {J}_{k},\hfill \\ {\lambda}_{{l}_{k}}^{k}=1-{\sum}_{i\in {I}_{k}^{0}}{\lambda}_{i}^{k}\ge 0.\hfill \end{array}$$

7

We define a generalized gradient projection matrix to test whether the current iteration point *x*^{k} satisfies (6)

8

where *E*_{n} is an *n*th-order identity matrix.

$${N}_{k}:=({g}_{i}^{k}-{g}_{{l}_{k}}^{k},i\in {I}_{k}^{0};{g}_{j}^{k},j\in {J}_{k}),\phantom{\rule{2em}{0ex}}{Q}_{k}:={({N}_{k}^{T}{N}_{k}+{D}_{k})}^{-1}{N}_{k}^{T},$$

9

$${D}_{k}:=diag({D}_{j}^{k},j\in {L}_{k}),\phantom{\rule{2em}{0ex}}{D}_{j}^{k}:=\{\begin{array}{cc}{({F}^{k}-{f}_{j}^{k})}^{p},\hfill & j\in {I}_{k}^{0};\hfill \\ {(-{f}_{j}^{k})}^{p},\hfill & j\in {J}_{k}.\hfill \end{array}$$

10

Suppose that (${x}^{k},{\lambda}_{{L}_{k}}^{k}$) is a stationary point pair, from (7), it is not difficult to get

$${N}_{k}^{T}{N}_{k}{\lambda}_{{L}_{k}}^{k}=-{N}_{k}^{T}{g}_{{l}_{k}}^{k},\phantom{\rule{2em}{0ex}}{D}_{k}{\lambda}_{{L}_{k}}^{k}=0,\phantom{\rule{2em}{0ex}}{\lambda}_{{L}_{k}}^{k}\ge 0.$$

These further imply that

$$({N}_{k}^{T}{N}_{k}+{D}_{k}){\lambda}_{{L}_{k}}^{k}=-{N}_{k}^{T}{g}_{{l}_{k}}^{k},\phantom{\rule{2em}{0ex}}{\lambda}_{{L}_{k}}^{k}=-{Q}_{k}{g}_{{l}_{k}}^{k},$$

11

$${P}_{k}{g}_{{l}_{k}}^{k}=0,\phantom{\rule{2em}{0ex}}{\lambda}_{{l}_{k}}^{k}\ge 0,\phantom{\rule{2em}{0ex}}{D}_{j}^{k}{\lambda}_{j}^{k}=0,\phantom{\rule{2em}{0ex}}{\lambda}_{j}^{k}\ge 0,\phantom{\rule{1em}{0ex}}j\in {L}_{k}.$$

12

Based on the above analysis, we introduce the following optimal identification function for the stationary point:

$${\rho}_{k}:={\parallel {P}_{k}{g}_{{l}_{k}}^{k}\parallel}^{2}+{\omega}_{k}+{\overline{\omega}}_{k}^{2},$$

13

where

$${\omega}_{k}:=\sum _{j\in {L}_{k}}max\{-{\mu}_{j}^{k},{\mu}_{j}^{k}{D}_{j}^{k}\},\phantom{\rule{2em}{0ex}}{\overline{\omega}}_{k}:=max\{-{\mu}_{{l}_{k}}^{k},0\},$$

14

$${\mu}_{{L}_{k}}^{k}:=-{Q}_{k}{g}_{{l}_{k}}^{k},\phantom{\rule{2em}{0ex}}{\mu}_{{l}_{k}}^{k}:=1-\sum _{i\in {I}_{k}^{0}}{\mu}_{i}^{k}.$$

15

Before describing our algorithm, one has the following lemma.

*Suppose that Assumption *
A1
*holds*. *Then*

- (i)
*the matrix*${N}_{k}^{T}{N}_{k}+{D}_{k}$*is nonsingular and positive definite*.*Suppose**x*^{k}→*x*^{∗},*N*_{k}→*N*_{∗},*D*_{k}→*D*_{∗},*then the matrix*${N}_{\ast}^{T}{N}_{\ast}+{D}_{\ast}$*is also nonsingular and positive definite*; - (ii) ${N}_{k}^{T}{P}_{k}={D}_{k}{Q}_{k}$, ${N}_{k}^{T}{Q}_{k}^{T}={E}_{|{L}_{k}|}-{D}_{k}{({N}_{k}^{T}{N}_{k}+{D}_{k})}^{-1}$;
- (iii) ${({g}_{{l}_{k}}^{k})}^{T}{P}_{k}{g}_{{l}_{k}}^{k}={\parallel {P}_{k}{g}_{{l}_{k}}^{k}\parallel}^{2}+{\sum}_{j\in {L}_{k}}{({\mu}_{j}^{k})}^{2}{D}_{j}^{k}$;
- (iv)
*ρ*_{k}= 0*if and only if**x*^{k}*is a stationary point of the problem*(1).

Under Assumption A1, it is shown that the matrix ${N}_{k}^{T}{N}_{k}+{D}_{k}$ is nonsingular by [25], Theorem 1.1.9. Then, we can prove that the matrix ${N}_{\ast}^{T}{N}_{\ast}+{D}_{\ast}$ is also definite similar to [25], Lemma 2.2.2. The conclusions (ii) and (iii) can obtained similar to [25], Theorem 1.1.9. Next, we prove the conclusion (iv) in detail below.

(iv) If *ρ*_{k} = 0, combining the equations (13), (8), and (15), we obtain

$$0={P}_{k}{g}_{{l}_{k}}^{k}={g}_{{l}_{k}}^{k}-{N}_{k}{Q}_{k}{g}_{{l}_{k}}^{k}={g}_{{l}_{k}}^{k}+{N}_{k}{\mu}_{{L}_{k}}^{k}.$$

We have $max\{-{\mu}_{j}^{k},{\mu}_{j}^{k}{D}_{j}\}=0$ by *ω*_{k} = 0, which follows by ${\mu}_{j}^{k}\ge 0$, ${\mu}_{j}^{k}{D}_{j}^{k}=0$, ∀*j* ∈ *L*_{k} and it is not difficult to get ${\mu}_{{l}_{k}}^{k}\ge 0$ by ${\overline{\omega}}_{k}=0$. So we have

$$\{\begin{array}{c}{\sum}_{i\in {I}_{k}}{\mu}_{i}^{k}{g}_{i}^{k}+{\sum}_{j\in {J}_{k}}{\mu}_{j}^{k}{g}_{j}^{k}=0,{\sum}_{i\in {I}_{k}}{\mu}_{i}^{k}=1,\hfill \\ {\mu}_{i}^{k}\ge 0,{\mu}_{i}^{k}({f}_{i}^{k}-{F}^{k})=0,i\in {I}_{k};{\mu}_{j}^{k}\ge 0,{\mu}_{j}^{k}{f}_{j}^{k}=0,j\in {J}_{k}.\hfill \end{array}$$

Therefore, *x*^{k} is a stationary point of the problem (1) with the multiplier $({\mu}_{{I}_{k}\cup {J}_{k}}^{k},{0}_{(I\cup J)\mathrm{\setminus}({I}_{k}\cup {J}_{k})})$.

Conversely, if *x*^{k} is a stationary point of the problem (1) with the multiplier vector *λ*^{k}, then from the (6)-(15) one knows that ${\mu}_{{L}_{k}}^{k}={\lambda}_{{L}_{k}}^{k}$, and *ρ*_{k} = 0.□

The above results show that the current iteration point *x*^{k} is a stationary point of the problem (1) if and only if *ρ*_{k} = 0, that is, *ρ*_{k} is optimal identification function. In case of *ρ*_{k} > 0, together with *I*_{k} and *J*_{k}, we compute the search direction, which is motivated by the generalized gradient projection technique in [25], Chapter II, and [26]

$${d}^{k}={\rho}_{k}^{\xi}\{-{P}_{k}{g}_{{l}_{k}}^{k}+{Q}_{k}^{T}{v}_{{L}_{k}}^{k}\}-{\varrho}_{k}{Q}_{k}^{T}{e}^{k},$$

16

where the parameter *ξ* > 0, *e*^{k} = (1,1,…,1)^{T} ∈ *R*^{|Lk|},

$${\varrho}_{k}=\frac{{\rho}_{k}^{1+\xi}}{1+{\parallel {\mu}_{{L}_{k}}^{k}\parallel}_{1}},$$

17

the vector ${v}_{{L}_{k}}^{k}=({v}_{j}^{k},j\in {L}_{k})$ with

$${v}_{j}^{k}=\{\begin{array}{cc}{\overline{\omega}}_{k}-1,\hfill & \text{if}{\mu}_{j}^{k}0,j\in {I}_{k}^{0};\hfill \\ {\overline{\omega}}_{k}+{D}_{j}^{k},\hfill & \text{if}{\mu}_{j}^{k}\ge 0,j\in {I}_{k}^{0},\hfill \end{array}\phantom{\rule{2em}{0ex}}{v}_{j}^{k}=\{\begin{array}{cc}-1,\hfill & \text{if}{\mu}_{j}^{k}0,j\in {J}_{k};\hfill \\ {D}_{j}^{k},\hfill & \text{if}{\mu}_{j}^{k}\ge 0,j\in {J}_{k}.\hfill \end{array}$$

18

The following lemma further describes the important characteristics of the search direction, which is feasible and descent.

*Suppose that Assumption *
A1
*holds*. *Then*

- (i) ${({g}_{{l}_{k}}^{k})}^{T}{d}^{k}\le -{\rho}_{k}^{\xi}{\overline{\omega}}_{k}-{\varrho}_{k}$;
- (ii)
${({g}_{j}^{k})}^{T}{d}^{k}\le -{\varrho}_{k}$, ∀
*j*∈ (*I*(*x*^{k})∖{*l*_{k}}) ∪*J*(*x*^{k}); - (iii)
*F*^{′}(*x*^{k};*d*^{k}) ≤ −*ϱ*_{k},*where**F*^{′}(*x*^{k};*d*^{k})*is the directional derivative of**F*(*x*)*at the point**x*^{k}*along the direction**d*^{k}.

(i) First, by (16), together with Lemma 1(iii), (15), (18) and (14), we obtain

$$\begin{array}{rl}{\left({g}_{{l}_{k}}^{k}\right)}^{T}{d}^{k}& ={\rho}_{k}^{\xi}\{-{\left({g}_{{l}_{k}}^{k}\right)}^{T}{P}_{k}{g}_{{l}_{k}}^{k}+{\left({Q}_{k}{g}_{{l}_{k}}^{k}\right)}^{T}{v}_{{L}_{k}}^{k}\}-{\varrho}_{k}{\left({Q}_{k}{g}_{{l}_{k}}^{k}\right)}^{T}{e}^{k}\\ & ={\rho}_{k}^{\xi}\{-{\parallel {P}_{k}{g}_{{l}_{k}}^{k}\parallel}^{2}-\sum _{j\in {L}_{k}}{\left({\mu}_{j}^{k}\right)}^{2}{D}_{j}^{k}-{\left({\mu}_{{L}_{k}}^{k}\right)}^{T}{v}_{{L}_{k}}^{k}\}+{\varrho}_{k}{\left({\mu}_{{L}_{k}}^{k}\right)}^{T}{e}^{k}\\ & \le {\rho}_{k}^{\xi}\{-{\parallel {P}_{k}{g}_{{l}_{k}}^{k}\parallel}^{2}-\sum _{{\mu}_{i}^{k}<0,i\in {I}_{k}^{0}}{\mu}_{i}^{k}({\overline{\omega}}_{k}-1)-\sum _{{\mu}_{i}^{k}\ge 0,i\in {I}_{k}^{0}}{\mu}_{i}^{k}({\overline{\omega}}_{k}+{D}_{i}^{k})\\ & \phantom{\rule{1em}{0ex}}-\sum _{{\mu}_{j}^{k}<0,j\in {J}_{k}}(-{\mu}_{j}^{k})-\sum _{{\mu}_{j}^{k}\ge 0,j\in {J}_{k}}{\mu}_{j}^{k}{D}_{j}^{k}\}+{\varrho}_{k}{\left({\mu}_{{L}_{k}}^{k}\right)}^{T}{e}^{k}\\ & ={\rho}_{k}^{\xi}\{-{\parallel {P}_{k}{g}_{{l}_{k}}^{k}\parallel}^{2}-\sum _{{\mu}_{j}^{k}<0,j\in {L}_{k}}(-{\mu}_{j}^{k})-\sum _{{\mu}_{j}^{k}\ge 0,j\in {L}_{k}}{\mu}_{j}^{k}{D}_{j}^{k}-{\overline{\omega}}_{k}\sum _{i\in {I}_{k}^{0}}{\mu}_{i}^{k}\}+{\varrho}_{k}{\left({\mu}_{{L}_{k}}^{k}\right)}^{T}{e}^{k}\\ & ={\rho}_{k}^{\xi}\{-{\parallel {P}_{k}{g}_{{l}_{k}}^{k}\parallel}^{2}-{\omega}_{k}-{\overline{\omega}}_{k}\sum _{i\in {I}_{k}^{0}}{\mu}_{i}^{k}\}+{\varrho}_{k}{\left({\mu}_{{L}_{k}}^{k}\right)}^{T}{e}^{k}.\end{array}$$

In addition, based on the definition of ${\mu}_{{l}_{k}}^{k}$, it immediately follows ${\overline{\omega}}_{k}{\sum}_{i\in {I}_{k}^{0}}{\mu}_{i}^{k}={\overline{\omega}}_{k}+{\overline{\omega}}_{k}(-{\mu}_{{l}_{k}}^{k})$. If ${\mu}_{{l}_{k}}^{k}\ge 0$, we have ${\overline{\omega}}_{k}=0$, ${\overline{\omega}}_{k}(-{\mu}_{{l}_{k}}^{k})=0={\overline{\omega}}_{k}^{2}$. On the other hand ${\mu}_{{l}_{k}}^{k}<0$, then ${\overline{\omega}}_{k}=-{\mu}_{{l}_{k}}^{k}$, ${\overline{\omega}}_{k}(-{\mu}_{{l}_{k}}^{k})={\overline{\omega}}_{k}^{2}$. Thus, ${\overline{\omega}}_{k}{\sum}_{i\in {I}_{k}^{0}}{\mu}_{i}^{k}={\overline{\omega}}_{k}+{\overline{\omega}}_{k}^{2}$ is always true. We have from (13) and (17)

$$\begin{array}{rl}{\left({g}_{{l}_{k}}^{k}\right)}^{T}{d}^{k}& \le {\rho}_{k}^{\xi}\{-{\parallel {P}_{k}{g}_{{l}_{k}}^{k}\parallel}^{2}-{\omega}_{k}-{\overline{\omega}}_{k}-{\overline{\omega}}_{k}^{2}\}+{\varrho}_{k}{\left({\mu}_{{L}_{k}}^{k}\right)}^{T}{e}^{k}\\ & ={\rho}_{k}^{\xi}(-{\rho}_{k}-{\overline{\omega}}_{k})+{\varrho}_{k}{\left({\mu}_{{L}_{k}}^{k}\right)}^{T}{e}^{k}\\ & \le -{\rho}_{k}^{\xi}{\overline{\omega}}_{k}-{\rho}_{k}^{1+\xi}+{\varrho}_{k}{\parallel {\mu}_{{L}_{k}}^{k}\parallel}_{1}\\ & =-{\rho}_{k}^{\xi}{\overline{\omega}}_{k}-{\varrho}_{k}.\end{array}$$

19

(ii) From Lemma 1(ii) and (16), we obtain

$$\begin{array}{rl}{N}_{k}^{T}{d}^{k}& ={\rho}_{k}^{\xi}\{-{N}_{k}^{T}{P}_{k}{g}_{{l}_{k}}^{k}+{N}_{k}^{T}{Q}_{k}^{T}{v}_{{L}_{k}}^{k}\}-{\varrho}_{k}{N}_{k}^{T}{Q}_{k}^{T}{e}^{k}\\ & ={\rho}_{k}^{\xi}\{-{D}_{k}{Q}_{k}{g}_{{l}_{k}}^{k}+{v}_{{L}_{k}}^{k}-{D}_{k}{({N}_{k}^{T}{N}_{k}+{D}_{k})}^{-1}{v}_{{L}_{k}}^{k}\}\\ & \phantom{\rule{1em}{0ex}}-{\varrho}_{k}\{{E}_{|{L}_{k}|}-{D}_{k}{({N}_{k}^{T}{N}_{k}+{D}_{k})}^{-1}\}{e}^{k}.\end{array}$$

20

Then we discuss the following two cases, respectively.

*Case 1.* For $i\in (I({x}^{k})\mathrm{\setminus}\{{l}_{k}\})\subseteq {I}_{k}^{0}$, it follows that ${D}_{j}^{k}=0$. From (20), we have ${({g}_{i}^{k}-{g}_{{l}_{k}}^{k})}^{T}{d}^{k}={\rho}_{k}^{\xi}{v}_{i}^{k}-{\varrho}_{k}$. Then, combined (18) with conclusion (i), we have

$${\left({g}_{i}^{k}\right)}^{T}{d}^{k}={\left({g}_{{l}_{k}}^{k}\right)}^{T}{d}^{k}+{\rho}_{k}^{\xi}{v}_{i}^{k}-{\varrho}_{k}\le -{\varrho}_{k}-{\rho}_{k}^{\xi}{\overline{\omega}}_{k}+{\rho}_{k}^{\xi}{\overline{\omega}}_{k}-{\varrho}_{k}=-2{\varrho}_{k}\le -{\varrho}_{k}.$$

*Case 2.* For *j* ∈ *J*(*x*^{k}) ⊆ *J*_{k}, ${D}_{j}^{k}=0$ holds. It follows from (20) and (18) that

$${\left({g}_{j}^{k}\right)}^{T}{d}^{k}={\rho}_{k}^{\xi}{v}_{j}^{k}-{\varrho}_{k}\le -{\varrho}_{k}.$$

By summarizing the above discussion, the conclusion (ii) holds.

(iii) Since ${F}^{\prime}({x}^{k};{d}^{k})=max\{{({g}_{i}^{k})}^{T}{d}^{k},i\in I({x}^{k})\}$, we have *F*^{′}(*x*^{k}; *d*^{k}) ≤ −*ϱ*_{k} from the conclusions (i) and (ii).□

Based on the improved direction *d*^{k} defined by (16) and analysed above, we are now ready to describe the steps of our algorithm as follows.

*Step 0.* Choose an initial feasible point *x*^{0} ∈ *X* and parameters: *α*, *β* ∈ (0, 1), *ε* > 0, *p* ≥ 1, *ξ* > 0. Let *k*: = 0.

*Step 1.* For the current iteration point *x*^{k}, generate the working set *I*_{k}, *J*_{k} by (4) and (5), calculate the projection matrix *P*_{k}, the optimal identification function values *ρ*_{k} and *ϱ*_{k} by (8), (13)-(15) and (17). If *ρ*_{k} = 0, then *x*^{k} is a stationary point of the problem (1), stop. Otherwise, go to Step 2.

*Step 2.* Obtain the search direction *d*^{k} by (16)-(18).

*Step 3.* Compute the step size *t*_{k}, which is the maximum *t* of the sequence {1, *β*, *β*^{2}, …} satisfying

21

22

*Step 4.* Let *x*^{k+1} = *x*^{k} + *t*_{k}*d*^{k}, *k*: = *k* + 1, and go back to Step 1.

The inequality (21) is equivalent to *f*_{i}(*x*^{k} + *t**d*^{k}) ≤ *F*^{k} − *α**t**ϱ*_{k}, *i* ∈ *I*.

Note that Lemma 2, we get *F*^{′}(*x*^{k}; *d*^{k}) ≤ −*ϱ*_{k} < 0 and ${({g}_{j}^{k})}^{T}{d}^{k}\le -{\varrho}_{k}$, ∀*j* ∈ *J*(*x*^{k}), so it is easy to know that (21) and (22) hold for *t* > 0 small enough, then Algorithm A is well defined.

In this section, we will analyze the global and strong convergence of Algorithm A. If Algorithm A stops at *x*^{k} in a finite number of iterations, then *ρ*_{k} = 0. From Lemma 1(iv), we know that *x*^{k} is a stationary point of the problem (1). Next, we assume that Algorithm A yields an infinite iteration sequence {*x*^{k}} of points, and prove that any accumulation point *x*^{∗} of {*x*^{k}} is a stationary point for the problem (1) under some mild conditions including the following assumption.

The sequence {*x*^{k}} generated by Algorithm A is bounded.

(i) Because of Assumption A2 and Lemma 1(i), it is easy to get the total sequences ${\{{P}_{k}\}}_{k=1}^{\mathrm{\infty}}$ and ${\{{Q}_{k}\}}_{k=1}^{\mathrm{\infty}}$ of matrices are bounded. Furthermore, from (15) and (18), we know that $\{{\mu}_{{L}_{k}}^{k}\}$ and $\{{v}_{{L}_{k}}^{k}\}$ are bounded. This implies that $\parallel {d}^{k}\parallel \le c{\rho}_{k}^{\xi}$.

(ii) In view of {*F*(*x*^{k})} is decreasing and bounded, so lim_{k→∞}*F*(*x*^{k}) = *F*(*x*^{∗}). Then, combining (17) with the definition of *ϱ*_{k}, one has ${lim}_{k\to \mathrm{\infty}}{t}_{k}{\rho}_{k}^{1+\xi}=0$. Taking into account the parameter *ξ* > 0, it follows that

$$\underset{k\to \mathrm{\infty}}{lim}\parallel {x}^{k+1}-{x}^{k}\parallel =\underset{k\to \mathrm{\infty}}{lim}{t}_{k}\parallel {d}^{k}\parallel \le \underset{k\to \mathrm{\infty}}{lim}c{t}_{k}{\rho}_{k}^{\xi}=c\underset{k\to \mathrm{\infty}}{lim}{\left[{\left({t}_{k}{\rho}_{k}^{1+\xi}\right)}^{\xi}{t}_{k}\right]}^{\frac{1}{1+\xi}}=0.$$

□

Based on the lemma above, we can present the global convergence of our algorithm.

*Suppose that Assumptions*
A1
*and*
A2
*hold*. *Then Algorithm *
A
*generates an infinite sequence*
{*x*^{k}}
*of points such that each accumulation*
*x*^{∗}
*of*
{*x*^{k}}
*is a stationary point of the problem* (1).

If the infinite iteration index set 𝒦 satisfies lim_{k∈𝒦}*x*^{k} = *x*^{∗}, it follows that lim_{k∈𝒦}*x*^{k−1} = *x*^{∗} from Lemma 3(ii). Noting that *I*_{k}, *J*_{k} and *l*_{k} are finite, we suppose ∀*k* ∈ 𝒦 (choosing a subsequence of 𝒦 when necessary) satisfies

$${I}_{k}\equiv {I}_{\ast},\phantom{\rule{2em}{0ex}}{J}_{k}\equiv {J}_{\ast},\phantom{\rule{2em}{0ex}}{l}_{k}\equiv {l}_{\ast},\phantom{\rule{2em}{0ex}}{I}_{k}^{0}\equiv {I}_{\ast}^{0}:=\{{I}_{\ast}\}\mathrm{\setminus}{l}_{\ast},\phantom{\rule{2em}{0ex}}{L}_{k}\equiv {L}_{\ast}:={I}_{\ast}^{0}\cup {J}_{\ast},$$

23

$$\begin{array}{rl}& {I}_{k-1}\equiv {\overline{I}}_{\ast},\phantom{\rule{2em}{0ex}}{J}_{k-1}\equiv {\overline{J}}_{\ast},\phantom{\rule{2em}{0ex}}{l}_{k-1}\equiv {\overline{l}}_{\ast},\\ & {I}_{k-1}^{0}\equiv {\overline{I}}_{\ast}^{0}:=\{{\overline{I}}_{\ast}\}\mathrm{\setminus}{\overline{l}}_{\ast},\phantom{\rule{2em}{0ex}}{L}_{k-1}\equiv {\overline{L}}_{\ast}:={\overline{I}}_{\ast}^{0}\cup {\overline{J}}_{\ast}.\end{array}$$

24

Define

$${D}_{j}^{\ast}=\{\begin{array}{cc}{(F({x}^{\ast})-{f}_{j}({x}^{\ast}))}^{p},\hfill & j\in {I}_{\ast}\mathrm{\setminus}\{{l}_{\ast}\};\hfill \\ {(-{f}_{j}({x}^{\ast}))}^{p},\hfill & j\in {J}_{\ast},\hfill \end{array}\phantom{\rule{2em}{0ex}}{D}_{\ast}=diag({D}_{j}^{\ast},j\in {L}_{\ast}),$$

25

$${N}_{\ast}=(\mathrm{\nabla}{f}_{i}\left({x}^{\ast}\right)-\mathrm{\nabla}{f}_{{l}_{\ast}}\left({x}^{\ast}\right),i\in {I}_{\ast}^{0};\mathrm{\nabla}{f}_{j}\left({x}^{\ast}\right),j\in {J}_{\ast}),\phantom{\rule{2em}{0ex}}{P}_{\ast}={E}_{n}-{N}_{\ast}{Q}_{\ast},$$

26

$${Q}_{\ast}={({N}_{\ast}^{T}{N}_{\ast}+{D}_{\ast})}^{-1}{N}_{\ast}^{T},{\mu}_{{L}_{\ast}}^{\ast}=({\mu}_{j}^{\ast},j\in {L}_{\ast})=-{Q}_{\ast}\mathrm{\nabla}{f}_{{l}_{\ast}}\left({x}^{\ast}\right),$$

27

$${\omega}_{\ast}=\sum _{j\in {L}_{\ast}}max\{-{\mu}_{j}^{\ast},{\mu}_{j}^{\ast}{D}_{j}^{\ast}\},\phantom{\rule{2em}{0ex}}{\mu}_{{l}_{\ast}}^{\ast}=1-\sum _{i\in {I}_{\ast}^{0}}{\mu}_{i}^{\ast},\phantom{\rule{2em}{0ex}}{\overline{\omega}}_{\ast}=max\{-{\mu}_{{l}_{\ast}}^{\ast},0\},$$

28

$${\rho}_{\ast}={\parallel {P}_{\ast}\mathrm{\nabla}{f}_{{l}_{\ast}}\left({x}^{\ast}\right)\parallel}^{2}+{\omega}_{\ast}+{\overline{\omega}}_{\ast}^{2},\phantom{\rule{2em}{0ex}}{\varrho}_{\ast}=\frac{{\rho}_{\ast}^{1+\xi}}{1+{\parallel {\mu}_{{L}_{\ast}}^{\ast}\parallel}_{1}}.$$

29

The above definitions are well defined by Lemma 1(i). Similarly, for *x*^{∗}, ${\overline{I}}_{\ast}$, ${\overline{J}}_{\ast}$ and ${\overline{l}}_{\ast}$, we define ${\overline{\rho}}_{\ast}$ and ${\overline{\varrho}}_{\ast}$. In addition, the matrix ${N}_{\ast}^{T}{N}_{\ast}+{D}_{\ast}$ is positive definite by Lemma 1(i). Therefore, the sequences {*v*^{k}}_{𝒦} and {*d*^{k}}_{𝒦} are bounded. Then, assume by contradiction that *x*^{∗} is not the stationary point of the problem (1), we can easily get *ϱ*_{∗} > 0 and ${\overline{\varrho}}_{\ast}>0$ similar to the analysis of Lemma 1(iv). Then, we have

$$\begin{array}{c}{\varrho}_{k}\ge 0.5{\varrho}_{\ast},\phantom{\rule{2em}{0ex}}{\varrho}_{k-1}\stackrel{\mathcal{K}}{\to}{\overline{\varrho}}_{\ast}:=\frac{{\overline{\rho}}_{\ast}}{1+\parallel {\overline{\mu}}_{{\overline{L}}_{\ast}}^{\ast}\parallel}>0,\hfill \\ {\tilde{\varrho}}_{k}=min\{\epsilon ,{\varrho}_{k-1}\}\stackrel{\mathcal{K}}{\to}{\varrho}_{\ast}^{\sim}:=min\{\epsilon ,{\overline{\varrho}}_{\ast}\}>0.\hfill \end{array}$$

Next, we will prove this theorem in two steps.

A. The step size sequence {*t*_{k}}_{k∈𝒦} is always bounded away from zero, that is, $\overline{t}:=inf\{{t}_{k},k\in \mathcal{K}\}>0$. We only need to show the inequalities (21) and (22) hold for *k* ∈ 𝒦 large enough and *t* > 0 sufficiently small.

A1. For *i* ∈ *I*, in this case, we have *i* ∉ *I*(*x*^{∗}) and *i* ∈ *I*(*x*^{∗}) as two cases.

A11. Case *i* ∉ *I*(*x*^{∗}), that is *f*_{i}(*x*^{∗}) < *F*(*x*^{∗}). Taking into account the differentiability of *f*_{i}(*x*) and the boundedness of {*d*^{k}}_{𝒦} and using Taylor expansion, we have

$$\begin{array}{rl}{f}_{i}({x}^{k}+t{d}^{k})-{F}^{k}+\alpha t{\varrho}_{k}& ={f}_{i}^{k}+t{\left({g}_{i}^{k}\right)}^{T}{d}^{k}+o(t)-{F}^{k}+\alpha t{\varrho}_{k}\\ & ={f}_{i}^{k}-{F}^{k}+O(t)\\ & \le 0.5({f}_{i}\left({x}^{\ast}\right)-F\left({x}^{\ast}\right))+O(t)\\ & \le 0.\end{array}$$

A12. Case *i* ∈ *I*(*x*^{∗}), that is, *f*_{i}(*x*^{∗}) = *F*(*x*^{∗}). Note that *x*^{k} → *x*^{∗} and ${\varrho}_{\ast}^{\sim}>0$, by (4) and (5), we know that *I*(*x*^{∗}) ⊆ *I*_{k} always holds for *k* ∈ 𝒦 large enough. Hence, *i* ∈ *I*_{k}. In this case, we also have two cases, which are *i* = *l*_{∗} and *i* ≠ *l*_{∗}. Therefore, we discuss the two cases, respectively.

Assume *i* = *l*_{∗}, it follows by Lemma 2(i) that

$${\left({g}_{{l}_{\ast}}^{k}\right)}^{T}{d}^{k}\le -{\rho}_{k}^{\xi}{\overline{\omega}}_{k}-{\varrho}_{k}\le -{\varrho}_{k}.$$

30

Assume *i* ≠ *l*_{∗}, ${D}_{i}^{k}={({F}^{k}-{f}_{i}^{k})}^{p}\stackrel{\mathcal{K}}{\to}{(F({x}^{\ast})-{f}_{i}({x}^{\ast}))}^{p}=0$. From Lemma 1(i), we have ${({N}_{k}^{T}{N}_{k}+{D}_{k})}^{-1}\to {({N}_{\ast}^{T}{N}_{\ast}+{D}_{\ast})}^{-1}$. Together with (20) we conclude that

$${({g}_{i}^{k}-{g}_{{l}_{k}}^{k})}^{T}{d}^{k}={\rho}_{k}^{\xi}{v}_{i}^{k}-{\varrho}_{k}+O\left({D}_{i}^{k}\right).$$

In view of (18), ${v}_{i}^{k}\le {\overline{\omega}}_{k}+O({D}_{i}^{k})$ holds. Combining (19) with *ϱ*_{k} → *ϱ*_{∗} > 0, we have

$${\left({g}_{i}^{k}\right)}^{T}{d}^{k}\le {\rho}_{k}^{\xi}{\overline{\omega}}_{k}+{\left({g}_{{l}_{k}}^{k}\right)}^{T}{d}^{k}-{\varrho}_{k}+O\left({D}_{i}^{k}\right)\le -2{\varrho}_{k}+O\left({D}_{i}^{k}\right)\le -{\varrho}_{k}.$$

31

Thus, for *i* ∈ *I*(*x*^{∗}), from (30) and (31), using Taylor expansion, we obtain

$$\begin{array}{rl}{f}_{i}({x}^{k}+t{d}^{k})-{F}^{k}+\alpha t{\varrho}_{k}& \le {f}_{i}^{k}+t{\left({g}_{i}^{k}\right)}^{T}{d}^{k}+o(t)-{f}_{i}^{k}+\alpha t{\varrho}_{k}\\ & \le -(1-\alpha )t{\varrho}_{k}+o(t)\\ & \le -0.5t(1-\alpha ){\varrho}_{\ast}+o(t)\\ & \le 0.\end{array}$$

According to the analysis of the above A11 and A12, it is sufficient to show that the inequality (21) is always satisfied for *k* ∈ 𝒦 large enough and *t* > 0 sufficiently small.

A2. For *j* ∈ *J*, there are also *j* ∉ *J*(*x*^{∗}) and *j* ∈ *J*(*x*^{∗}) two cases.

A21. Case *j* ∉ *J*(*x*^{∗}), it follows that *f*_{j}(*x*^{∗}) < 0. Taking into account the boundedness of {*d*^{k}}_{𝒦} and using Taylor expansion, we have

$${f}_{j}({x}^{k}+t{d}^{k})={f}_{j}^{k}+O(t)\le 0.5{f}_{j}\left({x}^{\ast}\right)+O(t)\le 0.$$

32

A22. Case *j* ∈ *J*(*x*^{∗}), that is, *f*_{j}(*x*^{∗}) = 0. *j* ∈ *J*_{k} follows in a similar analysis to A12, and we have ${D}_{j}^{k}={(-{f}_{j}^{k})}^{p}\stackrel{\mathcal{K}}{\to}0$. By recalling (20), ${({g}_{j}^{k})}^{T}{d}^{k}={\rho}_{k}^{\xi}{v}_{j}^{k}-{\varrho}_{k}+O({D}_{j}^{k})$. Then using Taylor expansion and (18), we get

$$\begin{array}{rl}{f}_{j}({x}^{k}+t{d}^{k})& ={f}_{j}^{k}+t{\left({g}_{j}^{k}\right)}^{T}{d}^{k}+o(t)\\ & \le {f}_{j}^{k}-t{\varrho}_{k}+tO\left({D}_{j}^{k}\right)+o(t)\\ & \le -0.5t{\varrho}_{\ast}+o(t)\\ & \le 0.\end{array}$$

Thus, inequality (22) always holds for *k* ∈ 𝒦 large enough and *t* > 0 sufficiently small. Hence, $\overline{t}:=inf\{{t}_{k},k\in \mathcal{K}\}>0$ holds.

B. Export contradiction by using ${t}_{k}\ge \overline{t}>0$ (*k* ∈ 𝒦). In view of (21), it is easy to know that the sequence {*F*^{k}} is monotone nonincreasing. Since lim_{k∈𝒦}*F*^{k} = *F*(*x*^{∗}), it implies lim_{k→∞}*F*^{k} = *F*(*x*^{∗}). This, together with (21) and ${t}_{k}\ge \overline{t}$, *ϱ*_{k} ≥ 0.5*ϱ*_{∗}, we have

$$F\left({x}^{\ast}\right)=\underset{k\in \mathcal{K}}{lim}{F}^{k+1}\le \underset{k\in \mathcal{K}}{lim}({F}^{k}-\alpha {t}_{k}{\varrho}_{k})\le \underset{k\in \mathcal{K}}{lim}({F}^{k}-0.5\alpha \overline{t}{\varrho}_{\ast})=F\left({x}^{\ast}\right)-0.5\alpha \overline{t}{\varrho}_{\ast},$$

which contradicts $\overline{t}>0$ and *ϱ*_{∗} > 0. Therefore, *x*^{∗} is a stationary point for the problem (1), and the whole proof is completed.□

Subsequently, we further show that Algorithm A has the property of strong convergence.

*Suppose that Assumptions*
A1
*and*
A2
*hold*. *If the sequence*
{*x*^{k}}
*of points generated by Algorithm *
A
*possesses an isolated accumulation point*
*x*^{∗}, *then*
lim_{k→∞}*x*^{k} = *x*^{∗}, *that is*, *Algorithm *
A
*is strongly convergent*.

Since the sequence {*x*^{k}} of points generated by Algorithm A possesses an isolated accumulation point, together with lim_{k→∞} ∥ *x*^{k+1} − *x*^{k} ∥ = 0 (Lemma 3(ii)) and [25], Corollary 1.1.8, we immediately have lim_{k→∞}*x*^{k} = *x*^{∗}. Finally, by lim_{k→∞}*x*^{k} = *x*^{∗} and Theorem 1, it follows that *x*^{∗} is the stationary point of the problem (1).□

In this section, in order to validate the efficiency of our proposed Algorithm A, some preliminary numerical experiments have been carried out. Test problems are divided into two groups. The first test group is made up of 10 problems (P1-P10), of which four small scale problems P1-P4 are taken from [25], which is the problem 7.3.28, 7.3.32, 7.3.31 and 7.3.29, respectively; and the other six middle-large-scale problems P5-P10 are from [31]. These six problems are composed of the corresponding objective functions and constraint functions in [31]. The second test group, we pick up six problems from [31] and compare the results of Algorithm A with the algorithm from [17] (called Algorithm B). In particular, P5 = 2.3 + 4.1(1) (which means the objective and constraints of the problem P11 are 2.3 and 4.1(1) in [31], respectively, and the same blew), P6 = 2.3 + 4.6(2), P7 = 2.1 + 4.6(2), P8 = 2.1 + 4.1(1), P9 = 2.5 + 4.6(2) (*n* = 200), P10 = 2.9 + 4.1(1), P11 = 2.1 + 4.6(1), P12 = 2.5 + 4.6(2) (*n* = 50), P13 = 2.9 + 4.6(2).

Algorithm A is coded in MATLAB R2010b, and on a PC computer with Windows 7, Intel(R) Pentium(R) CPU 2.4 GHz. During the numerical experiments, we set parameters *α* = 0.4, *β* = 0.4, *ε* = 7, *p* = 1, *ξ* = 0.2. Execution is terminated if *ρ*_{k} < 10^{−5} or NI ≥ 150.

The numerical results are listed in Tables 1 and and2.2. The following notations are used: ‘Prob.’: the test problem number; ‘n’: the dimensions of the variable *x*; ‘*l*‘: number of all component objective functions; ‘*m*’: number of constraint functions; ‘*x*^{0}’: initial feasible point; ‘Alg.’: algorithm; ‘A and B’: the algorithms of this paper and [17], respectively. ‘NI’: number of iterations; ‘NF’: number of all component functions evaluations in the objective; ‘NC’: number of constraints evaluations; ‘T’: CPU time (in seconds); ‘-’: the corresponding datum are not reported; ‘*F*(*x*^{∗})’: final objective value.

From Table 1, we see that Algorithm A can generate approximately optimal solution for all the test problems. The search direction is generated by the generalized gradient projection explicit formula, and a new working set is used, which can reduce the scale of the generalized gradient projection, so the proposed Algorithm A is efficient.

In Table 2, we compare our Algorithm A with Algorithm B, and all the numerical results are tested by a same PC computer. The performance of the two algorithms is similar in terms of the approximate optimal objective value at the final iteration point, although the number of all component functions evaluations in the objective and constraints evaluations is few for Algorithm B, our proposed algorithm performs much better than Algorithm B relative to the cost of CPU running times.

In summary, through the numerical results in two tables and the analysis above, we can get that the proposed Algorithm A is promising for middle-small-scale minimax problem.

Although the generalized gradient projection algorithms have good theoretical convergence and effectiveness in practice, their applications to minimax problems have not yet been investigated. In this paper, we present a new generalized gradient projection algorithm for minimax optimization problems with inequality constraints.

The main conclusions of this work:

- A new approximation working set is presented.
- Using the technique of generalized gradient projection, we construct a generalized gradient projection feasible decent direction.
- Under mild assumptions, the algorithm is global and strong convergent.
- Some preliminary numerical results show that the proposed algorithm performs efficiently.

In this work, a new generalized gradient projection algorithm for minimax optimization problems with inequality constraints is presented. As further work, we think the ideas can be extended to minimax optimization problems with equality and inequality constraints and other optimization problems.

Project supported by the Natural Science Foundation of China (No. 11271086), the Natural Science Foundation of Guangxi Province (No. 2015GXNSFBA139001) and the Science Foundation of Guangxi Education Department (No. KY2015YB242) as well as the Doctoral Scientific Research Foundation (No. G20150010).

**Competing interests**

The authors declare that they have no competing interests.

**Authors’ contributions**

GDM carried out the idea of this paper, the description of Algorithm A and drafted the manuscript. YFZ carried out the convergence the analysis of Algorithm A. MXL participated in the numerical experiments and helped to draft the manuscript. All authors read and approved the final manuscript.

Guodong Ma, Email: moc.361@6002dgm.

Yufeng Zhang, Email: moc.qq@0452548711.

Meixing Liu, Email: moc.621@1102gnixiemuil.

1. Baums A. Minimax method in optimizing energy consumption in real-time embedded systems. Autom. Control Comput. Sci. 2009;43:57–62. doi: 10.3103/S0146411609020011. [Cross Ref]

2. Li YP, Huang GH. Inexact minimax regret integer programming for long-term planning of municipal solid waste management - part A, methodology development. Environ. Eng. Sci. 2009;26:209–218. doi: 10.1089/ees.2007.0241.ptA. [Cross Ref]

3. Michelot C, Plastria F. An extended multifacility minimax location problem revisited. Ann. Oper. Res. 2002;111:167–179. doi: 10.1023/A:1020953703533. [Cross Ref]

4. Cai XQ, Teo KL, Yang XQ, Zhou XY. Portfolio optimization under a minimax rule. Manag. Sci. 2000;46:957–972. doi: 10.1287/mnsc.46.7.957.12039. [Cross Ref]

5. Khan MA. Second-order duality for nondifferentiable minimax fractional programming problems with generalized convexity. J. Inequal. Appl. 2013;2003 doi: 10.1186/1029-242X-2013-500. [Cross Ref]

6. Gaudioso M, Monaco MF. A bundle type approach to the unconstrained minimization of convex nonsmooth functions. Math. Program. 1982;23:216–226. doi: 10.1007/BF01583790. [Cross Ref]

7. Polak E, Mayne DQ, Higgins JE. Superlinearly convergent algorithm for min-max problems. J. Optim. Theory Appl. 1991;69:407–439. doi: 10.1007/BF00940683. [Cross Ref]

8. Gaudioso M, Giallombardo G, Miglionico G. An incremental method for solving convex finite min-max problems. Math. Oper. Res. 2006;31:173–187. doi: 10.1287/moor.1050.0175. [Cross Ref]

9. Jian JB, Tang CM, Tang F. A feasible descent bundle method for inequality constrained minimax problems. Sci. Sin., Math. 2015;45:2001–2024.

10. Xu S. Smoothing method for minimax problems. Comput. Optim. Appl. 2001;20:267–279. doi: 10.1023/A:1011211101714. [Cross Ref]

11. Polak E, Royset JO, Womersley RS. Algorithms with adaptive smoothing for finite minimax problems. J. Optim. Theory Appl. 2003;119:459–484. doi: 10.1023/B:JOTA.0000006685.60019.3e. [Cross Ref]

12. Polak E, Womersley RS, Yin HX. An algorithm based on active sets and smoothing for discretized semi-infinite minimax problems. J. Optim. Theory Appl. 2008;138:311–328. doi: 10.1007/s10957-008-9355-9. [Cross Ref]

13. Xiao Y, Yu B. A truncated aggregate smoothing Newton method for minimax problems. Appl. Math. Comput. 2010;216:1868–1879.

14. Zhou JL, Tits AL. An SQP algorithm for finely discretized continuous minimax problems and other minimax problems with many objective functions. SIAM J. Optim. 1996;6:461–487. doi: 10.1137/0806025. [Cross Ref]

15. Zhu ZB, Cai X, Jian JB. An improved SQP algorithm for solving minimax problems. Appl. Math. Lett. 2009;22:464–469. doi: 10.1016/j.aml.2008.06.017. [Cross Ref]

16. Jian JB, Zhang XL, Quan R, Ma Q. Generalized monotone line search SQP algorithmfor constrained minimax problems. Optimization. 2009;58:101–131. doi: 10.1080/02331930801951140. [Cross Ref]

17. Jian JB, Hu QJ, Tang CM. Superlinearly convergent norm-relaxed SQP method based on active set identification and new line search for constrained minimax problems. J. Optim. Theory Appl. 2014;163:859–883. doi: 10.1007/s10957-013-0503-5. [Cross Ref]

18. Jian JB, Chao MT. A sequential quadratically constrained quadratic programming method for unconstrained minimax problems. J. Math. Anal. Appl. 2010;362:34–45. doi: 10.1016/j.jmaa.2009.08.046. [Cross Ref]

19. Jian JB, Mo XD, Qiu LJ, Yang SM, Wang FS. Simple sequential quadratically constrained quadratic programming feasible algorithm with active identification sets for constrained minimax problems. J. Optim. Theory Appl. 2014;160:158–188. doi: 10.1007/s10957-013-0339-z. [Cross Ref]

20. Wang FS, Wang CL. An adaptive nonmonotone trust-region method with curvilinear search for minimax problem. Appl. Math. Comput. 2013;219:8033–8041.

21. Ye F, Liu HW, Zhou SS, Liu SY. A smoothing trust-region Newton-CG method for minimax problem. Appl. Math. Comput. 2008;199:581–589.

22. Obasanjo E, Tzallas-Regas G, Rustem B. An interior-point algorithm for nonlinear minimax problems. J. Optim. Theory Appl. 2010;144:291–318. doi: 10.1007/s10957-009-9599-z. [Cross Ref]

23. Rosen JB. The gradient projection method for nonlinear programming, part I. Linear constraints. J. Soc. Ind. Appl. Math. 1960;8:181–217. doi: 10.1137/0108011. [Cross Ref]

24. Du DZ, Wu F, Zhang XS. On Rosen’s gradient projection methods. Ann. Oper. Res. 1990;24:9–28. doi: 10.1007/BF02216813. [Cross Ref]

25. Jian JB. Fast Algorithms for Smooth Cconstrained Optimization - Theoretical Analysis and Numerical Experiments. Beijing: Science Press; 2010.

26. Ma GD, Jian JB. An *ε*-generalized gradient projection method for nonlinear minimax problems. Nonlinear Dyn. 2014;75:693–700. doi: 10.1007/s11071-013-1095-1. [Cross Ref]

27. Burke JV, More JJ. On the identification of active constraints. SIAM J. Numer. Anal. 1988;25:1197–1211. doi: 10.1137/0725068. [Cross Ref]

28. Facchinei F, Fischer A, Kanzow C. On the accurate identification of active constraints. SIAM J. Optim. 1998;9:14–32. doi: 10.1137/S1052623496305882. [Cross Ref]

29. Oberlin C, Wright SJ. Active set identification in nonlinear programming. SIAM J. Optim. 2006;17:577–605. doi: 10.1137/050626776. [Cross Ref]

30. Han DL, Jian JB, Li J. On the accurate identification of active set for constrained minimax problems. Nonlinear Anal. 2011;74:3022–3032. doi: 10.1016/j.na.2011.01.024. [Cross Ref]

31.
Karmitsa, N: Test problems for large-scale nonsmooth minimization, Reports of the Department of Mathematical Information Technology. Series B, Scientific computing, No. B, 4 (2007)

Articles from Springer Open Choice are provided here courtesy of **Springer**

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |