A Superlinearly and Quadratically Convergent SSLE Algorithm for Optimization Problems without Strict Complementarity^{1}

Jin-bao Jian^{2}

(Department of Mathematics and Information Science, Guangxi University, China)

Abstract In this paper, a new algorithm of sequential systems of linear equations (SSLE) for nonlinear inequality constrained optimization problems is presented. At each iteration, the algorithm solves only one system of linear equations or compute a generalized gradient projection, where the approximate Hessian of the Lagrange function need not be positive definite. Under weak assumptions without the strict complementarity, the algorithm possesses global and strong convergence, superlinear and quadratic convergence.

Keywords. Inequality constraints, optimization problems, SSLE, generalized projection, global and strong convergence, superlinear and quadratic convergence.

AMS subject classification 90C, 65K.

1. Introduction

Since the sequential quadratic programming (SQP) algorithms possess fast convergence, it is one of the most effective methods for solving nonlinear constrained optimization, and the researches on this object are more active. But in order to avoid the Maratos effect and obtain superlinear convergence, most previous results, Refs. [1]– [8] for examples, need make a strict complementarity hypothesis on the problems which is hard to be tested. Bonnas and Launay [9](1995) and Facchinei [10](1997) presented respectively superlinearly convergent algorithms without the strict complementarity, where two or one quadratic programming were solved at each iteration. For overcoming the shortcoming of large amount of computation for solving quadratic programming of SQP type methods, a kind of superlinealy convergent SSLE algorithms are depply studied in recent years [11]– [15], however the superlinear convergence properties of these algorithms still depend on the strict complementarity. Facchinei and Lucidi [16](1995), Jian [17](1996) studied respectively SSLE algorithms for inequality and general constrained optimization problems without the strict complementarity, but their convergence results were only local. In order to overcome the previous algorithms’ shortcoming of large amount of computation, strong hypotheses, local convergence and so on, this paper presents a new SSLE algorithm for nonlinear inequality constrained optimization, it has the main features as follows. It solves only one system of linear equations or computes only one generalized projection at each iteration; it does not require the approximate Hessian of the Lagrange function to be positive definite; the object function is used as the effect function and Armijo linear search to is used to yield the step size, moreover, it uses directly the quasi Newton technique to generate the step size 1 when k large enough; it possesses global and strong convergence, superlinear and quadratic convergence.

1This work was supported by the National Natural Science Fundation (19801009) of China

2Professor, Ph. D, Department of Mathematics and Information Science, Guangxi University, Nanning 530004, P.R. China. E-mail: jianjb@gxu.edu.cn .

2. Algorithm

We consider the inequality constrained optimization problem

min{f_{0}(x) : f_{j}(x) ≤ 0, j ∈ I = {1, ⋯, m}}.  (1)

Denote

X = {x ∈ ℜ^{n} : f_{j}(x) ≤ 0, j ∈ I}, I^{0} = {0, 1, 2, ⋯, m}, I(x) = {j ∈ I : f_{j}(x) = 0} for x ∈ X.

Assumption (A1). (i) Functions f_{j} (j ∈ I^{0}) are continuously differentiable.

Assumption (A2). ∀x ∈ X, the vectors {∇f_{j}(x), j ∈ I(x)} are linearly independent.

In this paper, the following notation and definitions are used.

g_{j}(x) = ∇f_{j}(x), D_{j}(x) = f_{j}(x)^{2}, j ∈ I^{0}, D(x) = diag(D_{j}(x), j ∈ I), e = (1, ⋯, 1)^{T} ∈ ℜ^{m}, (2)
L(x, u) = f_{0}(x)+ ∑_{j∈I} u_{j}f_{j}(x), N(x) = (g_{j}(x), j ∈ I), Q(x) = (N(x)^{T} N(x)+D(x))^{−1}N(x)^{T} , (3)
A_{J}(x) = (g_{j}(x), j ∈ J ⊆ I), P (x) = E_{n} − N(x)Q(x), π(x) = −Q(x)g_{0}(x),  (4)
ω(x) = ∑_{j∈I} max\{−π_{j}(x), π_{j}(x)f_{j}(x)^{2}\}, ρ(x) = \frac{∥P (x)g_{0}(x)∥^{2} + ω(x)}{1 + |e^{T} π(x)|},  (5)
q(x) = ρ(x) \{−P (x)g_{0}(x) + Q(x)^{T} [v(x) + \frac{ρ(x)}{2(1 + |e^{T} π(x)|)}e]\} ,  (6)
v_{j}(x) = −1 − ρ(x), if π_{j}(x) < 0; v_{j}(x) = f_{j}(x)^{2} − ρ(x), ifπ_{j}(x) ≥ 0.  (7)

For a given approximate solution x^{k} and its associated approximation multiplier u^{k} = (u_{j}^{k}, j ∈ I), define a approximately active constraint set J_{k} by

