Ch5.Convex

Convex Set

Affine Set

Definition

一个集合$\mathcal{C}\subset {\mathbb{R}}^n$满足任意不同两点$x_1,x_2\in \mathcal{C},\theta \in \mathbb{R}$, 且$\theta x_1+(1-\theta )x_2\in \mathcal{C}$, 则这个集合是affine的

即, 如果任意两点连线表示的直线上的所有点都在这个set中, 那么这个set是affine set

这个定义可以扩展到多个点: $x_1,\cdots ,x_k$的affine combination ${\theta }_1{x}_1+\cdots +{\theta }_k{x}_k$ where ${\sum }_{i=1}^k{\theta }_i=1$也是属于affine set的.

Definition

1. affine dimension: 一个affine hull的维度定义为affine dimension

2. relative interior: 闭包仿射(closure affine C)的内部, 记作$\mathbf{relint}C=\{x\in C|B(x,r)\cap \mathbf{aff}C\subset C\text{ for some }r>0\}$

   其中$B(x,r)=\{y|\Vert y-x\Vert \le r\}$表示relative boundary

Convex Set

Definition

一个集合$\mathcal{C}\subset {\mathbb{R}}^n$满足任意不同两点$x_1,x_2\in \mathcal{C},\theta \in [0,1]$, 且$\theta x_1+(1-\theta )x_2\in \mathcal{C}$, 则这个集合是convex的

即, 如果任意两点连线上的所有点都在这个set中, 那么这个set是convex set

注意与affine set区分, affine set要求整个直线都在这个set里面, 但是convex只要求连线线段在set中

Definition

convex hull: $\mathbf{conv}C=\{{\theta }_1{x}_1+\cdots +{\theta }_k{x}_k|x_i\in C,{\theta }_i\ge 0,i=i,\cdots ,k,{\sum }_i{\theta }_i=1\}$

Cones

Definition

1. $\forall x\in C,\theta \ge 0$, 如果满足$\theta x\in C$, 那么C是cone, 或者non-negative homogeneous(非负齐次)
2. $\forall x_1,x_2\in C,{\theta }_1,{\theta }_2\ge 0$, 如果${\theta }_1{x}_1+{\theta }_2{x}_2\in C$, 那么$C$是convex cone
3. $\{{\theta }_1{x}_1+\cdots +{\theta }_k{x}_k|{\theta }_i\ge 0,x_i\in C,i=1,\cdots ,k\}$称为conic cone(锥包). 即所有点的conic combination的集合

Operation that Preserve Convexity

1. Insertion 如果$S_1,\cdots ,S_k$都是convex的, 那么$S_1\cap \cdots \cap S_k$也是convex的
2. affine function 如果$f:{\mathbb{R}}^n\mapsto {\mathbb{R}}^m$是affine的($f(x)=\mathbf{Ax}+\mathbf{b},\mathbf{A}\in {\mathbb{R}}^{m\times n},\mathbf{b}\in {\mathbb{R}}^m$)
3. perspective and linear-fractional function:
   • perspective function: $P(x,t)=\frac{x}{t},\text{dom}P=\{(x,t)|t\ge 0\}$
   • Linear-fractional function: $f(x)=\frac{\mathbf{Ax}+\mathbf{b}}{{\mathbf{c}}^{\top }\mathbf{x}+d},\text{dom}P=\{x|{\mathbf{c}}^{\top }\mathbf{x}+d>0\}$

Convex Function

Definition

convex functino:

$$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$$

examples:

in $\mathbb{R}$:

• $ax+b$
• $|x{|}^p$, $p\ge 1$
• $x^p$, $p\ge 1$ or $p\le 0$
• $e^{ax}$
• $x\log x$ Concave: $\log x$, $ax+b$, $x^p$ for $0\le p\le 1$

in ${\mathbb{R}}^n$:

