# Second-Order Multiplier Iteration Based on a Class of Nonlinear Lagrangians

Authors: Yong-Hong Ren
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Nonlinear Lagrangian algorithm plays an important role in solving constrained optimization problems. It is known that, under appropriate conditions, the sequence generated by the first-order multiplier iteration converges superlinearly. This paper aims at analyzing the second-order multiplier iteration based on a class of nonlinear Lagrangians for solving nonlinear programming problems with inequality constraints. It is suggested that the sequence generated by the second-order multiplier iteration converges superlinearly with order at least two if in addition the Hessians of functions involved in problem are Lipschitz continuous.


---

## Body

## 1. Introduction

Lagrangians play an important role for solving constrained optimization problems. Hestenes [1] and Powell [2] introduced the proximal augmented Lagrangian for problems with equality constraints and Rockafellar [3] developed the proximal augmented Lagrangian for problems with both equality and inequality constraints.Based on the above Lagrangians, Bertsekas [4, 5] discussed the convergence of sequence generated by the second-order multiplier iteration. The same author further improved the convergence and convergent rate of the second-order multiplier iteration using Newton’s method in 1982. Besides, Brusch [6] and Fletcher [7] first independently proposed the second-order multiplier iteration using quasi-Newton’s method, respectively. Bertsekas [8] developed new framework of quasi-Newton’s method in 1982.Consider the following inequality constrained optimization problem:(
INP
)
minimize
f
0
(
x
)
subject
to
f
i
(
x
)
≥
0
,
i
=
1
,
…
,
m
,
where f
i
:
ℝ
2
→
ℝ, i
=
0
,
…
,
m are continuous differentiable functions.As nonlinear Lagrangians can be used to develop dual algorithms for nonlinear programming, requiring no restrictions on primal feasibility, important contributions on this topic have been done by many authors.Polyak and Teboulle [9] discussed a class of Lagrange functions of the form
(1)
H
(
x
,
u
,
c
)
=
f
0
(
x
)
-
c
∑
i
=
1
m
u
i
ψ
(
c
-
1
f
i
(
x
)
)
‍
for solving (
INP
), where c
>
0 is penalty parameter and ψ is twice continuous differentiable function. Furthermore, Polyak and Griva [10] proposed a general primal-dual nonlinear rescaling (PDNR) method for convex optimization with inequality constraints, and Griva and Polyak [11] developed a general primal-dual nonlinear rescaling method with dynamic scaling parameter update. Besides the works by Polyak and his coauthors, Auslender et al. [12] and Ben-Tal and Zibulevsky [13] studied other nonlinear Lagrangians and obtained interesting convergence results for convex programming problems, too. Under appropriate conditions, the sequence generated by the first-order multiplier iteration converges superlinearly.Ren and Zhang [14] analysed the following nonlinear Lagrangians:
(2)
H
(
x
,
u
,
c
)
=
f
0
(
x
)
-
k
-
1
∑
i
=
1
m
u
i
ψ
(
k
f
i
(
x
)
)
‍
and constructed the dual algorithm based on minimizing H
(
x
,
u
,
k
) as follows.D-AlgorithmStep 1.
Givenk
>
0 large enough, ε
≥
0 small enough, u
0
∈
ℝ
+
+
m, and x
0
∈
ℝ
n, set s
=
0.Step 2.
Solve (approximately)(3)
minimize
H
(
x
,
u
s
,
k
)
and obtain its (approximate) solution x
s.Step 3.
Ifu
i
s
f
i
(
x
s
)
≤
ε, i
=
1
,
…
,
m, stop; otherwise go to Step 4.Step 4.
Update Lagrange multiplieru
(4)
u
s
+
1
=
diag
⁡
1
≤
i
≤
m
⁡
(
ψ
′
(
k
f
i
(
x
s
)
)
)
u
s
.Step 5.
Sets
=
s
+
1 and return to Step 2.It was shown that, under a set of conditions, dual algorithm based on this class of Lagrange is locally convergent when the penalty parameter is larger than a threshold.In view of interpretation of the multiplier iteration as the steepest ascent method, it is natural to consider Newton’s method for maximizing the dual functional. Using known results for Newton’s method, we expect that the second-order iteration will yield a vectoru
s
+
1 which is closer to u
* than u
s. This paper aims at discussing the second-order multiplier iteration based on nonlinear Lagrangians of the form (2). It is suggested that the sequence generated by the second-order multiplier iteration converges superlinearly with order at least two if ∇
2
f
i
(
x
)
(
i
=
0
,
…
,
m
) are Lipschitz continuous.We introduce the following notation to end this section:(5)
∇
f
(
x
)
=
(
∇
f
1
(
x
)
,
…
,
∇
f
m
(
x
)
)
,
u
*
=
(
u
1
*
,
…
,
u
m
*
)
∈
ℝ
m
,
u
(
m
-
r
)
*
=
(
u
r
+
1
*
,
…
,
u
m
*
)
∈
ℝ
m
-
r
,
S
(
y
,
ε
)
=
{
x
∈
ℝ
n
:
∥
x
-
y
∥
≤
ε
}
.
∇
f
(
r
)
(
x
)
=
(
∇
f
1
(
x
)
,
…
,
∇
f
r
(
x
)
)
,
u
(
r
)
*
=
(
u
1
*
,
…
,
u
r
*
)
∈
ℝ
r
,
∥
x
∥
=
∥
x
∥
∞
=
max
⁡
1
≤
i
≤
n
|
x
i
|
.


