Loading [MathJax]/jax/output/CommonHTML/jax.js

12/08/2019

[凸分析] 凸優化最佳解所成之集合為凸集

在凸優化問題中,僅管凸性保證了任意局部最優解 (local minimizer) 就是 全局最優解 (global minimizer),但凸性並沒有保證所考慮的凸優化問題 一定 存在 最優極小解。下面的結果刻劃了凸優化最佳解的性質,常被用來檢驗最佳解的存在性,是個十分有用的結果。

===========
Theorem: (凸優化最佳解的集合為凸集)
SRn 為 凸集合 且 f:SR 為 凸函數。令 S 為所有極小點所成之集合亦即
S:={xS:f(x)f(y),yS}S 為凸集。
===========

Proof: 若 S= 則上述定理陳述自動成立。若 S,則存在 x0S。考慮 level set
Sf(x0):={xS:f(x)f(x0)} 則不難驗證 Sf(x0)=S。接著由下述 Lemma 可知 S 為 convex。至此證明完畢。


===========
Lemma: SRn為凸集,且 f:SR  為凸函數。則對任意 αR, (lower) level set
Sα:={xRn:f(x)α} 為 凸集。
===========

Proof: 若 level set Sα 為空集合或者單點集,則陳述自動成立。若不然,取 x1,x2Sα ,則 f(x1)αf(x2)α。我們要證明 convex combination of x1x2 仍落在 Sα 之中,亦即我們要證明 λx1+(1λ)x2Sα。為此,我們利用 f 的凸性,對任意 λ(0,1)
f(λx1+(1λ)x2)λf(x1)+(1λ)f(x2)αλx1+(1λ)x2Sα,至此得證。


Remark:
對於 concave 函數我們仍有類似的結果記錄如下:

SRn 為凸集,且 f:SR 為 concave 函數,則所有極大點所成的集合 S 為 convex set。


沒有留言:

張貼留言

[人工智慧] 本地端 DeepSeek R1 快速安裝:以 Macbook Pro M4 Chip為例

最近火熱的 DeepSeek R1 模型由於採用了 distill 技術,可以大幅降低計算成本,使得一般人有機會在自家筆電上跑性能逼近 Open AI ChatGPT o1的大語言模型。本文簡單介紹一步安裝在 Macbook Pro 的方法以及使用方法,以下測試採用 Macboo...