Convex Optimization

by allenlu2007

 

Convex optimisation 的問題

找到最小值

NewImage

 

NewImage

 

通常上述的 equations 沒有 close form, 需要用迭代法逐步找到最小值

NewImage 

事實上應該是 a * -delta f(x).  a is a step parameter.  

這個方法稱為 gradient descent method 或 steepest descent method.  梯度下降法或最陡下降法。理論上如果 a 很小,就是1st order 近似法的最佳解。但是收歛的時間會很久。如果 a 太大,在一些 local ellipsoid 很扁平的情況下會 overshoot, 同樣會有收歛慢的情況。

2nd order 近似法的最佳解就是牛頓法。最大的缺點是 Hessian 可能很難算。

從另一角度來看,也可以說 steepest descent method 是基於 unit circle (Euclidean norm) 的最佳解。但實際情況需要用 quadratic norm (ellipsoid).  另外也有 l1 norm.

這部份可以參考 Boyd 的 notes.

NewImage

Steepest descent   –>  Euclidean norm  –> 1st order approximation

NewImage

 

牛頓法原理

原始的牛頓法是用來解 ( f(x) = 0 )

NewImage

如上圖所示,可以得到:

NewImage 

以收歛速度而言,只是一階的近似。

其實牛頓法最 powerful 是在找最大或最小值。因為 f'(x) = 0.

x(n+1) = x(n) – f'(x(n)) / f”(x(n))   

以上圖求最小值來說,一階導數是直線。一次就可以找到最小值。

因此牛頓法找最大或最小值,是二階近似。

Two dimension or higher dimension, use Hessian to replace f” and gradient to replace f’.


 

 

 

 

 

Advertisements