## 2. Preliminaries

Consider the inequality constrained optimization problem(
INP
). Let
(6)
L
(
x
,
u
)
=
f
0
(
x
)
-
∑
i
=
1
m
‍
u
i
f
i
(
x
)
denote the Lagrange function for problem (
INP
) and I
(
x
)
=
{
i
∣
f
i
(
x
)
=
0, i
=
1
,
…
,
m
}.For the convenience of description in the sequel, we list the following assumptions, some of which will be used somewhere.(a)
Functionsf
i
(
x
)
(
i
=
0
,
…
,
m
) are twice continuously differentiable.
(b)
For convenience of statement, we assumeI
(
x
*
)
=
{
i
∣
f
i
(
x
*
)
=
0, i
=
1
,
…
,
m
}
=
{
1
,
…
,
r
}.
(c)
Let(
x
*
,
u
*
)
∈
ℝ
n
×
ℝ
m satisfy the Kuhn-Tucker conditions
(7)
∇
x
L
(
x
*
,
u
*
)
=
0
,
u
*
≥
0
,
u
i
*
f
i
(
x
*
)
=
0
,
i
=
1
,
…
,
m
.
(d)
Strict complementary condition holds; that is,(8)
u
i
*
>
0
for
i
∈
I
(
x
*
)
.
(e)
The set of vectors{
∇
f
i
(
x
*
)
∣
i
∈
I
(
x
*
)
} are linearly independent.
(f)
For ally
≠
0 satisfying ∇
f
i
(
x
*
)
T
y
=
0, i
∈
I
(
x
*
), the following inequality holds:
(9)
y
T
∇
x
2
L
(
x
*
,
u
*
)
y
>
0
.Let functionψ in H
(
x
,
u
,
k
) defined in (2) and its derivatives satisfy the following conditions:(H1)
ψ
(
0
)
=
0;
(H2)
ψ
′
(
t
)
>
0, for all t
∈
(
b
,
+
∞
), with -
∞
≤
b
<
0, and ψ
′
(
0
)
=
1;
(H3)
ψ
′′
(
t
)
<
0, for all t
∈
(
b
,
+
∞
), with -
∞
≤
b
<
0;
(H4)
k
ψ
′
(
k
t
) is bounded, where t
∈
(
b
,
+
∞
), with -
∞
≤
b
<
0, and for k
>
0 large enough.The following proposition concerns properties ofH
(
x
,
u
,
k
) at a Kuhn-Tucker point (
x
*
,
u
*
).Proposition 1 (see [14]).
Assume that (a)–(f) and (H1)–(H3) hold. For anyk
>
0 and any Kuhn-Tucker point (
x
*
,
u
*
) the following properties are valid:(i)
H
(
x
*
,
u
*
,
k
)
=
L
(
x
*
,
u
*
)
=
f
(
x
*
);
(ii)
∇
x
H
(
x
*
,
u
*
,
k
)
=
∇
x
L
(
x
*
,
u
*
)
=
∇
f
(
x
*
)
-
∑
i
=
1
m
u
i
*
∇
f
i
(
x
*
)
=
0;
(iii)
∇
x
2
H
(
x
*
,
u
*
,
k
)
=
∇
x
2
L
(
x
*
,
u
*
)
-
k
ψ
′′
(
0
)
∇
f
(
r
)
(
x
*
)
T
U
*
∇
f
(
r
)
(
x
*
),where
U
*
=
diag
⁡
1
≤
i
≤
r
(
u
i
*
);
(iv)
there exist
c
0
>
0
and
μ
>
0
such that,for any
c
>
c
0,
(10)
〈
∇
x
2
H
(
x
*
,
u
*
,
k
)
y
,
y
〉
≥
μ
〈
y
,
y
〉
,
∀
y
∈
ℝ
n
s
a
t
i
s
f
y
i
n
g
∇
f
(
r
)
(
x
*
)
T
y
=
0
.Letδ
>
0 be small enough, 0
<
ε
<
min
⁡
⁡
{
u
i
*
∣
i
=
1
,
…
,
r
}, and k
0 large enough satisfying (iv) of Proposition 1. For any fixed k
>
k
0, define
(11)
U
k
i
(
ε
,
δ
)
=
{
{
u
i
∣
max
⁡
{
ε
,
u
i
*
-
δ
k
}
≤
u
i
≤
u
i
*
+
δ
k
}
,
i
=
1
,
…
,
r
,
{
u
i
∣
0
≤
u
i
≤
δ
k
}
,
i
=
r
+
1
,
…
,
m
,
U
k
(
ε
,
δ
)
=
U
k
1
(
ε
,
δ
)
×
…
×
U
k
r
(
ε
,
δ
)
×
…
×
U
k
m
(
ε
,
δ
)
.
For any k
1
>
k
0, we denote
(12)
D
(
ε
,
δ
)
=
{
(
u
,
k
)
∣
u
∈
U
k
(
ε
,
δ
)
,
k
∈
[
k
0
,
k
1
]
}
.
Let σ
=
min
⁡
⁡
{
f
i
(
x
*
)
∣
r
+
1
≤
i
≤
m
}
>
0, I
r is the r
×
r identity matrix, and 0
r is the r
×
r zero matrix.Theorem 2 (see [14]).
Assume that (a)–(f) and (H1)–(H4) hold. Then there existsk
0
>
0 large enough such that, for any k
1
>
k
0, there exist ε
1
>
0
,
δ
>
0, satisfying that for any (
u
,
k
)
∈
D
(
ε
,
δ
), the following statements hold.(i)
There exists a vector(13)
x
^
=
x
^
(
u
,
k
)
∈
arg
min
⁡
{
H
(
x
,
u
,
k
)
x
∈
S
(
x
*
,
ε
1
)
}
.
(ii)
Forx
^ in (i) and u
^
=
u
^
(
u
,
k
)
=
diag
⁡
1
≤
i
≤
m
(
ψ
′
(
k
f
i
(
x
^
)
)
)
u, the following estimate is valid:
(14)
max
⁡
⁡
{
∥
x
^
-
x
*
∥
,
∥
u
^
-
u
*
∥
}
≤
c
k
-
1
∥
u
-
u
*
∥
,
where c
>
0 is a scalar independent of k
0 and k
1.
(iii)
FunctionH
(
x
,
u
,
k
) is strongly convex in a neighborhood of x
^.


## 3. The Second-Order Multiplier Iteration

Based on the nonlinear Lagrange functionH
(
x
,
u
,
k
), we consider the dual function defined on S
(
x
*
,
ε
1
)
×
ℝ
+
m as follows:
(15)
d
k
(
u
)
=
inf
⁡
{
H
(
x
,
u
,
k
)
∣
x
∈
S
(
x
*
,
ε
1
)
}
-
δ
(
u
∣
U
k
(
ε
,
δ
)
)
,
where δ
(
u
∣
U
k
(
ε
,
δ
)
)
=
{
0
if
u
∈
U
k
(
ε
,
δ
)
+
∞
if
u
∉
U
k
(
ε
,
δ
) is the indicator function of U
k
(
ε
,
δ
).Lemma 3.
Assume that conditions (a)–(f) and (H1)–(H4) hold; then for any fixedk
≥
k
0 function d
k
(
u
) is twice continuously differentiable and concave on U
k
(
ε
,
δ
).Proof.
Obviously, fork
>
0, function d
k
(
u
) is concave. In view of Theorem 2,  for any (
u
,
k
)
∈
D
(
ε
,
δ
), function H
(
x
,
u
,
k
) is strong convex in the neighborhood of x
^
=
x
^
(
u
,
k
). So x
^
(
u
,
k
) is unique minimizer of function H
(
x
,
u
,
k
) with respect to x in the neighborhood of point x
^, and d
k
(
u
)
=
H
(
x
^
(
u
,
k
)
,
u
,
k
) is smooth in U
k
(
ε
,
δ
); that is, the Jacobian of d
k
(
u
) exists, and
(16)
∇
u
d
k
(
u
)
=
∇
u
x
^
(
u
,
k
)
∇
x
H
(
x
^
(
u
,
k
)
,
u
,
k
)
+
∇
u
H
(
x
^
(
u
,
k
)
,
u
,
k
)
=
(
∇
u
1
d
k
(
u
)
,
…
,
∇
u
m
d
k
(
u
)
)
T
.
For (
u
,
k
)
∈
D
(
ε
,
δ
), matrix ∇
x
2
H
(
x
,
u
,
k
) is positive definite, and system ∇
x
H
(
x
,
u
,
k
)
=
0
n generates unique vector-valued function x
^
(
u
,
k
) satisfying x
^
(
u
*
,
k
)
=
x
* and
(17)
∇
u
x
^
(
u
,
k
)
=
-
∇
x
u
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
(
∇
x
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
)
-
1
,
hhhhhhhhhhhhhhhhhhhhhh
∀
(
u
,
k
)
∈
D
(
ε
,
δ
)
.
In view of ∇
x
H
(
x
^
(
u
,
k
)
,
u
,
k
)
=
0
n, we have
(18)
∇
u
d
k
(
u
)
=
∇
u
H
(
x
^
(
u
,
k
)
,
u
,
k
)
=
-
k
-
1
(
ψ
(
k
f
1
(
x
^
(
u
,
k
)
)
)
,
…
,
ψ
(
k
f
m
(
x
^
(
u
,
k
)
)
)
)
T
.
It follows from (18) that
(19)
∇
u
x
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
=
-
(
ψ
′
(
k
f
1
(
x
^
(
u
,
k
)
)
)
∇
f
1
(
x
^
(
u
,
k
)
)
,
…
,
h
h
h
h
h
h
ψ
′
(
k
f
m
(
x
^
(
u
,
k
)
)
)
∇
f
m
(
x
^
(
u
,
k
)
)
)
=
-
∇
f
(
x
^
(
u
,
k
)
)
ψ
′
(
k
f
(
x
^
(
u
,
k
)
)
)
,
which means
(20)
∇
x
u
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
=
(
∇
u
x
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
)
T
=
-
ψ
′
(
k
f
(
x
^
(
u
,
k
)
)
)
∇
f
(
x
^
(
u
,
k
)
)
T
.
Thus,
(21)
∇
u
2
d
k
(
u
)
=
∇
u
x
(
u
,
k
)
∇
u
x
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
=
-
∇
x
u
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
(
∇
x
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
)
-
1
×
∇
u
x
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
=
-
ψ
′
(
k
f
(
x
^
(
u
,
k
)
)
)
(
∇
f
(
x
^
(
u
,
k
)
)
)
T
×
(
∇
x
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
)
-
1
×
(
∇
f
(
x
^
(
u
,
k
)
)
)
ψ
′
(
k
f
(
x
^
(
u
,
k
)
)
)
.
So,
(22)
∇
u
2
d
k
(
u
*
)
=
-
ψ
′
(
k
f
(
x
*
)
)
(
∇
f
(
x
*
)
)
T
(
∇
x
2
H
(
x
*
,
u
*
,
k
)
)
-
1
×
(
∇
f
(
x
*
)
)
ψ
′
(
k
f
(
x
*
)
)
.Letx
^
(
u
,
k
) be the minimizer of H
(
x
,
u
,
k
) in a neighborhood of x
*; then we obtain that
(23)
∇
u
d
k
(
u
)
=
∇
u
H
(
x
^
(
u
,
k
)
,
u
,
k
)
=
-
k
-
1
(
ψ
(
k
f
1
(
x
^
(
u
,
k
)
)
)
,
…
,
ψ
(
k
f
m
(
x
^
(
u
,
k
)
)
)
)
T
,
∇
u
2
d
k
(
u
)
=
-
ψ
′
(
k
f
(
x
^
(
u
,
k
)
)
)
∇
f
(
x
^
(
u
,
k
)
)
T
×
(
∇
x
2
H
(
x
^
(
u
,
k
)
,
u
,
k
)
)
-
1
×
∇
f
(
x
^
(
u
,
k
)
)
ψ
′
(
k
f
(
x
^
(
u
,
k
)
)
)
.In view of the interpretation of the multiplier iteration as the steepest ascent method, it is natural to consider Newton’s method for maximizing the dual functionald
k which is given by
(24)
u
s
+
1
=
u
s
-
[
∇
2
d
k
(
u
s
)
]
-
1
∇
d
k
(
u
s
)
.
In view of (23), this iteration can be written as
(25)
u
s
+
1
=
u
s
-
B
k
-
1
k
-
1
ψ
(
k
f
(
x
(
u
s
,
k
)
)
)
,
where
(26)
B
k
=
ψ
′
(
k
f
(
x
(
u
s
,
k
)
)
)
∇
f
(
x
(
u
s
,
k
)
)
T
×
[
∇
x
2
H
(
x
(
u
s
,
k
)
,
u
s
,
k
)
]
-
1
×
∇
f
(
x
(
u
s
,
k
)
)
ψ
′
(
k
f
(
x
(
u
s
,
k
)
)
)
.
We will provide a convergence and rate of convergence result for iteration (25) and (26).Fork
>
0 and (
x
,
u
)
∈
ℝ
n
+
m, we define
(27)
A
+
(
x
,
u
)
=
{
i
∣
u
i
ψ
(
k
f
i
(
x
)
)
>
0
,
i
=
1
,
…
,
m
}
A
-
(
x
,
u
)
=
{
i
∣
i
∉
A
+
(
x
,
u
)
,
i
=
1
,
…
,
m
}
.
For a given (
x
,
u
), assume (by reordering indices if necessary) that A
+
(
x
,
u
) contains the first r indices where r is an integer with 0
≤
r
≤
m. Define
(28)
ψ
+
(
k
f
(
x
)
)
=
(
ψ
(
k
f
1
(
x
)
)
⋮
ψ
(
k
f
r
(
x
)
)
)
ψ
-
(
k
f
(
x
)
)
=
(
ψ
(
k
f
r
+
1
(
x
)
)
⋮
ψ
(
k
f
m
(
x
)
)
)
u
+
=
(
u
1
,
…
,
u
r
)
T
,
u
-
=
(
u
r
+
1
,
…
,
u
m
)
T
,
H
+
(
x
,
u
,
k
)
=
f
0
(
x
)
-
k
-
1
u
+
T
ψ
+
(
k
f
(
x
)
)
.
We note that r
,
ψ
+
,
ψ
-
,
u
+
,
u
- and H
+ depend on (
x
,
u
), but to simplify notation we do not show explicitly this dependence. Now, we consider Newton’s method for solving the system of necessary conditions
(29)
∇
x
H
+
(
x
,
u
,
k
)
=
∇
f
0
(
x
)
-
∑
i
=
1
r
‍
u
i
ψ
′
(
k
f
i
(
x
)
)
∇
f
i
(
x
)
=
0
,
k
-
1
ψ
(
k
f
i
(
x
)
)
=
0
,
i
=
1
,
…
,
r
.Considering the extension of Newton’s method, given(
x
,
u
), we denote the next iterate by (
x
^
,
u
^
) where u
^
=
(
u
^
1
,
…
,
u
^
m
)
T. We also write
(30)
u
^
+
=
(
u
^
1
,
…
,
u
^
r
)
T
,
u
^
-
=
(
u
^
r
+
1
,
…
,
u
^
m
)
T
.
The iteration, roughly speaking, consists of setting the multipliers of the inactive constraints (j
∈
A
-
(
x
,
u
)) to zero and treating the remaining constraints as equalities. More precisely, we set u
^
-
=
0
m
-
r and obtain x
^
,
u
^
+ by solving the system
(31)
(
∇
x
2
H
+
(
x
,
u
,
k
)
-
∇
f
(
r
)
(
x
)
ψ
+
′
(
k
f
(
x
)
)
ψ
+
′
(
k
f
(
x
)
)
∇
f
(
r
)
(
x
)
T
0
)
(
x
^
-
x
u
^
+
-
u
+
)
=
(
-
∇
x
H
+
(
x
,
u
,
k
)
-
k
-
1
ψ
+
(
k
f
(
x
)
)
)
,
where ψ
+
′
(
k
f
(
x
)
)
=
[
diag
⁡
ψ
′
(
k
f
i
(
x
)
)
]
i
=
1
r.If∇
x
2
H
+
(
x
,
u
,
k
) is invertible and ∇
f
(
r
)
(
x
) has rank r, we can solve system (31) explicitly. It follows from (31) that
(32)
∇
x
2
H
+
(
x
,
u
,
k
)
(
x
^
-
x
)
-
∇
f
(
r
)
(
x
)
ψ
+
′
(
k
f
(
x
)
)
(
u
^
+
-
u
+
)
=
-
∇
x
H
+
(
x
,
u
,
k
)
,
(33)
ψ
+
′
(
k
f
(
x
)
)
∇
f
(
r
)
(
x
)
T
(
x
^
-
x
)
=
-
k
-
1
ψ
+
(
k
f
(
x
)
)
.
Premultiplying (32) with ψ
+
′
(
k
f
(
x
)
)
∇
f
(
r
)
(
x
)
T
[
∇
x
2
H
+
(
x
,
u, k
)
]
-
1 and using (33), we obtain
(34)
x
^
-
x
=
[
∇
x
2
H
+
(
x
,
u
,
k
)
]
-
1
{
∇
f
(
r
)
(
x
)
ψ
+
′
(
k
f
(
x
)
)
(
u
^
+
-
u
+
)
hhhhhhhhhhhhhhhhh
-
∇
x
H
+
(
x
,
u
,
c
)
ψ
+
′
∇
f
(
r
)
}
,
from which, we have
(35)
u
^
+
=
u
+
-
{
ψ
+
′
(
k
f
(
x
)
)
∇
f
(
r
)
(
x
)
T
[
∇
x
2
H
+
(
x
,
u
,
k
)
]
-
1
hhhhhhhhh
×
∇
f
(
r
)
(
x
)
ψ
+
′
(
k
f
(
x
)
)
}
-
1
k
-
1
ψ
+
(
k
f
(
x
)
)
.
Substitution in (32) yields
(36)
x
^
=
x
-
∇
x
2
H
+
(
x
,
u
,
k
)
∇
x
H
+
(
x
,
u
^
,
k
)
.
Return to (25) and (26), and using the fact that ∇
x
H
+
(
x
(
u
,
k
)
,
u
,
k
)
=
0, we see that iteration (25) and (26) is of the form (35).For a triple(
x
,
u
,
k
) for which the matrix on the left-hand side of (31) is invertible, we denote by x
^
(
x
,
u
,
k
), u
^
+
(
x
,
u
,
k
) the unique solution of (31) and say that x
^
(
x
,
u
,
k
), u
^
+
(
x
,
u
,
c
) are well defined.Define(37)
u
+
s
+
1
=
u
^
+
(
x
(
u
s
,
k
)
,
u
s
,
k
)
,
u
-
s
+
1
=
0
.Proposition 4.
Letk be a scalar. For every triple (
x
,
u
,
k
), if ψ
′ satisfies
(38)
ψ
+
′
2
-
2
ψ
+
′
+
I
=
0
,
then the vectors x
^
(
x
,
u
,
k
), u
^
+
(
x
,
u
,
k
) are well defined if and only if the vectors x
^
(
x
,
ψ
′
(
k
f
(
x
)
)
u
,
0
), u
^
+
(
x
,
ψ
′
(
k
f
(
x
)
)
u
,
0
) are well defined.
Furthermore,(39)
x
^
(
x
,
u
,
k
)
=
x
^
(
x
,
ψ
′
(
k
f
(
x
)
)
u
,
0
)
,
(40)
u
^
+
(
x
,
u
,
k
)
=
u
^
+
(
x
,
ψ
′
(
k
f
(
x
)
)
u
,
0
)
.Proof.
By calculating, we have(41)
∇
x
H
+
(
x
,
u
,
k
)
=
∇
x
L
(
x
,
ψ
′
(
k
f
(
x
)
)
u
)
,
∇
x
2
H
+
(
x
,
u
,
k
)
=
∇
x
2
L
(
x
,
ψ
′
(
k
f
(
x
)
)
u
)
-
k
∑
i
=
1
r
‍
u
i
ψ
′′
(
k
f
i
(
x
)
)
∇
f
i
(
x
)
∇
f
i
(
x
)
T
.
As a result, the system (31) can be written as(42)
(
∇
x
2
L
(
x
,
ψ
′
(
k
f
(
x
)
)
u
)
-
k
∑
i
=
1
r
‍
u
i
ψ
′′
(
k
f
i
(
x
)
)
∇
f
i
(
x
)
∇
f
i
(
x
)
T
-
∇
f
(
r
)
(
x
)
ψ
+
′
(
k
f
(
x
)
)
ψ
+
′
(
k
f
(
x
)
)
∇
f
(
r
)
(
x
)
T
0
)
×
(
x
^
-
x
u
^
+
-
u
+
)
=
(
-
∇
x
L
(
x
,
ψ
′
(
k
f
(
x
)
)
u
)
-
k
-
1
ψ
+
(
k
f
(
x
)
)
)
.The second equation yields
(43)
ψ
+
′
(
k
f
(
x
)
)
∇
f
(
r
)
(
x
)
T
(
x
^
-
x
)
=
-
k
-
1
ψ
+
(
k
f
(
x
)
)
.
If we form the second-order Taylor series expansion of ψ around t
k,
(44)
ψ
(
t
)
=
ψ
(
t
k
)
+
ψ
′
(
t
k
)
(
t
-
t
k
)
+
1
2
(
t
-
t
k
)
T
ψ
′′
(
t
k
)
(
t
-
t
k
)
,
we obtain
(45)
ψ
′
(
t
)
=
ψ
′
(
t
k
)
+
ψ
′′
(
t
k
)
(
t
-
t
k
)
.
Take t
=
k
f
i
(
x
^
), t
k
=
k
f
i
(
x
), i
=
1
,
…
,
r, and it follows that
(46)
ψ
′
(
k
f
i
(
x
)
)
=
1
-
k
(
x
^
-
x
)
T
∇
f
i
(
x
)
ψ
′′
(
k
f
i
(
x
)
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
=
1
,
…
,
r
.
Substituting (46) into (43), we have
(47)
diag
⁡
1
≤
i
≤
r
⁡
(
1
-
k
(
x
^
-
x
)
T
∇
f
i
(
x
)
ψ
′′
(
k
f
i
(
x
)
)
)
×
∇
f
(
r
)
(
x
)
T
(
x
^
-
x
)
=
-
k
-
1
ψ
+
(
k
f
(
x
)
)
which, when substituted into the first equation in (42), yields
(48)
∇
x
2
L
(
x
,
ψ
′
(
k
f
(
x
)
)
u
)
(
x
^
-
x
)
-
∇
f
(
r
)
(
x
)
ψ
+
′
(
k
f
(
x
)
)
u
^
+
+
2
∇
f
(
r
)
(
x
)
ψ
+
′
(
k
f
(
x
)
)
u
+
-
∇
f
(
r
)
(
x
)
u
+
=
-
L
(
x
,
ψ
′
(
k
f
(
x
)
)
u
)
.
Thus, in view of condition ψ
+
′
2
-
2
ψ
+
′
+
I
=
0, system (42) is equivalent to
(49)
(
∇
x
2
L
(
x
,
ψ
′
(
k
f
(
x
)
)
u
)
-
∇
f
(
r
)
(
x
)
ψ
+
′
(
k
f
(
x
)
)
ψ
+
′
(
k
f
(
x
)
)
∇
f
(
r
)
(
x
)
T
0
)
×
(
x
^
-
x
u
^
+
-
ψ
+
′
(
k
f
(
x
)
)
u
+
)
=
(
-
∇
x
L
(
x
,
ψ
′
(
k
f
(
x
)
)
u
)
-
k
-
1
ψ
+
(
k
f
(
x
)
)
)
.
This shows (39) and (40).In view of (40), we can write (37) as
(50)
u
+
s
+
1
=
u
^
+
(
x
(
u
s
,
k
)
,
u
~
(
u
s
,
k
)
,
0
)
,
u
-
s
+
1
=
0
m
-
r
,
where
(51)
u
~
(
u
s
,
k
)
=
ψ
′
(
k
f
(
x
(
u
s
,
k
)
)
)
u
s
.
This means that one can carry out the second-order multiplier iteration (25), (26) in two stages. First execute the first-order iteration (51) and then the second-order iteration (50), which is part of Newton’s iteration at (
x
(
u
s
,
k
)
)
,
u
~
(
u
s
,
k
) for solving the system of necessary conditions (29).Now, we know thatx
(
u
s
,
k
)
,
u
~
(
u
s
,
k
) is close to (
x
*
,
u
*
) for (
u
s
,
k
) in an appropriate region of ℝ
m
+
1. Therefore, using known results for Newton’s method, we expect that (50) will yield a vector u
s
+
1 which is closer to u
* than u
s. This argument is the basis for the proof of the following proposition.Proposition 5.
Assume (a)–(f) hold, and letk
0
>
0, δ
>
0 be as in Theorem 2. Then, given any scalar γ
>
0, there exists a scalar δ
1 with 0
<
δ
1
≤
δ such that for all (
u
,
k
)
∈
D
1
=
{
(
u
,
k
)
:
u
∈
U
k
(
ε
,
δ
1
)
,
k
≥
k
0
} there holds
(52)
∥
(
x
^
(
u
,
k
)
,
u
^
(
u
,
k
)
)
-
(
x
*
,
u
*
)
∥
≤
γ
k
-
1
∥
u
-
u
*
∥
,
where
(53)
u
s
+
1
=
u
s
-
B
k
-
1
k
-
1
ψ
(
k
f
(
x
(
u
s
,
k
)
)
)
,
where
(54)
B
k
=
ψ
′
(
k
f
(
x
(
u
s
,
k
)
)
)
∇
f
(
x
(
u
s
,
k
)
)
T
×
[
∇
x
2
H
(
x
(
u
s
,
k
)
,
u
s
,
k
)
]
-
1
∇
f
(
x
(
u
s
,
k
)
)
ψ
′
×
(
k
f
(
x
(
u
s
,
k
)
)
)
.
If, in addition, ∇
2
f
i
(
x
), i
=
0
,
…
,
m are Lipschitz continuous in a neighborhood of x
*, there exists a scalar γ
1
>
0 such that,for all
(
u
,
k
)
∈
D
1, there holds
(55)
∥
(
x
^
(
u
,
k
)
,
u
^
(
u
,
k
)
)
-
(
x
*
,
u
*
)
∥
≤
γ
1
k
-
2
∥
u
-
u
*
∥
2
.Proof.
In view of Theorem2, given any γ
>
0, there exist ε
1
>
0
,
ε
2
>
0 and M
>
0 such that if x
(
u
,
k
)
∈
S
(
x
*
,
ε
1
) and u
~
(
u
,
k
)
∈
S
(
u
*
,
ε
2
), there holds
(56)
∥
(
x
^
(
x
(
u
,
k
)
,
u
~
(
u
,
k
)
,
0
)
,
u
^
(
x
(
u
,
k
)
,
u
~
(
u
,
k
)
,
0
)
)
-
(
x
*
,
u
*
)
∥
≤
γ
M
∥
(
x
(
u
,
k
)
,
u
~
(
u
,
k
)
)
-
(
x
*
,
u
*
)
∥
(compare with Proposition 1.17, Bertsekas [8]). Take δ
1 sufficiently small so that, for all (
u
,
k
)
∈
D
1, we have x
(
u
,
k
)
∈
S
(
x
*
,
ε
1
), u
~
(
u
,
k
)
∈
S
(
u
*
,
ε
2
), and
(57)
∥
(
x
(
u
,
k
)
,
u
~
(
u
,
k
)
)
-
(
x
*
,
u
*
)
∥
≤
M
k
-
1
∥
u
-
u
*
∥
.
From (50), we have
(58)
∥
(
x
^
(
x
(
u
,
k
)
,
u
~
(
u
,
k
)
,
0
)
,
u
^
(
x
(
u
,
k
)
,
u
~
(
u
,
k
)
,
0
)
)
-
(
x
*
,
u
*
)
∥
≤
γ
M
·
M
k
-
1
∥
u
-
u
*
∥
=
γ
k
-
1
∥
u
-
u
*
∥
.
If ∇
2
f
i
(
x
)
(
i
=
0
,
…
,
m
) are Lipschitz continuous, then there exists a γ
1
>
0 such that for x
(
u
,
k
)
∈
S
(
x
*
,
ε
) and u
~
(
u
,
k
)
∈
S
(
u
*
,
ε
), we have
(59)
∥
(
x
^
(
x
(
u
,
k
)
,
u
~
(
u
,
k
)
,
0
)
,
u
^
(
x
(
u
,
k
)
,
u
~
(
u
,
k
)
,
0
)
)
-
(
x
*
,
u
*
)
∥
≤
γ
1
2
M
2
∥
(
x
(
u
,
k
)
,
u
~
(
u
,
k
)
)
-
(
x
*
,
u
*
)
∥
2
≤
γ
1
2
M
2
(
(
M
k
-
1
)
2
∥
u
-
u
*
∥
2
+
(
M
k
-
1
)
2
∥
u
-
u
*
∥
2
)
=
γ
1
k
-
2
∥
u
-
u
*
∥
2
.From the above analysis, we know that the sequence generated by the second-order multiplier iteration converges superlinearly with order at least two if the Hessians of functions involved in problem are Lipschitz continuous.



---

*Source: 210284-2014-04-09.xml*