确定线性程序是否是自对偶的?

Determining if a linear program is self-dual?

提问人:Noah Borquaye 提问时间:11/8/2023 更新时间:11/8/2023 访问量:13

问:

我想证明 if 是一个偏对称矩阵,然后是自对偶矩阵。$A$$n\times n$($A^{T}=-A$ )$c\in \mathbb{R}^{n},$$$\begin{array}{cc} \max & c^{T}x \\ s.t. & Ax\geq c \\ & x\geq 0 \end{array} $$

我通过改变目标开始了我的解决方案:$\max c^{T}x $ to $\min -c^{T}x $.

然后,我得到原始程序为

$$ \begin{array}{cc} \min & -c^Tx \\ s.t. & Ax \geq c \\ & x \geq 0 \\ \end{array} $$

和相应的 Dual 程序作为

$$ \begin{array}{cc} \max & y^Tc \\ s.t. & A^Ty \leq -c \\ & y \geq 0 \\ \end{array} $$

我知道,如果线性程序是自对偶的,那么素数与对偶相同。我的问题是我如何确定这一点?

线性规划 运筹学

评论

0赞 Raymond Chen 12/18/2023
这是一个数学问题,而不是计算机编程问题。

答:

0赞 Li Jianqing 12/18/2023 #1

在用 innter 指针法求解线性规划 (LP) 时,我们可以为任何 LP 构建一个等效的“齐次自对偶线性可行性优化问题”(HLF)。然后,我们可以通过求解HLF得到原始LP的最优解。

我最近一直在学习这个问题,很想讨论一下。

参考资料包括: Andersen, ED, & Andersen, KD (2000)。用于线性规划的 MOSEK 内点优化器:齐次算法的实现。在高性能优化中(第 197-232 页)。马萨诸塞州波士顿:美国斯普林格。

Xu, X., Hung, P. F., & Ye, Y. (1996)。一种简化的齐次自对偶线性规划算法及其实现.运筹学年鉴, 62(1), 151-171.