• ${\mathbf{a}}^{\top }\mathbf{x}+b$
• $\Vert x{\Vert }_k$
• quadratic function: $f(x)={\mathbf{x}}^{\top }\mathbf{Px}+2{\mathbf{q}}^{\top }\mathbf{x}+r$ is concave if and only if $P⪯0$
• geometric mean: $f(x)={\left({\prod }_{i=1}^n{x}_i\right)}^{\frac{1}{n}}$ is concave on ${\mathbb{R}}_{++}^n$
• $\log {\sum }_i{e}^{x_i}$ is concave on ${\mathbb{R}}^n$
• $f(\mathbf{x},y)=\frac{{\mathbf{x}}^{\top }\mathbf{x}}{y}$ is concave on ${\mathbb{R}}^n\times {\mathbb{R}}_{++}$

in ${\mathbb{R}}^{n\times n}$:

• affine function: $f(\mathbb{X})=\text{tr}(\mathbb{AX})+b$ is concave and convex on ${\mathbb{R}}^{n\times n}$
• Logarithmic Determinant Function: $f(\mathbf{X})=\log \det \mathbf{X}$ is concave on ${\mathbb{S}}^n=\{\mathbb{X}\in {\mathbb{R}}^{n\times n}|\mathbf{X}⪰0\}$
• maximum eigenvalue function: $f(\mathbf{x})={\lambda }_{\text{max}}(\mathbf{X})={\sup }_{y\ne 0}\frac{{\mathbf{y}}^{\top }\mathbf{Xy}}{{\mathbf{y}}^{\top }\mathbf{y}}$ is convex on ${\mathbb{S}}^n$

Definition

epigraph: $\text{epi}f=\{(\mathbf{x},t)\in {\mathbb{R}}^{n+1}|\mathbf{x}\in \text{dom}f,f(\mathbf{x})\le t\}$

Restriction of a Convex Function to a Line

Theorem

let $f:{\mathbb{R}}^n\mapsto \mathbb{R}$ and $g:\mathbb{R}\mapsto \mathbb{R}$ is $g(t)=f(\mathbf{x}+t\mathbf{v})$.

$f$ is convex if and only if $g$ is convex for $\forall \mathbf{x}\in \text{dom}f,\mathbf{v}\in {\mathbb{R}}^n$

First and Second Order Condition

Gradient:

$$\nabla f(\mathbf{x})={\left[\begin{array}{ccc}\frac{\partial f(\mathbf{x})}{\partial x_1}& \cdots & \frac{\partial f(\mathbf{x})}{\partial x_n}\end{array}\right]}^{\top }\in {\mathbb{R}}^n$$

Hessian:

$${\nabla }^{2}f(\mathbf{x})={\left(\frac{{\partial }^{2}f(\mathbf{x})}{\partial x_i\partial x_j}\right)}_{ij}\in {\mathbb{R}}^{n\times n}$$

Definition

• First order condition: 有convex的domain的可微函数$f$, 当且仅当$f(\mathbf{y})\ge f(\mathbf{x})+\nabla f(\mathbf{x}{)}^{\top }(\mathbf{y}-\mathbf{x})$的时候是convex的
• Second order condition: convex domain的二次可微的函数$f$, 当且仅当${\nabla }^{2}f(\mathbf{x})⪰0$的时候是convex的

Some Other Convexity

Quasi-Convexity

一个函数$f:{\mathbb{R}}^n\mapsto \mathbb{R}$是quasi-convexity的, 当且仅当$\text{dom}f$是convex的且sublevel set $S_{\alpha }=\{x\in \text{dom}f|f(x)\le \alpha \}$对于任何$\alpha$都是convex的

Log-Convexity

$$f(\theta x+(1-\theta )y)\ge f(x{)}^{\theta }f(y{)}^{1-\theta }$$

Convexity w.r.t. Generalized Inequalities

$f:{\mathbb{R}}^n\mapsto \mathbb{R}$如果$\text{dom}f$是convex的且满足

$$\forall \mathbf{x},\mathbf{y}\in \text{dom}\mathbf{f},0\le \theta \le 1,\mathbf{f}(\theta \mathbf{x}+(1-\theta )\mathbf{y}){⪯}_K\theta \mathbf{f}(\mathbf{x})+(1-\theta )\mathbf{f}(\mathbf{y})$$

