运筹学中对偶的问题

要想正确找出相对应的解，需严格安排对偶问题的转换方式，便可找出对偶问题的解。你举得例子X4自然对应的是y1 。所谓严格按照对偶问题的转换方式，就是指大小相换，条件与变量相换。系数矩阵A变为A转置。另外你的例子确实存在问题，在线性规划问题中，有三种变量分别为决策变量，松弛变量，人工变量。而基变量是不断变化的。 假设我理解你的题意应该是X1 X2 X3为决策变量。由此可见原问题有两个约束条件，故对偶问题有两个决策变量，且应该严格对应，第一个条件对应第一个变量y1,以此类推。而且对偶问题三个松弛变量。故对偶问题中有五个变量，而不是四个。具体对应如下，x4,x5的检验数对应的是对偶问题中的y1,y2。y3,y4,y5的检验数对应x1,x2,x3

本次记录：

原问题与对偶问题的关系；

强对偶与弱对偶；

引入KKT的原因；

定义一个原问题：

写出拉格朗日：

对偶函数 θ 产生了一个原问题最优值p 的一个下界，也就是，对于任意的λ>=0 以及 μ 来说，有：

好了，现在证明对偶问题是原问题的下界（假设 x 是在可行域内）：

也就是说我们找到了原问题最优值的一个下界。既然我们找到了一个下界，显然我们要找到它最好的下界。什么是最好的下界的？显然就是所有下界当中最大的那一个。所以需要对 θ 最大化，即：

以上的对偶性质被称作是弱对偶性。

首先引入一个对偶间隙： p - d ，也就是原问题的最优值与通过拉个郎日对偶函数获得的其最好（最大）的下界之差。

那么有没有可能在某种情况下，对偶间隙消失了呢？也就是说对偶问题的最优值与原问题的最优值相等了呢？

答案是，如果不等式约束 g(x) 满足严格的 < 0，那么可以使得 d = p 。

上面这个被称作 slater条件 ，可以证明凸优化问题，如果slater条件满足了，那么可以得到 d=p ，slater同时也是原问题可以等价为对偶问题的一个充分条件，该条件 确保了鞍点 的存在。

上述的对偶被称为强对偶。

如果对偶间隙消失，那么我们在证明 θ <= p 的过程就会变为：

上图中的等号 1 说明原问题的最优点 x 是使得 L 取得最小值的点

等号2 说明：

上式被称作互补条件，也就是说，只要一个不为0，另一个就必为0！

这个互补条件在SVM中起到很大的作用，当 g(x) < 0 时，x 是在可行域内的，这时不等式不起作用，此时 λ = 0。

而λ > 0使的点肯定是可行域边界的点，也就是g(x) = 0

也就是说，只有积极约束才有不为0的对偶变量，而这在支持向量机中有重要作用，原因：

svm的约束为：

那么哪些不等式约束对应着不为0的对偶变量呢？显然只有当 d(wx+b) = 1时，这个约束对应的对偶变量才可能不为0，而d(wx+b) = 1同时意味着样本点x是在支持向量上的，也就是说，只有支持向量上的点对应的拉格朗日乘子不为0。

slater条件确保了鞍点的存在，但是无法确保鞍点一定是最优解，所以KKT条件的作用便体现出来。

KKT条件的作用：KKT条件是确保鞍点是原函数最优解的充分条件

KKT可以概括为以下三个条件：

1）最优点x必须满足所有等式及不等式限制条件, 也就是说最优点必须是一个可行解

2）在最优点x, ∇f 必须是 ∇gi 和 ∇hj 的线性组合（α和β是拉格朗日乘子）

是的。根据对偶理论，对偶问题与原问题是互为对偶问题的，且对偶问题的目标函数恰好等于原问题最有目标函数，并且可以证明这一目标函数值也是最优的，反过来同样成立，假设对偶问题的最优解不唯一，那么其对偶问题（也就是原问题）的最优解也不唯一，这与原问题有唯一解矛盾。

因为原问题与对偶问题是相互对偶的，所以他们有一定的对应关系。在有限最优解的方面：原问题有有限最优解只能保证对偶问题有有有限最优解。原问题松弛变量的检验数的相反数就是对偶问题的最优解。

对偶理论(Duality theory)研究线性规划中原始问题与对偶问题之间关系的论。发展简在线性规划早期发展中最重要的发现是对偶问题，即每一个线性规划问题(称为原始问题)有一个与它对应的对偶线性规划问题（称为对偶问题）。

扩展资料：

对偶问题的最优解：从原始问题的最终单纯形表中（最优单纯形算子）可直接得到对偶问题的最优解。原始问题中松弛变量的检验数对应着对偶问题的解（符号相反）。

在用单纯形法时每一步迭代可得到原始问题的可行解x0和对偶问题的补充解y0且cx0=y0b，若x0不是原始问题的最优解，y0就不是对偶问题的可行解。最后一步迭代得到原始问题的最优解x和对偶问题的补充最优解y，且cx=yb。y是原始问题的影子价格。

对偶问题：每一个线性规划问题都伴随有另一个线性规划问题，称为对偶问题。原来的线性规划问题则称为原始线性规划问题，简称原始问题。对偶问题有许多重要的特征，它的变量能提供关于原始问题最优解的许多重要资料，有助于原始问题的求解和分析。

参考资料来源：百度百科-对偶理论

对偶（min型）变量的最优解等于原问题松弛变量检验数的绝对值；对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值；原问题和对偶问题是相互对偶的。

原问题指的是原本的问题，而不是延伸出来的所有问题。

对偶问题是实质相同但从不同角度提出不同提法的一对问题。

如果 原问题 有最优解 , 对偶问题也 有最优解 ;

如果 原问题 有 无界解 , 对偶问题 无可行解 ;

如果 原问题 无可行解 , 对偶问题 无法判断 ;

希望我的回答能帮到你。

以上就是关于运筹学中对偶的问题全部的内容，包括:运筹学中对偶的问题、SVM原问题与对偶问题、线性规划中，如何已知原问题的最优解，直接写出对偶问题的最优解等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！