The Weighted Nonnegative Least-Squares Problem with Implicitly Characterized Points

• 成果类型: Article
• 署名作者: Fattahi, Ali; Dasu, Sriram; Ahmadi, Reza
• 署名单位: University of California System; University of California Los Angeles; University of Southern California
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1793
• 发表日期: 2019
• 页码: 1106-1119

摘要

The nonnegative least-squares (NNLS) problem is defined as finding the Euclidean distance to a convex cone generated by a set of discrete points in R. In this paper, we study NNLS when the discrete points are implicitly known and there are an exponentially large number of them (e.g., the set of integer feasible solutions of a mixed-integer program). This problem is motivated by a large auto manufacturer that produces mass customized products where the products are configured by choosing a subset of features. In addition, this problem can have applications in other manufacturing settings, machine learning, clustering, pattern recognition, and statistics. The NNLS can be formulated as a convex optimization problem, and there are efficient algorithms in the literature for solving it. However, NNLS with implicit points cannot be solved using the existing methods. Therefore, we first present a surrogate problem that enables us to find the optimal solution to this problem. Second, we design a Frank-Wolfe-based solution approach for solving our surrogate problem. At each iteration k of our proposed methodology, we generate a feasible solution (upper bound) and show that the upper bound converges to the optimal value at O(1/k). Third, we develop a lower bound that enables us to estimate the optimality gap at each iteration and show that the lower bound also converges to the optimal value at O(1/k). Finally, we test the effectiveness of our approach on a set of simulated and real industrial instances.