Vector Space Methods in System Optimization
Vector Space Methods in System Optimization MA 719
Popular in Course
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
Popular in Mathematics (M)
This 32 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 Kazufumi Ito in Fall. Since its upload, it has received 6 views. For similar materials see /class/223709/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 1 Preliminaries The purpose of this chapter is to provide some basic background information 0 Linear Space 0 Hilbert Space 0 Basic Principles 2 Preliminaries Linear Space The notion of linear space provides simple7 intuitive7 and geometric interpretations on many complex mathematical entities o A linear space is an algebraic entity Where every of its elements can be expressed alge braically as a linear combination of other elements ltgt The simplest linear space is a vector space ltgt A linear space can also be considered as a at geometric entity in the sense of a hyperplane in the ambient space o If a linear space is equipped With a notion of sizes7 called norm 7 of its elements7 then ltgt We may measure the distance between any two elements ltgt We may introduce the idea of convergence ltgt Whether the limit points belong to a linear space is quite a signi cant issue o If a linear space is equipped With a notion of inner product 7 then ltgt The inner product can be used to induce a norm ltgt The inner product can be used to determine Whether two elements in the linear space are perpendicular or not ltgt The notion of projection is critically important in applications Linear Space 3 Vector Space o A vector space V over a eld l is a set of elements called vectors together With two operations7 VgtltVaV viax7ygt gtXy7 FXV V viaor7xgt gtorx7 NH VV that satisfy the following properties xy yx xyzxyx There is a null vector 0 E V such that X 0 x for all X E V dxy dxdy or mx dx Bx amx oawx 0x071xx NQWHgtWNE o A nonempty subset S of a vector space V is called a subspace of V if every vector of the form 04x By E S Whenever X7y E S Preliminaries 0 Some examples ltgt The set 73 anrn a1x a0lan E R of all polynomials over R With degree less than or equal to n is a vector space ltgt The set 31017 b f 17 b a le is continuous over 17 b of continuously di erentiable functions is a vector space ltgt The set 7 T E anltij PiH17 where n 7r 6 R arbitrary of n dirnensional Toeplitz matrices is a vector space ltgt The set b rpw f 17 a Q lflpd lt 00 a of p integrable functions is a vector space ltgt The set 00 5 kZ1lk1 EO k 0 is a vector space Linear Space More De nitions o A set V is called a linear variety of a subspace M if VXOMx0mlmEM o A set C is said to be a cone with vertex at the origin if 06X 6 C7 Whenever x E C and 04 gt 0 ltgt The set of all nonnegative matrices is a cone ltgt The set of all nonnegative continuous functions is a convex cone 0 A vector x is said to be linearly independent of a set S is x cannot be written as a linear combination of vectors from S ltgt The vectors x17 7Xn are mutually linearly independent if and only if TL ZO Z XZ 0gtO 07 i17n 21 ltgt lf x17 7xn are linearly independent7 and 221 dixi 221 52X then 04 Bi for alli177n o A nite set X17 7xn of linearly independent vectors is said to be a basis of the space V if and only if V spanx1L7 7xn dixildi E lF 21 Preliminaries Convexity o A set K is said to be convex if oax1io y E K Whenever Xy E K and 0 S on S 1 ltgt The sum of two convex sets is convex ltgt The intersection of convex sets is convex 0 Given a set S the convex hull of S denoted by c0S is de ned to be the smallest convex set containing S ltgt Prove that c0S is the collection of all convex combinations from S ie c0S ooxnlxi E S 04 Z 0 Zoo 1 and n is arbitrary but nite 2 1 i1 ltgt What is the convex hull of all n dimensional orthogonal matrices ltgt What is the convex hull of all n dimensional doubly stochastic matrices Birkho ms theorem 0 A real valued function o V a R is said to be a convex function if gtx 1 MY 3 MW 1 My foreachxyEVand0 1 Linear Space Normeol Vector Space o A vector space V is said to be a normed space if there is a map H H i V n R such that 1 gt 0 ifxa 0 2 Hx Yll S for all x and y in V 3 HOrXH lOrlHXH for all x E V and or E F 0 Some examples ltgt Over R the function W 11 Hpr 2391 D Identify the unit balls of R under di erent vector norms is a norm7 ifp Z 1 Note that unit balls are necessarily convex D How does the notion of unit balls a ects approximations Preliminaries ltgt Over RM the function M HMHP sup X 0 Hpr is called an induced matrix norm D What is the geometric meaning of an induced matrix norm D What is the analog of the SVD if other norms are used in the variation formu lation Any usage D Why is the usual Frobenius norm of a matrix not an induced norm ltgt Over C39lla7b7 the function W s max lfltrvl gggblf WN 13sz is a norm Note that the maximum exists over the closed interval a7 ltgt De ne the total variation of a function f over a7 b by T50 3 SUP Z UM fgt1l azoltltznb 21 D If T50 lt 007 we say that f is of bounded variation D The set BVlavbl 3 f 3 lavbl RWU lt 00 is a normed vector space With the norm de ned by M fa Tim D Give an example of a continuous function Which is not of bounded variation Linear Space 9 Convergence and Completeness o A sequence of vector xn in a normed vector space V is said to converge to a vector X7 denoted by Xn a x if HxnixH a0 asnaoo ltgt If a sequence converges7 then its limit is unique 0 A sequence Kn in a normed vector space V is said to be a Cauchy sequence if to every 6 gt 07 there exists and integer N such that HXn 7 XmH lt 6 Whenever m7 n gt N ltgt Every convergent sequence is a Cauchy sequence ltgt A Cauchy sequence may not be convergent Give an example 0 A space V in Which every Cauchy sequence converges to a limit in V is said to be complete ltgt A complete normed vector space is called a Banach space 10 Preliminaries 0 Some examples ltgt The space Ca7b With the norm b M lfcldc is incomplete D The sequence 07 for0 il7 n fn 7zxig17 for7 7 1 for m 2 is Cauchy since Hf 7 me 7 l but its limit point is not continuous ltgt The same space C39a7 b With the norm M r agggbl v the space plmb With p Z 17 and any nite dimensional normed vector space are complete ltgt Any normed vector space V is isometrically isomorphic to a dense subset of a Banach space V D X and Y are isomorphic if there exist a one to one mapping T of X onto Y such that T061X1 062X2 061TX1 062TX2 D An isomorphism T is isometric if HTXH HXH Linear Space 11 Banach Space o A mapping A from a vector V into a vector space W is said to be a linear operator if Aoltx BY 04AX 6AM for all X7y E V and 0475 E F o A linear operator A is said to be bounded if A sup XH lt00 X evx7e0 llxll ltgt The above calculation can be simpli ed to supHxH1 ltgt A bounded linear operator is uniformly continuous ltgt If a linear operator is continuous at one point7 it is bounded ltgt An example Show that the di erential operator DU f is linear and unbounded from 0117 b to Ca7 b under some norms 0 Given a normed vector space X and a Banach space Y7 the space 8X7 Y A X 6 Yl A is linear and bounded is itself a Banach space With as the norm Preliminaries o The dual space V of a normed vector space V is de ned to be V f V 6 Flf is linear and continuous ltgt The dual space V of any normed vector space is automatically a Banach space D Characterize the unit ball in V o Hahn Banach Theorem This theorem plays a fundamental role in optimization theory ltgt Let p V a R be a function satisfying pm y S px py and pdx dpx ltgt Suppose that f is a real valued linear functional on a subspace S and that 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 D What is the geometric meaning of the Hahn Banach theorem in R Pay attention to the minimum norm extension Hilbert Space 13 Hilbert Space Hilbert spaces7 equipped With their inner products7 possess a wealth of geometric properties that generalize all of our understanding about the classical Euclidean space R o A concept of orthogonality analogous to the dot product77 in R3 can be developed based on the belief of inner product We use the algebraic expression of inner product to probe the inner structure of an abstract space Orthogonality naturally leads to the notion of projection7 Which then leads to the idea of minimum distance Though the minimum norm in a general normed vector space has a similar idea7 the shortest distance by projection has a particularly appealing geometric intuition 14 Preliminaries Inner Product 0 Given a vector space X over a eld l either C or lR7 we say that it is equipped With an inner product 3 X X X a F if the inner product satis es the following axioms 1 KM lty7xgt 2 ltxy7zgt ltxzgt ltyzgt 3 orx7ygt orltxygt 4 ltXXgt Z 0 and ltX7Xgt 0 if and only if x 0 ltgt The quantity HXH i X7Xgt naturally de nes a vector norm on X ltgt Two vectors x and y are said to be orthogonal7 denoted by x l y7 if ltxygt 0 Hilbert Space 15 0 Some basic facts ltgt Cauchy Schwarz Inequality For all X7 y in an inner product space7 KM S llxllllYll Equality holds if and only if x dy or y 0 ltgt Parallelogram Law With the induced inner product norrn7 UK YHZ HX YHZ 2Hle 2HYH2 ltgt Continuity Suppose that xn a x and yn a y Then xn7 yngt a X7 ygt ltgt Note that these geometric properties follow from the algebraic de nition of inner product 0 A complete inner product space is called a Hilbert space 16 Preliminaries Orthogonal Complements 0 Given any subset S in an inner product space X7 the set SL y E le l x for every x E S is called the orthogonal complement of S ltgt SL is a closed subspace ltgt S C SHL ltgt StL is the smallest closed subspace containing S c We say that X is the direct sum of two subspaces M and N7 denoted by M M QBN7 if every x E X has a unique representation of the form x m n Where In E M and n E N ltgt The Classical Projection Theorem Let M be a closed subspace of a Hilbert space H Corresponding to every x 6 H7 D There exists a unique m0 6 M such that MK 7 moH S MK 7 for all m E M D A necessary and su icient condition that m0 be the unique best approximation ofxinMis thatximo lM ltgt If M is a closed linear subspace of a Hilbert space X7 then X M 63 ML 0 Given a vector x0 6 X and a closed subspace M7 the unique vector m0 6 M such that x0 7 m0 6 ML is called the orthogonal projection of XO onto M Hilbert Space Gram Schmidt Orthogalization Process c Any given sequence nite or in nite Kn of linearly independent vectors in an inner product space X can be orthogonalized in the following sense ltgt There exists an orthonormal sequence Zn in X such that for each nite positive integer 7 spanx1L7 7X2 spanzL7 7ze ltgt lndeed7 the sequence Zn can be generated via the Gram Schmidt process X1 Z1 7 W n71 Wn Km 7 ZltX 7Z gtZ 7 72 gt17 1 Zn 7 72 gt 1 lww ltgt Show that in nite dimensional space7 the Gram Schmidt process is equivalent to that any full column rank matrix A 6 RM can be decomposed as AQR Where Q E Rwy QTQ m7 and R E Rmxm R is upper triangular 18 Preliminaries 0 An example Applying the Gram Schmidt procedure With respect to a given inner product in the space CW17 b on the sequence of polynomials 17 1727 ltgt Six popular orthogonal polynomial families D Gegenbuer 71717 w 1 7 2 a any irrational number of rationalZ 5 D Hermite 7007007 w 2 D Laguerre 07 oo7 w 6 a any irrational or rational Z 71 D Legendre Needed in Gaussian quadrature D Jacobi 7117 w 17 1 Mb 1 any irrational or ration Z 71 D ChebysheV 7117w 17 2i ltgt Show that the resulting orthonormal polynomials satisfy a recursive relation ship of the form anm bn2n1 7 Cn2n727 n 27 37 Where the coe icients am bmcn can be explicitly determined ltgt Show that the zeros of the orthonormal polynomials are real7 simple7 and located in the interior of 17 Hilbert Space 19 Best Approximation One of the most fundamental optimization question is as follows 0 Let x0 represent a target vector in a Hilbert space X ltgt The target vector could mean a true solution that is hard to get in the abstract space X 0 Let M denote a subspace of X ltgt Consider M as the set of all computable7 constructible7 or reachable by some rea sonable means vectors in X ltgt M shall be called a feasible set 0 Want to solve the optimization problem g gllxoimll 20 Preliminaries Projection Theorem o A necessary and su icient condition that m0 6 M solves the above optimization problem is that X0 7 mg L ltgt The minimizer m0 is unique7 if it exists ltgt The existence is guaranteed only if M is Closed 0 How to nd this minimizer ltgt Assume that M is of nite dimension and has a basis M spany1 7yn Write TL mo Z 0609 21 Then 0417 704 satisfy the normal equation 71 X07 Zaiyhy 07 j17n 21 Hilbert Space 21 ltgt ln matrix form7 the linear system can be written as Y17Y1gt 5 27 Y1gt ltYn7y1gt 061 X07Y1gt Y17Y2gt 062 X07 Y2gt ltY17IYngt I Yngt ltX07IYTLgt D If the basis yL7 7yn are orthonormal7 then trivially 062 X07Y gt ltgt What can be done if M is not of nite dimension ltgt If M is of codimension n7 ie7 if the orthogonal complement of M has dimension n then a dual approximation problem can be formulated 22 Preliminaries Fourier Series 0 Let Zn be an orthonormal sequence in a Hilbert space X ltgt The convergence of an in nite series in X can be identi ed as a square summable sequence in R in the following way Z zi a x if and only if 2 l lz lt oo 21 2 1 ltgt ltX7 Zigt o Bessel7s Inequality Given x 6 X7 then 0 ZlltX7Z gtl2 S M2 2 1 ltgt The convergent series 0 flquot 3 ZltX7Z gtZ 2 1 guaranteed by Bessle7s inequality is called the Fourier series of x in X D fx belongs to the closure of spanzn D x 7 fx l spanzn and hence its closure D When Will an orthonormal sequence Zn generate a Hilbert space Hilbert Space 23 0 An orthonormal sequence Zn in a Hilbert space X is said to be complete if the closure of spanzn is X itself ltgt An orthonormal sequence Zn in a Hilbert space is complete if and only if the only vector orthogonal to each Zn is the zero vector ltgt The subspace of polynomials is dense in 2171 ltgt The Legendre polynomials7 ie7 the orthonormal sequence 272 191 d 2 27172 dm 1 7 2 Zn is a complete in 27171 24 Preliminaries Minimum Norm Problems The minimization problem described in the proceeding section can appear in di erent forms7 including o The dual approximation problem 0 The minimum energy control problem 0 The shortest distance to a convex set Hilbert Space 25 Dual Problem of Best Approximation 0 Given y1 7yn in a Hilbert space7 de ne the feasible set F X E HlltX7y gt Ci Want to solve the minimum norm problem min XEF 0 De ne M spany17 7yn Then F c Mi for some suitable c E F ltgt Analogous to the notion that a general solution is the sum of a particular solution c and a general homogeneous solution ML ltgt We say that F is a linear variety With codimension n D Note that F or ML itself could be of in nite dimension 26 Preliminaries 0 Using the Projection Theorem7 we know that the solution exists and is unique Indeed7 the optimal solution x x 6 MA M O X 21 ltgt The coe icients Bi are determined from the linear system Y17Y1gt 5 27 Y1gt ym Y1gt 51 Ci Y17Y2i 52 02 lty1739yngt ltyn yngt 5 a ltgt What is the geometric meaning of the dual problem Hilbert Space 27 A Control Problem 0 Consider the problem of minimizing subject to ut7 0 given ltgt The objective function represents a comprise between a desire to have t small While simultaneously conserving control energy 0 Equip the product space H 207T gtlt 207T With the inner product T 17u1727u2gt l1t2t u1tu2tldt 0 0 Let V be the linear variety t v m e Hun 0 u7 d739 0 o The control problem is equivalent to nding the element in V With minimal norm ltgt It can be shown that V is closed in H ltgt The Projection Theorem is hence applicable The solution exists and is unique ltgt HOW to do the computation 28 Preliminaries Minimum Distance to a Convex Set o The concept of linear varieties can be generalized to convex sets 0 Given a vector x and a closed convex subset K in a Hilbert space H7 ltgt There is a unique kg 6 K such that HX koH S HX W for all k E K ltgt A necessary and su icient condition for k0 being the global minimizer is that xikmkikd S 0 for allkEK Hilbert Space 29 Linear Complementary Problem 0 Given y1 7yn C H7 and X 6 H7 want to minimize TL llX Zleb 2 1 subject to 04 Z 0 for all 239 o The feasible set forms a cone ltgt There exists a unique solution X oriyi 0 Try to Characterize the coe icients 04 ltgt Take k X yj7 then X 7 X7yjgt S 0 ltgt Take k X 7 O jyj7 then X 7 X7 7Oijyjgt S 0 ltgt Together7 X 7 X7y gt S 07 With equality if 04 gt 0 o Rewrite in matrix form7 ltgt Y17Y1gt 5 27 Y1gt ym Y1gt 061 X7 Y1gt Y17Y2gt 062 7 X7 Y2gt ltY17IYngt ltYmIYTLgt ltX7IYTLgt ltgt 2212 0 for alli ltgt 04223 0 for all 239 0 Check out CPnet for more discussions on complementary problems Preliminaries Hilbert Space 31 Quadratic Programming Problem Given a symmetric positive de nite matrix Q 6 RM A E Rm m lt 717 and b E R want to minimize XTQX7 subject to Ax b The feasible set is a linear variety7 AxbltgtxEX0NA ltgt N RATL This is a minimum norm problem ltgt X7 ygt XTQy de nes an oblique inner product Write down a numerical algorithm for the solution 32 Preliminaries Basic Principles in Optimization According to David Luenberger7 the theory of optimization can be summarized from a few simple intuitive7 geometric relations77 These are c The Projection Theorem ltgt The simplest form of this theorem is that the shortest line from a point to a plane is necessarily perpendicular to the plane 0 The Hahn Banach Theorem ltgt The simplest form of this theorem is that a sphere and a point not in the sphere can be separated by a hyperplane o Duality ltgt The simplest way to describe the duality is that the shortest distance from a point to a convex set is equal to the maximum of the distance from the point to a hyperplane separating the point from the convex set 0 Di erentials ltgt In R a functional is optimized only at places Where the gradient vanishes Each of these notions can easily be understood in R3 and can be extended into in nite dimensional space
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'