An Active-Set Fischer–Burmeister Trust-Region Algorithm to Solve a Nonlinear Bilevel Optimization Problem

Abstract

In this paper, the Fischer–Burmeister active-set trust-region (FBACTR) algorithm is introduced to solve the nonlinear bilevel programming problems. In FBACTR algorithm, a Karush–Kuhn–Tucker (KKT) condition is used with the Fischer–Burmeister function to transform a nonlinear bilevel programming (NBLP) problem into an equivalent smooth single objective nonlinear programming problem. To ensure global convergence for the FBACTR algorithm, an active-set strategy is used with a trust-region globalization strategy. The theory of global convergence for the FBACTR algorithm is presented. To clarify the effectiveness of the proposed FBACTR algorithm, applications of mathematical programs with equilibrium constraints are tested.

1. Introduction

The mathematical formulation for NBLP problem which we will consider it is

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u(v,w)\hfill \\ s.t.\hfill & g_u(v,w)\le 0,\hfill \\ \underset{w}{min}\hfill & f_l(v,w),\hfill \\ s.t.\hfill & g_l(v,w)\le 0,\hfill \end{array}$$

(1)

where $v\in {\Re }^{n_1}$ and $w\in {\Re }^{n_2}$. In our approach, the  functions $f_u:{\Re }^{n_1+n_2}\to \Re$, $f_l:{\Re }^{n_1+n_2}\to \Re$, $g_u:{\Re }^{n_1+n_2}\to {\Re }^{m_1}$, and $g_l:{\Re }^{n_1+n_2}\to {\Re }^{m_2}$ must have a twice continuously differentiable function at least.

The NBLP problem (1) is utilized so extensively in transaction network, resource allocation, finance budget, price control, etc., see [1,2,3,4]. The  NBLP problem (1) has two levels of optimization problems, upper and lower levels. A decision maker with the upper level objective function $f_u(v,w)$ takes the lead, and so he chooses the decision vector v. According to this, the decision maker with lower level objective function $f_l(v,w)$, chooses the decision vector w to optimize her objective, parameterized in v.

To obtain the solution of problem (1), number of different approaches have been offered, see (1), see [5,6,7,8,9]. In our method, we utilize one of these approaches to transforme NBLP problem (1) to a single level one by replacing the lower level optimization problem with its KKT conditions, see [10,11].

Utilizing KKT optimality conditions for the lower level problem, the NBLP problem (1) is reduced to the following single-objective optimization problem:

$$\begin{array}{cc}\underset{v,w}{min}\hfill & f_u(v,w)\hfill \\ s.t.\hfill & g_u(v,w)\le 0,\hfill \\ \hfill & {\nabla }_w{f}_l(v,w)+{\nabla }_w{g}_l(v,w)\lambda =0,\hfill \\ \hfill & g_l(v,w)\le 0,\hfill \\ \hfill & {\lambda }_j{g}_{l_j}(v,w)=0,j=1,\dots ,m_2,\hfill \\ \hfill & {\lambda }_j\ge 0,j=1,\dots ,m_2,\hfill \end{array}$$

(2)

where $\lambda \in {\Re }^{m_2}$ a multiplier vector which is associated with inequality constraint $g_l(v,w)$.

Problem (2) is non-differentiable and non-convex. Furthermore, the regularity assumption prerequisites to successfully handle smooth optimization problems are never satisfied. Following the smoothing method which is proposed by [2], we can introduce the FBACTR algorithm to solve the problem (2). Before introducing FBACTR algorithm, we need the following definition.

Definition 1.

A Fischer–Burmeister function is the function ${\Psi }(e,d):{\Re }^2\to \Re$ and it is defined by ${\Psi }(e,d)=e+d-\sqrt{e^2+d^2}$. A perturbed Fischer–Burmeister function is the function $\psi (e,d,\widehat{\epsilon }):{\Re }^3\to \Re$ and it is defined by $\psi (e,d,\widehat{\epsilon })=e+d-\sqrt{e^2+d^2+\widehat{\epsilon }}$.

The Fischer–Burmeister function has the property that ${\Psi }(e,d)=0$ if and only if $e\ge 0$, $d\ge 0$, and $ed=0$. It is non-differentiable at $e=d=0$. Its perturbed variant satisfies $\psi (e,d,\widehat{\epsilon })=0$ if and only if $e>0$, $d>0$, and $ed=\frac{\widehat{\epsilon }}{2}$ for $\widehat{\epsilon }>0$. This function is smooth with respect to e, d, for  $\widehat{\epsilon }>0$, and for more details see [12,13,14,15].

The next perturbed Fischer–Burmeister function is used to satisfy the asymptotic stability conditions, and allow the FBACTR algorithm to solve problem (2).

$$\psi (e,d,\widehat{\epsilon })=\sqrt{e^2+d^2+\widehat{\epsilon }}-e-d.$$

(3)

Using the perturbed Fischer–Burmeister function (3), problem (2) can be approximated by:

$$\begin{array}{cc}\underset{v,w}{min}\hfill & f_u(v,w)\hfill \\ s.t.\hfill & g_u(v,w)\le 0,\hfill \\ \hfill & {\nabla }_w{f}_l(v,w)+{\nabla }_w{g}_l(v,w)\lambda =0,\hfill \\ \hfill & \sqrt{g_{l_j}^2+{\lambda }_j^2+\widehat{\epsilon }}-{\lambda }_j+g_{l_j}=0,j=1,\dots ,m_2.\hfill \end{array}$$

(4)

The following notations are introduced to simplify our discussion. These notations are $n=n_1+n_2+m_2$, $x={(v,w,\lambda )}^T\in {\Re }^n$ and $c\left(x\right)=({\nabla }_w{f}_l(v,w)+{\nabla }_w{g}_l(v,w)\lambda ,$$\sqrt{g_{l_j}^2+{\lambda }_j^2+\widehat{\epsilon }}-{\lambda }_j+g_{l_j}{)}^T,j=1,\dots ,m_2$. Hence problem (4) can be reduced as follows:

$$\begin{array}{cc}\mathrm{minimize}& f_u\left(x\right)\hfill \\ \mathrm{subject}\mathrm{to}& g_u\left(x\right)\le 0,\hfill \\ & c\left(x\right)=0,\hfill \end{array}$$

(5)

where $f_u:{\Re }^n\to \Re$, $g_u:{\Re }^n\to {\Re }^{m_1}$, and $c:{\Re }^n\to {\Re }^{n_2+m_2}$.

A set of indices of binding or violated inequality constraints at x is defined by $I\left(x\right)=\{i:g_{u_i}\left(x\right)\ge 0\}$. A regular point is the point $x_{*}$ at which the vectors of the set $\{\nabla c_i\left(x_{*}\right),i=1,2,\dots ,n_2+m_2\}$⋃$\{\nabla g_{u_i}\left(x_{*}\right),i\in I\left(x_{*}\right)\}$ are linearly independent.

A regular point $x_{*}$ is KKT point of problem (5) if there exist Lagrange multiplier vectors ${\mu }_{*}\in {\Re }^{n_2+m_2}$ and ${\lambda }_{*}\in {\Re }^{m_1}$ such that the following KKT conditions hold:

$$\begin{array}{ccc}\hfill \nabla f_u\left(x_{*}\right)+\nabla c\left(x_{*}\right){\mu }_{*}+\nabla g_u\left(x_{*}\right){\lambda }_{*}& =& 0,\hfill \end{array}$$

(6)

$$\begin{array}{ccc}\hfill c\left(x_{*}\right)& =& 0,\hfill \end{array}$$

(7)

$$\begin{array}{ccc}\hfill g_u\left(x_{*}\right)& \le & 0,\hfill \end{array}$$

(8)

$$\begin{array}{ccc}\hfill {\left({\lambda }_{*}\right)}_i{g}_{u_i}\left(x_{*}\right)& =& 0,i=1,\dots ,m_1,\hfill \end{array}$$

(9)

$$\begin{array}{ccc}\hfill {\left({\lambda }_{*}\right)}_i& \ge & 0,i=1,\dots ,m_1.\hfill \end{array}$$

(10)

To solve the nonlinear single-objective constrained optimization problem (5), various approaches have been proposed; for more details, see [16,17,18,19,20,21,22].

An active-set strategy is utilized to reduce problem (5) to equality constrained optimization problem. The  idea beyond the active-set method is to identify at every iteration, the active inequality constraints and treat them as equalities and this allows to utilize the improved methods which are used to solve the equality constrained problems, see [21,23,24]. Most of the methods that are used to solve the equality constrained problems, may not converge if the starting point is far away from the stationary point, so it is called a local method.

To ensure a convergence to the solution from any starting point, a trust-region strategy which is strongly global convergence can be induced. It is very important strategy to solve a smooth optimization. It is more robust when it deals with rounding errors. It does not require the objective function of the model be convex. For more details see [11,21,22,23,24,25,26,27,28,29,30,31,32].

To treat the difficult of having infeasible trust-region subproblem in FBACTR algorithm, a reduced Hessian technique which is suggested by [33,34] and used by [22,24,35] is utilized.

Under five assumptions, a theory of global convergence for FBACTR algorithm is proved. Moreover, numerical experiments display that FBACTR algorithm performers effectively and efficiently in pursuance.

We shall use the following notation and terminology. We use $\parallel .\parallel$ to denote the Euclidean norm ${\parallel .\parallel }_2$. Subscript k refers to iteration indices. For example, $f_{u_k}\equiv f_u\left(x_k\right)$, $g_{u_k}\equiv g_u\left(x_k\right)$,$c_k\equiv c\left(x_k\right)$, $Y_k\equiv Y\left(x_k\right)$, $P_k\equiv P\left(x_k\right)$, ${\nabla }_x{\ell }_k\equiv {\nabla }_x\ell (x_k,{\mu }_k)$, and so on to denote the function value at a particular point.

The rest of the paper is organized as follows. Section 2 is devoted to the description of an active-set trust-region algorithm to solve problem (5) and summarized to FBACTR algorithm to solve NBLP problem (1) is introduced. In Section 3 the analysis of the theory of global convergence of the FBACTR algorithm is presented. Section 4 contains an implementation of the FBACTR algorithm and the results of test problems. Finally, some further remarks are given in Section 5.

2. Active-Set with Trust-Region Technique

A detailed description for active-set with the trust-region strategy to solve problem (5) and summarized to FBACTR algorithm to solve problem (1) are introduced in this section.

Based on the active-set method which is suggested by [36] and used with [21,22,23,24], we define a 0–1 diagonal matrix $P\left(x\right)\in {\Re }^{m_1\times m_1}$, whose diagonal entries are:

$$p_i\left(x\right)=\left\{\begin{array}{cc}1& if{g}_{u_i}\left(x\right)\ge 0,\\ 0& if{g}_{u_i}\left(x\right)<0.\end{array}\right.$$

(11)

Using the previous definition of the matrix $P\left(x\right)$, a smooth and simple function is utilized to replace problem (5) with the following simple problem

$$\begin{array}{cc}\mathrm{minimize}& f_u\left(x\right)+\frac{r}{2}{\parallel P\left(x\right)g_u\left(x\right)\parallel }^2\\ \mathrm{subject}\mathrm{to}& c\left(x\right)=0,\end{array}$$

(12)

where $r>0$ is a parameter, see [21,22,23]. The Lagrangian function associated with problem (12) is given by:

$$L(x,\mu ;r)=\ell (x,\mu )+\frac{r}{2}{\parallel P\left(x\right)g_u\left(x\right)\parallel }^2,$$

(13)

where

$$\ell (x,\mu )=f_u\left(x\right)+{\mu }^{T}c\left(x\right),$$

(14)

and $\mu \in {\Re }^{n_2+m_2}$ represents a Lagrange multiplier vector which is associated with the constraint $c\left(x\right)$. A KKT point $(x_{*},{\mu }_{*})$ for problem (12) is the point at which the following conditions are satisfied

$$\begin{array}{ccc}\hfill \nabla \ell (x_{*},{\mu }_{*})+r\nabla g_u\left(x_{*}\right)P\left(x_{*}\right)g_u\left(x_{*}\right)& =& 0,\hfill \end{array}$$

(15)

$$\begin{array}{ccc}\hfill h\left(x_{*}\right)& =& 0,\hfill \end{array}$$

(16)

where $\nabla \ell (x_{*},{\mu }_{*})=\nabla f_u\left(x_{*}\right)+\nabla c\left(x_{*}\right){\mu }_{*}$.

If the KKT point $(x_{*},{\mu }_{*})$ satisfies conditions (6)–(10), we notice that it is also satisfies conditions (15) and (16), but the converse is not necessarily true. So, we design FBACTR algorithm in a way that, if  $(x_{*},{\mu }_{*})$ satisfies conditions (15) and (16), then it is also satisfies KKT conditions (6)–(10).

Various approaches which were proposed to solve the equality constrained are local methods. By local method, we mean a method such that if the starting point is sufficiently close to a solution, then under some reasonable assumptions the method is guaranteed by theory to converge to the solution. There is no guarantee that the local method converges starting from the remote. Globalizing a local method means modifying the method in such a way that is guaranteed to converge from any starting point without sacrificing its fast local rate of convergence. To ensure convergence from the remote, the trust-region technique is utilized.

2.1. A Trust-Region Technique

To solve problem (12) and to convergence from remote with any starting point, the trust-region strategy is used. A naive trust-region quadratic subproblem associated with problem (12) is:

$$\begin{array}{cc}\mathrm{minimize}& q_k\left(s\right)={\ell }_k+{\nabla }_x{\ell }_k^{T}s+\frac{1}{2}{s}^T{H}_{k}s+\frac{r}{2}\parallel P_k{(g_{u_k}+\nabla g_{u_k})}^{T}s{)\parallel }^2\\ \mathrm{subject}\mathrm{to}& c_k+\nabla c_k^{T}s=0,\\ & \parallel s\parallel \le {\delta }_k,\end{array}$$

(17)

where $0<{\delta }_k$ represents the trust-region radius and $H_k$ is the Hessian matrix of the Lagrangian function (14) or an approximation to it.

Subproblem (17) may be infeasible because there may be no intersecting points between hyperplane of the linearized constraints $c\left(x\right)+\nabla c{\left(x\right)}^{T}s=0$ and the constraint $\parallel s\parallel \le {\delta }_k$. Even if they intersect, there is no guarantee that this will keep true if ${\delta }_k$ is reduced, see [37]. To overcome this problem, a reduced Hessian technique which was suggested by [33,34] and used by [22,23,35] is used. In this technique, to obtain the trial step $s_k$, it is decomposed into two orthogonal components: the tangential component $s_k^t$ to improve optimality and the normal component $s_k^n$ to improve feasibility. To evaluate each of $s_k^n$ and $s_k^t$, two unconstrained trust-region subproblems are solved.

• To obtain the normal component ${\mathit{s}}^{\mathit{n}}$

To evaluate the normal component $s_k^n$, the following trust-region subproblem must be solved:

$$\begin{array}{cc}\mathrm{minimize}& \frac{1}{2}{\parallel c_k+\nabla c_k^T{s}^n\parallel }^2\\ \mathrm{subject}\mathrm{to}& \parallel s^n\parallel \le \zeta {\delta }_k,\end{array}$$

(18)

for some $\zeta \in (0,1)$.

