Title | ||
---|---|---|
An Affine-Scaling Interior-Point Method for Continuous Knapsack Constraints with Application to Support Vector Machines |
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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1137/090766255 | SIAM Journal on Optimization |
Keywords | Field | DocType |
affine-scaling interior-point method,constraint multiplier,asl converges r-linearly,affine-scaling algorithm,support vector machines,continuous knapsack constraints,ill-conditioned matrix,global convergence,optimization problem,objective function,hessian approximation,nonmonotone line search,identity matrix,interior point method,support vector machine,interior point,linear convergence | Relative interior,Discrete mathematics,Mathematical optimization,Hessian matrix,Convex function,Stationary point,Feasible region,Knapsack problem,Interior point method,Optimization problem,Mathematics | Journal |
Volume | Issue | ISSN |
21 | 1 | 1052-6234 |
Citations | PageRank | References |
6 | 0.46 | 43 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
María D. González-Lima | 1 | 25 | 4.75 |
William W. Hager | 2 | 1603 | 214.67 |
Hongchao Zhang | 3 | 809 | 43.29 |