線性規劃對偶問題的理解
- 1.弱對偶
- 2.強對偶
曾在上課的時候多次遇到這個求一個問題的對偶形式，大多是硬套公式。記一次，忘一次。后來在蘇大佬的博客中看到了相關闡述，感覺豁然開朗，（可以記得就一些了）遂做筆記記之。原文詳見：https://spaces.ac.cn/archives/6280
在規劃和優化問題中，對偶形式 是一個非常重要的概念。一般情況下，對偶是一種變換，能夠將原問題轉換成一個等價的，看起來幾乎不一樣的新問題：
原問題?對偶變換對偶問題原問題\overset{\text{對偶變換}}{\longrightarrow}對偶問題原問題?對偶變換?對偶問題
線性規劃的一般目標式為：
min?x{cTx∣Ax=b,x≥0}(1)\min_x\{c^Tx|Ax=b, \ x\ge0\}\tag{1}xmin?{cTx∣Ax=b,?x≥0}(1)
在離散化情況下，x,c∈Rnx,c \in \mathbb{R^n}x,c∈Rn(行向量)，b∈Rmb \in \mathbb{R}^mb∈Rm, A∈Rm×nA\in \mathbb{R}^{m\times n}A∈Rm×n, Ax=bAx=bAx=b對應為m個等式約束。
1.弱對偶
假定式 (1)的最小值在x?x^*x?處取得，那么將有:
Ax?=bAx^*=bAx?=b
在其兩邊個乘上一個y∈Rmy\in\mathbb{R}^my∈Rm,使其變成一個標量：
yTAx=yTb(2)y^TAx=y^Tb\tag{2}yTAx=yTb(2)
假設（1）： yTA<cTy^TA < c^TyTA<cT，那么有(x非負)：
yTAx?<cTx?y^TAx^* < c^Tx^*yTAx?<cTx?
帶入(2)式，有(x在左邊不見了)：
yTb<cTx?y^Tb<c^Tx*yTb<cTx?
也就是說，在假設（1）的條件下，任意的yTby^TbyTb總是不大于(1)式，即使是最大的yTby^TbyTb也一樣：
max?y{yTb∣yTA<cT}≤min?x{cTx∣ATx=b,x≥0}(3)\max_y\{y^Tb | y^TA < c^T\} \le \min_x\{c^Tx|A^Tx = b, x\ge0\}\tag{3}ymax?{yTb∣yTA<cT}≤xmin?{cTx∣ATx=b,x≥0}(3)
即左邊的最大值 不大于 右邊的最小值。弱對偶只是找到了原來問題的下界，就是那個極大值。這個下界可以給優化問題提供一個近似目標 用于計算。
（在構造的過程中 原來的約束構了新的目標。將自變量消除了）
2.強對偶
強對偶形式是說(3)式中的等號成， 即：
max?y{yTb∣yTA<cT}=min?x{cTx∣ATx=b,x≥0}(3)\max_y\{y^Tb | y^TA < c^T\} = \min_x\{c^Tx|A^Tx = b, x\ge0\}\tag{3}ymax?{yTb∣yTA<cT}=xmin?{cTx∣ATx=b,x≥0}(3)
強對偶形式的推到需要用到Farkas引理，從等式約束中得出的得出的一個結論（矩陣A和向量b ）基本思路是max 可以任意程度的接近于min（詳見蘇大神的博文）。
結論：強弱對偶的變換形式是一致的，區別就在于等號是否能夠取得到
--運算符、表達式、條件結構(if, switch))
用法（參數詳細說明）)
--初識循環while，do-while)
--for循環,break,continue語句)
-leetcode-劍指offer6)
-leetcode-劍指offer1)
-leetcode-劍指offer2)