Any method can be used to solve subproblem (18), as long as a fraction of the normal predicted decrease obtained by the Cauchy step $s_k^{ncp}$ is less than or equal to the normal predicted decrease obtained by $s_k^n$. That is, the following condition must be held:

$$\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k^n{\parallel }^2\ge {\vartheta }_1\{\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k^{ncp}{\parallel }^2\},$$

(19)

for some ${\vartheta }_1\in (0,1]$. The normal Cauchy step $s_k^{ncp}$ is given by:

$$s_k^{ncp}=-{\tau }_k^{ncp}\nabla c_k{c}_k,$$

(20)

where the parameter ${\tau }_k^{ncp}$ is given by:

$${\tau }_k^{ncp}=\left\{\begin{array}{cc}\frac{\parallel \nabla c_k{c}_k{\parallel }^2}{\parallel {(\nabla c_k)}^T\nabla c_k{c}_k{\parallel }^2}& if\frac{\parallel \nabla c_k{c}_k{\parallel }^3}{\parallel \nabla c_k^T\nabla c_k{c}_k{)\parallel }^2}\le {\delta }_k\\ \\ & \mathrm{and}\parallel \nabla c_k^T\nabla c_k{c}_k)\parallel >0,\\ \\ \frac{{\delta }_k}{\parallel \nabla c_k{c}_k\parallel }& \mathrm{otherwise}.\end{array}\right.$$

(21)

A dogleg method is used to solve subproblem (18). It is very cheap if the Hessian is indefinite. The dogleg algorithm approximates the solution curve to subproblem (18) by piecewise linear function connecting the Newton point to the Cauchy point. For more details, see [35].

Once $s_k^n$ is estimated, we will compute $s_k^t=Y_k{\overline{s}}_k^t$. A matrix $Y_k$ is the matrix whose columns form a basis for the null space of ${(\nabla c_k)}^T$.

• To obtain the tangential component ${\mathit{s}}_{\mathit{k}}^{\mathit{t}}$.

To evaluate the tangential component $s_k^t$, the following subproblem is solved by using the dogleg method

$$\begin{array}{cc}\mathrm{minimize}& {(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{s}}^t+\frac{1}{2}{\overline{s}}^{t^T}{Y}_k^T{B}_k{Y}_k{\overline{s}}^t\\ \mathrm{subject}\mathrm{to}& \parallel Y_k{\overline{s}}^t\parallel \le {\mathsf{\Delta }}_k,\end{array}$$

(22)

where $\nabla q_k\left(s_k^n\right)={\nabla }_x{\ell }_k+B_k{s}_k^n+r_k\nabla g_{u_k}{P}_k{g}_{u_k}$, $B_k=H_k+r_k\nabla g_{u_k}{P}_k\nabla g_{u_k}^T$, and ${\mathsf{\Delta }}_k=\sqrt{{\delta }_k^2-{\parallel s_k^n\parallel }^2}$.

Since the dogleg method is used to solve the above subproblem, then a fraction of the tangential predicted decrease obtained by a tangential Cauchy step ${\overline{s}}_k^{tcp}$ is less than or equal to the tangential predicted decrease which is obtained by tangential step ${\overline{s}}_k^t$. That is, the following conditions hold

$$q_k\left(s_k^n\right)-q_k(s_k^n+Y_k{\overline{s}}_k^t)\ge {\vartheta }_2[q_k\left(s_k^n\right)-q_k(s_k^n+Y_k{\overline{s}}_k^{tcp})],$$

(23)

for some ${\vartheta }_2\in (0,1]$. The tangential Cauchy step $s_k^{tcp}$ is defined as follows

$${\overline{s}}_k^{tcp}=-{\tau }_k^{tcp}{Y}_k^T\nabla q_k\left(s_k^n\right),$$

(24)

where the parameter ${\tau }_k^{tcp}$ is given by

$${\tau }_k^{tcp}=\left\{\begin{array}{cc}\frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right){\parallel }^2}{{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)}& if\frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right){\parallel }^3}{{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)}\le {\mathsf{\Delta }}_k\\ \\ & \mathrm{and}{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)>0,\\ \\ \frac{{\mathsf{\Delta }}_k}{\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel }& \mathrm{otherwise},\end{array}\right.$$

(25)

such that ${\overline{B}}_k=Y_k^T{B}_k{Y}_k$.

To be decided whether the step $s_k=s_k^n+s_k^t$ will be accepted or not, a merit function is needed to tie the objective function with the constraints in such a way that progress in the merit function means progress in solving the problem. The following augmented Lagrange function is used in FBACTR algorithm as a merit function,

$${\Phi }(x,\mu ;r;\sigma )=\ell (x,\mu )+\frac{r}{2}\parallel P\left(x\right)g_u{\left(x\right)\parallel }^2+\sigma {\parallel c\left(x\right)\parallel }^2,$$

(26)

where $\sigma >0$ is a penalty parameter.

To test whether the point $(x_k+s_k,{\mu }_{k+1})$ will be taken in the next iterate, an actual reduction and a predicted reduction are defined.

The actual reduction $Are{d}_k$ in the merit function in moving from $(x_k,{\mu }_k)$ to $(x_k+s_k,{\mu }_{k+1})$ is defined as follows:

$$Are{d}_k={\Phi }(x_k,{\mu }_k;r_k;{\sigma }_k)-{\Phi }(x_k+d_k,{\mu }_{k+1};r_k;{\sigma }_k).$$

$Are{d}_k$ can also be written as follows:

$$Are{d}_k=\ell (x_k,{\mu }_k)-\ell (x_{k+1},{\mu }_k)-\mathsf{\Delta }{\mu }_k^T{c}_{k+1}+\frac{r_k}{2}[\parallel P_k{g}_u\left(x_k\right){\parallel }^2-\parallel P_{k+1}{g}_{u_{k+1}}{\parallel }^2]+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_{k+1}{\parallel }^2],$$

(27)

where $\mathsf{\Delta }{\mu }_k=({\mu }_{k+1}-{\mu }_k)$.

The predicted reduction in the merit function is defined to be:

$$\begin{array}{ccc}\hfill Pre{d}_k& =& -{({\nabla }_x\ell (x_k,{\mu }_k))}^T{s}_k-\frac{1}{2}{s}_k^T{H}_k{s}_k-\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)+\frac{r_k}{2}[\parallel P_k{g}_{u_k}{\parallel }^2-\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{s}_k){\parallel }^2]\hfill \\ & & +{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2].\hfill \end{array}$$

(28)

$Pre{d}_k$ can be written as:

$$\begin{array}{ccc}\hfill Pre{d}_k& =& q_k\left(0\right)-q_k\left(s_k\right)-\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2].\hfill \end{array}$$

(29)

• To update the penalty parameter ${\mathbf{\sigma }}_{\mathbf{k}}$

To update the penalty parameter ${\sigma }_k$ to ensure that $Pre{d}_k\ge 0$, the following schemeis used (see Algorithm 1):

Algorithm 1 To update the penalty parameter ${\sigma }_k$

If $$\hspace{1em}\hspace{1em}\hspace{1em}Pre{d}_k\le \frac{{\sigma }_k}{2}[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{\mu }_k{s}_k{\parallel }^2],$$ (30) then, set $$\hspace{1em}\hspace{1em}\hspace{1em}{\sigma }_k=\frac{2[q_k\left(s_k\right)-q_k\left(0\right)+\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)]}{\parallel c_k{\parallel }^2-{\parallel c_k+\nabla c_k^T{s}_k\parallel }^2}+{\beta }_0,$$ (31) where${\beta }_0>0$ is a small fixed constant. Else, set $$\hspace{1em}\hspace{1em}\hspace{1em}{\sigma }_{k+1}=max({\sigma }_k,r_k^2).$$ (32) End if.

For more details, see [22].

• To test the step ${\mathit{s}}_{\mathit{k}}$ and update ${\mathbf{\delta }}_{\mathit{k}}$

The framework to test the step $s_k$ and update ${\delta }_k$ is clarified in the Algorithm 2.

Algorithm 2 (To test the step $s_k$ and update ${\delta }_k$)

Choose$0<{\alpha }_1<{\alpha }_2<1$, $0<{\tau }_1<1<{\tau }_2$, and ${\delta }_{min}\le {\delta }_0\le {\delta }_{max}$.

While$\frac{Are{d}_k}{Pre{d}_k}\in (0,{\alpha }_1)$ or $Pre{d}_k\le 0$.

Set${\delta }_k={\tau }_1\parallel s_k\parallel$.

Evaluate a new trial step$s_k$.

End while.

If$\frac{Are{d}_k}{Pre{d}_k}\in [{\alpha }_1,{\alpha }_2)$.

Set$x_{k+1}=x_k+s_k$ and ${\delta }_{k+1}=max({\delta }_k,{\delta }_{min})$.

End if. If$\frac{Are{d}_k}{Pre{d}_k}\in [{\alpha }_2,1]$.

Set$x_{k+1}=x_k+s_k$ and ${\delta }_{k+1}=min\{{\delta }_{max},max\{{\delta }_{min},{\tau }_2{\delta }_k\}\}$.

End if.

• To update the positive parameter ${\mathbf{r}}_{\mathbf{k}}$

To update the positive parameter $r_k$, we use the following scheme (see Algorithm 3)

Algorithm 3 To update the positive parameter $r_k$

If $$\hspace{1em}\hspace{1em}\hspace{1em}\frac{1}{2}[q_k\left(s_k^n\right)-q_k\left(s_k\right)]\le \parallel \nabla g_u\left(x_k\right)P\left(x_k\right)g_u\left(x_k\right)\parallel min\{\parallel \nabla g_u\left(x_k\right)P\left(x_k\right)g_u\left(x_k\right)\parallel ,{\delta }_k\},$$ (33)

Set$r_{k+1}=r_k$.

Else, set$r_{k+1}=2r_k$.

End if.

For more details see, [25].

Finally, the algorithm stopped if the termination criteria $\parallel Y_k^T{\nabla }_x{\ell }_k\parallel +\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel +\parallel c_k\parallel \le {\epsilon }_1$ or $\parallel s_k\parallel \le {\epsilon }_2$, for some ${\epsilon }_1,{\epsilon }_2>0$ is satisfied.

• A trust-region algorithm

The framework of the trust-region algorithm to solve subproblem (17) are summarized as follows (see Algorithm 4).

Algorithm 4 Trust-region algorithm

Step 0. (Initialization)   Starting with $x_0$. Evaluate ${\mu }_0$ and $P_0$. Set $r_0=1$, ${\sigma }_0=1$, and ${\beta }_0=0.1$.   Choose ${\epsilon }_1$, ${\epsilon }_2$, ${\tau }_1$, ${\tau }_2$, ${\alpha }_1$, and ${\alpha }_2$ such that $0<{\epsilon }_1$, $0<{\epsilon }_2$, $0<{\tau }_1<1<{\tau }_2$,   and $0<{\alpha }_1<{\alpha }_2<1$.   Choose ${\delta }_{min}$, ${\delta }_{max}$, and ${\delta }_0$ such that ${\delta }_{min}\le {\delta }_0\le {\delta }_{max}$. Set $k=0$. Step 1. If $\parallel Y_k^T{\nabla }_x{\ell }_k\parallel +\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel +\parallel c_k\parallel \le {\epsilon }_1$, then stop. Step 2. (How to compute $s_k$)   (a) Evaluate the normal component $s_k^n$ by solving subproblem (18).   (b) Evaluate the tangential component ${\overline{s}}_k^t$ by solving subproblem (22).   (c) Set $s_k=s_k^n+Y_k{\overline{s}}_k^t$. Step 3. If $\parallel s_k\parallel \le {\epsilon }_2$, then stop. Step 4. Set $x_{k+1}=x_k+s_k$. Step 5. Compute $P_{k+1}$ given by (11). Step 6. Evaluate ${\mu }_{k+1}$ by solving the following subproblem $$minimize\parallel \nabla f_{u_{k+1}}+\nabla c_{k+1}\mu +r_k\nabla g_{u_{k+1}}{P}_{k+1}{g}_{u_{k+1}}{\parallel }^2.$$ (34) Step 7. To update the penalty parameter ${\sigma }_k$, using Algorithm 1. Step 8. To test the step $s_k$ and update the radius${\delta }_k$, using Algorithm 2. Step 9. To update the positive parameter $r_k$, using Algorithm 3. Step 10. Set $k=k+1$ and go to Step 1.

The main steps for solving the NBLP problem (1) are clarified in the following algorithm.

2.2. Fischer–Burmeister Active-Set Trust-Region Algorithm

The framework to solve NBLP problem (1) is summarized in the Algorithm 5.

Algorithm 5 FBACTR algorithm

Step 1. Use KKT optimality conditions for the lower level of problem (1) and convert it to a single objective constrained optimization problem (2). Step 2. Using Fischer–Burmeister function (3) with $ϵ=0.001$ to obtain the smooth problem (4). Step 3. Summarize problem (4) to the form of nonlinear optimization problem (5). Step 4. Use the active set strategy to reduce problem (5) to problem (12). Step 5. Use trust-region Algorithm 4 to solve problem (12) and obtained approximate solution for problem (5) which is approximate solution for problem (1).

The next section is dedicated to the global convergence analysis for the active-set with the trust-region algorithm.

3. Global Convergence Analysis

Let $\left\{(x_k,{\mu }_k)\right\}$ be the sequence of points generated by FBACTR Algorithm 5. Let $\mathsf{\Omega }\subseteq {\Re }^n$ be a convex set which is contained all iterates $x_k\in {\Re }^n$ and $x_k+s_k\in {\Re }^n$.

Standard assumptions which are needed on the set $\mathsf{\Omega }$ to demonstrate global convergence theory for FBACTR Algorithm 5 are stated in the following section.

3.1. A Standard Assumptions

The next standard assumptions are required to demonstrate the global convergence theory for the FBACTR Algorithm 5.

• [${\mathit{SA}}_{\mathbf{1}}$.] Functions $f_u:{\Re }^n\to \Re$, $g_u:{\Re }^n\to {\Re }_1^m$, $f_l:{\Re }^n\to {\Re }^{n_2}$, and $g_l:{\Re }^n\to {\Re }^{m_2}$ are twice continuously differentiable functions for all $x\in \mathsf{\Omega }$.
• [${\mathit{SA}}_{\mathbf{2}}$.] The sequence of the Lagrange multiplier vectors $\left\{{\mu }_k\right\}$ is bounded.
• [${\mathit{SA}}_{\mathbf{3}}$.] All of $c\left(x\right)$, $\nabla c\left(x\right)$, ${\nabla }^2{c}_i\left(x\right)$ for $i=1,2,\dots ,n_2+m_2$, $g_u\left(x\right)$, $\nabla g_u\left(x\right)$, ${\nabla }^2{g}_{u_i}\left(x\right)$ for $i=1,2,\dots ,m_1$, and ${(\nabla c{\left(x\right)}^T\nabla c\left(x\right))}^{-1}$ are uniformly bounded on $\mathsf{\Omega }$.
• [${\mathit{SA}}_{\mathbf{4}}$.] The matrix $\nabla c\left(x\right)$ has full column rank.
• [${\mathit{SA}}_{\mathbf{5}}$.] The sequence of Hessian matrices $\left\{H_k\right\}$ is bounded.

