Convex Set and Convex Function

by allenlu2007

本文參考 Stanford Professor Stephen Boyd (Boyd 是我最印象深刻的教授之一,among Thomas Lee, Cioffi) 的 MOOC CVX101.

Convex optimization 是顯學,應用在各式各樣的 optimization, machine learning (e.g. SVM), control, signal processing, etc.  最基本的 convex optimization 是基於 convex function f(x), 值域, 但同樣重要的是 x ∊ C (定義域是convex set).   Convex function 和 convex set 有任何關係嗎?

 

Convex function 定義

convex function 的定義其實就是 Jensen’s inequality 如下。幾何詮釋如下圖,f(x) 對應的值小於 hyperplane 的值。

NewImage

 

Convex set 定義

Convex optimization 的另一個重點是定義域也需要是 convex set!

Convex set 也有非常類似而且簡單的定義如下。幾何來說,任取 C 中兩點,所有 iine-of-sight 屬於 C!

 

NewImage

 

Why Convex Optimization = Convex set + Convex function?

原因很簡單。可以保証 local optimization = global optimization!!

如果沒有 convex function, optimization 可能會收歙在 local minimum.  

同樣沒有 convex set, optimization 可能也會卡在 local domain. 

 

 

以上都很直覺,但是否 convex set 和 convex function 有更緊密的關連?

Yes!   f is a convex function if and only if  epif  is a convex set. 

 

NewImage

 

Advertisements