几类常见优化问题的对偶问题

以下列举一些常见优化问题的对偶问题的形式

线性规划

考虑不等式形式的线性规划： $\begin{array}{ll} \operatorname{minimize} & c^{T} x \\ \text {subject to } & A x \preceq b \end{array}$ 它的对偶函数： $g(\lambda)=\inf_{x} L(x, \lambda)=-b^{T} \lambda+\inf _{x}\left(A^{T} \lambda+c\right)^{T} x$

从而：

$g(\lambda) =\left\{\begin{array}{ll} -b^{T} \lambda & A^{T} \lambda+c=0 \\ -\infty & \text { otherwise } \end{array}\right.$

所以它的对偶问题是： $\begin{array}{ll} \operatorname{maximize} & -b^{T} \lambda \\ \text {subject to } & A^T\lambda +c =0,\; \lambda \succeq 0. \end{array}$

以上是不等式形式的对偶。接下来考虑标准形式的线性规划： $\begin{array}{ll} \operatorname{minimize} & c^{T} x \\ \text {subject to } & A x=b \\ & x \succeq 0 \end{array}$ 对偶函数： $g(\lambda, \nu)=\left\{\begin{array}{ll} -b^{T} \nu & A^{T} \nu-\lambda+c=0 \\ -\infty & \text { otherwise } \end{array}\right.$

对偶问题：
$\begin{array}{ll} \text { maximize } & -b^{T} \nu \\ \text { subject to } & A^{T} \nu-\lambda+c =0 ,\; \lambda \succeq 0 \end{array}$
也可以写成： $\begin{array}{ll} \text { maximize } & b^{T} \nu \\ \text { subject to } & A^{T} \nu +\lambda=c,\; \lambda \succeq 0 \end{array}$

锥形式下线性规划标准形式的对偶。

也可以写成不等式形式： $\begin{array}{ll} \text { maximize } & -b^{T} \nu \\ \text { subject to } & A^{T} \nu+c \succeq 0 \end{array}$
线性规划的不等式形式的对偶问题的形式是等式，而线性规划的等式形式的对偶问题的形式可以写成不等式。

2

考虑问题：

$\begin{array}{ll} \operatorname{minimize} & x^{T} x \\ \text {subject to } & A x=b \end{array}$

拉格朗日函数： $L(x, \nu)=x^{T} x+\nu^{T}(A x-b)$

$\nabla_{x} L(x, \nu)=2 x+A^{T} \nu=0 \Rightarrow x=-(1 / 2) A^{T} \nu$

从而有对偶函数：

$g(\nu)=L\left(-(1 / 2) A^{T} \nu, \nu\right)=-(1 / 4) \nu^{T} A A^{T} \nu-b^{T} \nu$

对偶问题：

$\operatorname{maximize} \quad-(1 / 4) \nu^{T} A A^{T} \nu-b^{T} \nu$

这是一个无约束的凹函数最大化问题！（自然可以转化为无约束的凸优化问题）。从而我们知道，原问题是约束优化问题，对偶问题可能是无约束的问题！

3

考虑QCQP：

$\begin{array}{ll} \operatorname{minimize} & (1 / 2) x^{T} P_{0} x+q_{0}^{T} x+r_{0} \\ \text {subject to } & (1 / 2) x^{T} P_{i} x+q_{i}^{T} x+r_{i} \leq 0, \quad i=1, \ldots, m \end{array}$

拉格朗日函数：

$L(x, \lambda)=(1 / 2) x^{T} P(\lambda) x+q(\lambda)^{T} x+r(\lambda)$

其中：

$P(\lambda)=P_{0}+\sum_{i=1}^{m} \lambda_{i} P_{i}, \quad q(\lambda)=q_{0}+\sum_{i=1}^{m} \lambda_{i} q_{i}, \quad r(\lambda)=r_{0}+\sum_{i=1}^{m} \lambda_{i} r_{i}$

在 $\lambda \succeq 0$ 时， $P(\lambda)$ 是正定的，从而： $g(\lambda)=\inf _{x} L(x, \lambda)=-(1 / 2) q(\lambda)^{T} P(\lambda)^{-1} q(\lambda)+r(\lambda)$

所以有对偶问题：

$\begin{array}{ll} \operatorname{maximize} & -(1 / 2) q(\lambda)^{T} P(\lambda)^{-1} q(\lambda)+r(\lambda) \\ \text {subject to } & \lambda \succeq 0 \end{array}$

最后编辑于：2021.11.24 09:01:20