随机组合优化算法与复杂性研究

Stochastic optimization has established itself as a major method to handle uncertainty in various optimization problems, by modeling the uncertainty by a probability distribution over possible realizations. Traditionally, the main focus in stochastic optimization has been various stochastic mathematical programming. Motivated by the need of handling uncertian data and various applications from online advertisement, sensor networks, scheduling and so on, there has been a surge of interest in stochastic combinatorial optimization problems in recent years from the theoretical computer science community. In this project, we aim to study stochastic versions of classical combinatorial optimization problems. Since most problems in this domain are NP-hard (or #P-hard, or even PSPACE-hard), we focus on the results which provide polynomial time approximation algorithms, with provable approximation guarantees. We focus on some important and representative problems in this domain such as 2-stage stochastic optimization model, stochastic geometric optimization, stochastic knapsack, stochastic matching, multi-armed bandit etc. The goal of the project is to develop new mathematical and algorithmic techniques, and to use them to provide new reductions for proving computational hardness, improve existing approximation results and design new approximation algorithms for existing and new stochastic combinatorial optimization problems.

随机优化是处理非确定情况下的优化问题的主要方法。其主要是以概率论为基础，用概率分布去描述非确定情况下发生不同事件的可能性。传统随机优化的主要研究内容是随机数学规划，如线性规划，凸规划等。但近年来，很多需要解决的组合优化问题应用领域中自然产生了大规模非确定数据，如在线广告分配，无线传感器网络等，因此，随机组合优化问题引起了理论计算机科学界的广泛关注。随机组合优化问题大部分都是NP-hard（甚至是#P-hard或PSPACE-hard）。.本项目计划重点研究随机组合优化问题的复杂性，多项式时间近似算法，和不可近似性，特别是对于该领域中几个有代表性的问题，如双阶段随机优化模型，随机几何优化问题，随机背包问题，随机匹配问题，多臂老虎机问题等。项目的研究目标是发展处理随机组合优化问题的新的数学和算法技术，并应用这些技术设计新的证明复杂性的规约，设计新的多项式时间近似算法和分析方法。

项目主要研究内容为随机组合优化问题。在随机组合优化问题中，概率分布和组合结构的相互作用使得多数随机组合优化问题是NP-Hard，甚至是#P-hard或PSPACE-hard 的。因此本项目主要目标是针对重要的随机组合优化问题设计有近似度保证的近似算法。项目结题主要成果包括：（1）提出了一大类随机优化问题的多项式时间近似方案（2）提出了基于傅里叶分析的随机组合优化问题的算法设计技术（3）针对随机连续优化，提出了非凸优化问题的方差缩减算法的一个分析，得到了有最优收敛速度（收敛到一阶局部最优点）（4）针对有转移概率的马尔可夫决策游戏，并首次得到了常数近似度的近似算法。项目还在机器学习理论领域取得若干成果。在本项目的资助下，共发表论文27篇，其中CCF-A类论文14篇。