Transcription of Nonlinear Constrained Optimization: Methods and Software
1 ARGONNE NATIONAL LABORATORY9700 South Cass AvenueArgonne, Illinois 60439 Nonlinear Constrained optimization : Methods and SoftwareSven Leyffer and Ashutosh MahajanMathematics and Computer Science DivisionPreprint ANL/MCS-P1729-0310 March 17, 2010 This work was supported by the Office of Advanced Scientific Computing Research, Office of Science, Departmentof Energy, under Contract Background and Introduction12 Convergence Test and Termination Conditions23 Local Model: Improving a Solution Linear and Quadratic Programming.
2 Methods ..54 Globalization Strategy: Convergence from Remote Starting Lagrangian Methods .. and Merit Function Methods .. and Funnel Methods .. Effect and Loss of Fast Convergence .. 105 Globalization Methods .. Methods .. 116 Nonlinear optimization Software : Summary127 Interior-Point .. 158 Sequential Linear/Quadratic .. SQPlab .. 209 Augmented Lagrangian .. 2210 Termination of NCO Normal Termination at KKT Points .. Termination at Other Critical Points.
3 Remedies If Things Go Wrong .. 2311 Calculating Derivatives2412 Web Resources24iiiivNonlinear Constrained optimization : Methods and Software Sven Leyffer and Ashutosh Mahajan March 17, 2010 AbstractWe survey the foundations of nonlinearly Constrained optimization Methods , emphasiz-ing general Methods and highlighting their key components, namely, the local model andglobal convergence mechanism. We then categorize current Software packages for solvingconstrained Nonlinear optimization problems.
4 The packages include interior-point Methods ,sequential linear/quadratic programming Methods , and augmented Lagrangian Methods . Forevery package we highlight the main methodological components and provide a brief sum-mary of interfaces and availability. We also comment on termination conditions of nonlinearsolvers and provide a list of online optimization : Mathematical programming Methods , Newton-type Methods , Nonlinear pro-gramming, interior-point Methods , sequential quadratic programming, sequential linearprogrammingAMS-MSC2000.
5 49M05, 49M15, 49M37, 65K05, 90C30, 90C51, 90C551 Background and IntroductionNonlinearly Constrained optimization problems (NCOs) are an important class of problems witha broad range of engineering, scientific, and operational applications. For ease of presentation, weconsider NCOs of the formminimizexf(x)subject toc(x) = 0andx 0,( )where the objective function,f:IRn IR, and the constraint functions,c:IRn IRm, are twicecontinuously differentiable. We denote the multipliers corresponding to the equality constraints,c(x) = 0, byyand the multipliers of the inequality constraints,x 0, byz 0.
6 An NCO may alsohave unbounded variables, upper bounds, or general range constraints of the formli ci(x) ui,which we omit for the sake of simplicity. Preprint ANL/MCS-P1729-0310 Mathematics and Computer Science Division,Argonne National Laboratory,Argonne,IL Mathematics and Computer Science Division,Argonne National Laboratory,Argonne,IL Leyffer and Ashutosh MahajanIn general, one cannot solve ( ) directly or explicitly. Instead, an iterative method is used thatsolves a sequence of simpler, approximate subproblems to generate a sequence of approximatesolutions,{xk}, starting from an initial guess,x0.
7 A simplified algorithmic framework for solving( ) is as initial estimatex0 IRn, setk= 0;whilexkis not optimaldorepeatApproximately solve and refine a local model of ( ) improved solution estimatexk+1is found;Check whetherxk+1is optimal; setk=k+ 1: Framework for Nonlinear optimization MethodsIn this paper, we review the basic components of Methods for solving NCOs. In particular,we review the four fundamental components of Algorithm 1: theconvergence testthat checks foroptimal solutions or detects failure; thelocal modelthat computes an improved new iterate; theglobalization strategythat ensures convergence from remote starting points, by indicating whethera new solution estimate is better than the current estimate.
8 And theglobalization mechanismthattruncates the step computed by the local model to enforce the globalization strategy, effectivelyrefining the local for NCOs are categorized by the choice they implement for each of these funda-mental components. In the next section, we review the fundamental building blocks of methodsfor nonlinearly Constrained :Throughout this paper, we denote iterates byxk,k= 1,2,.., and we use subscripts toindicate functions evaluated at an iterate, for example,fk=f(xk)andck=c(xk).
9 We also denotethe gradients bygk= f(xk)and the Jacobian byAk= c(xk). The Hessian of the Lagrangian isdenoted Convergence Test and Termination ConditionsWe start by describing the convergence test, a common component among all NCO convergence test also provides the motivation for many local models that are described convergence analysis of NCO algorithms typically provides convergence only to KKT suitable approximate convergence test is thus given by c(xk) and gk Akyk zk and min(xk,zk) ,( )
10 Where >0is the tolerance and theminin the last expression corresponding to complementaryslackness is taken Constrained optimization : Methods and Software3In practice, it may not be possible to ensure convergence to an approximate KKT point, forexample, if the constraints fail to satisfy a constraint qualification (Mangasarian, 1969, Ch. 7). Inthat case, we replace the second condition by Akyk+zk ,which corresponds to a Fritz-John Stationary PointsUnless the NCO is convex or some restrictive assumptions aremade, Methods cannot guarantee convergence even to a feasible point.