那么称$f$是K-convex的

Convex Problem

Standard form:

$$\begin{array}{ccc}\text{minimize}& f_0(x)& \\ \text{subject to}& f_i(x)\le 0& i=1,\cdots ,m\\ & h_i(x)=0& i=1,\cdots ,p\end{array}$$

feasibility:

• 如果一个点$x\in \text{dom}f$满足所有的constraints, 那么称这个点是feasible的. 否则是infeasible
• 如果一个问题, 至少有一个点是feasible的, 那么称该问题为feasible的. 否则是infeasible

optimal:

$$p^{\ast }=\inf \{f_0(x)|f_i(x)\le 0,i=1,\cdots ,m,h_i(x)=0,i=1,\cdots ,p\}$$

• 如果问题是infeasible的, 那么$p^{\ast }=\infty$
• 如果问题是无边界的(unbounded below), 那么$p^{\ast }=-\infty$

Stationary Point

Definition

如果$\nabla f(\mathbf{x})=0$, 那么称$\mathbf{x}$为stationary point

Theorem

1. 如果一个stationary point $\mathbf{x}$, 对于其neighborhood $\mathcal{B}\subset {\mathbb{R}}^n$, 满足$f(\mathbf{y})\ge f(\mathbf{x}),\forall \mathbf{y}\in \mathcal{B}$, 那么$\mathbf{x}$是local minimization
2. 如果一个stationary point $\mathbf{x}$, 有$\forall \mathbf{y}\in \text{dom}f$, 满足$f(\mathbf{y})\ge f(\mathbf{x})$, 那么$\mathbf{x}$是global minimization
3. 如果一个stationary point $\mathbf{x}$, 对于其neighborhood $\mathcal{B}\subset {\mathbb{R}}^n$, 满足$f(\mathbf{z})\le f(\mathbf{x})\le f(\mathbf{y}),\mathbf{y},\mathbf{z}\in \mathcal{B}$, 并且${\lambda }_{\text{min}}({\nabla }^{2}f(\mathbf{x}))\le 0$ 那么称$\mathbf{x}$为Saddle point

Convex Optimization Problem

standard form:

$$\begin{array}{ccc}\text{minimize}& f_0(x)& \\ \text{subject to}& f_i(x)\le 0& i=1,\cdots ,m\\ & \mathbf{Ax}=\mathbf{b}& \end{array}$$

其中, $f_0,f_1,\cdots ,f_m$都是convex的. 等式约束(equality constraints)都是affine的

对于一个convex problem, 其local optimal就是global optimal.

Theorem

一个可行解(feasible point)$\mathbf{x}$是optimal的 当且仅当

$$\nabla f(\mathbf{x}{)}^{\top }(\mathbf{y}-\mathbf{x})\ge 0,\forall \text{ feasible }y$$

Quasi-Convex Optimization Problem

standard form:

$$\begin{array}{ccc}\text{minimize}& f_0(x)& \\ \text{subject to}& f_i(x)\le 0& i=1,\cdots ,m\\ & \mathbf{Ax}=\mathbf{b}& \end{array}$$

其中, $f_0$是Quasi-Convexity的, $f_1,\cdots ,f_m$都是convex的. 等式约束(equality constraints)都是affine的

将$f_0$使用epigraph ${\varphi }_t(x)$表示:

$$f_0(x)\le t\iff {\varphi }_t(x)\le 0$$

e.g.: Assume $p(x)$ is convex, $q(x)$ is concave and $p(x)\ge 0$, $q(x)>0$.

$$f(x)=\frac{p(x)}{q(x)}\iff {\varphi }_t(x)=p(x)-tq(x)$$

for $t\ge 0$, ${\varphi }_t(x)$ is convex in $x$ $\frac{p(x)}{q(x)}\le t$ if and only if ${\varphi }_t(x)\le 0$

