A modified nonmonotone QP-free method without penalty function or filter

Abstract

In this paper, a modified nonmonotone QP-free method without penalty function or filter is proposed for inequality constrained optimization. There is only two or three systems of linear equations with the same coefficients are solved at each iteration. We obtain a fundamental direction and the corresponding multiplier by the first equation, and then make full use of Lagrangian function information and multiplier to bend the search direction appropriately and obtain the search direction by the second linear equation. Moreover, the acceptable criterion of trial points is relaxed by the modified nonmonotone linear search technique. Under mild conditions, the global convergence of the algorithm is proved. Numerical results are given at the end of the paper.

Keywords

Inequality constrained optimization QP-free method nonmonotone working set global convergence

1 Introduction

Considering the following nonlinear optimization problem with inequality constraints $\begin{matrix} min f (x) \\ s . t . c_{i} (x) \leq 0, i \in I = {1, 2, \dots, m}, \end{matrix}$ (1) where f : Rⁿ → R and c_i : Rⁿ → R, i ∈ I are twice continuously differentiable function. Let feasible set be Ω = {x ∈ Rⁿ|c_i (x) ≤0, i ∈ I}.

The nonlinear constrained optimization problem is arisen in various field, such as management, economy, engineering design, military, supply issues and so on. So, it has attracted much attention due to its various applications.

It is well known that sequential quadratic programming (SQP) method is one of the most effective methods to solve nonlinearly constrained optimization problems. However, in the traditional SQP method [1, 2], there are more than one of the quadratic programming (QP) subproblems need to be solved at each iteration in order to get the search direction, which greatly increases the computational scale. In addition, the consistency of the corresponding QP subproblems is difficult to obtain in each iteration. Some scholars proposed norm-relaxed feasible sequential quadratic programming (NRFSQP) method [3, 4] which only need to solve a particular following QP subproblem $\begin{matrix} min z + \frac{1}{2} d^{T} H_{k} d \\ s . t . \nabla f (x^{k})^{T} d \leq z \\ c_{i} (x^{k}) + \nabla c_{i} (x^{k})^{T} d \leq a_{k} z, i \in I, \end{matrix}$ (2) where the matrix H_k is chosen as a positive-definite estimate of the Hessian matrix of the Lagrangian function of problem (1), a_k is a positive parameter, and z is an auxiliary variable. However, this approach is required to work out the special QP subproblem at each iteration, which lead to computational scale largely. Therefore, QP-free method has been studied by many scholars.

In 1988, Panier et al. [5] proposed a feasible QP-free algorithm to solving inequality constrained optimization problems, which only need to solve two linear systems with the same coefficient matrix and a least squares problem at each iteration, however, the stationary point is required to be isolated. Then, Qi et al. [6] constructed a new QP-free feasible algorithm by Fischer-Burmeister nonlinear complementarity function (NCP), which does not require strict complementarity conditions and does not need to assume the isolation of stable points. In fact, a lot of different types of QP-free algorithms have been proposed [7 –9]. Besides those, the primal-dual interior-point method [10, 11] is also considered for (1), but the barrier parameter is needed in their mentod. Zhu [12] proposed an interior-point-type approach, but a new feasible direction is needed to construct so that the computational scale is large. In 2010, Jian et al. [13] presented a new feasible decreasing QP-free algorithm for inequality constraints. With the introduction of a new working set, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination, but the algorithm contains an inner loop in each iteration, virtually increased the amount of calculation.

Many scholars use the penalty function as the value function with the QP-free method [14]. But it is well known that the choice of penalty parameter is difficult. If the penalty parameter is too large, then any monotonic method would be forced to follow the nonlinear constraints manifold very closely, resulting in much shortened Newton steps and slow convergence. On the other hand, too small a choice of the penalty parameter may result in converging to an infeasible point, or even an unbounded increase in the penalty. Therefore, Fletcher et al. [15] proposed the filter algorithm that does not need to introduce the penalty parameter. After that, many different filter methods [16, 17] were proposed. But the filter set is large, which makes the storage and calculation large. Therefore, many scholars proposed various of QP-free algorithms without penalty or filter [18, 19]. But most of these methods are monotone line search. Monotonic linear search [20, 21] results in step size too short when the trial point falls into the canyon and cannot jump out. Then, Grippo et al. [22] proposed a nonmonotone line search, this technique allows the value of the objective function to increase in a finite step. In 2010, Shen et al. [23] proposed a nonmonotone line search technique of QP-free algorithm for nonlinear programming and the global convergence of the algorithm is obtained under certain conditions.

In this paper, motivated by the ideas in norm-relaxed QP subproblem, a new feasible nonmonotone QP-free method is proposed. We make full use of Lagrangian function information to bend the search direction appropriately and accelerate the convergence. Constructing a new working set based on the pivoting operation to reduce the amount of calculation at each iteration. Moreover, we modify the traditional nonmonotone technique and present a new nonmonotone linear search to relax the acceptable criterion. Furthermore, at each iteration, only two or three systems of linear equations with the same coefficients are needed to solve for the search direction.

The remainder of this paper is organized as follows: In Section 2, we introduce our QP-free algorithm based on nonmonotone line search technique. The global convergence of this algorithm is established in Section 3. Some numerical experiments are shown in Section 4.

2 The nonmonotone line search QP-free algorithm

In this section, we present our algorithm and show it is well-defined. At the beginning, for a point x ∈ Ω and the index set J ⊆ I, we define the following notations. $\begin{matrix} r_{i} (x) = \nabla c_{i} (x) / ∥ \nabla c_{i} (x) ∥ (i \in J), \\ R_{J} (x) = (r_{i} (x), i \in J), \end{matrix}$ (3) $\begin{matrix} N_{J} (x) = [R_{J} (x)^{T} R_{J} (x)]^{- 1} R_{J} (x)^{T}, \end{matrix}$ (4) $\begin{matrix} P_{J} (x) = E_{n} - R_{J} (x) N_{J} (x), \end{matrix}$ (5) $\begin{matrix} (ϑ_{i} (x), i \in J) = N_{J} (x) \nabla f (x), \end{matrix}$ (6) $\begin{matrix} ρ_{J} (x) = \frac{\det [R_{J} (x)^{T} R_{J} (x)]}{e | J | ∥ \nabla f (x) ∥ + 1}, \end{matrix}$ (7) $\begin{matrix} a_{i} (x, σ) = r_{i} (x) - σ ρ_{J} (x) \nabla f (x), \end{matrix}$ (8) $\begin{matrix} C_{J} (x^{k}, ζ) = & (\nabla c_{i} (x) - ζ ∥ \nabla c_{i} (x) ∥ \nabla f (x), i \in J \\ and ζ \in [0, ρ_{J} (x)]), \end{matrix}$ (9) where |J| is the number of elements in set J, e is Napierian base, σ is nonnegative real number and E_n is identity matrix. A given point x ∈ Rⁿ is said to be a Karush-Kuhn-Tucker (KKT) point of problem (1) if there exits a vector μ ∈ R^m such that $\begin{matrix} \nabla_{x} L (x, μ) = 0, \\ μ_{i} c_{i} (x) = 0, i \in I \\ μ_{i} \geq 0, c_{i} (x) \leq 0, i \in I \end{matrix}$ (10) where $L (x, μ) = f (x) + \sum_{i = 1}^{m} μ_{i} c_{i} (x)$ is the Lagrangian function of problem (1), all i ∈ I and the vector μ = (μ₁, μ₂, ⋯ , μ_m) ^T is the corresponding lagrangian multiplier.

