Safe Feature Elimination for Non-negativity Constrained Convex Optimization

James Folberth () and Stephen Becker ()
Additional contact information
James Folberth: University of Colorado at Boulder
Stephen Becker: University of Colorado at Boulder

Journal of Optimization Theory and Applications, 2020, vol. 184, issue 3, No 11, 952 pages

Abstract: Abstract Inspired by recent work on safe feature elimination for 1-norm regularized least-squares, we develop strategies to eliminate features from convex optimization problems with non-negativity constraints. Our strategy is safe in the sense that it will only remove features/coordinates from the problem when they are guaranteed to be zero at a solution. To perform feature elimination, we use an accurate, but not optimal, primal–dual feasible pair, making our methods robust and able to be used on ill-conditioned problems. We supplement our feature elimination problem with a method to construct an accurate dual feasible point from an accurate primal feasible point; this allows us to use a first-order method to find an accurate primal feasible point and then use that point to construct an accurate dual feasible point and perform feature elimination. Under reasonable conditions, our feature elimination strategy will eventually eliminate all zero features from the problem. As an application of our methods, we show how safe feature elimination can be used to robustly certify the uniqueness of nonnegative least-squares problems. We give numerical examples on a well-conditioned synthetic nonnegative least-squares problem and on a set of 40,000 extremely ill-conditioned problems arising in a microscopy application.

Keywords: Feature elimination; Dimension reduction; Duality; NNLS; 49N15; 90C25; 90C46 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-019-01612-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:184:y:2020:i:3:d:10.1007_s10957-019-01612-w

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-019-01612-w

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().