In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like "input", "size" and "complexity" in the context of general mathematical optimization, avoiding context dependent definitions which is one of the sources of difference in the treatment of complexity within continuous and discrete optimization. In the second part of the paper, we employ the language developed in the first part to study information theoretic and algorithmic complexity of {\em mixed-integer convex optimization}, which contains as a special case continuous convex optimization on the one hand and pure integer optimization on the other. We strive for the maximum possible generality in our exposition. We hope that this paper contains material that both continuous optimizers and discrete optimizers find new and interesting, even though almost all of the material presented is common knowledge in one or the other community. We see the main merit of this paper as bringing together all of this information under one unifying umbrella with the hope that this will act as yet another catalyst for more interaction across the continuous-discrete divide. In fact, our motivation behind Part I of the paper is to provide a common language for both communities.


翻译:在本文件第一部分,我们提出了一个分析任何优化问题的算法复杂性的统一框架,无论是连续性的还是离散的。这有助于在一般数学优化的背景下正式确定“投入”、“大小”和“复杂”等概念,避免背景依赖定义,这是在连续和离散优化中处理复杂问题的不同来源之一。在本文件第二部分,我们使用第一部分所开发的语言,研究各种优化问题的信息理论和算法复杂性,无论是连续性的还是离散的。这有助于在一般数学优化的背景下,将“投入”、“大小”和“复杂”等概念正式化。我们希望本文包含连续优化者和离散优化者都发现的新和有趣的材料,尽管几乎所有材料都是一个或另一个社区的共同知识。我们认为,本文件的主要优点是将所有这些信息集中到一个统一的伞之下,希望它能成为在两个社区之间进行更多互动的另一个特殊案例。我们希望,我们力求在展览中尽可能做到尽可能普遍的普遍性。我们希望本文包含一些材料,即连续优化者和离散优化者发现新的和有趣的材料,尽管几乎所有材料都是一个或另一个社区的共同知识。我们认为,本文件的主要优点是将所有这些信息汇集在一个统一的伞之下,希望这将作为两个社区之间持续互动的另一个催化剂的另一种催化剂是共同的动力。

0
下载
关闭预览

相关内容

让 iOS 8 和 OS X Yosemite 无缝切换的一个新特性。 > Apple products have always been designed to work together beautifully. But now they may really surprise you. With iOS 8 and OS X Yosemite, you’ll be able to do more wonderful things than ever before.

Source: Apple - iOS 8
Python图像处理,366页pdf,Image Operators Image Processing in Python
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
89+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
267+阅读 · 2019年10月9日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年12月14日
Arxiv
0+阅读 · 2021年12月13日
Arxiv
0+阅读 · 2021年12月10日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
可解释的CNN
CreateAMind
17+阅读 · 2017年10月5日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员