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.
翻译：在半无限期的编程中,两重可能无法达到其最佳价值,而且可能存在双重性差距,即原始值和双重最佳值可能有所不同。 在一份惊人的论文中,拉马纳提出了一个多元体的扩大双倍体积,它没有这些缺陷,在复杂理论中产生了一些基本结果。 在这项工作中,我们通过一个简明和自成一体的拉马纳双重体衍生法,主要依靠基本线性代数。
相关内容
专知会员服务
34+阅读 · 2019年10月17日
Arxiv
0+阅读 · 2022年7月15日
Arxiv
0+阅读 · 2022年7月15日
Arxiv
0+阅读 · 2022年7月15日
Arxiv
0+阅读 · 2022年7月14日
Arxiv
0+阅读 · 2022年7月13日
Arxiv
13+阅读 · 2020年6月24日
相关VIP内容
专知会员服务
34+阅读 · 2019年10月17日
相关资讯
相关论文
Arxiv
0+阅读 · 2022年7月15日
Arxiv
0+阅读 · 2022年7月15日
Arxiv
0+阅读 · 2022年7月15日
Arxiv
0+阅读 · 2022年7月14日
Arxiv
0+阅读 · 2022年7月13日
Arxiv
13+阅读 · 2020年6月24日
微信扫码咨询专知VIP会员