A Modified Augemented Lagrangian Method for a Class of Nonlinear Ill-Posed Problems

doi:10.4236/ojapps.2013.31B1014

Paper Menu >>

Journal Menu >>

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: [email protected]

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

()( ()),





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( )



 tt



tt t

Examples of the function t

()t



are:

() [2],

()cosh()1 [2],

ln( 1)(( 1)1)

() [4],

()ln(1) [5].











 

tt t



M. SHARIFF 71

When



is very large it can be shown that the cor-

responding vector constraint

()hx



(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

hh h

Problem (II): Minimize

()(())p





fx g





subject to the constrained



() (),hxg p



where

 





[,,],

hshT

gg g, s is an invertible

function,



 



(, [g,g,g]ggg



,g



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].



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

xx (1)



() ()hxg p0



(2)





(( ))( ( ))().gpgpg pq



0



(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



(())

pT

p is nonsingular and hence from Equa-

tion (3) we see that the Lagrange multiplier



( )((( )))(( ))(()),qp



 



(4)

where



(5)

We note that when

(g )

() .

(g )



















, we have



'().q



 (6)

On replacing the Lagrange mult

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 00L



, where

(7)

where is given by Equation (4).

3. A Modified Augmented Lagrangian

Pr solved using a large scale iterative



()(())( )(( )( )),pqphx gp



 

T

Lfx g







()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



()qqp2. Set



3. ,xmin ()xp





|() )|hgp

f 4. I

tolerance



: stop

5. )))q



1((( )(qhx gp

 

ii iii





6. 1

()pqq





7. S1



i; go

nction

to 2

The fu



(, )()(())()(()

( (()()))

()),

Lfxg







 







xppqp hx

hxg p



(8)

In step 6, if





obta

then numerical value of p is

i+1

nerally easier toin numerically than when





For example, when()cosh() 1



tt



, we have 1



sin ( )





hq . In the sen pecial case wh2

()tt



for



2 we

simply have,



, 11





M. SHARIFF

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





. Then the sequence



{(( ())))}qq hx

 

ii ii





(gp

converges to a vector which satisfies

(9)

()qqp



***

) ()x(xhq 0



() ()hxg p0





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-

wher

(10)



 



**1*

(() )qgpgp



 



) .gp



(11)

tions.

n (8) and step 3 we have



(,)xpi

xcii



()(( ))[((( )()))]

(, ) 0.

xxqhxgp

 

 

xi xiiiii

xii

fh c



()hxx

p 5, the

ank.

nged to give

1() (),qBBBx



 

iiiixi

f (13)



().

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

we get the

ve 1





***

()(())0.xhxq 

f )

{}qi



{( )))}qh p

i, (( ()g

iii





'((()()))}hgp

ii i



e proposed algorithm and taki

ubsequence (except fo

that {}qi is a sr q0) of 1

{}qi, we

have



'(( ()()))}0.hgp

ii i



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:

()

(2)2



(2)

() 2tt





() ()



hxhx x y

ulat

and .

We reforme this problem below using the m



() ()gp gpp

ethod

given in Section 2:

Find x, y and p suh that00L



, where

42 2

0(2)(2)( ). 

Lx xypxy



given i(8) takes

the form

The function (, ,)

Lxyp n Equation

()







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

In the t

ler

jugate gradient method is set to and the toler-

ance for the proposed algorithm is set to 6

10 



. We let

500



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















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 00L



, where

0(2)(2) (cos()1)

sin2).( )(



 



Lx xyhp





y p



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



For this problem we have

y 0.8103

p 2.390

M. SHARIFF

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

eloped



6. Conclusions

p 1.9301

q 3.371

Table 6. ε = 10 Numerations = 5. To overcome the nu

sociated with high

. M. S

s Princip

nalty

rical difficur problems as-

formulated the

[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.

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

(, )

Lx p ,ygiven i

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



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

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

6100

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.