首先明确一下，很多凸优化问题都可以通过对偶问题来求解（SVM），线性规划只是一个特例。而且线性规划的对偶问题，可以用拉格朗日对偶理论导出。
为什么要进行对偶问题？
线性规划中，如果原始问题约束条件多，决策变量少，转换为对偶问题约束变少了，更好求解。
一个对偶问题的例子
| 产品 | 产品A1 | 产品A2 | 资源量 | 资源价格（影子价格） |
|---|---|---|---|---|
| 设备B1 | 5 | 10 | 40台 | y1 |
| 材料B2 | 2 | 0 | 8吨 | y2 |
| 材料B3 | 0 | 6 | 18吨 | y3 |
| 利润 | 4万元 | 6万元 | ||
| 产量 | x1 | x2 |
原问题
| Max：s = 4x1 + 6x2 |
|---|
| s.t. |
| 5x1 + 10x2 <= 40 |
| 2*x1 <= 8 |
| 6*x2 <= 18 |
| x1 >= 0 |
| x2 >= 0 |
对偶问题
| Min: w = 40y1 + 8y2 + 18*y3 |
|---|
| s.t. |
| 5y1 + 2y2 >= 4 |
| 10y1 + 6y3 >= 6 |
| y1 >= 0 |
| y2 >= 0 |
| y3 >= 0 |
对偶问题的经济学解释
原问题
- 直观解释：我自己加工，卖产品，得利润
- 约束：每个产品里的成本量，必须满足小于资源总量
- 目标：最大利润
对偶问题
- 直观解释：别人委托我加工，付给我资源使用费
- 约束：对于我来说，每个产品的资源使用费一定要高于该产品的利润，否则我会自己加工。
- 目标：获得更多的委托，间接表示为资源使用费最小。
（从需求供给上来考虑，我的资源使用费必须尽可能的小，才能接收到更多的委托，才能得到更多的资源使用费）
当委托加工的目标函数降到最小时，就等同于自己加工利润的最大值。所以说，上述对偶问题是原问题的上界。
影子价格？
对偶问题的解，相当于原规划中各种资源的价值，称为影子价格(Shadow price)，是对资源价值的一个估价。影子价格又称边际价值（Marginal Value）。
- 影子价格为0的资源，是系统中的长线资源，其供应的继续扩大（对偶问题目标函数的资源量，eg，40），并不能使系统的最大收益有所增加；
- 影子价格大于0的资源，则是系统中的短线资源，它的供应的扩大，将使系统中的最大收益增加。
影子价格不是资源的市场价格，也不是会计帐面上的数字，而是经济分析中使用的一个概念，是用以分析某种资源在系统中所起的作用。
拉格朗日对偶中的理论解释
原问题
| Max：s = 4x1 + 6x2 |
|---|
| s.t. |
| 5x1 + 10x2 <= 40 |
| 2*x1 <= 8 |
| 6*x2 <= 18 |
| x1 >= 0 |
| x2 >= 0 |
优化问题一般是求极小值，因此转化一下原问题的目标函数和约束，得到原问题1。
原问题1
| Min：s = -4x1 - 6x2 |
|---|
| s.t. |
| 5x1 + 10x2 - 40 <= 0 |
| 2*x1 - 8 <= 0 |
| 6*x2 - 18 <= 0 |
| -x1 <= 0 |
| -x2 <= 0 |
拉格朗日对偶问题，先min，后max
构造拉格朗日函数，
Max L = -4*x1-6*x2 + y1*(5*x1+10*x2-40) + y2*(2*x1-8) + y3*(6*x2-18) + y4*(-x1) + y5*(-x2)
分别对x1和x2求偏导，得到
-4 + 5y1 + 2y2 - y4 = 0
-6 + 10y1 + 6y3 – y5 = 0
Y1,y2,y3,y4,y5>=0
将y4和y5用y1,y2,y3替换得
y4 = -4 + 5y1 + 2y2 >= 0
y5 = -6 + 10y1 + 6y3 >=0
y1,y2,y3>=0
将L函数中的y4,y5用y1,y2,y3替换得
L = -4*x1-6*x2 + y1*(5*x1+10*x2-40) + y2*(2*x1-8) + y3*(6*x2-18) +
(-4+5*y1+2*y2)*(-x1) + (-6+10*y1+6*y3)*(-x2)
化简L，得
L=-40*y1-8*y2-18*y3
所以，拉格朗日对偶问题为，
| Max L = -40y1 - 8y2 - 18*y3 |
|---|
| s.t. |
| -4 + 5y1 + 2y2 >= 0 |
| -6 + 10y1 + 6y3 >=0 |
| y1,y2,y3 >= 0 |
整理一下，得线性规划对偶问题的形式
| Min: L = 40y1 + 8y2 + 18*y3 |
|---|
| s.t. |
| 5y1 + 2y2 >= 4 |
| 10y1 + 6y3 >= 6 |
| y1 >= 0 |
| y2 >= 0 |
| y3 >= 0 |
所以，可以看出线性规划的对偶问题，是拉格朗日对偶的一个特例。
