Online Dynamic Submodular Optimization
This work addresses optimization problems in dynamic settings for applications like power systems, but it is incremental as it builds on existing online and submodular methods.
The authors tackled online dynamic submodular optimization by proposing algorithms like OSGA and OSPGD, achieving dynamic regret bounds comparable to tight results in online convex optimization, with numerical tests in power system applications.
We propose new algorithms with provable performance for online binary optimization subject to general constraints and in dynamic settings. We consider the subset of problems in which the objective function is submodular. We propose the online submodular greedy algorithm (OSGA) which solves to optimality an approximation of the previous round loss function to avoid the NP-hardness of the original problem. We extend OSGA to a generic approximation function. We show that OSGA has a dynamic regret bound similar to the tightest bounds in online convex optimization with respect to the time horizon and the cumulative round optimum variation. For instances where no approximation exists or a computationally simpler implementation is desired, we design the online submodular projected gradient descent (OSPGD) by leveraging the Lovaśz extension. We obtain a regret bound that is akin to the conventional online gradient descent (OGD). Finally, we numerically test our algorithms in two power system applications: fast-timescale demand response and real-time distribution network reconfiguration.