ABSTRACT
In this study, by using the technique of the projection and the idea of the conjugate projection, a new algorithm is presented to solve the linear equality and inequality constrained optimization. Under some suitable conditions which are weaker than those in corresponding references, it is proved that the proposed method is global convergence as well as superlinear convergence.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/jas.2006.1085.1089
URL: https://scialert.net/abstract/?doi=jas.2006.1085.1089
INTRODUCTION
We consider the following linear constrained optimization:
(1) |
where:
Since the gradient projection method was proposed by Rosen (1960), it become one of basic methods to solve nonlinear programming, and some authors were absorbed in research on this method (Zhang, 1979; Jian and Zhang, 1999). However, being lack of the information of twice derivatives, this type of methods converges slowly.
In order to quicken the rate of convergence, recently, it is arisen some improved algorithms (Han, 1976; Panier and Tits, 1987; Facchinel and Lucidi, 1995). In two references (Shi, 1996; Zhang and Wang, 1999) by generalizing the conjugate projection from the gradient projection, a new projection variable metric algorithm is presented which is combined the penalty function method with the variable metric algorithm. While, even under some strong conditions (for example, the sequence {xk} converges to the optimum solution {uk} and the corresponding multiplier vector sequence {uk} converges to the optimum multipliers u*), it is only proved that the sequence {xk, uk} converges superlinearly to (x*, u*), instead of the sequence {xk} itself.
In this study, by taking advantage of the projection gradient technique, a new general projection gradient method is present to improve those methods (Shi, 1996; Zhang and Wang, 1999). Under some weaker suitable conditions, it is proved that the sequence {xk} generated by the algorithm is superlinear convergent to the optimum solution x*.
DESCRIPTION OF ALGORITHM
The following assumptions are true throughout the study.
H 1: The feasible set X ≠ Ø and the function f0(x) is twice differentiable;
H 2: ∀x ∈ X vectors {aj, j ∈ I(x)∪ E} are linear independent.
Definition 1: The function μ(x): Rn → Rm is called a multiplier function, if μ(x) is continuous and μ(x*) is the corresponding K-T multiplier vector for the K-T point x* of (1).
For the current approximate solution xk ∈ X, σk>0, a positive definite matrix Bk = B(xk), the set Lk ⊆ IUE, we define:
(2) |
(3) |
Consider the following auxiliary problem:
(4) |
Where
define the directional derivative along dat xas follows:
It is easy to see that
The following algorithm is proposed for solving problem (1):
Algorithm A
Step 0:
Step 1: Let i = 0, σk,i = σ0
Step 2: If det and go to Step 4, otherwise, go to Step 3,where
Step 3: Let i = i + 1, σk,i = 1/2σk,i-1, go to step 2.
Step 4: Compute
Step 5: Compute dk0. If dk0 = 0, STOP; Otherwise, compute dk0. If
(5) |
go to Step 6, otherwise goto Step 7;
Step 6: Let λ= 1.
1) If
(6) |
set λk = λ, go to Step 8, otherwise go to 2).
2) Let λ = 1/2λ. If λ<∈, go to Step 7, otherwise go to 1) of Step 6.
Step 7: Compute
(8) |
Find out βk, the first number β in the sequence {1, 1/2, 1/4, ...} satisfying
(9) |
(10) |
Set dk = qk, λk = βk.
Step 8: Obtain Bk+1 by updating the positive definite matrix Bk using some quasi-Newton formulas. Set
Set k = k + 1. Go back to Step 1.
CONVERGENCE OF ALGORITHM
Here, firstly, it is shown that Algorithm A is well defined.
H 3: The sequence {xk} is bounded, and the sequence {Bk} is positive definite.
Lemma 1: For any iteration, there is no infinite cycle between Step 1 and Step 3. Moreover, if then there exits a constant , such that for k ∈ K, k large enough.
Proof: The proof is refereed to Lemma 1 in reference (Zhu et al., 2003).
Theorem 1: ∀k, if dk0 = 0, then xk is a K-T point of (1), else, it holds that
(11) |
Proof: Firstly, it is easy to see that
If dk0 = 0, it holds that
0 = ATkdk0 = Vk, Pk∇f0 (xk) = 0 |
So, form (2), (3) and H 3, we have
which shows that xk is a K-T point of (1).
If dk0 = 0, form the definition of Vk, it is obvious that
So, it holds that
Form the definition of ck, it holds that DGck (xk , dk0) < 0 since ATkdk0 = Vk, it holds that
So, we have
The conclusion holds.
Lemma 2: There exists a constant k0, such that .
In the sequel , we always assume that ck ≡ c.
Theorem 2: The algorithm either stops at the K-T point xk of the problem (1) in finite iteration, or generates an infinite sequence {xk}, any accumulation point x* of which is a K-T point of the problem (1).
Proof: The first statement is obvious, the only stopping point being step 5. Thus, suppose that {xk}k∈K → x*, dk0 → 0, k ∈ K. From (5), (6), (9) and Theorem 1, it is easy to see that {Gc (xk)} is decreasing. So, it holds that
(12) |
If there exists K1 ⊆ K (|K1| = ∞), such that for all k ∈ K1, xk+1 = xk + λkdk is generated by step 6 and step 8, then from (5), (6), we get
So, dk0 → 0, k ∈ K1 since dk0 → d*0, k ∈ K it is clear that d*0 = 0 i.e., dk0 → 0, k ∈ K. So, according to Theorem 1, it is obvious that xk is a K-T point of (1).
Now, we might as well assume that, for all k ∈ K, xk+1 = xk + λkdk is generated for by step 7 and step 8, Suppose that the desired conclusion is false, i.e., dk0 ≠ 0. Imitating the proof of Theorem 1,we have DGc (x*, q*)<0 and we can conclude that the step-size βk obtained by the linear search in step 7 is bounded away from zero on K, i.e.,
βk≥β* = inf {βk, k ∈ K}>0, k ∈ K |
So, from (9) and Theorem 1, it holds that
It is a contradiction, which shows that dk0 → 0, k ∈ K, k → ∞ . So, according to Theorem 1. It is easy to see that xk is a K-T point of (1).
In order to obtain superlinear convergence, we also make the following additional assumptions.
H 4: The sequence generated by the algorithm possesses an accumulation point x*.
H 5: Bk → B*, k → ∞.
H 6: The second-order sufficiency conditions with strict complementary slackness are satisfied at the K-T point x* and the corresponding multiplier vector u*.
According to Lemma 5 in reference (Zhu, 2005), we have the following conclusion.
Lemma 3: The entire sequence {xk} converges to x*, i.e., xk → x*, k → ∞ and for k large enough , it holds that
Lemma 4: Denote ék = πk + (ATkB-1k Ak)-1 F(xk). Under above mentioned conditions, for k large enough , it holds that
∇f0(xk) + Bkdk0 + Akék = 0, F(xk) + ATkdk0 |
Proof: According to Lemma 3 and H 6, it holds, for k large enough, that πk>0. So, from the definition of Vk, we have
ATkdk0 = Vk = -F(xk), F(xk) + ATkdk0 = 0 |
While,
The conclusion holds.
Lemma 5: For k large enough, there exists a constant b>0, such that
Proof : Since xk → x*and for k large enough, Lk ≡ I(x* U) E, it holds that
Thereby, there exists some η>0, such that
while, from Lemma 4 it holds that
In addition, it holds, for k large enough, that πkj>0, ATkdk0 = Vk = - fj(xk), j ∈ Lk. So
From τ (2, 3), we have ||dk|| ~ ||dk0||, ||dk1|| = o(||dk0||2).
In order to obtain superlinear convergence, a crucial requirement is that a unit step size be used in a neighborhood of the solution. This can be achieved if the following assumption is satisfied.
H 7: Let
where
In view of Lemma 4, imitating the proof of Lemma 4.4 in reference (Zhu, 2005), it is easy to obtain the following conclusion.
Lemma 6: For k large enough, step 7 is no longer performed in the algorithm and the attempted search in step 6 is successful in every iteration, i.e., λk ≡ 1, xk+1 = xk + dk.
Moreover, in view of Lemma 3.8 and the way of Theorem 2 in reference (Panier and Tits, 1987), we may obtain the following theorem:
Theorem 3: Under all above-mentioned assumptions, the algorithm is superlinearly convergent, i.e., the sequence {xk} generated by the algorithm satisfies
ACKNOWLEDGMENT
This study was supported in part by the NNSF (10501009, 60471039) of China.
REFERENCES
- Facchinel, F. and S. Lucidi, 1995. Quadratically and superlinearly convergent algorithms for the solution of inequality constrained minimization problems. J. Optimization Theor. Appl., 85: 265-289.
CrossRef - Han, S.P., 1976. Superlinearly convergent variable metric algorithm for general nonlinear programming problem. Math Programm., 11: 263-282.
CrossRef - Panier, E.R. and A.L. Tits, 1987. A superlinearly convergent feasible method for the solution of inequality constrained optimization problems. SIAM. J. Control Optim., 25: 934-950.
CrossRefDirect Link - Rosen, J.B., 1960. The gradient projection method for nonlinear programming. Part I: Linear constraint. SIAM J. Applied Math., 8: 181-217.
Direct Link - Zhu, Z.B., K.C. Zhang and J.B. Jian, 2003. An improved SQP algorithm for inequality constrained optimization. Math. Methods Operat. Res., 58: 271-282.
CrossRef - Zhu, Z.B., 2005. A globally and superlinearly convergent feasible QP-free method of nonlinear programming. Applied Math. Comput., 168: 519-539.
Direct Link