Some Other Solver

LP(Linear Programming)

$$\begin{array}{cc}\text{minimize}& {\mathbf{c}}^{\top }\mathbf{x}+d\\ \text{subject to}& \mathbf{Gx}\le \mathbf{h}\\ & \mathbf{Ax}=\mathbf{b}\end{array}$$

Convex Problem: affine的objective function and constraints.

QP(Quadratic Programming)

$$\begin{array}{cc}\text{minimize}& \frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Px}+{\mathbf{q}}^{\top }\mathbf{x}+r\\ \text{subject to}& \mathbf{Gx}\le \mathbf{h}\\ & \mathbf{Ax}=\mathbf{b}\end{array}$$

convex problem: assume $P\in {\mathbb{S}}_{+}^n⪰0$, convex quadratic objective function and affine constraints

QCQP(Quadratically Constrained QP)

$$\begin{array}{ccc}\text{minimize}& \frac{1}{2}{\mathbf{x}}^{\top }{\mathbf{P}}_0\mathbf{x}+{\mathbf{q}}_0^{\top }\mathbf{x}+r_0& \\ \text{subject to}& \frac{1}{2}{\mathbf{x}}^{\top }{\mathbf{P}}_{\mathbf{i}}\mathbf{x}+{\mathbf{q}}_i^{\top }\mathbf{x}+r_i\le 0& i=1,\cdots ,m\\ & \mathbf{Ax}=\mathbf{b}& \end{array}$$

convex problem: assume $P\in {\mathbb{S}}_{+}^n⪰0$, convex quadratic objective function and constraints

SOCP(Second-Order Cone Programming)

$$\begin{array}{ccc}\text{minimize}& {\mathbf{f}}^{\top }\mathbf{x}& \\ \text{subject to}& \Vert {\mathbf{A}}_i\mathbf{x}+{\mathbf{b}}_i\Vert \le {\mathbf{c}}_i^{\top }\mathbf{x}+{\mathbf{d}}_i& i=1,\cdots ,m\\ & \mathbf{Fx}=\mathbf{g}& \end{array}$$

convex problem: linear objective and second-order cone constraints

• 如果${\mathbf{A}}_i$是行向量, 那么会退化成LP(Linear Programming)
• 如果${\mathbf{c}}_i=0$, 那么会退化成QCQP(Quadratically Constrained QP)

Generalized Inequality Constraints

$$\begin{array}{ccc}\text{minimize}& f_0(\mathbf{x})& \\ \text{subject to}& {\mathbf{f}}_i(\mathbf{x}){⪯}_{K_i}0& i=1,\cdots ,m\\ & \mathbf{Ax}=\mathbf{b}& \end{array}$$

其中, $f_0$是convex objective function, ${\mathbf{f}}_i$是K-Convex的

Conic Form Problem

$$\begin{array}{cc}\text{minimize}& {\mathbf{c}}^{\top }\mathbf{x}\\ \text{subject to}& \mathbf{Fx}+\mathbf{g}⪯0\\ & \mathbf{Ax}=\mathbf{b}\end{array}$$

SDP(Semidefinite Problem)

$$\begin{array}{cc}\text{minimize}& {\mathbf{c}}^{\top }\mathbf{x}\\ \text{subject to}& x_1{\mathbf{F}}_1+\cdots +x_n{\mathbf{F}}_n⪯\mathbf{G}\\ & \mathbf{Ax}=\mathbf{b}\end{array}$$

convex problem: linear objective function and linear matrix inequality(LMI) constraints

注意到多个LMI可以写成一个LMI, 因此有:

