Introduction
Mathematical Programs with Equilibrium Constraints (MPECs) are a class of optimization problems where the constraints include equilibrium conditions, such as variational inequalities or complementarity conditions. These problems are prevalent in economics, engineering, and energy management. However, MPECs are notoriously difficult to solve because they are typically non-convex and fail standard constraint qualification tests. Furthermore, real-world data is often uncertain, requiring a robust approach to ensure feasibility and optimality under fluctuating conditions. This paper introduces a novel framework that combines robust optimization with a hierarchy of sum-of-squares (SOS) relaxations to solve robust equilibrium-constrained polynomial problems, with a specific focus on electric vehicle (EV) charging schedules.
The Robust MPEC Problem
The core challenge addressed is the Robust MPEC. Unlike classical MPECs that assume perfect knowledge of input data, the robust formulation accounts for uncertainties in parameters such as electricity prices or consumer demand. The goal is to find a solution that remains optimal and feasible even when data fluctuates within a predefined uncertainty set, typically modeled as a polytope. By "immunizing" the solution against worst-case scenarios, the model provides a more reliable framework for critical infrastructure management.
Methodology: Hierarchical Relaxations
The researchers bridge the gap between abstract equilibrium theory and practical computation through a multi-step approach:
- Dual Characterization: Equilibrium constraints (variational inequalities) are transformed into standard, albeit non-convex, polynomial constraints using a dual approach akin to Karush-Kuhn-Tucker (KKT) conditions.
- Robust Formulation: Uncertainty is defined using polytope sets, ensuring the solution's robustness.
- Hierarchy of Relaxations: To handle the non-convexity, the authors employ a hierarchy of convex relaxations. These provide increasingly tight lower bounds on the global optimum:
- SOS (Sum-of-Squares): Highly accurate but computationally intensive, utilizing Semidefinite Programming (SDP).
- DSOS (Diagonally Dominant SOS): More efficient, utilizing Linear Programming (LP).
- SDSOS (Scaled Diagonally Dominant SOS): A middle ground utilizing Second-Order Cone Programming (SOCP).
- Convergence Proofs: The paper provides mathematical proofs that these hierarchies asymptotically converge to the true global optimal value as the degree of the relaxation increases.
Case Study: EV Charging in Chongqing
The framework was validated using a practical application: scheduling EV charging for an office building in Chongqing, China. The model utilized 24-hour baseload electricity data and technical specifications based on the Tesla Model 3 (75 kWh battery, 30 kW max charge, 45 kW max discharge). In this "Vehicle-to-Grid" (V2G) scenario, the equilibrium between the user (minimizing cost) and the operator (maximizing profit) is highly sensitive to price volatility. The robust approach ensures the schedule remains viable despite uncertain discharging supplies from other vehicles.
Results and Discussion
Numerical tests confirmed that as the relaxation order ($k$) increases, the lower bounds calculated by the hierarchies successfully converge to the known global optimum. A key insight was the identification of the "Memory Wall"—while SOS relaxations are theoretically superior, they often exceed memory limits on standard hardware for complex problems.
The authors found that SDSOS serves as the "sweet spot," providing the best balance of performance and computational feasibility. For the EV model at relaxation order $k=3$, standard LP hierarchies and popular tools like Gloptipoly 3 failed due to memory constraints, whereas the proposed DSOS and SDSOS schemes successfully returned optimal values.
Conclusion
This research provides a mathematically grounded framework for solving complex, uncertain equilibrium problems. By leveraging SDSOS relaxations, the authors offer a scalable path to global optimality for real-world applications like EV charging. Future work will focus on exploiting "sparsity" in SOS hierarchies to handle even larger-scale systems, potentially extending the framework to fields such as taxation equilibria and process engineering.
Summary updated