CVXPY Course at NASA

Instructors: Philipp Schiele, Steven Diamond, Parth Nobel, Akshay Agrawal
Term: June and July 2024

Syllabus

July 29: Nonconvex optimization examples

Handouts

July 22: Code generation for quadcopter control

Handouts

July 15: Geometric programming and aircraft design

Handouts

Homework

  1. Formulate and solve the wing sizing optimization problem discussed in class as a geometric program, using the attached homework notebook.

July 8: Regression and statistical estimation

Handouts

Homework

  1. Maximum likelihood estimation with exponentially distributed noise. We consider a linear measurement model

y_i = a_i^Tx + v_i, \quad i = 1, \ldots, m

where x \in \reals^n is a vector of parameters to be estimated, y_i \in \reals are the observed quantities, and v_i are the measurement errors or noise. We assume that v_i are independent, identitically distributed (IID) with density p on \reals.

The maximum-likelihood estimate is any optimal point for the problem

\begin{array}{ll} \text{maximize} & \sum_{i=1}^{m} \log p(y_i - a_i^Tx), \end{array}

with variable x.

Show how to solve this problem when the noise is exponentially distributed, with density

p(z) = \begin{cases} (1/a)e^{-z/a} & z \geq 0 \\ 0 & z < 0, \end{cases}

where a > 0.

  1. Comparing regularizers in regression. Complete the exercise in the attached homework notebook, in which you’ll compare and contrast solutions to an optimization problem using \ell_1-norm regularization versus \ell_2.

July 1: Sensitivity analysis and robust Kalman filtering

Handouts

Homework

  1. Sensitivity Analysis:

Consider the convex optimization problem:

\begin{array}{ll} \text{minimize} & f_0(x) \\ \text{subject to} & f_1(x) \leq s, \quad Ax = b, \end{array}

with variables x \in \mathbb{R}^n, parametrized by the real number s. Let \lambda^\star be an optimal dual variable (Lagrange multiplier) associated with the constraint f_1(x) \leq s_{\text{nom}}. Below we consider scenarios in which we change the value of s below or above the nominal value s_{\text{nom}}, and then solve the modified problem. We are interested in the optimal objective value of this modified problem, compared to the original one above.

For each of the following, choose the best response. (Please note that the words were carefully chosen.)

a. If \lambda^\star is large, then decreasing s below s_{\text{nom}}:

b. If \lambda^\star is large, then increasing s above s_{\text{nom}}:

c. If \lambda^\star = 0, then increasing s above s_{\text{nom}}:

  1. Robust Kalman Filtering:

Consider the following linear dynamical system: \begin{array}{ll} x_{t+1} &= A x_t + B w_t \\ y_t &= C x_t + v_t, \end{array} where x_t \in \reals^n is the vehicle’s state at time t \in \{0, \ldots, N-1\}, y_t \in \reals^r are the measurements, and w_t \in \reals^m are unobserved inputs, and v_t \in \reals^r is noise. The matrices A, B, and C determining the system are fixed. Because we suspect outliers in the measurements, we want to use a robust Kalman filter to estimate the state x_t. Implement the robust Kalman filter below in the accompanying notebook.

\begin{array}{ll} \text{minimize} & \sum_{t=0}^{N-1} \|w_t\|_2^2 + \tau \phi(v_t) \\ \text{subject to} & x_{t+1} = A x_t + B w_t \\ & y_t = C x_t + v_t, \end{array} where \phi is the Huber loss function (“cp.huber”), parameterized by M.

  1. Sensitivity analysis for portfolio optimization: Recall the basic portfolio optimization problem with variance constraint \begin{array}{ll} \text{maximize} & \mu^T x\\ \text{subject to} & x^T \Sigma x \leq \sigma^2, \quad p^T x = B, \end{array} In the notebook, we solve this problem for varying values of \sigma, tracing out the set of Pareto optimal solutions called the “efficient frontier”. To see how dual variables provide linear approximations to the efficient frontier, implement the missing code in the notebook.

June 24: Landing a rocket using model predictive control

Handouts

Homework

  1. For this question, we’re going to consider variations on the optimal trajectory planning from lecture.

    1. Add the glide slope constraint p_k^T e_3 \geq \tan \alpha \|p_k^T e_1, p_k^T e_2\|_2 to the trajectory planning problem.
    2. Add a regularization term to the trajectory planning problem that penalizes the height of the rocket to avoid hovering at high altitudes.
    3. Add a regularization term that penalizes deviations in the x and y directions to improve the approach angle of the rocket.
    4. Make the glide slope constraint a soft constraint by penalizing violations of the constraint in the objective function. Hint: Use the “pos” atom.
    5. Minimum time descent. Instead of minimizing the fuel consumption, we want to minimize the time it takes to land the rocket. Hint: You should solve a sequence of convex feasibility problems.

  2. Fitting a sphere to data. For this problem, we’re going to go back to something we discussed in week 2: changing variables to make nonconvex problems convex. Consider the problem of fitting a sphere \{x \in\reals^n \mid \|x-c\|_2 = r\} to m points u_1,\ldots, u_m\in \reals^n, by minimizing the loss function \sum_{i=1}^m \left( \|u_i - c\|_2^2 - r^2 \right)^2 over the variables c \in\reals^n, r\in\reals.

    1. Explain how to solve this problem using convex optimization by changing variables from (c,r) to (c,t), with t=r^2-\|c\|_2^2. It is not ipso facto obvious that this transformation is valid: if t < -\|c\|_2^2 than we can’t recover a valid r; that’s okay for now.
    2. Use your method to solve the problem instance with data given in the notebook named Spehere Fitting in Handouts, with n=2. Verify that for this problem data your change of variables is valid. Plot the fitted circle and the data points.
    3. Challenge question: Can you show analytically that the optimal solution of your problem in (a) always satisfies t \geq -\|c\|_2^2?

