An Affine-Scaling Interior-Point Method for Continuous Knapsack Constraints with Application to Support Vector Machines
Authors:
- Maria D. Gonzalez-LimaMGMaria D. Gonzalez-Lima
- William W. HagerWHWilliam W. Hager
- Hongchao ZhangHZHongchao Zhang
- 1 January 2011
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 21 (1) , 361-390
Abstract
An affine-scaling algorithm (ASL) for optimization problems with a single linear equality constraint and box restrictions is developed. The algorithm has the property that each iterate lies in the relative interior of the feasible set. The search direction is obtained by approximating the Hessian of the objective function in Newton's method by a multiple of the identity matrix. The algorithm is particularly well suited for optimization problems where the Hessian of the objective function is a large, dense, and possibly ill-conditioned matrix. Global convergence to a stationary point is established for a nonmonotone line search. When the objective function is strongly convex, ASL converges R-linearly to the global optimum provided the constraint multiplier is unique and a nondegeneracy condition holds. A specific implementation of the algorithm is developed in which the Hessian approximation is given by the cyclic Barzilai-Borwein (CBB) formula. The algorithm is evaluated numerically using support vector machine test problems.Keywords
This publication has 48 references indexed in Scilit:
- New algorithms for singly linearly constrained quadratic programs subject to lower and upper boundsMathematical Programming, 2005
- Inexact spectral projected gradient methods on convex setsIMA Journal of Numerical Analysis, 2003
- Alternate step gradient method*Optimization, 2003
- Large-Scale Active-Set Box-Constrained Optimization Method with Spectral Projected GradientsComputational Optimization and Applications, 2002
- Algorithm 813ACM Transactions on Mathematical Software, 2001
- The analysis of decomposition methods for support vector machinesIEEE Transactions on Neural Networks, 2000
- Nonmonotone Spectral Projected Gradient Methods on Convex SetsSIAM Journal on Optimization, 2000
- A Tutorial on Support Vector Machines for Pattern RecognitionData Mining and Knowledge Discovery, 1998
- Two-Point Step Size Gradient MethodsIMA Journal of Numerical Analysis, 1988
- Minimization of functions having Lipschitz continuous first partial derivativesPacific Journal of Mathematics, 1966