Tag Archives: 凸優化

線性規劃 (四):單形法

本文的閱讀等級:中級 美國數學家丹齊格 (George Dantzig) 於1947年提出第一個有效的線性規劃算法──單形法,或稱單純形法 (simplex method),被後人譽為線性規劃之父。1946年丹齊格從加州大學柏克萊分校取得博士學位,次年他以數學顧問身分為美國空軍工作,經常他被要求解決一些與規劃相關的問題,譬如,如何配置預算、人力、飛機,及其他資源使達到最佳的成本效益。因為這些問題多少與經濟學有關,丹齊格跑去徵詢經濟學家科普斯曼 (Tjalling Koopmans,1975年諾貝爾經濟學獎得主)。丹齊格設想經濟學家應當早已發展出解線性規劃問題的技術,出乎意料之外,科普斯曼告訴他經濟學家也沒有線性規劃問題的系統化解法。於是在1947年的暑假,丹齊格決定自己著手尋找一個方法[1]。 Advertisements

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , | 9 Comments

凸優化──凸函數的最小化

本文的閱讀等級:中級 凸優化 (convex optimization) 是最佳化理論的一個分支。顧名思義,凸優化探討定義於一個凸集的凸函數最小化問題[1]。令 為凸集且 為凸函數。我們的目標要找出一個點 ,使得每一 滿足 。在最佳化理論中, 稱為可行域 (feasible set), 稱為目標函數, 稱為全域最佳解[2]。任一凸優化問題皆可表示為下列標準型: 其中 是凸函數, 是仿射函數,即 ,,。最小平方法與線性規劃是兩種常見的凸優化問題。令 為一個 階實矩陣, 為 維實向量, 為 維實向量。最小平方法是一個無約束 (unconstrained) 最佳化問題: 。 線性規劃標準型問題具有下列形式 (見“線性規劃 (一):標準型問題”): 本文介紹凸優化的一個重要性質:任一局部最佳解 (亦稱相對最佳解) 即為全域最佳解。所謂局部最佳解 是指存在 使得集合 中每一點 滿足 。

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , | 4 Comments