optimization

# convex optimization

## convex sets (boyd 2)

• affine set: $x_1, x_2 \in C, \theta \in \mathbb{R} \implies \theta x_1 + (1 - \theta) x_2 \in C$
•  affine hull: aff C = {$\sum \theta_i x_i x_i \in C, \sum \theta_i =1$}
• convex set: $x_1, x_2 \in C, 0 \leq \theta \leq 1 \implies \theta x_1 + (1 - \theta) x_2$
•  convex hull: conv C = {$\sum \theta_i x_i : x_i \in C, \theta_i \geq 0, \sum \theta_i = 1$}
• cone: $\theta \geq 0 \implies \theta x \in C$
• operations that preserve convexity
• intersection (finite intersection of half-spaces)
• pointwise max of affine funcs
• composition
• affine
• perspective
• linar fractional = projective
• generalized inequalities:
• proper cone K: convex, closed, pointed, solid
• $x \preceq_K y \iff y-x \in K$
• separating hyperplane thm: C, D convex $C \cap D =\emptyset \implies \exists a \neq 0, b : s.t. \ a^Tx \leq b \forall x \in C, \a^Tx \geq b \forall x \in D$
•  supporting hyperplane thm: {$x a^tx = a^t x_0$} where $x_0$ on boundary of convex C
•  dual cone $K^*$ = {$y x^Ty \geq 0 : \forall x \in K$}
• $\preceq_{K^*}$ is dual of $\preceq_K$
• $x \preceq_K y \iff \lambda^T x \leq \lambda^T y \quad \forall : \lambda \succeq_{K^*} 0$

### geometry

•  ellipsoid: {$x \in \mathbb{R}^n (x-x_c)^T P^{-1} (x-x_c) \leq 1$} where P symmetric, PSD
•  {$x_c + Au u _2 \leq 1$}
•  hyperplane: {$x a^Tx = b$} ~ creates a halfspace
•  norm cone: {$(x, t) : x \leq t$}
•  polyhedron: {x Ax=b, Cx=d} = ${ \sum_i^k \theta_i v_i \; \sum_i^m \theta_i = 1, \theta_i \geq 0 } : m \leq k$
• simplex: conv{$v_{0:k}$}

## convex funcs (boyd 3)

• definitions
1. Jensen’s inequality $0 \leq \theta \leq 1$
• $f(\theta x_1 + (1 - \theta) x_2) \leq \theta f(x_1) + (1 - \theta) f(x_2)$
• $f(E[X]) \leq E[f(X)]$
2. $\nabla^2 f(x) \succeq 0$
3. $f(x_2) \geq f(x_1) + \nabla f(x_1)^T (x_2 - x_1)$
• can show this by restricting to an arbitrary line
4. consider epi f - also use things that preseve convexity
• concepts
•  epigraph epi f = ${ (x, t) \; : x \in dom f, f(x) \leq t }$
• extended value extension: $\tilde{f}(x) = f(x)$ if $x \in dom f$ else $\infty$
• wide sense function - can take on values $\pm \infty$
•  = dom f = {$x f(x) < \infty$}
•  wide sense convex func: $f(x) = inf { t \in \mathbb{R} (x, t) \in F}$ where $F \subseteq \mathbb{R}^{n+1}$
•  $F(x) = inf { t \in \mathbb{R} (x, t) \in F }$
• $\alpha$-sublevel set of convex func is convex
• operations that preserve convexity
• nonnegative weighted sums ~ multiplies for logs
• affine map
• pointwise max of convex
• composition
• perspective
• minimization ~ sometimes
• conjugate of f
• $f^*(y) = \underset{x \in dom f}{sup} : y^T x - f(x)$
•  dom $f^*$ = {$y f^*(y)$ is finite}
• called Legendre transform when f differentiable
• fenchel’s inequality: $f(x) + f^*(y) \geq x^ty$
• $f^{**} = f$ iff convex, closed
• ex. $f(S) = log : det X^{-1}$
• $f^*(Y) = \underset{X}{sup} [tr(YX) + log : det X]$
• $= -n - log : det(-Y)$ if $-Y \in S^n_{++}$
• can use conj. to go other way: $f(y) = \underset{x}{sup}(y^Tx - f^*(x))$

