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.

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.

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 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.