The convex optimization problem

Definition: Convex optimization problem

An optimization problem is called convex whenever it is of the form where is convex and is convex.

Theorem

Let be the set of all optimal solutions to . Then is convex.

Proof:
Let be optimal solutions with optimal value . Then but from optimality we also know , so we have equality.

Corollary

is either empty, contains one point, or infinitely many points.

Proof:
Whenever contains two distinct points, the line segment between them is contained and consists of infinitely many points.

Theorem

Suppose in is strictly convex. Then there is at most one optimal solution.

Proof:
Suppose are distinct optimal solutions with optimal value . Then, for every , which contradicts strict convexity.

Theorem

Suppose is a local minimizer of in . Then is a global minimizer.

Proof:
Suppose there exists a with . Let be a neighbourhood of in which is a global minimizer. Then there exists a such that But we have since , contradicting the local minimality of .

Theorem

Suppose in is continuously differentiable. Then an interior point is a global minimizer if and only if .

Proof:
Suppose there is some with . Then for all . Taking the limit as we get contradicting that . Thus is a global minimizer. If is a global minimizer it is a local minimizer, from which it follows from a previous theorem that .

Theorem

A point is optimal to if and only if there does not exist a feasible descent direction for at .

Proof:
If there exists a feasible descent direction it is clear that is not optimal. Now suppose is not optimal, and let such that . Then for every , so choosing we get as a feasible descent direction.