J_{k} = J(x^{k}) = {j ∈ I : f_{j}(x^{k}) ≥ −u_{j}^{k}}.  (8)

Algorithm A. Step 0. Choose parameters δ_{1} > 0, σ_{1} > 0, γ, α, β ∈ (0, 1), u^{1} = (u_{j}^{1}, j ∈ I). Select a feasible starting point x^{1} ∈ X and an initial matrix B_{1},let k = 1, l_{1} = 1.

Step 1. If k = l_{k}, then go to Step 3, otherwise compute J_{k} and matrix A_{k} = A_{J_{k}}(x^{k}), and solve the system of linear equations

( \begin{matrix}B_{k} & A_{k} \\ A_{k}^{T} & 0 \end{matrix} ) ( \begin{matrix}d \\ u \end{matrix} ) = − ( \begin{matrix}g_{o}(x^{k}) \\ f_{J_{k}}(x^{k}) \end{matrix} )  (9)

to obtain a solution(d_{0}^{k}, ũ^{k+1}), where f_{J_{k}}(x^{k}) = (f_{j}(x^{k}), j ∈ J_{k}). If d_{0}^{k} = 0, ũ^{k+1} ≥ 0 and x^{k} ∈ X, then x^{k} is a K-T point of (1), stop.

Step 2. Let

y^{k+1} = x^{k} + d_{0}^{k}, u^{k+1} = (ũ^{k+1}, 0_{I\J_{k}}).  (10)

If

∥y^{k+1} − x^{k}∥ ≤ σ_{k}γ^{(k−l_{k}−1)}, u_{j}^{k+1} ≥ −σ_{k}γ^{(k−l_{k}−1)}, j ∈ I,  (11)

then let

x^{k+1} = y^{k+1} = x^{k} + d_{0}^{k}, (δ_{k+1}, σ_{k+1}, l_{k+1}) = (δ_{k}, σ_{k}, l_{k});  (12)

otherwise let

x^{k+1} = x^{l_{k}+1}, (δ_{k+1}, σ_{k+1}, l_{k+1}) = \{ \begin{matrix}(δ_{k}, γδ_{k}, k + 1), & if k ≥ l_{k} + 2; \\ (δ_{k}, σ_{k}, k + 1), & if k < l_{k} + 2. \end{matrix}  (13)

Go to Step 4.

Step 3. Compute the direction q^{k} = q(x^{k}) according to (6). If ρ_{k} = ρ(x^{k}) = 0, then x^{k} is a K-T point of (1), stop; otherwise find the first number λ_{k} of sequence {1, β, β^{2}, ⋯} satisfying

f_{0}(x^{k} + λq^{k}) ≤ f_{0}(x^{k}) + αλg_{0}(x^{k})^{T} q^{k}, f_{j}(x^{k} + λq^{k}) ≤ 0, j ∈ I,  (14)

and let

\begin{matrix}x^{k+1} = x^{k} + λ_{k}q^{k}, u^{k+1} = π^{k} = π(x^{k}), \\ (δ_{k+1}, σ_{k+1}, l_{k+1}) = \{ \begin{matrix}(γδ_{k}, σ_{k}, k), & if ∥x^{k+1} − x^{k}∥ ≤ δ_{k}; \\ (δ_{k}, σ_{k}, k + 1), & if ∥x^{k+1} − x^{k}∥ > δ_{k}. \end{matrix} \end{matrix}  (15)

Step 4. Generate a new matrix B_{k+1} by some given method, let k := k + 1, go to Step 1.

3. Global convergence and rate of convergence

For convenience, we denote cycle Steps 1–2–3–4–1 by cycle A, cycle Steps 1–2–4–1 by cycle B, and divide the iterative index set by

Z_{1} = {k : the k − th iteration takes in cycle A}, Z_{2} = {k + 1 : k ∈ Z_{1}, ∥x^{k+1} − x^{k}∥ ≤ δ_{k}}, (16)
Z_{3} = {k + 1 : the k − th iteration takes in cycle B and (11) holds},  (17)

Assumption (A3). If an infinite index set K satisfies that k ⊆ Z_{3}, J_{k−1} ≡ J, ∀k ∈ K, and {x^{k−1}}_{k∈K} is convergent, then {B_{k−1}}_{k∈K} is bounded.

Theorem 1. Suppose that the assumptions (A1), (A2) and (A3) hold, then the proposed Algoritnm A either stops at a K-T point of problem (1) in a finite number of iteration, or produces an infinite sequence x^{k} such that any accumulation point x^{∗} of {x^{k}} is a K-T point of problem (1).

Assumption (A4). Functions f_{j}(x) (j ∈ I^{0}) are second order continuously differentiable, the sequence {x^{k}} of points generated by Algorithm A is bounded, and has an accumulation point x^{∗} (then x^{∗} is a K-T point by Theorem 1) such that the strong second order sufficient conditions for optimality hold at K-T pair (x^{∗}, u^{∗}).

Assumption (A5). Suppose that ∥(B_{k} − ∇_{xx}^{2}L(x^{k}, u^{k})) d_{0}^{k}∥ = o(∥d_{0}^{k}∥.

Theorem 2. Suppose that the assumptions (A2)–(A4) hold, then we have

(i) lim_{k→∞} x^{k} = x^{∗}, i.e., Algorithm A is strongly convergent.

(ii) Assume in addition that (A5) hold, then Algorithm A is superlinearly convergent, i.e.,

∥x^{k+1} − x^{∗}∥ = o(∥x^{k} − x^{∗}∥), and lim_{k→∞}(x^{k}, u^{k}) = (x^{∗}, u^{∗}).

Theorem 3. Suppose that the assumptions (A2)–(A4) hold, f_{j}(x) ∈ C^{3}, j ∈ I^{0}, we have (i) If the matrix B_{k} in Algorithm A is computed by B_{k} = ∇_{xx}^{2}L(x^{k}, u^{k}), then the proposed

Algorithm A is superlinearly convergent, moreover the sequence {(x^{k}, u^{k})} of points converges quadratically to (x^{∗}, u^{∗}).

(ii) If the matrix B_{k} in Algorithm A is computed by B_{k} = ∇_{xx}^{2}L(x^{k}, μ(x^{k})), then the proposed Algorithm A is quadratically convergent, i.e., ∥x^{k+1} − x^{∗}∥ = O(∥x^{k} − x^{∗}∥^{2}), where approximate multiplier function μ(x) is defined by

μ(x) = −M(x)^{−1}N(x)^{T} g_{0}(x), M(x) = N(x)^{T} N(x) + D(x) + { ∑_{j∈I} [max{0, f_{j}(x)}]^{3}} E_{m}.

References

[1] D.Q. Magne, E. Polak, A superlinearly convergent algorithm for constrained optimization problems, Mathematical Programming Study,16(1982), pp. 45–61

[2] P.T. Boggs, J.W. Tolle, P. Wang, On the local convergence of quasi-Newton methods for constrained optimization, SIAM J. Control and Optimization,20(1982), pp. 161–171

[3] M.C. Biggs, On the convergence of some constrained minimization algorithm based on recursive quadratic programming, J. of Institute of Mathematics and Its Application,21(1979), pp. 67–82

[4] M. Fukushima, A successive quadratic programming algorithm with global and superlinear convergence properties, Maththematical Programming, 35(1986), pp. 253–264

[5] E.P. Panier, A.L. Tits, A superlinearly convergent feasible method for the solution of inequality constrained optimization problems, SIAM J Control and Optimization,25(1987), pp. 934–950

[6] J.B. Jian, A subfeasible direction method combining SQP technique with generalized projection, Appl. Math.–A Journal of Chinese Universities (Ser. A),11(1)(1996), pp. 65–74

[7] Z. Y. Gao, F. Wu, A superlinearly feasible method for nonlinear constraints, Acta Mathematica Sinica (Ser. A), 40(6)(1997), pp. 896–900

[8] G.P. He, B.Q. Diao, Z.Y.Gao, An SQP algorithm with nonmonotone linear search for general nonlinear constrained optimization problems, J. of Computational Mathematics,15(2)(1997), pp. 179–192

[9] J.F. Bonnans, G. Launay, Sequential quadratic programming with penalization the displacement, SIAM J Optimization, 54(1995), pp. 796–812

[10] F. Facchinei, Robust recursive quadratic programming algorithm model with global and superlinear convergence properties, J. Optimization Theory and Its Applications, 92(1997),pp. 543–579

[11] E.R. Panier, A.L. Tits, J.N. Hersrovits. A QP free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM J Control and Optimization,26(1988), pp. 788–811

[12] Z.Y. Gao, F. Wu, Y.L. Lai, A superlinearly convergent algorithm of sequential systems of equations for nonlinear optimization, Chinese Science Bulletin,39(9)(1994), pp. 774–777

[13] Z.Y. Gao, G.P. He, F. Wu, An algorithm of sequential systems of equations with arbitrary initial point, Since in China (Ser. A), 27(1)(1997), pp. 24–33

[14] J.B. Jian, A generalized projection–successive lineer equations algorithm for nonlinear equality and inequality constrained optimization and its rate of convergence, Appl. Math.–A Journal of Chinese Universities (ser.B),12(4)(1997), pp. 343–354

[15] Z.Y. Gao,G.P. He, F. Wu, Sequential systems of linear equations algorithm for nonlinear optimization problems with general constraints, J. OptimizationTheory and Its Applications, 95(1997), pp. 371–397

[16] F. Facchinei, S. Lucidi, Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems, J. Optimization Theory and Its Applications, 85(1995), pp. 265–289

[17] J.B. Jian, Quadratically and superlinearly convergent algorithm for equality and inequality constrained optimization based on solutions of successive linear equations, Journal of Basic Science and Engineering (PRC), 4(3)(1996), pp. 223–230