New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds |
| |
Authors: | Yu-Hong Dai Roger Fletcher |
| |
Institution: | (1) State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering computing, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, PO Box 2719, Beijing, 100080, PR China;(2) Department of Mathematics, University of Dundee, Dundee DD1 4HN, Scotland, UK |
| |
Abstract: | There are many applications related to singly linearly constrained quadratic programs subjected to upper and lower bounds.
In this paper, a new algorithm based on secant approximation is provided for the case in which the Hessian matrix is diagonal
and positive definite. To deal with the general case where the Hessian is not diagonal, a new efficient projected gradient
algorithm is proposed. The basic features of the projected gradient algorithm are: 1) a new formula is used for the stepsize;
2) a recently-established adaptive non-monotone line search is incorporated; and 3) the optimal stepsize is determined by
quadratic interpolation if the non-monotone line search criterion fails to be satisfied. Numerical experiments on large-scale
random test problems and some medium-scale quadratic programs arising in the training of Support Vector Machines demonstrate
the usefulness of these algorithms.
This work was supported by the EPRSC in UK (no. GR/R87208/01) and the Chinese NSF grants (no. 10171104 and 40233029). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|