Define Φ : R^n+m → R^n+m: $Φ (x, μ) = (\begin{matrix} \nabla_{x} L (x, μ) \\ min {- c_{I} (x), μ} \end{matrix}),$ (11) where c_I (x) = (c₁ (x) , c₂ (x) , ⋯ , c_m (x)) ^T. It is obviously that (10) and Φ (x, μ) =0 are equivalent. Then, we define another function φ : R^n+m → R $φ (x, μ) = \sqrt{∥ Φ (x, μ) ∥},$ (12) where ∥· ∥ denotes the Euclidean norm. The function φ is non-negative and continuous. It means that (x, μ) is a KKT point of problem (1) if and only if φ (x, μ) =0. Define the violation function h : Rⁿ → R by $h (x) = \sum_{i \in I} max {c_{i} (x), 0} .$ (13)

In the following algorithm, we get an index set ${\bar{W}}_{k}$ based on the pivoting operation, and then update a working set with φ (x, μ) in ${\bar{W}}_{k}$ , which can be made to reduce the amount of calculation and is easier to implement compared to the existing techniques.

The algorithm solves the first linear equation system to obtain the direction and the corresponding multiplier, then uses the multiplier and Lagrangian function to bend the search direction. Moreover, we make the second-order correction to avoid the Maratos effect.