Some fundamental lemmas which are needed in the proof of the main theorem introduced in the following section.

3.2. Main Lemmas

Some basic lemmas which are required to demonstrate the main theorems are presented in this section.

Lemma 1.

Under standard assumption $S{A}_1$–$S{A}_5$ and at any iteration k, there exists a positive constant $K_1$ such that:

$$\parallel s_k^n\parallel \le K_1\parallel c_k\parallel .$$

(35)

Proof. 

Since the normal component $s_k^n$ is normal to the tangent space, then we have:

$$\begin{array}{ccc}\hfill \parallel s_k^n\parallel & =& \parallel \nabla c_k{(\nabla c_k^T\nabla c_k)}^{-1}\nabla c_k^T{s}_k\parallel \hfill \\ & =& \parallel \nabla c_k{(\nabla c_k^T\nabla c_k)}^{-1}[c_k+\nabla c_k^T{s}_k-c_k]\parallel \hfill \\ & \le & \parallel \nabla c_k{(\nabla c_k^T\nabla c_k)}^{-1}\parallel [\parallel c_k+\nabla c_k^T{s}_k\parallel +\parallel c_k\parallel ]\hfill \\ & \le & \parallel \nabla c_k{(\nabla c_k^T\nabla c_k)}^{-1}\parallel \parallel c_k\parallel ,\hfill \end{array}$$

where $\parallel c_k+\nabla c_k^T{s}_k\parallel \le \parallel c_k\parallel$. Using standard assumptions $S{A}_1$–$S{A}_5$, we have the desired result. □

Lemma 2.

Under standard assumptions $S{A}_1$ and $S{A}_3$, the functions $P\left(x\right)g_u\left(x\right)$ are Lipschitz continuous in Ω.

Proof. 

See Lemma (4.1) in [36]. □

From Lemma 2, we conclude that $g_u{\left(x\right)}^{T}P\left(x\right)g_u\left(x\right)$ is differentiable and $\nabla g_u\left(x\right)P\left(x\right)g_u\left(x\right)$ is Lipschitz continuous in $\mathsf{\Omega }$.

Lemma 3.

At any iteration k, let $A\left(x_k\right)\in {\Re }^{\left(m_1\right)\times \left(m_1\right)}$ be a diagonal matrix whose diagonal entries are:

$${\left(a_k\right)}_i=\left\{\begin{array}{cc}1& if{\left(g_{u_k}\right)}_i<0 and {\left(g_{u_{k+1}}\right)}_i\ge 0,\\ -1& if{\left(g_{u_k}\right)}_i\ge 0 and {\left(g_{u_{k+1}}\right)}_i<0,\\ 0& otherwise,\end{array}\right.$$

(36)

where $i=1,2,\dots ,m_1$. Then

$$P_{k+1}=P_k+A_k.$$

(37)

Proof. 

See Lemma (6.2) in [21]. □

Lemma 4.

Under standard assumptions $S{A}_1$ and $S{A}_3$, there exists a positive constant $K_2$ such that

$$\parallel A_k{g}_{u_k}\parallel \le K_2\parallel s_k\parallel .$$

(38)

Proof. 

See Lemma (6.3) in [21]. □

Lemma 5.

Under standard assumptions $S{A}_1$–$S{A}_5$, there exists a positive constant $K_3$ such that:

$$\mid Are{d}_k-Pre{d}_k\mid \le K_3{\sigma }_k{\parallel s_k\parallel }^2.$$

(39)

Proof. 

From (37) and (27) we have:

$$Are{d}_k=\ell (x_k,{\mu }_k)-\ell (x_{k+1},{\mu }_k)-\mathsf{\Delta }{\mu }_k^T{c}_{k+1}+\frac{r_k}{2}[g_{u_k}^T{P}_k{g}_{u_k}-g_{u_{k+1}}^T(P_k+A_k)g_{u_{k+1}}]+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_{k+1}{\parallel }^2].$$

(40)

From (40), (28), and using Cauchy–Schwarz inequality, we have:

$$\begin{array}{ccc}\hfill \mid Are{d}_k-Pre{d}_k\mid & \le & \mid \ell (x_k,{\mu }_k)+{\nabla }_x\ell {(x_k,{\mu }_k)}^T{s}_k-\ell (x_{k+1},{\mu }_k)\mid +\mid \mathsf{\Delta }{\mu }_k^T[c_k+\nabla c_k^T{s}_k-c_{k+1}]\mid \hfill \\ & & +\frac{r_k}{2}\mid \parallel P_k(g_{u_k}+\nabla g_{u_k}^T{s}_k){\parallel }^2-g_{u_{k+1}}^T(P_k+A_k)g_{u_{k+1}}\mid +{\sigma }_k\mid \parallel c_k+\nabla c_k^T{s}_k{\parallel }^2-{\parallel c_{k+1}\parallel }^2\mid .\hfill \end{array}$$

Hence,

$$\begin{array}{ccc}\hfill |Are{d}_k-Pre{d}_k|& \le & \frac{1}{2}\mid s_k^T(H_k-{\nabla }^2\ell (x_k+{\xi }_1{s}_k,{\mu }_k))s_k\mid +\frac{1}{2}\mid s_k^T\left[{\nabla }^{2}c(x_k+{\xi }_2{s}_k)\mathsf{\Delta }{\mu }_k\right]s_k\mid \hfill \\ & & +\frac{r_k}{2}\mid s_k^T[\nabla g_{u_k}{P}_k\nabla g_{u_k}^T-\nabla g_u(x_k+{\xi }_4{s}_k)P_k\nabla g_u{(x_k+{\xi }_4{s}_k)}^T]s_k\mid \hfill \\ & & +\frac{r_k}{2}\mid s_k^T{\nabla }^2{g}_u(x_k+{\xi }_4{s}_k)P_k{g}_u(x_k+{\xi }_4{s}_k)s_k\mid +\frac{r_k}{2}{\parallel A_k[g_{u_k}+\nabla g_u{(x_k+{\xi }_5{s}_k)}^T{s}_k]\parallel }^2\hfill \\ & & +{\sigma }_k\mid s_k^T[\nabla c_k\nabla c_k^T-\nabla c(x_k+{\xi }_6{s}_k)\nabla c{(x_k+{\xi }_6{s}_k)}^T]s_k\mid \hfill \\ & & +{\sigma }_k\mid s_k^T{\nabla }^{2}c(x_k+{\xi }_6{s}_k)c(x_k+{\xi }_6{s}_k)s_k\mid ,\hfill \end{array}$$

for some ${\xi }_1$, ${\xi }_2$, ${\xi }_3$, ${\xi }_4$, ${\xi }_5$, and ${\xi }_6\in (0,1)$. Using standard assumptions $S{A}_1$–$S{A}_5$, ${\sigma }_k\ge r_k$, ${\sigma }_k\ge 1$, and inequality (38), we have:

$$\mid Are{d}_k-Pre{d}_k\mid \le {\kappa }_1\parallel s_k{\parallel }^2+{\kappa }_2{\sigma }_k\parallel s_k{\parallel }^2\parallel c_k\parallel +{\kappa }_3{\sigma }_k{\parallel s_k\parallel }^3,$$

(41)

where ${\kappa }_1>0$, ${\kappa }_2>0$, and ${\kappa }_3>0$ are constants and independent of the iteration k. From inequality (41), ${\sigma }_k\ge 1$, $\parallel s_k\parallel$, and $\parallel c_k\parallel$ are uniformly bounded, we obtain the desired result. □

Lemma 6.

Under standard assumptions $S{A}_1$–$S{A}_5$, there exists a positive constant $K_4$ such that:

$$\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k^n{\parallel }^2\ge K_4\parallel c_k\parallel min\{{\delta }_k,\parallel c_k\parallel \}.$$

(42)

Proof. 

We consider two cases:

Firstly, from (20), if $s_k^{ncp}=-\frac{{\delta }_k}{\parallel \nabla c_k{c}_k\parallel }(\nabla c_k{c}_k)$ and ${\delta }_k\parallel \nabla c_k^T\nabla c_k{c}_k{\parallel }^2\le {\parallel \nabla c_k{c}_k\parallel }^3$, then we have:

$$\begin{array}{ccc}\hfill \parallel c_k{\parallel }^2-{\parallel c_k+\nabla c_k^T{s}_k^{ncp}\parallel }^2& =& -2{(\nabla c_k{c}_k)}^T{s}_k^{ncp}-s_k^{{ncp}^T}\nabla c_k\nabla c_k^T{s}_k^{ncp}\hfill \\ & =& 2{\delta }_k\parallel \nabla c_k{c}_k\parallel -\frac{{\delta }_k^2{\parallel \nabla c_k^T\nabla c_k{c}_k\parallel }^2}{\parallel \nabla c_k{c}_k{\parallel }^2}\hfill \\ & \ge & 2{\delta }_k\parallel \nabla c_k{c}_k\parallel -{\delta }_k\parallel \nabla c_k{c}_k\parallel \hfill \\ & \ge & {\delta }_k\parallel \nabla c_k{c}_k\parallel .\hfill \end{array}$$

(43)

Secondly, from (20), if $s_k^{ncp}=-\frac{\parallel \nabla c_k{c}_k{\parallel }^2}{\parallel \nabla c_k^T\nabla c_k{c}_k{\parallel }^2}(\nabla c_k{c}_k)$ and ${\delta }_k\parallel \nabla c_k^T\nabla c_k{c}_k{\parallel }^2\ge {\parallel \nabla c_k{c}_k\parallel }^3$, then we have:

$$\begin{array}{ccc}\hfill \parallel c_k{\parallel }^2-{\parallel c_k+\nabla c_k^T{s}_k^{ncp}\parallel }^2& =& -2{(\nabla c_k{c}_k)}^T{s}_k^{ncp}-s_k^{{ncp}^T}\nabla c_k\nabla c_k^T{s}_k^{ncp}\hfill \\ & =& \frac{2\parallel \nabla c_k{c}_k{\parallel }^4}{\parallel \nabla c_k^T\nabla c_k{c}_k{\parallel }^2}-\frac{\parallel \nabla c_k{c}_k{\parallel }^4}{\parallel \nabla c_k^T\nabla c_k{c}_k{\parallel }^2}\hfill \\ & =& \frac{\parallel \nabla c_k{c}_k{\parallel }^4}{\parallel \nabla c_k^T\nabla c_k{c}_k{\parallel }^2}\hfill \\ & \ge & \frac{\parallel \nabla c_k{c}_k{\parallel }^2}{\parallel \nabla c_k^T\nabla c_k{c}_k{\parallel }^2}.\hfill \end{array}$$

(44)

Using standard assumption $S{A}_3$, we have $\parallel \nabla c_k{c}_k\parallel \ge \frac{\parallel c_k\parallel }{\parallel {(\nabla c_k^T\nabla c_k)}^{-1}\nabla c_k\parallel }$. From inequalities (19), (43), (44), and using standard assumption $S{A}_2$, we obtain the desired result.

From Algorithm 1 and Lemma 6, we have, for all k:

$$Pre{d}_k\ge \frac{{\sigma }_k}{2}{K}_4\parallel c_k\parallel min\{{\delta }_k,\parallel c_k\parallel \}.$$

(45)

□

Lemma 7.

Under standard assumptions $S{A}_1$–$S{A}_5$, there exists a constant $K_5>0$, such that:

$$\begin{array}{c}\hfill q_k\left(s_k^n\right)-q_k(s_k^n+Y_k{\overline{s}}_k^t)\ge \frac{1}{2}{K}_5\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel min\{{\mathsf{\Delta }}_k,\frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel }{\parallel {\overline{B}}_k\parallel }\},\end{array}$$

(46)

where ${\overline{B}}_k=Y_k^T{B}_k{Y}_k$.

Proof. 

We consider two cases:

Firstly, from (24), if ${\overline{s}}_k^{tcp}=-\frac{{\mathsf{\Delta }}_k}{\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel }{Y}_k^T\nabla q_k\left(s_k^n\right)$ and ${\mathsf{\Delta }}_k{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)\le {\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel }^3$, then we have:

$$\begin{array}{ccc}\hfill q_k\left(s_k^n\right)-q_k(s_k^n+Y_k{\overline{s}}_k^{tcp})& =& -{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{s}}_k^{tcp}-\frac{1}{2}{\overline{s}}_k^{{tcp}^T}{\overline{B}}_k{\overline{s}}_k^{tcp}\hfill \\ & =& {\mathsf{\Delta }}_k\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel \hfill \\ & & -\frac{{\mathsf{\Delta }}_k^2}{2\parallel Y_k^T\nabla q_k\left(s_k^n\right){\parallel }^2}[{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)]\hfill \\ & \ge & {\mathsf{\Delta }}_k\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel -\frac{1}{2}{\mathsf{\Delta }}_k\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel \hfill \\ & \ge & \frac{1}{2}{\mathsf{\Delta }}_k\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel .\hfill \end{array}$$

(47)

Secondly, from (24), if ${\overline{s}}_k^{tcp}=-\frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right){\parallel }^2}{Y_k^T\nabla q_k\left(s_k^n\right){)}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)}{Y}_k^T\nabla q_k\left(s_k^n\right)$ and ${\mathsf{\Delta }}_k{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)\ge {\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel }^3$, then we have:

$$\begin{array}{ccc}\hfill q_k\left(s_k^n\right)-q_k(s_k^n+Y_k{\overline{s}}_k^{tcp})& =& -{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{s}}_k^{tcp}-\frac{1}{2}{\overline{s}}_k^{{tcp}^T}{\overline{B}}_k{\overline{s}}_k^{tcp}\hfill \\ & =& \frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right){\parallel }^4}{{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)}\hfill \\ & & -\frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right){\parallel }^4}{2{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)}\hfill \\ & =& \frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right){\parallel }^4}{2{(Y_k^T\nabla q_k\left(s_k^n\right))}^T{\overline{B}}_k{Y}_k^T\nabla q_k\left(s_k^n\right)}\hfill \\ & \ge & \frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right){\parallel }^2}{2\parallel {\overline{B}}_k\parallel }.\hfill \end{array}$$

(48)

□

From inequalities (23), (47), (48), and using standard assumptions $S{A}_1$–$S{A}_5$, we obtain the desired result.

The next lemma shows that FBACTR algorithm cannot be looped infinitely without finding an acceptable step.

Lemma 8.

Under standard assumptions $S{A}_1$–$S{A}_5$, if there exists $\epsilon >0$ such that $\parallel c_k\parallel \ge \epsilon$, then $\frac{Are{d}_{k^j}}{Pre{d}_{k^j}}\ge {\alpha }_1$ for some finite j.

Proof. 

Using (39), (45), and from $\parallel c_k\parallel \ge \epsilon$, we have:

$$\left|\frac{Are{d}_k}{Pre{d}_k}-1\right|=\frac{\mid Are{d}_k-Pre{d}_k\mid }{Pre{d}_k}\le \frac{2K_3{\delta }_k^2}{K_4\epsilon min\{\epsilon ,{\delta }_k\}}.$$

${\delta }_{k^j}$ becomes small as $s_{k^j}$ gets rejected and eventually we will have:

$$\left|\frac{Are{d}_{k^j}}{Pre{d}_{k^j}}-1\right|\le \frac{2K_3{\delta }_{k^j}}{K_4\epsilon }.$$

Then, the acceptance rule will be met for finite j. This completes the proof. □

Lemma 9.

Under standard assumptions $S{A}_1$–$S{A}_5$ and if jth trial step of iteration k satisfies

$$\parallel s_{k^j}\parallel \le min\{\frac{(1-{\alpha }_1)K_4}{4K_3},1\}\parallel c_k\parallel ,$$

(49)

then it must be accepted.

Proof. 

This lemma is proved by contradiction. In case of assuming that inequality (49) holds, the trial step $s_{k^j}$ is rejected, by using inequalities (39), (45), and (49), then:

$$(1-{\alpha }_1)<\frac{\mid Are{d}_{k^j}-Pre{d}_{k^j}\mid }{Pre{d}_{k^j}}<\frac{2K_3{\parallel s_{k^j}\parallel }^2}{K_4\parallel c_k\parallel \parallel s_{k^j}\parallel }\le \frac{(1-{\alpha }_1)}{2}.$$

This contradiction and therefore the lemma is proved.

□

Lemma 10.

Under standard assumptions $S{A}_1$–$S{A}_5$, there exists ${\delta }_{k^j}$ satisfies:

$${\delta }_{k^j}\ge min\{\frac{{\delta }_{min}}{{\beta }_1},\frac{{\tau }_1(1-{\alpha }_1)K_4}{4K_3},{\tau }_1\}\parallel c_k\parallel ,$$

(50)

for all trial steps j of any iteration k where ${\beta }_1$ is a positive constant independent of k or j.

Proof. 

At any trial iterate $k^j$ of any iteration k, we consider two cases:

Firstly, if $j=1$, then the step is accepted. That is ${\delta }_k^1\ge {\delta }_{min}$ and take ${\beta }_1={sup}_{x\in \mathsf{\Omega }}\parallel c_k\parallel$, we have

$${\delta }_k\ge {\delta }_{min}\ge \frac{{\delta }_{min}}{{\beta }_1}\parallel c_k\parallel .$$

(51)

Secondly, if $j>1$, then there is at least one trial step which is rejected. From Lemma 9, we have

$$\parallel s_{k^i}\parallel >min\{\frac{(1-{\alpha }_1)K_4}{4K_3},1\}\parallel c_k\parallel ,$$

for all trial steps $i=1,2,\dots j-1$ which are rejected. Since $s_{k^i}$ is a trial step which is rejected, then from the previous inequality and Algorithm 2, we have:

$${\delta }_{k^j}={\tau }_1\parallel s_{k^{j-1}}\parallel >{\tau }_{1}min\{\frac{(1-{\alpha }_1)K_4}{4K_3},1\}\parallel c_k\parallel .$$

From inequality (51) and the above inequality, we obtain the desired result.

The next lemma obviously shows that as long as $\parallel c_k\parallel$ is bounded away from zero, the radius of the trust-region is bounded away from zero. □

Lemma 11.

Under standard assumptions $S{A}_1$–$S{A}_5$, if there exists $\epsilon >0$ such that $\parallel c_k\parallel \ge \epsilon$. Then there exists $K_6>0$ such that:

$${\delta }_{k^j}\ge K_6.$$

Proof. 

Let

$$K_6=\epsilon min\{\frac{{\delta }_{min}}{{\beta }_1},\frac{{\tau }_1(1-{\alpha }_1)K_4}{4K_3},{\tau }_1\},$$

(52)

and using (50), the proof follows directly. □

In the next section, the iteration sequence convergence is studied when $r_k\to \infty$.

3.3. Convergence When the Positive Parameter $r_k\to \infty$

This section is devoted to the convergence of the iteration sequence when the positive parameter $r_k$ goes to infinity.

Notice that, we do not require [$\nabla g_{u_i}\left(x\right)$, $i\in I\left(x\right)$] has full column rank in standard assumption $S{A}_4$, so, we may have other kinds of stationary points, which are defined in the following definitions.

Definition 2.

A feasible Fritz John (FFJ) point is a point $x_{*}$ that satisfies the following FFJ conditions:

$$\begin{array}{ccc}\hfill {\eta }_{*}\nabla f_u\left(x_{*}\right)+\nabla c\left(x_{*}\right){\mu }_{*}+\nabla g_u\left(x_{*}\right){\lambda }_{*}& =& 0,\hfill \\ \hfill c\left(x_{*}\right)& =& 0,\hfill \\ \hfill P\left(x_{*}\right)g\left(x_{*}\right)& =& 0,\hfill \\ \hfill {\left({\lambda }_{*}\right)}_i{g}_{u_i}\left(x_{*}\right)& =& 0,i=1,\dots ,m_1,\hfill \\ \hfill {\eta }_{*},{\left({\lambda }_{*}\right)}_i& \ge & 0,i=1,\dots ,m_1.\hfill \end{array}$$

where ${\eta }_{*}$, ${\mu }_{*}$, and ${\lambda }_{*}$ are not all zeros. For more details see [18].

If ${\eta }_{*}\ne 0$, then the point $(x_{*},1,\frac{{\mu }_{*}}{{\eta }_{*}},\frac{{\lambda }_{*}}{{\eta }_{*}})$ is called a KKT point and FFJ conditions are called KKT conditions.

Definition 3.

An infeasible Fritz John (IFJ) point is a point $x_{*}$ that satisfies the following IFJ conditions:

$$\begin{array}{ccc}\hfill {\eta }_{*}\nabla f_u\left(x_{*}\right)+\nabla c\left(x_{*}\right){\mu }_{*}+\nabla g_u\left(x_{*}\right){\lambda }_{*}& =& 0,\hfill \\ \hfill c\left(x_{*}\right)& =& 0,\hfill \\ \hfill \nabla g_u\left(x_{*}\right)P\left(x_{*}\right)g_u\left(x_{*}\right)& =& 0but\parallel P\left(x_{*}\right)g_u\left(x_{*}\right)\parallel >0,\hfill \\ \hfill {\left({\lambda }_{*}\right)}_i{g}_{u_i}\left(x_{*}\right)& \ge & 0,i=1,\dots ,m_1,\hfill \\ \hfill {\eta }_{*},{\left({\lambda }_{*}\right)}_i& \ge & 0,i=1,\dots ,m_1,\hfill \end{array}$$

where ${\eta }_{*}$, ${\mu }_{*}$, and ${\lambda }_{*}$ are not all zeros. For more details see [18].

If ${\eta }_{*}\ne 0$, then the point $(x_{*},1,\frac{{\mu }_{*}}{{\eta }_{*}},\frac{{\lambda }_{*}}{{\eta }_{*}})$ is called an infeasible KKT point and IFJ conditions are called infeasible KKT conditions.

Lemma 12.

Under standard assumptions $S{A}_1$–$S{A}_5$, a subsequence $\left\{k_i\right\}$ of the sequence of the iteration satisfies IFJ conditions if the following conditions satisfied:

(i)

${lim}_{k_i\to \infty }c\left(x_{k_i}\right)=0.$

(ii)

${lim}_{k_i\to \infty }\parallel P_{k_i}{g}_u\left(x_{k_i}\right)\parallel >0$.

(iii)

${lim}_{k_i\to \infty }\left\{mi{n}_{s\in {\Re }^{n-m_1+1}}{\parallel P_{k_i}(g_{u_{k_i}}+\nabla g_{u_{k_i}}^T{Y}_{k_i}{\overline{s}}^t)\parallel }^2\right\}={lim}_{k_i\to \infty }{\parallel P_{k_i}{g}_{u_{k_i}}\parallel }^2.$

Proof. 

For simplification and without loss of generality, let $\left\{k_i\right\}$ represents the whole sequence $\left\{k\right\}$. Assume that ${\tilde{s}}_k$ is the solution of the subproblem $minimiz{e}_{{\overline{s}}^t}{\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{Y}_k{\overline{s}}^t)\parallel }^2$, then it satisfies the following equation:

$$Y_k^T\nabla g_{u_k}{P}_k{g}_{u_k}+Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{Y}_k{\tilde{s}}_k=0.$$

(53)

It also satisfies the right hand side of Condition (iii). That is,

$$\underset{k\to \infty }{lim}\{2{\tilde{s}}_k{}^T{Y}_k^T\nabla g_{u_k}{P}_k{g}_{u_k}+{\tilde{s}}_k{}^T{Y}_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{Y}_k{\tilde{s}}_k\}=0.$$

(54)

We will consider two cases:

Firstly, if ${lim}_{k\to \infty }{\tilde{s}}_k=0$, then from Equation (53) we have ${lim}_{k\to \infty }{Y}_k^T\nabla g_{u_k}{P}_k{g}_{u_k}=0$.

Secondly, if ${lim}_{k\to \infty }{\tilde{s}}_k\ne 0$, then by multiplying Equation (53) from the left by $2{\tilde{s}}_k^T$ and subtract it from Equation (54), we have ${lim}_{k\to \infty }{\parallel P_k\nabla g_{u_k}^T{Y}_k{\tilde{s}}_k\parallel }^2=0$. Hence ${lim}_{k\to \infty }{Y}_k^T\nabla g_{u_k}{P}_k{g}_{u_k}=0$. That is, in two cases, we have

$$\underset{k\to \infty }{lim}{Y}_k^T\nabla g_{u_k}{P}_k{g}_{u_k}=0.$$

(55)

Since ${lim}_{k\to \infty }\parallel P_k{g}_{u_k}\parallel >0$, then ${lim}_{k\to \infty }{\left(P_k{g}_{u_k}\right)}_i\ge 0$, for $i=1,\dots ,m_1$ and ${lim}_{k\to \infty }{\left(P_k{g}_{u_k}\right)}_i>0$, for some i. Let ${\left({\lambda }_k\right)}_i={\left(P_k{g}_{u_k}\right)}_i$, $i=1,\dots ,m_1$, then ${lim}_{k\to \infty }{Y}_k^T\nabla g_{u_k}{\lambda }_k=0$. Hence, there exists a sequence of $\left\{{\mu }_k\right\}$ such that ${lim}_{k\to \infty }{Y}_k^T\{\nabla c_k{\mu }_k+\nabla g_{u_k}{\lambda }_k\}=0$. That is, IFJ conditions hold in the limit with ${\eta }_{*}=0$, see Definition 3. □

Lemma 13.

Under standard assumptions, $S{A}_1$–$S{A}_5$, a subsequence $\left\{k_i\right\}$ of the sequence of the iteration satisfies FFJ conditions if the following conditions are satisfied:

(i)

${lim}_{k_i\to \infty }c\left(x_{k_i}\right)=0.$

(ii)

For all $k_i$, $\parallel P_{k_i}{g}_{u_{k_i}}\parallel >0$ and ${lim}_{k_i\to \infty }{P}_{k_i}{g}_{u_{k_i}}=0.$

(iii)

${lim}_{k_i\to \infty }\left\{{min}_{s\in {\Re }^{n-m_1+1}}\frac{\parallel P_{k_i}(g_{u_{k_i}}+\nabla g_{u_{k_i}}^T{Y}_{k_i}{\overline{s}}^t){\parallel }^2}{\parallel P_{k_i}{g}_{u_{k_i}}{\parallel }^2}\right\}=1$.

Proof. 

For simplification and without loss of generality, let $\left\{k_i\right\}$ represents the whole sequence $\left\{k\right\}$. Notice that the following equation,

$$\underset{k\to \infty }{lim}\left\{\underset{\nu \in {\Re }^{n-m_1+1}}{min}\left\{\parallel U_k+P_k\nabla g_k^T{Y}_k{\nu \parallel }^2\right\}\right\}=1,$$

(56)

is equivalent to Condition (iii), where $U_k$ is a unit vector in the direction of $P_k{g}_{u_k}$ and $\nu =\frac{{\overline{s}}^t}{\parallel P_k{g}_{u_k}\parallel }$. Let ${\tilde{\nu }}_k$ be a solution of the following problem:

$$\underset{\nu \in {\Re }^{n-m_1+1}}{min}\left\{\parallel U_k+P_k\nabla g_k^T{Y}_k{\nu \parallel }^2\right\}.$$

(57)

Hence,

$$Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{Y}_k{\tilde{\nu }}_k+Y_k^T\nabla g_{u_k}{P}_k{U}_k=0.$$

(58)

Now two cases are considered:

Firstly, if ${lim}_{k\to \infty }{Y}_k{\tilde{\nu }}_k=0$ and using (58), then ${lim}_{k\to \infty }{Y}_k^T\nabla g_{u_k}{P}_k{U}_k=0$.

Secondly, if ${lim}_{k\to \infty }{Y}_k{\tilde{\nu }}_k\ne 0$, then from (56) and the fact that ${\tilde{\nu }}_k$ is a solution of problem (57) we have:

$$\underset{k\to \infty }{lim}\{{\overline{{\nu }_k}}^T{Y}_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{Y}_k{\tilde{\nu }}_k+2U_k^T{P}_k\nabla g_{u_k}^T{Y}_k{\tilde{\nu }}_k\}=0.$$

Multiplying Equation (58) from the left by $2{\tilde{\nu }}_k^T$ and subtracting it from the above limit, we have the following equation: ${lim}_{k\to \infty }{\tilde{\nu }}_k^T{Y}_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{Y}_k{\tilde{\nu }}_k=0$. That is ${lim}_{k\to \infty }\left\{Y_k\nabla g_{u_k}{P}_k{U}_k\right\}=0$. Hence in both cases, we have ${lim}_{k\to \infty }\left\{Y_k\nabla g_{u_k}{P}_k{U}_k\right\}=0$. The remnant of the proof follows using cases similar to those in Lemma 12. □

Lemma 14.

Under standard assumptions $S{A}_1$–$S{A}_5$, if k represents the index of iteration at which ${\sigma }_k$ is increased, then we have:

$$r_k{\parallel c_k\parallel }^2\le K_7,$$

(59)

where $K_7$ is a positive constant.

Proof. 

Since ${\sigma }_k$ is increased, then from Algorithm 1 we have:

$$\begin{array}{ccc}\hfill \frac{{\sigma }_k}{2}[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2]& =& [q_k\left(s_k\right)-q_k\left(0\right)+\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)]+\frac{{\beta }_0}{2}[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2].\hfill \end{array}$$

From (42), (50), and using the above equality, we have:

$$\begin{array}{ccc}\hfill \frac{{\sigma }_k}{2}{K}_4{\parallel c_k\parallel }^2& min& \{\frac{{\delta }_{min}}{{\beta }_1},\frac{{\tau }_1(1-{\alpha }_1)K_4}{4K_3},{\tau }_1,1\}\le {\nabla }_x{\ell }_k^T{s}_k+\frac{1}{2}{s}_k^T{H}_k{s}_k+\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)\hfill \\ & +& \frac{r_k}{2}[\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{s}_k){\parallel }^2-\parallel P_k{g}_{u_k}{\parallel }^2]+\frac{{\beta }_0}{2}[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2].\hfill \end{array}$$

However, ${\sigma }_k\ge r_k^2$, then:

$$\begin{array}{ccc}\hfill \frac{r_k^2}{2}{K}_4{\parallel c_k\parallel }^{2}min\{\frac{{\delta }_{min}}{{\beta }_1},\frac{{\tau }_1(1-{\alpha }_1)K_4}{4K_3},{\tau }_1,1\}& \le & {\nabla }_x\ell {(x_k,{\mu }_k)}^T{s}_k+\frac{1}{2}{s}_k^T{H}_k{s}_k+\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)\hfill \\ & +& \frac{r_k}{2}[\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{s}_k){\parallel }^2+\frac{{\beta }_0}{2}{\parallel c_k\parallel }^2.\hfill \end{array}$$

Hence,

$$\begin{array}{ccc}\hfill \frac{r_k}{2}{K}_4{\parallel c_k\parallel }^{2}min\{\frac{{\delta }_{min}}{{\beta }_1},\frac{{\tau }_1(1-{\alpha }_1)K_4}{4K_3},{\tau }_1,1\}& \le & \frac{1}{r_k}[{\nabla }_x{\ell }_k^T{s}_k+\frac{1}{2}{s}_k^T{H}_k{s}_k+\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)\hfill \\ & +& \frac{{\beta }_0}{2}\parallel c_k{\parallel }^2]+\frac{1}{2}{\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{s}_k)\parallel }^2\hfill \\ & \le & \frac{1}{r_k}\left[\right|{\nabla }_x{\ell }_k^T{s}_k|+\frac{1}{2}|s_k^T{H}_k{s}_k|+|\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)|\hfill \\ & +& \frac{{\beta }_0}{2}\parallel c_k{\parallel }^2]+\frac{1}{2}{\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{s}_k)\parallel }^2.\hfill \end{array}$$

From Cauchy–Schwarz inequality, standard assumptions $S{A}_3$–$S{A}_5$, and the fact that $\parallel s_k\parallel \le {\delta }_{max}$, the proof is completed. □

Lemma 15.

Under standard assumptions $S{A}_1$–$S{A}_5$, if $r_k\to \infty$ and there is an infinite subsequence $\left\{k_i\right\}$ of the sequence of the iteration at which ${\sigma }_k$ is increased, then:

$$\underset{k_i\to \infty }{lim}\parallel c_{k_i}\parallel =0.$$

(60)

Proof. 

From lemma (59) and using $r_k$ is unbounded, the proof is completed. □

Theorem 1.

Under standard assumptions $S{A}_1$–$S{A}_5$, if $r_k\to \infty$ as $k\to \infty$, then

$$\underset{k\to \infty }{lim}\parallel c_k\parallel =0.$$

(61)

Proof. 

See Theorem 4.18 [22]. □

Lemma 16.

Under standard assumptions $S{A}_1$–$S{A}_5$, if there exists a subsequence $\left\{k_j\right\}$ of indices indexing iterates that satisfy $\parallel P_k{g}_{u_k}\parallel \ge \epsilon >0$ for all $k\in \left\{k_j\right\}$ and $r_k\to \infty$ as $k\to \infty$. Then a subsequence of the iteration sequence indexed $\left\{k_j\right\}$ satisfies IFJ conditions in the limit.

Proof. 

For simplification and without loss of generality, the total sequence $\left\{k\right\}$ denotes to $\left\{k_j\right\}$. This lemma is proved by contradiction, therefor we suppose there is no subsequence of the sequence $\left\{k\right\}$ satisfies IFJ conditions in the limit. Using Lemma 12, we have for all k, $|\parallel P_k{g}_{u_k}{\parallel }^2-\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{Y}_k{\overline{s}}_k^t){\parallel }^2|\ge {\epsilon }_1$ for some ${\epsilon }_1>0$. From (55), we have $\parallel Y_k\nabla g_{u_k}{P}_k{g}_{u_k}\parallel \ge {\epsilon }_2$, for some ${\epsilon }_2>0$, hence:

$$\begin{array}{ccc}\hfill \parallel Y_k^T\nabla g_{u_k}{P}_k{g}_{u_k}+Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{s}_k^n\parallel & \ge & \parallel Y_k^T\nabla g_{u_k}{P}_k{g}_{u_k}\parallel -\parallel Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T\parallel \parallel s_k^n\parallel \hfill \\ & \ge & {\epsilon }_2-K_1\parallel Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T\parallel \parallel c_k\parallel .\hfill \end{array}$$

Since $\{\parallel c_k\parallel \}$ converges to zero and $\parallel Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T\parallel$ is bounded, then we can write: $\parallel Y_k^T\nabla g_{u_k}{P}_k{g}_{u_k}+Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{s}_k^n\parallel \ge \frac{{\epsilon }_2}{2}$. Therefore,

$$\begin{array}{ccc}\hfill \parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel & \ge & r_k\parallel Y_k^T\nabla g_{u_k}{P}_k{g}_{u_k}+Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{s}_k^n\parallel -\parallel Y_k^T{\nabla }_x{\ell }_k+Y_k^T{H}_k{s}_k^n\parallel \hfill \\ & \ge & r_k\frac{{\epsilon }_2}{2}-\parallel Y_k^T{\nabla }_x{\ell }_k+Y_k^T{H}_k{s}_k^n\parallel \hfill \\ & \ge & r_k[\frac{{\epsilon }_2}{2}-\frac{1}{r_k}\parallel Y_k^T{\nabla }_x{\ell }_k+Y_k^T{H}_k{s}_k^n\parallel ].\hfill \end{array}$$

From (46), we have:

$$\begin{array}{ccc}\hfill q_k\left(s_k^n\right)-q_k\left(s_k\right)& \ge & \frac{K_5}{2}{r}_k[\frac{{\epsilon }_2}{2}-\frac{1}{r_k}\parallel Y_k^T[{\nabla }_x{\ell }_k+H_k{s}_k^n]\parallel ]min\{{\mathsf{\Delta }}_k,\frac{\frac{{\epsilon }_2}{2}-\frac{1}{r_k}\parallel Y_k^T[{\nabla }_x{\ell }_k+H_k{s}_k^n]\parallel }{\parallel Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{Y}_k\parallel +\frac{1}{r_k}\parallel Y_k^T{H}_k{Y}_k\parallel }\}.\hfill \end{array}$$

For a k sufficiently large, we have:

$$q_k\left(s_k^n\right)-q_k\left(s_k\right)\ge \frac{K_5{\epsilon }_2}{4}{r}_{k}min\{{\mathsf{\Delta }}_k,\frac{{\epsilon }_2}{2\parallel Y_k^T\nabla g_{u_k}{P}_k\nabla g_{u_k}^T{Y}_k\parallel }\}.$$

From Algorithm 3, $\left\{r_k\right\}$ is boundless only if there exist an infinite subsequence of indices $\left\{k_i\right\}$, at which:

$$\frac{1}{2}[q_k\left(s_k^n\right)-q_k\left(s_k\right)]<\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel min\{\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel ,{\delta }_k\}.$$

(62)

Since $r_k\to \infty$, therefore an infinite number of acceptable iterates at which (62) holds and from the way of updating $r_k$, we have $r_k\to \infty$ as $k\to \infty$. This gives a contradiction unless $r_k{\delta }_k$ is bounded and hence ${\delta }_k\to 0$. Therefore $\parallel s_k\parallel \to 0$. We will consider two cases:

Firstly, if $\parallel P_k{g}_{u_k}{\parallel }^2-{\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{Y}_k{\overline{s}}_k^t)\parallel }^2>{\epsilon }_1$, then we have

$$r_k\{\parallel P_k{g}_{u_k}{\parallel }^2-\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{Y}_k{\overline{s}}_k^t){\parallel }^2\}>r_k{\epsilon }_1\to \infty .$$

(63)

Using (63) and standard assumptions $S{A}_3-S{A}_5$, we have $[q_k\left(s_k^n\right)-q_k\left(s_k\right)]\to \infty$. That is, the left hand side of inequality (62) goes to infinity while the right hand side tends to zero and this is a contradiction in this case.

Secondly, if $\parallel P_k{g}_{u_k}{\parallel }^2-{\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{Y}_k{\overline{s}}_k^t)\parallel }^2<-{\epsilon }_1$, then

$$r_k\{\parallel P_k{g}_{u_k}{\parallel }^2-\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{Y}_k{\overline{s}}_k^t){\parallel }^2\left|\right\}<-r_k{\epsilon }_1\to -\infty ,$$

where $r_k\to \infty$ as $k\to \infty$ and similar to the first case, $[q_k\left(s_k^n\right)-q_k\left(s_k\right)]\to -\infty$. This is a contradiction with $[q_k\left(s_k^n\right)-q_k\left(s_k\right)]>0$. The lemma is proved. □

Lemma 17.

Under standard assumptions $S{A}_1$–$S{A}_5$, if $r_k\to \infty$ as $k\to \infty$, and there exists a subsequence indexed $\left\{k_j\right\}$ of iterates that satisfy $\parallel P_k{g}_{u_k}\parallel >0$ for all $k\in \left\{k_j\right\}$ and ${lim}_{k_j\to \infty }\parallel P_{k_j}{g}_{u_{k_j}}\parallel =0$, then a subsequence of the sequence of iterates indexed $\left\{k_j\right\}$ satisfies FFJ conditions in the limit.

Proof. 

Without loss of generality, let $\left\{k_j\right\}$ be the whole iteration sequence $\left\{k\right\}$ to simplify. This lemma is proved by contradiction and so suppose that there is no subsequence that satisfies FFJ conditions in the limit. From condition (iii) of Lemma 13, for all k sufficiently large, there exists a constant ${\epsilon }_3>0$ such that:

$$\frac{\mid \parallel P_k{g}_{u_k}{\parallel }^2-{\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{Y}_k{\overline{s}}_k^t)\parallel }^2\mid }{\parallel P_k{g}_{u_k}{\parallel }^2}\ge {\epsilon }_3.$$

(64)

The following two cases are considered:

Firstly, if $limin{f}_{k\to \infty }\frac{{\overline{s}}_k^t}{\parallel P_k{g}_{u_k}\parallel }=0$, then there is a contradiction with inequality (64).

Secondly, if $limsu{p}_{k\to \infty }\frac{{\overline{s}}_k^t}{\parallel P_k{g}_{u_k}\parallel }=\infty$, then from subproblem (22) we have:

$$Y_k^T\nabla q_k\left(s_k^n\right)=-Y_k^T(B_k+{\upsilon }_{k}I)Y_k{\overline{s}}_k^t,$$

(65)

where ${\upsilon }_k\ge 0$ represents the Lagrange multiplier vector, which is associated with the constraint $\parallel Y_k{\overline{s}}^t\parallel \le {\mathsf{\Delta }}_k$. From (65) and (46), we have:

$$q_k\left(s_k^n\right)-q_k\left(s_k\right)\ge \frac{K_5}{2}\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel min\{{\mathsf{\Delta }}_k,\frac{\parallel Y_k^T[\frac{1}{r_k}{H}_k+(\frac{{\upsilon }_k}{r_k}I+\nabla g_{u_k}{P}_k\nabla g_{u_k}^T)]Y_k{\overline{s}}_k^t\parallel }{\parallel Y_k^T(\frac{1}{r_k}{H}_k+\nabla g_{u_k}{P}_k\nabla g_{u_k}^T)Y_k\parallel }\}.$$

(66)

Since $r_k\to \infty$ as $k\to \infty$, then there exists an infinite number of acceptable steps such that inequality (62) holds. However, inequality (62) can be written as follows:

$$\frac{1}{2}[q_k\left(s_k^n\right)-q_k\left(s_k\right)]<{\beta }_2^2{\parallel P_k{g}_{u_k}\parallel }^2,$$

(67)

where ${\beta }_2=su{p}_{x\in \mathsf{\Omega }}\parallel Y_k\nabla g_{u_k}\parallel$.

From (66) and (67), we have:

$$\frac{K_5}{2}\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel min\{\frac{{\mathsf{\Delta }}_k}{\parallel P_k{g}_{u_k}\parallel },\frac{\parallel Y_k^T[\frac{1}{r_k}{H}_k+(\frac{{\upsilon }_k}{r_k}I+\nabla g_{u_k}{P}_k\nabla g_{u_k}^T)]Y_k{\overline{s}}_k^t\parallel }{\parallel Y_k^T(\frac{1}{r_k}{H}_k+\nabla g_{u_k}{P}_k\nabla g_{u_k}^T)Y_k\parallel \parallel P_k{g}_{u_k}\parallel }\}<2{\beta }_2^2\parallel P_k{g}_{u_k}\parallel .$$

However, in previous inequality, the right hand side tends to zero as $k\to \infty$ and also ${lim}_{k_i\to \infty }\frac{{\overline{s}}_{k_i}^t}{\parallel P_{k_i}{g}_{k_i}\parallel }=\infty$ along the subsequence $\left\{k_i\right\}$. Therefore,

$$\parallel Y_{k_i}^T\nabla q_{k_i}\left(s_{k_i}^n\right)\parallel \frac{\parallel Y_{k_i}^T[\frac{1}{r_{k_i}}{H}_{k_i}+(\frac{{\upsilon }_{k_i}}{r_{k_i}}I+\nabla g_{k_i}{P}_{k_i}\nabla g_{k_i}^T)]Y_{k_i}{\overline{s}}_{k_i}^t\parallel }{\parallel Y_{k_i}^T(\frac{1}{r_{k_i}}{H}_{k_i}+\nabla g_{k_i}{P}_{k_i}\nabla g_{k_i}^T)Y_{k_i}\parallel \parallel P_{k_i}{g}_{k_i}\parallel },$$

is bounded. That is, either $\frac{{\overline{s}}_{k_i}^t}{\parallel P_{k_i}{g}_{k_i}\parallel }$ lies in the null space of $Y_{k_i}^T(\frac{{\upsilon }_{k_i}}{r_{k_i}}I+\nabla g_{k_i}{P}_{k_i}\nabla g_{k_i}^T)Y_{k_i}^T$ or $\parallel Y_{k_i}\nabla q_{k_i}\left(s_{k_i}^n\right)\parallel \to 0$.

The first possibility occurs only when $\frac{{\upsilon }_{k_i}}{r_{k_i}}\to 0$ as $k_i\to \infty$ and $\frac{{\overline{s}}_{k_i}^t}{\parallel P_{k_i}{g}_{k_i}\parallel }$ lie in the null space of the matrix $Y_{k_i}^T\nabla g_{k_i}{P}_{k_i}\nabla g_{k_i}^T{Y}_{k_i}$ which is contradicted with assumption (64). This means that, FFJ conditions are satisfied in the limit. As $k_i\to \infty$, the second possibility is, $\parallel Y_{k_i}\nabla q_{k_i}\left(s_{k_i}^n\right)\parallel \to 0$ and from (65), we have $\parallel {\overline{s}}_{k_i}^t\parallel \to 0$ which is contradicted with assumption (64). That is FFJ conditions are satisfied in the limit.

In the next section, the convergence of the sequence of the iteration sequence is studied when $r_k$ bounded.

3.4. Global Convergence When $r_k$ Is Bounded

Our analysis in this section is continued supposing that $r_k$ is bounded. Therefore, let $\overline{k}$ be an integer at which $r_k=\overline{r}<\infty$ for all $k\ge \overline{k}$. That is,

$$\frac{1}{2}[q_k\left(s_k^n\right)-q_k\left(s_k\right)]\ge \parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel min\{\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel ,{\delta }_k\}.$$

(68)

