Following the breakthrough work of Tardos in the bit-complexity model, Vavasis and Ye gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) $\max\, c^\top x,\: Ax = b,\: x \geq 0,\: A \in \mathbb{R}^{m \times n}$, Vavasis and Ye developed a primal-dual interior point method using a 'layered least squares' (LLS) step, and showed that $O(n^{3.5} \log (\bar{\chi}_A+n))$ iterations suffice to solve (LP) exactly, where $\bar{\chi}_A$ is a condition measure controlling the size of solutions to linear systems related to $A$. Monteiro and Tsuchiya, noting that the central path is invariant under rescalings of the columns of $A$ and $c$, asked whether there exists an LP algorithm depending instead on the measure $\bar{\chi}^*_A$, defined as the minimum $\bar{\chi}_{AD}$ value achievable by a column rescaling $AD$ of $A$, and gave strong evidence that this should be the case. We resolve this open question affirmatively. Our first main contribution is an $O(m^2 n^2 + n^3)$ time algorithm which works on the linear matroid of $A$ to compute a nearly optimal diagonal rescaling $D$ satisfying $\bar{\chi}_{AD} \leq n(\bar{\chi}^*)^3$. This algorithm also allows us to approximate the value of $\bar{\chi}_A$ up to a factor $n (\bar{\chi}^*)^2$. As our second main contribution, we develop a scaling invariant LLS algorithm, together with a refined potential function based analysis for LLS algorithms in general. With this analysis, we derive an improved $O(n^{2.5} \log n\log (\bar{\chi}^*_A+n))$ iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor $n/\log n$ improvement on the iteration complexity bound of the original Vavasis-Ye algorithm.


翻译:塔多斯在 bit- complex 模型中的突破性工作之后, Vavasis 和 Ye 提供了在实际计算模型中直线程序使用成本的首次精确算法, 运行时间仅取决于限制矩阵。 对于解决一个线性程序( LP) $\ max\, c ⁇ top x,\: x\ geq 0.,\: x x\ geqq 0.,\: a\ in mathbralb{R} $, Vavasis 和 Ye 开发了一个原始内部点方法, 使用“ 平坦最小的 平方 ” (LLS) 步骤, 并显示 $(n=3.5}\ log (bral) 美元, colorisal =xal ==xxxx 美元 。

0
下载
关闭预览

相关内容

再缩放是一个类别不平衡学习的一个基本策略。当训练集中正、反例数据不均等时,令m+表示正例数,m-表示反例数,并且需对预测值进行缩放调整。
专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
75+阅读 · 2021年3月16日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
商业数据分析,39页ppt
专知会员服务
157+阅读 · 2020年6月2日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
144+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
168+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
已删除
将门创投
3+阅读 · 2017年10月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年7月2日
Arxiv
0+阅读 · 2021年6月30日
VIP会员
相关VIP内容
专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
75+阅读 · 2021年3月16日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
76+阅读 · 2020年7月26日
商业数据分析,39页ppt
专知会员服务
157+阅读 · 2020年6月2日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
144+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
168+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
CCF A类 | 顶级会议RTSS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年4月17日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
已删除
将门创投
3+阅读 · 2017年10月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员