凸优化学习笔记（三）：凸优化问题

三、凸优化问题

一般优化问题

$$ \begin{aligned} \text{minimize}\ (\min) \ & f_0(X) \\ \text{Subject}\ \text{to}(s.t.) \ & f_i(X)\leq 0, i=1,...,M \\ & h_i(x)=0,i=1,...,P \end{aligned} $$

优化变量 (Optimization Variable)： $X\in R^n$
目标函数 (Objective function)： $f_0:R^n\rightarrow R$
极小化损失函数 (Cost function)
极大化效用函数 (Utility function)
不等式约束 (Inequality Constraint)： $f_i(x)\leq 0$
等式约束 (Equality Constraint)： $h_i(x)=0$
无约束 (Unconstrained)： $m=p=0$
优化问题的域 (domain)： $D=\bigcap^m_{i=1}dom(f_i)\cap\bigcap^p_{i=1}dom(h_i)$
可行解集 (feasible set)
$x\in D$ 为可行解，若 $f_i(x)\leq 0,i=1,…,m$ 且 $h_i(x)=0,i=1,…,p$
$X_f={x为可行解}$ 为可行解集
问题的最优值 (Optimal Value)： $P^{*}=\inf\{f_0(x)|x\in X_f\}$ ；若 $X_f$ 为空集，则 $P^*$ 为正无穷
最优解 (Optimal Point / Solution)：若 $x^*$ 可行且 $f_0(x^*)=P^*$
最优解集 (Optimal Set)： $X_{opt}=\{x|x\in X_f,f_0(x)=P^*\}$
$\epsilon$ 次优解集 ( $\epsilon$ -Suboptimal Set)： $X_{\epsilon}=\{x|x\in X_f,f_0(x)\leq p^*+\epsilon\}$
局部最优解 (locally optimal)： $f_0(x)=\inf\{f_0(z)|f_i(z)\leq 0,i=1,…,m;h_i(z)=0,i=1,…,p;||z-x||\leq R\}$ ，存在 $R>0$ 使 $x$ 局部最优
局部最优解集： $X_{loc}$

$f_i(x)\leq 0$ 而不是 $f_i(x)<0$ 的原因在于， $<$ 始终可以转化为 $\leq$

凸优化问题

广义

目标函数为凸函数，约束集合为凸集。

狭义

$$ \begin{aligned} \min \ & f_0(X) \\ s.t. \ & f_i(X)\leq 0, i=1,...,m \\ & a_i^TX=b_i,i=1,...,p \end{aligned} $$

目标函数、不等式约束函数均为凸函数
等式约束为仿射函数

重要性质

局部最优 = 全局最优

目标函数可微时， $X^*\in X_f$ 最优 $\Leftrightarrow \nabla f_0^T(X^*)(y-X^*)\geq 0,\forall y\in X_f$

典型凸问题

线性规划 (Linear Programming - LP)：

$$ \begin{aligned} \min \ & c^Tx+d,c\in R^n,d\in R \\ s.t. \ & Gx\leq h,G\in R^{m\cdot n},h\in R^m \\ & Ax=b,A\in R^{k\cdot n},b\in R^k \end{aligned} $$

二次规划 (Quadratic Programming - QP)：

当 $P$ 半正定时为凸优化问题

$$ \begin{aligned} \min \ & \frac{1}{2}x^TPx+q^Tx+r \\ s.t. \ & Gx\leq h \\ & Ax=b \end{aligned} $$

二次约束二次规划 (Quadratically Constrained Quadratic Programming - QCQP)：

$$ \begin{aligned} \min \ & \frac{1}{2}x^TPx+q^Tx+r, P\in S^n_{+} \\ s.t. \ & x^TP_ix+q_i^Tx+r_i\leq 0, P_i\in S^n_{+},i=1,...,m \\ & Ax=b \end{aligned} $$

半正定规划 (Semi-Definite Programming - SDP)：

矩阵空间的线性优化问题

$$ \begin{aligned} \min \ & tr(CX) \\ s.t. \ & tr(A_iX)=b_i,i=1,...,p \\ & X\succeq 0,X\in S^n_{+},C,A_i\in R^{n\cdot n},b_i\in R \end{aligned} $$

问题等价证明

若问题 $P1$ 与 $P2$ 等价，则：

$P1$ 中的一个可行解必对应 $P2$ 中的一个可行解，且两个可行解对应的目标函数值相等
$P2$ 中的一个可行解必对应 $P1$ 中的一个可行解，且两个可行解对应的目标函数值相等

问题转换技巧

$x=x^{+}-x^{-},x^{+},x^{-}\geq 0$ ，举例 $x=[1\ 2\ -1]^T$ ，则 $x^{+}=[1\ 2\ 0]^T,x^{-}=[0\ 0\ 1]^T$ ，可用于 $||x||_1\Leftrightarrow I^Tx^{+}+I^Tx^{-},x^{+},x^{-}\geq 0$

多目标优化问题

$$ \begin{aligned} \min \ & f_0(X) \\ s.t. \ & f_i(X)\leq 0, i=1,...,m \\ & h_i(x)=0,i=1,...,p \\ & f_0:R^n\rightarrow R^q,f_i:R^n\rightarrow R,h_i:R^n\rightarrow R \end{aligned} $$

转单目标优化问题：

若 ${f_0(x)}$ 在 $R^k$ 中为凸， $f(x)$ 为凸， $h_i(x)$ 为仿射，则必可通过下述方法求得 Pareto front（帕利托最优面）中一点
通过遍历 ${\lambda_i}$ 可找出所有点

$$ \begin{aligned} \min \ & \sum\limits_{i=1}^q \lambda f_{0i}(X),\lambda_i\geq 0 \\ s.t. \ & f_i(X)\leq 0, i=1,...,m \\ & h_i(x)=0,i=1,...,p \\ & f_0:R^n\rightarrow R^q,f_i:R^n\rightarrow R,h_i:R^n\rightarrow R \end{aligned} $$

岭回归 (Ridge Regression) 举例：

下述三种表示方式等价
$A\in R^{m\cdot n},x\in R^n,b,e\in R^m$

$$ \begin{aligned} \min \ & ||b-Ax||^2_2\\ \min \ & ||x||_2^2 \\ \end{aligned}\Leftrightarrow $$

$$ \begin{aligned} \min \ & ||b-Ax||^2_2+\lambda ||x||_2^2\\ \end{aligned}\Leftrightarrow $$

$$ \begin{aligned} \min \ & ||b-Ax||^2_2\\ s.t. \ & ||x||_2^2\leq \epsilon \\ \end{aligned} $$