Optimization - Basics

1. Matrix Derivatives

Objective Function $f(x):{\mathbb{R}}^n\to \mathbb{R}$$f(x):\R^n\to\R$

• 1st-Order Gradient

  一般规定为一个 Row Vector

  $$\frac{\partial f}{\partial x}\in {\mathbb{R}}^{1\times n}$$

  It is a linear operator mapping $\mathrm{\Delta }x$$\Delta x$ into $\mathrm{\Delta }f$$\Delta f$

  $$f(x+\mathrm{\Delta }x)=f(x)+\frac{\partial f}{\partial x}\mathrm{\Delta }x$$

  在敲代码的时候，这样的规定能让 dimension 对得上，省略很多麻烦

  不过在写公式的时候用另一种 Notation 会更方便

  $$\begin{array}{c}\mathbf{\nabla }f(x)=(\frac{\partial f}{\partial x}{)}^T=\left(\begin{array}{c}\frac{\partial f}{\partial x_1}\\ \frac{\partial f}{\partial x_2}\\ ⋮\\ \frac{\partial f}{\partial x_n}\end{array}\right)\in {\mathbb{R}}^n\end{array}$$

• 2nd-Order Gradient

  即 Hessian

  $$\begin{array}{c}{\mathbf{\nabla }}^{2}f(x)=\frac{\partial }{\partial x}\mathbf{\nabla }f(x)=\frac{{\partial }^{2}f}{\partial x^2}=\left(\begin{array}{cccc}\frac{{\partial }^{2}f}{\partial x_1^2}& \frac{{\partial }^{2}f}{\partial x_1{x}_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_1{x}_n}\\ \frac{{\partial }^{2}f}{\partial x_2{x}_1}& \frac{{\partial }^{2}f}{\partial x_2^2}& \cdots & \frac{{\partial }^{2}f}{\partial x_2{x}_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_n{x}_1}& \frac{{\partial }^{2}f}{\partial x_n{x}_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right)\in {\mathbb{R}}^{n\times n}\end{array}$$

  Hessian 是 Symmetric Matrix，所以 Notation 无所谓，dimension 总是对的

  可以用它对 objective function 进行 2nd-Order Taylor Expansion

  $$f(x+\mathrm{\Delta }x)=f(x)+\frac{\partial f}{\partial x}\mathrm{\Delta }x+\frac{1}{2}(\mathrm{\Delta }x{)}^T\frac{{\partial }^{2}f}{\partial x^2}(\mathrm{\Delta }x)$$

Objective Function $g(y):{\mathbb{R}}^n\to {\mathbb{R}}^m$$g(y):\R^n\to\R^m$

• 1st-Order Gradient

  一般规定为 $n\times m$$n\times m$ 的 Vector

  $$\begin{array}{c}\mathbf{\nabla }g(y)=\frac{\partial g}{\partial y}=\left(\begin{array}{cccc}\frac{\partial g_1}{\partial y_1}& \frac{\partial g_2}{\partial y_1}& \cdots & \frac{\partial g_m}{\partial y_1}\\ \frac{\partial g_1}{\partial y_2}& \frac{\partial g_2}{\partial y_2}& \cdots & \frac{\partial g_m}{\partial y_2}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial g_1}{\partial y_n}& \frac{\partial g_2}{\partial y_n}& \cdots & \frac{\partial g_m}{\partial y_n}\end{array}\right)\in {\mathbb{R}}^{n\times m}\end{array}$$

  其 transpose 也叫 Jacobian

  $$J(y)=(\frac{\partial g}{\partial y}{)}^T\in {\mathbb{R}}^{m\times n}$$

Notes:

对以上两种 Objective Function 一阶导之规定，即 $\frac{\partial f}{\partial x}\in {\mathbb{R}}^{1\times n}$$\frac{\partial f}{\partial x} \in \R^{1\times n}$ 和 $\frac{\partial g}{\partial y}\in {\mathbb{R}}^{n\times m}$$\frac{\partial g}{\partial y} \in \R^{n\times m}$，是为了让 Chain Rule 能 work

$$f(g(y+\mathrm{\Delta }y))=f(g(y))+{\frac{\partial f}{\partial x}\phantom{\int }|}_{x=g(y)}{\frac{\partial g}{\partial y}\phantom{\int }|}_{y=y}\mathrm{\Delta }y$$

 

 

 

2. Root Finding

Given $f(x)$$f(x)$, find $x^{\ast }$$x^*$ such that $f(x^{\ast })=0$$f(x^*)=0$，其实就是找到 Equilibrium of Dynamics

