This is the live blog of Lecture 22 of my graduate class “Convex Optimization.” A Table of Contents is here.
Given their mutual background in control and dynamical systems, It’s curious that Boyd and Vandenberghe have minimal coverage of control theory in their book. There are control applications scattered in the exercises but not central coverage. Optimal control gets two pages in Chapter 10, and it’s mostly to highlight the banded structure of the associated KKT system.
It’s particularly curious because one of the most touted cvx success stories is the use of cvxgen in the control of Space X rockets. Written by Boyd’s advisee Jacob Mattingley, cvxgen generates fast code to solve disciplined quadratic programming. Beyond cvxgen, control engineers remain some of the biggest consumers of convex optimization methods. The first half of Predictive Control for Linear and Hybrid Systems by Borrelli, Bemporad, and Morari covers optimization methods.
Moreover, in the 20 years since the publication of their book, there’s been a renewed interest in control and its applications as people have pushed the limits of reinforcement learning. A little taste of control in an optimization class can help contextualize some of the jargon and methods used in modern “learning robotic” systems.
It’s worth a week exploring why optimization is central to modern control systems. Fortunately, Boyd has taught control theory before, and his course materials are fantastic. One of these, EE 363, has excellent lecture notes. I’ll go through the first couple of lectures this week, leaning on the connection to optimization. I’ve also written about control extensively on this blog. It’s a favorite topic of mine, and one I’m always happy to teach.
Now, what can we do in two lectures? That’s a fun pedagogical question, and we shall see how it goes this week.
The optimal control problem concerns steering a system’s configuration over time by applying appropriate inputs. At every time, we can record a list of measurements of the system, called outputs and the set of inputs we are currently executing to steer the system. The cost of the optimization problem is a function of the time history, or trajectory, of the inputs and outputs.
For example, we might want a vehicle to follow a path with a particular velocity using minimal power consumption. The measurements here are the position and velocity, and the input is the associated power consumption. The objective will measure deviation from the trajectory and the total amount of power consumption.
Another canonical example comes from supply chains. Here, the measured outputs are the amount of a product available on shelves today. The objective function concerns how much revenue a store makes for a particular product, how much it costs to hold an amount of supply in stock, how much the store loses due to opportunity cost if they understock, and how much it costs to resupply. The outputs here are the amounts of products in stock. The inputs are the daily amounts of restocking. Additionally, the purchases are uncertain inputs out of the control of the store. These must be modeled and forecast.
Control problems are constrained by dynamics. The system under control has a set of internal states that govern its behavior. The dynamical model of the system asserts that the next state is a function only of the current state and current input. An optimal control problem aims to minimize the cost of a trajectory subject to the dynamical laws relating inputs and states.
Dynamical laws are equality constraints. This class has taught us that the only equality constraints that generically result in convex constraint sets are linear. Hence, we should not be surprised that the most common dynamical models are linear as well. They assert that the future state is a linear function of the current state and input. Not all dynamical systems are linear, of course, but the supply chain example I listed above is. Newton’s Laws are also linear. Many nonlinear problems, including those in vehicle dynamics problems, can be well approximated by linear dynamics in reasonable operating regimes.
For the cost function, a common modeling constraint is that the objective decomposes into a sum of costs for every time step of the trajectory. This is not a necessary assumption for convexity, but this assumption guarantees that the optimal control problem can be solved in time scaling linearly with the length of the trajectory. Without a separable cost function, the optimal control problem may require cubic time in this length, and such algorithmic scaling quickly becomes prohibitive.
Algorithmic concerns tend to tie our hands in control modeling. For the sake of computational efficiency, our texts advise focusing on linear systems and separable costs. These modeling restrictions provide a crutch to make optimization algorithms work, but you can land giant rockets with such structured optimization problems. These constraints are more freeing than they appear.
There’s another reason why we can get away with linear models in control problems: feedback. While you can plan over a long trajectory, modeling errors and unforeseen disturbances in the environment can quickly ruin your plans. The solution in modern controls is constant replanning. You use the optimal control problem to make an optimal plan subject to your forecast of what might happen given your model of dynamics and disturbances. You take a single step and then see what actually happens with the unforeseen disturbances and the states. You replan from there. This constant replanning, called Model Predictive Control, helps you correct for unanticipated behaviors. The art of design in model predictive control is understanding what you should forecast and for how long in order to engineer good performance. But the mechanics of model predictive control follow immediately from what we’ve studied in our semester of convex optimization.
Newton laws are linear ? Big if true! Newton's law of gravitation (an application of second law) is highly nonlinear. In fact, it is SO nonlinear it led to creation of the field nonlinear dynamics, concept of chaos, and dynamical systems theory (via the three-body problem of Poincare).