## optimization

• standard form: $p^* = min : f_0(x)\s.t. : f_i(x) \leq 0 \ h_i(x) = 0$
• equivalent problems
• change of vars
• constraint transformations
• slack vars
• eliminating equalities
• eliminating linear equalities
• introducing equalities
• optimizing over some vars ~ ex. quadratic
• epigraph form: $min : t : s.t. : f_0 \leq t$
• implicit + explicit constraints

## convex optimization

• standard form: $p^* = min \: f_0(x)\\s.t. \: f_i(x) \leq 0 \\ a_i^Tx = b_i$ where all f are convex
• optimality criteria (special cases of KKT)
• x optimal if
1. x is feasible
2. $\nabla f_0 (x)^T(y-x) \geq 0 : \forall y$ feasible
• if unconstrained $\nabla f_0 (x) = 0$
• if equality only Ax=b, $\nabla f_0 (x) \perp N(A)$
• $x \succeq 0$, $\nabla f_0 (x) \succeq 0; x_i (\nabla f_0 (x))_i = 0$
• equivalent convex problems
• eliminating equality constraints
• introducing equality constraints
• slack vars ~ for linear inequalities
• epigraph form
• minimizing over some vars

## linear optimization

• $p^* = min \: c^T x + d\\s.t. \: Gx \succeq h \\ Ax=b$
• standard form $x \succeq 0$ is the only inequality
• standard dual: max $-b^T \nu$ s.t. $A^T \nu + c \geq 0$
• linear-fractional program
• $min : \frac{c^Tx + d}{e^tx+f} \ s.t : Gx \succeq h \ Ax = b$ ~ can be converted to LP

• $min \: 1/2 x^TPx + q^Txr \\s.t. \: Gx \succeq h$ where $P \in S_+^n$
• QCQP - inequality constraints also convex
•  ex. $min : Ax-b _2^2$
•  SOCP - $$min f^Tx \ s.t. : A_ix+b_i _2 \leq c_i^T + d_i \ Fx=g$$

## geometric program

• $min \: f_0(x) \\ s.t. \: f_i(x) \leq 1 \: i = 1:m \\ h_i(x) = 1 \: i = 1:p$ where $f_{0:m}$ posynomials, $h_i$ monomials
• monomial $f(x) = c x_1^{a_1} \cdot x_n^{a_n}, c>0$
• posynomial ~ sum of monomials ~ can transform into convex w/ $y_i = log x_i$

## generalized inequality

• $min \: f_0(x)\\s.t. \: f_i(x) \preceq_{K_i} 0, i=1:m\\Ax=b$
• conic form problem: $min \: c^Tx \\ s.t. \: Fx +g \preceq_K 0\\Ax=b$ ~ set $K=S_+^K$
• SDP = semi-definite program: $min \: c^T x\\s.t. \: x_1F_1+...+x_nF_n+G \preceq 0\\Ax=b$ ~ where $F_1, …, F_n \in S^k$
• standard form: $min : tr(CX) \ s.to : tr(A_iX)=b_i \ X \succeq 0$

# duality (boyd 5)

• consider $\min : f_0 (x) \ s.t. : f_i(x) \leq 0 \ h_i(x) = 0$
• lagrangian $L(x, \lambda, \nu) = f_0(x) + \sum \lambda_i f_i(x) + \sum \nu_i h_i(x)$
• dual function $g(\lambda, \nu) = \underset{x \in D}{\inf} L(x, \lambda, \nu)$ ~ g always concave

• $\lambda \succeq 0 \implies g(\lambda, \nu) \leq p^*$
• $(\lambda, \nu)$ dual feasible if
1. $\lambda \succeq 0$
2. $(\lambda, \nu) \in dom : g$
• when $p^* = - \infty$, dual infeasible
• when $d^*=\infty$, primal infeasible
• dual related to to conjugate func

