A Geometric Feasible Direction Algorithm for Large-Scale Optimization with l1 Norm Constraint

• Activity Number: 111
• Type: Contributed
• Date/Time: Monday, July 30, 2007 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Computing
• Author(s): Jian Zhang*+
• Companies: Purdue University
• Keywords: lasso ; constrained optimization ; feasible direction ; variable selection

Abstract

Recently, a lot of interests in machine learning and statistics have been given to learning methods which can lead to sparse solutions. Among those learning methods, many can be formulated as an optimization problem with l1 norm constraint. We propose a feasible direction algorithm which utilizes the geometric structure of the feasible region and is computationally efficient. We present sufficient and necessary conditions for optimality, as well as its convergence properties. Numerical experiments are conducted to show that, compared to several other methods, it is very efficient, robust and accurate.