Active Information Acquisition for Linear Optimization
Active Information Acquisition for Linear Optimization
复制标题
DOI：
--
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Shuran Zheng;Bo Waggoner;Yang Liu;Yiling Chen
中科院分区：
文献类型：
--
作者：
Shuran Zheng;Bo Waggoner;Yang Liu;Yiling Chen
我们考虑部分指定的优化问题，其中的目标是主动但有效地获取关于问题的缺失信息以解决问题。算法设计者希望解决一个线性规划(LP)，$\max\mathbf{c}^T\mathbf{x}$s.t。$\mathbf{A}\mathbf{x}\leq\mathbf{b}，\mathbf{x}\ge\mathbf{0}$，但最初并不知道某些参数。该算法可以迭代地选择一个未知参数，并以以该参数的(未知)值为中心的噪声样本的形式收集信息。其目标是在抽取少量样本的情况下，以较高的概率找到潜在线性规划的近似可行的最优解。我们主要关注两个案例。(1)当目标的参数未知时，我们采用信息论的方法，给出了大致匹配的样本复杂度上界和下界，并给出了一种(低效)逐次消元算法。(2)在初始约束参数未知的情况下，结合椭球法和Bandit算法的置信度方法，提出了一种有效的线性规划算法。该算法仅在需要时才自适应地收集有关约束的信息以取得进展。我们给出了该算法的样本复杂度界，并通过仿真证明了其相对于朴素方法的改进。
We consider partially-specified optimization problems where the goal is to actively, but efficiently, acquire missing information about the problem in order to solve it. An algorithm designer wishes to solve a linear program (LP), $\max \mathbf{c}^T \mathbf{x}$ s.t. $\mathbf{A}\mathbf{x} \leq \mathbf{b}, \mathbf{x} \ge \mathbf{0}$, but does not initially know some of the parameters. The algorithm can iteratively choose an unknown parameter and gather information in the form of a noisy sample centered at the parameter's (unknown) value. The goal is to find an approximately feasible and optimal solution to the underlying LP with high probability while drawing a small number of samples. We focus on two cases. (1) When the parameters $\mathbf{c}$ of the objective are initially unknown, we take an information-theoretic approach and give roughly matching upper and lower sample complexity bounds, with an (inefficient) successive-elimination algorithm. (2) When the parameters $\mathbf{b}$ of the constraints are initially unknown, we propose an efficient algorithm combining techniques from the ellipsoid method for LP and confidence-bound approaches from bandit algorithms. The algorithm adaptively gathers information about constraints only as needed in order to make progress. We give sample complexity bounds for the algorithm and demonstrate its improvement over a naive approach via simulation.