Optimization - Lecture 3 Eigenvalues, Eigenvectors, Gradient, Hessian .

1y ago
8 Views
2 Downloads
2.00 MB
20 Pages
Last View : 2m ago
Last Download : 2m ago
Upload by : Alexia Money
Transcription

Optimization – Lecture 3Eigenvalues, Eigenvectors,Gradient, Hessian, Curvature ofSurfaceshttp://users.encs.concordia.ca/ luisrodCopyright Luis Rodrigues, January 2014

Outline Projections, Eigenvalues and Eigenvectors Directional Derivative and Gradient Vector Surfaces and Functions of Two Variables Surface Curvature and Hessian MatrixCopyright Luis Rodrigues2

Projections on a Plane To study optimization of functions of two variables we willneed to study projections of the curvature vector on thetangent plane and on the normal vector to a surface A plane S can be represented by the so-called normal equations when a unit normal (orthogonal) vector n tonthe plane is known Sc { x : n x c} where c is a constant and the notation { x : n x c}means the set of vectors x such that n x c The projection of a vector v onto the plane S c is p I nn v where P I nn()is the projection tensorCopyright Luis Rodrigues3

Example v e1 2e2 3e3 , S 0 {x : e3 x 0} p I e3e3 v I v e3 (e3 v ) v (e3 v )e3() p e1 2e2 3e3 3e3 e1 2e2 e3 e1 v e2 pCopyright Luis Rodrigues4

Normal Equations Another way to find the projection p of a vector v onto aplane that passes through the origin (subspace) is to find a set of basis vectors u , u for the plane and then1 2write the equations p α1u1 α 2u2 (v p) u1 0 v u1 α1u1 u1 α2u2 u1 0 Normal (v p) u2 0 v u2 α1u1 u2 α2u2 u2 0 Equations Example: For the previous example we get (v p) e1 0 v e1 α1e1 e1 α2e2 e1 0 v1 α1 (1) α2 (0) (v p) e2 0 v e2 α1e1 e2 α2e2 e2 0 v2 α1 (0) α2 (1) p α1e1 α 2 e2 v1e1 v2 e2 e1 2e2Copyright Luis Rodrigues5

Eigenvalues and Eigenvectors What happens if you project a vector on a plane whenthe vector is already on the plane ? The projection is the original vector (same direction) andthe vector is left invariant under the projection operation In 3 dimensional space if we assume that we areprojecting vectors on the horizontal plane e1, e2 then the coordinates of the projection tensor in frame E ( e1, e2 , e3 )become! 1 0 0 # ! 0 #! 1 0 0 #E E ! P# ! I e 3e 3 # && 0 1 0 '' && 0 ''! 0 0 1 # && 0 1 0 ''" " " & 0 0 1 ' & 1 '& 0 0 0 '" " " Foralready in the e1, e2 plane we see thatv any vector eigenvalue of PP v λ v, λ 1 so λ 1 is an with eigenvector v v1e1 v2 e2Copyright Luis Rodrigues6

Eigenvalue Computation From the previous considerations we see that tocompute eigenvalues we need to solve the equation P v λ v ( P λ I ) v 0 Let P, I be the coordinates(matrices) of P, I in a frameof interest, for example frame E ( e1, e2 , e3 ) Then the equation for computing eigenvalues for nontrivial (nonzero) eigenvectors isP λI 0 Example: For the projection tensor we get! 1 0 0 ! 1 0 0 1 λ00#& #&01 λ 0 0# 0 1 0 & λ# 0 1 0 & 0 # 0 0 0 & # 0 0 1 &00 λ"% "% λ (1 λ )2 0 λ 0 λ 1 λ 1Copyright Luis Rodrigues7

Eigenvector Computation To compute the eigenvectors associated with eacheigenvalue λ we just need to solve the equation(P λ I )v 0 Example: For the projection tensor we getλ 1 (P (1)I )v 0# v &# 0 0 0 &# v1 &# 11(%(%(%%% 0 0 0 (% v2 ( 0 v3 0 % v2 ( v1 % 0%(% 0 0 1 (% v (% 0v '% 3 ('% 3 ('# 0 &&%((( v2 % 1 (% 0 ((' '# v &# 0 &1%(%(λ 0 (P (0)I )v 0 v1 0 v2 0 % v2 ( v3 % 0 (%(% 1 (v '% 3 ('Copyright Luis Rodrigues8

Diagonalization of Matrices If we find the eigenvectors of a matrix then we candiagonalize such a matrix The principal diagonal of the diagonalized matrix isformed by the eigenvalues This can be shown using the eigenvector equation(P λ I )v 0 Pvi λi vi v v ' v v ' λ 0 'nn& 1) & 1)& 1)P& ) & )& 0 0 )& ) & )& 0 λ ) n )&%)( &%)(&%( TTΛ 1 Therefore Λ T PT . When the eigenvectors form anTT 1Torthonormal set then T T and (Tx) P(Tx) x ΛxCopyright Luis Rodrigues9