• In Continuous Time

  使导数为 0 即可

  $${\mathbf{\nabla }f(x)\phantom{\int }|}_{x=x^{\ast }}=0$$

• In Discrete Time

  Discrete-Time Dynamics 的一般形式是 $x_{k+1}=f(x_k)$$x_{k+1} = f(x_k)$，找到其 fixed point 即可

  $$x^{\ast }=f(x^{\ast })$$

 

 

2.1 Newton's Method

用于 root finding 的最基础的一种算法

 

2.1.1 Algorithm

假设 objective function $f(x)$$f(x)$ 是 smooth 的，root $x^{\ast }$$x^*$ 位于 $\mathbf{\nabla }f(x^{\ast })=0$$\grad f(x^*)=0$，那么

1. Fit a linear approximation to $f(x)$$f(x)$

   $$\begin{array}{rl}\mathbf{\nabla }f(x+\mathrm{\Delta }x)& =\mathbf{\nabla }f(x)+\frac{\partial }{\partial x}\mathbf{\nabla }f(x)\cdot \mathrm{\Delta }x\\ & =\mathbf{\nabla }f(x)+\frac{\partial }{\partial x}[(\mathbf{\nabla }f(x){)}^T\cdot \mathrm{\Delta }x]\end{array}$$

2. Solve for $\mathrm{\Delta }x$$\Delta x$

   $$\mathrm{\Delta }x=\underset{\text{"descent"}}{\underbrace{-}}\stackrel{\text{"learning rate"}}{\overbrace{({\mathbf{\nabla }}^{2}f(x){)}^{-1}}}\underset{\text{"gradient"}}{\underbrace{\mathbf{\nabla }f(x)}}$$

   • ${\mathbf{\nabla }}^{2}f(x)>0⟶$$\grad^2 f(x) > 0 \longrightarrow$ "Descent" (minimization)

   • ${\mathbf{\nabla }}^{2}f(x)<0⟶$$\grad^2 f(x) < 0 \longrightarrow$ "Ascent" (maximization)

3. Update $x$$x$

   $$x\leftarrow x+\mathrm{\Delta }x$$

4. Repeat Step 1-3 until convergence

Notes:

基于现有的条件，Newton's Method only converges to the closest Fixed Point to the Initial Guess

鬼知道找到的 Root 是 {global / local} {maximum / minimum} 还是 saddle point，反正你自己看着办吧

 

2.1.2 Regularization

在 2.1.1 的 step 2 中提及了保证 descent 的条件

If ${\mathbf{\nabla }}^{2}f(x)>0$$\grad^2 f(x) > 0$ everywhere $\mathrm{\forall }x$$\forall x$ (which means $f(x)$$f(x)$ is strongly convex), then we can always find a minimum with Newton's Method

但很遗憾的是，现实中 it is usually not the case for nonlinear problems

解决方案即 regularization，做法如下

1. Pick a scalar hyperparameter $\beta$$\beta$

2. Check if Hessian $H={\mathbf{\nabla }}^{2}f(x)$$H = \grad^2 f(x)$ is Positive Definite

   $$H>0$$

3. if not, then

   $$H\leftarrow H+\beta I$$

4. Repeat step 2-3 until $H$$H$ is Positive Definite

• It guarantees descent

• Also called "Damped Newton"

 

 

2.2 Line Search (Back Tracking)

Newton's Method 的 step size 并不是所谓 adaptive 的，到最后总会有那么一步会 overshoots the minimum

这个方法算是给 Newton's Method 打的补丁，to make sure step agrees with linearization within some tolerance

Specifically, we check $f(x+\mathrm{\Delta }x)$$f(x + \Delta x)$ and "back track" until we get a good reduction value

Let $p$$p$ be the Direction of Descent

所以首先一定有 $(\mathbf{\nabla }f(x){)}^{T}p<0$$(\grad f(x))^Tp < 0$，请记住这一点

There are several effective strategies

 

2.2.1 Armijo Condition

or Sufficient Decrease Condition

1. Set

   • percentage of reduction $\alpha =1$$\alpha = 1$

   • tolerance $c_1$$c_1$

   • $\alpha$$\alpha$'s reduction rate $b\in (0,1)$$b \in (0, 1)$

2. Check if

   $$f(x+\alpha p)\le f(x)+c_1\alpha (\mathbf{\nabla }f(x){)}^{T}p$$

   Here, $\mathrm{\Delta }x=\alpha p$$\Delta x = \alpha p$

