众所周知, 在优化问题算法与理论的研究过程中, 如增广拉格朗日方法的应用以及优化问题的灵敏性分析等, 凸集上投影算子的性质起着极其重要的作用。通过投影算子对应的凸二次优化的Karush-Kuhn-Tucker (KKT)条件, 给出了可变盒子集合投影算子显示解的计算方法, 并对其Matlab软件实现。通过具体的数值算例, 验证了研究结果的正确性与有效性。
As we all know, the properties of the metric projection over convex sets play significant role in the study of the algorithms and theory of the related optimization problems such as the applications of the augmented Lagrangian methods and sensibility analysis of optimization problems, and so on.This paper presents the computational formula of the metric projection over the set of variable box by using the Karush-Kuhn-Tucker (KKT) condition of the corresponding convex quadratic optimization problems.We implement it via Matlab software.The reported numerical results for specific examples show that our algorithm is correct and effective.
[1]HELGASON R, KENNINGTON J, LALL H.A polynomially bounded algorithm for a singly constrained quadratic program [J].Mathematical Programming, 1980, 18(1):338-343.
[2]BRUCKER P.An O(n) algorithm for quadratic knapsack problems [J].Operations Research Letters, 1984, 3(3):163-166.
[3]MACULAN N, PAULA G G De.A linear-time median-finding algorithm for projecting a vector on the simplex of [J].Operations Research Letters, 1989, 8(4):219-222.
[4]PARDALOS P M, KOVOOR N.An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds [J].Mathematical Programming, 1990, 46(1-3):321-328.
[5]MACULAN N, SANTIAGO C P, MACAMBIRA E M, et al.An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in [J].Journal of Optimization Theory and Applications, 2003, 117(3):553-574.
[6]KIWIEL K C.Breakpoint searching algorithms for the continuous quadratic knapsack problem [J].Mathematical Programming, 2008, 112(2):473-491.
[7]DING C, SUN D F, TOH K-C.An introduction to a class of matrix cone programming [J].Methematical Programming, 2010(12):1-39.
[8]WU B, Ding C, SUN D F, et al.On the Moreau-Yoshida regularization of the vector k-norm related function [DB/OL].http://www.optimization-online.org/DB_FILE/2011/03/2978.pdf, 下载时间:2013-03-26.
[9]LIU Y-J, WANG S Y, SUN J-H.Finding the projection onto the intersection of a closed half-space and a variable box [J].Operations Research Letters, 2013, 41:259-264.
[10]GRANT M, BOYD S.CVX:Matlab software for disciplined convex programming, version 2.0 beta[DB/OL].http://cvxr.com/cvx, 下载时间:2012-12-09.
