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

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

Convex Optimization

  • Convex optimization is a mathematical field that is at least 120 years old and was well-developed by the 1970s.
  • Practical applications took off in the 1940s with the development of computers.
  • Early applications include designing lightweight structures in aerospace and designing filters in electrical engineering.
  • In the late 1990s and early 2000s, convex optimization became widely used in control, signal processing, communications, statistics, and machine learning.
  • Today, convex optimization methods are used in training neural networks and solving non-convex problems.

Convex Sets

  • A convex set is a set where any two points in the set have a clear line of sight to each other.
  • An affine set is a set that contains the line through any two distinct points in the set.
  • A convex combination is a linear combination of vectors with all the coefficients non-negative.
  • The convex hull of a set is the set of all convex combinations of points from that set.
  • A conic combination is a linear combination of vectors with non-negative coefficients.
  • Hyperplanes and half-spaces are both convex sets.
  • Balls and ellipsoids are also convex sets.
  • Polyhedra are the solution sets of a set of linear inequalities.
  • The positive semidefinite cone (PSD cone) is the set of symmetric matrices with non-negative eigenvalues.

Convex Functions

  • Convexity can be verified syntactically by constructing a set using operations that preserve convexity.
  • Apine functions (affine functions plus a constant) preserve convex sets.
  • Perspective functions (functions that divide an N+1 vector by its last entry) preserve images and inverse images of convex sets.
  • Linear fractional functions (affine functions divided by a scalar apine function) also preserve convex sets.

Generalized Inequalities

  • Generalized inequalities are defined using proper cones, which are closed, solid, and pointed convex cones.
  • The notation for generalized inequalities is similar to that of ordinary inequalities, but with a squiggly symbol to indicate that the inequality is with respect to a cone.
  • Unlike inequalities on real numbers, generalized inequalities for vectors do not have the property of total ordering.
  • In vector spaces, the concept of minimum bifurcates into two distinct concepts: minimum and minimal.
  • A point is a minimum element if everything else in the set is comparable to it and bigger.
  • A point is minimal if there's no other point in the set that is less than or equal to it, except itself.

Overwhelmed by Endless Content?