-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathSpecial_Review_Session.aux
111 lines (111 loc) · 11.9 KB
/
Special_Review_Session.aux
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
\relax
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand\HyField@AuxAddToFields[1]{}
\providecommand\HyField@AuxAddToCoFields[2]{}
\@writefile{toc}{\contentsline {section}{\numberline {1}Vector Concepts}{1}{section.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Linear Independence}{1}{subsection.1.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Orthogonality and Orthonormality}{2}{subsection.1.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.3}Span}{2}{subsection.1.3}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Matrix Concepts}{3}{section.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Dyads}{3}{subsection.2.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Orthogonal Matrix}{3}{subsection.2.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Trace}{3}{subsection.2.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Invertibility}{4}{subsection.2.4}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Range and Nullspace}{5}{section.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Range}{5}{subsection.3.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Nullspace}{5}{subsection.3.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Rank-Nullity Theorem}{5}{subsection.3.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.4}Examples}{6}{subsection.3.4}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Fundamental Theorem of Linear Algebra}{7}{section.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}How to Apply Fundamental Theorem of Linear Algebra}{7}{subsection.4.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}Getting the range or nullspace when you only know the other}{7}{subsection.4.2}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Eigenvalue Decomposition and Singular Value Decomposition}{9}{section.5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Eigendecomposition}{9}{subsection.5.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}SVD}{9}{subsection.5.2}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.1}Compact Form}{9}{subsubsection.5.2.1}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.2.2}Expanded Form}{10}{subsubsection.5.2.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.3}Recovering $U$ or $V$ given $A$, $\Sigma $, and the other}{10}{subsection.5.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.4}Recovering $u_i$ or $v_i$ given $A$, $\sigma _i$, and the other}{11}{subsection.5.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.5}Connecting SVD to Eigendecomposition}{12}{subsection.5.5}}
\@writefile{toc}{\contentsline {section}{\numberline {6}The Most Important Equation in Linear Algebra: $Ax = b$}{14}{section.6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.1}Case 1: $A$ is invertible (One Solution)}{14}{subsection.6.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2}Case 2: $b \notin \mathop {\mathcal {R}}\nolimits (A)$ (Zero Solutions)}{14}{subsection.6.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.3}Case 3: $A$ is not invertible, but $b \in \mathop {\mathcal {R}}\nolimits (A)$ (Infinity Solutions)}{14}{subsection.6.3}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Projections}{15}{section.7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.1}Projecting onto a line}{15}{subsection.7.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.2}Projecting onto a plane}{16}{subsection.7.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.3}Projection onto a subspace}{16}{subsection.7.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {7.4}Vectors and Tensors: Invariance Under Rotations}{16}{subsection.7.4}}
\@writefile{toc}{\contentsline {section}{\numberline {8}Optimization Concepts}{17}{section.8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {8.1}You Can Optimize In Any Order}{17}{subsection.8.1}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {8.1.1}What about constraints?}{17}{subsubsection.8.1.1}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {8.1.2}What if I have a $\qopname \relax m{min}$ and a $\qopname \relax m{max}$? Does this still work?}{18}{subsubsection.8.1.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {8.2}Solving Simple Unconstrained Optimization Problems}{18}{subsection.8.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {8.3}Example: Single-Variable Quadratic Optimization}{18}{subsection.8.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {8.4}Example: Multivariable Least-Squares}{19}{subsection.8.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {8.5}Example: $L_2$-Regularized Least-Squares}{19}{subsection.8.5}}
\@writefile{toc}{\contentsline {section}{\numberline {9}Convex Sets}{20}{section.9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {9.1}Examples of Convex Sets}{20}{subsection.9.1}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {9.1.1}Affine Sets}{20}{subsubsection.9.1.1}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {9.1.2}Hyperplanes and Halfspaces}{20}{subsubsection.9.1.2}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {9.1.3}Euclidean Balls}{21}{subsubsection.9.1.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {9.2}Operations Preserving Convexity}{22}{subsection.9.2}}
\@writefile{toc}{\contentsline {section}{\numberline {10}Convex Functions}{23}{section.10}}
\@writefile{toc}{\contentsline {subsection}{\numberline {10.1}First-Order Conditions for Convexity}{23}{subsection.10.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {10.2}Second-Order Conditions for Convexity}{23}{subsection.10.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {10.3}Examples of Convex Functions}{23}{subsection.10.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {10.4}Operations that preserve convexity}{24}{subsection.10.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {10.5}Examples of proving convexity using operations that preserve convexity}{25}{subsection.10.5}}
\@writefile{toc}{\contentsline {section}{\numberline {11}Convex Optimization: Definitions}{27}{section.11}}
\newlabel{convexopt}{{2}{27}{Convex Optimization: Definitions}{equation.11.2}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {11.1}Linear Programs (LP)}{27}{subsection.11.1}}
\newlabel{LP}{{3}{27}{Linear Programs (LP)}{equation.11.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {11.2}Quadratic Programs (QP)}{28}{subsection.11.2}}
\newlabel{QP}{{4}{28}{Quadratic Programs (QP)}{equation.11.4}{}}
\@writefile{toc}{\contentsline {section}{\numberline {12}Convex Optimization: Equivalent Optimization Problems}{29}{section.12}}
\@writefile{toc}{\contentsline {subsection}{\numberline {12.1}Simple Sub-problems}{29}{subsection.12.1}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Optimizing a quadratic function with the constraint $x \geq 0$. The shaded part of the real line represents the feasible set. $x_u^*$ is the global solution to the unconstrained problem. $x^*$ solves the constrained problem.\relax }}{30}{figure.caption.1}}
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{conquad}{{1}{30}{Optimizing a quadratic function with the constraint $x \geq 0$. The shaded part of the real line represents the feasible set. $x_u^*$ is the global solution to the unconstrained problem. $x^*$ solves the constrained problem.\relax }{figure.caption.1}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Optimizing a linear function, $a^T x$, over a halfspace $b^T x \geq c$. The objective decreases in the direction $-a$. If any vector in the hyperplane $b^T x = c$ has positive inner product with $-a$, then the objective decreases as you move along the hyperplane (following the dashed path), and the optimal value is $-\infty $. In order for the optimization problem to have finite value, $a$ must align with $b$.\relax }}{31}{figure.caption.2}}
\newlabel{hs}{{2}{31}{Optimizing a linear function, $a^T x$, over a halfspace $b^T x \geq c$. The objective decreases in the direction $-a$. If any vector in the hyperplane $b^T x = c$ has positive inner product with $-a$, then the objective decreases as you move along the hyperplane (following the dashed path), and the optimal value is $-\infty $. In order for the optimization problem to have finite value, $a$ must align with $b$.\relax }{figure.caption.2}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {12.2}Equality-Preserving Transformations}{32}{subsection.12.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {12.3}Constraint Magic}{33}{subsection.12.3}}
\newlabel{maxconstraint}{{5}{33}{Constraint Magic}{equation.12.5}{}}
\newlabel{maxconstraint2}{{6}{34}{Constraint Magic}{equation.12.6}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Geometric intuition for constraints involving absolute values. Here, we are considering a case where $s_i \geq 0$.\relax }}{35}{figure.caption.3}}
\newlabel{absval}{{3}{35}{Geometric intuition for constraints involving absolute values. Here, we are considering a case where $s_i \geq 0$.\relax }{figure.caption.3}{}}
\@writefile{toc}{\contentsline {section}{\numberline {13}Duality Intro: Defining Weak and Strong Duality}{36}{section.13}}
\@writefile{toc}{\contentsline {subsection}{\numberline {13.1}Weak Duality}{36}{subsection.13.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {13.2}Strong Duality}{37}{subsection.13.2}}
\@writefile{toc}{\contentsline {section}{\numberline {14}Duality Intro: Lagrange Dual Problems}{38}{section.14}}
\newlabel{primal}{{8}{38}{Duality Intro: Lagrange Dual Problems}{equation.14.8}{}}
\newlabel{minmax}{{9}{38}{Duality Intro: Lagrange Dual Problems}{equation.14.9}{}}
\newlabel{maxmin}{{10}{38}{Duality Intro: Lagrange Dual Problems}{equation.14.10}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {14.1}Why Does the Min-Max Formulation Work?}{39}{subsection.14.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {14.2}Lagrange Dual Problems Always Exist}{40}{subsection.14.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {14.3}Lagrange Dual Problems Are Not Unique}{40}{subsection.14.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {14.4}Lagrange Dual Problems for Maximization Primal Problems}{42}{subsection.14.4}}
\@writefile{toc}{\contentsline {section}{\numberline {15}Duality Intro: When Does Strong Duality Hold?}{44}{section.15}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.1}Strong Duality for Lagrange Dual Problems}{44}{subsection.15.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.2}Strong Duality for General Min-Max Problems}{45}{subsection.15.2}}
\@writefile{toc}{\contentsline {section}{\numberline {16}KKT Conditions}{46}{section.16}}
\@writefile{toc}{\contentsline {section}{\numberline {17}\href {http://catb.org/jargon/html/magic-story.html}{More Magic}}{47}{section.17}}
\@writefile{toc}{\contentsline {subsection}{\numberline {17.1}The Norm Trick}{47}{subsection.17.1}}
\newlabel{exconv}{{12}{47}{}{equation.17.12}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {17.2}``Min---There Exists'' Trick}{48}{subsection.17.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {17.3}Bad Case of the Infinities}{48}{subsection.17.3}}