[PDF] A LIMITED MEMORY ALGORITHM FOR BOUND CONSTRAINED

View - Download A LIMITED MEMORY ALGORITHM FOR BOUND CONSTRAINED

Previous PDF

Next PDF

NORTHWESTERN UNIVERSITYDepartment of Electrical Engineeringand Computer ScienceA LIMITED MEMORY ALGORITHM FOR BOUNDCONSTRAINED OPTIMIZATIONbyRichardH?Byrd

?? Peihuang Lu ??Jorge Nocedal ?and Ciyou Zhu ?Technical Rep ort NAM???Revised? May

?Computer Science Department? University of Colorado at Boulder? Boulder Colorado ???? This author wassupp orted by NSF grant CCR?

? ARO grantDAAL ??G? ? and AFOSR grantAFOSR???? Department of Electrical Engineering and Computer Science? Northwestern University?Evanston Il ??? no cedaleecsnwuedu These authors were supp orted by National Science Foundation Grants CCR?? andASC?? and by Department of Energy GrantDEFG??ER ?A??

A LIMITED MEMORY ALGORITHM FOR BOUNDCONSTRAINED OPTIMIZATIONbyRichardH?Byrd? Peihuang Lu? Jorge Nocedal and Ciyou ZhuABSTRACTAn algorithm for solving large nonlinear optimization problems with simple b ounds is de?

scrib ed? It is based on the gradient pro jection metho d and uses a limited memory BFGSmatrix to approximate the Hessian of the ob jective function? It is shown howtotakeadvan?tage of the form of the limited memory approximation to implement the algorithm e?ciently?The results of numerical tests on a set of large problems are rep orted?Key words?b ound constrained optimization limited memory metho d nonlinear optimizationquasi?Newton metho d large?scale optimizationAbbreviated title?A Limited Memory Metho d?? Intro duction?In this pap er we describ e a limited memory quasi?Newton algorithm for solving large nonlinearoptimization problems with simple b ounds on the variables We write this problem asminf

x ?sub ject tol?x?u? ?wheref??

n??is a nonlinear function whose gradientgis available the vectorslandurepresentlower and upp er b ounds on the variables and the number of variablesnis assumedto b e large The algorithm do es not require second derivatives or knowledge of the structure ofthe ob jective function and can therefore b e applied when the Hessian matrix is not practical tocompute A limited memory quasi?Newton up date is used to approximate the Hessian matrix insuchaway that the storage required is linear inn

The algorithm describ ed in this pap er is similar to the algorithms prop osed by Conn Gouldand Toint

and More and Toraldo

? in that the gradient pro jection metho d is used to deter?mine a set of active constraints at each iteration Our algorithm is distinguished from the thesemetho ds by our use of line searches

as opp osed to trust regions but mainly by our use of limitedmemory BFGS matrices to approximate the Hessian of the ob jective function The prop ertiesof these limited memory matrices have far reaching consequences in the implementation of themetho d as will b e discussed later on We nd that by making use of the compact representationsof limited memory matrices describ ed by Byrd No cedal and Schnab el

the computational costof one iteration of the algorithm can b e kepttobeofordernWe used the gradient pro jection approach

to determine the active set b ecauserecent studies

indicate that it p ossess go o d theoretical prop erties and b ecause it alsoapp ears to b e ecientonmany large problems

? However some of the main comp onentsof our algorithm could b e useful in other frameworks as long as limited memory matrices areused to approximate the Hessian of the ob jective function?? Outline of the algorithm?

At the b eginning of each iteration the current iteratexk the function valuefk the gradientg k and a p ositive denite limited memory approximationBk are given This allows us to form aquadratic mo del offatxk m k xf xk g Tk x?xk x?xk TB k x?xk ?Just as in the metho d studied by Conn Gould and Toint the algorithm approximately min?imizesmk x sub ject to the b ounds given by

This is done by rst using the gradientpro jection metho d to nd a set of active b ounds followed by a minimization ofmk

treating thoseb ounds as equality constraintsTo do this we rst consider the piece?wise linear pathx tP xk ?tgk ?l?u?obtained by pro jecting the steep est descent direction onto the feasible region whereP x? l ? ui l i ifxi ?lix i ifxi li ?ui u i ifxi ?ui ?We then compute the generalized Cauchypointx c which is dened as the rst lo cal minimizerof the univariate piece?wise quadraticq k tmk x t?The variables whose value atx cis at lower or upp er b ound comprising the activesetA x c areheld xed We then consider the following quadratic problem over the subspace of free variables minfmk x?xi x ci ?iA x cg ?sub ject toli ?xi ?ui iA x c? ?We rst solve or approximately solve

ignoring the b ounds on the free variables whichcanb e accomplished either by direct or iterative metho ds on the subspace of free variables or byadual approach handling the active b ounds in

by Lagrange multipliers When an iterativemetho d is employed we usex

cas the starting p oint for this iteration We then truncate the pathtoward the solution so as to satisfy the b ounds