From assumptions $S{A}_3$ and $S{A}_5$, and using (68), then for all k, there is a constant ${\beta }_3>0$ such that:

$$\parallel B_k\parallel \le {\beta }_3,\parallel Y_k^T{B}_k\parallel \le {\beta }_3,and\parallel Y_k^T{B}_k{Y}_k\parallel \le {\beta }_3,$$

(69)

where $B_k=H_k+\overline{r}\nabla g_{u_k}{P}_k\nabla g_{u_k}^T$. □

Lemma 18.

Under standard assumptions $S{A}_1$–$S{A}_5$, there exists a constant $K_8>0$ such that:

$$q_k\left(0\right)-q_k\left(s_k^n\right)-\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)\ge -K_8\parallel c_k\parallel .$$

(70)

Proof. 

Since

$$\begin{array}{ccc}\hfill q_k\left(0\right)-q_k\left(s_k^n\right)& =& -{\nabla }_x{\ell }_k^T{s}_k^n-\frac{1}{2}{s}_k^{n^T}{H}_k{s}_k^n+\frac{\overline{r}}{2}[\parallel P_k{g}_{u_k}{\parallel }^2-\parallel P_k(g_{u_k}+\nabla g_{u_k}^T{s}_k^n){\parallel }^2]\hfill \\ & =& -{({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})}^T{s}_k^n-\frac{1}{2}{s_k^n}^T(H_k+\overline{r}\nabla g_{u_k}{P}_k\nabla g_{u_k}^T)s_k^n\hfill \\ & =& -{({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})}^T{s}_k^n-\frac{1}{2}{s_k^n}^T{B}_k{s}_k^n,\hfill \end{array}$$

then we have:

$$\begin{array}{ccc}\hfill q_k\left(0\right)-q_k\left(s_k^n\right)& -& \mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)=-{({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})}^T{s}_k^n-\frac{1}{2}{s_k^n}^T{B}_k{s}_k^n-\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)\hfill \\ & \ge & -\parallel {\nabla }_x{\ell }_k\parallel \parallel s_k^n\parallel -\overline{r}\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel \parallel s_k^n\parallel -\parallel B_k\parallel \parallel s_k^n{\parallel }^2-\parallel \mathsf{\Delta }{\mu }_k\parallel \parallel c_k+\nabla c_k^T{s}_k\parallel \hfill \\ & \ge & -[\parallel {\nabla }_x{\ell }_k\parallel +\overline{r}\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel +\parallel B_k\parallel \parallel s_k^n\parallel ]\parallel s_k^n\parallel -\parallel \mathsf{\Delta }{\mu }_k\parallel \parallel \nabla c_k\parallel \parallel s_k^n\parallel .\hfill \end{array}$$

From inequality (35) and the fact that $Y_k^T\nabla c\left(x_k\right)=0$, then we have:

$$\begin{array}{ccc}\hfill q_k\left(0\right)-q_k\left(s_k^n\right)-\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)& \ge & \left[\right(\parallel {\nabla }_x{\ell }_k\parallel +\overline{r}\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel +\parallel B_k\parallel \parallel s_k^n\parallel +\parallel \mathsf{\Delta }{\mu }_k\parallel \parallel \nabla c_k\parallel )K_1]\parallel c_k\parallel .\hfill \end{array}$$

From standard assumptions $S{A}_2$, $S{A}_3$, $S{A}_5$, the fact that $\parallel s_k^n\parallel \le {\delta }_{max}$, and using (69), then there exists $K_8>0$, such that inequality (70) holds. □

Lemma 19.

Under standard assumptions $S{A}_1$–$S{A}_5$, then for all k we have:

$$\begin{array}{ccc}\hfill Pre{d}_k& \ge & \frac{1}{2}{K}_5\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel min\{{\mathsf{\Delta }}_k,\frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel }{\parallel {\overline{s}}_k\parallel }\}+\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel min\{\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel ,{\delta }_k\}\hfill \\ & & -K_8\parallel c_k\parallel +{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2].\hfill \end{array}$$

(71)

Proof. 

From (29), we have:

$$\begin{array}{ccc}\hfill Pre{d}_k& =& [q_k\left(s_k^n\right)-q_k\left(s_k\right)]+[q_k\left(0\right)-q_k\left(s_k^n\right)-\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)]+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2]\hfill \\ & =& \frac{1}{2}[q_k\left(s_k^n\right)-q_k\left(s_k\right)]+\frac{1}{2}[q_k\left(s_k^n\right)-q_k\left(s_k\right)]\hfill \\ & & +[q_k\left(0\right)-q_k\left(s_k^n\right)-\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)]+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2].\hfill \end{array}$$

Using inequalities (46), (68), and (70), we obtain the desired result. □

Lemma 20.

Under standard assumptions $S{A}_1$–$S{A}_5$, if $\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel +\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel \ge \epsilon >0$ and $\parallel c_k\parallel \le \tau {\delta }_k$ where τ is a positive constant given by

$$\tau \le min\left\{\frac{\epsilon }{6{\beta }_3{K}_1{\delta }_{max}},\frac{\sqrt{3}}{2K_1},\frac{K_5\epsilon }{24K_8}min\{\frac{2\epsilon }{3{\delta }_{max}},1\},\frac{\epsilon }{4K_8}min\{\frac{\epsilon }{2{\delta }_{max}},1\}\right\},$$

(72)

then there exists a constant $K_9>0$ such that:

$$Pre{d}_k\ge K_9{\delta }_k+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2].$$

(73)

Proof. 

Since $\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel +\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel \ge \epsilon$, then we can say $\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel \ge \frac{\epsilon }{2}$ and $\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel \ge \frac{\epsilon }{2}$. We will consider two cases:

Firstly, if $\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel \ge \frac{\epsilon }{2}$, then from inequalities (69), (35) and $\parallel c_k\parallel \le \tau {\delta }_k$, we have:

$$\begin{array}{ccc}\hfill \parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k}+B_k{s}_k^n)\parallel & \ge & \parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel -\parallel Y_k^T{B}_k{s}_k^n\parallel \hfill \\ & \ge & \parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel -{\beta }_3{K}_1\parallel c_k\parallel \hfill \\ & \ge & \frac{\epsilon }{2}-{\beta }_3{K}_1\tau {\delta }_k.\hfill \end{array}$$

However, $\tau \le \frac{\epsilon }{6{\beta }_3{K}_1{\delta }_{max}}$, then

$$\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k}+A_k{s}_k^n)\parallel \ge \frac{\epsilon }{3}.$$

(74)

From inequality (35), assumption $\parallel c_k\parallel \le \tau {\delta }_k$, and using the value of $\tau$ in (72), we have $\parallel s_k^n\parallel \le K_1\parallel c_k\parallel \le K_1\tau {\delta }_k\le K_1\frac{\sqrt{3}}{2K_1}{\delta }_k=\frac{\sqrt{3}}{2}{\delta }_k$. That is, ${\mathsf{\Delta }}_k^2={\delta }_k^2-{\parallel s_k^n\parallel }^2\ge {\delta }_k^2-\frac{3}{4}{\delta }_k^2=\frac{1}{4}{\delta }_k^2$. This means that,

$${\mathsf{\Delta }}_k\ge \frac{1}{2}{\delta }_k.$$

(75)

From inequalities (71), (74), (75), and assumption $\parallel c_k\parallel \le \tau {\delta }_k$, we have the following:

$$\begin{array}{ccc}\hfill Pre{d}_k& \ge & \frac{1}{2}{K}_5\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k}+B_k{s}_k^n)\parallel min\{\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k}+B_k{s}_k^n)\parallel ,\frac{1}{2}{\delta }_k\}\hfill \\ & & -K_8\parallel c_k\parallel +{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2]\hfill \\ & \ge & \frac{K_5\epsilon }{12}{\delta }_{k}min\{\frac{2\epsilon }{3{\delta }_{max}},1\}-K_8\tau {\delta }_k+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2].\hfill \end{array}$$

However, $\tau \le \frac{K_5\epsilon }{24K_8}min\{\frac{2\epsilon }{3{\delta }_{max}},1\}$, then we have

$$Pre{d}_k\ge \frac{K_5\epsilon }{24}min\{\frac{2\epsilon }{3{\delta }_{max}},1\}{\delta }_k+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2].$$

Secondly, if $\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel \ge \frac{\epsilon }{2}$ and using inequality (71), then

$$\begin{array}{ccc}\hfill Pre{d}_k& \ge & \parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel min\{\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel ,{\delta }_k\}-K_8\parallel c_k\parallel +{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2]\hfill \\ & \ge & \frac{\epsilon }{2}min\{\frac{\epsilon }{2{\delta }_{max}},1\}{\delta }_k-K_8\tau {\delta }_k+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2]\hfill \\ & \ge & \frac{\epsilon }{4}min\{\frac{\epsilon }{2{\delta }_{max}},1\}{\delta }_k+{\sigma }_k[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2],\hfill \end{array}$$

where $\tau \le \frac{\epsilon }{4K_8}min\{\frac{\epsilon }{2{\delta }_{max}},1\}$. Let $K_9=min\left\{\frac{K_5\epsilon }{24}min\{\frac{2\epsilon }{3{\delta }_{max}},1\},\frac{\epsilon }{4}min\{\frac{\epsilon }{2{\delta }_{max}},1\}\right\}$, then the result follows.

From the previous lemma, we notice that either $\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel \ge \frac{\epsilon }{2}>0$ or $\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel \ge \frac{\epsilon }{2}>0$ and $\parallel c_k\parallel \le \tau {\delta }_k$, where $\tau$ is given by (72) at any iteration k, the value of the penalty parameter ${\sigma }_k$ is not needed to increase. That is the penalty parameter ${\sigma }_k$ is increased only when $\parallel c_k\parallel \ge \tau {\delta }_k$.

□

Lemma 21.

Under standard assumptions $S{A}_1$–$S{A}_5$, if ${\sigma }_k$ is increased at kth iteration, then there is a positive constant $K_{10}$ such that:

$${\sigma }_{k}min\{\parallel c_k\parallel ,{\delta }_k\}\le K_{10}.$$

(76)

Proof. 

From Algorithm 1, we have:

$$\begin{array}{ccc}\hfill \frac{{\sigma }_k}{2}[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2]& =& [q_k\left(s_k\right)-q_k\left(s_k^n\right)]+[q_k\left(s_k^n\right)-q_k\left(0\right)]+\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)\hfill \\ & & +\frac{{\beta }_0}{2}[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2]\hfill \\ & =& -\frac{1}{2}[q_k\left(s_k^n\right)-q_k\left(s_k\right)]-\frac{1}{2}[q_k\left(s_k^n\right)-q_k\left(s_k\right)]\hfill \\ & & +[q_k\left(s_k^n\right)-q_k\left(0\right)+\mathsf{\Delta }{\mu }_k^T(c_k+\nabla c_k^T{s}_k)]+\frac{{\beta }_0}{2}[\parallel c_k{\parallel }^2-\parallel c_k+\nabla c_k^T{s}_k{\parallel }^2],\hfill \end{array}$$

where ${\sigma }_k$ increased at any iteration and $r_k=\overline{r}$. From the previous equation, (42), (46), (68), and (70), we have

$$\begin{array}{ccc}\hfill \frac{{\sigma }_k}{2}{K}_4\parallel c_k\parallel min\{{\delta }_k,\parallel c_k\parallel \}& \le & -\frac{K_5}{2}\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel min\{{\mathsf{\Delta }}_k,\frac{\parallel Y_k^T\nabla q_k\left(s_k^n\right)\parallel }{\parallel {\overline{B}}_k\parallel }\}\hfill \\ & & -\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel min\{\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel ,{\delta }_k\}+K_8\parallel c_k\parallel +\frac{{\beta }_0}{2}{\parallel c_k\parallel }^2\hfill \\ & \le & K_8\parallel c_k\parallel +\frac{{\beta }_0}{2}{\parallel c_k\parallel }^2.\hfill \end{array}$$

Using assumption $S{A}_3$, we get the desired result. □

Lemma 22.

Under standard assumptions $S{A}_1$–$S{A}_5$ and at the jth trial iterate of any iteration k. If ${\sigma }_{k^j}$ is increased, then there is a constant $K_{11}>0$, such that

$${\sigma }_{k^j}\parallel c_k\parallel \le K_{11}.$$

(77)

Proof. 

From (50) and (76), we get the desired result. □

Lemma 23.

Under standard assumptions $S{A}_1$–$S{A}_5$, if ${\sigma }_k\to \infty$, then

$$\underset{k_i\to \infty }{lim}\parallel c_{k_i}\parallel =0,$$

(78)

where $\left\{k_i\right\}$ is a subsequence indexes the iterates at which ${\sigma }_k$ is increased.

Proof. 

From Lemma 22 we obtain the desired result. □

3.5. Main Results for Global Convergence

In this section, main global convergence results for FBACTR algorithm are introduced.

Theorem 2.

Under standard assumptions $S{A}_1$–$S{A}_5$, the sequence of iterates which is generated by FBACTR algorithm satisfies

$$\underset{k\to \infty }{lim}\parallel c_k\parallel =0.$$

(79)

Proof. 

This theorem is proved by contradiction and so we suppose that ${lim\; sup}_{k\to \infty }\parallel c_k\parallel \ge \epsilon >0$. This means that there exists an infinite subsequence of indices $\left\{k_j\right\}$ indexing iterates that satisfy $\parallel c_{k_j}\parallel \ge \frac{\epsilon }{2}$. However, there exists an infinite sequence of acceptable steps from Lemma 8. Without loss of generality and to simplify, we suppose that all members of $\left\{k_j\right\}$ are acceptable iterates. Now, two cases are considered:

Firstly, if $\left\{{\sigma }_k\right\}$ is unbounded, then an infinite number of iterates $\left\{k_i\right\}$ exists and at which the penalty parameter ${\sigma }_k$ is increased. So, for k that is sufficiently large and from Lemma 23, let $\left\{k_i\right\}$ and $\left\{k_j\right\}$ be the two sequences which are not have common elements. Let $k_{{\rho }_1}$ and $k_{{\rho }_2}$ be two consecutive iterates at which ${\sigma }_k$ is increased and $k_{{\rho }_1}<k<k_{{\rho }_2}$, where $k\in \left\{k_j\right\}$. The penalty parameter ${\sigma }_k$ is the same for all iterates that lie between $k_{{\rho }_1}$ and $k_{{\rho }_2}$. Since all the iterates of $\left\{k_j\right\}$ are acceptable, then for all $k\in \left\{k_j\right\}$,

$${{\Phi }}_k-{{\Phi }}_{k+1}=Are{d}_k\ge {\alpha }_{1}Pre{d}_k.$$

Using inequality (45), we have:

$$\frac{{{\Phi }}_k-{{\Phi }}_{k+1}}{{\sigma }_k}\ge \frac{{\alpha }_1{K}_4}{2}\parallel c_k\parallel min\{\parallel c_k\parallel ,{\delta }_k\}.$$

Summing over all acceptable iterates that lie between $k_{{\rho }_1}$ and $k_{{\rho }_2}$, we have:

$$\sum _{k=k_{{\rho }_1}}^{k_{{\rho }_2}-1}\frac{{{\Phi }}_k-{{\Phi }}_{k+1}}{{\sigma }_k}\ge \frac{{\alpha }_1{K}_4\epsilon }{4}min\{\widehat{K_6},\frac{\epsilon }{2}\},$$

