CCT-TR-2009-10

Title:
An Affine-scaling Interior-point Method for Continuous Knapsack Constraints

Authors:
Maria D. Gonzalez-Lima, William W. Hager, Hongchao Zhang

Summary:
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. Numerical comparisons are
given using Support Vector Machine test problems.

Download Article: CCT-TR-2009-10.pdf

Print this Page

Refer this page to a friend