线性规划
Last updated
Was this helpful?
Last updated
Was this helpful?
食谱摄入营养的例子就是线性规划问题，类似的还有货物运输问题，不同的货物运输成本不同，求解最优的配送方式使总运输成本最低。
在最优化中，凸优化是最为常见而又最为重要的，因为凸优化有一个良好的性质：局部最优是全局最优，这个性质使得我们不需要去证明解是否会收敛到全局最优，或者如何避免局部最优。因此凸优化有广泛应用，在优化问题不是凸的时候，往往也会尝试将其变为凸问题便于求解。
对于一个集合中任意的两个点，这两个点组成的一个线段，如果这个线段上所有的点还位于该集合内，那么该集合就是凸集。
如果Hessian矩阵是半正定，即 H(x) 行列式 ≥ 0（用顺序主子式判断正定），是凸函数。反之，如果是半负定是凹函数。
注意：在几何形状上，与高等函数的凹凸性刚好相反，在高等数学上的凹函数在最优化这里变成了凸函数（可能是中外文化差异导致）。
目标函数和约束条件都是凸函数，就是凸规划。
费马定理给出的不带约束条件下的函数极值的必要条件。对于一些实际应用问题，一般还带有等式或者不等式约束条件。对于带等式约束的极值问题，经典的解决方案是拉格朗日乘数法。
就是高等数学多元函数微分学章节中用的拉格朗日乘数法。
可将有 d 个变量与 k 个约束条件的最优化问题转化为具有 d+k 个变量的无约束优化问题求解。
KKT条件是拉格朗日乘数法的推广，用于求解既带有等式约束，又带有不等式约束的函数极值。
KKT条件的求解有个前提条件，目标函数要是凸函数，且约束函数要是凹函数。
-g(x)是凸函数那么g(x)就是凹函数。
原问题是求极大，对偶问题就是求极小。原问题自变量是x的，对偶问题自变量就是y。
把原约束条件这一列的值变成对偶问题的系数，目标函数变成 => min z = 5y1 + 3y2 + 8y3
以写对偶问题第一个约束条件为例，把原约束条件x1这一列的系数对应转换为对偶问题第一个约束条件y1、y2、y3的系数，第一个约束条件 => y1 - y2 + 4y3 （此时约束条件的符合和右边的值还未定）
第二个约束条件，提取x2这一列的系数 => 2y1 + 5y2 + 7y3
第三个约束条件，提取x3这一列的系数 => 2y1 - y2 + 3y3
就是原问题中 x1，x2，x3 的系数，第一、二、三个约束条件右边的值为：5、6、3。
参照原问题x的取值约束来变换对偶问题约束条件的符号。
若原问题的x为无约束，对偶问题的y就写=；若原问题的目标函数求极大，约束条件的>、<与原问题x符号一致；若原问题的目标函数求极小，约束条件的>、<与原问题x符号相反。
如本问题x1无约束，则第一个约束条件符号为=；原问题的目标函数为求max，原问题第二个约束条件为≥，则对偶问题的第二个约束条件与该符号一致≥；原问题第三个约束条件为≤，则对偶问题的第三个约束条件也是≤。
此时，三个约束条件确定完毕：
y1 - y2 + 4y3 = 5
2y1 + 5y2 + 7y3 ≥ 6
2y1 - y2 + 3y3 ≤ 3
根据原约束条件的符号来定对偶问题y的取值约束。
这个变换规则与上一个相反，若原问题目标函数为求max，需要取相反的符号，若原问题的目标函数为求min，则取相同。
注：= 和 无约束都是互换。
如本例的变换，= 变成无约束，≥ 和 ≤ 互换。
变换结果即：y1无约束、y2 ≤ 0、y3 ≥ 0
，，
