The Weighted Nonnegative Least-Squares Problem with Implicitly Characterized Points

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 ${\mathbb{R}}^n$. 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 $\mathcal{O}\left(1/k\right)$. 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 $\mathcal{O}\left(1/k\right)$. Finally, we test the effectiveness of our approach on a set of simulated and real industrial instances.