Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 9

Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 9

Optimization Concepts

  • Avoid treating CVX Pi coding assignments as a "monkey at a typewriter" exercise.
  • Focus on understanding the problem and the underlying concepts rather than blindly typing in code.
  • The course design emphasizes real-world problem-solving rather than theoretical concepts.

Duality in Optimization

  • Duality involves converting a problem into an equivalent problem, known as its dual.
  • Strong duality assumes that the optimal values of the primal and dual problems are the same.
  • Simple transformations can lead to radically different duals.
  • Patterns can be observed in dual problems, such as the appearance of conjugates and adjoints.
  • Partial dualization involves dualizing only a subset of the constraints.

Box-Constrained Problems

  • The box-constrained problem has an equivalent formulation where the box constraints are implicit in the objective function.
  • The Lagrangian dual of the box-constrained problem can be derived analytically, and the optimal value of the dual problem is related to the primal problem.

Generalized Inequalities

  • For problems with generalized inequalities, the Lagrangian dual is formed by taking the inner product of the inequality constraints with non-negative vectors in the dual cone.

Semi-Definite Programming

  • Semi-definite programming involves minimizing a linear function subject to linear matrix inequalities. The Lagrangian dual of a semi-definite program is another semi-definite program.

Duality for Feasibility Problems

  • Duality for feasibility problems, also known as theorems of the alternative, involves formulating a feasibility problem as minimizing zero subject to constraints. The optimal value of the primal problem is either zero or infinity, and the dual problem can be derived accordingly.

Penalty Functions

  • Penalty functions are used to approximate norms in optimization problems.
  • The L1 approximation is a penalty function that uses the absolute value of the residual.
  • The dead zone linear penalty function has a "dead zone" where the penalty is zero, and outside of that zone, the penalty grows linearly.
  • The log barrier penalty function closely matches the quadratic penalty function for small residuals but increases more rapidly for larger residuals.
  • The choice of penalty function depends on the specific problem being solved.

Least Norm Problems

  • Least Norm problems involve minimizing a norm subject to linear constraints.
  • In estimation problems, the goal is to find the most plausible solution when there are more unknowns than measurements.
  • In design problems, the goal is to minimize a cost function subject to constraints.

Regularized Approximation

  • Regularized approximation involves balancing the fit to the data with the size of the solution.


  • Applications of these concepts include minimum fuel trajectory design and missile guidance systems.
  • The speaker provides an example of optimal input design in control engineering, where the goal is to minimize tracking error, input magnitude, and input smoothness simultaneously.
  • The video discusses a control system that tracks an input signal.
  • The goal is to design a controller that tracks the input signal well while minimizing tracking error, input wiggliness, and input size.

Overwhelmed by Endless Content?