全部笔记的汇总贴（视频也有传送门）：中科大-凸优化
一、凸函数的定义（复习）
-
f : R n → R f:\R^n\rightarrow\R f:Rn→R 为凸函数 ⇔ d o m f \Leftrightarrow dom f ⇔domf为凸集
∀ x , y ∈ d o m f , 0 ≤ θ ≤ 1 有 f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) \forall x,y\in dom f,0\le\theta\le1有f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y) ∀x,y∈domf,0≤θ≤1有f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y) -
（高维情况） f : R n → R f:\R^n\rightarrow\R f:Rn→R为凸函数 ⇔ d o m f \Leftrightarrow dom f ⇔domf为凸集 ∀ x ∈ d o m f ∀ 方 向 向 量 v g ( t ) = f ( x + t v ) 为 凸 函 数 d o m g = { t ∣ x + t v ∈ d o m f } （ 降 维 ） \forall x\in dom f\;\;\;\forall 方向向量v\\g(t)=f(x+tv)为凸函数\;\;dom \;g=\{t|x+tv\in dom f\}（降维） ∀x∈domf∀方向向量vg(t)=f(x+tv)为凸函数domg={t∣x+tv∈domf}（降维）
-
f : R n → R f:\R^n\rightarrow\R f:Rn→R为凸函数 ⇔ d o m f \Leftrightarrow dom f ⇔domf为凸集
若 f f f可微， ∀ x , y ∈ d o m f , f ( y ) ≥ f ( x ) + ∇ f T ( x ) ( y − x ) \forall x,y\in dom f,f(y)\ge f(x)+\nabla f^T(x)(y-x) ∀x,y∈domf,f(y)≥f(x)+∇fT(x)(y−x)
（一维） f : R → R f:\R\rightarrow\R f:R→R可微， f f f为等价于 d o m f dom f domf为凸， ∀ x , y ∈ d o m f , f ( y ) ≥ f ( x ) + f ( x ) ( y − x ) \forall x,y\in dom f,f(y)\ge f(x)+f(x)(y-x) ∀x,y∈domf,f(y)≥f(x)+f(x)(y−x)
二、高维情况的证明
-
证明（ ⇒ \Rightarrow ⇒）
设 f f f为凸，考虑 x , y ∈ d o m f x,y\in dom f x,y∈domf
g ( t ) = f ( t y + ( 1 − t ) x ) = f ( x + t ( y − x ) ) g(t)=f(ty+(1-t)x)=f(x+t(y-x)) g(t)=f(ty+(1−t)x)=f(x+t(y−x))其中 t y + ( 1 − t ) x ty+(1-t)x ty+(1−t)x看作仿射组合
g ′ ( t ) = ∇ f T ( x + t ( y − x ) ) ( y − x ) g'(t)=\nabla f^T(x+t(y-x))(y-x) g′(t)=∇fT(x+t(y−x))(y−x)
g ( t 1 ) ≥ g ( t 2 ) + g ′ ( t 2 ) ( t 1 − t 2 ) g(t_1)\ge g(t_2)+g'(t_2)(t_1-t_2) g(t1)≥g(t2)+g′(t2)(t1−t2)对 ∀ t 1 , t 2 \forall t_1,t_2 ∀t1,t2成立
令 t 1 = 1 , t 2 = 0 t_1=1,t_2=0 t1=1,t2=0
得到 g ( 1 ) ≥ g ( 0 ) + g ′ ( 0 ) f ( y ) ≥ f ( x ) + ∇ f T ( y − x ) g(1)\ge g(0)+g'(0)\\f(y)\ge f(x)+\nabla f^T(y-x) g(1)≥g(0)+g′(0)f(y)≥f(x)+∇fT(y−x) -
证明（ ⇐ \Leftarrow ⇐）
∀ x , y ∈ d o m f , ∀ t t y + ( 1 − t ) x ∈ d o m f t ~ y + ( 1 − t ~ ) x ∈ d o m f \forall x,y\in dom f,\forall t\\ty+(1-t)x\in dom f\\\tilde{t}y+(1-\tilde{t})x\in dom f ∀x,y∈domf,∀tty+(1−t)x∈domft~y+(1−t~)x∈domf
f ( t y + ( 1 − t ) x ) ≥ f ( t ~ y + ( 1 − t ~ ) x ) + ∇ f T ( t ~ y + ( 1 − t ~ ) x ) ( t y + ( 1 − t ) x − t ~ y − ( 1 − t ~ ) x ) ≥ f ( t ~ y + ( 1 − t ~ ) x ) + ∇ f T ( t ~ y + ( 1 − t ~ ) x ) ( y − x ) ( t − t ~ ) f(ty+(1-t)x)\ge f(\tilde{t}y+(1-\tilde{t})x)+\nabla f^T(\tilde{t}y+(1-\tilde{t})x)(ty+(1-t)x-\tilde{t}y-(1-\tilde{t})x)\\\ge f(\tilde{t}y+(1-\tilde{t})x)+\nabla f^T(\tilde{t}y+(1-\tilde{t})x)(y-x)(t-\tilde{t}) f(ty+(1−t)x)≥f(t~y+(1−t~)x)+∇fT(t~y+(1−t~)x)(ty+(1−t)x−t~y−(1−t~)x)≥f(t~y+(1−t~)x)+∇fT(t~y+(1−t~)x)(y−x)(t−t~)
又已知 g ( t ) = f ( t y + ( 1 − t ) x ) g ( t ~ ) = f ( t ~ y + ( 1 − t ~ ) x ) g ′ ( t ~ ) = ∇ f T ( t ~ y + ( 1 − t ~ ) x ) ( y − x ) g(t)=f(ty+(1-t)x)\\g(\tilde{t})=f(\tilde{t}y+(1-\tilde{t})x)\\g'(\tilde t)=\nabla f^T(\tilde{t}y+(1-\tilde{t})x)(y-x) g(t)=f(ty+(1−t)x)g(t~)=f(t~y+(1−t~)x)g′(t~)=∇fT(t~y+(1−t~)x)(y−x)
所以 g ( t ) ≥ g ( t ~ ) + g ′ ( t ) ( t − t ~ ) f ( x ) 是 凸 函 数 g(t)\ge g(\tilde t)+g'(t)(t-\tilde t)\;\;\;\;\;\;\;\;f(x)是凸函数 g(t)≥g(t~)+g′(t)(t−t~)f(x)是凸函数