After an approximate solution xk??

of this problem has b een obtained we compute the newiteratexk?? by a line search alongdk xk?? ?xk that satises the sucient decrease conditionf xk?? ?f xk k g Tk d k ?and that also attempts to enforce the curvature conditionjg Tk?? d k j?jg Tk d k j? ?wherek is the steplength andare parameters that have the values ?

??and ?? resp ectivelyin our co deThe line search which ensures that the iterates remain in the feasible region isdescrib ed inx Wethenevaluate the gradientatxk??

compute a new limited memory HessianapproximationBk?? and b egin a new iterationBecause in our algorithm every Hessian approximationBk is p ositive denite the approximatesolution xk?? of the quadratic problem denes a descent directiondk xk?? ?xk forthe ob jective functionfTo see this rst note that the generalized Cauchypointx c whichisaminimizer ofmk x on the pro jected steep est descent direction satisesmk xk ?mk x cifthepro jected gradient is nonzero Since the p ointxk?? is on a path fromx cto the minimizer of along whichmk decreases the value ofmk at xk?? is no larger than its value atx c Therefore wehavef xk mk xk ?mk x cmk xk?? f xk g Tk d k d Tk B k dk ?This inequality implies thatg Tk d k ??ifBk is p ositive denite anddk

is not zero In this pap erwe do not presentanyconvergence analysis or study the p ossibility of zigzagging However giventhe use of gradient pro jection in the step computation webelieve analyses similar to those in

and

should b e p ossible and that zigzagging should only b e a problem in the degenerate caseThe Hessian approximationsBk

used in our algorithm are limited memory BFGS matrices

No cedal

and Byrd No cedal and Schnab el

Even though these matrices do not takeadvantage of the structure of the problem they require only a small amount of storage and as wewill show allow the computation of the generalized Cauchy p oint and the subspace minimizationto b e p erformed inO

n op erationsThe new algorithm therefore has similar computationaldemands as the limited memory algorithm

L?BFGS for unconstrained problems describ ed byLiu and No cedal ? and Gilb ert and Lemarechal

In the next three sections we describ e in detail the limited memory matrices the computationof the Cauchy p oint and the minimization of the quadratic problem on a subspace

?? Limited Memory BFGS Matrices?In our algorithm the limited memory BFGS matrices are represented in the compact formdescrib ed by Byrd No cedal and Schnab el

Atevery iteratexk the algorithm stores a smallnumb er saym of correction pairsfsi ?yi g?ik??????k?m wheres k xk?? ?xk ?yk gk?? ?gk

?These correction pairs contain information ab out the curvature of the function and in conjunctionwith the BFGS formula dene the limited memory iteration matrixBk

The question is howtob est represent these matrices without explicitly forming themIn it is prop osed to use a compact or outer pro duct form to dene the limited memorymatrixBk in terms of thenmcorrection matricesY k yk?m ?????yk?? ?Sk sk?m ?????sk?? ?More sp ecically it is shown in that ifis a p ositive scaling parameter and if themcorrectionpairsfsi ?yi g k?mik?? satisfys Ti y i ?? then the matrix obtained by up datingI m?times using theBFGS formula and the pairsfsi ?yi g k?mik?? can b e written asB k I?Wk Mk W Tk ?where W k hY k Sk i ?M k ?Dk L TkL k S Tk S k ?and whereLk andDk are themmmatrices Lk i?j sk?m???i T yk?m???j ifi?j?otherwise? ?D k diag hs Tk?m y k?m ?????s Tk?? y k?? i

We should p oint out that

is a slight rearrangement of equation in Note thatsinceMk is a mmmatrix and sincemis chosen to b e a small integer the cost of computingthe inverse in is negligible It is shown in that by using the compact representation various computations involvingBk b ecome inexp ensive In particular the pro duct ofBk

times avector which o ccurs often in the algorithm of this pap er can b e p erformed ecientlyThere is a similar representation of the inverse limited memory BFGS matrixHk

that ap?proximates the inverse of the Hessian matrix?H k I W k M k W Tk where W k h Y k Sk i M k ??R ??k?R ?Tk R ?Tk Dk Y Tk Y k R ??k ?and Rk i?j sk?m???i T yk?m???j ifi?j?otherwise

We note that

is a slight rearrangement of equationquotesdbs_dbs47.pdfusesText_47

[PDF] Limite et asymptote

[PDF] limite et continuité 1ere s pdf

[PDF] limite et continuité exercices

[PDF] limite et continuité exercices corrigés bac science

[PDF] limite et continuité pdf

[PDF] limite et continuité terminale s

[PDF] Limite et Factoriel

[PDF] Limite et image de fonction

[PDF] Limite et suite

[PDF] limite exponentielle en 0

[PDF] limite exponentielle et logarithme

[PDF] Limite finie de suite

[PDF] limite fonction

[PDF] limite fonction racine nième

[PDF] limite fonction rationnelle en 0