Curvature of Surfaces An important application of eigenvalues and eigenvectorsis the computation of principal curvatures of a surface We saw that the curvature of a curve is associated to therate of change of the unit velocity vector The curvature of a surface is connected to the rate ofchange of the unit normal vector to the surface For example, the curvature of a plane is zero because thedirection of the unit normal vector does not change If we compute the curvature vector of any curve in theplane and then find its component along the normal wesee that the normal curvature of any curve is zero We now generalize this idea to surfaces by computing thenormal curvature of curves in the surfaceCopyright Luis Rodrigues10

Directional Derivatives Before writing an expression for the normal curvature weneed to review directional derivatives A directional derivative of a scalar function f x along adirection given by vector v is defined as v f lim h 0 [( f ( x hv) f ( x)) h ]() A partial derivative is a directional derivative in one of thedirections of the orthonormnal basis ( e1, e2 , e3 ) . We write2 f f ei f lim h 0 [( f ( x hei ) f ( x)) h ] f xi , f xi x j xi x j xi The gradient vector is the vector of all partial derivatives f " f x1#f x2f x3T % (( v f f v (using Taylor series)'& " Directional derivative of a vector: v f # v f1 v f2Copyright Luis RodriguesT v f3 %11

Taylor Series Using derivatives one can approximate a differentiablefunction by a polynomial through Taylor series. The higherthe order of the polynomial the best the approximation If the function to be approximated is already a polynomialthen the approximation will be exact when the order of theTaylor series is the same as the order of the polynomial2ndC The 2 order Taylor series of a class (twice Hessiandifferentiable) function around a point x0 isMatrix! ff xy T 1 Txx&f ( x) f ( x0 ) f ( x0 ) [ x x0 ] [ x x0 ] H [ x x0 ] H ## f yx f yy &2"% Example (Directional Derivative Using Taylor Series) %' v f lim [( f ( x hv) f ( x)) h ] lim & f ( x) ( v ) h h( f ( x) vh 0h 0Copyright Luis Rodrigues12

