Understanding Range and Null Space in Convex Optimization
Explore the concept of range and null space in convex optimization through discussions on matrix properties, reduced row echelon form, pivot operations, and solvability. Learn how to determine solutions and dimensions in various scenarios to enhance problem-solving skills.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE 203B: Convex Optimization Week 2 Discuss Session Xinyuan Wang 01/16/2019 1
Contents Preparation for HW1 Review and Exercise Properties of dual cone 2
Q1: Range an Null space The range of matrix ? ? ? is ? = ?? | ? ? or column subspace ??? ? Row subspace ??? ? = ??? ? ?} The nullspace of ? is defined to be ? ? = ? | ?? = 0 ? ? ??? ? dim(? ? ) + dim(??? ? ) = ? Analogy for column space How to find the range and null space of a matrix? 3
Q1: Range an Null space Reduced Row Echelon Form Determines whether ?? = ? is solvable and describes all the solutions Gaussian elimination on rows Pivot: the leading coefficient (first nonzero element from the left) is scaled to 1 Each column containing a leading 1 has zeros at other elements Operation at column k 4
Q1: Range an Null space 1 1 1 0 1 2 2 5 8 1 2 4 An example ?1= At column 1, choose ???as pivot R2-R1, R3-R1 1 0 0 0 1 2 2 3 6 1 1 3 ?1 ?2= At column 2, choose ???as pivot R2 R3 R2/2 R3-R2 1 0 0 0 1 0 2 3 0 1 1 0 0 0 1 1 2 3 3 1 1 0 0 0 2 1 2 6 3 1 3 1 3/2 1/2 ?2 ?3= 3/2 1 5
Q1: Range an Null space No pivot at col 3. At column 4, choose ???as pivot R1-R3, R2-R3*3/2 R3/-0.5 1 0 0 0 1 0 2 3 0 1 1 0 0 0 1 0 2 3 0 0 0 1 ?3 ?4= 3/2 1 Columns 1, 2 and 4 are independent The range ?1? = ?1???1 + + ?4???4 1 1 1 The column spaces of ?1and ?4can be different, but their dimensions must be the same. 0 1 2 1 2 4 ?1 = , , 6
Q1: Range an Null space Proposition: given a matrix ? ?? ?and ? ??, after any sequence of elementary row operations ? ,? = ?(?,?), then solutions of ?? = ? are the same as ? ? = ? . The null space of of ? is defined as ? ? = ? | ?? = 0 ?1? = 0 ?4? = 0 where 1 0 2 0 1 3 0 0 0 0 0 1 ?4= For example, a nonzero solution 2 3 ?1+ 2?3= 0 ?2+ 3?3= 0 ?4= 0 ? = ? ? Solve 1 0 Which spans the null space because dim(? ? )=1. 7
Q1: Range an Null space What if there exist many variables? The space of ? ?(?) could be format with the constrained and free variables. ?1= 2?3 ?2= 3?3 ?3= ?3 ?4= 0 ?1+ 2?3= 0 ?2+ 3?3= 0 ?4= 0 1 0 0 0 1 0 2 3 0 0 0 1 ?4= Free variable ?1 ?2 ?3 ?4 2 3 1 0 2 3 1 0 ? = = ?3 , so ? ? = { } 8
Q2:Eigenvalue Decomposition Let ? ? ?, ?? = ?? leads to det ? ?? = 0. Then it could be factorized as ? = ? ? 1 where ? ? ? contains the eigenvector ?? of ?, and = diag ?1, ,?? whose diagonal elements are the corresponding eigenvalues. The eigenvectors are usually normalized. If ? is symmetric then ? is orthogonal. Defective matrix: cannot find ? independent eigenvectors, so it is not diagonalizable ?1 0 ? = ?? ?? , = ?? 0 0 Nil-potent 9
Q2:Eigenvalue Decomposition Could we tell the range and null space of matrix from its eigenvalue decomposition? ?? = ?? If ?? 0, then ?? (?) If ??= 0, ???= 0 then ?? ? ? Example: 1 1 1 0 1 2 2 5 8 ? = 9.4721 0.1969 0.5154 0.8240 0.9123 0.3484 0.2154 0.5345 0.8018 0.2673 ? = , = 0.5279 0.0000 10
Q3:Singular Value Decomposition Let ? ? ?, ?? = ?? leads to det ? ?? = 0. Then it could be factorized as ? = ??? where ? ? ? and ? ? ? are unitary matrices which are orthogonal if ? is real. is a diagonal matrix with non-negative real diagonal, called singular values. The columns of ? are eigenvectors of ? ? ? ? = ?? ? ? ?? = ??2? The columns of ? are eigenvectors of ?? ?? = ?? ? ? ?? = ??2? The non-zero elements of are the square roots of the non-zero eigenvalues of ? ? and ?? Related to eigenvalue decomposition, can we figure out the range and null space of a matrix from its SVD results? 11
Review: Dual Cone Properties Definition: Let ? be a cone, the set ? = ? ??? 0 for all ? ?} is called the dual cone of ?. A convex cone ? is proper cone if ? is closed (contains its boundary) ? is solid (has nonempty interior) ? is pointed (contains no line) Let ? be the dual cone of a convex cone ?. (see exercise 2.31) ? is indeed a convex cone. ?1 ?2 implies ?2 ? is closed. The interior of ? is given by ??? ? = ? ??? > 0 for all ? ?? ?}. If ? has nonempty interior then ? is pointed. ? is the closure of ?. (Hence if ? is closed, ? = ?.) If the closure of ? is pointed then ? has nonempty interior. ?1 . 12
Review: Dual Cone Properties How to prove that ? is indeed a convex cone? See the definition of ? ? ??? 0 ??? ??? ? ?}, ? is the intersection of a set of homogeneous halfspace (??? 0) which include the origin as a boundary point. So ? is a closed convex cone. ?1 ?2 implies ?2 From the definition of ? , if ? ?2 also in ?1 ? is the closure of ?. (Hence if ? is closed, ? = ?.) See the definition of ? , ? 0 is the normal vector of a homogeneous halfspace containing ? iff ? ? . The intersection of all the homogeneous halfspaces containing a convex cone ? is the closure of ?. Therefore the closure of ? is ?1 then ??? 0 for all ? ?2. So ??? 0 for all ? ?1, ? is . ? ??? 0} = {? ??? 0 for all ? ? = ? ?? ? = ? ? Try to prove the other properties. 13
