提问人:Noah Borquaye 提问时间:11/8/2023 更新时间:11/8/2023 访问量:13
确定线性程序是否是自对偶的?
Determining if a linear program is self-dual?
问:
我想证明 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} $$
我知道,如果线性程序是自对偶的,那么素数与对偶相同。我的问题是我如何确定这一点?
答:
在用 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.
评论