An accelerated proximal gradient algorithm for singly linearly constrained quadratic programs with box constraints.
Recently, the existed proximal gradient algorithms had been used to solve non-smooth convex optimization problems. As a special nonsmooth convex problem, the singly linearly constrained quadratic programs with box constraints appear in a wide range of applications. Hence, we propose an accelerated proximal gradient algorithm for singly linearly constrained quadratic programs with box constraints. At each iteration, the subproblem whose Hessian matrix is diagonal and positive definite is an easy model which can be solved efficiently via searching a root of a piecewise linear function. It is proved that the new algorithm can terminate at an ε-optimal solution within [Formula: see text] iterations. Moreover, no line search is needed in this algorithm, and the global convergence can be proved under mild conditions. Numerical results are reported for solving quadratic programs arising from the training of support vector machines, which show that the new algorithm is efficient.
School of Mathematical Sciences, University of Chinese Academy of Sciences, Shijingshan District, Beijing 100049, China.
Congying
C
Han
Mingqiang
M
Li
Tong
T
Zhao
Tiande
T
Guo
D000465:Algorithms; D011382:Programming, Linear