3. Update

   $$\alpha \leftarrow b\alpha$$

   and repeat Step 2-3 until Step 2 is fulfilled

一般各项参数取值为

下图中 acceptable 的部分表示这个 step length 没有 overshoot the minimum

不 acceptable 的部分显然是 overshoot 了，即斜虚线比函数本身还要小

 

2.2.2 Curvature Condition

从 2.2.1 的图中不难看出只要 $\alpha$$\alpha$ 够小就能满足 Armijo Condition

但这会导致 descent 的量不够大，而 curvature condition 能防止 $\alpha$$\alpha$ 过小

where

这个 condition 的要求可以理解为 "The slope at the next iterate is 'less negative' than the current slope"

所以如果这个条件被满足，已知 $(\mathbf{\nabla }f(x){)}^{T}p<0$$(\grad f(x))^Tp < 0$，slope 有两种情况

1. 比 current slope 更接近 0，函数值更接近 minimum

2. 直接是 positive slope，函数值越过 minimum

还有一种更加严格的 curvature condition 版本

用绝对值限制之后，就只有把 slope 往 0 上靠这一个选择了

 

2.2.3 Wolfe Conditions

Wolfe Conditions 就是把 Armijo Condition 和 Curvature Condition 组合在一起

• 弱 Wolfe Condition

  $$\begin{array}{rl}f(x+\alpha p)& \le f(x)+c_1\alpha (\mathbf{\nabla }f(x){)}^{T}p\\ \\ (\mathbf{\nabla }f(x+\alpha p){)}^{T}p& \ge c_2(\mathbf{\nabla }f(x){)}^{T}p\end{array}$$

• 强 Wolfe Condition

  $$\begin{array}{rl}f(x+\alpha p)& \le f(x)+c_1\alpha (\mathbf{\nabla }f(x){)}^{T}p\\ \\ |(\mathbf{\nabla }f(x+\alpha p){)}^{T}p|& \le |c_2(\mathbf{\nabla }f(x){)}^{T}p|\end{array}$$

 

 

 

3. Unconstrained Minimization

Find the minimum $x^{\ast }$$x^*$ of the Objective Function $f(x)$$f(x)$

 

 

3.1 Hessian 正定之必要性

若以 2.1 中的 Newton's Method 为基础算法进行 minimization，需要重点关注 Step 2，两侧同乘 $(\mathbf{\nabla }f(x){)}^T$$(\grad f(x))^T$

如果对 $f(x+\mathrm{\Delta }x)$$f(x + \Delta x)$ 进行 2nd-Order Taylor Expansion

若不能使 ${\mathbf{\nabla }}^{2}f(x)>0$$\grad^2f(x) >0$，即为 Positive Definite，那么显然在 $f(x+\mathrm{\Delta }x)$$f(x+\Delta x)$ 的过程中无法保证 $f(x)$$f(x)$ 的数值会下降，即达到 Minimum 而不是 Maximum 或者 Saddle Point 这种奇奇怪怪的地方

 

 

3.2 Local Minimum 判断标准

Assume $x^{\ast }$$x^*$ is a Local Minimizer and $f(x)$$f(x)$ is continuously differentiable, then

• 1st-Order Necessary Condition

  $$\mathbf{\nabla }f(x^{\ast })=0$$

• 2nd-Order Necessary Condition

  $${\mathbf{\nabla }}^{2}f(x^{\ast })\ge 0$$

• 2nd-Order Sufficient Condition

  If this condition is fulfilled, then $x^{\ast }$$x^*$ is a Strict Local Minimizer of $f(x)$$f(x)$

  $${\mathbf{\nabla }}^{2}f(x^{\ast })>0$$

 

 

 

4. Constrained Minimization

Find the minimum $x^{\ast }$$x^*$ of the Objective Function $f(x)$$f(x)$ subjected to the following constraints

我们最终要把一个 Constrained Problem 转化为一个 Unconstrained Problem 才能解它

 

 

4.1 Equality Constraints

where

• $f(x):{\mathbb{R}}^n\to \mathbb{R}$$f(x): \R^n\to\R$

• $g(x):{\mathbb{R}}^n\to {\mathbb{R}}^m$$g(x): \R^n\to\R^m$

The 1st-Order Necessary Condition to find the minimum is

1. $\mathbf{\nabla }f(x)=0$$\grad f(x) = 0$

   只要在 FREE directions 上满足即可

2. $g(x)=0$$g(x) = 0$

   Equality Constraint 规定了哪里是 $\mathbf{\nabla }f(x)$$\grad f(x)$ 的 Free Direction

 

