非凸半无限规划算法及其在分布式鲁棒随机优化中的应用研究

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11401331
项目类别：
青年科学基金项目
资助金额：
22.0万
负责人：
马骋
依托单位：
青岛大学
学科分类：
A0405.连续优化
结题年份：
2017
批准年份：
2014
项目状态：
已结题
起止时间：
2015-01-01 至2017-12-31

项目参与者：
徐庆；杜守强；初阿杰；苏一笑；
关键词：
凸松弛半无限规划鲁棒随机优化松弛切平面算法分支定界算法

项目摘要

Nonconvex semi-infinite programming is a special class of optimization problem. In recent years, with the rapid development of interdisciplinary subjects, nonconvex semi-infinite programming has a very wide application fields, such as control and decision, artificial intelligence, machine learning, data mining, actuarial risk theory and so on. To design fast and robust algorithms for nonconvex semi-infinite programming has already become one of the most popular research topics in optimization fields. In this project, we focus on designing global optimization algorithms for nonconvex semi-infinite programming and applying them to distributionally robust stochastic programming. Firstly, based on convex relaxation problem of nonconvex semi-infinite programming, a relaxed cutting plane method for nonconvex semi-infinite programming is proposed. The global convergence theorem and convergence rate are presented. Secondly, based on the structure characteristics of nonconvex semi-infinite programming, a two phases branch and bound algorithm is proposed for the upper and the lower problems, respectively. Finally, we characterize properties of distributionally robust stochastic programming and its equivalence with semi-infinite programming problem and apply the newly-designed algorithms for distributionally robust stochastic programming.

非凸半无限规划问题是一类具有特殊结构的最优化问题。近年来，随着交叉学科的蓬勃发展，非凸半无限规划在控制决策、人工智能、机器学习、数据挖掘、精算风险度量理论等领域中有着极其广泛的应用。设计非凸半无限规划问题的快速稳定算法成为当前优化领域中最热门的研究课题之一。本项目拟对非凸半无限规划问题的全局优化算法及其在分布式鲁棒随机优化问题中的应用进行深入地研究。首先，构造非凸半无限规划的一类凸松弛问题，并设计松弛切平面算法，分析算法的收敛性以及收敛速率；其次，针对非凸半无限规划问题的结构特点，对上、下层问题量身设计两阶段分支定界算法；最后，刻画分布式鲁棒随机优化问题的性质及其与半无限规划的等价关系，并将新设计的算法推广应用于求解分布式鲁棒随机优化问题。

结项摘要

目前，对一般结构的分布式鲁棒随机优化问题的研究还非常少。这一缺陷限制了分布式鲁棒随机优化的应用范围。为此，项目主持人及其研究生以及多年的合作者在分布式鲁棒随机优化算法及应用方面进行了深入的研究。具体包括：1）设计了一种新型的交换集算法来求解分布式鲁棒随机优化问题，并且证明该算法的全局收敛性定理。这种新的交换集算法的创新点在于通过增加适当的约束条件，只保留起作用约束的正拉格朗日乘子, 这样大大减少了计算量。采用傅里叶变换以及多项式截断的技巧处理非线性约束，获得较好的数值结果。2）设计了新型两阶段分支定界算法求解非凸半无限规划问题。在离散化参数集合，决策变量集合的基础上，借用现代分析工具分别构造内、外问题的凸松弛方法，将半无限规划问题转化为有限的凸规划问题，进行收敛性分析。3）设计了一类新的精确光滑简单罚函数，成功刻画出了全局精确罚以及局部精确罚的性质，且数值效果良好。并将该新算法应用于管理学领域流行的搜索引擎广告拍卖问题中，效果良好。4）在设计分布式鲁棒随机优化问题算法过程中，发现该问题在解决管理学实际问题中也有着很好的应用。搜索引擎优化问题是市场需求不确定的二阶价拍卖机制博弈问题，利用连续优化算法求解该算法的成果并不多见。本项目中，搜索引擎优化问题成功转化为一个0-1整数规划模型，利用Lagrangian 松弛以及次梯度算法求解出目标函数的最优值。数值结果证明了算法的合理有效性。5）应用分布式鲁棒随机优化模型，对拍卖激励机制设计问题进行了研究。建立了双层供应链供应商遴选激励机制，使得供应链达到渠道协调。