基于半定规划松弛的凸二层规划问题算法研究  

Researches on Convex Bilevel Optimization:Algorithms Based on Semidefinite Programming Relaxation

作　　者：金照林 JIN Zhao-lin(School of Electronic Commerce,Wuhan Technology and Business University,Wuhan 430065,China)

机构地区：[1]武汉工商学院电子商务学院,湖北武汉430065

出　　处：《数学的实践与认识》2023年第4期43-51,共9页Mathematics in Practice and Theory

基　　金：武汉工商学院博士基金项目“二层规划问题的新算法与应用研究”(D2013003)。

摘　　要：提出使用凸松弛的方法求解二层规划问题,通过对一般带有二次约束的二次规划问题的半定规划松弛的探讨,研究了使用半定规划(SDP)松弛结合传统的分枝定界法求解带有凸二次下层问题的二层二次规划问题,相比常用的线性松弛方法,半定规划松弛方法可快速缩小分枝节点的上下界间隙,从而比以往的分枝定界法能够更快地获得问题的全局最优解.This paper proposes a method based on convex relaxation to solve Bilevel Programming(BLP)problems.Through the introduction of convex relaxation,we dicuss the use of semidefine programming relaxation combined with the branch and bound method to solve the BLP problems.Compared with the commonly linear relaxation,the semidefinite programming relaxation can greatly narrow the gap of the upper and lower bounds of the branch node,thus the branch and bound method can obtain the global optimal solution of problem more quickly than in the past.

关 键 词：二层规划 SDP松弛 分枝定界 

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