Convex Optimization

Convex Set

A set where, for any two points inside it, the line segment connecting them lies entirely within the set.

Convex Function

A function whose graph always lies below the straight line connecting any two points on the graph; it curves upward like a bowl.

Convex Optimization Problem

An optimization problem with a convex objective function and a convex feasible set.

Feasible Set

The set of all variable values that satisfy the constraints of an optimization problem.

Objective Function

The function being minimized or maximized in an optimization problem.

Local Minimum

A point that has a smaller function value than all nearby points.

Global Minimum

The point with the smallest function value in the entire domain.

Affine Function

A function of the form f(x) = Ax + b; it is both convex and concave.

Indicator Function

A function that is 0 for points inside the feasible set and infinity for points outside it; used to combine constraints with the objective.

Strong Duality

A property where the optimal values of the primal and dual problems are equal.

Weak Duality

The property that the dual problem provides a lower bound on the primal problem’s optimal value.

Slater’s Condition

A condition ensuring strong duality for convex problems; it holds if there exists at least one point strictly inside the feasible set.

Nonnegative Weighted Sum

A combination of convex functions using nonnegative weights that remains convex.

Composition Rule

If f is convex and g(x) = f(Ax + b), then g is also convex.

Norm

A function that measures the size or length of a vector; every norm is convex.

Squared Norm

The function f(x) = ||x||²; it is convex and commonly used in optimization.

Convex Combination

A linear combination of two points x and y given by αx + (1−α)y, where α is between 0 and 1.

Convexity Theorem

States that if a function is convex, every local minimum is also a global minimum.