• ex. min f(x) s.t. $x = 0 \implies g(\nu) = -f^*(-\nu)$
• lagrange dual problem: $\max : g(\lambda, \nu)\s.t. : \lambda \succeq 0$
• weak duality: $d^* \leq p^*$

• optimal duality gap: $p^* - d^*$
• strong duality: $d^* = p^*$ ~ requires more than convexity
• slater’s condition ~ if problem convex $\implies$ strong duality + $\exists$ dual optimal point
• $\exists x \in relint : D\f_i(x) < 0\Ax = b$ ~ point is strictly feasible
• to weaken this, affine $f_i$ can be $\leq 0$
• sion’s minimax thm: $x \to f(x, y)$ ~ conditions

• $\implies \underset{x}{min} : \underset{y}{sup} : f(x,y) = \underset{y}{sup} : \underset{x}{min} : f(x,y)$

## optimality conditions

• duality gap: $f_0(x) - g(\lambda, \nu)$
• can use stopping condition duality gap $\leq \epsilon_{abs}$ to be $\epsilon_{abs}$ - suboptimal
• strong duality yields complementary slackness
• $\lambda_i f_i(x^*)=0$
• KKT optimality conditions ~ assume $f_0, f_i, h_i$ differentiable, strong duality
1. $f_i(x^*) \leq 0$
2. $h_i(x^*) = 0$
3. $\lambda_i^* \geq 0$
4. $\lambda_i^f(x_i^) = 0$
5. $\nabla f_0 (x^) + \sum \lambda_i^ \nabla f_i (x_i^) + \sum \nu_i^ \nabla h_i (x^*) = 0$

## thms of alternatives

• weak alternative - at most one of 2 is true
• strong alternative - exactly one is true
• ex. Fredholm alternative
• ex. Farkas’s lamma
1. $\exists x : Ax \leq 0, c^Tx < 0$
2. $\exists y : y \geq 0, A^Ty + c = 0$

# approx + fitting (boyd 6)

## norm approx problem

•  minimize $Ax-b$
•  ex. weighted norm approx. min W(Ax-b)
•  ex. least squares min Ax-b $_2^2$
•  ex. chebyshev approx norm min Ax-b $_\infty$
• ex. penalty function approx problem: $min : \phi(r_1) + … + \phi(r_m)\s.t. : r=Ax-b$

## least norm problem

•  min $x \s.t. : Ax=b$ ~ min $x_0+ Zu$, Z cols basis for N(A)

## regularized approximation

•  min $Ax-b + \gamma x$
•  min $Ax-b ^2 + \gamma x ^2$
•  Tikhonov: $min : Ax-b _2^2 + \gamma x _2^2$
• examples
•  ex. regularize w/ Dx
• ex. lasso
• ex. total variation

## robust approximation

• $A = \bar{A} + U$ ~ random w/ mean 0
1.  stochastic robust approx problem: $min : E Ax-b$
2.  (worst-case) robust approx prob: $min : sup Ax-b : A \in \mathcal{A}$

## function fitting

• $f(u) = x_1 f_1 (u) + …. + x_n f_n (u)$ ~ $f_i$ are basis funcs, $x_i$ are coefficients
• sparse descriptions + basis pursuit
• interpolation

# unconstrained minimization (boyd 9)

## unconstrained problems

• $x^* = \text{argmin} : f(x) \implies \nabla f(x^*) = 0$
• examples
• ex. quadratic: $\min : 1/2 x^TPX + q^Tx + r$
• solved w/ $Px^* + q = 0$, if $P \succeq 0$, unique soln $-P^{-1}q$
• ex. unconstrained geometric program
• ex. analytic center of linear inequalities
•  $\min : f(x) = -\sum : \log (b_i - a_i^Tx)$ where dom f = ${x a_i^Tx< b_i, i = 1:m}$
• 3 definitions of convexity
• $0 \leq \theta \leq 1$
• $f(\theta x_1 + (1 - \theta) x_2) \leq \theta f(x_1) + (1 - \theta) f(x_2)$
• $\nabla^2 f(x) \succeq 0$
• $f(x_2) \geq f(x_1) + \nabla f(x_1)^T (x_2 - x_1)$
• $\color{red}0 \preceq \color{green}{\underset{\text{strong convexity}}{mI}} \preceq \nabla^2 \color{cornflowerblue}{f(x)} \preceq \underset{\text{smoothness}}{MI}$
• $\kappa = M/m$ bounds condition number of $\nabla^2 f = \frac{\lambda_{\max}(\nabla^2 f)}{\lambda_{\min}(\nabla^2 f)}$
• strongly convex: $\nabla^2 f(x) \succeq mI$
•  $\implies f(x_2) \geq f(x_1) + \nabla f(x_1)^T(x_2-x_1) + m/2 x_2-x_1 _2^2$
•  minimizing yields $p^* \geq f(x) - 1/(2m) \nabla f(x) _2^2$
• if the gradient of f at x is small enough, then the difference between f(x) and p⋆ is small
• smooth: $\exists : M, : \nabla^2f(x) \preceq MI$
•  $\implies f(y) \leq f(x) + \nabla f(x)^T(y-x) + M/2 y-x _2^2$
• cond(C) = $W_{\max}^2 / W_{\min}^2$
•  width of convex set $C \subset \mathbb{R}^n$ in direction q with $q _2=1$
• $W(C, q) = \underset{z \in C}{\sup} : q^Tz - \underset{z \in C}{\inf} : q^Tz$
•  alpha-level subset: $C_\alpha = {x f(x) \leq \alpha}$

## descent methods

• update rule $x = x + t \Delta x$
• exact line search: $t = \underset{s \geq 0}{\text{argmin}} :f(x+s \Delta x)$
• backtracking line search
• given a descent direction $\Delta x \text{ for } f, x \in dom : f, \alpha \in (0, 0.5), \beta \in (0, 1)$
• t:=1, $\alpha \in (0, 0.5), \beta \in (0, 1)$
• while $f(x + t \Delta x) > f(x) + \alpha t \nabla f(x)^T \Delta x$
• $t *= \beta$
• ## gd method

• convergence
• can bound number of iterations required to be less than $\epsilon$
• examples
• a quadratic problem in $R^2$
• non-quadratic problem in $R^2$
• a problem in $R^{100}$
• gradient method and condition number
• conclusions
• gd often exhibits approximately linear convergence
• convergence rate depends greatly on $cond (\nabla^2 f(x))$ or sublevel sets

## steepest descent method

• examples
• euclidean norm: $\Delta x_{sd} = - \nabla f(x)$
•  quadratic norm $z _P = (z^TPz)^{1/2} = P^{1/2}z 2$ where $P \in S{++}^n$
• $\Delta x_{sd} = -P^{-1} \nabla f(x)$
• $\ell_1$ norm: $\Delta_{sd} = -\frac{\partial f(x)}{\partial x_i} e_i$

## newton’s method

• Newton step $\Delta x_{nt} = - \nabla^2 f(x)^{-1} \nabla f(x)$
• PSD $\implies \nabla f(x)^T \Delta x_{nt} = - \nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x) < 0$
• Newton’s method
1. compute the newton step $\Delta x_{nt}$ and decrement $\lambda^2 = \nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x)$
2. stopping criterion: quit if $\lambda^2 / 2 \leq \epsilon$
3. line search: choose step size t w/ backtracking line search
4. update: $x += t \Delta x_{nt}$

# basic algorithms

• types: batch (have full data) vs online
• gradient - vector that points to direction of maximum increase
• at every step, subtract gradient multiplied by learning rate: $x_k = x_{k-1} - \alpha \nabla_x F(x_{k-1})$
• alpha = 0.05 seems to work
• $J(\theta) = 1/2 (\theta ^T X^T X \theta - 2 \theta^T X^T y + y^T y)$
• $\nabla_\theta J(\theta) = X^T X \theta - X^T Y$
• = $\sum_i x_i (x_i^T - y_i)$
• this represents residuals * examples
• don’t use all training examples - approximates gradient
• single-sample
• mini-batch (usually better in offline case)
• coordinate-descent algorithm
• online algorithm - update theta while training data is changing
• when to stop?
• predetermined number of iterations
• stop when improvement drops below a threshold
• each pass of the whole data = 1 epoch
• benefits
1. less prone to getting stuck to shallow local minima
2. don’t need huge ram
3. faster
3. newton’s method for optimization
• second-order optimization - requires 1st & 2nd derivatives
• $\theta_{k+1} = \theta_k - H_K^{-1} g_k$
• update with inverse of Hessian as alpha - this is an approximation to a taylor series
• finding inverse of Hessian can be hard / expensive
4. ADMM - alternating direction method of multipliers (ADMM) is an algorithm that solves convex optimization problems by breaking them into smaller pieces, each of which are then easier to handle

# expectation maximization - j 11

• method to maximize likelihood on model with observed X and hidden Z
1. expectation step - values of unobserved latent variables are filled in
• calculates prob of latent variables given observed variables and current param values
2. maximization step - parameters are adjusted based on filled-in variables
• goal: maximize complete log-likelihood, but don’t know z
•  expected complete log-likelihood $E_{p’}[l(\theta; x,z)] = \sum_z p’(z x,\theta) \cdot \log : p(x,z \theta)$
• p’ distribution is assignment to z vars
•  deriving auxilary function $\mathcal L(q, \theta, x) = \sum_z p’(z x) \log \frac{p(x,z \theta)}{p’(z x)}$ - lower bound for the log likelihood
•  \begin{align} l(\theta; x) &= \log : p(x \theta) & \text{incomplete log-likelihood} \&= \log \sum_z p(x,z \theta) &\text{complete log-likelihood}\&= \log\sum_z p’(z x) \frac{p(x,z \theta)}{p’(z x)} &\text{multiplying by 1} \ &\geq \sum_z p’(z x) \log \frac{p(x,z \theta)}{p’(z x)} &\text{Jensen’s inequality}\&\triangleq \mathcal L (p’, \theta) \end{align}
• this removes dependence on z
• steps
•  E: $p’(z x, \theta) = \underset{p’}{\text{argmax}}: \mathcal L(p’,\theta, x)$
• M: $\theta = \underset{\theta}{\text{argmax}} : \mathcal L(p’, \theta, x)$
• equivalent to maximizing expected complete log-likelihood
• stochastically converges to local minimum
• alternatively, can look at kl-divergences

# misc

## nn optimization

### why is it hard?

• plateaus
• winding canyons
• cliffs
• local maxima to dodge
• saddle points (local max and local min)
• most popular
• sgd
• sgd + nesterov momentum
• rmsprop - (ignore) per-parameter learning rates that are adapted based on the average of recent magnitudes of the gradients for the weight (e.g. how quickly it is changing)
• keep track of per-parameter learning rate (based on first moment of gradients tracked) and per-parameter second moment (based on variance of gradients tracked)
• alpha - learning rate
• beta1 - exponential decay rate for first moment estimate
• default 0.9
• beta2 - exponential decay rate for 2nd moment estimates (should be higher when gradients sparser)
• default 0.999
• epsilon - small number to prevent division by zero
• default 1e-8 - usually requires tuning (ex. inception requires 1e-1) visualization
• requires low dims
• goodfellow 2015 “Qualitatively characterizing neural network optimization problems” plots loss on line from starting point to ending point
• could do PCA on params

### complicated is simpler

• ex. $x^3 \sin(x)$ is simpler than just $x$ on the domain [−0.01, 0.01]
• dropout is like ridge

## mixed integer programming (mip)

Notes from this overview

• ex: minimize $c^{\top} x$ s.t.

• $\mathrm{A} \mathrm{x}=\mathrm{b}$ (linear constraints)
• $l\leq x \leq u$ (bound constraints)
• some or all $x_j$ must take integer values (integrality constraints)
• solving: branch-and-bound

• integer constraints make this difficult so start by solving the relaxation without integer constraints

• pick one of the variables $x_b$ that was not integer to be our branching variable

• say it’s value was 5.7, now solve 2 MIPS, one with constraint $x_b \leq 5$ an $x_b \geq 6$
• return better solution of these two
• iterate by solving relaxation and then adding more branching constraints