向一类特殊集合进行投影的无迭代式精确解算法  

An Algorithm to Realize the Exact Projection onto a Special Cons traint Set Without Iteration

作　　者：何胜学[1] HE Sheng-xue(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《数学的实践与认识》2022年第2期117-124,共8页Mathematics in Practice and Theory

基　　金：国家自然科学基金(71801153,71871144);上海市自然科学基金项目(18ZR1426200)。

摘　　要：决策变量之和为定值且各分量具有上下界的特殊集合广泛出现在各种实际优化问题中.在求解相关优化问题时往往需要反复向上述的决策变量约束集合进行-投影,即反复求解一个内嵌的二次规划问题.为了提高相关优化算法的计算效率,快速实现上述投影就成为问题的关键.针对上述投影,提出了一种精确求解算法.通过代数变幻和概念替换,上述投影问题等价转化为一个静态交通分配问题.利用出行者选择路线的Wardrop第一原则可以实现对上述流量分配问题的无迭代式快速精确求解,即实现对原投影问题的快速精确求解.将上述精确算法的计算结果与利用传统迭代算法的商业软件计算结果相对比,证实了新方法的有效性.The set of constraints consisting of the given sum of the values of decision variables and the given upper and/or lower bounds of the decision variables appears commonly in various optimization problems in the real world.To solve the related optimization problems,repeatedly projecting onto the above constraints set is generally required,in other words,it is necessary repeatedly to solve an embedding quadratic programming problem.To improve the efficiency of related optimization algorithms,it is critical to realize the above projection quickly.To this end,this paper proposed an algorithm to obtain the exact projection related to the above special set.After proper algebra operations and conception replacements,the projection problem is transformed into an equivalent static traffic assignment.By making use of the first Wardrop’s principle of choosing travel routes,we can solve the traffic assignment quickly and exactly without iteration.In another word,it means realizing the original projection quickly and exactly.The comparison between the results from the new exact algorithm and the commercial software,which is based on the classical iteration algorithm,verified the effectiveness of our new algorithm.

关 键 词：数值优化 投影算法 交通流分配 单纯形约束 

分 类 号：O224[理学—运筹学与控制论]