A Variable Metric Algorithm with Broyden Rank One Modifications for Nonlinear Equality Constraints Optimization ()
1. Introduction & Algorithm
This In this paper, it is proposed to consider the following nonlinear mathematical programming problem:
(1)
where
are continuously differentiable functions. Denote the feasible set as follows:
![](https://www.scirp.org/html/5-2730011\c3599b19-351d-4e2d-b296-e0db41e5cdf2.jpg)
Let
be Lagrangian function of (1), and
![](https://www.scirp.org/html/5-2730011\3f023d29-c7ad-4239-b34c-3dec8025f06d.jpg)
If
is a KKT point pair of Equation (1), then
i.e.,
(2)
where ![](https://www.scirp.org/html/5-2730011\4ddef3e8-ff62-4504-8376-2003b1b011c9.jpg)
At the point pair
, the Newton’s iteration of (2) is defined as follows:
(3)
Later, a positive definite matrix
is replaced for
by a lot of authors to develop some kinds of variable metric methods, such as sequential quadratic programming (SQP) methods [1-5], sequential systems of linear equations (SSLE) algorithms [6-8]. In general, the computational cost of those methods is large.
In this paper, a new variable metric method is presented, in which the following fact is based on: a positive definite matrix
is replaced for the matrix
.
In the sequel, we describe the algorithm for the solution of (1). Denote
![](https://www.scirp.org/html/5-2730011\531c875e-8166-4d76-ad81-b63d3a81fd8c.jpg)
![](https://www.scirp.org/html/5-2730011\36891742-5208-407c-a3ba-0ce1d6c63064.jpg)
![](https://www.scirp.org/html/5-2730011\ddfe768e-99ff-42fb-9ab5-ef38726c620e.jpg)
![](https://www.scirp.org/html/5-2730011\26fb316f-4fbe-45a0-b3a7-34b1d543f39d.jpg)
It is obvious that
and from Equation (3), we have
(4)
To the system of linear Equations (4), like unconstrained optimization,
is dealt with using Broyden rank one modifications as follows:
(5)
Now, the algorithm for the solution of Equation (1) can be stated as follows:
Algorithm A:
Step 1: Initialization: Given a starting point
(i.e.,
), and a initial positive definite matrix
. ![](https://www.scirp.org/html/5-2730011\65786a56-796f-441f-a723-24d72d6256d5.jpg)
Step 2: Compute
. If
, stop;
Step 3: Compute
;
Step 4: Let
, and obtain
according to (5). Set
. Go back to step 2.
2. Convergence of Algorithm
If the algorithm stops at
, then
is a KKT point of (1). In the sequel, we suppose that algorithm generates an infinite sequence
.
Four basic assumptions are given as follows:
A1 The feasible set
is nonempty; The functions
are two-times continuously differentiable;
A2 For all
, the vectors
are linearly independent;
A3
and
are bounded. There exists a KKT point pair
, such that
is positive definite;
A4 There exists a ball
of radius
about
, where
satisfy the Lipschitz condition on
.
Lemma 1 [9] Let
be continuously differentiable in some open and convex set
, and
is Lipschitz continuous in
, then
, it holds that
![](https://www.scirp.org/html/5-2730011\062793a0-6624-4c4b-82b1-bcf8b05c1cdd.jpg)
where
is the Lipschitz constant. Moreover, ![](https://www.scirp.org/html/5-2730011\ca4347a5-432f-43c7-b48b-35fe17ecc07e.jpg)
, it follows that
![](https://www.scirp.org/html/5-2730011\4f029c0c-aa7e-4c5e-baa2-db2d65b85068.jpg)
Lemma 2 [9] Let
be continuously differentiable in some open and convex set
, and
is Lipschitz continuous in
. Moreover, assume
is invertible for some
, then there exist some
, such that for all
, the fact
implies that
![](https://www.scirp.org/html/5-2730011\fddc61f7-e325-4a81-a2f5-3e1ec0050308.jpg)
Lemma 3 [9] For operator
, which satisfies:
R1
is continuously differentiable on
;
R2 There exists a point
, such that
, and
is reversible;
R3
is Lipschitz continuous at
, i.e., there exists a constant
, such that
![](https://www.scirp.org/html/5-2730011\ba602158-7075-41d6-9341-803bc42facb4.jpg)
Let
, where
, and it holds that
(6)
then there exist
and
, when
![](https://www.scirp.org/html/5-2730011\ef92ea45-0512-4c89-be49-a8a0fec3e26e.jpg)
it is true that
is meaning, and
is linearly convergent to
. Thereby, we can conclude that
is superlinearly convergent to
, if and only if
(7)
In the sequel, we prove the convergence Theorem as follows:
Theorem 1 If there exist constants
and
such that
![](https://www.scirp.org/html/5-2730011\a3988429-f1ab-42cd-9fbd-cc9484c158b1.jpg)
then
is meaning, and
is linearly convergent to
, thereby
and
are linearly convergent to
and
respectively.
Proof: From Lemma 3, we only prove that
and
satisfy conditions R1, R2, R3 and the inequality (6). From assumption A1, it is obvious that
is continuously differentiable. From A3, it holds that
, and
![](https://www.scirp.org/html/5-2730011\4ce2b70b-484f-4ca8-8fa0-4f29f5c0491e.jpg)
While
is positive definite, and
are linearly independent. So, it is easy to see that
is reversible. In addition,
![](https://www.scirp.org/html/5-2730011\2ca10584-8e96-4023-9c19-5e33419bb775.jpg)
From assumption A4, it holds that
is Lipschitz continuous at
. In a word,
satisfies the conditions R1, R2, R3.
Now, we prove that, for
and
generated according to (5), (6) is satisfied.
In fact, from (5), we have
(8)
So,
![](https://www.scirp.org/html/5-2730011\1ff91045-eccf-4681-ae72-0cf72e8de745.jpg)
While
![](https://www.scirp.org/html/5-2730011\410d8adf-526c-467b-8adb-f20b883af0d7.jpg)
and from Lemma 1, we have
(9)
So,
i.e., (6) is true, thereby, from Lemma 3, we get
![](https://www.scirp.org/html/5-2730011\39be7cb5-e1c8-4a53-bda5-ede6ff645561.jpg)
The claim holds.
Theorem 2 Under above-mentioned assumptions, if
,
in Theorem 1 satisfy that
(10)
then
is superlinearly convergent to
, i.e.,
![](https://www.scirp.org/html/5-2730011\28db9036-2a78-4ef6-9bc9-919adf76fae8.jpg)
Proof. From Lemma 3, we only prove that
and ![](https://www.scirp.org/html/5-2730011\e5910d84-d9ba-47f6-90b2-84586c084e2a.jpg)
satisfy (7). Denote
,
norm,
Frobenius norm. From (8),
(11)
Since
![](https://www.scirp.org/html/5-2730011\50d8f846-4832-4382-9771-86629d59f948.jpg)
![](https://www.scirp.org/html/5-2730011\e33d1ffa-f28a-4776-be23-376d3f99bebf.jpg)
So,
(12)
In addition, from (6), (10), using the method of mathematical induction, it is not difficult to prove that
(13)
thereby,
(14)
Thus, from (9), (12), (13), we have
![](https://www.scirp.org/html/5-2730011\20c6110b-ac89-4531-abc1-519f1aa64dcb.jpg)
![](https://www.scirp.org/html/5-2730011\92ea403d-ee40-43f2-8a31-f97a03c7c9ee.jpg)
i.e.
is convergent, thereby, ![](https://www.scirp.org/html/5-2730011\a828c9de-2c5f-4f96-9f12-6f71cf5b78ed.jpg)
From Theorem 2, we don’t conclude that
is superlinearly convergent to
, i.e.,
In the sequel, we discuss one condition which assures that
is superlinearly convergent to
.
Lemma 4 Let
be a function defined by
![](https://www.scirp.org/html/5-2730011\d8276187-8c87-46bb-a54a-73d98ef478a2.jpg)
where ![](https://www.scirp.org/html/5-2730011\16cfc0a8-f7b0-490f-a0f5-b89245066b3f.jpg)
Then,
, if and only if
![](https://www.scirp.org/html/5-2730011\2f4dfb2e-196a-4801-b2c7-5861b6ab1de2.jpg)
Proof. Obviously, using the triangle inequality, it holds that
![](https://www.scirp.org/html/5-2730011\e07b89ca-2f5a-485d-8839-631e695494d6.jpg)
In addition, from A1, we know that
is continuously differentiable, and
(15)
It holds that
is nonsingular. In fact, let
, and
![](https://www.scirp.org/html/5-2730011\bdb161a5-1978-439d-9e41-4f73c616f83d.jpg)
the facts that
has full rank,
is semi-positive definite and
is positive definite imply that
![](https://www.scirp.org/html/5-2730011\779d1a4a-968b-4c5f-a101-bbe20ce7843b.jpg)
So,
![](https://www.scirp.org/html/5-2730011\6326d8b5-19c4-4393-99a2-5bfc4ce04e81.jpg)
which is a contradiction.
Thereby, from A4 and Lemma 2, there exist
, such that
![](https://www.scirp.org/html/5-2730011\4702dc57-294d-4915-a4f3-5f321488b011.jpg)
So,
.
The claim holds.
Theorem 3 Under above-mentioned conditions, ![](https://www.scirp.org/html/5-2730011\a4a332e0-1712-4dc3-96ae-ef55574b390c.jpg)
is superlinearly convergent to
if and only if
![](https://www.scirp.org/html/5-2730011\3fd7bc26-b5a3-43a8-86bc-b2bc5d4e3e06.jpg)
and
i.e.,
(16)
Proof. The sufficiency: Suppose that (16) holds. We only prove that ![](https://www.scirp.org/html/5-2730011\478d6f37-93b8-4c4a-806b-40d710fb9a8a.jpg)
From (4), we have
![](https://www.scirp.org/html/5-2730011\435abf06-45c9-4163-9334-4fc48b1725e9.jpg)
So, the fact
implies that
![](https://www.scirp.org/html/5-2730011\755a6b44-0a0c-4111-bc1e-c9e330f306d5.jpg)
thereby,
![](https://www.scirp.org/html/5-2730011\86bad14a-fe45-41ff-88ce-138272ac7c40.jpg)
From (15), we have
So,
![](https://www.scirp.org/html/5-2730011\0ca2c952-0fe7-4ff3-802f-3a49a504fbd2.jpg)
While
![](https://www.scirp.org/html/5-2730011\126fe124-b7fd-4989-b465-bc8be54eb5a0.jpg)
In addition, according to Lemma 1, we have
![](https://www.scirp.org/html/5-2730011\759a2ddf-ba6d-4150-bf8c-975558abec47.jpg)
so, from (16), it holds that ![](https://www.scirp.org/html/5-2730011\58922b96-9629-41dc-aec0-036d8e264001.jpg)
The necessity: Suppose that ![](https://www.scirp.org/html/5-2730011\a82213cf-2913-479c-93bb-0f485fa706ce.jpg)
i.e., ![](https://www.scirp.org/html/5-2730011\a92c52ab-192e-42fc-8fc0-ab099c1e8c0a.jpg)
On one hand,
![](https://www.scirp.org/html/5-2730011\b749185c-cdfe-4cd3-8fd9-d5dfb62d2b1a.jpg)
So, in order to prove that
![](https://www.scirp.org/html/5-2730011\7e99b100-3e6d-4ebb-8c41-95b362b74b81.jpg)
While
![](https://www.scirp.org/html/5-2730011\997a1a13-8b13-4650-a6f3-e8fa1d369b12.jpg)
According to Lemma 1, we have
![](https://www.scirp.org/html/5-2730011\7d046951-0006-4b5f-8973-e02aa1eda8b6.jpg)
and ![](https://www.scirp.org/html/5-2730011\e0445544-c833-4d4e-84a4-9d694de003f7.jpg)
So, ![](https://www.scirp.org/html/5-2730011\dfc76dcb-fc4e-49cf-9e2d-09bcbcd247bc.jpg)
On the other hand, the fact
implies that
![](https://www.scirp.org/html/5-2730011\eabcfae7-eb20-4095-a6a3-0d5ea76de27f.jpg)
Let
, then
It is easy to see that
![](https://www.scirp.org/html/5-2730011\395c4e6d-b007-4a45-9bd8-f9fc21e43a80.jpg)
Thereby,
![](https://www.scirp.org/html/5-2730011\bd8042b5-b116-4e4d-9e14-4230e66a7734.jpg)
The claim holds.
3. Acknowledgements
This work was supported in part by NNSF (No. 11061 011) of China and Guangxi Fund for Distinguished Young Scholars (2012GXSFFA060003).