Header logo is ei

Tackling Box-Constrained Optimization via a New Projected Quasi-Newton Approach




Numerous scientific applications across a variety of fields depend on box-constrained convex optimization. Box-constrained problems therefore continue to attract research interest. We address box-constrained (strictly convex) problems by deriving two new quasi-Newton algorithms. Our algorithms are positioned between the projected-gradient [J. B. Rosen, J. SIAM, 8 (1960), pp. 181–217] and projected-Newton [D. P. Bertsekas, SIAM J. Control Optim., 20 (1982), pp. 221–246] methods. We also prove their convergence under a simple Armijo step-size rule. We provide experimental results for two particular box-constrained problems: nonnegative least squares (NNLS), and nonnegative Kullback–Leibler (NNKL) minimization. For both NNLS and NNKL our algorithms perform competitively as compared to well-established methods on medium-sized problems; for larger problems our approach frequently outperforms the competition.

Author(s): Kim, D. and Sra, S. and Dhillon, IS.
Journal: SIAM Journal on Scientific Computing
Volume: 32
Number (issue): 6
Pages: 3548-3563
Year: 2010
Month: December
Day: 0

Department(s): Empirical Inference
Research Project(s): Optimization and Large Scale Learning
Bibtex Type: Article (article)

Digital: 0
DOI: 10.1137/08073812X
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: Web


  title = {Tackling Box-Constrained Optimization via a New Projected Quasi-Newton Approach},
  author = {Kim, D. and Sra, S. and Dhillon, IS.},
  journal = {SIAM Journal on Scientific Computing},
  volume = {32},
  number = {6},
  pages = {3548-3563 },
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  month = dec,
  year = {2010},
  month_numeric = {12}