4.1.1 Lagrangian

Lagrangian 能把上述的 Constrained Problem 转化为 Unconstrained Problem，以下是推导过程

• 关于 Equality Constraint

  "What is Free Direction?" 简而言之，当 $x$$x$ 作了一个很小的位移 $\mathrm{\Delta }x$$\Delta x$ 后仍能满足 $g(x)=0$$g(x)=0$，那这个位移就在 "Free Direction" 上，即

  $$g(x+\mathrm{\Delta }x)=0$$

  进行 1st-Order Taylor Expansion 得到

  $$g(x+\mathrm{\Delta }x)=g(x)+(\mathbf{\nabla }g(x){)}^T\mathrm{\Delta }x$$

  Notes: $\mathbf{\nabla }g(x)$$\grad g(x)$ 是个 Jacobian

  由于 $g(x)=0$$g(x) = 0$，所以需要满足的其实是

  $$(\mathbf{\nabla }g(x){)}^T\mathrm{\Delta }x=0$$

• 关于 Objective Function

  同样，假设 $x$$x$ 在 Objective Function 上做了一个很小的位移 $\mathrm{\Delta }x$$\Delta x$，进行 1st-Order Taylor Expansion 得到

  $$f(x+\mathrm{\Delta }x)=f(x)+(\mathbf{\nabla }f(x){)}^T\mathrm{\Delta }x$$

  如果 $x$$x$ 尚不是 minimum $x^{\ast }$$x^*$，那么只要 $(\mathbf{\nabla }f(x){)}^T\mathrm{\Delta }x<0$$(\grad f(x))^T\Delta x < 0$，它就还能继续下降。同样，如果 $x$$x$ 往相反的方向位移，即 $-\mathrm{\Delta }x$$-\Delta x$，那么

  $$f(x-\mathrm{\Delta }x)=f(x)+(\mathbf{\nabla }f(x){)}^T(-\mathrm{\Delta }x)$$

  只要 $(\mathbf{\nabla }f(x){)}^T(-\mathrm{\Delta }x)<0$$(\grad f(x))^T(-\Delta x) < 0$，它也能继续下降

  Tangent Space 是对称的，我懒得解释了你不懂就自己搜搜看吧...

  反正就是，如果你不想让 $x$$x$ 下降，那么这个 $x$$x$ 就必须满足

  $$\begin{array}{rl}(\mathbf{\nabla }f(x){)}^T(\mathrm{\Delta }x)& \ge 0\\ (\mathbf{\nabla }f(x){)}^T(-\mathrm{\Delta }x)& \ge 0\end{array}$$

  也就是 $x=x^{\ast }$$x = x^*$ 要满足

  $$(\mathbf{\nabla }f(x){)}^T\mathrm{\Delta }x=0$$

• Summary

  从上述两个部分推出的结论是

  $$\begin{array}{rl}(\mathbf{\nabla }f(x){)}^T\mathrm{\Delta }x& =0\\ (\mathbf{\nabla }g(x){)}^T\mathrm{\Delta }x& =0\end{array}$$

  也就是 $\mathbf{\nabla }f(x)$$\grad f(x)$ 和 $\mathbf{\nabla }g(x)$$\grad g(x)$ 都需要 Normal 于移动方向 $\mathrm{\Delta }x$$\Delta x$，换而言之 $\mathbf{\nabla }f(x)$$\grad f(x)$ must be parallel to $\mathbf{\nabla }g(x)$$\grad g(x)$

  $$\mathbf{\nabla }f(x)\parallel \mathbf{\nabla }g(x)$$

  或者写成

  $$\mathbf{\nabla }f(x)+\mathbf{\nabla }g(x)\lambda =0$$

  [ Example ]

  你会看到 minimum 处的 objective function 和 equality constraint 的 gradient 是平行的

  $$\begin{array}{rl}\underset{x_1,x_2}{min}& x_1^2+x_2^2\\ \text{subject to}& (x_1-2{)}^2+x_2^2-1=0\end{array}$$

  

• Lagrangian

  Based on this gradient condition, we define Lagrangian as

  $$L(x,\lambda )=f(x)+{\lambda }^{T}g(x)$$

  such that the 1st-Order Necessary Condition becomes

  $$\mathbf{\nabla }L(x,\lambda )=0$$

  or equivalently

  $$\begin{array}{rl}{\mathbf{\nabla }}_{x}L(x,\lambda )& ={\mathbf{\nabla }}_{x}f(x)+{\mathbf{\nabla }}_{x}g(x)\lambda =0\\ {\mathbf{\nabla }}_{\lambda }L(x,\lambda )& =g(x)=0\end{array}$$

 