Note: Originally, we had missed a minus sign in front of \|c\|_2^2 in both inequalities.

June 17: Disciplined convex programming

Handouts

Homework

  1. Portfolio optimization. In this problem, we are going to discuss how to use a model of a market to maximize profit. Portfolio optimization is the backbone of quantitative finance and energy allocation.

    Imagine we have a budget B (dollars). We can purchase n different assets (e.g. stocks, bonds) with current prices p (dollars per unit), expected returns \mu (dollars per unit), and covariance \Sigma (dollars squared per unit squared). Your goal is to ensure the standard deviation of your portfolio to be less than S (dollars). We are only buying assets, not borrowing them, so we cannot “short” stocks and have a “long”-only portfolio. Lastly, we don’t want to end up over-invested in a single asset, so, let’s ensure we never put more than 5\% of our budget into a single asset.

    Using the data in the notebook (see Handouts) find the portfolio that maximizes expected returns.

  2. Diet problem. We are going to solve a simple diet problem. We are choosing nonnegative amounts x_1, \ldots, x_n of n different foods. One unit of food j has cost c_j and contains A_{ij} units of nutrient i. We want to minimize the total cost of the food, while ensuring that we get at least b_i units of nutrient i.

    Write down the optimization problem for the diet problem and solve it using the data in the notebook (see Handouts).

  3. Minimum fuel optimal control. We consider a linear dynamical system with state x(t) \in \reals^n, t=0, \ldots, N, and actuator or input signal u(t) \in \reals, for t=0, \ldots, N-1. The dynamics of the system is given by the linear recurrence x(t+1)=Ax(t) +bu(t), \quad t=0, \ldots, N-1, where A \in \reals^{n \times n} and b \in \reals^n are given. We assume that the initial state is zero, i.e., x(0)=0.

    The minimum fuel optimal control problem is to choose the inputs u(0), \ldots, u(N-1) so as to minimize the total fuel consumed, which is given by F = \sum_{t=0}^{N-1} f(u(t)), subject to the constraint that x(N)=x_\mathrm{des}, where N is the (given) time horizon, and x_\mathrm{des} \in \reals^n is the (given) desired final or target state. The function f:\reals \rightarrow \reals is the fuel use map for the actuator, and gives the amount of fuel used as a function of the actuator signal amplitude. In this problem we use f(a) = \left\{ \begin{array}{ll} |a| & |a| \leq 1\\ 2|a|-1 & |a| > 1. \end{array}\right. This means that fuel use is proportional to the absolute value of the actuator signal, for actuator signals between -1 and 1; for larger actuator signals the marginal fuel efficiency is half.

    1. Write down what the variables in your optimization problem are.
    2. Write down what constraints there are on the variables.
    3. Write down a DCP-compatible expression for the objective.
    4. Solve the problem with the following problem data:

A=\left [ \begin{array}{rrr} -1 & 0.4 & 0.8\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{array} \right], \qquad b=\left[ \begin{array}{c} 1\\ 0\\ 0.3\\ \end{array} \right], \qquad x_\mathrm{des}=\left[ \begin{array}{r} 7\\ 2\\ -6\\ \end{array} \right], \qquad N = 30. e. Plot the optimal actuator signal u(t) as a function of t.

June 10: Introduction to convex optimization and CVXPY

Handouts

Homework

  1. work on Problems 1 - 5 from the notebook (https://marimo.app/l/3s4nd6)
  2. analyze the following expressions as either DCP-compatible or not. Check your work with https://dcp.stanford.edu/analyzer
    1. sqrt(1 + 4 * square(x) + 16 * square(y)
    2. min(x, log(y)) - max(y, z)
    3. log(exp(2 * x + 3) + exp(4 * y + 5))
  3. play the DCP quiz at https://dcp.stanford.edu/quiz
  4. bonus problem 1: figure out how to write the non-DCP functions from q2 as DCP.
  5. bonus problem 2:

Fuel use as function of distance and speed. A vehicle uses fuel at a rate f(s), which is a function of the vehicle speed s. We assume that f: R \to R is a positive increasing convex function, with dom f = R_+. The physical units of s are m/s (meters per second), and the physical units of f(s) are kg/s (kilograms per second). Let g(d,t) be the total fuel used (in kg) when the vehicle moves a distance d ≥ 0 (in meters) in time t > 0 (in seconds) at a constant speed. Write g in DCP form. Hint: Check out the “perspective” atom.