No Arabic abstract
This paper presents competitive algorithms for a novel class of online optimization problems with memory. We consider a setting where the learner seeks to minimize the sum of a hitting cost and a switching cost that depends on the previous $p$ decisions. This setting generalizes Smoothed Online Convex Optimization. The proposed approach, Optimistic Regularized Online Balanced Descent, achieves a constant, dimension-free competitive ratio. Further, we show a connection between online optimization with memory and online control with adversarial disturbances. This connection, in turn, leads to a new constant-competitive policy for a rich class of online control problems.
This paper studies the impact of imperfect information in online control with adversarial disturbances. In particular, we consider both delayed state feedback and inexact predictions of future disturbances. We introduce a greedy, myopic policy that yields a constant competitive ratio against the offline optimal policy with delayed feedback and inexact predictions. A special case of our result is a constant competitive policy for the case of exact predictions and no delay, a previously open problem. We also analyze the fundamental limits of online control with limited information by showing that our competitive ratio bounds for the greedy, myopic policy in the adversarial setting match (up to lower-order terms) lower bounds in the stochastic setting.
We study the control of a linear dynamical system with adversarial disturbances (as opposed to statistical noise). The objective we consider is one of regret: we desire an online control procedure that can do nearly as well as that of a procedure that has full knowledge of the disturbances in hindsight. Our main result is an efficient algorithm that provides nearly tight regret bounds for this problem. From a technical standpoint, this work generalizes upon previous work in two main aspects: our model allows for adversarial noise in the dynamics, and allows for general convex costs.
Robust control is a core approach for controlling systems with performance guarantees that are robust to modeling error, and is widely used in real-world systems. However, current robust control approaches can only handle small system uncertainty, and thus require significant effort in system identification prior to controller design. We present an online approach that robustly controls a nonlinear system under large model uncertainty. Our approach is based on decomposing the problem into two sub-problems, robust control design (which assumes small model uncertainty) and chasing consistent models, which can be solved using existing tools from control theory and online learning, respectively. We provide a learning convergence analysis that yields a finite mistake bound on the number of times performance requirements are not met and can provide strong safety guarantees, by bounding the worst-case state deviation. To the best of our knowledge, this is the first approach for online robust control of nonlinear systems with such learning theoretic and safety guarantees. We also show how to instantiate this framework for general robotic systems, demonstrating the practicality of our approach.
We consider optimization problems for (networked) systems, where we minimize a cost that includes a known time-varying function associated with the systems outputs and an unknown function of the inputs. We focus on a data-based online projected gradient algorithm where: i) the input-output map of the system is replaced by measurements of the output whenever available (thus leading to a closed-loop setup); and ii) the unknown function is learned based on functional evaluations that may occur infrequently. Accordingly, the feedback-based online algorithm operates in a regime with inexact gradient knowledge and with random updates. We show that the online algorithm generates points that are within a bounded error from the optimal solution of the problem; in particular, we provide error bounds in expectation and in high-probability, where the latter is given when the gradient error follows a sub-Weibull distribution and when missing measurements are modeled as Bernoulli random variables. We also provide results in terms of input-to-state stability in expectation and in probability. Numerical results are presented in the context of a demand response task in power systems.
The wake effect is one of the leading causes of energy losses in offshore wind farms (WFs). Both turbine placement and cooperative control can influence the wake interactions inside the WF and thus the overall WF power production. Traditionally, greedy control strategy is assumed in the layout design phase. To exploit the potential synergy between the WF layout and control so that a system-level optimal layout can be obtained with the greatest energy yields, the layout optimization should be performed with cooperative control considerations. For this purpose, a novel two-stage WF layout optimization model is developed in this paper. Cooperative WF control of both turbine yaw and axis-induction are considered. However, the integration of WF control makes the layout optimization much more complicated and results in a large-scale nonconvex problem, hindering the application of current layout optimization methods. To increase the computational efficiency, we leverage the hierarchy and decomposability of the joint optimization problem and design a decomposition-based hybrid method (DBHM). Case studies are carried out on different WFs. It is shown that WF layouts with higher energy yields can be obtained by the proposed joint optimization compared to traditional separate layout optimization. Moreover, the computational advantages of the proposed DBHM on the considered joint layout optimization problem are also demonstrated.