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.
HU Xu, LIU Yong-jin, LIU Mei-jiao, GAO Jing-ru
. Study on the projection operator over the set of variable box[J]. Journal of Shenyang Aerospace University, 2013
, 30(6)
: 93
-97
.
DOI: 10.3969/j.issn.2095-1248.2013.06.020
[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.
