对偶问题推导

2020-04-13  本文已影响0人  Greyish

原问题和对偶问题

每一个线性优化问题，都可以表示为一个对偶问题。

原问题：\begin{equation} \begin{aligned} \text { Minimize } z &=\mathbf{c}^{\mathrm{T}} \mathbf{x} \\ \text {s.t.} & \mathbf{A x} \geq \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \end{aligned} \end{equation}          

对偶问题：\begin{equation} \begin{aligned} \text {Maxmize } z &=\mathbf{b}^{\mathbf{T}} \mathbf{y} \\ \text {s.t.} & \mathbf{A^{T} x} \leq \mathbf{c} \\ & \mathbf{y} \geq \mathbf{0} \end{aligned} \end{equation}

原问题不等式（Ax \geq b）的数量为对偶问题中变量的数量。

原问题变量(x \geq 0)的数量为对偶问题中不等式的数量。

如何推导？

原问题和对偶问题推导对应表

首先要明确上表中variable和constraints的区别，拿上面提到的例子来讲，原问题不等式（Ax \geq b）即为不等式约束，原问题变量（x \geq 0）即为变量的约束，两者都是约束，但是分为不等式约束和变量约束。

推导对偶问题时，首先对原问题的每一个不等式约束列写对偶问题的变量，然后对原问题的每一个变量列写对偶问题的不等式约束，该约束的正负号（或等号）与该变量相关。最后，对原问题的每一个非变量约束列写对偶问题的变量约束，该约束的正负号（或等号）与该约束相关。

上一篇下一篇

猜你喜欢

热点阅读