\relax \@writefile{toc}{\contentsline {section}{\numberline {1}Why Optimization}{1}{}\protected@file@percent } \newlabel{sec:why}{{1}{1}{}{section.1}{}} \@writefile{toc}{\contentsline {section}{\numberline {2}Convex Sets and Convex Functions}{1}{}\protected@file@percent } \newlabel{sec:convex}{{2}{1}{}{section.2}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Convex Sets}{1}{}\protected@file@percent } \@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Convex and non-convex sets.}}{2}{}\protected@file@percent } \newlabel{fig:sets}{{1}{2}{}{figure.1}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Convex Functions}{2}{}\protected@file@percent } \newlabel{eq:convexdef}{{2}{2}{}{equation.2}{}} \@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces A convex function. (a) Definition \eqref {eq:convexdef}. (b) First-order condition \eqref {eq:firstorder}. (c) The slopes inequality \eqref {eq:slopes}: the tangent slope at $w_1$, the chord slope, and the tangent slope at $w_2$ increase in that order.}}{2}{}\protected@file@percent } \newlabel{fig:convexfn}{{2}{2}{}{figure.2}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Derivatives of Convex Functions}{2}{}\protected@file@percent } \newlabel{eq:firstorder}{{4}{2}{}{equation.4}{}} \newlabel{eq:slopes}{{5}{2}{}{equation.5}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Convex Functions in This Course}{3}{}\protected@file@percent } \newlabel{sec:examples}{{2.4}{3}{}{subsection.2.4}{}} \@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces (a) The squared, logistic and hinge losses are convex in the margin $z$, and hence in $\mathbf {w}$; the 0-1 loss is not. (b) A non-convex function can trap a descent method in a local minimum; a convex one has only global minima.}}{3}{}\protected@file@percent } \newlabel{fig:losses}{{3}{3}{}{figure.3}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.5}Why Convexity Matters}{3}{}\protected@file@percent } \newlabel{sec:whyconvex}{{2.5}{3}{}{subsection.2.5}{}} \@writefile{toc}{\contentsline {section}{\numberline {3}Unconstrained Optimization}{4}{}\protected@file@percent } \newlabel{sec:unc}{{3}{4}{}{section.3}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {3.1}One Variable: Interval Cutting and Newton's Method}{4}{}\protected@file@percent } \@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces (a) Interval cutting on $f'$: the bracket $[0,2]$ is halved five times. (b) Newton's method from $w_0=0$: each step jumps to the minimum of the parabola that matches $f$, $f'$, $f''$ at the current point.}}{4}{}\protected@file@percent } \newlabel{fig:bisect}{{4}{4}{}{figure.4}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Several Variables}{5}{}\protected@file@percent } \@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Minimizing an elongated quadratic $\frac 12\mathbf {w}^TA\mathbf {w}$ (eigenvalues 1 and 12) from the same start. (a) Gradient descent with a fixed step zig-zags across the valley (after 30 steps it is still $0.014$ from the minimum); conjugate gradient reaches the minimum exactly in $D=2$ steps; Newton in one. (b) Coordinate descent minimizes along one axis at a time.}}{5}{}\protected@file@percent } \newlabel{fig:paths}{{5}{5}{}{figure.5}{}} \@writefile{toc}{\contentsline {section}{\numberline {4}Equality Constraints: Lagrange Multipliers}{6}{}\protected@file@percent } \newlabel{sec:eq}{{4}{6}{}{section.4}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Mary, Cal, and the River}{6}{}\protected@file@percent } \@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Mary (M) must reach Cal (C) as fast as possible but has to stop at the river first. Routes of equal length $|MP|+|PC|$ are ellipses with foci $M$ and $C$. The best stop $P$ is where the smallest ellipse that still reaches the river touches it: there the ellipse and the river are tangent, so $\nabla f$ and $\nabla h$ are parallel (computed: the angle between them is $0$).}}{6}{}\protected@file@percent } \newlabel{fig:mary}{{6}{6}{}{figure.6}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.2}The Lagrangian and Lagrange's Theorem}{6}{}\protected@file@percent } \newlabel{eq:lagrange}{{10}{7}{}{equation.10}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.3}Worked Examples}{7}{}\protected@file@percent } \@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces Lagrange multipliers at work: at each solution a level curve of $f$ (blue) is tangent to the constraint (green), so $\nabla f\parallel \nabla h$.}}{7}{}\protected@file@percent } \newlabel{fig:lagex}{{7}{7}{}{figure.7}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.4}Connection: PCA}{8}{}\protected@file@percent } \@writefile{toc}{\contentsline {section}{\numberline {5}Inequality Constraints and the KKT Conditions}{8}{}\protected@file@percent } \newlabel{sec:ineq}{{5}{8}{}{section.5}{}} \newlabel{eq:primal}{{14}{8}{}{equation.14}{}} \newlabel{eq:L}{{15}{8}{}{equation.15}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Active and Inactive Constraints}{8}{}\protected@file@percent } \@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces Feasible set (green) $g_1=w_1+w_2-2\le 0$, $g_2=-w_1\le 0$. (a) The unconstrained minimizer is feasible: no constraint matters, all $\alpha _i=0$. (b) The unconstrained minimizer $(2,1)$ is infeasible: the solution is on the boundary of $g_1$, where $\nabla f=-\alpha _1\nabla g_1$ with $\alpha _1=1\ge 0$. (c) At a corner two constraints are active and $-\nabla f$ lies in the cone spanned by their gradients.}}{9}{}\protected@file@percent } \newlabel{fig:ineq}{{8}{9}{}{figure.8}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Several Active Constraints}{9}{}\protected@file@percent } \@writefile{toc}{\contentsline {subsection}{\numberline {5.3}The KKT Conditions}{9}{}\protected@file@percent } \@writefile{toc}{\contentsline {section}{\numberline {6}Lagrangian Duality}{10}{}\protected@file@percent } \newlabel{sec:dual}{{6}{10}{}{section.6}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {6.1}The Primal as a Min--Max}{10}{}\protected@file@percent } \@writefile{toc}{\contentsline {subsection}{\numberline {6.2}The Dual Function and Weak Duality}{10}{}\protected@file@percent } \newlabel{eq:dualfn}{{18}{10}{}{equation.18}{}} \newlabel{eq:weak}{{19}{10}{}{equation.19}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {6.3}A Saddle Point, Explicitly}{10}{}\protected@file@percent } \@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces (a) The Lagrangian of: minimize $(w-7)^2$ subject to $2w-8=0$. Along $\beta =3$ (green) it is a parabola in $w$ with minimum at $w=4$; along $w=4$ (black) it is constant, because $h(4)=0$. (b) The dual function: always below $p^*$, touching it at $\beta =3$.}}{11}{}\protected@file@percent } \newlabel{fig:saddle}{{9}{11}{}{figure.9}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {6.4}The Geometry of Duality}{11}{}\protected@file@percent } \newlabel{sec:geom}{{6.4}{11}{}{subsection.6.4}{}} \@writefile{toc}{\contentsline {subsection}{\numberline {6.5}Strong Duality and Slater's Condition}{11}{}\protected@file@percent } \newlabel{sec:slater}{{6.5}{11}{}{subsection.6.5}{}} \@writefile{lof}{\contentsline {figure}{\numberline {10}{\ignorespaces Each $\mathbf {w}$ is plotted at $(u,t)=(g(\mathbf {w}),f(\mathbf {w}))$; feasible points have $u\le 0$. A dual value $\theta (\alpha )$ is the height at $u=0$ of a line of slope $-\alpha $ that stays below all the points. (a) Minimize $w^2$ s.t.\ $1-w\le 0$: the set is convex and the best line (slope $-2$) passes through $(0,p^*)$, no gap. (b) A non-convex problem: the best line ($\alpha =0.3$) rests on both dips and crosses $u=0$ below $p^*$: $d^*=0