Abstract
In many practical applications, optimization problems arise not in isolation, but as multiple instances of similar problems. In resource management for example, the instances take the form of linear programs involving the same coefficient matrix that describes a fixed network distribution structure, while the cost and “right-hand side” vectors change over time. In statistics, problems of cross-validation may involve set of least-squares problems where the different “design matrices” are very close to each other. In such instances, it makes sense to spend processing time on the common part of the problems, in order to compress it in some way, and speed up the overall computation.
In this work we propose an approach to multiple-instance conic optimization based on “robust sketching”, where the data matrix of an optimization problem is approximated by a "sketch", that is, a simpler matrix that preserves some property of interest, on which computations can be performed faster than the original, while feasibility with respect to the original problem is preserved. We examine applications of the concept in the areas of machine learning and in the context of very large LPs arising in energy management.