where $\widehat{K_6}$ is as $K_6$ in (52)but $\epsilon$ is replaced by $\frac{\epsilon }{2}$. Hence,

$$\frac{\ell (x_{k_{{\rho }_1}},{\mu }_{k_{{\rho }_1}};\overline{r})-\ell (x_{k_{{\rho }_2}},{\mu }_{k_{{\rho }_2}};\overline{r})}{{\sigma }_{k_{{\rho }_1}}}+[\parallel c_{k_{{\rho }_1}}{\parallel }^2-\parallel c_{k_{{\rho }_2}}{\parallel }^2]\ge \frac{{\alpha }_1{K}_4\epsilon }{4}min\{\widehat{K_6},\frac{\epsilon }{2}\}.$$

Since ${\sigma }_k\to \infty$, then for $k_{{\rho }_1}$ sufficiently large, we have:

$$\frac{\mid \ell (x_{k_{{\rho }_1}},{\mu }_{k_{{\rho }_1}};\overline{r})-\ell (x_{k_{{\rho }_2}},{\mu }_{k_{{\rho }_2}};\overline{r})\mid }{{\sigma }_{k_{{\rho }_1}}}<\frac{{\alpha }_1{K}_4\epsilon }{8}min\{\widehat{K_6},\frac{\epsilon }{2}\}.$$

Therefore,

$$\parallel c_{k_{{\rho }_1}}{\parallel }^2-{\parallel c_{k_{{\rho }_2}}\parallel }^2\ge \frac{{\alpha }_1{K}_4\epsilon }{8}min\{\widehat{K_6},\frac{\epsilon }{2}\}.$$

This leads to a contradiction with Lemma 23 unless $\epsilon =0$.

Secondly, If $\left\{{\sigma }_k\right\}$ is bounded, then for all an integer $\tilde{k}$ and $k\ge \tilde{k}$, we have ${\sigma }_k=\tilde{\sigma }$. Hence, for any $\widehat{k}\in \left\{k_j\right\}$ where $\widehat{k}\ge \tilde{k}$ and using (45), we have:

$$\begin{array}{ccc}\hfill Pre{d}_{\widehat{k}}& \ge & \frac{\tilde{\sigma }{K}_4}{2}\parallel c_{\widehat{k}}\parallel min\{{\delta }_{\widehat{k}},\parallel c_{\widehat{k}}\parallel \}\ge \frac{\epsilon \tilde{\sigma }{K}_4}{4}min\{\frac{\epsilon }{2{\delta }_{max}},1\}{\delta }_{\widehat{k}}.\hfill \end{array}$$

(80)

Then for any $\widehat{k}\in \left\{k_j\right\}$, we have:

$${{\Phi }}_{\widehat{k}}-{{\Phi }}_{\widehat{k}+1}=Are{d}_{\widehat{k}}\ge {\alpha }_{1}Pre{d}_{\widehat{k}},$$

such that all the iterates of $\left\{k_j\right\}$ are acceptable. From above inequality, inequality (80) and using Lemma 11 we have:

$${{\Phi }}_{\widehat{k}}-{{\Phi }}_{\widehat{k}+1}\ge \frac{{\alpha }_1\epsilon \tilde{\sigma }{K}_4}{4}min\{\frac{\epsilon }{2{\delta }_{max}},1\}\widehat{K_6}>0.$$

However, this is a contradiction of the fact that $\left\{{{\Phi }}_k\right\}$ is bounded when $\left\{{\sigma }_k\right\}$ is bounded. Therefore, we have a contradiction in both cases. Hence the supposition is not correct and this proves the theorem. □

Theorem 3.

Under standard assumptions $S{A}_1$–$S{A}_5$, the sequence of iterates generated by FBACTR algorithm satisfies:

$$\underset{k\to \infty }{lim\; inf}[\parallel Y_k^T{\nabla }_x{\ell }_k\parallel +\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel ]=0.$$

(81)

Proof. 

First, we prove that:

$$\underset{k\to \infty }{lim\; inf}[\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel +\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel ]=0.$$

(82)

The proof of (82) is by contradiction, so, for all k, assume that $\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel +\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel >\epsilon$. Let $\left\{k_i\right\}$ be an infinite subsequence at which $\parallel c_{k_i}\parallel >\tau {\delta }_{k_i}$, where $\tau$ is defined in (72). However, $\parallel c_k\parallel \to 0$, then

$$\underset{k_i\to \infty }{lim}{\delta }_{k_i}=0.$$

Let $k^j$ be any trial iterate belonging to $\left\{k_i\right\}$ and we consider two cases:

Firstly, if $\left\{{\sigma }_k\right\}$ is unbounded, then for the rejected trial step $j-1$ of iteration $k\in \left\{k_i\right\}$, we have $\parallel c_k\parallel >\tau {\delta }_{k^j}={\tau }_1\tau \parallel s_{k^{j-1}}\parallel$. Since the trial step $s_{k^{j-1}}$ is rejected and using inequalities (45) and (41), then

$$\begin{array}{ccc}\hfill (1-{\alpha }_1)& \le & \frac{|Are{d}_{k^{j-1}}-Pre{d}_{k^{j-1}}|}{Pre{d}_{k^{j-1}}}\hfill \\ & \le & \frac{[2{\kappa }_1\parallel s_{k^{j-1}}\parallel +2{\kappa }_2{\sigma }_{k^{j-1}}\parallel s_{k^{j-1}}\parallel \parallel c_k\parallel +2{\kappa }_3{\sigma }_{k^{j-1}}\parallel s_{k^{j-1}}{\parallel }^2]}{{\sigma }_{k^{j-1}}{K}_{4}min({\tau }_1\tau ,1)\parallel c_k\parallel }\hfill \\ & \le & \frac{2{\kappa }_1}{{\sigma }_{k^{j-1}}{K}_4{\tau }_1\tau min({\tau }_1\tau ,1)}+\frac{2{\kappa }_2{\tau }_1\tau +2{\kappa }_3}{K_4{\tau }_1\tau min({\tau }_1\tau ,1)}\parallel s_{k^{j-1}}\parallel .\hfill \end{array}$$

However, $\left\{{\sigma }_k\right\}$ is unbounded, hence for all $k\ge \widehat{k}$, $\widehat{k}$ is sufficiently large, we have:

$${\sigma }_{k^{j-1}}>\frac{4{\kappa }_1}{K_4{\tau }_1\tau min({\tau }_1\tau ,1)(1-{\alpha }_1)}.$$

Therefore, for all $k\ge \widehat{k}$, we have:

$$\parallel s_{k^{j-1}}\parallel \ge \frac{K_4{\tau }_1\tau min({\tau }_1\tau ,1)(1-{\alpha }_1)}{4({\kappa }_2{\tau }_1\tau +{\kappa }_3)}.$$

From Algorithm 2, we have:

$${\delta }_{k^j}={\tau }_1\parallel s_{k^{j-1}}\parallel \ge \frac{K_4{\tau }_1^2\tau min({\tau }_1\tau ,1)(1-{\alpha }_1)}{4({\kappa }_2{\tau }_1\tau +{\kappa }_3)}.$$

This gives a contradiction and this leads to ${\delta }_{k^j}$ not being able to go to zero in this case.

Secondly, if the sequence $\left\{{\sigma }_k\right\}$ is bounded, then there exists an integer $\overline{k}$ and $\overline{\sigma }$ such that for all $k\ge \overline{k}$, ${\sigma }_k=\overline{\sigma }$. Consider a trial step j of iteration $k\ge \overline{k}$ and $\parallel c_k\parallel >\tau {\delta }_{k^j}$, we consider three cases:

(i)

If $j=1$, then ${\delta }_{k^j}\ge {\delta }_{min}$, see Algorithm 2. This means that, ${\delta }_{k^j}$ is bounded in this case;

(ii)

If $j>1$, and $\parallel c_{k^l}\parallel >\tau {\delta }_{k^l}$ for $l=1,\dots ,j$, then for all rejected trial steps $l=1,\dots ,j-1$ of iteration $k\ge \overline{k}$, we have

$$(1-{\alpha }_1)\le \frac{|Are{d}_{k^l}-Pre{d}_{k^l}|}{Pre{d}_{k^l}}\le \frac{2K_6\parallel s_{k^l}\parallel }{K_{4}min(\tau ,1)\parallel c_k\parallel }.$$

Hence,

$$\begin{array}{ccc}\hfill {\delta }_{k^j}={\tau }_1\parallel s_{k^{j-1}}\parallel & \ge & \frac{{\tau }_1{K}_{4}min(\tau ,1)(1-{\alpha }_1)\parallel c_k\parallel }{2K_3}\ge \frac{{\tau }_1{K}_{4}min(\tau ,1)(1-{\alpha }_1)\tau }{2K_3}{\delta }_{k^1}\hfill \\ & \ge & \frac{{\tau }_1{K}_{4}min(\tau ,1)(1-{\alpha }_1)\tau }{2K_3}{\delta }_{min}.\hfill \end{array}$$

That is, ${\delta }_{k^j}$ is also bounded in this case.

(iii)

If $j>1$ and $\parallel c_{k^l}\parallel >\tau {\delta }_{k^l}$ does not hold for all l, then there exists an integer $\varrho$ such that $\parallel c_{k^l}\parallel >\tau {\delta }_{k^l}$ holds for $l=\varrho +1,\dots ,j$ and $\parallel c_{k^l}\parallel \le \tau {\delta }_{k^l}$ holds for all $l=1,\dots ,\varrho$. As in case (ii), we can write:

$${\delta }_{k^j}\ge \frac{{\tau }_1{K}_{4}min(\tau ,1)(1-{\alpha }_1)}{2K_3}\parallel c_k\parallel \ge \frac{{\tau }_1{K}_{4}min(\tau ,1)(1-{\alpha }_1)\tau }{2K_3}{\delta }_{k^{\varrho +1}}.$$

(83)

From Algorithm 2, we have:

$${\delta }_{k^{\varrho +1}}\ge {\tau }_1\parallel s_{k^{\varrho }}\parallel .$$

(84)

From Lemma 20, if $\parallel c_{k^l}\parallel \le \tau {\delta }_{k^l}$ and $s_{k^{\varrho }}$ is rejected, then we have:

$$(1-{\alpha }_1)\le \frac{|Are{d}_{k^{\varrho }}-Pre{d}_{k^{\varrho }}|}{Pre{d}_{k^{\varrho }}}\le \frac{2K_6\overline{r}\parallel s_{k^{\varrho }}\parallel }{K_9}.$$

That is,

$$\parallel s_{k^{\varrho }}\parallel \ge \frac{K_9(1-{\alpha }_1)}{2K_6\overline{\sigma }}.$$

This implies that $\parallel s_{k^{\varrho }}\parallel$ is bounded and from (83) and (84) we have also ${\delta }_{k^j}$ is bounded in this case. That is in three cases, we have ${\delta }_{k^j}$ is bounded, but this leading to a contradiction. Hence, all the iterates satisfy $\parallel c_k\parallel \le \tau {\delta }_{k^j}$ for $k^j$ are sufficiently large. From Lemma 20, then the value of the penalty parameter is not needed to increase. Hence, $\left\{{\sigma }_k\right\}$ is bounded. Using Lemma 20 and for $k^j\ge \overline{k}$, we have:

$${{\Phi }}_{k^j}-{{\Phi }}_{k^j+1}=Are{d}_{k^j}\ge {\alpha }_{1}Pre{d}_{k^j}\ge {\alpha }_1{K}_9{\delta }_{k^j}.$$

As $k\to \infty$, then:

$$\underset{k\to \infty }{lim}{\delta }_{k^j}=0.$$

(85)

That is the trust-region radius is not bounded below and this leading to a contradiction. Because at iteration $k^j>\overline{k}$, if the previous step was accepted; i.e., at $j=1$, then ${\delta }_{k^1}\ge {\delta }_{min}$. That is ${\delta }_{k^j}$ is bounded in this case.

If $j>1$, then there exists at least one rejected trial step. From Lemmas 5 and 20, then for the rejected trial step $s_{k^{j-1}}$ we have:

$$(1-{\alpha }_1)<\frac{\overline{\sigma }{K}_3{\parallel s_{k^{j-1}}\parallel }^2}{K_9{\delta }_{k^{j-1}}}.$$

From Algorithm 2, we have:

$${\delta }_{k^j}={\tau }_1\parallel s_{k^{j-1}}\parallel >\frac{{\tau }_1{K}_9(1-{\alpha }_1)}{\overline{\sigma }{K}_3}.$$

Hence ${\delta }_{k^j}$ is bounded and this contradicts (85). That is, the supposition is wrong and hence,

$$\underset{k\to \infty }{lim\; inf}[\parallel Y_k^T({\nabla }_x{\ell }_k+\overline{r}\nabla g_{u_k}{P}_k{g}_{u_k})\parallel +\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel ]=0.$$

That is, (81) holds and the proof is completed.

From the above two theorems, we conclude that, given any $\epsilon >0$, the algorithm terminates because $\parallel Y_k^T{\nabla }_x{\ell }_k\parallel +\parallel \nabla g_{u_k}{P}_k{g}_{u_k}\parallel +\parallel c_k\parallel <\epsilon$, for some finite k. □

4. Numerical Results and Comparisons

In this section, we introduce an extensive variety of possible numeric NBLP problems to illustrate the validity of the proposed Algorithm FBACTR Algorithm 5 to solve the NBLP problem. The proposed algorithm FBACTR experimented on 16 benchmark examples given in [4,7,38,39,40].

Ten independent runs with a distinct initial value starting points for every test example are performed to observe the matchmaking of the result. Statistical results of all examples are briefed in

Table 1. Comparisons of the results of FBACTR Algorithm 5 with the method [11] and methods in the reference.

Problem Name	$({\mathit{v}}_{*},{\mathit{w}}_{*})$ Method [11]	${\mathit{f}}_{\mathit{u}}^{*}$ ${\mathit{f}}_{\mathit{l}}^{*}$ Method [11]	$({\mathit{v}}_{*},{\mathit{w}}_{*})$ FBACTR Algorithm 5	${\mathit{f}}_{\mathit{u}}^{*}$ ${\mathit{f}}_{\mathit{l}}^{*}$ FBACTR Algorithm 5	$({\mathit{v}}_{*},{\mathit{w}}_{*})$ Ref.	${\mathit{f}}_{\mathit{u}}^{*}$ ${\mathit{f}}_{\mathit{l}}^{*}$ Ref.
TP1	(0.8503, 0.0227,	−2.6764	(0.8465, 0.7695, 0)	−2.0772	(0.8438, 0.7657, 0)	−2.0769
	0.03589)	0.0332		−0.5919		−0.5863
TP2	(0.609, 0.391, 0,	0.6086	(0.6111, 0.3890, 0,	0.64013	(0.609, 0.391, 0,	0.6426
	0, 1.828)	1.6713	0, 1.8339)	1.6816	0, 1.828)	1.6708
TP3	(0.97, 3.14,	−8.92	(0.97, 3.14	−8.92	(0.97, 3.14,	−8.92
	2.6, 1.8)	−6.05	2.6, 1.8)	−6.05	2.6, 1.8)	−6.05
