Open Journal of Applied Sciences, 2013, 3, 70-73
doi:10.4236/ojapps.2013.31B1014 Published Online April 2013 (http://www.scirp.org/journal/ojapps)
A Modified Augemented Lagrangian Method for a Class of
Nonlinear Ill-Posed Problems
Mhbm Shariff
Department of Applied Mathematics and Sciences, Khalifa University, Sharjah, UAE
Email: shariff@kustar.ac.ae
Received 2013
ABSTRACT
A class of nonlinear problems with real parameters is defined. Generally, in this class of problems, when the parametric
values are very large, the problems become ill-posed and numerical difficulties are encountered when trying to solve
these problems. In this paper, the nonlinear problems are reformulated to overcome the numerical difficulties associated
with large parametric values. A novel iterative algorithm, which is suitable for large scale problems and can be easily
parallelized, is proposed to solve the reformulated problems. Numerical tests indicate that the proposed algorithm gives
stable solutions. Convergence properties of the proposed algorithm are investigated. In the limiting case, when the cor-
responding constraint is exactly satisfied, the proposed method is equivalent to the standard augmented Lagrangian
method.
Keywords: Iterative Method; Nonlinear; Ill-conditioned; Large Parameter Values; Large-scale
1. Introduction
There are a number of physical problems, where penalty
terms (large parameter) occur naturally in the problems.
For example, in nonlinear isotropic elasticity, the bulk
modulus [1] can be considered as a penalty term for the
incompressible constraint. When the penalty term is very
large the corresponding constraint is nearly satisfied.
Generally, numerical difficulties are encountered, see,
e.g., [2], when trying to solve problems with very large
penalty values.
In this paper we consider a class of parametric prob-
lems that can be reformulated in such a way that the nu-
merical difficulties mentioned above can be overcome.
The reformulated problem generally yields indefinite
system of equations. When such a system is solved using
an existing iterative method, its convergence properties
are generally not as good as an iterative method design
for a symmetric positive definite system. Here, we pro-
posed a novel iterative algorithm to solve the reformu-
lated problem. The proposed algorithm solves a symmet-
ric positive definite system in each iteration. The con-
vergence properties of the proposed algorithm are inves-
tigated and numerical tests are implemented. The algo-
rithm is an extension of the algorithm developed by
Shariff [3] for quadratic problems with (near) linear con-
straints. Our proposed method is suitable for large scale
problems in the sense that it only uses a handful of vec-
tors in the algorithm. The proposed algorithm is easily
parallelized and is especially suitable for sparse system
of equations.
2. A Class of Nonlinear Constrained
Problems
Consider a class of nonlinear problems which is of the
form
Problem (I): Minimize
1
()( ()),
m
i
i
fx εχhx
where
is a real constant (can be considered as a pen-
alty term), 1
and :RR
with the properties
(a)
is twice continuously differentiable and strictly
convex on R
(b) '
(0)0, (0)0

limlim( )l
and
'' (0) 1
''
im( )
(c) .im l
 tt

tt t
Examples of the function t
()t
.
are:
2
9
() [2],
2
()cosh()1 [2],
1
ln( 1)(( 1)1)
9
() [4],
9
()ln(1) [5].


 
t
t
tt
tt
t
tt t
Copyright © 2013 SciRes. OJAppS
M. SHARIFF 71
When
is very large it can be shown that the cor-
responding vector constraint
()hx
0
(12 ) is nearly satisfied and, generally,
numerical difficulties are encountered when trying to
solve Problem (I). For example, a near incompressible
problem often leads to numerical difficulties when a fi-
nite element displacement solution is sought. One way to
overcome these difficulties is to formulate Problem (I) in
an alternative form [3] as given below.
[, ,]h
T
m
hh h
Problem (II): Minimize
1
()(())p
m
i
i
fx g
subject to the constrained
() (),hxg p
where
 

12
[,,],
g
hshT
m
gg g, s is an invertible
function,
 

12
(, [g,g,g]ggg
T
m
ps

,g
T
and p is an m-vector variable. We note in several practi-
cal problems, the function is often approximated [1].
An engineering example of Problem (II) can be found in
Shariff and Parker [1].
h
Using the method of Lagrange multiplier, the solution
of Problem (II) can be obtained from the following
problem.
Problem (III): Find x, p and q such that
() (())fxhx q 0
T
xx (1)
() ()hxg p0
(2)

'
(( ))( ( ))().gpgpg pq
0
T
pp

(3)
We note that Problem (II) can be solved using the
standard augmented Lagrangian method. In the case
when
is very close to zero, it can be easily seen from
Equation (3) that the numerical values of p are not reli-
able due to computations in non-exact arithmetic [3]. In
addition to this, using the standard augmented Lagran-
gian method introduces an unnecessary variable q in the
formulation. To reduce the number of variables from
three to two, we propose a modified augmented Lagran-
gian method to solve an equivalent Problem (IV) given
below. In order to formulate Problem (IV), we assume
that
(())
g
pT
p is nonsingular and hence from Equa-
tion (3) we see that the Lagrange multiplier
1'
( )((( )))(( ))(()),qp
g
p
g
p
g
p
 
TT
pp
(4)
where
(5)
We note that when
'
1
'
'2
'
(g )
(g )
() .
..
(g )
g





m
gg
, we have
'().q
g
(6)
On replacing the Lagrange mult
p
iplier by a function of
given in Equation (4) in the Lagrangian function we
obtain an equivalent statement:
(IV) Find x and p such that 00L
, where
(7)
where is given by Equation (4).
3. A Modified Augmented Lagrangian
Pr solved using a large scale iterative
0
1
()(())( )(( )( )),pqphx gp
 
T
i
i
Lfx g

m
()qp
Method
oblem (IV) can be
method designed for an indefinite system. However, the
convergence properties of most large scale iterative
methods for indefinite systems are generally not as good
as those iterative methods for symmetric positive definite
(SPD) systems. The augmented Lagrangian method, how-
ever, solves a SPD system in each iteration and generally
the solution is obtained in only a few iterations. Here, we
modify this method to solve problem (IV). The modified
algorithm solves a SPD system in each iteration and is
given by:
1. Set 0
i, select pi and a penalty parameter
0
i
c
.
()qqp2. Set
ii
3. ,xmin ()xp
i
ic
xL
i
|() )|hgp
ii
f 4. I
x
tolerance
'
: stop
et
5. )))q
1((( )(qhx gp
 
ii iii
c

6. 1
11
()pqq

ii
7. S1
i; go
nction
to 2
The fu
1
1
(, )()(())()(()
( (()()))
()),
m
T
ci
i
m
ii
i
Lfxg
c
c

 

xppqp hx
hxg p
gp
(8)
In step 6, if
gg
obta
then numerical value of p is
ge
i+1
nerally easier toin numerically than when
gg
.
For example, when()cosh() 1
tt
, we have 1
i
p
1
1
sin ( )
i
hq . In the sen pecial case wh2
()tt
for
gg
2 we
simply have,
, 11
pq

ii
.
Copyright © 2013 SciRes. OJAppS
M. SHARIFF
72
4. Convergence
how in Proposition 1, that under a
e sequences and con-
is boed and
In this section we s
certain conditions th {}xi {}pi
verge to their appropriate values.
Proposition 1: Assume that the sequence { con-
verges to a vector x*, the sequence
}xi
und{}qi
1

ii
cc
. Then the sequence
'
1
{(( ())))}qq hx
 
ii ii
c

(gp
i
converges to a vector which satisfies
(9)
**
()qqp
***
) ()x(xhq 0
T
xx
f
**
() ()hxg p0
Proof: We only consider exact arithmetic calcula
For a given pi, xi minimizes and hence from Equa-
tio
(12)
Here, we assume[2] has a full row r
Hence, in view of steabove equation can be rear-
ra
wher
(10)
 

**1*
(() )qgpgp
 
T
pp


'*
) .gp
T
(11)
tions.
i
n (8) and step 3 we have
(,)xpi
xcii
T
L
c
L
'
0
()(( ))[((( )()))]
(, ) 0.
xxqhxgp
xp
 
 
xi xiiiii
xii
fh c
L

()hxx
p 5, the
ank.
nged to give
1
1() (),qBBBx
 
T
iiiixi
f (13)
e
().
B
hx
ixi
Hence from Equation (13)
As we ha
relati
(14
Since is bounded and
q
it follows that is boued. From
Step 5 in thng to account
*
{}xx
i
we get the
ve 1
qq
k.
on
*
***
()(())0.xhxq 
T
xx
f )
{}qi
'*
{( )))}qh p
i, (( ()g
iii
cx

'((()()))}hgp
ii i
cx

e proposed algorithm and taki
ubsequence (except fo
nd
in
that {}qi is a sr q0) of 1
{}qi, we
have
'(( ()()))}0.hgp
ii i
cx

In view of the prop-
erties of
, we have
**
() ()hxg p
0
. Frep 6
and Eqtion given in Equation
(11).
5. Numerical Test
om st
uation (4) we obtain the rela
For the reader to have
rithm, a simple numeric
confidence in the proposed algo-
al test problem is given. Consider
the simple test problems:
Test 1: Minimize:
22
42
()
(2)2
(2)
2
() 2tt
,
2
() ()
hxhx x y
ulat
and .
We reforme this problem below using the m
c
() ()gp gpp
ethod
given in Section 2:
Find x, y and p suh that00L
, where
2
42 2
0(2)(2)( ). 
p
Lx xypxy
2
given i(8) takes
the form
The function (, ,)
c
Lxyp n Equation
22
0
()
.
2
c


x
yp
c
hird step of the proposed algorithm, the corre-
sponding values of x and y are obtained us ng a nonlinear
conjugate gradient method [6]. The toance for the
con
LL
In the t
i
ler
jugate gradient method is set to and the toler-
ance for the proposed algorithm is set to 6
10
6
10
. We let
500
k
c and the starting value for x, y and p is zero.
The results are tabulated below for several values of
(Tables 1-4)
Test 2: Minimize:
422
( 2)(2)(cosh(())1).
 Fx xyxy

For this problem we have ()cosh()1tt
,
hx

2,
xx y ()gph
()gp
and () sinqp
lem below using th
h()p.
e meod We reformulate this probth
given in Section 2:
Find x, y and p such that 00L
, where
42
0(2)(2) (cos()1)
sin2).( )(
 
Lx xyhp
h
y p
px
Table 1. ε = 0. Number of iterations = 8.
x 0.9456
y 0.8942
p 3.371
Table 2. ε = 10 Numerations = 8.
–6.ber of it
x 0.9456
y 0.8942
p 3.371
Table 3. ε = 10Numerations = 11.
–3. ber of it
x 0.9466
y 0.8927
p 3.355
Table 4. ε = 10erations = 23.
–1. Number of it
x 1.024
x
y
xy
For this problem we have
Fx
y 0.8103
p 2.390
Copyright © 2013 SciRes. OJAppS
M. SHARIFF
Copyright © 2013 SciRes. OJAppS
73
Table 5. ε = erations = 3. 0. Number of it
x 0.9455
y 0.8940
we vary the values of
. As expected, the rate of con-
vergence for 0.1
is not as good as those for smaller
values of
. We must mphasize that the proposed al-
gorithm is devprimarily for 1
e
eloped
.
6. Conclusions
p 1.9301
q 3.371
Table 6. ε = 10 Numerations = 5. To overcome the nu
sociated with high
m
pe
E
. M. S
s Princip
e
nalty
FE
rical difficur problems as-
formulated the
RE
[1] M. HAn Extension of
Key’y,” Journal of
lties fo
values, we re
NCES
, “
icit
–6.ber of it
x 0.9456 problems via the use of Lagrange multipliers. A modified
augmented Lagrangian method is proposed to solve the
reformulated problem. The proposed algorithm is stable
and its solution is shown to converge to its appropriate
value. The numerical test done seems to support the
theoretical analysis.
R
y 0.8941
p 1.930
q 3.371
Table 7. ε = 10 iterations = 3.
–3. Number of
x 0.9462
y 0.8933
p 1.927 . Bhariff and D. F. Parker
le to Nonlinear Elast
q 3.362
Engngineering Mathematics, Vol. 37, No. 1-3, 2000, pp.
Table 8. ε = 10Numerations = 32. 171-190. doi:10.1023/A:1004734311626
–1. ber of it
x 1.001
[2] D. P. Bertsekas, “Constrained Optimization and Lagran-
gian Multiplier Methods,” Athena Scientific, Massachu-
onstrained problems,” Journal of
y 0.832
p 1.702
setts, USA, 1981.
[3] M. H. B. M. Shariff, “ A modified augmented Lagrangian
method for a class of c
q 2.653
Computational and Applied Mathematics, Vol. 151, No. 2,
2003, pp. 257-270. doi:10.1016/S0377-0427(02)00813-0
[4] R. W. Ogden, “Volume Changes Associated with the
Deformation of Rubber-like Solids,” Journal of Mechan-
The function n Equation (8) takes
the form
(, )
c
Lx p ,ygiven i
2
0
cos(())1).

hcx yp
lerance for the conjugate gradient method is set
to and the tolerance for the proposed algorith
. We let and the starting value
y
c
LL c
The to
ics and Physics Solids, Vol. 24, No. 6, 1976, pp. 323-338.
doi:10.1016/0022-5096(76)90007-7
[5] P. J. Blatz, “Finite Elastic Deformation of a Plane Strain
Wedge-Shaped Radial Crack in a C
ompressible Cylin-
ar Parallel Computing and
6
10
set to 10
valu
m is
for x,
der,” Second-Order Effects in Elasticity, Plasticity and
Fluid Dynamics, Pergamon Press, Oxford, 1964, pp.
145-161.
[6] M. H. B. M. Shariff, “Parallel Finite Element Software
for Nonline
6100
k
c
and p is zero. The results are tabulated below for sev-
erales of
(Tables 5-8)
Frome above tale see that the proposed algo-
rithm can also produce solutions for values of
Stress Problems,”
thbs we
that
are not small. The solutions change smoothly (stable) as
Transputer Applications, IOS Press, Amsterdam, 1992,
pp. 1261-1270.