A New Lagrangian Multiplier Method on Constrained Optimization ()
1. Introduction
Considering the following nonlinear inequality constrained optimization Problem (NLP):
(1)
where
and
![](https://www.scirp.org/html/22-7400953\810341c1-5d0e-45c6-ab61-eb0438952c7e.jpg)
are continuously differentiable functions.
We denote by
![](https://www.scirp.org/html/22-7400953\5660ffc1-7b5d-487c-845e-13f2425478a4.jpg)
the feasible set of the problem (NLP).
The Lagrangian function associated with the problem (NLP) is the function
![](https://www.scirp.org/html/22-7400953\0804cd83-538c-4dcf-a70d-c3796a776d45.jpg)
where
![](https://www.scirp.org/html/22-7400953\5a4067b8-3c18-413f-a72f-b4188230240c.jpg)
are the multiplier vectors, For simplicity, we use
to denote the column vector ![](https://www.scirp.org/html/22-7400953\6803708a-d03e-4e92-b5df-70f4302bbba7.jpg)
Defintion 1.1. A point
is called a Karush-Kuhn-Tucker (KKT) point or a KKT pair of Problem (NLP), if it satisfies the following conditions:
(2)
where
, we also say
is a KKT point if there exists a
such that
satisfies (2).
For the nonlinear inequality constrained optimization problem (NLP), there are many practical methods to solve it, such as augmented Lagrangian function method [1-6], Trust-region filter method [7,8], QP-free feasible method [9,10], Newton iterative method [11,12], etc. As we know, Lagrange multiplier method is one of the efficient methods to solve problem (NLP). Pillo and Grippo in [1-3] proposed a class of augmented Lagrange function methods which have nice equivalence between the unconstrained optimization and the primal constrained problem and get good convergence properties of the related algorithm. However, a max function is used for these methods which may be not differentiable at infinite numbers of points. To overcome this shortcoming, Pu in [4] proposed a augmented Lagrange function with FischerBurmeister nonlinear NCP function and Lagrange multiplier methods. Pu and Ding in [6] proposed a Lagrange multiplier methods with 3-piecewise linear NCP function. In this paper, a new class augmented Lagrange function with 4-piecewise linear NCP function and some Lagrange multiplier methods are proposed for the minimization of a smooth function subject to smooth inequality constraints and equality constrains.
The paper is organized as follows: In the next section we give some definitions and properties about NCP function, and then define a new augmented Lagrange function with 4-piecewise NCP function. In Section three, we give the algorithm. In Section four, we prove convergence of the algorithm. Some conclusions are given in Section five.
2. Preliminaries
In this section, we recall some definitions and define a new Lagrange multiplier function with 4-piecewise NCP function.
Definition 2.1 (NCP pair and SNCP pair). We call a pair (a, b) to be an NCP pair if
and ab = 0; and call (a, b) to be an SNCP pair if (a, b) is a pair and
.
Definition 2.2 (NCP function). A function
is called an NCP function if
if and only
is an NCP pair.
In this paper, we propose a new 4-piecewise linear NCP function
is as follows:
(3)
If
, then
(4)
and
(5)
It is easy to check the following propositions:
1)
;
2) The square of
is continuously differentiable;
3)
is twice continuously differentiable everywhere except at the origin but it is strongly semi-smooth at the origin.
Let
![](https://www.scirp.org/html/22-7400953\04626070-1898-43c3-a1b1-c39d5f81afbb.jpg)
where
is a parameter.
if and only if
,
and
for any
.
We construct function:
![](https://www.scirp.org/html/22-7400953\1d3150df-2144-4e6e-80a1-9e3f7eb836ab.jpg)
Clearly, the KKT point condition (2) is equivalently reformulate as the condition:
![](https://www.scirp.org/html/22-7400953\81fa4b1a-0b5f-437a-a2a3-bfe2530523c3.jpg)
If
, then
is continuously differentiable at
. We have
(6)
where
is the ith column of the unit matrix, its jth element is 1, and other elements are 0, in this paper take k = 1.
If
, and then
is strongly semi-smooth and direction differentiable at
. We have
(7)
For Problem (NLP), we define a Di Pillo and Grippo type Lagrange multiplier function with 4-piecewise linear NCP function is as following:
(8)
where
are the Lagrange multiplier, C and D are positive parameters.
In this section, we gave some assumptions as follows:
Assumpion 1 f,
,
, ![](https://www.scirp.org/html/22-7400953\e14bbd16-cd65-4348-bae2-67dedab0a21a.jpg)
are twice Lipschitz continuously differentiable.
Define index set
and
as follows:
![](https://www.scirp.org/html/22-7400953\356d1f31-b3f7-4909-80d1-fb94572df314.jpg)
for any
, according to definition of
, have
![](https://www.scirp.org/html/22-7400953\6e556053-fd3d-43a1-bc87-f36fbbace0e6.jpg)
for any
, we have 1) if
, we have
(9)
The gradient of
is
(10)
The Henssian matrix of
at KKT point
is
(11)
2) if
, then
(12)
The gradient of
is
(13)
The Henssian matrix of
at KKT point
is
(14)
Definition 2.3 A point
is said to satisfy the strong second-order sufficiency condition for problem (NLP) if it satisfies the first-order KKT condition and if
for all
![](https://www.scirp.org/html/22-7400953\a97b69c8-ccd0-429f-91b0-c6c81eaf09e6.jpg)
and
.
Assumption 2 At any KKT point
satisfied strong second-order sufficiency condition.
Lemma If
is a positive semi-definite matrix, for any
,
, matrix
satisfied
, then exist
, for any
,
is positive definite matrix (see [4]).
Theorem 2.1 If
is KKT point of problem (1), then for sufficiently large C and D,
is strong convex function at point
.
Proof: Let ![](https://www.scirp.org/html/22-7400953\9e824b0e-088a-4a8d-9fbc-113425985472.jpg)
![](https://www.scirp.org/html/22-7400953\21854b60-dd65-4cf6-a15f-e89cd251809b.jpg)
for
, we have
![](https://www.scirp.org/html/22-7400953\337bd4e3-65bd-4e6c-beff-afcc3998da05.jpg)
from A2, we have
. Furthermore there is
if
, for any
,
is positive definite matrix. And then for any
and sufficiently large C and D have
![](https://www.scirp.org/html/22-7400953\6ac18f8f-2408-417c-bd09-dc2b139a0c05.jpg)
by its continuously, we may obtained that there is
, for all
![](https://www.scirp.org/html/22-7400953\55befd38-65a9-42a1-adc6-d9701f37db09.jpg)
we have
the theorem hold.
3. Lagrange Multiplier Algorithm
Step 0 Choose parameters
,
,
,
, given point
, and
![](https://www.scirp.org/html/22-7400953\d6edc8cc-98e5-4bc2-88ff-311f2359959c.jpg)
Let
.
Step 1 Solve following, we will obtain
.
![](https://www.scirp.org/html/22-7400953\63b51261-81ec-490e-a2a9-783478dd5a7e.jpg)
if
and
then stop.
Step 2 For
,
, then
or
, for
, if
then
, or ![](https://www.scirp.org/html/22-7400953\ff5861f3-e886-452d-af9d-7ea29e45f310.jpg)
Step 3 Compute
and ![](https://www.scirp.org/html/22-7400953\a7220ec7-5170-4e01-96e0-5be1848694d8.jpg)
![](https://www.scirp.org/html/22-7400953\aae70818-ddc1-4910-8ec3-926f69e24a92.jpg)
Step 4 Let k = k + 1, go to Step 1.
4. Convergence of the Algorithm
In this section, we make a assumption follow as:
Assumption 3 For any
,
,
,
,
exists a minimizer point
.
Theorem 4.1 Assume feasible set of problem (NLP) is non-empty set and
is bounded, then algorithm is bound to stop after finite steps iteration.
Proof: Assume that the algorithm can not stop after finite steps iteration, by the sack of convenience, we define index set as following
![](https://www.scirp.org/html/22-7400953\79312639-9692-4d1b-9f0d-3ee3bcd0dd23.jpg)
according to assumption A3, it is clearly that
or
are non-empty set. for any k, obtain
![](https://www.scirp.org/html/22-7400953\27c31377-5c7a-48b6-a013-ffda79d5bbf4.jpg)
from above assumption, we obtain that for any a
there is
, for any
and
,
and
, for sufficiently large k, it is not difficult to see that
![](https://www.scirp.org/html/22-7400953\c18b5a44-2c74-4663-8266-c82b86510eb4.jpg)
Or for any
and
,
and
, for sufficiently large k, have
![](https://www.scirp.org/html/22-7400953\55597359-1cf8-4d9b-bf11-af502a4d5025.jpg)
When
we can hold
![](https://www.scirp.org/html/22-7400953\1e6f2622-e9c6-4da3-8668-e911bede43a3.jpg)
Which contradicts A3, the theorem holds.
Theorem 4.2 Let
is a compact set, sequence
are generated by the algorithm, and
, in algorithm, 0 take the place of
, either algorithm stops at its
and
is solution of problem(NLP), or for any an accumulation
of sequence
,
is solution of problem (NLP).
Proof: Because the algorithm stops at its
, then we have
(15)
for
,
, it is easy to see that for any
have
![](https://www.scirp.org/html/22-7400953\ce8b0ed6-83b0-4a1e-ab8e-a6498d5e6fc8.jpg)
It is from Step 2 of the algorithm that we have
(16)
putting (15) (16) into (10) or (13), we can obtain
![](https://www.scirp.org/html/22-7400953\9222fd56-b089-4e8d-9096-68a3a8f00b8a.jpg)
for
,
, according to definition of
, we can obtain, that
![](https://www.scirp.org/html/22-7400953\6cef0ef8-20a8-4781-8620-25b1d7fbbbc0.jpg)
First part of the theorem holds,
is solution of problem (NLP).
On the other hand, if the algorithm is not stop at
, for any accumulation point
of sequence
, from theorem 4.1, we can obtain, for any positive number C, that
![](https://www.scirp.org/html/22-7400953\9782b4a5-d9a9-414d-af4d-01fea810f4d4.jpg)
for any
, have
![](https://www.scirp.org/html/22-7400953\6e2efefd-acf6-485d-932d-8ba742d7d164.jpg)
Let
,have
![](https://www.scirp.org/html/22-7400953\bbf5970d-fa5e-482b-b546-a01dad9d2a92.jpg)
Clearly, second part of the theorem holds.
is solution of problem (NLP).
5. Conclusion
A new Lagrange multiplier function with 4-piecewise linear NCP function is proposed in this paper which has a nice equivalence between its solution and solution of original problem. We can solve it to obtain solution of original constrained problem, the algorithm corresponding with it be endowed with convergence.
6. Acknowledgements
This paper was partially supported by the NNSF of China under Grant No. 10971053, and NNSF of Henan under Grant No. 094300510050.
NOTES
#Corresponding author.