TP4	(0.5, 0.5, 0.5, 0.5)	−1	(0.5, 0.5, 0.5, 0.5)	−1	(0.5, 0.5, 0.5, 0.5)	−1
		0		0		0
TP5	(9.839, 10.059)	96.809	(9.9953, 9.9955)	99.907	(10.03, 9.969)	100.58
		0.0019		$1.8628\times {10}^{-4}$		0.001
TP6	(1.6879, 0.8805, 0)	−1.3519	(1.8889, $8.8889\times {10}^{-1}$,	−1.4074	NA	3.57
		7.4991	$6.8157\times {10}^{-6}$)	7.6172		2.4
TP7	(1, 0)	17	(1, 0)	17	(1, 0)	17
		1		1		1
TP8	(0.75, 0.75,	−2.25	(0.7513, 0.7513,	−2.2480	($\sqrt{3}/2$, $\sqrt{3}/2$,	−2.1962
	0.75, 0.75)	0	0.752, 0.752)	0	$\sqrt{3}/2$, $\sqrt{3}/2$)	0
TP9	(11.138, 5)	2209.8	(11.25, 5)	2250	(11.25, 5)	2250
		222.52		197.753		197.753
TP10	(1, 0, $6.6387\times {10}^{-6}$)	$6.6387\times {10}^{-6}$	(1, 0, 1)	1	(1, 0, 1)	1
		$-6.6387\times {10}^{-6}$		−1		−1
TP11	(24.972, 29.653,	4.9101	(25, 30, 5, 10)	5	(25, 30, 5, 10)	5
	5.0238, 9.7565)	0.01332		0		0
TP12	(3, 5)	9	(3, 5)	9	(3, 5)	9
		0		0		0
TP13	(0, 1.7405,	−15.548	(0, 2, 1.875, 0.9063)	−12.68	(0, 2, 1.875, 0.9063)	−12.68
	1.8497, 0.9692)	−1.4247		−1.016		−1.016
TP14	(10.016, 0.81967)	81.328	(10, 0.011)	$8.1978\times {10}^1$	(10.04, 0.1429)	82.44
		−0.3359		0		0.271
TP15	(0, 0.9, 0, 0.6, 0.4)	−29.2	(0, 0.9, 0, 0.6, 0.4)	−29.2	(0, 0.9, 0, 0.6, 0.4)	−29.2
		3.2		3.2		3.2
TP16	(0, 0.9, 0, 0.6,	−29.2	(0, 0.9, 0, 0.6,	−29.2	(0, 0.9, 0, 0.6,	−29.2
	0.4, 0, 0, 0)	0.3148	0.4, 0, 0, 0)	0.3148	0.4, 0, 0, 0)	0.3148

which displays that the results found by the FBACTR Algorithm 5 are approximate or equal to those by the compered algorithms in method [11] and the literature.

For comparison, the corresponding results of the mean number of iterations (iter), the mean number of function evaluations (nfunc), and the mean value of CPU time (CPUs) in seconds obtained by Methods in [11,41,42] respectively are included and summarized in

Table 2. Comparisons of the results of FBACTR Algorithm 5 with method [11], method [41] and method [42] with respect to the number of iterations, the number of function evaluations, and time/s.

Problem Name	Iter Method [11]	nfunc Method [11]	CPUs Method [11]	Iter FBACTR Algorithm	nfunc FBACTR Algorithm	CPUs FBACTR Algorithm	CPUs Method [41]	CPUs Method [42]
TP1	11	12	1.43	10	13	1.62	1.734	-
TP2	10	14	1.987	9	12	1.87	2.375	-
TP3	6	8	2.9	7	8	2.52	3.315	11.854
TP4	10	14	1.68	12	13	1.92	1.576	-
TP5	6	9	1.635	6	7	1.523	1.825	5.888
TP6	6	11	4.1	8	10	3.95	4.689	25.332
TP7	12	13	1.9	11	12	1.652	1.769	-
TP8	10	11	1.002	11	12	0.953	1.124	-
TP9	10	13	1.95	8	10	1.87	-	-
TP10	5	7	2.987	5	6	3.31	-	-
TP11	9	12	3.742	10	13	3.632	-	37.308
TP12	8	9	1.23	7	9	1.33	-	-
TP13	5	7	2.1	5	8	1.998	-	14.42
TP14	6	8	2.12	5	6	1.97	-	4.218
TP15	5	6	20.512	6	7	20.125	-	45.39
TP16	5	7	40.319	4	5	35.21	-	107.55

. These results show that results of the FBACTR Algorithm 5 are approximate or equal to those of the compared algorithms in the literature.

It is evident from the results that our approach is able to handle NBLP problems even if the upper and the lower levels are convex or not and the computed results converge to the optimal solution which is similar or approximate to the optimal reported in the literature. Finally, it is obvious from the comparison between the solutions obtained using the FBACTR Algorithm 5 with those in the literature, that the FBACTR Algorithm 5 is capable of finding the optimal solution to some problems by a small number of iterations, a small number of function evaluations, and less time.

We offered the numerical results of FBACTR Algorithm 5 using MATLAB (R2013a) (8.2.0.701)64-bit(win64) and a starting point $x_0\in int\left(\tilde{\mathit{F}}\right)$. The following parameter setting is used: ${\delta }_{min}={10}^{-4}$, ${\delta }_0=max(\parallel s_0^{cp}\parallel ,{\delta }_{min})$, ${\delta }_{max}={10}^4{\delta }_0$, ${\alpha }_1={10}^{-3}$, ${\alpha }_2=0.8$, ${\tau }_1=0.5$, ${\tau }_2=2$, ${\epsilon }_1={10}^{-10}$, and ${\epsilon }_2={10}^{-12}$.

5. Conclusions

In this paper, the FBACTR Algorithm 5 is presented to solve the NBLP problem (1). A KKT condition is used with the Fischer–Burmeister function and an active-set strategy to convert the NBLP problem to an equivalent smooth equality constrained optimization problem. To ensure global convergence for the FBACTR algorithm, a trust-region globalization strategy is used.

A global convergence theory for the FBACTR algorithm is introduced and applications to mathematical programs with equilibrium constraints are provided to clarify the effectiveness of the proposed approach. Numerical results reflect the good behavior of the FBACTR algorithm and the computed results converge to the optimal solutions. It is clear from the comparison between the solutions obtained using the FBACTR algorithm with algorithms [11,41,42] that the FBACTR can find the optimal solution to some problems with a small number of iterations, small number of function evaluations, and in less time.

Test Problem 1 [41]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=w_1^2+w_2^2+v^2-4v\hfill \\ s.t.\hfill & 0\le v\le 2,\hfill \\ \underset{w}{min}\hfill & f_l=w_1^2+0.5w_2^2+w_1{w}_2+\hfill \\ & (1-3v)w_1+(1+v)w_2,\hfill \\ s.t.\hfill & 2w_1+w_2-2v\le 1,\hfill \\ & w_1\ge 0,w_2\ge 0.\hfill \end{array}$$

Test Problem 2 [41]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=w_1^2+w_3^2-w_1{w}_3-4w_2-7v_1+4v_2\hfill \\ s.t.\hfill & v_1+v_2\le 1,\hfill \\ & v_1\ge 0,v_2\ge 0\hfill \\ \underset{w}{min}\hfill & f_l=w_1^2+0.5w_2^2+0.5w_3^2+w_1{w}_2+\hfill \\ & (1-3v_1)w_1+(1+v_2)w_2,\hfill \\ s.t.\hfill & 2w_1+w_2-w_3+v_1-2v_2+2\le 0,\hfill \\ & w_1\ge 0;w_2\ge 0w_3\ge 0.\hfill \end{array}$$

Test Problem 3 [41]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=0.1(v_1^2+v_2^2)-3w_1-4w_2+0.5(w_1^2+w_2^2)\hfill \\ s.t.\hfill & \\ \underset{w}{min}\hfill & f_l=0.5(w_1^2+5w_2^2)-2w_1{w}_2-v_1{w}_1-v_2{w}_2,\hfill \\ s.t.\hfill & -0.333w_1+w_2-2\le 0,\hfill \\ \hfill & w_1-0.333w_2-2\le 0,\hfill \\ \hfill & w_1\ge 0,w_2\ge 0,\hfill \end{array}$$

Test Problem 4 [41]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=v_1^2-2v_1+v_2^2-2v_2+w_1^2+w_2^2\hfill \\ s.t.\hfill & v_1\ge 0,v_2\ge 0\hfill \\ \underset{w}{min}\hfill & f_l={(w_1-v_1)}^2+{(w_2-v_2)}^2,\hfill \\ s.t.\hfill & 0.5\le w_1\le 1.5,\hfill \\ \hfill & 0.5\le w_2\le 1.5,\hfill \end{array}$$

Test Problem 5 [41]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=v^2+{(w-10)}^2\hfill \\ s.t.\hfill & -v+w\le 0,\hfill \\ \hfill & 0\le v\le 15,\hfill \\ \underset{w}{min}\hfill & f_l={(v+2w-30)}^2,\hfill \\ s.t.\hfill & v+w\le 20,\hfill \\ \hfill & 0\le w\le 20,\hfill \end{array}$$

Test Problem 6 [41]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u={(v_1-1)}^2+2w_1^2-2v_1\hfill \\ s.t.\hfill & v_1\ge 0,\hfill \\ \underset{w}{min}\hfill & f_l={(2w_1-4)}^2+{(2w_2-1)}^2+v_1{w}_1,\hfill \\ s.t.\hfill & 4v_1+5w_1+4w_2\le 12,\hfill \\ \hfill & -4v_1-5w_1+4w_2\le -4,\hfill \\ \hfill & 4v_1-4w_1+5w_2\le 4,\hfill \\ \hfill & -4v_1+4w_1+5w_2\le 4,\hfill \\ \hfill & w_1\ge 0,w_2\ge 0,\hfill \end{array}$$

Test Problem 7 [41]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u={(v-5)}^2+{(2w+1)}^2\hfill \\ s.t.\hfill & v\ge 0,\hfill \\ \underset{w}{min}\hfill & f_l={(2w-1)}^2-1.5vw,\hfill \\ s.t.\hfill & -3v+w\le -3,\hfill \\ \hfill & v-0.5w\le 4,\hfill \\ \hfill & v+w\le 7,\hfill \\ \hfill & w\ge 0.\hfill \end{array}$$

Test Problem 8 [41]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=v_1^2-3v_1+v_2^2-3v_2+w_1^2+w_2^2\hfill \\ s.t.\hfill & v_1\ge 0,v_2\ge 0,\hfill \\ \underset{w}{min}\hfill & f_l={(w_1-v_1)}^2+{(w_2-v_2)}^2,\hfill \\ s.t.\hfill & 0.5\le w_1\le 1.5,\hfill \\ \hfill & 0.5\le w_2\le 1.5,\hfill \end{array}$$

Test Problem 9 [3]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=16v^2+9w^2\hfill \\ s.t.\hfill & -4v+w\le 0,\hfill \\ & v\ge 0,\hfill \\ \underset{w}{min}\hfill & f_l={(v+w-20)}^4,\hfill \\ s.t.\hfill & 4v+w-50\le 0,\hfill \\ & w\ge 0.\hfill \end{array}$$

Test Problem 10 [3]:

$$\begin{array}{cc}\underset{v}{min}& f_u=v_1^3{w}_1+w_2\hfill \\ s.t.& 0\le v_1\le 1,\hfill \\ \underset{w}{min}& f_l=-w_2\hfill \\ s.t.& v_1{w}_1\le 10,\hfill \\ & w_1^2+v_1{w}_2\le 1,\hfill \\ & w_2\ge 0.\hfill \end{array}$$

Test Problem 11 [42]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=2v_1+2v_2-3w_1-3w_2-60\hfill \\ s.t.\hfill & v_1+v_2+w_1-2w_2\le 40,\hfill \\ & 0\le v_1\le 50,\hfill \\ & 0\le v_2\le 50,\hfill \\ \underset{w}{min}\hfill & f_l={(w_1-v_1+20)}^2+{(w_2-v_2+20)}^2,\hfill \\ s.t.\hfill & v_1-2w_1\ge 10,\hfill \\ \hfill & v_2-2w_2\ge 10,\hfill \\ \hfill & -10\le w_1\le 20,\hfill \\ \hfill & -10\le w_2\le 20.\hfill \end{array}$$

Test Problem 12 [3]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u={(v-3)}^2+{(w-2)}^2\hfill \\ s.t.\hfill & -2v+w-1\le 0,\hfill \\ & v-2w+2\le 0,\hfill \\ & v+2w-14\le 0,\hfill \\ & 0\le v\le 8,\hfill \\ \underset{w}{min}\hfill & f_l={(w-5)}^2\hfill \\ s.t.\hfill & w\ge 0.\hfill \end{array}$$

Test Problem 13 [42]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=-v_1^2-3v_2^2-4w_1+w_2^2\hfill \\ s.t.\hfill & v_1^2+2v_2\le 4,\hfill \\ & v_1\ge 0,v_2\ge 0,\hfill \\ \underset{w}{min}\hfill & f_l=2v_1^2+w_1^2-5w_2,\hfill \\ s.t.\hfill & v_1^2-2v_1+2v_2^2-2w_1+w_2\ge -3,\hfill \\ \hfill & v_2+3w_1-4w_2\ge 4,\hfill \\ \hfill & w_1\ge 0,w_2\ge 0.\hfill \end{array}$$

Test Problem 14 [42]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u={(v-1)}^2+{(w-1)}^2\hfill \\ s.t.\hfill & v\ge 0,\hfill \\ \underset{w}{min}\hfill & f_l=0.5w^2+500w-50vw\hfill \\ s.t.\hfill & y\ge 0.\hfill \end{array}$$

Test Problem 15 [42]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=-8v_1-4v_2+4w_1-40w_2-4w_3\hfill \\ s.t.\hfill & v_1\ge 0,v_2\ge 0\hfill \\ \underset{w}{min}\hfill & f_l=v_1+2v_2+w_1+w_2+2w_3,\hfill \\ s.t.\hfill & w_2+w_3-w_1\le 1,\hfill \\ \hfill & 2v_1-w_1+2w_2-0.5w_3\le 1,\hfill \\ \hfill & 2v_2+2w_1-w_2-0.5w_3\le 1,\hfill \\ \hfill & w_i\ge 0,i=1,2,3.\hfill \end{array}$$

Test Problem 16 [42]:

$$\begin{array}{cc}\underset{v}{min}\hfill & f_u=-8v_1-4v_2+4w_1-40w_2-4w_3\hfill \\ s.t.\hfill & v_1\ge 0,v_2\ge 0\hfill \\ \underset{w}{min}\hfill & f_l=\frac{1+v_1+v_2+2w_1-w_2+w_3}{6+2v_1+w_1+w_2-3w_3},\hfill \\ s.t.\hfill & -w_1+w_2+w_3+w_4=1,\hfill \\ \hfill & 2v_1-w_1+2w_2-0.5w_3+w_5=1,\hfill \\ \hfill & 2v_2+2w_1-w_2-0.5w_3+w_6=1,\hfill \\ \hfill & w_i\ge 0,i=1,\dots ,6.\hfill \end{array}$$