• LP(Linear Programming) and equivalent SDP(Semidefinite Problem): $$\begin{array}{cc}\text{minimize}& {\mathbf{c}}^{\top }\mathbf{x}\\ \text{subject to}& \mathbf{Ax}⪯\mathbf{b}\end{array}\equiv \begin{array}{cc}\text{minimize}& {\mathbf{c}}^{\top }\mathbf{x}\\ \text{subject to}& \text{diag}(\mathbf{Ax}-\mathbf{b})⪯0\end{array}$$
• SOCP(Second-Order Cone Programming) and equivalent SDP(Semidefinite Problem): $$\begin{array}{ccc}\text{minimize}& {\mathbf{f}}^{\top }\mathbf{x}& \\ \text{subject to}& \Vert {\mathbf{A}}_i\mathbf{x}+{\mathbf{b}}_i\Vert \le {\mathbf{c}}_i^{\top }\mathbf{x}+{\mathbf{d}}_i& i=1,\cdots ,m\end{array}$$ $$\equiv \begin{array}{ccc}\text{minimize}& {\mathbf{f}}^{\top }\mathbf{x}& \\ \text{subject to}& \left[\begin{array}{cc}({\mathbf{c}}_i^{\top }\mathbf{x}+{\mathbf{d}}_i)\mathbf{I}& {\mathbf{A}}_i\mathbf{x}+{\mathbf{b}}_i\\ {\mathbf{A}}_i\mathbf{x}+{\mathbf{b}}_i& c_i^{\top }\mathbf{x}+{\mathbf{d}}_i\end{array}\right]⪯0& i=1,\cdots ,m\end{array}$$

Eigenvalue minimization:

\begin{matrix}\text{minimize}&\lambda_\max(\mathbf A(\mathbf x))\end{matrix}

其中, \lambda_\max指的是$\mathbf{A}(\mathbf{x})={\mathbf{A}}_0+{\mathbf{x}}_1{\mathbf{A}}_1+\cdots +{\mathbf{x}}_n{\mathbf{A}}_n$的最大的特征值, 因此有\lambda_\max(\mathbf A(\mathbf x))\leq t\Leftrightarrow\mathbf A(\mathbf x)\preceq t\mathbf I

因此, 可以转成等效SDP:

$$\begin{array}{cc}\text{minimize}& t\\ \text{subject to}& \mathbf{A}(\mathbf{x})⪯t\mathbf{I}\end{array}$$

Lagrangian

$$\begin{array}{ccc}\text{minimize}& f_0(\mathbf{x})& \\ \text{subject to}& f_i(\mathbf{x})\le 0& i=1,\cdots ,m\\ & h_i(\mathbf{x})=0& i=1,\cdots ,n\end{array}$$

定义Lagrangian方程为:

$$\mathcal{L}(\mathbf{x},\lambda ,\nu )=f_0(\mathbf{x})+\sum {\lambda }_i{f}_i(\mathbf{x})+\sum {\nu }_i{h}_i(\mathbf{x})$$

Lagrangian Dual Function

Theorem

下界:

$$f_0(\tilde{\mathbf{x}})\ge \mathcal{L}(\tilde{\mathbf{x}},\lambda ,\nu )\ge \underset{x\in \mathcal{D}}{\inf }\mathcal{L}(x,\lambda ,\nu )=g(\lambda ,\nu )$$

拉格朗日对偶优化问题:

$$\begin{array}{cc}\underset{\lambda }{\mathrm{minimize}}& g(\lambda ,\nu )\\ \text{subject to}& \lambda ⪰0\end{array}$$

KKT Condition

primal feasibility

原始条件可行:

$$\begin{array}{c}{f}_i(\mathbf{x})]\le 0,i=1,\cdots ,m\\ h_i(\mathbf{x})=0,i=1,\cdots ,n\end{array}$$

dual feasibility

对偶的Lagrangian multiplier非负:

$$\lambda ⪰0$$

complementary slackness

$${\lambda }_i{f}_i({\mathbf{x}}^{\ast })=0,i=1\cdots ,m$$

zero gradient for Lagrangian with respect to x

$${\nabla }_{\mathbf{x}}{f}_0(\mathbf{x})+\sum {\nabla }_{\mathbf{x}}{\lambda }_i{f}_i(\mathbf{x})+\sum {\nabla }_{\mathbf{x}}{\nu }_i{h}_i(\mathbf{x})=0$$