# 03-Convex-Optimization-Problems

6 minute read

This is the third notebook of the series going through Convex Optimizaion. The topics here are following MOOC Convex Optimization course by Stephen Boyd at Stanford.

### Convex Optimization in standard form

A convex optimization problem is one of the form:

\begin{align} \text{minimize }& f_0(x)\\ \text{subject to }& f_i(x) \leq 0, i=1,\dots,m\\ & a_i^Tx=0 , i=1,\dots,p\\ \end{align}

where $f_0,\dots,f_m$ are convex functions and equality constraints are affine.

• feasible set of a convex optimization problem is convex: $$D=\bigcap_{i=0}^m \textbf{dom }f_i \cap \bigcap_{j=0}^p \textbf{dom }h_j$$

### Local and global optima

For any convex optimization problem, any locally optimal point is also (globally) optimal.

Suppose:

$$f_0(x)=\text{inf }\{f_0(z)|z \text{ feasible }, \parallel z-x \parallel_2 \leq R\}$$ for some $R$. Suppose $x$ is not globally optimal. Then there is a feasible $y$ such that $f_0(y)<f_0(x)$ and $$\parallel y-x\parallel_2>R$$. Now consider the point $z$: $z=(1-\theta)x+\theta y, \theta=\frac{R}{2\parallel y-x\parallel_2}$ and therefore $\parallel z-x\parallel_2=R/2<R$.

By convexity of $f_0$ we have: $f_0(z)\leq (1-\theta)f_0(x)+\theta f_0(y)<f_0(x)$ Which is a contradiction to earlier assumption and therefore there exist no feasible $y$ with $f_0(y)<f_0(x)$.

### Optimality criterion for differentiable $f_0$

Suppose $f_0$ in a convex optimization problem is differentiable, so that for all $x,y \in \textbf{dom } f_0$,

$f_0(y)\geq f_0(x)+\nabla f_0(x)^T(y-x)$

Let $X$ denote the feasible set,

$X=\{x \vert f_i(x) \leq 0,i=1,\dots,m,h_i(x)=0,i=1,\dots,p\}$

Then $x$ is optimal iff $x\in X$ and:

$\nabla f_0(x)^T(y-x)\geq 0 \text{ for all } y\in X$.

#### Problems with equality constraints only

\begin{align} \text{minimize }& f_0(x)\\ \text{subject to }& Ax=b\\ \end{align}

Based on the optimizality condition for $x$ we have: \begin{align} \nabla f_0(x)^T(y-x)\geq 0 & \text{ for all } y , Ay=b\\ \end{align}

Which can be shown that :

\begin{align} \nabla f_0(x)+A^T\nu=0 & \text{ for some }\nu \end{align}

This derives the Lagrange Multiplier optimality.

#### Minimization over nonnegative orthant

\begin{align} \text{minimize }& f_0(x)\\ \text{subject to }& x \succeq 0\\ \end{align}

Based on the optimizality condition for $$x \succeq 0$$ we have: \begin{align} \nabla f_0(x)^T(y-x)\geq 0 & \text{ for all } y , x \succeq 0\\ \end{align}

Which can be shown that holds when:

\begin{align} \nabla f_0(x)^T X=0\\ x\succeq 0,\nabla f_0(x)\succeq 0\\ \end{align}

Because both $$x$$ and $$\nabla f_0(x)$$ are nonnegative in every element therefore it must be the case that sparsity patterns of two vectors are complimentary.

### Equivalent convex problems

Two problems are (informally) equivalent if the solution of one is readily obtained from the solution of the other, and vice versa.

#### Eliminating equality constraints.

All equality constrainst are of the form:

\begin{align} Ax=b\\ \end{align}

which can be eliminated by finding a particular $x_0$ of $Ax=b$, and a mtrix F whose range is the nullspace of A.

\begin{align} \text{ minimize }&f_0(Fz+x_0)\\ \text{subject to }&f_i(Fz+x_0)\leq 0\\ \end{align}

#### Introducing equality constraints

\begin{align} \text{ minimize }&f_0(A_0x+b_0)\\ \text{subject to }&f_i(A_ix+b_i)\leq 0 & i=1\dots m\\ \end{align}

is equivalent to:

\begin{align} \text{ minimize(over x, y_i) }&f_0(y_0)\\ \text{subject to }&f_i(y_i)\leq 0 & i=1\dots m\\ & y_i=A_i x+b_i& i=0\dots m\\ \end{align}

#### Introducing slack variables for linear inequalities

\begin{align} \text{ minimize }&f_0(x)\\ \text{subject to }&a_i^Tx\leq b_i & i=1\dots m\\ \end{align}

is equivalent to:

\begin{align} \text{ minimize }&f_0(x)\\ \text{subject to }&a_i^Tx+ s_i= b_i & i=1\dots m\\ &s_i\geq 0,i=0\dots m \end{align}

#### epigraph form

Any convex optimization problem can be converted to epigraph form:

\begin{align} \text{minimize }& t\\ \text{subject to }& f_0(x)-t\leq 0\\ & f_i(x)\leq 0& i=1,\dots,m\\ &a_i^Tx=b_i& i=1,\dots,p\\ \end{align}

therefore linear objective is universal for convex optimization

#### Minimizing over some variables

\begin{align} \text{ minimize }&f_0(x_0,x_1)\\ \text{subject to }&f_i(x_1)\leq 0 & i=1\dots m\\ \end{align}

is equivalent

\begin{align} \text{ minimize }& \tilde{f}_0(x_1)\\ \text{subject to }&f_i(x_1)\leq 0 & i=1\dots m\\ \end{align}

where $$\tilde{f}_0(x_1)=inf_{x_2} f_0(x_0,x_1)$$

### Quasiconvex optimization

\begin{align} \text{ minimize }&f_0(x) && \text{quasiconvex function}\\ \text{subject to }&f_i(x)\leq 0 & i=0,\dots,m& \text{convex functions}\\ &Ax=b\\ \end{align}

For these problems $x$ is optimal if:

\begin{align} x \in X, \nabla f_0(x)^T(y-x)>0 \text{ for all } y \in X \backslash \{x\} \end{align}

Notes:

• The condition is only sufficient for optimality.
• The condition requires $$\nabla f_0(x)$$ be nonzero.

### Linear Programming

\begin{align} \text{ minimize }&c^Tx+d \\ \text{subject to }&Gx\leq 0 \\ &Ax=b\\ \end{align}

In [1]:

In [7]:

C:
[[7]
[8]
[9]]
b:
[10  8]
G:
[[2 3 2]
[1 1 2]]
optimal point:
[ 2.00e+00]
[ 5.40e-07]
[ 3.00e+00]


In [8]:

#### Chebyshev center of polyhedron

Chebyshev center of

$P=\{x\vert a_i^Tx\leq b_i,i=1\dots m\}$

is center of largest inscribed ball:

$B=\{x_c+u \vert \parallel u \parallel_2 \leq r \}$

$a_i^T x\leq b_i$ for all $x \in B$ iff: $\text{sup } {a_i^T(x_c+u) \vert \parallel u \parallel_2 \leq r }=a_i^Tx_c+r \parallel a_i \parallel_2 \leq b_i$ hence: \begin{align} \text{ maximize }&r \\ \text{subject to }&a_i^Tx_c+r\parallel a_i \parallel_2 \leq b_i & i=1\dots m \\ \end{align}

In [4]:

0.447213535807
[-9.50e-08]
[-6.87e-18]


### Quadratic Programming

\begin{align} \text{ minimize }&1/2x^TP x+q^T x +r\\ \text{subject to }&Gx\leq h \\ &Ax=b\\ \end{align}

$P \in S_{+}^n$ and therefore objective is convex.

• Least square is an example of QP:
\begin{align} \text{ minimize }&\parallel Ax-b\parallel_2^2 \\ \text{subject to }&Gx\leq h \\ &Ax=b\\ \end{align}
\begin{align} \parallel Ax-b\parallel_2^2 &= (Ax-b)^T(Ax-b)\\ &=(x^TA^T-b^T)(Ax-b)\\ &=x^TA^TAx-x^TA^Tb-b^TAx+b^Tb \end{align}

In [5]:

Optimal Point:
[ 4.92e+00]
[ 2.71e+00]


Tags:

Categories:

Updated: