Multiparametric programmingThis example requires the Multi-Parametric Toolbox (MPT). YALMIP can be used to calculate explicit solutions of linear and quadratic programs by interfacing the Multi-Parametric Toolbox (MPT). This chapter assumes that the reader is familiar with parametric programming and the basics of MPT. Standard example.Consider the following simple quadratic program in the decision variable z, solved for a particular value on a parameter x.
To obtain the parametric solution with respect to x, we call the
function
The first output is an MPT structure. In accordance with MPT syntax, the optimizer for the parametric value is given by the following code.
By using more outputs from
The function now returns solutions using YALMIPs
nonlinear operator framework. To retrieve the solution for a particular
parameter, simply use
Some of the plotting capabilities of MPT are overloaded for the piecewise functions.
More about the output later. MPC exampleDefine numerical data for a linear system, prediction matrices, and variables for current state x and the future control sequence U, for an MPC problem with horizon 5.
The future output predictions are linear in the current state and the control sequence.
We wish to minimize a quadratic cost, compromising between small input and outputs.
The input variable has a hard constraint, and so does the output at the terminal state.
We seek the explicit solution U(x) over the exploration set |x|≤1.
The explicit solution U(x) is obtained by calling
The explicit solution can, e.g, be plotted (see the MPT manual informationon the solution structure)
The following piece of code calculates the explicit MPC controller with an worst-case L∞ cost instead (i.e. worst case control/output peak along the predictions).
This example enables us to introduce the overloading of the projection functionality in MPT. In MPC, only the first input, U(1), is of interest. What we can do is to project the whole problem to the parametric variable x, the objective function t, and the variable of interest, U(1). The following piece of code projects the problem to the reduced set of variables, and solves the multi-parametric LP in this reduced space (not necessarily an efficient approach though, projection is very expensive, and we can easily end up with a problem with many constraints in the reduced variables.)
To check that the two solutions actually coincide, we compare the value functions and conclude that they are essentially the same.
Since the objective function is t, the optimal t should coincide with the value function. The optimal t in the projected problem was requested as the second optimizer
In the code above, we used the pre-constructed function The first approach explicitly generates future states using the given current state and future inputs (note that the solution not is exactly the same as above due to a small difference in indexing logic.)
The second method introduced new decision variables for both future states and connect these using equality constraints.
This second method is less efficient, since it has a lot more decision variables. However, in some cases, it is the most convenient way to model a system (see the PWA examples below for similar approaches), and the additional decision variables are removed anyway during a pre-solve process YALMIP applies before calling the multi-parametric solver. Parametric programs with binary variables and equality constraintsYALMIP extends the parametric algorithms in MPT by adding a layer to enable binary variables and equality constraints. We can use this to find explicit solutions to, e.g., predictive control of PWA (piecewise affine) systems. Let us find the explicit solution to a predictive control problem, where the gain of the system depends on the sign of the first state. This will be a pretty advanced example, so let us start slowly by defining the some data.
To simplify the code and the notation, we create a bunch of state and control vectors in cell arrays
We now run a loop to add constraints on all states and inputs. Note the use of binary variables define the PWA dynamics, and the recommended use of bounds to improve big-M relaxations)
The parametric variable here is the current state x{1}. In this optimization problem, there are a lot of variables that we have no interest in. To tell YALMIP that we only want the optimizer for the current state u{1}, we use a fifth input argument.
To obtain the optimal control input for a specific state, we use
The optimal cost at this state is available in the value function
To convince our self that we have a correct parametric solution, let us compare it to the solution obtained by solving the problem for this specific state.
Dynamic programming with LTI systemsThe capabilities in YALMIP to work with piecewise functions and parametric programs enables easy coding of dynamic programming algorithms. The value function with respect to the parametric variable for a parametric linear program is a convex PWA function, and this is the function returned in the fourth output. YALMIP creates this function internally, and also saves information about convexity etc, and uses it as any other nonlinear operator (see more details below). For binary parametric linear programs, the value function is no longer convex, but a so called overlapping PWA function. This means that, at each point, it is defined as the minimum of a set of convex PWA function. This information is also handled transparently in YALMIP, it is simply another type of nonlinear operator. The main difference between the two function classes is that the second class requires introduction of binary variables when used. Note, the algorithms described in the following sections are mainly intended for with (picewise) linear objectives. Dynamic programming with quadratic objective functions give rise to problems that are much harder to solve, although it is supported. To illustrate how easy it is to work with these PWA functions, we can solve predictive control using dynamic programming, instead of setting up the whole problem in one shot as we did above. As a first example, we solve a standard linear predictive control problem. To fully understand this example, it is required that you are familiar with predictive control, dynamic programming and parametric optimization.
Now, instead of setting up the problem for the whole prediction horizon, we only set it up for one step, solve the problem parametrically, take one step back, and perform a standard dynamic programming value iteration.
Notice the minor changes needed compared to the one shot solution. Important to understand is that the value function at step k will be a function in x{k}, hence when it is used at k-1, it will be a function penalizing the predicted state. Note that YALMIP automatically keep track of convexity of the value function. Hence, for this example, no binary variables are introduced along the solution process (this is why we safely can omit the use of bounds). To study the development of the value function, we can easily plot them.
The optimal control input can also be plotted.
Of course, you can do the same thing by working directly with the numerical MPT data.
Why not solve the problem with a worst-case L∞ cost! Notice the non-additive value iteration! Although this might look complicated using a mix of maximums, norms and piecewise value-functions , the formulation fits perfectly into the nonlinear operator framework in YALMIP.
Dynamic programming with PWA systemsAs mentioned above, the difference between the value function from a parametric LP and a parametric LP with binary variables is that convexity of the value function no longer is guaranteed. In practice, this means that (additional) binary variables are required when the the value function is used in an optimization problem. This is done automatically in YALMIP through the nonlinear operator framework, but it is extremely important to realize that the value function from a binary problem is much more complex than the one resulting from a standard parametric problem. Nevertheless, working with the objects is easy, as the following example illustrates. In this case, we solve the dynamic programming problem for our PWA system
Just as in the LTI case, we set up the problem for the one step case, and use the value function from the previous iteration.
Plotting the final value function clearly reveals the nonconvexity.
Behind the scenes and advanced useThe first thing that might be a bit unusual to the advanced user is
the piecewise functions that YALMIP returns in the fourth and fifth
output from
The pwf command will recognize the MPT
solution structure and create a PWA function based on the
fields Pn, Bi and Ci. The dedicated
nonlinear operator is implemented in the file If the field Ai is non-empty (solution obtained from
a multi-parametric QP), a corresponding PWQ function is created ( To create a PWA function representing the optimizer, two things have to be changed. To begin with, YALMIP searches for the Bi and Ci fields, but since we want to create a PWA function based on Fi and Gi fields, the field names have to be changed. Secondly, the piecewise optimizer is typically not convex, so a general PWA function is created instead (requiring 1 binary variable per region if the variable later actually is used in an optimization problem.)
A third important case is when the solution structure returned from
This is only recommended if you just intend to plot or investigate the value function. Typically, if you want to continue computing with the result, i.e. use it in another optimization problem, as in the dynamic programming examples above, it is recommended to keep the overlapping solutions. To model a general PWA function, 1 binary variable per region is needed. However, by using a dedicated nonlinear operator for overlapping convex PWA functions, only one binary per PWA function is needed.
As we have seen in the examples above, the PWA and PWQ functions can be plotted. This is currently nothing but a simple hack. Normally, when you apply the plot command, the corresponding double values are plotted. However, if the input is a simple scalar PWA or PWQ variable, the underlying MPT structures will be extracted and the plot commands in MPT will be called. |