Institute Homepage DE Sign In

Back

Empirical Inference Article 2010

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

Thumb ticker sm thumb suvrit sra
Empirical Inference
Suvrit Sra

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
Bibtex Type: Article (article)
DOI: 10.1137/08073812X
Digital: 0
Electronic Archiving: grant_archive
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik
Links:

BibTex 

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