===========
Theorem: (凸優化最佳解的集合為凸集)
令 S⊆Rn 為 凸集合 且 f:S→R 為 凸函數。令 S∗ 為所有極小點所成之集合亦即
S∗:={x∈S:f(x)≤f(y),∀y∈S} 則 S∗ 為凸集。
===========
S≤f(x0):={x∈S:f(x)≤f(x0)} 則不難驗證 S≤f(x0)=S∗。接著由下述 Lemma 可知 S∗ 為 convex。至此證明完畢。◻
===========
Lemma: 令 S⊆Rn為凸集,且 f:S→R 為凸函數。則對任意 α∈R, (lower) level set
S≤α:={x∈Rn:f(x)≤α} 為 凸集。
===========
f(λx1+(1−λ)x2)≤λf(x1)+(1−λ)f(x2)≤α故 λx1+(1−λ)x2∈S≤α,至此得證。◻
Remark:
對於 concave 函數我們仍有類似的結果記錄如下:
令 S⊆Rn 為凸集,且 f:S→R 為 concave 函數,則所有極大點所成的集合 S∗ 為 convex set。
沒有留言:
張貼留言