Convex Optimization Problems

Optimization Problem

Definition

Def (General) Optimization Problem

Def Feasible Point A point is feasible if and it satisfies the constraints.

Def Solution A solution, or optimal point, has the smallest value of among all feasible .

Def Optimal Value The optimal value of an optimization problem is $$p^\star=\inf_{x\in\mathcal{D}}\left{f_0(x) \left| \begin{array}{ll}f_i(x)\leq0,&i=1,\ldots,m\h_i(x)=0,&i=1,\ldots,p\end{array}\right. \right}$$$p^\star = ∞$ if the problem is infeasible.

Def Locally Optimal A point is locally optimal if there is an such that is optimal for

Def Equivalent Optimization Problems Two problems are equivalent if the solution of one is readily obtained from the solution of the other, and vice-versa.

Convex Optimization Problem

Def Convex Optimization Problem A optimization problem is convex if are convex and are affine, often written as . A optimization problem is quasiconvex if is quasiconvex, are convex and are affine, often written as .

Prop An optimization problem is convex iff the objective function is convex and the feasible set is also convex.

Prop Any local minimum of a convex problem is (globally) optimal. Proof

Thrm Optimality Criterion for Differentiable Objective For an optimization problem with differentiable objective, is optimal if and only if it is feasible and for all feasible .

Corollary For a unconstrained problem, is optimal if and only if

Corollary For an equality constrained problem, is optimal if and only if there exists a such that Equivalently, is orthogonal to the null space of .

Linear Program (LP)

Def Linear Program Linear program is a convex problem with affine objective and constraint functions:

Def Chebyshev Center Chebyshev centre of a polyhedron is the center of the largest inscribed ball

Def Linear-Fractional Program The linear-fractional program is of the form:where .

Prop Linear-fractional program is quasiconvex.

Prop The linear-fractional program is equivalent to the following linear program:

Def Generalised Linear-Fractional Program The generalised linear-fractional program is a a quasiconvex optimization problem to minimize the objective:

Quadratic Program (QP)

Def Quadratic Program where , so objective is a convex quadratic.

Def Quadratically Constrained Quadratic Program (QCQP) where , objective and constraints are convex quadratic. If then the feasible region is the intersection of m ellipsoids and an affine set.

Def Second-order Cone Program (SOCP) where .

Prop For all LP and QCQP, exists some SOCP such that they are equivalent. i.e. SOCP is more general than QCQP and LP.

Def Robust Linear Programming The parameters in optimization problems are often uncertain, hence we introduce probability here:

Geometric Program (GP)

Def Monomial Function A monomial function is defined with the following form:

Def Posynomial Function A posynomial function is defined as sum of monomials:

Def Geometric Programming with posynomial, monomial.

Thrm Geometric programming problem is equivalent to the following convex problem:

Def Spectral Radius Suppose is a matrix and are its eigenvalues, the spectral radius is defined as:

Generalized Inequality Constraints

Def Generalized Convex Optimization Problem Convex problem with generalized inequality constraints: where is convex, is -convex with respect to proper cone .

Semidefinite Program (SDP)

Def Semidefinite Program with .

Optimal and Pareto Optimal Points

Def Pareto Optimal For some generalised optimization problem, suppose . Feasible is optimal if is the minimum value of . Feasible is Pareto optimal if is a minimal value of .