To obtain the convergence of the algorithm, motivated by the ideas in [23], we relax the traditional nonmonotone line search measure, and use $\bar{f} (x^{k})$ and $\bar{h} (x^{k})$ instead of the objective function f (x^k) and constraint violation function h (x^k) in the nonmonotone line search technique of our algorithm, where $\begin{matrix} \bar{f} (x^{k}) = {\begin{matrix} f (x^{0}), if k = 1, \\ \frac{f (x^{k}) + \bar{f} (x^{k - 1})}{2}, if k > 1 . \end{matrix} \\ \bar{h} (x^{k}) = {\begin{matrix} h (x^{0}), if k = 1, \\ \frac{h (x^{k}) + \bar{h} (x^{k - 1})}{2}, if k > 1 . \end{matrix} \end{matrix}$ (14)

We are now ready to state the algorithm.

Algorithm A.

Step 0: Give an initial point x⁰ ∈ X. η₁, η₂ ∈ (0, 1/2), β ∈ (0, 1), t₁, t₂ > 0, ɛ₀ > 0, M > 0, γ ∈ [0, 1], the initial symmetric positive definite matrix H₀. Set k = 1;

Step 1: (Pivoting operation)

Step 1.1: Set ɛ = ɛ_k-1 > 0, where ɛ_k-1 > 0 is the parameter produced by the previous pivoting operation iterate x^k-1.

Step 1.2: Compute I (x^k, ɛ) = {i ∈ I| - ɛ ≤ c_i (x^k) ≤0}.

Step 1.3: If det [c_I(x^k,ɛ) (x^k) ^Tc_I(x^k,ɛ) (x^k)] ≥ ɛ or I (x^k, ɛ) =∅, where c_I(x^k,ɛ) (x^k) = (c_i (x^k) , i ∈ I (x^k, ɛ)), set $ɛ_{k} = ɛ, {\bar{W}}_{k} = I (x^{k}, ɛ)$ , and go to Step 2; otherwise, let ɛ : = ɛ/2, repeat Step 1.2.

Step 2: Compute the approximate multiplier vector μ (x^k), $\begin{matrix} μ (x^{k}) = & [- ((\nabla c_{{\bar{W}}_{k}} (x^{k}))^{T} \nabla c_{{\bar{W}}_{k}} (x^{k}))^{- 1} \times \\ (\nabla c_{{\bar{W}}_{k}} (x^{k}))^{T} \nabla f (x^{k}), 0_{I ∖ {\bar{W}}_{k}}] . \end{matrix}$ (15) And the working set $\begin{matrix} W_{k} = {i \in {\bar{W}}_{k} | c_{i} (x^{k}) + φ (x^{k}, μ (x^{k})) \geq 0} \end{matrix}$ (16) where φ (x, μ (x^k)) is obtained by calculation (12). If φ (x^k, μ (x^k)) =0, then x^k is the KKT point of (1), stop.

Step 3: Compute $ρ_{k} = ρ_{{\bar{W}}_{k}} (x^{k})$ from (7) and adjust the parameter $ζ_{k} = {\begin{matrix} ρ_{0}, if k = 1; \\ min {ρ_{k}, ∥ d^{k - 1, 0} ∥^{t_{1}} + ∥ {\tilde{v}}^{k - 1} ∥^{t_{2}}, ζ_{k - 1}}, \\ if k > 1 . \end{matrix}$ (17) Set C_k = C_{W
_k} (x^k, ζ_k), and let coefficient matrix $\begin{matrix} N_{k} = (\begin{matrix} H_{k} C_{k} \\ C_{k}^{T} 0 \end{matrix}) . \end{matrix}$ (18)

Step 4: Compute $(d^{k, 0}, λ_{W_{k}}^{k, 0})$ by solving the linear system: $N_{k} (\begin{matrix} d \\ λ \end{matrix}) = - (\begin{matrix} \nabla f (x^{k}) \\ 0 \end{matrix});$ (19)

Step 5: Compute $(d^{k, 1}, λ_{W_{k}}^{k, 1})$ by solving the linear system: $N_{k} (\begin{matrix} d \\ λ \end{matrix}) = - (\begin{matrix} \nabla_{x} L (x^{k}, u^{k}) \\ v^{k} \end{matrix})$ (20) where $u^{k} = (u_{i}^{k}, i \in W_{k})$ , $u_{i}^{k} = max {λ_{i}^{k, 0}, 0}$ and $v^{k} = (v_{i}^{k}, i \in W_{k})$ , ${\tilde{v}}^{k} = ({\tilde{v}}_{i}^{k}, i \in W_{k})$ , $\begin{matrix} v_{i}^{k} = {\begin{matrix} λ_{i}^{k, 0}, if λ_{i}^{k, 0} < 0, \\ - c_{i} (x^{k}), if λ_{i}^{k, 0} c_{i} (x^{k}) < 0, \\ 0, otherwise . \end{matrix} \\ {\tilde{v}}_{i}^{k} = {\begin{matrix} λ_{i}^{k, 0}, if λ_{i}^{k, 0} < 0, \\ λ_{i}^{k, 0} c_{i} (x^{k}), if λ_{i}^{k, 0} c_{i} (x^{k}) < 0, \\ 0, otherwise . \end{matrix} \end{matrix}$ (21)

Let $Γ_{k} = 1 - ζ_{k} \sum_{i \in W_{k}} λ_{i}^{k, 1} ∥ \nabla c_{i} (x^{k}) ∥$ . If d^k,1 = 0 and Γ_k ≥ 0, stop.

Step 6: If $\begin{matrix} \begin{matrix} f (x^{k} + d^{k, 1}) \leq & max_{0 \leq j \leq m (k) - 1} \bar{f} (x^{k - j}) + \\ η_{1} min {\nabla f (x^{k})^{T} d^{k, 1}, - h (x^{k})}, \end{matrix} \\ \begin{matrix} h (x^{k} + d^{k, 1}) \leq & max_{0 \leq j \leq m (k) - 1} \bar{h} (x^{k - j}) + \\ η_{2} min {- h (x^{k}), - ∥ d^{k, 1} ∥^{2}} \end{matrix} \end{matrix}$ (22) hold, where $\bar{f} (x^{k})$ and $\bar{h} (x^{k})$ are defined by (14), then let α_k = 1, d^k,2 = 0, and go to Step 9.

Step 7: Compute (d^k,2, λ^k,2) by solving the linear system: $N_{k} (\begin{matrix} d \\ λ \end{matrix}) = - (\begin{matrix} 0 \\ c (x^{k} + d^{k, 1}) \end{matrix})$ (23) where c (x^k + d^k,1) = (c_i (x^k + d^k,1) , i ∈ W_k). If ∥d^k,2∥ > M ∥ d^k,1 ∥, let d^k,2 = 0 and θ_k = ∥ d^k,1 ∥ ²; otherwise, let $θ_{k} = γ ∥ d^{k, 1} ∥^{2} + (1 - γ) ∥ λ_{W_{k}, -}^{k, 0} ∥^{2}$ , where $λ_{W_{k}, -}^{k, 0} = (λ_{i, -}^{k, 0}, i \in W_{k}) = (min {λ_{i}^{k, 0}, 0}, i \in W_{k})$ .

Step 8: Compute the step size α_k, the first number α of the sequence {1, β, β², ⋯} such that both inequalities $\begin{matrix} f (x^{k} + α_{k} d^{k, 1} + α_{k}^{2} d^{k, 2}) \leq max_{0 \leq j \leq m (k) - 1} \bar{f} (x^{k - j}) + \\ α_{k} η_{1} min {\nabla f (x^{k})^{T} d^{k, 1}, - h (x^{k})}, \\ h (x^{k} + α_{k} d^{k, 1} + α_{k}^{2} d^{k, 2}) \leq max_{0 \leq j \leq m (k) - 1} \bar{h} (x^{k - j}) + \\ η_{2} min {- α_{k} h (x^{k}), - α_{k}^{2} θ_{k}}, \end{matrix}$ (24) where m (0) =0 and 0 ≤ m (k) ≤ min {m (k - 1) +1, M}, M is a positive constant.

Step 9: Set $x^{k + 1} = x^{k} + α_{k} d^{k, 1} + α_{k}^{2} d^{k, 2}$ and update H_k+1. Set k = k + 1, go to back Step 1.

Remark 2.1. The pivoting operation produces the approximate positive set ${\bar{W}}_{k} \supset I (x^{k})$ to make $c_{{\bar{W}}_{k}} (x^{k})$ has full column rank.

Remark 2.2. If d^k,1 = 0 and Γ_k < 0 in the process of the Algorithm A, it will terminate at a point which is not KKT point. To prevent it, we let ζ_k+1 = (1/2) ζ_k, and then compute linear equations (19) and (20).

Remark 2.3. Step 6 of the Algorithm A is used to check whether the step size α_k = 1 can be accepted. If it is accepted, the computational amount of the algorithm is reduced.

3 Global convergent properties

In this section, we show that Algorithm A is global convergent to KKT points of problem (1). To prove that, we have the following assumptions:

Assumptions 3.1. The functions f (x) and c_i (x) , i ∈ I are twice continuously differentiable.

Assumptions 3.2. The vectors {∇ c_i (x) , i ∈ I (x)} are linearly independent for each point x ∈ Ω.

Assumptions 3.3. The sequence {x^k} produced by Algorithm A is bounded.

Assumptions 3.4. There exist two positive constants b₁ and b₂ such that $b_{1} ∥ y ∥^{2} \leq y^{T} H_{k} y \leq b_{2} ∥ y ∥^{2}, \forall y \in R^{n}$ (25) holds for all k.

Lemma 3.1. For a given point x ∈ X and the working set W_k ⊆ I, suppose the vectors {∇ c_i (x) , i ∈ W_k} be linearly independent. Then (i) there exists a function ρ_k > 0, such that vectors C_{W
_k} (x^k, ζ) are linearly independent for ζ ∈ [0, ρ_k]; (ii) the vectors {a_i (x, σ) , i ∈ W_k} are linearly independent for each σ ∈ [0, 1].

Proof. (i) According to the continuous differentiability of the functions c_i (x), ∀i ∈ I, the conclusion is established. (ii) For the sake of contradiction, we suppose that the conclusion is not true, that is to say, the vectors {a_i (x, σ) , i ∈ W_k} are linearly dependent, i.e. there exists a set of numbers k_i, i ∈ W_k which are not all zero, such that $\sum_{i \in W_{k}} k_{i} a_{i} (x, σ) = \sum_{i \in W_{k}} k_{i} [r_{i} (x) - σ ρ_{k} \nabla f (x)] = 0,$ (26) it means that $\sum_{i \in W_{k}} k_{i} r_{i} (x) = \sum_{i \in W_{k}} k_{i} σ ρ_{k} \nabla f (x) .$ (27) Due to the vectors {∇ c_i (x) , i ∈ W_k} are linearly independent, we have the vectors {r_i (x) , i ∈ W_k} are also linearly independent, that is ∑_{i∈W_k}k_ir_i (x) ≠0 and ∑_{i∈W_k}k_iσρ_k ≠ 0, therefore, $\nabla f (x) = \sum_{i \in W_{k}} \frac{k_{i}}{σ ρ_{k} \sum_{i \in W_{k}} k_{i}} r_{i} (x) .$ (28) By (5) and (28), we have $\begin{matrix} P_{W_{k}} \nabla f (x) & = \nabla f (x) - \\ \sum_{i \in W_{k}} r_{i} (x) [r_{i} (x)^{T} r_{i} (x)]^{- 1} r_{i} (x)^{T} \nabla f (x) \\ = \sum_{i \in W_{k}} \frac{k_{i}}{σ ρ_{k} \sum_{i \in W_{k}} k_{i}} r_{i} (x) - \\ \sum_{i \in W_{k}} {r_{i} (x) [r_{i} (x)^{T} r_{i} (x)]^{- 1} r_{i} (x)^{T} \times \\ \sum_{i \in W_{k}} \frac{k_{i}}{σ ρ_{k} \sum_{i \in W_{k}} k_{i}} r_{i} (x)} \\ = 0, \end{matrix}$ (29) therefore, $\begin{matrix} \nabla f (x) & = \sum_{i \in W_{k}} r_{i} (x) [r_{i} (x)^{T} r_{i} (x)]^{- 1} r_{i} (x)^{T} \nabla f (x) \\ = \sum_{i \in W_{k}} ϑ_{i} (x) r_{i} (x), \end{matrix}$ (30) together with (28), (30) and σ ∈ [0, 1], we have $\begin{matrix} \sum_{i \in W_{k}} ϑ_{i} (x) = \frac{1}{σ ρ_{k}} > \frac{1}{ρ_{k}} . \end{matrix}$ (31) In fact, by (6), $\begin{matrix} | \sum_{i \in J} ϑ_{i} (x) | & \leq \sum_{i \in J} | ϑ_{i} (x) | \\ \leq \sqrt{| J |} \sqrt{\sum_{i \in J} ϑ_{i}^{2} (x)} \\ = \sqrt{| J |} \times \\ ∥ [R_{J} (x)^{T} R_{J} (x)]^{- 1} R_{J} (x)^{T} \nabla f (x) ∥ \\ \leq \frac{\sqrt{| J |}}{{min}_{i = 1, \dots, | J |} τ_{i}} ∥ R_{J} (x)^{T} \nabla f (x) ∥, \end{matrix}$ (32) where τ_i > 0 (i = 1, ⋯ , |J|) is |J| characteristic roots of R_J (x) ^TR_J (x), hence $\begin{matrix} \prod_{i = 1}^{| J |} τ_{i} = det [R_{J} (x)^{T} R_{J} (x)] \\ \sum_{i = 1}^{| J |} τ_{i} = \sum_{i \in J} ∥ r_{i} (x) ∥^{2} = | J |, \end{matrix}$ (33) so it holds that $\begin{matrix} \prod_{i = 1 i \neq j}^{| J |} τ_{i} \leq (\frac{\sum_{i = 1 i \neq j}^{| J |} τ_{i}}{| J | - 1})^{| J | - 1} \leq (\frac{| J |}{| J | - 1})^{| J | - 1} < e, \end{matrix}$ (34) for every τ_i (i = 1, 2, ⋯ , j - 1, j + 1, ⋯ , |J|). So, we have $min_{i = 1, \dots, | J |} τ_{i} \geq \frac{det [R_{J} (x)^{T} R_{J} (x)]}{e}$ , and because $∥ R_{J} (x)^{T} \nabla f (x) ∥ = \sqrt{\sum_{i \in J} [r_{i} (x)^{T} \nabla f (x)]^{2}} \leq \sqrt{\sum_{i \in J} ∥ r_{i} (x) ∥^{2} ∥ \nabla f (x) ∥^{2}} = \sqrt{| J |} ∥ \nabla f (x) ∥$ , so, $\begin{matrix} | \sum_{i \in J} ϑ_{i} (x) | \leq \frac{e | J | ∥ \nabla f (x) ∥}{det [R_{J} (x)^{T} R_{J} (x)]} < \frac{1}{ρ_{J} (x)}, \end{matrix}$ (35) that means $\begin{matrix} | \sum_{i \in W_{k}} ϑ_{i} (x) | < \frac{1}{ρ_{k}} . \end{matrix}$ (36) That’s the contradiction with (31), the conclusion follows.

Lemma 3.2. Suppose Assumption 3.1-3.2 hold, C_{W
_k} (x^k, ζ) has full column rank for any ζ ∈ [0, ρ_k] and $W_{k} \subseteq {\bar{W}}_{k}$ .

Proof. It is known that $(a_{i} (x^{k}, σ), i \in {\bar{W}}_{k})$ has full column rank for each σ ∈ [0, 1] from Remark 2.1 and Lemma 3.1. Therefore, $(∥ \nabla c_{i} (x^{k}) ∥ a_{i} (x^{k}, σ), i \in {\bar{W}}_{k}) = (\nabla c_{i} (x^{k}) - σ ρ_{k} ∥ \nabla c_{i} (x^{k}) ∥ \nabla f (x^{k}), i \in {\bar{W}}_{k})$ has full column rank for each σ ∈ [0, 1]. Set ζ = σρ_k, C_{W
_k} (x^k, ζ) = (∇ c_i (x^k) - ζ ∥ ∇ c_i (x^k) ∥ ∇ f (x^k) , i ∈ W_k) for any ζ ∈ [0, ρ_k].

Lemma 3.3. Suppose Assumption 3.1-3.4 hold and x^k ∈ X. We have (i) the pivoting operation terminates in finite iterations. (ii) if a sequence {x^k} is bounded, then there exists a constant $\hat{ɛ} > 0$ , for the sequence {ɛ_k} which is produced by the pivoting operation, working set $W_{k} \subseteq {\bar{W}}_{k}$ and each ζ ∈ [0, ρ_k], the following formula $\begin{matrix} det [(\nabla c_{{\bar{W}}_{k}} (x^{k}))^{T} \nabla c_{{\bar{W}}_{k}} (x^{k})] \geq inf {ɛ_{k}} > 0, \forall k, \end{matrix}$ (37) $\begin{matrix} det [(C_{W_{k}} (x^{k}, ζ))^{T} C_{W_{k}} (x^{k}, ζ)] \geq \hat{ɛ_{k}}, \forall k, \end{matrix}$ (38) hold.

Proof. The proof is similar to Lemma 2.5 in [13].

According to lemma 3.2, it is obvious that the following conclusion is true.

Lemma 3.4. Let H_k ∈ R^n×n be a symmetric matrix satisfying Assumptions 3.4, then the matrix N_k defined by Equation (18) is non-singular.

Lemma 3.5. Suppose x^k ∈ X, (i) if φ (x^k, μ^k) =0, then x^k is the KKT point of (1); (ii) if d^k,1 = 0 and Γ_k ≥ 0, then x^k is the KKT point of (1).

Proof. (i) It is clearly that the conclusion holds by definition. (ii) Since the d^k,1 = 0, we have $v_{W_{k}}^{k} = 0$ from (20), and $C_{k}^{T} x = 0$ has a zero solution, together with the second equation of (19), we have d^k,0 = 0. Therefore, it holds that ${\begin{matrix} (1 - ζ_{k} \sum_{i \in W_{k}} λ_{i}^{k, 0} ∥ \nabla c_{i} (x^{k}) ∥) \nabla f (x^{k}) + \\ \sum_{i \in W_{k}} λ_{i}^{k, 0} \nabla c_{i} (x^{k}) = 0, \\ v_{W_{k}}^{k} = 0 . \end{matrix}$ (39) By $v_{W_{k}}^{k} = 0$ , then $λ_{W_{k}}^{k, 0} \geq 0$ , $\sum_{i \in W_{k}} λ_{i}^{k, 0} c_{i} (x^{k}) = 0$ , i ∈ W_k. In view of Γ_k ≥ 0, we know that $\frac{λ_{W_{k}}^{k, 0}}{Γ_{k}} \geq 0$ and $\frac{λ_{W_{k}}^{k, 0}}{Γ_{k}} c_{W_{k}} (x^{k}) = 0$ . Hence, for x ∈ X, (39) can be transformed into the following equation ${\begin{matrix} \nabla f (x^{k}) + \sum_{i \in W_{k}} \frac{λ_{i}^{k, 0}}{Γ_{k}} \nabla c_{i} (x^{k}) = 0, \\ \sum_{i \in W_{k}} \frac{λ_{i}^{k, 0}}{Γ_{k}} \geq 0, i \in W_{k}, \\ \sum_{i \in W_{k}} \frac{λ_{i}^{k, 0}}{Γ_{k}} c_{i} (x^{k}) = 0, i \in W_{k}, \\ c_{i} (x^{k}) \leq 0, i \in W_{k} . \end{matrix}$ (40) It means x^k is the KKT point of (1).

Lemma 3.6. Suppose the Assumption 3.1-3.4 hold, the sequences {ρ_k}, {μ (x^k)}, {ζ_k}, {d^k,0}, {λ^k,0}, {d^k,1}, {λ^k,1}, {r_k} are all bounded.

Proof. The proof is similar to Lemma 3.1 in [13].

Lemma 3.7. Suppose that Assumption 3.1–3.4 hold, if the Algorithm A does not terminate at iteration k, i.e., d^k,1 ≠ 0, then (i) f (x^k) ^Td^k,1 < 0; (ii) c_i (x^k) ≤ ζ_k ∥ ∇ c_i (x^k) ∥ ∇ f (x^k) ^Td^k,1 < 0, i ∈I (x^k).

Proof. (i) By the first formula of the equation (19), we have $\begin{matrix} \nabla f (x^{k})^{T} d^{k, 1} & = (d^{k, 1})^{T} \nabla f (x^{k}) \\ = - (d^{k, 1})^{T} H_{k} d^{k, 0} - (d^{k, 1})^{T} C_{k} λ^{k, 0}, \end{matrix}$ (41) in the same way, by the first formula of the equation (20), we have $\begin{matrix} \nabla f (x^{k})^{T} d^{k, 0} & = - (d^{k, 1})^{T} H_{k} d^{k, 0} - (λ^{k, 1})^{T} C_{k}^{T} d^{k, 0} - \\ (u^{k})^{T} \nabla c (x^{k}) d^{k, 0} \\ = - (d^{k, 1})^{T} H_{k} d^{k, 0} - \\ (u^{k})^{T} \nabla c (x^{k}) d^{k, 0}, \end{matrix}$ (42) combine with (41) and (42), it is obvious that $\begin{matrix} \nabla f (x^{k})^{T} d^{k, 1} & = \nabla f (x^{k})^{T} d^{k, 0} - (d^{k, 1})^{T} C_{k} λ^{k, 0} + \\ (u^{k})^{T} \nabla c (x^{k}) d^{k, 0} \\ = - (d^{k, 0})^{T} H_{k} d^{k, 0} - \\ (d^{k, 1})^{T} C_{k} λ^{k, 0} + (u^{k})^{T} \nabla c (x^{k}) d^{k, 0} \\ = - (d^{k, 0})^{T} H_{k} d^{k, 0} - v_{k}^{T} λ^{k, 0} + \\ (u^{k})^{T} \nabla c (x^{k}) d^{k, 0} \\ = - (d^{k, 0})^{T} H_{k} d^{k, 0} - \sum_{λ_{i}^{k, 0} < 0} (λ_{i}^{k, 0})^{2} + \\ \sum_{λ_{i}^{k, 0} c_{i} (x^{k}) < 0} λ_{i}^{k, 0} c_{i} (x^{k}) + \\ \sum_{λ_{i}^{k, 0} > 0} λ_{i}^{k, 0} \nabla c_{i} (x^{k}) d_{i}^{k, 0}, \end{matrix}$ (43) from the first formula of the equation (19), it holds that $\begin{matrix} (d^{k, 0})^{T} \nabla c (x^{k}) λ^{k, 0} \\ = - (1 - ζ_{k} ∥ \nabla c (x^{k}) ∥ λ^{k, 0}) (d^{k, 0})^{T} \nabla f (x^{k}) - \\ (d^{k, 0})^{T} H_{k} d^{k, 0} \\ = (- ζ_{k} ∥ \nabla c (x^{k}) ∥ λ^{k, 0}) (d^{k, 0})^{T} H_{k} d^{k, 0}, \end{matrix}$ (44) therefore, $\begin{matrix} \sum_{λ_{i}^{k, 0} > 0} λ_{i}^{k, 0} \nabla c_{i} (x^{k}) d_{i}^{k, 0} \\ = \sum_{λ_{i}^{k, 0} > 0} (- ζ_{k} ∥ \nabla c_{i} (x^{k}) ∥ λ_{i}^{k, 0}) (d^{k, 0})^{T} H_{k} d^{k, 0} < 0 . \end{matrix}$ (45)

In view of the definition of v_k, we know that ∇f (x^k) ^Td^k,1 < 0. (ii) For i ∈ I (x^k), we have $v_{i}^{k} \leq 0$ from the definition of $v_{i}^{k}$ and I (x^k) ⊆ W_k. Since d^k-1,1 ≠ 0, we have ζ_k > 0. Together with the second formula of (20) and the conclusion (i) above, it is obvious that $\begin{matrix} \nabla c_{i} (x^{k}) \leq ζ_{k} ∥ \nabla c_{i} (x^{k}) ∥ \nabla f (x^{k})^{T} d^{k, 1} < 0, i \in I (x^{k}) . \end{matrix}$ (46)

Lemma 3.8. Suppose that Assumption 3.1–3.4 hold, if x^k → x^* and ∇f (x^k) ^Td^k,1 → 0 hold, for all k ∈ K, where K is an infinite subset, then x^* is the KKT point of (1).

Proof. According to Lemma 3.6, suppose d^k,0 → d^*,0, λ^k,0 → λ^*,0, ζ_k → ζ_*, k ∈ K. Combine with Lemma 3.7 (i) and Assumption 3.4, we have $\begin{matrix} 0 \leftarrow \nabla f (x^{k})^{T} d^{k, 1} & \leq - (d^{k, 0})^{T} H_{k} d^{k, 0} - \\ \sum_{λ_{i}^{k, 0} < 0} (λ_{i}^{k, 0})^{2} + \\ \sum_{λ_{i}^{k, 0} c_{i} (x^{k}) < 0} λ_{i}^{k, 0} c_{i} (x^{k}) \\ + \sum_{λ_{i}^{k, 0} > 0} λ_{i}^{k, 0} \nabla c_{i} (x^{k}) d_{i}^{k, 0} \\ < 0 . \end{matrix}$ (47) hence, d^k,0 → 0, λ^k,0 → λ^*,0, k ∈ K, $λ_{i}^{*, 0} c_{i} (x^{*}) = 0$ , i ∈ I. Set k ∈ K, passing to the limit in (19), it holds that $\begin{matrix} (1 - ζ_{*} \sum_{i \in W_{k}} λ_{i}^{*, 0} ∥ \nabla c_{i} (x^{*}) ∥) \nabla f (x^{*}) \\ + \sum_{i \in W_{k}} λ_{i}^{*, 0} \nabla c_{i} (x^{*}) = 0; \end{matrix}$ (48)x^* ∈ X since x^* ∈ X. We get from the definition of ${\tilde{v}}^{k}$ that ${\tilde{v}}^{k} \to 0$ and then ζ_k+1 → ζ_* = 0, k ∈ K. Therefore, it follows from (48) and $λ_{i}^{*, 0} \geq 0$ , $λ_{i}^{*, 0} c_{i} (x^{*}) = 0$ , i ∈ I that x^* is the KKT point of (1).

Lemma 3.9. If ∇f (x^k) d^k,1 < 0 for all k, then $f (x^{k}) \leq \bar{f} (x^{k})$ and $h (x^{k}) \leq \bar{h} (x^{k})$ .

Proof. (i) If k = 0, $f (x^{k}) = \bar{f} (x^{k})$ and $h (x^{k}) = \bar{h} (x^{k})$ the conclusion clearly holds. (ii) If k > 0, define two functions F_k : R → R and H_k : R → R by $\begin{matrix} F_{k} (a) = \frac{a \bar{f} (x^{k - 1}) + f (x^{k})}{a + 1}, \\ H_{k} (a) = \frac{a \bar{h} (x^{k - 1}) + h (x^{k})}{a + 1} . \end{matrix}$ (49) Take the derivative of the above formula, we have $\begin{matrix} F_{k}^{'} (a) = \frac{\bar{f} (x^{k - 1}) - f (x^{k})}{(a + 1)^{2}}, \\ H_{k}^{'} (a) = \frac{\bar{h} (x^{k - 1}) - h (x^{k})}{(a + 1)^{2}} . \end{matrix}$ (50) Since h (x^k) = ∑_{i∈W_k} max {c_i (x) , 0} ≥0 and ∇f (x^k) d^k,1 < 0, it can be known from the nonmonotone line search in step 8 of the Algorithm A that $f (x^{k}) \leq \bar{f} (x^{k - 1})$ and $h (x^{k}) \leq \bar{h} (x^{k - 1})$ , so for all a ≥ 0, $\begin{matrix} F_{k}^{'} (a) = \frac{\bar{f} (x^{k - 1}) - f (x^{k})}{(a + 1)^{2}} \geq 0, \\ H_{k}^{'} (a) = \frac{\bar{h} (x^{k - 1}) - h (x^{k})}{(a + 1)^{2}} \geq 0 . \end{matrix}$ (51) That means F_k (a) and H_k (a) are nondecreasing, hence, for all a ≥ 0, we have f (x^k) = F_k (0) ≤ F_k (a) and h (x^k) = H_k (0) ≤ H_k (a).

In particular, let a = 1, then $f (x^{k}) = F_{k} (0) \leq F_{k} (1) = \frac{\bar{f} (x^{k - 1}) + f (x^{k})}{2}$ and $h (x^{k}) = H_{k} (0) \leq H_{k} (1) = \frac{\bar{h} (x^{k - 1}) + h (x^{k})}{2}$ . Therefore, for all k, $f (x^{k}) \leq \bar{f} (x^{k})$ and $h (x^{k}) \leq \bar{h} (x^{k})$ .

Lemma 3.10. Suppose Assumptions 3.1-3.4 hold, the following inequality $\begin{matrix} h (x^{k + 1}) \leq (1 - α) h (x^{k}) + o (α) \end{matrix}$ (52) holds for all k, where α is step size.

Proof. It follows from Assumptions 3.1-3.4, the mean value theorem and the definition of h (x) that

$\begin{matrix} h (x^{k + 1}) \\ = \sum_{i \in I} max {c_{i} (x^{k + 1}), 0} \\ \leq \sum_{i \in I} max {c_{i} (x^{k}) + α \nabla c_{i} (x^{k})^{T} d^{k, 1} + o (α), 0} \\ \leq \sum_{i \in I} max {(1 - α) c_{i} (x^{k}), 0} + \\ \sum_{i \in I} max {α [c_{i} (x^{k}) + \nabla c_{i} (x^{k})^{T} d^{k, 1}] + o (α), 0}, \end{matrix}$ (53) For all k ∈ K, where K is an infinite subset, due to the Lemma 3.3 (ii), there exists a constant δ > 0 such that ∥ ∇ c_i (x^k) ∥ ≥ δ.

Also since 0 > ∇ f (x^k) ^Td^k,1 → ∇ f (x^*) ^Td^*,1, there exists a constant c > 0, such that ∇f (x^k) ^Td^k,1 ≤ - c for a sufficiently large k ∈ K.

So it is known that $\begin{matrix} c_{i} (x^{k}) + \nabla c_{i} (x^{k})^{T} d^{k, 1} \\ = c_{i} (x^{k}) + α (v_{i}^{k} + ζ_{k} ∥ \nabla c_{i} (x^{k}) ∥ \nabla f (x^{k})^{T} d^{k, 1}) \\ \leq c_{i} (x^{k}) + α (v_{i}^{k} - \frac{1}{2} ζ_{*} δ c) \\ = {\begin{matrix} c_{i} (x^{k}) + α λ_{i}^{k, 0} - \frac{1}{2} ζ_{*} δ c α, λ_{i}^{k, 0} < 0, \\ (1 - α) c_{i} (x^{k}) - \frac{1}{2} ζ_{*} δ c α, λ_{i}^{k, 0} c_{i} (x^{k}) < 0, \\ c_{i} (x^{k}) - \frac{1}{2} ζ_{*} δ c α, otherwise . \end{matrix} \\ \leq 0 \end{matrix}$ (54) Therefore, combined with (53), (54) and the definition of h (x), we have (52) holds.

Theorem 3.1. Suppose Assumption A3.1-A3.4 hold, then Algorithm A either terminates in finite steps, or produces an infinite sequence {x^k, μ (x^k)}, which exists accumulation point be the KKT pair of (1).

Proof. Since ζ_k is monotonic and bounded, suppose ζ_k → ζ_* ≥ 0.

Case I: ζ_* > 0.

There exists a infinite subset K, we have $ζ_{k} \geq \frac{1}{2} ζ_{*}$ for all k ∈ K large enough.

Suppose x^* is not a KKT point of (1), we first show by contradiction that ∇f (x^k) ^Td^k,1 → 0, k ∈ K. From ∇f (x^k) ^Td^k,1 < 0 and ∇f (x^k) ^Td^k,1 → ∇ f (x^*) ^Td^*,1, for all k ∈ K large enough, there exists a constant c > 0 such that $\begin{matrix} \nabla f (x^{k})^{T} d^{k, 1} \leq - c . \end{matrix}$ (55)

For a given $η_{1} \in (0, \frac{1}{2})$ , (i) If min {∇ f (x^k) ^Td^k,1, - h (x^k)} = ∇ f (x^k) ^Td^k,1, then from Lemma 3.9, for k ∈ K large enough and α > 0 small enough, we have $\begin{matrix} f (x^{k} + α d^{k, 1} + α^{2} d^{k, 2}) - max_{0 \leq j \leq m (k) - 1} \bar{f} (x^{k - j}) - \\ η_{1} α \nabla f (x^{k})^{T} d^{k, 1} \\ \leq f (x^{k} + α d^{k, 1} + α^{2} d^{k, 2}) - f (x^{k}) - \\ η_{1} α \nabla f (x^{k})^{T} d^{k, 1} \\ = (1 - η_{1}) α \nabla f (x^{k})^{T} d^{k, 1} + o (α) \\ \leq - (1 - η_{1}) c α + o (α) \leq 0, \end{matrix}$ (56) where m (0) =0 and 0 ≤ m (k) ≤ min {m (k - 1) +1, M}, M is a positive constant. (ii) If min {∇ f (x^k) ^Td^k,1, - h (x^k)} = - h (x^k), that is ∇f (x^k) ^Td^k,1 ≥ - h (x^k), so h (x^k) ≥ c, then from Lemma 3.9, for k ∈ K large enough and α > 0 small enough, we have $\begin{matrix} f (x^{k} + α d^{k, 1} + α^{2} d^{k, 2}) - max_{0 \leq j \leq m (k) - 1} \bar{f} (x^{k - j}) \\ - η_{1} α \nabla f (x^{k})^{T} d^{k, 1} \\ \leq f (x^{k} + α d^{k, 1} + α^{2} d^{k, 2}) - f (x^{k}) + η_{1} α h (x^{k}) \\ = α \nabla f (x^{k})^{T} d^{k, 1} + η_{1} α h (x^{k}) + o (α) \\ = α (- c + η_{1} h (x^{k})) + o (α) \leq 0, \end{matrix}$ (57) where m (0) =0 and 0 ≤ m (k) ≤ min {m (k - 1) +1, M}, M is a positive constant. Therefore, the first formula of (24) holds for k ∈ K large enough, α > 0 small enough and η₁ > 0 small enough.

Next, we prove that the second formula of (24) holds for k ∈ K large enough, α > 0 small enough and η₂ > 0 small enough.

For a given $η_{2} \in (0, \frac{1}{2})$ , (i) If min {- αh (x^k) , - α²θ_k} = - αh (x^k), where θ_k = γ ∥ d^k,1 ∥ ² + (1 - γ) ∥ λ^k,0 ∥ ², γ ∈ [0, 1] then from Lemma 3.9, Lemma 3.10 and h (x^k) ≥0,for k ∈ K large enough and α > 0 small enough, we have $\begin{matrix} h (x^{k} + α d^{k, 1} + α^{2} d^{k, 2}) - max_{0 \leq j \leq m (k) - 1} \bar{h} (x^{k - j}) + \\ η_{2} α h (x^{k}) \\ \leq h (x^{k} + α d^{k, 1} + α^{2} d^{k, 2}) - h (x^{k}) + η_{2} α h (x^{k}) \\ \leq - (1 - η_{2}) α h (x^{k}) + o (α) \leq 0, \end{matrix}$ (58) where m (0) =0 and 0 ≤ m (k) ≤ min {m (k - 1) +1, M}, M is a positive constant. (ii) If min {- αh (x^k) , - α²θ_k} = - α²θ_k, where θ_k = γ ∥ d^k,1 ∥ ² + (1 - γ) ∥ λ^k,0 ∥ ², γ ∈ [0, 1] then from Lemma 3.9, Lemma 3.10 and h (x^k) ≥0, for k ∈ K large enough and α > 0 small enough, we have $\begin{matrix} h (x^{k} + α d^{k, 1} + α^{2} d^{k, 2}) - max_{0 \leq j \leq m (k) - 1} \bar{h} (x^{k - j}) + \\ η_{2} α^{2} θ_{k} \\ \leq h (x^{k} + α d^{k, 1} + α^{2} d^{k, 2}) - h (x^{k}) + η_{2} α^{2} θ_{k} \\ = (1 - α) h (x^{k}) - h (x^{k}) + η_{2} α^{2} θ_{k} + o (α) \\ = - α [h (x^{k}) - η_{2} α θ_{k}] + o (α) \leq 0, \end{matrix}$ (59) where m (0) =0 and 0 ≤ m (k) ≤ min {m (k - 1) +1, M}, M is a positive constant.. Therefore, for k ∈ K large enough, α > 0 small enough and η₁ > 0 small enough, the first formula of (24) holds.

Case II: ζ_* = 0. By the definition of ρ_k, Lemma 3.3 and the boundedness of {x_k}, we know that there exists a constant ρ > 0 such that ρ_k ≥ ρ for all k large enough. Since ζ_* = 0, we get from the definition of ζ_k that $ζ_{k} = ∥ d^{k - 1, 0} ∥^{t_{1}} + ∥ {\tilde{v}}^{k - 1} ∥^{t_{2}}, k \in K$ , that is d^k-1,0 → 0, ${\tilde{v}}^{k - 1} \to 0$ . Suppose x^k-1 → x^*, k ∈ K, hence, based on Lemma 3.7 and the definition of ${\tilde{v}}^{k}$ , we have $\begin{matrix} \nabla f (x^{k - 1})^{T} d^{k - 1, 0} \\ \leq - (d^{k - 1, 0})^{T} H_{k} d^{k - 1, 0} - \sum_{λ_{i}^{k - 1, 0} < 0} (λ_{i}^{k - 1, 0})^{2} \\ + \sum_{λ_{i}^{k - 1, 0} c_{i} (x^{k - 1}) < 0} λ_{i}^{k - 1, 0} c_{i} (x^{k - 1}) \\ + \sum_{λ_{i}^{k - 1, 0} > 0} λ_{i}^{k - 1, 0} \nabla c_{i} (x^{k - 1}) d_{i}^{k - 1, 0} \\ \to 0, \end{matrix}$ (60) so it holds that x^* is a KKT point of (1) by Lemma 3.8.

Therefore, there exists a constant α_*, such that the step size α_k ≥ α_* for all k ∈ K, together with (55) and the first formula of (24), it holds that $\begin{matrix} f (x^{k} + α d^{k, 1} + α^{2} d^{k, 2}) - \\ max_{0 \leq j \leq m (k) - 1} \bar{f} (x^{k - j}) \\ \leq η_{1} α_{k} min {\nabla f (x^{k})^{T} d^{k, 1}, - h (x^{k})} \\ \leq - η_{1} α_{*} c, \end{matrix}$ (61) for x^k → x^*, k ∈ K, it follows from $\begin{matrix} lim_{k \in K} max_{0 \leq j \leq m (k) - 1} \bar{f} (x^{k - j}) = lim_{k \in K} f (x^{k}) = f (x^{*}) \end{matrix}$ (62) that $lim_{k \to \infty} max_{0 \leq j \leq m (k) - 1} \bar{f} (x^{k - j}) = lim_{k \to \infty} f (x^{k}) = f (x^{*})$ . Taking limit on both sides of inequality (61) for k∈ K, k → ∞, we have -η₁α_*c ≥ 0, which is a contradiction with η₁ > 0, α_* > 0, c > 0, thus Lemma 3.8 holds, which means x^* is a KKT point of (1).

4 Numerical results

In this section, we will report some numerical results. Algorithm A is implemented in the environment of MATLAB R2016a. We give our preliminary results on the some test problems from Hock and Schittkowski [24], compared with the algorithm in [7] which is used filter technique, the algorithm in [21] which is used monotone line search and that in Matlab.

The results are summarized in Table 1. The details about the implementation are described as follows. (a) The parameter values as chosen as follows: t₁ = t₂ = 2, η₁ = η₂ = 0.2, ɛ₀ = 1, β = 0.8, γ = 0.5, M = 10. (b) The meanings of some notations in Table 1 are described as follows: No: the problem number given in Hock and Schittkowski [24];

n: the number of variables;

m: the number of constraints;

NIT: the number of iterations;

NF: the number of evaluations for f (x);

NG: the number of evaluations for c (x).

(d) H_k is updated by the damped BFGS formula.

From Table 1, we can see that for most examples, the numerical can be found the optimal solution through finite iteration in this paper. Comparing with the algorithms that Wang et al. [7], Li et al. [21] and the optimization code in Matlab (column ’MATLAB’), greatly improvement both in NIT and in NF/NG. Especially, some problems can be solved easily in Algorithm A while are unsolvable in other algorithm.

Table 1

The numerical comparison of different algorithms

			Algorithm A			Algorithm in [7]			Algorithm in [21]			Matlab
No	n	m	NIT	NF	NG	NIT	NF	NG	NIT	NF	NG	NIT - NF
HS1	2	1	9	26	17	23	48	54	-	-	-	27 - 95
HS3	2	1	11	34	23	13	19	23	2	2	2	4 - 15
HS4	2	2	3	10	7	2	4	2	3	4	3	2 - 6
HS5	2	4	3	7	4	10	12	31	21	59	21	10 - 34
HS9	2	1	9	19	10	14	51	14	6	6	6	6 - 31
HS12	2	1	6	13	7	10	12	10	27	31	27	8 - 25
HS28	3	1	8	30	22	17	33	40	7	17	7	7 - 29
HS29	3	1	6	22	16	9	27	25	38	164	38	12 - 49
HS30	3	7	9	32	23	6	11	20	18	18	18	11 - 44
HS33	3	6	2	4	3	3	13	22	3	3	3	5 - 20
HS35	3	4	24	94	70	14	43	59	15	18	15	6 - 24
HS36	3	7	4	16	12	8	24	33	5	20	5	2 - 8
HS37	3	8	2	11	9	12	27	25	5	10	5	9 - 40
HS43	4	3	7	18	11	12	22	17	8	57	8	12 - 63
HS44	4	10	5	21	16	9	17	39	7	7	7	79 - 402
HS46	5	2	7	21	14	13	57	83	15	15	15	12 - 75
HS47	5	3	14	144	130	33	61	34	38	91	38	28 - 335
HS48	5	2	7	45	38	14	24	14	42	149	42	8 - 50
HS49	5	2	14	31	17	103	198	213	25	26	25	19 - 117
HS50	5	3	50	103	53	115	167	132	56	279	56	10 - 84

To show the performance profile of the number of iterations of the proposed method, we provide Fig 1 as follows, in which the horizontal axis represents the problem and the vertical axis represents the number of iterations, the red circles represent the number of the iteration that computed by our method, blue ones the number of iteration by Algorithm in [7], yellow ones the number of iteration by Algorithm in [21], greens ones the number of iteration by Algorithm in Matlab.

Fig. 1

The number of iteration in different algorithms.

From the Fig 1, it is obviously that the red ones are in the lowest places compared with those yellows one, blue ones and green ones, that means the number of the iteration by Algorithm A is less than that by other methods. Furthermore, the proposed algorithm has few parameters and is easy to implement. Therefore, our algorithm is effective and has numerical promising.

Footnotes

Acknowledgement

This work was supported by the National Natural Science Foundation of China (No. 61572011), Hebei Province Nature Science Foundation of China (A2018201172), and the Key Research Foundation of Education Bureau of Hebei Province (No. ZD2015069).

References

Wilson

R.B.

, A simplicial algorithm for concave programming, PhD thesis, Graduate School of Business Administration, Harvard University, 1963.

Huang

M.X.

and Pu

D.G.

, A line search SQP method without a penality or a filter, Computational and Applied Mathematics 34(2) (2015), 741–753.

Kostreva

M.M.

and Chen

, A superlinearly convergent method of feasible directions, Applied Mathematics and Computation 116(3) (2000), 231–244.

Jian

J.B.

, Zheng

H.Y.

, Hu

Q.J.

and Tang

C.M.

, A new normrelaxed method of strongly sub-feasible direction for inequality constrained optimization, Applied Mathematics and Computation 168(1) (2005), 1–28.

Panier

E.R.

, Tits

A.L.

and Herskovits

J.N.

, A QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM Journal on Control and Optimization 26(4) (1988), 788–811.

H.D.

and Qi

L.Q.

, A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM Journal on Optimization 11(1) (2000), 113–132.

Wang

, Liu

, Gu

and Pu

D.G.

, An infeasible activeset QP-free algorithm for general nonlinear programming, International Journal of Computer Mathematics 94(5) (2017), 884–901.

Jian

J.B.

, Zeng

H.J.

, Ma

G.D.

and Zhu

Z.B.

, Primal-dual interior point QP-free algorithm for nonlinear constrained optimization, Journal of Inequalities and Applications 239(1) (2017), 1–25.

Gao

Z.Y.

, He

G.P.

and Wu

, Sequential systems of linear equations algorithm for nonlinear optimization problems with general constraints, Journal of Optimization Theory and Applications 95(2) (1997), 371–397.

10.

Sasan

and Andrĺę

L.T.

, A simple primal-dual feasible interior-point method for nonlinear programming with monotone descent, Comput Optim Appl 25(1) (2003), 17–38.

11.

Andrĺę

L.T.

, Wachter

and Sasan

, A primal-dual interiorpoint method for nonlinear programming with strong global and local convergence properties, SIAM J Optim 14(1) (2003), 173–199.

12.

Zhu

, An interior point type QP-free algorithm with superlinear convergence for inequality constrained optimization, Appl Math Modelling 31(6) (2007), 1201–1212.

13.

Jian

J.B.

, Han

D.L.

and Xu

Q.J.

, A new sequential systems of linear equations algorithm of feasible descent for inequality constrained optimization, Acta Mathematica Sinica 26(12) (2010), 2399–2420.

14.

Wang

, Chen

and He

, Sequential systems of linear equations method for general constrained optimization without strict complementarity, J Comput Appl Math 182(2) (2004), 447–471.

15.

Fletcher

and Leyffer

, Nonlinear programming without a penalty function, Mathematical Programming 91(2) (2002), 239–269.

16.

Wchter

and Biegler

L.T.

, Line search filter methods for nonlinear: Global convergence, SIAM Journal on Optimization 16(1) (2005), 32–48.

17.

Shen

C.G.

, Leyffer

and Fletcher

, A nonmonotone filter method for nonlinear optimization, Computational Optimization and Applications 52(3) (2012), 583–607.

18.

Zhou

and Pu

D.G.

, A new QP-free feasible method for inequality constrained Optimization, Operations Research Transactions 11(3) (2007), 31–43.

19.

Liu

W.A.

, Shen

C.G.

, Zhu

X.J.

and Pu

D.G.

, An infeasible QP-free algorithm without a penalty function or a filter for nonlinear inequality-constrained optimization, Optimization Methods and Software 29(6) (2014), 1238–1260.

20.

Dennis

J.E.

Jr and Schnabel

R.B.

, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Englewoood Cliffs, NJ, 1983. Reprinted by SIAM Publications, 1993.

21.

J.L.

and Yang

Z.P.

, A QP-free algorithm without a penalty or a filter for nonlinear general-constrained optimization, Applied Mathematics and Computation 316(1) (2018), 52–72.

22.

Grippo

, Lampariello

and Ludidi

, A nonmonotone line search technique for Newton’s method, SIAM Journal on Numerical Analysis 23(4) (1986), 707–716.

23.

Shen

C.G.

, Xue

W.J.

and Pu

D.G.

, An infeasible nonmonotone SSLE algorithm for nonlinear programming, Journal of Mathmatical Metnod Operation Research 71(1) (2010), 103–124.

24.

Hock

and Schittkowski

, Test examples for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin Heidelberg New York, 1981.