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.