 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  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., , 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  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()( ()),miifx εχ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 tExamples of the function t()t.  are: 29() ,2()cosh()1 ,1ln( 1)(( 1)1)9() ,9()ln(1) . ttttttttt t Copyright © 2013 SciRes. OJAppS M. SHARIFF 71When  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  as given below. [, ,]hTmhh hProblem (II): Minimize 1()(())pmiifx g subject to the constrained () (),hxg p where  12[,,], ghshTmgg g, s is an invertible function,  12(, [g,g,g]gggTmps,gT and p is an m-vector variable. We note in several practi-cal problems, the function is often approximated . An engineering example of Problem (II) can be found in Shariff and Parker . hUsing 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 0Txx (1) () ()hxg p0 (2) '(( ))( ( ))().gpgpg pq0Tpp (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 . 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 (())gpTp is nonsingular and hence from Equa- tion (3) we see that the Lagrange multiplier 1'( )((( )))(( ))(()),qpgpgpgp TTpp (4) where  (5) We note that when '1''2'(g )(g )() ...(g )gm gg, we have '().qg (6) On replacing the Lagrange multp 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 01()(())( )(( )( )),pqphx gp TiiLfx gm()qp Method oblem (IV) can bemethod 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ic. ()qqp2. Set ii 3. ,xmin ()xpiicxLi|() )|hgpii f 4. Ixtolerance' : stop et 5. )))q 1((( )(qhx gp ii iiic6. 111()pqqii7. S1i; go nction to 2The fu11(, )()(())()(()( (()())) ()),mTciimiiiLfxgcc xppqp hxhxg pgp (8) In step 6, if gg obtathen numerical value of p is gei+1nerally easier toin numerically than when gg. For example, when()cosh() 1tt, we have 1ip 11sin ( )ihq . In the sen pecial case wh2()tt for gg2 wesimply have,, 11pq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 scertain conditions th {}xi {}piverge to their appropriate values. Proposition 1: Assume that the sequence { con-verges to a vector x*, the sequence }xiund{}qi1iicc. Then the sequence '1{(( ())))}qq hx ii iic (gpiconverges to a vector which satisfies (9) **()qqp***) ()x(xhq 0Txxf **() ()hxg p0  Proof: We only consider exact arithmetic calculaFor a given pi, xi minimizes and hence from Equa-tio (12) Here, we assume has a full row rHence, in view of steabove equation can be rear-rawher (10)  **1*(() )qgpgp Tpp'*) .gpT (11) tions. in (8) and step 3 we have  (,)xpixciiTLcL '0()(( ))[((( )()))](, ) 0.xxqhxgpxp  xi xiiiiixiifh cL ()hxx p 5, the ank. nged to give 11() (),qBBBx Tiiiixif (13) e ().BhxixiHence from Equation (13) As we harelati (14Since is bounded and qit follows that is boued. From Step 5 in thng to account *{}xxiwe get the ve 1qqk. on ****()(())0.xhxq Txxf ) {}qi'*{( )))}qh pi, (( ()giiicx'((()()))}hgpii icxe proposed algorithm and takiubsequence (except fondinthat {}qi is a sr q0) of 1{}qi, we have '(( ()()))}0.hgpii icx In view of the prop-erties of , we have **() ()hxg p0. Frep 6 and Eqtion given in Equation (11). 5. Numerical Test om stuation (4) we obtain the relaFor the reader to have rithm, a simple numericconfidence in the proposed algo-al test problem is given. Consider the simple test problems: Test 1: Minimize: 2242()(2)2(2)2() 2tt,2() ()hxhx x yulat and . We reforme this problem below using the mc () ()gp gppethod given in Section 2: Find x, y and p suh that00L, where 242 20(2)(2)( ). pLx xypxy 2given i(8) takes the form The function (, ,)cLxyp n Equation 220().2cxypchird step of the proposed algorithm, the corre-sponding values of x and y are obtained us ng a nonlinear conjugate gradient method . The toance for the conLL In the tilerjugate gradient method is set to and the toler-ance for the proposed algorithm is set to 610610  . We let 500kc 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 thh()p. e meod We reformulate this probthgiven in Section 2: Find x, y and p such that 00L, where 420(2)(2) (cos()1) sin2).( )( Lx xyhph 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 itx 0.9456 y 0.8942 p 3.371 Table 3. ε = 10Numerations = 11. –3. ber of itx 0.9466 y 0.8927 p 3.355 Table 4. ε = 10erations = 23. –1. Number of itx 1.024 xyxy For this problem we have Fxy 0.8103 p 2.390 Copyright © 2013 SciRes. OJAppS M. SHARIFF Copyright © 2013 SciRes. OJAppS 73Table 5. ε = erations = 3. 0. Number of itx 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eeloped . 6. Conclusions p 1.9301 q 3.371 Table 6. ε = 10 Numerations = 5. To overcome the nusociated with high mpeE. M. Ss Principenalty FErical difficur problems as-formulated the RE M. HAn Extension of Key’y,” Journal of lties fovalues, we reNCES , “icit–6.ber of itx 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. Ry 0.8941 p 1.930 q 3.371 Table 7. ε = 10 iterations = 3. –3. Number ofx 0.9462 y 0.8933 p 1.927 . Bhariff and D. F. Parkerle to Nonlinear Elastq 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 itx 1.001  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.  M. H. B. M. Shariff, “ A modified augmented Lagrangian method for a class of cq 2.653 Computational and Applied Mathematics, Vol. 151, No. 2, 2003, pp. 257-270. doi:10.1016/S0377-0427(02)00813-0  R. W. Ogden, “Volume Changes Associated with the Deformation of Rubber-like Solids,” Journal of Mechan- The function n Equation (8) takesthe form (, )cLx p ,ygiven i 20cos(())1).hcx yplerance for the conjugate gradient method is setto and the tolerance for the proposed algorith. We let and the starting valuey cLL c The toics and Physics Solids, Vol. 24, No. 6, 1976, pp. 323-338. doi:10.1016/0022-5096(76)90007-7  P. J. Blatz, “Finite Elastic Deformation of a Plane Strain Wedge-Shaped Radial Crack in a C ompressible Cylin-ar Parallel Computing and 610 set to 10 valum is for x, der,” Second-Order Effects in Elasticity, Plasticity and Fluid Dynamics, Pergamon Press, Oxford, 1964, pp. 145-161.  M. H. B. M. Shariff, “Parallel Finite Element Software for Nonline6100kc 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) asTransputer Applications, IOS Press, Amsterdam, 1992, pp. 1261-1270.