Tackling Box-Constrained Optimization via a New Projected Quasi-Newton Approach
Web
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. |
| Links: | |
| 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 |
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},
author = {Kim, D. and Sra, S. and Dhillon, IS.},
doi = {10.1137/08073812X},
month_numeric = {12}
}