ENGR OPTIMIZATION ISEN 629
Popular in Course
Popular in Industrial Engineering
This 4 page Class Notes was uploaded by Ms. Hipolito Willms on Wednesday October 21, 2015. The Class Notes belongs to ISEN 629 at Texas A&M University taught by Sergiy Butenko in Fall. Since its upload, it has received 47 views. For similar materials see /class/226197/isen-629-texas-a-m-university in Industrial Engineering at Texas A&M University.
Reviews for ENGR OPTIMIZATION
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/21/15
ISEN 629 Engineering Optimization Lecture 21 Sergiy Buten k0 Industrial and Systems Engineering Texas AampM University Fall 2007 11n Sta ndard Newton method 0 Choose X0 6 dom f 1 m Xk 7 Hairym k 2 o enote by AW lle erllx Theorem 4113 Let AfX lt 1 Then wfgtlt S RX RX S 040 W O dX S llX Xlllx S 0404 WWW S RX RX S MAM Where the last inequality holds for rX lt 1 21n Standard Newton method Theorem 4114 LetX E dom f and AfX lt 1 Then the point x x e if xr1r x belongs to don f and MX S 2 X Thus to guarantee that AfX lt AfX we need to have 3 7 5 Mx lt A Tf 03819 where X is the root of the equation 13A 1 31n Solution strategy gt First stage AfXk 2 where 6 0 Apply the damped Newton method At each iteration we have fXk1 S WW M l The number of steps N for this stage is bounded by 1 N lt f X 7 f X mi 0 M gt Second stage AfXk g Apply the standard Newton method We have the quadratic rate of convergence Even though the damped Newton method also has quadratic rate of convergence the proposed strategy gives better complexity oun 610 Self concordant barriers motivation gt Denote by Dom f c1dom f gt By standard constrained minimization problem we will mean a problem in the form nEiB cTX7 where Q is a closed convex set We also assume that we know a selfconcordant function f such that Dom f gt Consider a parametric barrier function ftX tcTX t39X7 t 2 0 gt Note that t39tX is selfconcordant in X gt Denote by Xt erg min t39tX xEdom f gt Xt is called the central path of the problem gt Can we expect that Xt gt Xquot as t gt oo sm Self concorda nt barriers motivation Recall the general scheme of the barrier function method Barrier function method 0 Choose X0 6 intQ Choose a sequence of penalty coefficients 0 lt tk lt tk and rk H00 1 kth iteration k 2 0 Find a point Xk1 erg mi3 X tikFX using Xk as a XE starting point Denote by WAX thX iFX 1 mig JIAX xe tk Theorem 132 Let barrier FX be bounded from below on Q Then lim W Where W is the optimal value of the considered Hoe probem ntn Self concordant barriers motivation The region of quadratic convergence of the standard Newton method applied to minimization of t39tX is given by 37 AnnW S lt X 2 Assume that we know X Xt for some t gt 0 Then FONC yield the following central path equation tc 00 0 We want to increase t while keeping X within the region of quadratic convergence of the Newton method for ft A ttAAgt0 AHHAMX S lt X ma Self concorda nt barriers motivation Note that the increase in t does not change the Hessian f t AX f tX Also from the central path equation we have tc f X 0 Therefore ftAX S is equivalent to ftAX llf fAXllx llfcAc f gtltllx Allcllx llf gtltllx S t If we increase t at a linear rate then the last inequality requires that 300 iiiMil E XTt39quotgtlt 1f gtlt is uniformly bounded on don f This is guaranteed by the following definition of selfconcordant barriers W Self concordant barriers definition Definition A standard selfconcordant function FX is called u self concordant barrier for set Dom F i sup 2F XTu 7 uTF Xu g u uER for all X E don F The value u is called the parameter of the barrier If we assume that F X is nondegenerate then the above inequality is equivalent to VAX llF Xlli E F XTFquotX 1F X S V Equivalent definitions 1 F XTu2 g uuTF Xu Vu E Rquot 2 F X F XF XT W Self concorda nt barriers exa m ples 1 Linear function fX aTX bdom f Rquot is not a selfconcordant barrier since f X 0 N Convex quadratic function fX XTAXJr bTX cd0m f Rquot is not a selfconcordant barrier since f XTf X 1f X AX bTA 1AX b XTAX 2bTX bA lb is not bounded from above on Rquot 101n Self concordant barriers examples 3 Logarithmic barrier for a ray FX 7InXdomF XE 1RXgt0 Then F X 71XF X 1X2 gt 0 and Thus FX is a u self concordant barrier for X E R X gt 0 with u 1 111n Self concorda nt barriers exa m ples 4 Logarithmic barrier for a quadratic region Let A AT 2 0 Consider the concave function x me bTX c Let FX 7 In X dom F X 6 1Rquot X gt 0 Then F XTu 736b7u 7 XTAu uTF Xu VAX bTu 7 XTAu2 WESUTAu Denote by an F XTu and tag v5 uTAu Then uTF Xu w w2 2 bf 2F XTu 7 uTF Xu g 2w1 7 u g 1 Therefore FX is a u self concordant barrier with u 1 12m Self concordant barriers properties Theorem 421 If FX is a selfconcordant barrier then cTX FX is a selfconcordant function on dom Theorem 422 Let F be usef concordant barriers i 12 Then the function FX F1X F2X is a selfconcordant barrier for o F Dom F1 F7 Dom F2 With the parameter u m V2 Theorem 423 Let AX AX b be a linear operator AX 1Rquot gt R quot If Fy is a usef concordant barrier then X FAX is a usef concordant barrier for the set DomCD XE 1Rquot AX EDom F 131n Self concordant barriers properties Theorem 424 1 Let FX be a usef concordant barrier Then for any X and y from dom F We have FXTy 7 x lt u Moreover if F XTy 7 X 2 0 then I T 7 Fm 7 mom 7 x 2 2 A standard selfconcordant function FX is a usef concordant barrier if and only if Fy 2 FX 7 uln lt17 imam 7xgt my 6 dom F 1o1n Self concordant barriers properties Theorem 425 Let FX be a usef concordant barrier Then for anyX E don F and anyy E Dom F such that F XTy X 2 07 We have iiyixiix MN Definition Let FX be a uself concordant barrier for the set Dom F The point X 39 F X F goat39s F lt is called the analytic center of convex set Dom F generated by the barrier FX 151n Self concorda nt barriers properties Theorem 426 Assume that the analytic center ofa usef concordant barrier FX eXists Then for anyX E Dom F We have iixixiiix Hm On the other hand for anyX 6 Rquot such that HX 7 XEHX g 1 We have X E Dom F Corollary IfDom F is bounded then for anyX E don F and v 6 Rquot We have ii vii S V 2 ii viii 1n1n