0101-數學優化

一、知識點羅列
- 1.1 概述
- 1.2 應用
- 1.3 求解優化問題
二、已解決疑難點
- 2.1 為什么線性函式不滿足線性函式定義

一、知識點羅列

1.1 概述

優化問題：
1. \[minimize\quad f_0(x) \\ subject\,to\quad f_i(x) \leq b_i, \quad i=1\cdots,m \]
優化變數：\(x=(x_1,\cdots,x_m)\)
目標函式：\(f_0: R^n->R\)
約束（不等式）函式：\(f_i: R^n->R, \quad i=1,\cdots,m\)
約束邊界（約束上界）：常數 \(b_1,\cdots,b_m\)
最優解（解）\(x^*\)：所有滿足約束的向量中的向量 \(x^*\) 對應的目標函式的值最小
1. 另一種嚴格的說法：對于任意滿足約束 \(f_1(z) \leq b_1, \cdots, f_m(z) \leq b_m\) 的向量 \(z\)，有 \(f_0(z) \leq f_0(x^*)\)，則稱 \(x^*\) 為最優解（解）
線性函式：對于任意的 \(x,y \in R^n\) 和 \(\alpha , \beta \in R\)，并且有 \(f_i(\alpha x+\beta y) = \alpha f_i(x)+\beta f_i(y)\)
線性規劃問題：目標函式和約束函式都為線性函式的優化問題
非線性規劃問題：不是線性規劃就是非線性規劃
凸函式：對于任意 \(x,y\in R^n\)，任意的 \(\alpha,\beta\in R\) 且滿足 \(\alpha+\beta = 1,\,\alpha\geq 0,\,\beta\geq 0\) 時，下述不等式 \(f_i(\alpha x+\beta y) \leq \alpha f_i(x)+\beta f_i(y)\) 成立
凸優化問題：目標函式和約束函式都是凸函式的優化問題
線性規劃和凸函式：線性函式需要嚴格滿足凸函式的定義，因此線性規劃問題就是凸優化問題，也可以把凸優化看成是線性規劃的擴展

1.2 應用

優化問題：可以看成在向量空間 \(R^n\) 的一組備選接解中選擇最好的解
備選解：滿足約束條件 \(f_i(x) \leq b_i\) 的所有解
目標函式（成本函式）：目標函式 \(f_0(x)\) 可以看成是選擇 \(x\) 的成本（同理也可以認為 \(-f_0(x)\) 表示選擇 \(x\) 的效益或效用）
優化問題的解：滿足約束條件的所有備選解中成本最小（或效用最大）的解
投資組合優化（實體）：尋求一個最佳投資方案將資本在 \(n\) 種資產中進行分配，
1. 變數：變數 \(x_i\) 表示投在在第 \(i\) 種資產上的資本，則向量 \(x\in R^n\) 描述了資本在各個資產上的分配情況
2. 約束條件：
  1. 對投資預算的限制（總投資額的限制）
  2. 每一份投資額非負
  3. 期望收益大于最小可接受收益值
3. 目標函式（成本函式）：對總的風險值或投資回報方差的度量
4. 優化問題：在所有可能的投資組合中選擇滿足所有約束條件且風險最小的那個組合
資料擬合（實體）：在一族模型中選擇最符合觀測資料和先驗知識的模型
1. 變數：模型中的引數
2. 約束條件：先驗知識、引數限制（比如非負性）
3. 目標函式：觀測資料與估計模型的預測值之間的偏差、引數值的似然度和置信度的統計和估計
4. 優化問題：尋找合適的模型引數值，使其符合先驗知識，且與真實模型之間的偏差或預測值與觀測值之間的偏差最小（或統計意義上更加相似）
嵌入式實時優化的目的：嵌入式應用中，在沒有（或者極少）人為干預的條件下實時做出選擇甚至實時執行，
1. 缺點：優化結果必須非常可靠，并且必須在給定的時間（和存盤量）內解決問題

1.3 求解優化問題

優化問題的求解方法：以給定精度求解此類優化問題中的某一實體的演算法
求解優化問題的難度所取決的因素：比如目標函式和約束函式的形式、優化問題所包含的變數和約束個數、特殊的結構如稀疏結構（約束函式僅取決于為數不多的幾個變數）等，這些因素的復雜可能會導致優化問題難以解決
1. 目標函式和約束函式是光滑的（如多項式）：求解這中形式的問題，需要較長的時間或找不到節
高效解決某些優化問題的例子：最小二乘問題、線性規劃問題
凸優化問題的求解：凸優化問題，存在有效的求解演算法可以如最小二乘以及線性規劃問題一樣進行有效求解

二、已解決疑難點

2.1 為什么線性函式不滿足線性函式定義

以前認為機器學習中講的線性函式只是如普通的一次線性函式 \(y=kx+b\) 這樣的線性函式，
但是今天看到書中線性函式的定義：對于任意的 \(x,y \in R^n\) 和 \(\alpha , \beta \in R\)，并且有 \(f_i(\alpha x+\beta y) = \alpha f_i(x)+\beta f_i(y)\)，
通過 \(y=2x+3\) 這樣的的一次線性函式套用定義卻發現行不通，
首先自己發現從線性函式中的定義可以看出 \(x,y\) 指的是向量，我直接套用簡單的線性函式有點冒失，
然后經過百度驗證線性函式指的是空間的映射，或者可以說成是 \(f\) 對加法和乘法的一種剛性的保持，而不是簡單地直線，也就是說不能通過直觀感受去理解，
這樣就行得通了，也更明白了，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280898.html

標籤：其他

上一篇：邱岳的產品實戰,每個互聯網人必備的心得

下一篇：itest work 開源介面測驗&敏捷測驗管理平臺 9.5.0 GA_u4發布，優化及修復BUG