Learning for Constrained Optimization: Identifying Optimal Active\n Constraint Sets

Le résumé fourni par la source

In many engineered systems, optimization is used for decision making at\ntime-scales ranging from real-time operation to long-term planning. This\nprocess often involves solving similar optimization problems over and over\nagain with slightly modified input parameters, often under tight latency\nrequirements. We consider the problem of using the information available\nthrough this repeated solution process to directly learn a model of the optimal\nsolution as a function of the input parameters, thus reducing the need to solve\ncomputationally expensive large-scale parametric programs in real time. Our\nproposed method is based on learning relevant sets of active constraints, from\nwhich the optimal solution can be obtained efficiently. Using active sets as\nfeatures preserves information about the physics of the system, enables\ninterpretable models, accounts for relevant safety constraints, and is easy to\nrepresent and encode. However, the total number of active sets is also very\nlarge, as it grows exponentially with system size. The key contribution of this\npaper is a streaming algorithm that learns the relevant active sets from\ntraining samples consisting of the input parameters and the corresponding\noptimal solution, without any assumptions on the problem structure. The\nalgorithm comes with theoretical performance guarantees, and is known to\nconverge fast for problem instances with a small number of relevant active\nsets. It can thus be used to establish the practicability of the learning\nmethod. Through extensive experiments on the Optimal Power Flow problem, we\nobserve that often only a few active sets are relevant in practice, suggesting\nthat the active sets is the appropriate level of abstraction for a learning\nalgorithm to target.\n

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.