Normal Curvature Let a curve in a surfacebe described by the parameterization vector x and let κ n be the normal curvature The derivative of x(s) relative to arc length is a unit tangent vector denoted by T x ' orthogonal to the unit normal ns dnd x ' n 0 ( x ' n ) 0 x '' n x ' 0dsds dnκ n (s) x '' n x ' ds Let our point of interest be p x(0) and let v x '(0). Then dn [ x(s)] κ n (0) v v ( n( p) v ) v ( v n) v L ( v )ds s 0Copyright Luis Rodrigues13

Weingarten Map The directional derivative in the last slide is a lineartransformation, called the Weingarten map, that transforms a tangent vector v into another tangent vector L(v) L ( v ) v n We can find the columns of the matrix representing thislinear transformationby applying it to the basis of tangentvectors vi obtained from the parameterization r of a surface # r # f & r f &r(x, y) [x, y, f (x, y)] v1 %1, 0, (, v2 %0,1, ( x x ' y y ' & &## n n n f n n n fL(v1 ) % (1) (0) (, L(v2 ) % (0) (1) ( y f x ' y f y ' x xCopyright Luis Rodrigues14

Weingarten Map An expression for the unit normal vector can also beobtained from the parameterization r leading to # r r &% ( x y '[n ] r r x y nLv [] 1# fx , fy ,1&' n x 0 , 22fx fy 1 f- L [ v ] n2-. y The normal vector is orthogonal to both tangent vectors, so & v n n v()ii( 0 vi n vi L ( v1 )( x x xvi n 0 ' i 1, 2 ( ( vi n ) 0 v n vi n v L v ()ii2( y y y)15Copyright Luis Rodrigues

Normal Curvature " T # T κ v L(v) [ v ] T [ v ]The normal curvature is obtained as n 1 for any unit tangent vector v α1e 1 α 2 e 2 , ei vi vi , v1 v2 % " %2 2 v1 L ( v1 ) v1 L ( v2 ) r n rn' ' 2 2v1 v2 ' x 2 v1 y x v1 v2 'v1T' T ' 2 2 v2 L ( v1 ) v2 L ( v2 ) ' rn r n' 2 ' 2 ' x y v v 2 yv2 v1v2v221'&'& #"fxx 21 f x1 T fyxfx2 fy2 1 221 f1 fxy #fxy1 fx2 1 fy2f yy1 fy2%''''''&Copyright Luis RodriguesNote: When f x f y 0matrix T (shapeoperator) becomesthe Hessian matrix H16

Example Applying the notion of curvature of a surface to the Earthconsidered as a spherical surface parameterized bylatitude φ and longitude λ with radius R [r(φ, λ )] [Rcos φ cos λ, Rcos φ sin λ, Rsin φ ]" r % ' [ Rsin φ cos λ, Rsin φ sin λ, Rcos φ ]# φ & " r % # '& [ Rcos φ sin λ, Rcos φ cos λ, 0 ], n(φ, λ ) λ r(φ, λ ) r(φ, λ )Note: Normal curvature in the"%1 1 01T ' I direction of both tangent vectorsR # 0 1 &R 1is the same and equal to RCopyright Luis Rodrigues17

Principal Curvatures The eigenvectors u1, u2 of T are orthogonal if λ1 λ2 T T λ1 [u1 ] [u2 ] T [u1 ] [u2 ] [u1 ] T T [u2 ] [u2 ] T T [u1 ] λ2 [u2 ] [u1 ] An orthonormal set of eigenvectors ei ui ui will givethe directions of principal curvature; the eigenvalues λi 1are the principal curvatures Expressing any unit vector e in the basis ( e1, e2 ) yields e cosα e1 sin α e2 κ n e L(e) (cosα e1 sin α e2 ) (cosα L(e1 ) sin α L(e2 )) 2 2 cos α e1 L(e1 ) sin α e2 L(e2 ) 0κ n cos2 αλ1 sin 2 αλ2 eαEuler’s Curvature Equation The principal curvatures correspond to the maximumand minimum normal curvatures of the surfaceCopyright Luis Rodrigues e1

Mean and Gauss Curvatures The principal curvatures give us two directions where thenormal curvature will be maximum and minimum but thequestion is: What is the curvature of the surface? There are two common measures of curvature used: themean curvature and the Gauss curvature The mean curvature is the arithmetic average of theprincipal curvatures (one half of the trace of T ) The Gauss curvature is the product of the principalcurvatures (the determinant of T) Gauss’s most accomplished result in differential geometryis the Theorema Egregium (latin for “RemarkableTheorem”) which states that the Gaussian curvature isindependent of the coordinate system and is thereforethe preferred measure of curvature associated with a19surfaceCopyright Luis Rodrigues

Conditions for Minimum The sufficient condition for a minimum of a function of asingle variable was that the curvature should be positive The criteria for minimum of a function of 2 variables shouldintuitively be that the curvature in all directions be positive The principal curvatures give us the minimum andmaximum normal curvatures A sufficient condition for a minimum is that the minimumnormal curvature be positive This means that a sufficient condition for a minimum isthat the minimum eigenvalue of the Hessian matrix bepositive A necessary condition for a minimum is that the slope oftangent plane in all directions be zero or, in other words,the gradient be zero. This will be proved in the next classCopyright Luis Rodrigues20

Directional Derivatives 11 Before writing an expression for the normal curvature we need to review directional derivatives A directional derivative of a scalar function along a direction given by vector is defined as . The gradient vector is the vector of all partial derivatives

Related Documents:

6.1. Introduction to Eigenvalues 289 To explain eigenvalues, we first explain eigenvectors. Almo st all vectors change di-rection, when they are multiplied by A. Certain exceptional vectors x are in the same direction as Ax. Those are the “eigenvectors” . Multiply an eigenvector by

Introduction of Chemical Reaction Engineering Introduction about Chemical Engineering 0:31:15 0:31:09. Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture

Eigenvalues, Eigenvectors, and Diagonalization 428 12.2Getting Started 12.2.1The Algebraic Eigenvalue Problem * View at edX The algebraic eigenvalue problem is given by Ax lx: where A 2Rn n is a square matrix, l is a scalar, and x is a nonzero ve

Eigenvalues and Eigenvectors Applications Diagonalisation and iteration Radboud University Nijmegen Political swingers, part II So

Lecture 11 – Eigenvectors and diagonalization Lecture 12 – Jordan canonical form Lecture 13 – Linear dynamical systems with inputs and outputs Lecture 14 – Example: Aircraft dynamics Lecture 15 – Symmetric matrices, quadratic forms, matrix norm, and SVD Lecture 16 – SVD applications

Note that we have de ned the exponential e t of a diagonal matrix to be the diagonal matrix of the e tvalues. Equivalently, eAtis the matrix with the same eigenvectors as A but with eigenvalues replaced by e t. Equivalently, for eigenvectors, A acts like a number , so eAt x k e kt x k. 2.1 Example For ex

Theorem 1 If A is symmetric, then any two eigenvectors from different eigenspaces are orthogonal. Proof Let v1 and v2 be eigenvectors corresponding to distinct eigenvalues 1 and 2.Observe that vT 2 Av1 v T 1 A Tv 2 v T 1 Av2 ) vT 2 ( 1v1) v T 1 ( 2v2) ) 1(v1 v2) 2(v1 v

network analysis and the topic models for text analysis, and our general theory can be . Bai and Silverstein(2006) for detailed book-length accounts of the topic of random matrices. There is a rich recent literature in mathematics on the asymptotic behaviors of eigenvalues and eigenvectors