论文标题
对Ramana的精确对偶的简化处理，用于半决赛编程
A Simplified Treatment of Ramana's Exact Dual for Semidefinite Programming
论文作者
论文摘要
在半决赛编程中，二元组可能无法达到其最佳值，并且可能存在二元性差距，即，原始和双重最佳值可能会有所不同。在一篇引人注目的论文中，拉马纳提出了一个多项式尺寸扩展双重双重，没有这些缺陷，并在复杂性理论中产生许多基本结果。在这项工作中，我们主要依靠基本的线性代数，使读者浏览Ramana双重的简洁且独立的派生。
In semidefinite programming the dual may fail to attain its optimal value and there could be a duality gap, i.e., the primal and dual optimal values may differ. In a striking paper, Ramana proposed a polynomial size extended dual that does not have these deficiencies and yields a number of fundamental results in complexity theory. In this work we walk the reader through a concise and self-contained derivation of Ramana's dual, relying mostly on elementary linear algebra.
