Comment on page
Convex Optimization
Convexity can be preserved by some operations.
Theorem 10, Theorem 11 are important because they allow us to prove sets are convex using sets that we know are convex. For example, Theorem 11 tells us that a projection of a convex set onto a subspace must also be convex since projection is a linear operator.
Loosely, convexity means that the function is bowl shaped since a line connecting any two points on the function is above the function itself. A concave function is simply one where
is convex, and these appear like a “hill”. Because convex functions are bowl shaped, they must be
outside their domain.
Just like convex sets, some operations preserve convexity for functions.
A similar property to Theorem 11 exists for convex functions.
We can also look at the first and second order derivatives to determine the convexity of a function.
Theorem 15 can be understood geometrically by saying the graph of
is bounded below everywhere by its tangent hyperplanes.
Geometrically, the second-order condition says that
looks bowl-shaped.
Because of the nice geometry that convexity gives, optimization problems which involve convex functions and sets are reliably solveable.
Since the constraints form a convex set, Definition 32 is equivalent to minimizing a convex function over a convex set
.
Theorem 19 is why convex problems are nice to solve.
When problems are convex, we can define conditions that any optimal solution must satisfy.
Since the gradient points in the direction of greatest increase, the dot product of the gradient with the different between any vector and the optimal solution being positive means other solutions will only increase the value of
. For unconstrained problems, we can make this condition even sharper.
Conic programming is the set of optimization problems which deal with variables constrained to a second-order cone.
By Cauchy-Schwartz,
. This means that second order cones are convex sets since they are the intersection of half-spaces. In spaces 3-dimensions and higher, we can rotate these cones.
The rotated second-order cone can be interpreted as a rotation because the hyperbolic constraint
can be expressed equivalently as
A SOC constraint will confine
to a second order cone since if we let
and
, then
.
An SOC program is a convex problem since its objective is linear, and hence convex, and the SOC constraints are also convex.
A special case of SOCPs are Quadratic Programs. These programs have constraints and an objective function which can be expressed as a quadratic function. In SOCP form, they look like
Since they are a special case of SOCPs, Quadratic Programs are also convex.
To be a quadratic program, the matrix
must be positive semi-definite. If the
in the constraints, then we get a normal quadratic program.
Its SOCP form looks like
In the special case where
is positive definite and we have no constraints, then
Thus
If the matrix in the objective function of a quadratic program is 0 (and there are no quadratic constraints), then the resulting objective and constraints are affine functions. This is a linear program.
Since linear program is a special case of a quadratic program, it can also be expressed as an SOCP.
Because of the constraints, the feasible set of a linear program is a polyhedron. Thus linear programs are also convex.
Last modified 1yr ago