An active-set with barrier method and trust-region mechanism to solve a nonlinear Bilevel programming problem

1.   Introduction

The NBLP problem is a nonlinear optimization problem that is constrained by another nonlinear optimization problem. This mathematical programming model arises when two independent decision makers, ordered within a hierarchical structure, have conflicting objectives. The decision maker at the lower level has to optimize her objective under the given parameters from the upper level decision maker, who, in return, with complete information on the possible reactions of the lower, selects the parameters so as to optimize her own objective. The decision maker with the upper level objective, $f_u(t, v)$ takes the lead, and chooses her decision vector t. The decision maker with lower level objective, $f_l(t, v)$, reacts accordingly by choosing her decision vector v to optimize her objective, parameterized in t. Note that the upper level decision maker is limited to influencing, rather than controlling, the lower level's outcome. In fact, the problem has been proved to be NP-hard ^[5]. However, the NBLP problem is used so extensively in transaction network, finance budget, resource allocation, price control etc. Various approaches have been devoted to study this field, which leads to a a speedy development in theories and algorithms, see ^{[1,3,30,32,41]}. For detailed exposition, the reader can review ^[23,25,35].

A mathematical formulation for the NBLP problem is

where $t\in \Re^{n_1}$ and $v\in \Re^{n_2}$.

Let $n = n_1+n_2$, and assume that the functions $f_u: \Re^{n} \rightarrow \Re$, $f_l: \Re^{n} \rightarrow \Re$, $g_u: \Re^{n} \rightarrow \Re^{m_1}$, and $g_l: \Re^{n} \rightarrow \Re^{m_2}$ are at least twice continuously differentiable function in our method.

Several approaches have been proposed to solve the NBLP problem 1.1, see ^{[2,13,14,25,27,37,40,42]}. KKT conditions one of these approaches and used in this paper to convert the original NBLP problem 1.1 to the following one-level programming problem:

where $\lambda_l\in \Re^{m_2}$ is a multiplier vector associated with inequality constraint $g_l(t, v)$. problem 1.2 is non-convex and non-differentiable, moreover the regularity assumptions which are needed to successfully handle smooth optimization problems are never satisfied and it is not good to use our approach to solve problem 1.2. Dempe ^[13] presents smoothing method for the NBLP problem and the same method is also presented in ^[28] for programming with complementary constraints. Following this smoothing method we can propose our approach for the NBLP problem. Before presenting our approach for the NBLP problem, we give some definitions firstly.

Definition 1.1. The Fischer-Burmeister function is $\Psi(\tilde{a}, \tilde{b}): \Re^2 \rightarrow \Re$ defined by $\Psi(\tilde{a}, \tilde{b}) = \tilde{a}+\tilde{b}- \sqrt{\tilde{a}^2+\tilde{b}^2}$ and the perturbed Fischer-Burmeister function is $\Psi(\tilde{a}, \tilde{b}, \hat{\varepsilon}): \Re^3 \rightarrow \Re$ defined by $\Psi(\tilde{a}, \tilde{b}, \epsilon) = \tilde{a}+\tilde{b}-\sqrt{\tilde{a}^2+\tilde{b}^2+\epsilon}$.

The Fischer-Burmeister function has the property that $\Psi(\tilde{a}, \tilde{b}) = 0$ if and only if $\tilde{a}\geq 0$, $\tilde{b}\geq 0$, and $\tilde{a}\tilde{b} = 0$. It is non-differentiable at $\tilde{a} = \tilde{b} = 0$. Its perturbed variant satisfies $\Psi(\tilde{a}, \tilde{b}, \epsilon) = 0$ if and only if $\tilde{a} > 0$, $\tilde{b} > 0$, and $\tilde{a}\tilde{b} = \frac{\epsilon}{2}$ for $\epsilon > 0$. This function is smooth with respect to $\tilde{a}$, $\tilde{b}$, for $\epsilon > 0$. for more details see ^[8,9,10,28].

In this paper, to allow the proposed algorithm ACBTR solve the NBLP problem 1.1 and satisfy the asymptotic stability conditions, we use the following changed perturbed Fischer-Burmeister function:

It is obvious that the changed perturbed Fischer-Burmeister function $\tilde{\Psi}(\tilde{a}, \tilde{b}, \epsilon)$ has the same property with the function $\Psi(\tilde{a}, \tilde{b}, \epsilon)$. Using the Fischer-Burmeister function 1.3, problem 1.2 equivalents to the following single objective constrained optimization problem

Let $x = (t, v)^T$, $m = n_2+m_2$ then the above problem can be written as SONP problem as follows

where $f_u : \Re^{n} \rightarrow \Re$, $h_l: \Re^{n} \rightarrow \Re^{m}$, and $g_u: \Re^{n} \rightarrow \Re^{m_1}$ are at least twice continuously differentiable functions.

Various approaches have been proposed to solve the SONP problem 1.5, see ^{[4,7,16,17,18,19,24]}. In this paper, we use an active-set with barrier method to reduce SONP problem 1.5 to equivalent equality constrained optimization problem. So, we can use one of methods which are used for solving equality constrained optimization problem.

In this paper, we use a trust-region technique which is successful approach for solving SONP problem and is very important to ensure global convergence from any starting point. The trust-region strategy can induce strongly global convergence. It is more robust when it deals with rounding errors. It does not require the Hessian of the objective function must be positive definite or the objective function of the model must be convex. Also, some criteria are used to test the trial step is acceptable or no. If it is not acceptable, then the subproblem must be resolved with a reduced the trust-region radius. For the detailed expositions, the reader review ^{[17,20,21,22,23,24,33,36,45,46,47,48]}.

A projected Hessian method which is suggested by ^[6,38] and used by ^[19,20,22], utilizes in this paper to treat the difficulty of having an infeasible trust-region subproblem. In this method, the trial step is decomposed into two components and each component is computed by solving a trust-region unconstrained subproblem.

Under standard five assumptions, a global convergence theory for ACBTR algorithm is introduced. Moreover, numerical experiments display that ACBTR algorithm performers effectively and efficiently in pursuance.

The balance of this paper is organized as follows. A detailed description for the proposed method to solve SONP problem 1.5 is introduced in the next section. Section 3 is devoted to analysis of the global convergence of ACBTR algorithm. In Section 4, we report preliminary numerical results. Finally, some further remark is given in Section 5.

Notations: We use $\|.\|$ to denote the Euclidean norm $\|.\|_2$. The $i-th$ component of any vector such as $x$ is written as $x^{(i)}$. The $j^{th}$ trial iterate of iteration $k$ is denoted by $k^j$. Subscript $k$ refers to iteration indices. For example, $f_{u_k} \equiv f_u(x_{k})$, $h_{l_k} \equiv h_l(x_k)$, $g_{u_k} \equiv g_u(x_k)$, $W_k \equiv W(x_k)$, $\nabla_{x} L^{s}_k\equiv \nabla_{x} L^{s}(x_k, \lambda_k; \sigma_k)$, and so on to denote the function value at a particular point.

2.   An active-set with barrier method and trust-region strategy

In this section, firstly, we will introduce the detailed description for the active-set strategy with barrier method to reduce SONP problem 1.5 to equality constrained optimization problem. Secondly, to solve the equality constrained optimization problem and guarantee convergence from any starting point, we will introduce the detailed description for the trust-region algorithm. Finally, we will introduce the main steps for the main algorithm ACBTR to solve NBLP problem 1.1.

2.1.   An active-set strategy and barrier method

Motivated by the active-set strategy which is introduced by ^[12] and used by ^{[17,18,19,20,21]}, we define a 0-1 diagonal matrix $W(x)\in \Re^{m_2\times m_2}$ whose diagonal entries are

where $i = 1, ..., m_2$. By Using the diagonal matrix $W(x)\in \Re^{m_2\times m_2}$, we can transform problem 1.5 to the following equality constrained optimization problem with positive variables

Penalty methods usually more suitable on problems with equality constraints. These methods are usually generate a sequence of points that converges to a solution of the problem from the exterior of the feasible region. An advantage of penalty methods is that they do not request the iterates to be strictly feasible. In this paper we use the penalty method to reduce the above problem to the following equality constrained optimization problem with positive variables

where $\sigma$ is a positive parameter. Let $F^+(x) = \{ x|x > 0 \}$.

Motivated by the barrier method which is discussed in [^[7,26,43], problem 2.2, for any $x\in F^+$ can be written as follows

for decreasing sequence of barrier parameters $s$ converging to zero, see ^[26].

The Lagrangian function associated with problem 2.3 is

where $\lambda \in \Re^{m}$ is a multiplier vector associated with the equality constraint $h_l(x) = 0$.

The first-order necessary condition for the strictly positive point $x_*$ to be a local minimizer of problem 2.3 is that there exists a Lagrange multiplier vector $\lambda_* \in \Re^{m}$, such that $(x_*, \lambda_*)$ satisfies the following nonlinear system

where $X$ is diagonal matrix whose diagonal entries are $(x_1, ..., x_n)\in F^+$. Let $s {X_*}^{-1} e = y\in \Re^{n}$ be an auxiliary variable, then the above system can be written as follows

where $x_*\in F^+$. The conditions [2.5–2.7] are called the barrier KKT conditions. For more details see ^[26].

Applying Newton's method to the nonlinear system (2.5)–(2.7), we have

where $H$ is the Hessian matrix of the following function or an approximation to it

The matrix $Y$ is a diagonal matrix whose diagonal entries are $(y_1, ..., y_{n})$ and $\nabla_{x}L^{s}(x, \lambda; \sigma) = \nabla f_u(x)-y+\nabla h_l(x)\lambda+\sigma \nabla g_u(x)W(x) g_u(x)$.

From the second equation of the system (2.8) we have

To decrease the dimension of system 2.8, we eliminate $d_y$ from the first equation of the system 2.8 by using Eq 2.9 as follows

Using Eq 2.6, we have the following system

where, $B = H +X^{-1} Y+\sigma \nabla g_u(x)W(x)\nabla g_u(x)^T$.

We notice that, the system 2.10 is equivalent to the first order necessary condition for the following sequential quadratic programming problem

That is, the point $(x_*, \lambda_*)$ that satisfies the KKT conditions for subproblem 2.11 will satisfy the KKT conditions for problem 1.5. A methods which are used to solve subproblem 2.11 is a local methods. That is, it may not converge to a stationary point if the starting point is far away from the solution. To guarantee convergence from any starting point, we use the trust-region technique.

2.2.   Trust-region strategy

By using trust-region technique to ensure convergence of subproblem 2.11 and estimate the step $d_k$, we solve the following subproblem

where $0 < \delta_k$ represents the radius of the trust-region. The subproblem 2.12 may be infeasible because there may be no intersecting points between hyperplane of the linearized constraints $h_l(x) + \nabla h_l(x)^T d$ and the constraint $\|d\|\leq \delta_k$. Even if they intersect, there is no guarantee that this will keep true if $\delta_k$ is reduced, see ^[11]. So, a projected Hessian technique is used in our approach to overcome this problem. This technique was suggested by ^[6,38] and used by ^[19,20,22]. In this technique, the trial step $d_k$ is decomposed into two orthogonal components: the normal component $d_k^n$ to improve feasibility and the tangential component $d_k^t$ to improve optimality. Each of $d_k^n$ and $d_k^t$ is evaluated by solving unconstrained trust-region subproblem.

● To compute the normal component $d^n$

for some $\zeta\in(0, 1)$. To solve the subproblem 2.13, we use a conjugate gradient method which is introduced by ^[39] and used by ^[23], see Algorithm 2.1 in ^[23]. It is very cheap if the problem is large-scale and the Hessian is indefinite. By using the conjugate gradient method, the following condition is hold

for some $\vartheta_1 \in (0, 1]$. That is, the normal predicted decrease obtained by the normal component $d_k^n$ is greater than or equal to a fraction of the normal predicted decrease obtained by the normal Cauchy step $d_k^{ncp}$. The normal Cauchy step $d_k^{ncp}$ is defined as

where the parameter $\alpha_k^{ncp}$ is given by

Once $d_k^n$ is estimated, we will compute $d_k^t = Z_k \bar{d}_k^t$. A matrix $Z_k$ is the matrix whose columns form a basis for the null space of $(\nabla h_{l_k})^T$.

● To compute the tangential component $d_k^t$

To estimate the tangential component $d_k^t$, let

and using the conjugate gradient method ^[23] to solve the following trust-region subproblem

where $\nabla q_k(d_k^n) = \nabla_{x} L^{s}_k + B_k d_k^n$ and $\Delta_k = \sqrt{\delta_k^2 - \| d_k^n \|^2}$.

Let a tangential predicted decrease which is obtained by the tangential component $d_k^t$ be

Since the conjugate gradient method is used to solve subproblem (2.18) and estimate $d_k^t$, then the following condition holds

for some $\vartheta_2 \in (0, 1]$. This condition clarified that the tangential predicted decrease which is obtained by tangential step $\bar{d}_k^t$ is greater than or equal to a fraction of the tangential predicted decrease obtained by a tangential Cauchy step $\bar{d}_k^{tcp}$. The tangential Cauchy step $\bar{d}_k^{tcp}$ is defined as follows

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

such that $\bar{B}_k = Z_k^T B_k Z_k$.

Once estimating $d_k^t$, we set $d_k = d_k^n+d_k^t$ and $x_{k+1} = x_k+ d_k$. To guarantee that $x_{k+1} \in F^+$ at every iteration $k$, we need to evaluate the damping parameter $\mu _k$.

● To estimate the damping parameter $\mu _k$

The damping parameter $\mu _k$ is defined as follows:

where

To be decided whether the scale step $\mu_k d_k$ will be accepted or no, we need to a merit function. The merit function is the function which is tie the objective function $f_u(x)$ with the constraints $h_l(x)$ and $g_u(x)$ in such a way that progress in the merit function means progress in solving problem. In the proposed algorithm, we use the following an augmented Lagrange function as a merit function, see ^[31].

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

To be decided whether the point $(x_k+\mu_k d_k, \lambda_{k+1})$ will be taken as a next iterate or no, we need to define the actual reduction $Ared_k$ and the predicted reduction $Pred_k$ in the merit function $\Phi^{s}(x, \lambda; \sigma; \rho)$.

In the proposed algorithm, $Ared_k$ is defined as follows

Also $Ared_k$ can be written as follows,

where $\Delta \lambda_k = (\lambda_{k+1} - \lambda_k)$.

In the proposed algorithm, $Pred_k$ is defined as follows

where $\nabla_{x}l^{s}(x, \lambda) = \nabla f_u(x)-y+\nabla h_l(x)\lambda$ and $\tilde{H} = H +X^{-1} Y$.

Also, $Pred_k$ can be written as follows

where the quadratic form $q(d)$ in 2.17 can be written as follows

● To update $\rho_k$

To ensure that $Pred_k \geq 0$, we update the penalty parameter $\rho_k$ utilizing the following scheme.

Algorithm 2.1. If

then, set

where $\beta_0 > 0$ is a small fixed constant.

Else, set

End if.

For more details, see ^{[15,16,17,18,19]}.

● To test the scaling step $\mu_k d_k$ and update $\delta_k$

The framework to test the scaling step $\mu_k d_k$ and update $\delta_k$ is presented in the following algorithm.

Algorithm 2.2. Choose $0 < \gamma_1 < \gamma_2 < 1$, $0 < \alpha_1 < 1 < \alpha_2$, and $\delta_{min}\leq \delta_0 \leq \delta_{max}$.

While $\frac{Ared_k}{Pred_k} \in(0, \gamma_1)$ or $Pred_k \leq 0$.

Set $\delta_k = \alpha_1\| d_k\|$ and return to evaluate a new trial step and end while.

If $\frac{Ared_k}{Pred_k}\in[\gamma_1, \gamma_2)$. Set $x_{k+1} = x_k + \mu_kd_k$ and $\delta_{k+1} = \max(\delta_k, \delta_{min})$.

End if.

If $\frac{Ared_k}{Pred_k}\in[\gamma_2, 1]$. Set $x_{k+1} = x_k + \mu_kd_k$ and $\delta_{k+1} = \min\{\delta_{max}, \max\{\delta_{min}, \alpha_2\delta_k\}\}$.

End if.

● To update the positive parameter $\sigma_k$

To update the positive parameter $\sigma_k$, we use the following scheme.

Algorithm 2.3. If

Set $\sigma_{k+1} = \sigma_{k}$.

Else, set $\sigma_{k+1} = 2\sigma_k$. End if.

For more details see ^[18,23].

Finally, the algorithm is stopped when $\| Z_k^T \nabla_x \ell^{s}_k \|+\| \nabla g_u(x_k) W_k g_u(x_k)\|+ \|h_{l_k}\| \leq \varepsilon_1$ or $\|d_k\|\leq \varepsilon_2$, for some $\varepsilon_1, \varepsilon_2 > 0$.

● A trust-region algorithm

The framework of the trust-region algorithm to solve subproblem 2.12 are summarized as follows.

Algorithm 2.4. (Trust-region algorithm)

Step 0. Starting with $x_0\in F^+$. Evaluate $y_0$ and $\lambda_0$. Set $s_0 = 0.1$, $\rho_0 = 1$, $\sigma_0 = 1$, and $\beta_0 = 0.1$.

Choose $\varepsilon_1$, $\varepsilon_2$, $\alpha_1$, $\alpha_2$, $\gamma_1$, and $\gamma_2$ such that $0 < \varepsilon_1$, $0 < \varepsilon_2$, $0 < \alpha_1 < 1 < \alpha_2$, and $0 < \gamma_1 < \gamma_2 < 1$.

Choose $\delta_{min}$, $\delta_{max}$, and $\delta_0$ such that $\delta_{min}\leq \delta_0 \leq \delta_{max}$. Set $k = 0$.

Step 1. If $\| Z_k^T \nabla_x\ell^{s}_k \|+\| \nabla g_u(x_k) W_k g_u(x_k)\|+ \|h_{l_k}\| \leq \varepsilon_1$, then stop.

Step 2. (How to compute $d_k$)

a). Evaluate the normal component $d_k^n$ by solving subproblem (2.13).

b). Evaluate the tangential component $\bar{d}_k^t$ by solving subproblem (2.18).

c). Set $d_k = d_k^n + Z_k \bar{d}_k^t$.

Step 3. If $\| d_k\| \leq \varepsilon_2$, then stop.

Step 4. (How to compute $\mu_k$)

a). Compute the damping parameter $\mu_k$ using (2.23).

b). Set $x_{k+1} = x_k + \mu_k d_k$.

Step 5. Compute the vector $y_{k+1}$, by using the following equation

The above equation is obtained from (2.9).

Step 6. Compute $W_{k+1}$ given by (2.1).

Step 7. Evaluate $\lambda_{k+1}$ by solving the following subproblem

Step 8. Using scheme 2.1 to update the penalty parameter $\rho_k$.

Step 9. Using Algorithm (2.2) to test the scaled step $\mu_k d_k$ and update the radius $\delta_k$.

Step 10. Update the positive parameter $\sigma_k$ using scheme 2.3.

Step 11. To Update the barrier parameter $s_k$, set $s_{k+1} = \frac{s_k}{10}$.

Step 12. Set $k = k+1$ and go to Step 1.

In the following subsection we will clarify the main steps for solving NBLP problem 1.1.

2.3.   An Active-set-barrier-trust-region algorithm

The framework to solve NBLP problem 1.1 are summarized in the following algorithm.

Algorithm 2.5. (An active-set-barrier-trust-region (ACBTR) algorithm)

Step 1. Using KKT optimality conditions for the lower level problem 1.1 to reduce problem 1.1 to one-level problem 1.2.

Step 2. Using Fischer-Burmeister function 1.3 with $\epsilon = 0.001$ to obtain the smooth problem 1.4 and which is equivalent problem 1.5.

Step 3. Using An active set strategy with Barrier method to obtain subproblem 2.11.

Step 4. Using trust-region Algorithm 2.4 to solve subproblem 2.11 and obtained approximate solution for problem 1.5.

In the following section we will introduce a global convergence analysis for ACBTR algorithm.

3.   Global convergence analysis for ACBTR algorithm

let $\Omega$ be a convex subset of $\Re^n$ that contains all iterates $x_k\in F^+$ and $(x_k + \mu_k d_k)\in F^+$. To prove the global convergence theory of ACBTR algorithm on $\Omega$, we assume that the following assumptions are hold.

● Assumptions

[$A_1$]. The functions $f_u(x)$, $h_l(x)$, and $g_u(x)$ are twice continuously differentiable function for all $0 < x \in S$.

[$A_2$]. All of $f_u(x)$, $\nabla f_u(x)$, $\nabla^2 f_u(x)$, $g_u(x)$, $\nabla g_u(x)$, $h_l(x)$, $\nabla h_l(x)$, $\nabla^2 h_{l_i}(x)$ for $i = 1, ..., m$, and $(\nabla h_{l_k})[(\nabla h_{l_k})^T(\nabla h_{l_k})]^{-1}$ are uniformly bounded in $S$.

[$A_3$]. The columns of the matrix $\nabla h_l(x)$ are linearly independent.

[$A_4$]. The sequence $\{\lambda_k\}$ is bounded.

[$A_5$]. The sequence of matrices $\{\tilde{H}_k\}$ is bounded.

In the above assumptions, even though we assume that $\nabla h_l(x)$ has full column rank for all $x_k\in F^+$, we do not require $\nabla g_u(x)$ has full column rank for all $x_k\in F^+$. So, we may have other kinds of stationary points which are presented in the following definitions.

Definition 3.1. A point $x_*\in F^+$ is called a Fritz John (FJ) point if there exist $\gamma_*$, $\lambda_*$, and $\nu_*$, not all zeros, such that

Equations (3.1)–(3.5) are called FJ conditions. More details see ^[4].

If $\tau_*\neq 0$, then the point $(x_*, 1, \frac{\lambda_*}{\tau_*}, \frac{\nu_*}{\tau_*})$ is called a KKT point and FJ conditions are called the KKT conditions.

Definition 3.2. A point $x_*\in F^+$ is called an infeasible Fritz John (IFJ) point if there exist $\tau_*$, $\lambda_*$, and $\nu_*$ such that

Equations (3.6)–(3.10) are called IFJ conditions.

If $\tau_*\neq 0$, then the point $(x_*, 1, \frac{\lambda_*}{\tau_*}, \frac{\nu_*}{\tau_*})$ is called an infeasible KKT point and IFJ conditions are called infeasible KKT conditions.

Lemma 3.1. Under assumptions $A_1$–$A_5$, a subsequence $\{x_{k_i}\}$ of the iteration sequence asymptotically satisfies IFJ conditions if it satisfies:

1). $\lim_{k_i \rightarrow \infty} h_l(x_{k_i}) = 0.$

2). $\lim_{k_i \rightarrow \infty}\| W_{k_i} g_u(x_{k_i}) \| > 0$.

3). $\lim_{k_i \rightarrow \infty} \left\{min_{d\in \Re^{n-m_2}} \| W_{k_i}(g_{u_{k_i}}+\nabla g_{u_{k_i}}^T Z_{k_i}\mu_{k_i} \bar{d}^t)\|^2 \right\} = \lim_{k_i \rightarrow \infty} \| W_{k_i} g_{u_{k_i}} \|^2.$

Proof. To simplify the notations, let the subsequence $\{k_i\}$ be renamed to $\{ k \}$. Let $\hat{d}_k$ be a minimizer of $minimize_{\bar{d}^t} \| W_k (g_u(x_k) + \nabla g_u(x_k)^T Z_k \mu_k \bar{d}^t)\|^2$, then it satisfies

From condition 3, we have

Now, we will consider two cases:

Firstly, if $\lim_{k \rightarrow \infty} \hat{d}_k = 0$, then from (3.11) we have $\lim_{k \rightarrow \infty}\mu_k Z_k^T \nabla g_u(x_k) W_k g_u(x_k) = 0.$

Secondly, if $\lim_{k \rightarrow \infty} \hat{d}_k \neq 0$, then multiplying (3.11) from the left by $2 \hat{d}_k^T$ and subtract it from the limit (3.12), we have $\lim_{k \rightarrow \infty} \| W_k \nabla g_u(x_k)^T Z_k \mu_k \hat{d}_k\|^2 = 0$. This implies $\lim_{k \rightarrow \infty} \mu_k Z_k^T \nabla g_u(x_k) W_k g_u(x_k) = 0$.

That is, in either case, we have

Take $(\nu_k)_i = (W_k g_u(x_k))_i$, $i = 1, ..., p$. Since $\lim_{{k} \rightarrow \infty}\| W_k g_u(x_k) \| > 0$, then $\lim_{{k} \rightarrow \infty}(\nu_k)_i\geq 0$, for $i = 1, ..., p$ and $\lim_{{k} \rightarrow \infty}(\nu_k)_i > 0$, for some $i$. Therefore $\lim_{{k} \rightarrow \infty} Z_k^T \nabla g_u(x_k) \nu_k = 0$. But this implies the existence of a sequence $\{ \lambda_k\}$ such that $\lim_{{k} \rightarrow \infty} \{\nabla h_{l_k} \lambda_k + \nabla g_u(x_k) \nu_k\} = 0$. Thus IFJ conditions are hold in the limit with $\tau_* = 0$.

The following lemma clarify that, for any subsequence $\{x_{k_i}\}$ of the iteration sequence that asymptotically satisfies the FJ conditions, the corresponding subsequence of smallest singular values of $\{ Z_k^T \nabla g_u(x_k) W_k \}$ is not bounded away from zero. That is, asymptotically the gradient of the active constraints are linearly dependent.

Lemma 3.2. Under assumptions $A_1$–$A_5$, a subsequence $\{x_{k_i}\}$ of the iteration sequence asymptotically satisfies FJ conditions if it satisfies:

1). $\lim_{k_i \rightarrow \infty } h(x_{k_i}) = 0.$

2). For all $k_i$, $\| W_{k_i} g_{u_{k_i}} \| > 0$ and $\lim_{k_i \rightarrow \infty } W_{k_i} g_{u_{k_i}} = 0.$

3). $\lim_{{k_i} \rightarrow \infty}\left \{ \min_{d\in \Re^{n-p}} \frac{\| W_{k_i}(g_{u_{k_i}}+\nabla g_{u_{k_i}}^T Z_{k_i}\mu_{k_i} \bar{d}^t)\|^2}{\| W_{k_i} g_{u_{k_i}}\|^2}\right \} = 1$.

Proof. The proof of this lemma is similar to the proof of Lemma 4.4 in ^[19].

In the following section, we introduce some basic lemmas which are requisite to prove global convergence analysis for ACBTR algorithm.

3.1.   Basic lemmas

In this section, we introduce some significant lemmas which are required to prove global convergence theory for ACBTR algorithm.

Lemma 3.3. Under assumptions $A_1$ and $A_3$, $W(x)g_u(x)$ is Lipschitz continuous in $\Omega$.

Proof. The proof of this lemma is similar to the proof of Lemma 4.1 of ^[12].

From the above lemma, we conclude that $g_u(x)^T W(x) g_u(x)$ is differentiable and $\nabla g_u(x) W(x) g_u(x)$ is Lipschitz continuous in $\Omega$.

Lemma 3.4. At any iteration $k$, let $E(x_k) \in \Re^{m_2 \times m_2}$ be a diagonal matrix whose diagonal entries are

where $i = 1, 2, ..., m_2$. Then

Proof. See Lemma 6.2 of ^[17].

Lemma 3.5. Under assumptions $A_1$–$A_3$, there exists at any iteration $k$, a constant $C_1 > 0$ independent of $k$ such that

where $E_k \in \Re^{m_2\times m_2}$ is the diagonal matrix whose diagonal entries are defined in (3.14).

Proof. See Lemma 6.3 of ^[17].

Lemma 3.6. Under assumptions $A_1$–$A_3$, there exists at any iteration $k$, a constant $0 < C_2$ independent of $k$ such that

Proof. Since $d_k^n$ is normal to the tangent space, then we have

where $\|h_{l_k}+\nabla h_{l_k}^T d_k\|\leq\| h_{l_k}\|$. Using the assumptions $A_1$–$A_5$, we have the desired result.

The next lemma clarifies how delicate the definition of $Ared_k$ is as an approximation to $Pred_k$.

Lemma 3.7. Under assumptions $A_1$–$A_5$, there exists a constant $0 < C_3$, such that

Proof. From the definition of $Ared_k$ (2.25) and using (3.15), we have

From the above equation, the definition of $Pred_k$ (2.26), and using the inequality of Cauchy-Schwarz, we have

for some $\xi_1$ and $\xi_2 \in (0, 1)$. By using assumptions $A_1$–$A_5$, $\rho_k \geq \sigma_k$, $\rho_k\geq 1$, and inequality (3.16), we have

where $\kappa_1$, $\kappa_2$, and $\kappa_3$ are positive constants. Since $\rho_k \geq 1$, $\| d_k\|\leq \delta_{max}$, and $\| h_{l_k} \|$ is uniformly bounded, then inequality (3.18) hold.

The proof of the following two lemmas depends on the fact that $d_k^n$ and $\bar{d}^t_k$ satisfy the condition of the fraction of Cauchy decrease.

Lemma 3.8. Under assumptions $A_1$–$A_5$, there exists a constant $0 < C_4$ such that

Proof. From the definition of the normal Cauchy step (2.15), we will consider two cases:

Firstly, if $d_k^{ncp} = - \frac{\delta_k }{\| \nabla h_{l_k} h_{l_k} \| }(\nabla h_{l_k} h_{l_k})$ and $\delta_k \|\nabla h_{l_k}^T \nabla h_{l_k} h_{l_k} \|^2\leq\|\nabla h_{l_k} h_{l_k} \|^3$, then we have

Secondly, if $d_k^{ncp} = - \frac{\|\nabla h_{l_k} h_{l_k} \|^2}{\|\nabla h_{l_k}^T \nabla h_{l_k} h_{l_k} \|^2}(\nabla h_{l_k} h_{l_k})$ and $\delta_k \|\nabla h_{l_k}^T \nabla h_{l_k} h_{l_k} \|^2\geq\| \nabla h_{l_k} h_{l_k} \|^3$, then we have

Using assumption $A_3$, we have $\|\nabla h_{l_k} h_{l_k} \|\geq \frac{\|h_{l_k} \|}{\|(\nabla h_{l_k}^T \nabla h_{l_k})^{-1}\nabla h_{l_k}\|}$. Hence, from inequalities (2.14), (3.21), (3.22), and using assumption $A_2$, we obtain the inequality (3.20).

From the above lemma and the fact that

where $\mu_k\in(0, 1]$, then we have

From the way of updating $\rho_k$ shown in Step 8 in Algorithm (2.4) and above inequality, we have

Lemma 3.9. Under assumptions $A_1$–$A_5$, there exists a constant $0 < C_5$, such that

Proof. From the definition of the tangential Cauchy step (2.21), we will consider two cases:

Firstly, if $\bar{d}_k^{tcp} = -\frac{\Delta_k }{\| Z_k^T\nabla q_k(d_k^n) \| }Z_k^T\nabla q_k(d_k^n)$ and $\Delta_k(Z_k^T\nabla q_k(d_k^n))^T \bar{B}_k Z_k^T\nabla q_k(d_k^n)\leq \| Z_k^T\nabla q_k(d_k^n) \|^3$, then we have

Secondly, if $\bar{d}_k^{tcp} = -\frac{\| Z_k^T\nabla q_k(d_k^n) \|^2}{Z_k^T\nabla q_k(d_k^n))^T \bar{B}_k Z_k^T\nabla q_k(d_k^n)}Z_k^T\nabla q_k(d_k^n)$ and $\Delta_k(Z_k^T\nabla q_k(d_k^n))^T \bar{B}_k Z_k^T\nabla q_k(d_k^n)\geq \| Z_k^T\nabla q_k(d_k^n) \|^3$, then we have

Hence, from inequalities (2.20), (3.26), (3.27), and using assumptions $A_1$–$A_5$, we obtain the desired result.

From (2.19), (3.25), and the fact that

where $\mu_k\in(0, 1]$, then we have

That is

The following lemma clarifies that if at any iteration $k$, the point $x_k\in F^+$ is not feasible, then algorithm ACBTR can not loop infinitely without finding an acceptable step.

Lemma 3.10. Under assumptions $A_1$–$A_5$. If $\| h_{l_k} \| \geq \varepsilon > 0$, then the condition $\frac{Ared_{k^j}}{Pred_{k^j}}\geq \gamma_1$ will be satisfied for some finite j.

Proof. From inequalities (3.18), (3.24), and the condition $\| h_{l_k} \| \geq \varepsilon$, we have

Now as the trial step $d_{k^j}$ gets rejected, $\delta_{k^j}$ becomes small and eventually we will have

For $j$ finite, this inequality implies that, the acceptance rule will be met. This completes the proof.

Lemma 3.11. Under assumptions $A_1$–$A_5$ and the $j^{th}$ trial step of iteration $k$ satisfies,

then the step accepted.

Proof. The proof of this lemma by contradiction. Assume that the inequality (3.30) holds and the step $d_{k^j}$ is rejected. From inequalities (3.18), (3.24), and using inequality (3.30), we have

This is a contradiction and this completes the proof.

Lemma 3.12. Under assumptions $A_1$–$A_5$ and for all $j^{th}$ trial step of any iteration $k$, then $\delta_{k^j}$ satisfies

where $b_1 > 0$ is a constant.

Proof. For all $j^{th}$ trial step of any iteration $k$, we will consider tow cases:

Firstly, if $j = 1$ and the step accepted, then $\delta_k \geq \delta_{min}$. Hence,

where $b_1 = \sup_{x\in S} \|h_{l_k}\|$. Then (3.31) holds in this case.

Secondly, if $j > 1$, then there exists at least one rejected trial step and hence from Lemma (3.11) we have

for all $i = 1, 2, ...j-1$. From Algorithm 2.2 and $d_{k^i}$ is a rejected trial step, then we have

From inequalities (3.32) and (3.32) the desired result is obtained.

The next lemma prove that as long as $\| h_{l_k} \|$ is bound away from zero, the trust-region radius is also bound away from zero.

Lemma 3.13. Under assumptions $A_1$–$A_5$. If $\| h_{l_k} \| \geq \varepsilon > 0$, then

where $C_6 > 0$ is a constant.

Proof. The proof follows directly by taking

in inequality (3.31).

3.2.   Global convergence theory when $\sigma_k\rightarrow \infty$

In this section, we clarify the convergence of the sequence of iteration when the positive parameter $\sigma_k \rightarrow \infty$.

Lemma 3.14. Under assumptions $A_1$–$A_5$. If $\rho_k$ is increased at any iteration $k$, then

where $C_7$ is a positive constant.

Proof. From the way of updating the positive penalty parameter $\rho_k$, we notice that $\rho_k$ is increased at a given iteration $k$ according to one of the two rules (2.31) or (2.30). Suppose that $\rho_k$ is increased according to the rule (2.30), then

Using inequalities (3.23) and (3.31), then we have

According to rule (2.31), we have $\rho_k\geq \sigma_k^2$. Hence

Then,

where $\mu_k \leq 1$. Using the Cauchy-Schwarz inequality, assumptions $A_3$–$A_5$, and the fact that $\|d_k\|\leq \delta_{max}$, the proof is completed.

Lemma 3.15. Under assumptions $A_1$–$A_5$. If $\sigma_k\rightarrow \infty$ and there exists an infinite subsequence $\{k_i\}$of the iteration sequence at which $\rho_k$ is increased, then

Proof. The proof follows directly from $\lim_{k_i\rightarrow \infty}\mu_{k_i} = 1$, $\sigma_k\rightarrow \infty$, and Lemma (3.14).

Theorem 3.1. Under assumptions $A_1$–$A_5$. If $\sigma_k\rightarrow \infty$, then

Proof. The proof similar to the proof of Theorem 4.18 ^[19].

We notice from the way of updating $\sigma$ that, the sequence $\{ \sigma_k \}$ is unbounded only when there exist an infinite subsequence of indices $\{ k_i\}$, at which

The following lemma shows that, if $\sigma_k\rightarrow \infty$ and $\limsup_{k \rightarrow \infty}\| W_k g_u(x_k) \| > 0$, then the iteration sequence generated by the algorithm ACBTR has a subsequence that satisfies IFJ conditions in the limit.

Lemma 3.16. Under assumptions $A_1$–$A_5$. If $\sigma_k\rightarrow \infty$ and there exists a subsequence $\{ k_j\}$ of indices indexing iterates that satisfy $\| W_k g_u(x_k) \| \geq \varepsilon > 0$ for all $k \in \{ k_j\}$, then a subsequence of the iteration sequence indexed $\{ k_j\}$ satisfies the IFJ conditions as $k\rightarrow \infty$.

Proof. The proof is by contradiction. Let the subsequence $\{k_j\}$ be renamed to $\{k \}$ to simplify the notation. Suppose that there is no a subsequence of the sequence of iterates that satisfies IFJ conditions in the limit. Then we have $|\| W_k g_u(x_k)\|^2 - \| W_k(g_u(x_k)+\nabla g_u(x_k)^T Z_k\mu_k \bar{d}_k^t)\|^2| \geq \varepsilon_1 > 0$ from Lemma (3.1). Also we have $\|Z_k \nabla g_u(x_k) W_k g_u(x_k) \| \geq \varepsilon_2 > 0$ from (3.13). Since

and using (3.17), then we have

But $\{ \| h_{l_k}\|\}$ convergence to zero and $\| Z_k^T \nabla g_u(x_k) W_k \nabla g_u(x_k)^T\|$ is bounded. Then $\|Z_k^T \nabla g_u(x_k) W_k (g_u(x_k) + \nabla g_u(x_k)^T d_k^n)\| \geq \frac{\varepsilon_2}{2}$ and therefore

Hence inequality (3.29) can be written as follows

That is for $k$ sufficiently large we have

Since $\sigma_k \rightarrow \infty$, then there exists infinite number of acceptable iterates at which (3.38) holds. That is, there exists a contradiction unless $\sigma_k \Delta_k$ is bounded. Hence $\Delta_k \rightarrow 0$ and therefore $\|d_k\| \rightarrow 0$. Now we will consider two cases:

Firstly, if $\| W_k g_u(x_k)\|^2 - \| W_k(g_u(x_k)+\nabla g_u(x_k)^T Z_k\mu_k \bar{d}_k^t)\|^2 > \varepsilon_1$, we have

Thus, from (2.19), (3.39), and using assumptions $A_3$–$A_5$, we have $Tpred_k(\mu_k\bar{d}_k^t)\rightarrow \infty$. That is, the left hand side of inequality (3.38) goes to infinity while the right hand side of the same inequality goes to zero. That is, there exists a contradiction in this case.

Secondly, if $\| W_k g_u(x_k)\|^2 - \| W_k(g_u(x_k)+\nabla g_u(x_k)^T Z_k\mu_k \bar{d}_k^t)\|^2 < - \varepsilon_1$, then

where $\sigma_k \rightarrow \infty$ as $k \rightarrow \infty$. Similar to the above case, $Tpred_k(\mu_k\bar{d}_k^t)\rightarrow -\infty$. This gives a contradiction in this case with $Tpred_k(\mu_k\bar{d}_k^t) > 0$. This two contradictions prove the lemma.

The following lemma shows that if $\lim_{k \rightarrow \infty}\sigma_k \rightarrow \infty$ and $\liminf_{k \rightarrow \infty}\| W_k g_u(x_k) \| = 0$, then the iteration sequence generated by the algorithm ACBTR has a subsequence that satisfies FJ conditions in the limit.

Lemma 3.17. Under assumptions $A_1$–$A_5$. Let $\{ k_j\}$ be a subsequence of iterates that satisfy $\| W_k g_u(x_k) \| > 0$ for all $k\in \{k_j\}$ and $\lim_{{k_j} \rightarrow \infty}\| W_{k_j} g_{k_j} \| = 0$. If $\lim_{k\rightarrow \infty}\sigma_k = \infty$, then a subsequence of $\{k_j\}$ satisfies FJ conditions in the limit.

Proof. The proof of this lemma is similar to the proof of Lemma 4.20 ^[19].

3.3.   Global convergence theory when $\sigma_k$ is bounded

In this section, we will continue our discussion assuming that the parameter $\sigma_k$ is bounded. We mean that there exists an integer $\bar{k}$ such that for all $k \geq \bar{k}$, $\sigma_k = \bar{\sigma} < \infty$, and

From assumptions $A_3$, $A_5$, and assumption (3.40), we can say that there exists a constant $0 < b_2$ such that for all $k \geq \bar{k}$

where $B_k = \tilde{H}_k + \bar{\sigma} \nabla g_u(x_k) W_k \nabla g_u(x_k)^T$.

Lemma 3.18. Under assumptions $A_1$–$A_5$, there exists a constant $C_8 > 0$ such that

for all $k \geq \bar{k}$.

Proof. By using the definition (2.28), we have

That is,

By using inequality (3.17), we can obtain the following inequality

From assumptions $A_3$–$A_5$, the fact that $\| d_k^n\| \leq \delta_{max}$, and using (3.41), then for all $k \geq \bar{k}$ there exists a constant $C_8 > 0$ such that inequality (3.42) hold. This completes the proof.

Lemma 3.19. Under assumptions $A_1$–$A_5$, we have

for all $k \geq \bar{k}$.

Proof. Since the definition of $Pred_k$ (2.27) can be written as follows

and by using (2.19), we have

Using inequalities (3.29), (3.40), and (3.42), we can obtain the desired result.

Lemma 3.20. Under assumptions $A_1$–$A_5$. If $\rho_k$ increased at iteration $k$, then there exists a constant $C_9 > 0$ such that

Proof. Since $\rho_k$ is increased at iteration $k$, then from (2.30) we have

Applying inequality (3.23) to the left hand side and inequalities (3.29), (3.40), and (3.42) to the right hand side, we obtain

The rest of the proof follows using the fact that $\mu_k \leq 1$ and assumption $A_3$.

Lemma 3.21. Under assumptions $A_1$–$A_5$. If $\| Z_k^T(\nabla_x \ell^{s}(x_k, \lambda_k) +\bar{\sigma}\nabla g_u(x_k) W_k g_u(x_k))\| + \| \nabla g_u(x_k) W_k g_u(x_k) \| \geq \varepsilon > 0$ and $\| h_{l_k} \| \leq \eta \delta_k$ where $\eta > 0$ is given by

then there exists a constant $C_{10} > 0$, such that

Proof. Suppose that $\| Z_k^T(\nabla_x \ell^{s}(x_k, \lambda_k) +\bar{\sigma}\nabla g_u(x_k) W_k g_u(x_k))\| \geq \frac{\varepsilon}{2}$, then $\|\nabla g_u(x_k) W_k g_u(x_k) \| \geq \frac{\varepsilon}{2}$. From inequality (3.17) and using (3.41), we have

Since $\eta \leq \frac{\varepsilon}{6 b_2 C_2\delta_{max}}$, then we have

Because $\Delta_k = \sqrt {{\delta_k}^2 - \| d_k^n \|^2}$ and $\| d_k^n \| \leq C_2 \| h_{l_k} \| \leq C_2 \eta\delta_k \leq C_2 \frac {\sqrt {3}}{2 C_2}\delta_k = \frac {\sqrt {3}}{2} \delta_k$, hence $\Delta_k^2 = \delta_k^2 - \| d_k^n \|^2 \geq \delta_k^2 - \frac {3}{4} \delta_k^2 = \frac{1}{4} \delta_k^2$. Thus,

From inequalities (3.43), (3.47) and (3.48), we have

Since $\eta \leq \min \left\{ \frac{C_5\varepsilon}{12C_8}\min\{\frac{2\varepsilon} {3\delta_{max}}, 1\}, \frac{\varepsilon}{4C_8}\min\{\frac{\varepsilon}{\delta_{max}}, 1\}\right \}$, then we have

The result follows if we take $C_{10} = \min \left \{ \frac{C_5\varepsilon}{24}\min\{\frac{2\varepsilon}{3\delta_{max}}, 1\}\; ,\; \frac{ \varepsilon }{8}\min \{\frac{2 \varepsilon }{\delta_{\max}}, 1 \}\right \}$.

We can easily see from lemma 3.21 that, at any iteration at which $\| Z_k^T(\nabla_x \ell^{s}(x_k, \lambda_k) +\bar{\sigma}\nabla g_u(x_k) W_k g_u(x_k))+\nabla g_u(x_k) W_k g_u(x_k)\| \geq \varepsilon$ and $\| h_{l_k} \| \leq \eta \delta_k$, where $\eta$ is given by (3.45), there is no need to increase the value of $\rho_k$. It is only increased when $\| h_{l_k} \| \geq \eta \delta_k$.

Lemma 3.22. Under assumptions $A_1$–$A_5$. If $\rho_{k^j}$ increased at the $j^{th}$ trial iterate of any iteration $k$, then

where $C_{11} > 0$ is a constant.

Proof. The proof of this lemma follows directly from inequalities (3.31) and (3.44).

Lemma 3.23. Under assumptions $A_1$–$A_5$. If $\rho_k\rightarrow \infty$, then

where $\{k_i \}$ is a subsequence of iterates at which the penalty parameter is increased.

Proof. The proof of this lemma follows directly from Lemma 3.22 and $\lim_{k \rightarrow \infty}\mu_k = 1$.

3.4.   Main global convergence theory

In this section, we will prove the main global convergence theorems for the proposed algorithm ACBTR.

Theorem 3.2. Assume that assumptions $A_1$–$A_5$ hold, then the sequence of iterates generated by ACBTR algorithmsatisfies

Proof. Suppose that $\limsup_{k\rightarrow \infty} \| h_{l_k} \|\geq \varepsilon$, where $\varepsilon > 0$ is a constant. Then there exists an infinite subsequence of indices $\{k_j\}$ indexing iterates that satisfy $\| h_{k_j} \| \geq \frac{\varepsilon}{2}$. From Lemma (3.10), we know that there exists an infinite sequence of acceptable steps, so to simplify, we assume that all members of the sequence $\{k_j\}$ are acceptable iterates. Now we will consider two cases:

Firstly, we consider that, if $\{\rho_k \}$ is unbounded. Then there exists an infinite number of iterates $\{k_i\}$ at which $\rho_k$ is increased. From Lemma (3.23) and for $k$ sufficiently large, we can say $\{k_i\}\bigcap\{k_j\} = \emptyset$. Let $k_{\zeta_1}$ and $k_{\zeta_2}$ be two consecutive iterates at which $\rho_k$ is increased and $k_{\zeta_1} < k < k_{\zeta_2}$, for any $k \in \{k_j\}$. Notice that, $\rho_k$ is the same for all iterates between $k_{\zeta_1}$ and $k_{\zeta_2}$. Since all the iterates of $\{k_j\}$ are acceptable, then

for all $k \in \{k_j\}$. Using inequality (3.24), we have

Summing over all acceptable iterates that lie between $k_{\zeta_1}$ and $k_{\zeta_2}$, we have

where $\hat{C_6}$ is as $C_6$ in (3.34), with $\varepsilon$ is replaced by $\frac{\varepsilon}{2}$. Hence,

Since $\rho_k \rightarrow \infty$, then for $k_{\zeta_1}$ sufficiently large, we have

Therefore,

But this leads to a contradiction with Lemma (3.23) unless $\varepsilon = 0$.

Secondly, if $\{ \rho_k\}$ is bounded, then there exists an integer $\tilde{k}$ such that for all $k \geq \tilde{k}$, $\rho_k = \tilde{\rho}$. Hence from inequality (3.24), we have for any $\hat{k}\in \{k_j\}$ and $\hat{k} \geq \tilde{k}$

Since all the iterates of $\{k_j\}$ are acceptable, then for any $\hat{k}\in \{k_j\}$, we have

Using inequality (3.52), we have

Using Lemma (3.13), we have

Thus there exists a contradiction with the fact that $\{\Phi_k\}$ is bounded when the sequence of the penalty parameter $\{\rho_k\}$ is bounded. Hence, in both cases the supposition is not correct and the theorem is proved.

Theorem 3.3. Under assumptions $A_1$–$A_5$, the sequence of iterates generated by ACBTR algorithm satisfies

Proof. To prove this theorem we will prove

by contradiction. That is, we assume $\| \; Z_k^T (\nabla_x \ell^{s}_k + \bar{\sigma} \nabla g_u(x_k) W_k g_u(x_k))\; \| + \| \nabla g_u(x_k) W_k g_u(x_k) \| > \varepsilon$ and there exists an infinite subsequence $\{k_i\}$ of the iteration sequence such that $\| h_{l_{k_i}} \| > \eta \delta_{k_i}$. Since $\| h_{l_{k_i}} \| \rightarrow 0$ as $k_i \rightarrow 0$, then

Let $k^j$ be any iteration in $\{k_i\}$. Then we will consider two cases:

Firstly, if $\{ \rho_k \}$ is unbounded and the trial step $j-1$ of iteration $k$ is rejected. Thus $\| h_{l_k} \| > \eta \delta_{k^j} = \alpha_1 \eta \|d_{k^{j-1}}\|$. Hence, from inequalities (3.24), (3.19), and $d_{k^{j-1}}$ was rejected, we have

Since $\{ \rho_k\}$ is unbounded, then there exists an iterate $\hat{k}$ sufficiently large such that for all $k \geq \hat{k}$, we have

and

From the way of updating the radius of the trust region, we have

But this is a contradiction and this means that $\delta_{k^j}$ can not go to zero in this case.

Secondly, if $\{ \rho_k \}$ is bounded and there exists an integer $\bar{k}$ and a constant $\bar{\rho}$ such that for all $k \geq \bar{k}$, $\rho_k = \bar{\rho}$. Let $j$ be a trial step of iteration $k$ at which $\|h_{k}\| > \eta \delta_{k^j}$. Now we will consider the following two cases:

I). If $j = 1$, then from our way of updating the radius of the trust-region, we have $\delta_{k^j} \geq \delta_{\min}$. That is, $\delta_{k^j}$ is bounded in this case.

II). If $j > 1$ and $\|h_{l_k}\| > \eta \delta_{k^l}$ for all $l = 1, \cdots, j$, then for all rejected trial steps $l = 1, \cdots, j-1$ of iteration $k$, we have

That is

This means that, $\delta_{k^j}$ is bounded.

Otherwise, if $j > 1$ and $\|h_{l_k}\| > \eta \delta_{k^l}$ holds for some $l$, then there exists an integer $\beta_1$ such that $\|h_{l_k}\| > \eta \delta_{k^l}$ holds for $l = \beta_1 + 1, ..., j$ and $\|h_{l_k}\| \leq \eta \delta_{k^l}$ for $l = 1, ..., \beta_1$. As in the above case, we can write

But from the way of updating the radius of the trust-region, we have

Since $\|h_{l_k}\| \leq \eta \delta_{k^l}$ for $l = 1, ..., \beta_1$, then from Lemma (3.21) and the fact that $d_{k^{\beta_1}}$ is rejected, we have

This implies

This implies that, $\| d_{k^{\beta_1}}\|$ is bounded. Hence, $\delta_{k^j}$ is bounded in this case too. But this is a contradiction. That is $\|h_{l_k} \| \leq \eta \delta_{k^j}$ for all $k^j$ sufficiently large.

Letting $k^j \geq \bar{k}$ and using Lemma (3.21), we have

As $k\rightarrow \infty$, then

That is $\delta_{k^j}$ is not bounded below. But this leads to a contradiction and to prove this contradiction we will consider the following two cases:

i). If $k^j > \bar{k}$ and the step was accepted at $j = 1$, then $\delta_k\geq \delta_{\min}$. Hence $\delta_{k^j}$ is bounded in this case.

ii). If $j > 1$ and there exists at least one rejected trial step $d_{k^{j-1}}$. Then from Lemmas (3.7) and (3.21), we have

From the way of updating $\delta_{k^j}$ we have

Hence $\delta_{k^j}$ is bounded in this case too. But this contradicts (3.57). This means that, the supposition is incorrect. Hence,

But this also implies (3.53). This completes the proof of the theorem.

From the above two theorems, we conclude that, given any $\varepsilon > 0$, the algorithm terminates because $\| Z_k^T \nabla_x \ell^{s}_k \| + \| \nabla g_u(x_k) W_k g_u(x_k)\| + \| h_{l_k} \| < \varepsilon$, for some finite $k$.

4.   Numerical results

Algorithm ACBTR was implemented as a MATLAB code and run under MATLAB version 8.2.701 (R2013b) 64-bit(win64). We begin by a starting point $x_0 \in F^+$ and the following parameter setting is used: $\delta_{min} = 10^{-4}$, $\delta_0 = max(\| d_0^{cp} \|, \delta_{min})$, $\delta_{max} = 10^4\delta_0$, $\gamma_1 = 10^{-4}$, $\gamma_2 = 0.75$, $\alpha_1 = 0.5$, $\alpha_2 = 2$ and $\varepsilon = 10^{-8}$.

Secondly, an extensive variety of possible numeric NBLP problems are introduced to clarify the effectiveness of the proposed ACBTR algorithm.

For each test problem, 10 independent runs with different initial starting point are proceeded to observe the matchmaking of the results. Statistical results of all test problems are summarized in Table 1. The results in Table 1 show that the resuls by the ACBTR Algorithm (2.5) are approximate or equal to those by the compared algorithms in the literature.

In Table 1, we adding the average of number of iterations (iter), the average of number of function evaluations (nfunc), the average of value of CPU time (CPUs) per seconds.

For comparison, we have included the corresponding results of the avarge value of CPU time (CPUs) which are obtained by Methods in ^[34] (Table 2), ^[29] (Table 3), and ^[44] (Table 4) respectively. It is obviously from the results that our algorithm ACBTR is qualified for treating NBLP problems even the upper and the lower levels are convex or not and the results converge to the optimal solution which is similarly or approximate to the optimal that reported in literature. Finally, it is obviously from the comparison between the solutions obtained by using ACBTR algorithm with literature, that ACBTR is able to find the optimal solution of all problems by a small number of iterations, small number of function evaluations, and less time.

Problem 1 ^[34]:

Problem 2 ^[34]:

Problem 3 ^[34]:

Problem 4 ^[34]:

Problem 5 ^[34]:

Problem 6 ^[34]:

Problem 7 ^[34]:

Problem 8 ^[34]:

Problem 9 ^[29]:

Problem 10 ^[29]:

Problem 11 ^[44]:

Problem 12 ^[29]:

Problem 13 ^[44]:

Problem 14 ^[44]:

5.   Conclusions

In this paper, we introduce an effective solution algorithm to solve NBLP problem with positive variables. This algorithm based on using KKT condition with Fischer-Burmeister function to transform NBLP problem into an equivalent smooth SONP problem. An active-set strategy with barrier method and the trust-region mechanism is used to ensure global convergence from any starting point. ACBTR algorithm can reduce the number of iteration and the number of function evaluation. The projected Hessian mechanism is used in ACBTR algorithm to overcome the difficulty of having an infeasible trust region subproblem. A global convergence theory of ACBTR algorithm is studied under five standard assumptions.

Preliminary numerical experiment on the algorithm is presented. The performance of the algorithm is reported. The numerical results show that our approach is of value and merit further investigation. For future work, there are many question should be answered

● Our approach used to transform problem 1.2 which is not smooth to smooth problem.

● Using the interior-point method guarantees the converges quadratically to a stationary point.

Conflict of interest

The authors declare that there is no conflict of interest in this paper.