跳到主要內容

發表文章

目前顯示的是 六月, 2018的文章

[最佳化] 對原最佳化問題的解是否能"回收"使用到新最佳化問題

令 $J: \mathbb{R}^n \to \mathbb{R}$ ,考慮以下最佳化問題
\[
\min_{x_1,x_2,...x_n} J(x_1,x_2,...x_n)  := J(x_1^*,x_2^*,...,x_n^*)
\]上述 $x_i^*$ 表示最佳解。現在考慮新的目標函數 $G: \mathbb{R}^n \to \mathbb{R}$ 為 上述的 $J:\mathbb{R}^n \to \mathbb{R}$ 額外加上新的函數 $F: \mathbb{R}^n \to \mathbb{R}$,亦即
\[
 G(x_1,x_2,...,x_n) :=J(x_1,x_2,...,x_n) + F(x_1,x_2,...,x_n)
\]我們想問前述獲得的最佳解 $x_1^*,x_2^*,.., x_n^*$ 是否仍然對新的目標函數成立?換句話說,是否能夠 "回收" 之前已經算好的最佳解  $ x_i^*$ 用在新的目標函數 $G$ 上呢。答案是否定的。考慮以下一個簡單的反例

Example:
對 $i=1,2,$,令 $x_i \in [-1,1]$並且將所有符合此條件的 $x_i$ 所成之集合記作 $\mathcal{X}$。現在考慮目標函數 $J(x_1,x_2) := x_1^2+x_2^2$ 並且 我們要求
$$
\min_{x_1,x_2 \in \mathcal{X}} J(x_1,x_2) =  \min_{x_1,x_2 \in \mathcal{X}}x_1^2+x_2^2
$$則最佳解不難發現為 $x_1^*=x_2^*=0$。現在我們考慮新的目標函數,將其記作
$$
G(x_1,x_2) :=J(x_1,x_2) + x_2
$$亦即 $G$ 為舊的目標函數 $J$ 額外加上 線性函數 $x_2 $。我們要求
$$
\min_{x_1,x_2 \in \mathcal{X}} G(x_1,x_2) = \min_{x_1,x_2 \in \mathcal{X}} x_1^2+x_2^2 + x_2
$$其最佳解變成 $x_1^* = 0$ 但 $x_2^* = -1/2 \;\;\; ( \neq 0)$。亦即舊的最佳解不能被"回收"使用。

Comments:
1. 上述謬誤偶爾能在文獻中…