Vector Space Methods in System Optimization
Vector Space Methods in System Optimization MA 719
Popular in Course
Popular in Mathematics (M)
This 63 page Class Notes was uploaded by Braeden Lind on Thursday October 15, 2015. The Class Notes belongs to MA 719 at North Carolina State University taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/223722/ma-719-north-carolina-state-university in Mathematics (M) at North Carolina State University.
Reviews for Vector Space Methods in System Optimization
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/15/15
Chapter 3 Duality in Banach Space Modern optimization theory largely centers around the interplay of a normed vector space and its corresponding dual The notion of duality is important for the following reasons 1 Dual space plays a role in the Banach space analogous to the inner product in a Hilbert space With suitable interpretation7 we can generalize the notion of projection to arbitrary normed vector space 2 Dual space is essential for the concept of gradien 77 Which7 in turn7 leads to the variational analysis of Lagrange multipliers This chapter Will focus on the both the algebraic and the geometric properties of dual spaces 0 Linear Functional o Hanh Banach Theorem 0 Applications 0 Adjoints 57 58 Duality Linear Functional 0 Suppose X and Y are normed spaces Let A E 8X7Y denote the collection of all bounded linear operators from X to Y ltgt If a linear operator is continuous at a single point7 then it is continuous throughout the entire X ltgt A linear operator is bounded if and only if it is continuous 0 Associated to each A E 8X7 Y the number MN 3 SUMHAXH lX 6 MM 1 ltgt is a norm on the space 8X7 Y ltgt If Y is a Banach space7 so is 8X7 Y 0 Some triVial examples of linear functionals ltgt On C3907 l7 fx is a bounded linear functional What is ltgt On 2017 fx f01yifxifdf7 Where y E 207 1 is xed7 is a bounded linear functional ltgt The space of nitely nonzero sequences With gt0 M62 21H gig l l is a Banach space The function x 2 Ice 5k0 is an unbounded functional Linear Functional 59 o The Banach space 8X7lF is called the dual space of X and is denoted by X ltgt Show that every Cauchy sequence in X converges and7 hence7 X is a Banach space ltgt For the symmetry or duality that exists between X and X7 elements in X are often denoted by x The action of x on any element 2 E X is denoted by Xz z7 Xgt ltgt The symmetric notation ltzxgt is meant to suggest that the bounded linear func tional in a Banach space plays a similar role as the inner product in a Hilbert space 60 Duality Basie Dual Spaces o The dual of R ltgt Assume that the 2 norrn is used ltgt Any linear functional A has a unique vector representation 7 Via D D If x 221th then Ax 221 mi ltX77Igt ltgt By Cauchy Schwarz inequality7 WXN X777gt S HXHHUH D HAH HUH ltgt HWY R With the same 2 norrn ltgt What Will it be if other norms are used Linear Functional 61 o The dual of p7 1 1 lt oo ltgt Ep x Q fill K21 lt 00 is a normed vector space With 1 1pr 5 21 ltgt The Holder Inequality lf 1 S p7q S 00 are such that 1p 1q 17 then given any x 6 Ep and y 7551 6 117 it is true that Zl ml HprHqu 2 1 ltgt Any bounder linear functional A on Ep can be uniquely represented Via D Ae 77 D If x 21 217 then Ax mi by continuity of A ltgt Need to show that 77 21 6 11 by the fact that A bounded D Show that HAH 119th ltgt EPY 11 With the q norrn ltgt Note that Ely 007 but EGOY y 1 Why 62 Duality o The dual of plm b ltgt There is aone to one correspondence between bounded linear functionals A E plm b and elements y E qla7 b such that b Ax xtytdt and HM llYllq D How to prove that every bounded linear functional is representable in the above inner product form D Weierstrass Approximation Theorem The space of polynomials is dense in Chub Linear Functional 63 o The dual of CD ltgt The space CO x Q 2921 hmH00 n 0 is a normed vector space With norm HXH mgx m o lCcoC w ltgt 03 E1 in the sense that 0 AX 26 21 for some y 7721521 6 1 ltgt Let c X Q 2921 hmH00 n lt 00 With maxi Characterize the dual space 0 Duality o The dual of a general Hilbert space ltgt Riesz Representation Theorem Every bounded linear functional A on a Hilbert space H has a unique representation y E H such that AX X W and HM HYH ltgt If H is a Hilbert space7 then H H HahnBan ach Theorem I 65 HahnBanach Theorem I The Hahn Banach Theorem is one of the most critical result for optimization in a normed space The Hahn Banach Theorem can be stated in several equivalent ways each of Which has its own particular advantages and applications Two fundamental versions of the theorem7 the extension form and the geometric form7 Will be discussed in this note The extension form serves as an appropriate generalization of the projection theorem from the Hilbert space to the normed vector space The geometric form7 together With the notion of hyperplanes7 serves to separate a point and a disjoint convex subset in the space Duality Extension Form o Hanh Banach Extension Theorem Let V be a normed separable vector space over R ltgt Assume that D There exists a functional p V a R px Y S MK PY7 Max 04pX7 for all X7y E V and 04 Z 0 D Suppose that f is a real valued linear functional on a subspace S and fs S ps for all s E S ltgt Then there exists a linear functional F V a R such that Fx 3 px for all X E V and Fs fs for all s E S 0 Shall assume that V is separable7 that is7 V has a countable dense set ltgt The Hanh Banach theorem is true in arbitrary normed space Where the proof is done by using Zorn7s lemma HahnBanach Theorem I 67 0 Assume y S ltgt Consider the subspace spanS7y ltgt Note that for arbitrary 51752 6 S7 f51 f52 S M51 Y M52 Y Hence7 there exist a constant c such that sup ms 7 plts 7 y s c g2 ms y 7 fs SSS ltgt Extend f by de ning 9s Gay fS 049M Where 9y 07 as is determined from above 0 Claim that gs dy S ps dy for all or 6 1R ltgt If on gt 07 then glts My 7 a c7 3 s a mg m 7 g ma 7 plts ow ltgt Ifoalt07 then gltsaygt 7 7a lt7c 10 s 7a mi 7 y 7 f 68 Duality 0 Let x17x27 be a countable dense of V ltgt Select a subset of vectors y17y27 7 one at a tirne7 Which is mutually independent and independent of S7 in the way described above ltgt Extend f to subspaces span spanspanS7 y17y27 7 one at a tirne7 as described above ltgt The space spanS7y1y27 is dense in V on Which the extension 9 is de ned 0 The nal extension F is de ned by continuity Hahn Ban ach Theorem I 69 o Corollaries ltgt If f is a bounded linear functional on a subspace S of a real valued normed vector space V7 the there exists a bounded linear functional F on V Which is the extension off and WM Hfll ltgt Let x E V Then there is a nontrivial x E V such that xix HXH and WM 1 D Assume x a 0 Consider the bounded linear functional ax allxll on the subspace spanx gt m 1 D There exists an extension F on V D Show that the converse of the about statement is not true Recall that E 00 If x fil de ne x 0 e e 21 f is a bounded linear functinal lndeed7 f lt gt 07 a g HfH sup 1 fX lt HXH ltgt Let B be the closed unit ball of V Then for every x 6 V7 HXH ltX7Xgtlx E 3 70 Duality Applications 0 An Idea of Application Existence of a solution to a minimization problem ltgt Given a functional f on a subspace M of a normed space7 an arbitrary extension of f to the entire space in general would be bad ie7 the resulting extension might be unbounded or have larger norm than ltgt Which extension Will give the minimum norm and What minimum norm can be attained ltgt The Hahn Banach theorem guarantees the existence of a minimum norm extension and prescribes the norm of the best extension 0 The second dual space 0 Orthogonality in Banach space 0 Extension of the projection theorem 0 Duality principles HahnBanach Theorem I 71 The Dual of Ca b o Cab NBVa7b That is7 f is a bounded linear functional on Chub if and only there is a function of bounded variation 1 on 17 such that b m animus In this case7 T v ltgt This has been a major application of the Hanh Banach theorern ltgt De ne B 17 a Rlx is bounded on 17 bl and HrHB supaStSb ltgt C39a7 b C B ltgt By the Hahn Banach theorern7 an extension F of f from Chub to B exists and WM Hfll 72 ltgt Try to understand how F should look like D For any 3 E 17b7 de ne 17 ifagtgs7 Us l 0 1f5ltt b7 and ua E 0 Obviously7 us 6 B D De ne v3 D Claim that v E BVlt17 b lndeed7 T S 2 WE MEAN ZltSgnvti 0t 71vt2 00524 239 1 3H Duality Zltsgnvt 7 vt 71Fua 7 Fuai s H F ltZSg vti 0t 71uti WM 2391 S HFHH Zltsgnvt vt 71ua an Hfll HahnBan ach Theorem I 73 D Given any r E Ch7 b7 consider the function 2a Zzltt 71gtltuw 2391 D Note that the di erence H2 7 56HB mfxtifflg ti Wm 7 WM goes to zero as the partition is made ner D By continuity7 D Observe that n b Zt 1vt 7 vt 1 tdvt 21 1 D It is clear that S Hence7 T v ltgt The bounded variation 1 corresponding to f is not unique D How could the functional f 12 be represented in terms a bounded variation v05 ltgt De ne NBVlt17 b v E BVabHva 07 v is right continuous and NBVlt17 b is one to one D The corresponding between Ca7b 74 Duality Second Dual Space 0 The function fx With Hfll S HXH ltxxgt Where x E V is xed is bounded linear functional on V ltgt By the Hanh Banach theorern there is one functional x such that Hx l 1 and X7Xgt HXH ltgt Hfll HXH ltgt Depending upon Whether x or x is xed both V and V de ne bounded functionals on each other 0 The dual space VW of V is called the second dual of V o The mapping Q5 V a VW via ltX7 Xgt ltX7xgt is called the natural mapping of V into V ltgt Note that We denote Q5 7 ltgt The mapping Q5 is not necessarily onto ltgt lf Q5 is onto we say that the space V is re exive and denote V V D p if1ltpltoo D 1 and L1 is not re exive D Any Hilbert space is re ective HahnBan ach Theorem I 75 Orthogonality in Banach Space o The symmetric operator x7xgt in a Banach space plays the role of inner product in a Hilbert space ltgt Cauchy Schwarz Inequality x7xgt S o A vector x is said to be aligned With a vector x if and only if ltxxgt o A vector x is said to be orthogonal to a vector x if and only if X7 Xgt 0 o Orthogonal complement ltgt Given S 6 V7 the orthogonal complement SL of S is de ned to be SL x E Vlltxxgt 07 for every x E S ltgt Given U E V the orthogonal complement LU of U is de ned to be LU X E Vlltxxgt 07 for every x E U D Think about U as a collection of normal vectors D Think about LU as the intersection of several not necessarily nite hyper planes 76 Duality o If M is a closed subspace of a normed space7 then LMi M ltgt It is clear that M C LML ltgt Prove the other direction by contradiction D Suppose x M De ne linear functional ax m or on the space spanned by x M D f is bounded since M sup lfltoltxm fxm 1 sup lt oo moment Hoax mH meM Hx mH mme Hx mH Why is it that the inf cannot be zero D By the Hanh Banach theorern7 f can be extended to x E V D Because ltmxgt 0 for all m 6 M7 x 6 ML D By construction7 ltxxgt 1 So7 x LML HahnBan ach Theorem I 77 Characterizing Alignment in CM b 0 Corresponding to x E Ca b recall that ltgt The functional must be of the form ltxxgt XtdVt for some V E NBV ltgt lndeed V8 FMS Where F is the extension of x and us is a collection of step functions 0 Recall also that for a xed x E V a functional x E V is aligned With x if and only if 7 oltt1ltlttn b X7Xgt XtdVt llxllllxll HXHOOM sup bZlWi WHN Let P t E laiblllXW HXHool ltgt P may be nite or in nite but is always nonempty o Prove the following facts x is aligned With x if and only if ltgt V is constant outside P ltgt V is nondecreasing if xt gt 0 ltgt V is nonincreasing if xt lt 0 ltgt If P is nite then an aligned functional must consists of a nite number of step discontinuities 78 Duality Minimum Norm Problems o The minimum norm problems in Hilbert space can be extended into Banach space With the exceptions that ltgt The solution in a Banach space is not necessarily unique D Give an example of non uniqueness ltgt The orthogonality condition should be modi ed in the sense of dual space ltgt The system for determining the optimizing vector in a Banach space generally is nonlinear c There are remarkable analogues in the theory for minimum norm problem between Hilbert space and Banach space Minimum Norm Problems 79 Extension of Projection Theorem 0 Given x in a real normed space X and a subspace M7 then 7 7 4lt d7 334w mH ltx7x gt max llxdlsls eMi ltgt What is the meaning of the characterization on the right if X is a Hilbert space ltgt Note that there is a di erence in the meaning of inf and min 0 By the de nition of inf7 for any 6 gt 07 there exists InE E M such that Hxi mill 3 16 ltgt For any x E ML7 Hle S 17 it is true that ltxixgt ltx 7 mm HxlHlx 7 mew d e ltgt It is thus proved that x7xgt S d It only remains to show that X7 X3gt d for some X3 D Note that we are going to prove that the max is attained at some functional 80 Duality ltgt De ne linear functional ax m ad on the space spanned by x M D f is bounded since f dx m d M sup l m 1 mEM H04Xmll H1me HX3H ltgt By the Hahn Banach theorem there exists an extension x3 of f With 1 ltgt Because ltmx3gt 0 for all m E M x3 6 ML ltgt By construction What construction7 ltxx3gt d 0 Note that the minimum distance d is achieved by x3 6 ML o If the in mum on the rst equality holds for some m0 6 M then x3 is alligned With X 7 m0 ltgt lf HxirnOH d for some m0 6 M let x3 6 ML be the functionalsatisfying 1 and ltxx3gt d ltgt Then X 7 m07X3gt d HXSH MK 7 moll Minimum Norm Problems 81 Duality Principle o The previous result states the equivalence of two optimization problems the minimization in X as the primal problem and the maximization in X as the dual problem 0 A vector m0 6 M existence satis es Hx 7 mOH S Hx 7 for all m E M if and only if there exists a nonzero x 6 ML aligned With x 7 m0 ltgt The only if 7 part is already proved ltgt Suppose that x 6 ML aligned With x 7 m0 Then Hximoll Kimmx l X7Xgt ltXm7Xgt S Hximll Another View Duality 0 Given x 6 Vi then min Hx 7 mH sup ltX7X WSW xeMHxH 1 ltgt For any m E ML7 Hx 7 mH sup x7 7 In 2 sup x7 7 In Hst1 XEM Hstl ltgt Only need to show equality holds for some 1113 6 ML gt39 sup ltX7X KEMliXHSI D Consider the restriction of x to M With norm supxeM HxHS xxW D Let y be the Hahn Banach extension of the restricted X D Let m3 x 7y 9 Then 111336 ML and H8 mSH HWH SUPxeMHngiltX7Xgt o The minimum of the left is achieved by some 1113 6 ML 0 If the supremum on the right is achieved by some x0 6 M7 then x 7 m3 is aligned With X0 ltgt Obviously HXOH 1 ltgt MK 7 HIGH ltXoixgt ltXoix 7 m3gt Applications 83 Applications In all applications of the duality theory7 0 Use the alignment properties of the space and its dual to characterize optimum solutions 0 Guarantee the existence of a solution by formulating minimum norm problems in a dual space 0 Examine to see if the dual problem is easier than the primal problem Duality Chebyshev Approximation Given f E C39lmb7 want to nd a polynomial p of degree less than or equal to n that best approximates f in the the sense of the sup norm over 17 b Let M be the space of all polynomials of degree less than or equal to n ltgt M is a subspace of C39a7 b of dimension n 1 The in mum of Hf 7 pHOO is achievable by some pg 6 M since M is closed Want to characterize p0 This is the essence of the ChebysheV theorem ltgt The set P t 6 a7 bHft 7le Hf7pHOO contains at least n2 points Why By the previous theory7 f 7 p0 must be aligned With some element in ML C Ola7 b NBVa b ltgt Assume P contains m lt 72 2 points a 3 751 lt lt tm S b ltgt If V E NETa7 b is aligned With f 7 p07 then V is a piecewise continuous function With jump discontinuities only at these ts ltgt Let tk be a point of jump discontinuity of V D The polynomial qt Hi 7 75k 6 M7 but ltq7vgt a 0 and hence V ML ltgt P must contain at least 72 2 points Applications 85 Characterizing Constrained Equalities 0 Given y17 7yn 6 X7 consider the problem Minimize llxll Subject to lty 7xgt Ci 1172 o The minimum can be achieved ltgt Let M spany17 Wyn Then d min llxll min H 7 ml H7 yixci2391n mquot6Mi for any 2 satisfying the equality constraints Why 0 By the duality principle7 d ltx2gt min H 7 mll sup WeMi xeMHxH 1 0 Write x Ya Where Y 5717 7yn and a E R Then d llxll max ltYa gt max cTa n HYaHSl min ixquot ci 2391 Ya lt1 y y y y y 7 o The optimal solution x3 must be aligned With Ya 86 Duality Control Problem 0 Want to select the eld current 11757 t E 0717 so as to drive a motor 5 19 ut from 60 0 to 61 1 and 0 While maintaining that is minimized 0 Cast the problem in X 107 1 With X 00l071 ltgt Seek u E X With minimum norm 0 By the variation of constants formula7 a general solution is t 615 04 56 17 es tusds 0 0 Boundary conditions imply the equality constraints 1 et 1utdt 07 0 1 17 et 1utdt 1 0 Note that these functionals are not inner products Applications 87 o By the previous theory7 min max 12 yiuci2 12 lla1y1a2y2H1Sq o The control problem now is reduced to nding constants a1 and a2 satisfying 1 lt11 7 a2et 1 agldt S 1 0 o The optimal solution u E 00m 1 should be aligned With 11 7 a2et 1 a2 6 1071 ltgt Note that 11 7 a2et 1 12 can change sign at most once ltgt The alignment condition implies that u must have values illullw and can change sign at most once This is the so called bang bang control 88 Duality Rocket Problem 0 Want to select a thrust program ut that propel a rocket vertically With altitude t governed by 05 7105 i 17 from 0 0 to T 1 With minimum fuel expenditure 0 With given uf7 the altitude is given by T T2 MT Titutdt7 0 2 o The nal time T is not speci ed7 the cost function for fuel is a function of T Want to T Minimize lufldf7 0 T T2 Subject to T itutdt1 0 ltgt 107T is not the dual of any normed vector space ltgt Embed 10T in NBV01 and associate control u With the derivative of v E NBV01 ltgt The objective function becomes T Minimize ldvtlT0TvHvH 0 Applications 89 o By the previous theory7 1 T72 min HvH 1 max 1 111 6 HTtallw31 o The optimal value is given by a at Which the optimal fuel is given by T21 1 mm M lt 2 gtT o The thrust program u must be such that its derivative 1 is aligned With T 7 ta ltgt The alignment condition implies that 1 can only vary at t 0 and hence is a step function Why ltgt u is a delta function at t 0 an impulse In What sense 0 The best nal time is obtained by minimizing the fuel expenditure function With respect to T ltgtT ltgt The derivative of the optimal thrust program is given by U 0 t0 39U V6 0lttgvi 90 Duality HahnBanach Theorem II o The notion of linear functionals in the dual space can be interpreted as that of hyperplanes in the primal space 0 The notion of extension can be interpreted as that of separation HahnBanach Theorem H 91 Hyperplanes o A hyperplane H in a linear vector space X is the largest proper linear variety in X ltgt A hyperplane H is a linear variety such that H a X and if V is any linear variety containing H then either V X or V H o If H is a hyperplane then there is a linear functional f and a constant c such that H XE lex c ltgt H x0 M for some linear subspace M ltgt lf x0 M then X spanx0 De ne fdx0 m 04 if x dxo In With m E M ltgt If H M there exists x1 M and X spanx1 De ne fdx1 m 04 ifxdxlmwithmEM ltgt H is called the c level hyperplane determined by f 0 Given any nonzero linear functional f the set x E lex c is a hyperplane in X ltgt Let M x E lex 0 and x0 be such that fx0 1 ltgt For any X E X x7fxx0 E M D M is a maximal proper subspace D X spanx0 ltgt Let x1 be such that fx1 0 Then fx c if and only if x 7 x1 6 M 92 Duality o If H is a hyperplane not containing the origin7 then there exists a unique linear functional fsuch that H x E lex1 ltgt What is the meaning of this unique linear functional in R 0 Let f be a nonzero linear functional on a normed space X Then the c level hyperplane H of f is closed if and only if f is continuous bounded ltgt There is a correspondence between the closed hyperplanes and elements in the dual space X Hahn Banach Theorem H 93 Separation of Convex Sets 0 Given a convex set K containing an interior point and a linear variety V containing no interior points of K7 there exists a closed hyperplane containing V but containing no interior point of K ltgt There exists an element x E X and a constant c such that ltVxgt c for all V E V and ltkxgt lt c for all k E K ltgt Consider the case that K is the unit sphere Why is the above statement obvious 0 Given a convex set K With the origin as an interior point7 de ne the Minkowski functional p of K on X by x px infrl 6 K77 gt 0 r ltgt px is the factor by Which K must be expanded so as to include x ltgt Prove that px satis es the sublinear functional conditions required by the Hahn Banach theorem gt 0 S px lt 00 D pdx dpx for or gt 0 D PltX1 X2 S PltX1 PX2 D p is continuous D K lex S 1 94 Duality 0 Assume 0 is an interior point of K Let M spanV ltgt V is a hyperplane in M containing no origin ltgt There is a linear functional f on M such that V x E lex 1 Why ltgt Since V contains no interior point of K7 fx 1 S Px for all x E V ltgt Note that fx 3 px for all x E M because D ax 04 po x for x E V anda gt0 D ax 04 S 0 po x for or lt0 ltgt By the Hahn Banach theorern7 there is an extension F of f from M to X With Fx 3 px 0 De ne H x E X Fx 1 ltgt Fx 3 px Hence F is continuous ltgt For all interior point x of K7 Fx lt 1 o If K is a closed convex set in a normed space7 then K is the intersection of all closed half spaces containing K ltgt Associating closed hyperplanes with elements in X a closed convex set in X may be regarded as a collection of elements in X HahnBanach Theorem H 95 Minimum Distance Problems o The minimum distance from a point to a convex set K is equal to the maximum of the distances from the point to hyperplanes separating the point and K o The theory can be included in more general machinery to be introduced later 96 Duality Adjoints o The constraints imposed in many optimization problems by di erential equations7 matrix equations7 and so on can be described by linear operators 0 The solution of these problems almost invariably calls for the notion of an associated operator 7 the adjoints o Adjoints provide a convenient mechanism for describing the orthogonality and duality relations Adjoints 97 Basic Properties 0 Let BX7Y be the collection of all continuous linear operators from the normed space X to the normed space Y ltgt Recall that if Y is complete7 then BX7 Y is a Banach space With the induced norrn HAXHI HAM sup xso M 0 Given A E BXY7 the adjoint operator A Y a X is de ned by the equation X7AYgt AX7Ygt ltgt Ay is a linear functional on X ltgt Since lltAX7Ygtl S HWHHAXH S HWHHAHHXW HAWH S HAHHYW 30 MW S HAH The functional Ay is an element in X ltgt lndeed HAW Why D For any nonzero x0 6 X7 there exists yE E Y HyOH 17 such that ltAx07y3gt HAXoH D HAXoH X07AYSgt S HAWSHHXoH S llAllllXoll 30 MM S HAW s 0 0 0 0 Thus 1 Ay Ks7tysds 0 ltgt IfX C017 Y R and Am 0517 052 7xtn For any given y y17y27 7yn 6 RH M71147 29MB 144119 2 1 Note that v Ay E NET071 and should be written as 1 ltzAygt xtdvt 0 D 1 is constant except at the point ti Where it has a jump yi Adjoints 99 Fredholm Alternative Theorem 0 Let X and Y be normed space and A E BX7 Y Then ltgt AX7Ygt X7AYgt ltgt y E 7214L gt Ay 0 ltgt y E NA gt y T AX for all x 0 Let X and Y be normed space and A E BX7 Y Then RU C MAW If RA is closed7 then RU MADL ltgt The Hahn Banach theorem is needed in the proof 100 Duality Normal Equations 0 Given two Hilbert spaces X and Y and A E BX7Y7 then for each given y E Y the vector x E X minimizes My 7 AxH if and only if AAx Ay ltgt The existence of a solution x is not guarantee since RA is not necessarily closed ltgt The solution is not expected to be unique ltgt How is the above result related to the projection theorem Where is the idea of orthogonality 0 Suppose RA C Y is closed and y E The vector x of minimum norm satisfying Ax y is given by x Az Where z is any solution of AAZ y Adjoints 101 An Example 0 Consider a system governed by the di erential equations Fxt but ltgt It is desired to drive x0 0 to XT x1 via a suitable scalar control ut While the energy T u2tdt 0 ltgt By the variation of constant formula7 is kept at minimum T XT 6FT tgtbutdt 0 0 De ne the linear operator A 207 T a R by T Aw eFlT tgtbutdt 0 ltgt The problem is equivalent to that of minimizing the norm of u While satisfying Au X1 102 Duality 0 Since R14 is nite dimensional7 it is closed ltgt The optimal solution is u 14z Where 1414z X1 ltgt It remains to calculate the operator 14 and 1414 o For any u E 20T and y 6 NZ T T lty714ugt yT 6FT tgtbutdt yTeFT tgtbutdt lt14y7ugt 0 0 ltgt 14y bTeFTT tgty ltgt 1111 OT eFT tgtbbTeFTT tgtdt 6 Rm 0 The optimal control is given by u 141414 1X1 Chapter 5 Optimization of Functionals There are optimization problem that cannot be formulated as minimum norm problems This chapter discusses the theory and geometry of the more general problems 1 The concepts of di rerentials7 gradients7 and so on can be generalized to normed spaces 2 Variational theory of optimization is much in parallel to the familiar theory in nite dimensions Topics to be discussed include o Di erentials o Extrema o Euler Lagrange Equations 133 134 Optimization Differentials There are several ways to introduce the notion of derivative in normed spaces 0 Gateaux derivative 0 F rechet derivatie Di erentials 135 3auteaux brentu Let T D 6 Y be a mapping Where D C X7 X is a vector space7 and Y is a normed space Given x E D and h 6 X7 ltgt The limit T h T 5Tb h hm M7 0H0 a if exists7 is called the Gateaux di erential of T at x With increment h D If 6TXh exists for each h 6 X7 the mapping T is said to be Gateaux di er entiable at x The limit is takin in the normed space Y The Gauteaux di erential is analogous to the directional derivative in that if f R R is continuously di cerentiable7 then m N W 6fx h Z a i1 For each xed x 6 D7 6Tx X 6 Y is a linear map in h 136 Optimization Fr ehet Differential 0 Let T D 6 Y be a mapping Where D C X is an open domain and XY are normed spaces Given x E D if for each h E X the Gauteaux di erential 6Tx h exists is continuous and satis es hm HTcheTc76TxhH 0 WHO th then T is said to be F rechet di erentiable at x ltgt At a xed point x E D the bounded linear operator Ax E BX Y such that Axh 6TX h is called the Frechet derivative of T at x and is denoted as T X o The mapping from X to BXY via x gt gt T x is called the Fr chet derivative of T o If T is a functional then T x E X is called the gradient of T at x 0 Much of the theory of ordinary derivatives including the implicit function theorem and the Taylor series expansion can be generalized to Frechet derivatives How Digerentials 137 0 Some examples ltgt lff R a Rm7 then aflx 7 2 f X 7 aj Where the Jacobian matrix acts like the matrix representation of the linear operator Recall how the dual space is represented ltgt Suppose I C071 a R is de ned by Where g R X R 6 R and exists Then the action of I f on ht E C071 is given by 1 a t t 1 mos L 7 htdt 0 v D May we say that 89 f t 7if V10 a 7 Recall that the dual space of C071 is identi ed With NBV071 138 Optimization Conditions at Extrema 0 Using the norm to de ne a neighborhood N of a given point x0 in a normed space7 x0 is said to be a relative minimum of a functional f on a subset 9 if fx0 3 fx for all x E 9 N 0 Suppose the real valued functional f is Gauteaux di erentiable at x0 in a normed space A necessary condition for f to have extremum at x0 is that 6fX0 h0 for all h E X ltgt Simple consequence by the ordinary calculus7 but signi cant impact EulerLagrange Equations 139 EulerLagurange Equations The Euler Lagurange equation is o A direct result of di erential calculus applied to the settings of functions 0 The equation usually ends up With a di erential equation that needs to be solved further 140 Optimization Fixed end Problem c Find a function t over the interval 751752 that minimizes the integral functional m t 2 anagram Where f is continuous and has continuous partial derivatives With respect to m and i ltgt We must agree on the class Dt17t2 of functions Within Which we seek the optimal values 7 the so called admissible set What class of functions should be consid ered ltgt One version is to assume that 051 and 052 are xed D Given t admissible7 if t ht is also admissible7 then ht1 ht2 0 o The necessary condition for the extremum is that for all h7 t2 W h manila novaown dt t 1t d ltfzx7i7t 7 Ewan htdt f vitht if 0 t1 ltgt To use the integration by parts7 we have to assume that fi is continuous EulerLagrange Equations 141 o If 0405 and 575 are continuous in 7517752 and t2 ltatht 5mm dt 0 1 for every h E Dt17t2 With ht1 ht2 07 then B is di erentiable and 0405 in t ltgt De ne 775 ft1o 739d7397 then f2 mm who dt e W at wt t1 ltgt 7775 E c D Let c be the average value of 7775 over 7517752 D De ne C75 777 7 0 1739 as a special h E Dt1t2 D Observe that t2 2 t2 t2 W e c d7 W e c klttgtdt ntktdticiht211051 0 t1 t1 t1 ltgt Mt 775 c is di erentiable 0 At the extrernurn point7 t must satisfy the Euler Lagrange equation d favlt7i7tgt Efflt7i7t39 142 Optimization Examples o Assumptions ltgt That a retired professor has no income other than that obtained from his xed quantity of savings S Oh7 that is how the government treats us ltgt That his rate of enjoyment at a given time is Urt Where rt is his rate of expenditure Uhmmm7 life is more than just material things That the true sense of enjoyment is degraded in time as e tUTt Alas7 money cannot buy all the joy ltgt ltgt That the current capital t at time 75 generates an investment interest 04t So this is the only bright thing in this scenario That the man knows exactly that he Will live for a period of time 0T When he begins to Withdraw his savings Attention Do not think that you can make this prediction ltgt 0 Objective T Maximize ei tUTtdt 0 Subject to 0 S7 T 07 Whereas 04t 7 75 ltgt What is the lifetime plan of investment and expenditure that maximize the total enjoyment EulerLagrange Equations 143 0 Optimal solution t must satisfy 4 d 75 046 U 04t 7 6 U 04t 7 0 ltgt Equivalently7 EffNU 5 04U Tt7 U rt U r0e gtt ltgt Once U is speci ed7 t and hence rt can be completely Characterized from the boundary conditions 0 T 0 144 Optimization Equality Constrained Problems o Fixed end problems are a kind of constrained problem Since these kinds of constrained are explicitly described7 they can be embedded in the space of admissible solutions 0 For implicitly de ned constraints7 the theory of Lagrange multiplier is quite useful Minimize fx7 Subject to g x07 1177n ltgt Recall that there is a geometric meaning of the Lagrange multiplier in nite dimen sional space Such a concept needs to be generalized in normed vector space ltgt The Lagrange multiplier theory usually ends up With a new functional Whose sta tionary points can be found by the Euler Lagrange equation Equality Constrained Problems 145 Notion of Tangent in Normed Space 0 Assume ltgt That x0 is an extremum of the functional f subject to the functional constraints 9X07i17n ltgt That the linear functionals 91X07 7gMXO are linear independent 0 Then 69 x0h 07 239 17n 6fxoh 0 ltgt Note that the concept of tangent is built in the notion of Gateaux di erential of gi at x0 With arbitrary increment h 146 Optimization 0 Here is the proof ltgt There exist 72 linearly independent vectors y17 yn 6 X7 such that the matrix M 3 59 X0 Yjl is nonsingular ltgt Consider the system of equations from R X R a R de ned by 91X0 06h Z 5072 07 21 92X006hZB Y 07 2391 9nltX0 06h Z 5072 07 21 for variables 047 517 n ltgt With a little bit abuse of the notation7 the Jacobian 892 357 7 M a0 0 is nonsingular Equality Constrained Problems 147 ltgt The implicit function theorem in R kicks in D There exists a function o in the neighborhood of oz 0 such 0 9 X0 04h Z 0305 j1 9 X0 045X0 h 59 Xm 0305 0034 0H 0305 H 0 M m D But M m 0H Z w 5 H Z j0ltyjH 0a ltgt Along the one parameter curve x0 ah 21 5704yj7 the functional f assume the extremurn at X0 So d n xo 04h 25704Yja0 0 71 ltgt The above derivative is precisely 6fx0 h 0 148 Optimization Lagrange Multiplier 0 Let 917gn be linear independent linear functionals on a vector space X Let f be another linear functional on X such that for every 6 X satisfying 07 239 17 7727 we always have x 0 Show that there are constants A17 7 An such that f ZAigi 11 0 Assume that ltgt The point x0 is an extremum of the functional f subject to the constraints g x 07 239 17 7n ltgt The linear functionals 91x07 7ng0 are linear independent Then there exists constants A17 A such that 6fx0h ZAj gjx0 h 0 71 for every h E X Equality Constrained Problems 149 Isometric Problem c Find the curve With length and end points 717 0 and 17 0 so that it encloses maximum area between the curve and the m axis 0 Mathematical model 1 Maximize gd7 71 1 Subject to 11 y 2dx 7 71 114 111 0 o By the Lagrange multiplier7 6Jy 71 0 for every admissible h Where the functional J is de ned by 1 my y A 1y 2d 71 0 Apply the Euler Lagrange equation7 liAi y dz 1 M ltgt Show that the solution is the arc of a circle 0
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'