Convergence analysis of the exterior-point
method
I. Griva, R. Polyak
AMS Meeting 2007, Oxford, March 16
*
x

Outline
1. Overview. Equality and inequality constraints. Conceptual
difficulties.
2. Exterior point method (EPM).
3. Local and global convergence analysis of EPM. Numerical results.
4. Conclusion.


Constrained optimization problem
EIXxxf
f
n
∩=∈
ℜ→ℜ
),(min
:
1
X
Equality constraints
{ }
pixgxE
i
n

, ,1,0)(: ==ℜ∈=
Inequality constraints
{ }
mixcxI
i
n
, ,1,0)(: =≥ℜ∈=
abledifferentily continuous twiceare ,,
ii
gcf

Equality constraints
( )
)(), ,()(,0)( s.t.),(min
1
xgxgxgxgxf
p
==
Lagrangian
∑
=
−=
p
i
ii
xgyxfyxL
1
)()(),(
Lagrange multipliers
), ,(

1 p
yyy =
Optimality conditions








=
=∇−∇
⇔
=∇
=∇
0)(
0)()(
0),(
0),(
xg
yxgxf
yxL
yxL
T
y
x
)( ofJacobian theis)( xgxg∇

Optimality conditions









=
=∇−∇
⇔
=∇
=∇
0)(
0)()(
0),(
0),(
xg
yxgxf
yxL
yxL
T
x
λ
)( ofJacobian theis)( xgxg∇
Newton’s method – quadratic convergence rate







−
∇+∇−
=






∆
∆






∇
∇−∇
)(
)()(
0)(
)(),(
2
xg
yxgxf
y
x

xg
xgyxL
TT
x
xxx ∆+=:
ˆ
yyy ∆+=:
ˆ
),(solution enough to close is ),(ion approximat If
**
yxyx
2
**
2
**
ˆ
,
ˆ
yyyyxxxx −≤−−≤−
αα

Inequality constraints
( )
)(), ,()(,0)( s.t.),(min
1
xcxcxcxcxf
m
=≥
)(
1

xc
)(
3
xc
)(
2
xc
)(
4
xc
3
)(
β
=xf
*
2
)(
ββ
==xf
1
)(
β
=xf
321
βββ
>>
{ }
0)(: :set Active
**
== xciI

i
{ }
3,2
*
=I
{ }
0)(: :set Inactive
*0
>= xciI
i
{ }
4,1
0
=I
*
x

Inequality constraints
*
,0)( s.t.),(min Iixcxf
i
∈=
( )
)(), ,()(,0)( s.t.),(min
1
xcxcxcxcxf
m
=≥
⇔
Choosing the active set is a combinatorial problem!!!


Optimality conditions



=
=∇−∇
0)(
0)()(
xY c
yxcxf
T
)( ofJacobian theis)( xcxc∇
Newton’s method






−
∇+∇−
=






∆

∆






∇
∇−∇
)(
)()(
)()(
)(),(
2
xYc
yxcxf
y
x
xCxcY
xcyxL
TT
x
)(
i
yd iagY =
( )
)()( xcdiagxC
i
=
0,0)( ≥≥ yxc

?0,0)( :itynonnegativ eaccount th into take toHow ≥≥ yxc
xxcYxCyy ∆∇−−=∆
−
)()(
solution near theaccuracy of loss Possible
1
Challenges
Complementarity!!!

Interior-point method



=
=∇−∇
exYc
yxcxf
T
µ
)(
0)()(
)( ofJacobian theis)( xcxc∇
Newton’s method






−

∇+∇−
=






∆
∆






∇
∇−∇
)(
)()(
)()(
)(),(
2
xYce
yxcxf
y
x
xCxcY
xcyxL
TT

x
µ
)(
i
yd iagY =
( )
)()( xcdiagxC
i
=
Complementarity relaxation
xxcYxCexCyy ∆∇−+−=∆
−−
)()()(
solution near theaccuracy of loss Possible
11
µ

Questions
1. How to come up with the primal-dual system that does not have
any complementarity related to inequality constraints?
2. How to relax the requirements of keeping the trajectory in the
interior?
3. What would be theoretical convergence properties of such a
method?
4. What would be its practical efficiency?


Outline
1. Overview. Equality and inequality constraints. Conceptual
difficulties.

2. Exterior point method (EPM).
3. Local and global convergence analysis of EPM. Numerical results.
4. Conclusion.


Nonlinear
Rescaling for
inequalities
(Polyak)
Augmented
Lagrangian for
equalities
(Hestenes, Powell)
Exterior point method (EPM)

ψ
( )t
t
)(min xf
( )
0)( s.t.
1
≥
−
xc
i
µµψ
Bertsekas andKort l,Exponentia - 1)(
2
t

et
−
−=
ψ
Polyak Barrier, Modified - )1log()(
1
tt +=
ψ
Equivalent problem
( )
∑
=
−
−=Φ
m
i
ii
xcyxfyx
1
1
)()(),(
µψµ
µ
Lagrangian for the equivalent problem
Nonlinear Rescaling of inequalities (Polyak)
parameterbarrier theis
µ

( )
2

1
1
)(
2
1
)()()(),,( xgxgzxcyxfvyx
T
m
i
ii
µ
µψµ
µ
+−−=Φ
∑
=
−
Augmented Lagrangian for equalities
(Hestenes, Powell)
2
)(
2
1
)()(),,( xgxgzxfvyxA
T
µ
µ
+−=
Nonlinear Rescaling - Augmented Lagrangian
(NRAL)


NRAL
),,(minarg
ˆ
zyxx
n
x
µ
Φ=
ℜ∈
( )
Yexcy )
ˆ
(
ˆ
1−
Ψ
′
=
µ
0),,
ˆ
( =Φ∇ zyx
x
µ
( )
Yexcy )
ˆ
(
ˆ

1−
Ψ
′
=
µ
or
( )
)(diag
))
ˆ
((diag
1
i
i
yY
xc
=
′
=Ψ
′
−
µψ
!!fixed! is
µ
1,0 s.t.
,min
2
≥≥ xx
x
)

ˆ
(
ˆ
1
xgzz
−
−=
µ
)
ˆ
(
ˆ
1
xgzz
−
−=
µ

( )
0))
ˆ
(()
ˆ
()
ˆ
()
ˆ
()
ˆ
(

),,
ˆ
(
1
1
1
=−∇−∇
′
−∇=
Φ∇
−
=
−
∑
xgzxgxcxcyxf
zyx
T
i
m
i
ii
x
µµψ
µ
( )
Yexcy )
ˆ
(
ˆ
1−

Ψ
′
=
µ
Primal-dual NRAL - Exterior point method (EPM)
0
ˆ
)
ˆ
(
ˆ
)
ˆ
()
ˆ
( =∇−∇−∇ zxgyxcxf
TT
( )
Yexcy )
ˆ
(
ˆ
1−
Ψ
′
=
µ
Primal-Dual system
)
ˆ

(
ˆ
1
xgzz
−
−=
µ
)
ˆ
(
ˆ
1
xgzz
−
−=
µ

Exterior point method (EPM)
( )
0)(
ˆ
0)
ˆ
(
ˆ
0
ˆ
)
ˆ
(

ˆ
)
ˆ
()
ˆ
(
1
1
=+−
=Ψ
′
−
=∇−∇−∇
−
−
xgzz
Yexcy
zxgyxcxf
TT
µ
µ
!!method! sNewton' using
)
ˆ
,
ˆ
,
ˆ
(for system thesolve vyx
( )











−
−Ψ
′
∇−
=










∆
∆
∆











∇
∇−
∇−∇−∇
−
−
−
−
)(
)(
),,(
0)(
0)(
)()(),,(
1
1
1
1
2
xg
yYexc
zyxL
z

y
x
Ixg
IxcD
xgxcvyxL
x
TT
xx
µ
µ
µ
µ
( )
)( diag,))((diag)(,)(
1
ii
yYxcYD =
′′
=⋅Ψ
′′
⋅Ψ
′′
=
−
µψ
)( and )( of Jacobians theare )( and )( xgxcxgxc ∇∇
xxx ∆+=:
ˆ
yyy ∆+=:
ˆ

zzz ∆+=:
ˆ

Outline
1. Overview. Equality and inequality constraints. Conceptual
difficulties.
2. Exterior point method (EPM).
3. Local and global convergence analysis of EPM. Numerical results.
4. Conclusion.


Local convergence properties of EPM
Fixed barrier parameter:
.10factor by the ),,( and ),,(between distance the
reduce toEPMfor step oneonly requiresit ),,(),,( and
anyfor such that 0 and0 exists there10any for then )(
and )( ),( Hessians for the hold condtions Lipschitz theand
satisfied are conditions optimalityorder second standard theIf .
****
***
2
22
<<==
Ω∈<
>><<∇
∇∇
γ
µµ
εµγ
γ

εγ
γγ
zyxtzyxt
zyxvyx
xg
xcxf
i
i
Theorem
10,
ˆ
**
<<−≤−
γγ
tttt

Local convergence properties of EPM
Decreasing barrier parameter:
{ }
|)(|,|,)(|),(,),,(max),,(
iiiiix
yxcyxgxczyxLvyxv −−∇=
Merit Function:
),,( zyx
νµ
=
estimation following thesatisfies that )
ˆ
,
ˆ

,
ˆ
(
ˆ
ion approximat dual-primal newobtain torequired isparameter barrier
dynamic with EPMfor step oneonly ),,(),,(
anyfor such that enough small 0 exists then there)(
and)( ),( Hessians for the hold condtions Lipschitz theand
satisfied are conditions optimalityorder second standard theIf .5
***
0
2
22
0
zyxt
zyxzyxt
xg
xcxf
i
i
=
Ω∈=
>∇
∇∇
ε
ε
Theorem
0,
ˆ
5.1

**
>−≤−
θθ
tttt
data. problem on the dependingconstant a is 0 where >
θ

Symmetric Quasidefinite System (Vanderbei, 1995)
( )
[ ]






−Ψ
′
−
∇−∇
=






∆
∆







−∇
∇∇−
−−−
yYexcD
yxcxf
y
x
Dxc
xcyxL
TT
xx
)(
)()(
)(
)(),(
111
2
µµµ






+

∇−∇
=






∆
∆






∇
∇∇−
−−
γρ
11
2
)()(
)(
)(),(
WY
yxcxf
y
x
WYxc

xcyxL
TT
xx






−
FA
AE
T
matrices definite positive symmetric are and FE
)(xcw −=
ρ
yeW −=
−1
µγ
)(
1
yWYw ∆−=∆
−
γ
Interior Point Method
Exterior Point Method
( )
ii
yxcD ))((diag
1−

′′
=
µψ

airport.mod
variables: non-neg 0, free 0, bdd 84, total 84
constraints: eq 0, ineq 42, ranged 0, total 42
nonzeros: A 84, Q 3528

| Primal | Dual | Sig
Iter | Obj Value Infeas | Obj Value Infeas | Fig Status
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 0.000000e+000 1.0e+002 -3.466610e+002 7.3e+001
2 1.317253e+004 2.6e+001 5.917189e+006 1.0e+000
3 2.349387e+004 1.2e+001 1.177748e+006 5.1e-001
4 3.190582e+004 5.1e+000 2.575002e+005 2.9e-001
5 3.783655e+004 5.1e+000 2.575002e+005 2.9e-001
6 4.233652e+004 1.0e+000 5.297997e+004 8.4e-002 1
7 4.626677e+004 2.3e-001 4.795822e+004 1.7e-002 1
8 4.763639e+004 4.1e-002 4.790958e+004 3.0e-003 2
9 4.792720e+004 3.2e-003 4.795102e+004 1.3e-003 3
10 4.795229e+004 9.4e-005 4.795270e+004 9.3e-005 5
11 4.795270e+004 1.6e-007 4.795270e+004 2.5e-007 8
12 4.795270e+004 1.2e-009 4.795270e+004 2.5e-012 9 DF
13 4.795270e+004 5.4e-011 4.795270e+004 9.8e-017 11 PF DF

OPTIMAL SOLUTION FOUND
Times (seconds):
Input = 0.02
Solve = 0.14

Output = 0
Inf = 1e-9
P-d gap = 1e-10

aljazzaf.mod
variables: non-neg 3, free 0, bdd 0, total 3
constraints: eq 1, ineq 0, ranged 0, total 1
nonzeros: A 3, Q 3

| Primal | Dual | Sig
Iter | Obj Value Infeas | Obj Value Infeas | Fig Status
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 7.501500e+001 1.0e+004 7.501500e+001 9.9e-001 60
2 3.941551e+001 2.8e+003 2.541860e+009 1.0e+000
…………………………
10 3.135336e+003 5.4e+000 1.272370e+004 3.3e-002
11 8.206041e+002 5.4e+000 1.272370e+004 3.3e-002
12 5.909210e+001 2.6e+000 1.369778e+003 1.3e-002
13 1.234775e+002 3.3e-001 1.800267e+002 9.8e-003
14 7.081711e+001 1.9e-001 8.850827e+001 3.9e-003 1
15 6.538005e+001 1.1e-001 7.407331e+001 5.4e-004 1
16 7.455193e+001 4.8e-003 7.502332e+001 1.4e-004 2
17 7.498405e+001 2.1e-004 7.500500e+001 1.3e-006 4
18 7.500500e+001 1.7e-008 7.500500e+001 5.3e-010 8 DF
19 7.500500e+001 3.8e-011 7.500500e+001 1.1e-017 10 PF DF
20 7.500500e+001 1.2e-012 7.500500e+001 7.1e-021 12 PF DF

OPTIMAL SOLUTION FOUND
Times (seconds):
Input = 0.02

Solve = 0.12
Output = 0.01
Inf = 1e-9
P-d gap = 1e-10

aug2d.mod
variables: non-neg 0, free 20192, bdd 0, total 20192
constraints: eq 9996, ineq 0, ranged 0, total 9996
nonzeros: A 39984, Q 19800

| Primal | Dual | Sig
Iter | Obj Value Infeas | Obj Value Infeas | Fig Status
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 9.900000e+003 1.0e+000 9.900000e+003 9.9e-001 60
2 3.150554e+005 7.9e-001 1.111293e+006 9.6e-015 DF
3 9.124249e+005 4.2e-001 1.561923e+006 2.1e-014 DF
4 1.429073e+006 1.3e-001 1.676068e+006 2.7e-014 1 DF
5 1.650187e+006 1.9e-002 1.687193e+006 2.7e-014 2 DF
6 1.685957e+006 7.4e-004 1.687411e+006 1.4e-011 3 DF
7 1.687404e+006 3.9e-006 1.687412e+006 6.2e-013 5 DF
8 1.687412e+006 1.0e-009 1.687412e+006 3.3e-014 9 DF
9 1.687412e+006 4.5e-014 1.687412e+006 2.8e-014 13 PF DF

OPTIMAL SOLUTION FOUND
Times (seconds):
Input = 0.34
Solve = 3.565
Output = 0.05
Inf = 1e-9
P-d gap = 1e-10


aug2dc.mod
variables: non-neg 198, free 20002, bdd 0, total 20200
constraints: eq 9996, ineq 0, ranged 0, total 9996
nonzeros: A 39984, Q 20200

| Primal | Dual | Sig
Iter | Obj Value Infeas | Obj Value Infeas | Fig Status
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1 1.010000e+004 1.0e+000 1.029800e+004 1.0e+000 2
2 3.240644e+005 7.9e-001 1.176603e+006 9.7e-002
3 9.550091e+005 4.4e-001 1.672284e+006 1.2e-001
4 1.518864e+006 1.4e-001 1.804192e+006 1.2e-001 1
5 1.772347e+006 2.2e-002 1.818080e+006 3.1e-003 2
6 1.816403e+006 9.3e-004 1.818392e+006 1.7e-011 3 DF
7 1.818380e+006 5.8e-006 1.818393e+006 8.2e-013 5 DF
8 1.818393e+006 1.6e-007 1.818393e+006 3.8e-014 9 DF
9 1.818393e+006 4.5e-008 1.818393e+006 2.9e-014 12 DF
10 1.818393e+006 2.2e-008 1.818393e+006 2.9e-014 12 DF
11 1.818393e+006 8.6e-009 1.818393e+006 3.0e-014 12 DF
12 1.818393e+006 2.3e-009 1.818393e+006 2.9e-014 13 DF
13 1.818393e+006 3.7e-010 1.818393e+006 2.9e-014 14 DF
14 1.818393e+006 2.5e-011 1.818393e+006 2.9e-014 15 PF DF

OPTIMAL SOLUTION FOUND
Times (seconds):
Input = 0.35
Solve = 4.997
Output = 0.01
Inf = 1e-9

P-d gap = 1e-10