4.1.2 KKT System

KKT = Karush-Kuhn-Tucker，更常见的相关概念一般是 KKT Conditions，见 4.2.2

目的是用 Newtonian 去解能使 $\mathbf{\nabla }L(x,\lambda )=0$$\grad L(x, \lambda) = 0$ 的 $(x^{\ast },{\lambda }^{\ast })$$(x^*, \lambda^*)$。首先进行 1st-Order Taylor Expansion

since $\frac{{\partial }^{2}L}{\partial x\partial \lambda }=\frac{\partial g}{\partial x}$$\frac{\partial^2 L}{\partial x \partial \lambda} = \frac{\partial g}{\partial x}$ and $\frac{\partial g}{\partial \lambda }=0$$\frac{\partial g}{\partial \lambda} = 0$, then

重新组织一下

写成 Matrix Form，就是 KKT System

 

4.1.3 Gauss-Newton Method

该方法能简化 4.1.2 中提及的 $\frac{{\partial }^{2}L}{\partial x^2}$$\frac{\partial^2 L}{\partial x^2}$ 的运算，一般是用 1st-Order Taylor Expansion 来算

The 2nd term is expensive to compute because it is a bloody Tensor!

So we just drop it! 我们不要第二项辣！蛤！蛤！蛤！

Gauss-Newton 会导致 slightly slower convergence than Full-Newton

会要跑更多的 Iterations，但是单个 Iteration 变 cheaper 了

 

 

4.2 Inequality Constraints

 

4.2.1 LICQ

让 KKT Condition 成立的条件

• The Active Set $\mathcal{A}(x)$$\mathcal{A}(x)$ of any feasible point $x$$x$ consists of the equality constraints and the inequality constraints for which $h_i(x)=0$$h_i(x)=0$

• Given a point $x$$x$ and the Active Set of constraints $\mathcal{A}(x)$$\mathcal{A}(x)$, we say that the Linear Independence Constraint Qualification (LICQ) holds if the gradients of all the active constraints are linearly independent"

 

4.2.2 KKT Conditions

具有不等约束的优化问题的 1st-Order-Necessary Conditions = Karush-Kuhn-Tucker (KKT) Conditions

• 完全体 Lagrangian

  有 $\lambda$$\lambda$ 和 $\mu$$\mu$ 两个 Lagrangian Multiplier

  $$L(x,\lambda ,\mu )=f(x)+{\lambda }^{T}g(x)+{\mu }^{T}h(x)$$

  "Suppose that $x^{\ast }$$x^*$ is a local solution and that the LICQ holds at $x^{\ast }$$x^*$, and that $f(x)$$f(x)$, $g_i(x)$$g_i(x)$ and $h_i(x)$$h_i(x)$ are continuously differentiable, then there are Lagrange multipliers ${\lambda }^{\ast }$$\lambda^*$ and ${\mu }^{\ast }$$\mu^*$ such that the KKT Conditions are satisfied"

• KKT Conditions

  $$\begin{array}{rl}\text{Stationarity Condition}& {\mathbf{\nabla }}_{x}L(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast })=0\\ \\ \text{Primal Condition}& \{\begin{array}{l}g(x^{\ast })=0\\ h(x^{\ast })\le 0\end{array}\\ \\ \text{Dual Feasibility}& {\mu }_i\ge 0\mathrm{\forall }i\\ \\ \text{Complementary Slackness}& {\mu }_i{h}_i(x^{\ast })=0\mathrm{\forall }i\end{array}$$

前两个 condition 真没什么好说的，后两个比较 tricky

Complementary Slackness 在满足 Dual Feasibility 的情况下，其意义是 "Either ${\mu }_i^{\ast }=0$$\mu_i^* = 0$ or $h_i(x^{\ast })=0$$h_i(x^*)=0$"

在 evaluate 一个 inequality constraint 的时候，假设 $h(x)$$h(x)$ 是一个点，会有三种情况：

1. $h(x)<0$$h(x) < 0$ - feasible point（非边界），因此 constraint inactive (${\mu }_i=0$$\mu_i = 0$)

2. $h(x)=0$$h(x) = 0$ - feasible point（边界上），因此constraint active (${\mu }_i\ge 0$$\mu_i \geq 0$)

3. $h(x)>0$$h(x) > 0$ - infeasible point