求解约束最小二乘半正定规划问题的L-BFGS方法

对带等式和不等式约束的最小二乘半正定规划问题的求解进行了研究。在Slater约束规范条件下,对偶问题的最优解与原问题最优解相等。因此,考虑将最小二乘半正定规划问题转化为相应的对偶问题,通过求解对偶问题达到求解原问题的目的。针对最小二乘半正定规划问题的对偶问题,首先构造相应的二次模型,沿负梯度方向最小化该二次模型得到柯西点,在此基础上,利用积极约束技巧,划分积极约束集与非积极约束集,然后应用L-BFGS技巧对自由变量进行加速,从而求得对偶问题的最优解。最后,从理论上证明了算法的全局收敛性,并进行了初步的数值实验,将该算法与光滑化牛顿法作对比,结果表明该算法在计算时间上有一定的优势。

L-BFGS Method for Constrained Least Squares Semidefinite Programming

The solution of the least squares semidefinite programming problem with equality and inequality constraints was studied. Under the Slater constraint specification, the optimum solutions for the dual and original problems are the same. Therefore, the least squares semidefinite programming problem was transformed into its corresponding dual problem, and the original problem was solved by solving the dual problem. For the solution of the dual problem of the least squares semidefinite programming problem, the quadratic model was constructed, and Cauchy point was obtained by minimizing the quadratic model along the negative gradient direction. On this basis, the positive constraint set and the non-active constraint set were divided by using positive constraint technique. Then, the L-BFGS technique was applied to accelerate the free variables to obtain the optimum solution of the dual problem. Finally, the global convergence of the algorithm was proved theoretically, and a preliminary numerical experiment was carried out to compare the algorithm with the smoothed Newton method. The results show that the algorithm has certain advantages in computing time.