最优化|凸优化问题

Posted by Derek on February 2, 2021

1. 凸优化问题


考虑最优化问题$$\min f(\mathbf{x})\ \ \text{s.t.}\ \ g_i(\mathbf{x}) \leq0, h_j(\mathbf{x})=0$$其中$i=1, \cdots, m$及$j=1, \cdots, l.$ 记可行域为$$S=\lbrace\mathbf{x}\in\mathbb{R}^n|g_i(\mathbf{x}) \leq 0, i=1, \cdots, m, h_j(\mathbf{x})=0, j=1, \cdots, l \rbrace$$当$f(\mathbf{x}), g_i(\mathbf{x})$是凸函数,$h_j(\mathbf{x})$是线性函数,上述最优化问题称为凸优化问题.

2. 凸优化的性质


我们之所以希望一个最优化问题是凸优化问题,是因为凸优化问题有一个非常好的性质——局部最优解即全局最优解. 在证明这一个性质之前,我们先对两个概念进行数理化定义.

定义 2.1(局部最优解)    局部最优解$\overline{\mathbf{x}}$满足$f(\overline{\mathbf{x}}) \leq f(\mathbf{x}), \forall \mathbf{x} \in S \cap N_\varepsilon(\overline{\mathbf{x}}).$

定义 2.2(全局最优解)    全局最优解$\mathbf{x}^*$满足$f(\mathbf{x}^*) \leq f(\mathbf{x}), \forall \mathbf{x} \in S.$

性质 2.3    对于凸优化问题,局部最优解即全局最优解.

证明    假设对于凸优化问题,$\overline{\mathbf{x}}$是局部最优解但不是全局最优解. 因此$\exists \mathbf{x}^* \in S$使得$f(\mathbf{x}^*)<f(\overline{\mathbf{x}}).$ 对于$\lambda \in (0, 1),$ 我们有$$f(\overline{\mathbf{x}}+\lambda(\mathbf{x}^*-\overline{\mathbf{x}}))=f(\lambda\mathbf{x}^*+(1-\lambda)\overline{\mathbf{x}}) \leq \lambda f(\mathbf{x}^*)+(1-\lambda)f(\overline{\mathbf{x}})<f(\overline{\mathbf{x}})$$ 当$\lambda \to 0$时,与$\overline{\mathbf{x}}$是局部最优解矛盾.

性质 2.4    对于凸优化问题,$\mathbf{x}^* \in S$是最优解的充要条件是$$\nabla f(\mathbf{x}^*)^T(\mathbf{x}-\mathbf{x}^*) \geq 0, \forall \mathbf{x} \in S$$ 证明    ($\Leftarrow$)对于任意的$\mathbf{x} \in S,$ $$f(\mathbf{x}) \geq f(\mathbf{x}^*)+\nabla f(\mathbf{x}^*)^T(\mathbf{x}-\mathbf{x}^*) \geq f(\mathbf{x}^*)$$ ($\Rightarrow$)假设$\exists\overline{x} \in S$使得$\nabla f(\mathbf{x}^*)^T(\overline{\mathbf{x}}-\mathbf{x}^*)<0.$ 对于$\lambda \in (0, 1),$ 我们有$$f(\mathbf{x}^*+\lambda(\overline{\mathbf{x}}-\mathbf{x}^*))=f(\mathbf{x}^*)+\lambda\nabla f(\mathbf{x}^*)^T(\overline{\mathbf{x}}-\mathbf{x}^*)+o(\lambda\|\overline{\mathbf{x}}-\mathbf{x}^*\|)$$经整理得$$\frac{f(\mathbf{x}^*+\lambda(\overline{\mathbf{x}}-\mathbf{x}^*))-f(\mathbf{x}^*)}{\lambda}=\nabla f(\mathbf{x}^*)^T(\overline{\mathbf{x}}-\mathbf{x}^*)+\frac{o(\lambda\|\overline{\mathbf{x}}-\mathbf{x}^*\|)}{\lambda}$$ 当$\lambda \to 0$时,$$f(\mathbf{x}^*+\lambda(\overline{\mathbf{x}}-\mathbf{x}^*))<f(\mathbf{x}^*)$$与$\mathbf{x}^*$是最优解矛盾.

3. 几种特殊凸问题的最优性条件


假设$f(\mathbf{x})$是凸函数,我们来看一下几种特殊凸问题的最优性条件:

1. 无约束凸问题$\min f(\mathbf{x})$: $\mathbf{x}^*$最优$\Leftrightarrow\nabla f(\mathbf{x}^*)=\mathbf{0}.$

证明    $\mathbf{x}^*$最优$\Leftrightarrow\nabla f(\mathbf{x}^*)^T(\mathbf{x}-\mathbf{x}^*)\geq0, \forall \mathbf{x}\in\mathbb{R}^n \Leftrightarrow \nabla f(\mathbf{x}^*)=\mathbf{0}.$

2. 等式约束凸问题$\min\lbrace f(\mathbf{x})|A\mathbf{x}=\mathbf{b}\rbrace$: $\mathbf{x}^*$最优$\Leftrightarrow\exists\mu$使得$\nabla f(\mathbf{x}^*)+A^T\mu=\mathbf{0}, A\mathbf{x}^*=\mathbf{0}.$

证明    $\mathbf{x}^*$最优$\Leftrightarrow$对于所有的满足$A\mathbf{x}=\mathbf{b}$的$\mathbf{x}$有$\nabla f(\mathbf{x}^*)^T(\mathbf{x}-\mathbf{x}^*)\geq0,$ 从而$A\mathbf{x}^*=\mathbf{b}.$ 因此上式等价于$\nabla f(\mathbf{x}^*)^T(\mathbf{x}-\mathbf{x}^*)=0, \forall (\mathbf{x}-\mathbf{x}^*) \in \text{Ker}(A) \Leftrightarrow \nabla f(\mathbf{x}^*) \in \text{Ker}(A)^\perp.$ 因此上式等价于$\nabla f(\mathbf{x}^*)$可以表示成$A$的行向量的线性组合,也即$\nabla f(\mathbf{x}^*)+A^T\mu=\mathbf{0}.$

3. 非负约束凸问题$\min\lbrace f(\mathbf{x})|\mathbf{x} \geq \mathbf{0} \rbrace$: $\mathbf{x}^*$最优$\Leftrightarrow \nabla f(\mathbf{x}^*)_ix_i^*=0, \mathbf{x}^* \geq \mathbf{0}, \nabla f(\mathbf{x}^*) \geq \mathbf{0}.$

证明    $\mathbf{x}^*$最优$\Leftrightarrow\nabla f(\mathbf{x}^*)^T(\mathbf{x}-\mathbf{x}^*) \geq 0, \forall \mathbf{x} \geq \mathbf{0},$ 从而$\mathbf{x}^* \geq \mathbf{0}.$ 因此上式等价于$\nabla f(\mathbf{x}^*)^T\mathbf{x} \geq \nabla f(\mathbf{x}^*)^T\mathbf{x}^*, \forall \mathbf{x}, \mathbf{x}^* \geq \mathbf{0} \Leftrightarrow \nabla f(\mathbf{x}^*) \geq \mathbf{0}, \mathbf{x}^* \geq \mathbf{0}, \nabla f(\mathbf{x}^*)^T\mathbf{x}^*=0$也就等价于$\nabla f(\mathbf{x}^*) \geq \mathbf{0}, \mathbf{x}^* \geq \mathbf{0}, \nabla f(\mathbf{x}^*)_ix_i^*=0.$

4. 常见的凸优化问题


1. 线性规划(Linear programming, LP)的标准形式:$$\min \mathbf{c}^T\mathbf{x}\ \ \text{s.t.}\ \ A\mathbf{x}=\mathbf{b}, \mathbf{x} \geq \mathbf{0}$$以下几类问题可转化为线性规划:

(1)分式线性规划:$$\min \frac{\mathbf{c}^T\mathbf{x}+d}{\mathbf{e}^T\mathbf{x}+f}\ \ \text{s.t.}\ \ A\mathbf{x}=\mathbf{b}, D\mathbf{x} \leq \mathbf{h}$$其中$\mathbf{e}^T\mathbf{x}+f>0.$

我们可以令$\displaystyle t=\frac{1}{\mathbf{e}^T\mathbf{x}+f}.$ 上述问题可以转化为$$\min \mathbf{c}^T\mathbf{x}t+dt\ \ \text{s.t.}\ \ A\mathbf{x}t=\mathbf{b}t, D\mathbf{x}t \leq \mathbf{h}t$$进一步转化为$$\min \mathbf{c}^T\mathbf{y}+dt\ \ \text{s.t.}\ \ A\mathbf{y}-\mathbf{b}t=\mathbf{0}, D\mathbf{y}-\mathbf{h}t \leq \mathbf{0}, t>0$$ (2)最小化绝对值函数:$$\min\lbrace |\mathbf{a}^T\mathbf{x}+c|\ \ \text{s.t.}\ \ A\mathbf{x}=\mathbf{b} \rbrace$$ 上述问题可以转化为$$\min t\ \ \text{s.t.}\ \ |\mathbf{a}^T\mathbf{x}+c| \leq t$$我们知道$|\mathbf{a}^T\mathbf{x}+c|=\max\lbrace\mathbf{a}^T\mathbf{x}+c, -(\mathbf{a}^T\mathbf{x}+c)\rbrace,$ 因此进一步转化为$$\min t\ \ \text{s.t.}\ \ \mathbf{a}^T\mathbf{x}+c \leq t, -(\mathbf{a}^T\mathbf{x}+c) \leq t$$ (3)最小化多面体函数:$$\min\lbrace f(\mathbf{x})\ \ \text{s.t.}\ \ D\mathbf{x}=\mathbf{d} \rbrace$$其中$$f(\mathbf{x})=\max\lbrace \mathbf{a}_1^T\mathbf{x}+b_1, \cdots, \mathbf{a}_m^T\mathbf{x}+b_m \rbrace$$ 上述问题可以转化为$$\min t\ \ \text{s.t.}\ \ f(\mathbf{x}) \leq t$$也即$$\min t\ \ \text{s.t.}\ \ \mathbf{a}_1^T\mathbf{x}+b_1 \leq t, \cdots, \mathbf{a}_m^T\mathbf{x}+b_m \leq t$$ 2. 凸二次规划(Quadratic programming, QP)的标准形式:$$\min \frac{1}{2}\mathbf{x}^TQ\mathbf{x}+\mathbf{c}^T\mathbf{x}\ \ \text{s.t.}\ \ A\mathbf{x}=\mathbf{b}, \mathbf{x} \geq \mathbf{0}$$其中$Q \succeq 0.$ 凸二次规划问题有许多的应用,比如在投资学里的均值—方差模型,在统计学里的最小二乘模型:$\min \|A\mathbf{x}-\mathbf{b}\|^2_2$等等.

3. 带凸二次约束的二次规划(Quadratically constrained quadratic program, QCQP)的标准形式:$$\min \frac{1}{2}\mathbf{x}^TQ_0\mathbf{x}+\mathbf{c}_0^T\mathbf{x}\ \ \text{s.t.}\ \ \frac{1}{2}\mathbf{x}^TQ_i\mathbf{x}+\mathbf{c}_i^T\mathbf{x}+b_i \leq 0, i=1, \cdots, k, A\mathbf{x} \leq \mathbf{d}$$其中$Q_i \succeq 0, i=0, \cdots, k.$ 比如说带多种风险约束的均值方差模型就是其中的一个应用.

4. 二阶锥规划(Second-order cone program, SOCP)的标准形式:$$\min f^T\mathbf{x}\ \ \text{s.t.}\ \ \|A_i\mathbf{x}+\mathbf{b}_i\|_2 \leq \mathbf{c}_i^T\mathbf{x}+d_i, i=1, \cdots, k, D\mathbf{x} \leq \mathbf{g}$$其中我们称$\|A_i\mathbf{x}+\mathbf{b}_i\|_2 \leq \mathbf{c}_i^T\mathbf{x}+d_i$为二阶锥约束. 当$k=0$时,就是线性规划;当所有$c_i=0$时,就是带凸二次约束的二次规划. 关于这一问题,我们举一个应用的例子——概率约束问题$$\min\lbrace \mathbf{c}^T\mathbf{x}|P(\xi^T\mathbf{x} \leq a) \geq 95\% \rbrace$$ 其中$\xi \sim \mathcal{N}(\mu, \Sigma).$

我们来看一下这个特殊的概率约束问题. 因为$\xi \sim \mathcal{N}(\mu, \Sigma),$ 所以$\xi^T\mathbf{x} \sim \mathcal{N}(\mu^T\mathbf{x}, \mathbf{x}^T\Sigma\mathbf{x}).$ 我们可以将概率约束改写为$$P\left(Z=\frac{\xi^T\mathbf{x}-\mu^T\mathbf{x}}{\sqrt{\mathbf{x}^T\Sigma\mathbf{x}}} \leq \frac{a-\mu^T\mathbf{x}}{\sqrt{\mathbf{x}^T\Sigma\mathbf{x}}}\right) \geq 95\%$$其中$Z \sim \mathcal{N}(0, 1).$ 我们已知$P(Z \leq z_c)=95\%,$ 因此$$\frac{a-\mu^T\mathbf{x}}{\sqrt{\mathbf{x}^T\Sigma\mathbf{x}}} \geq z_c \Leftrightarrow \sqrt{\mathbf{x}^T\Sigma\mathbf{x}} \leq \frac{a-\mu^T\mathbf{x}}{z_c}$$ 因为$\Sigma$是一个协方差矩阵,所以我们可以对其进行Cholesky分解$\Sigma=L^TL.$ 因此,$$\mathbf{x}^T\Sigma\mathbf{x}=\mathbf{x}^TL^TL\mathbf{x}=\|L\mathbf{x}\|_2^2$$从而$$\|L\mathbf{x}\|_2 \leq \frac{a-\mu^T\mathbf{x}}{z_c}$$因此这一个概率约束问题是一个二阶锥规划的问题.

5. 半定规划(Semidefinite program, SDP)的标准形式:$$\min \text{tr}(CX)\ \ \text{s.t.}\ \ \text{tr}(Q_iX)=b_i, i=1, \cdots, m, X \succeq 0$$对应的矩阵不等式形式为$$\min \mathbf{c}^T\mathbf{x}\ \ \text{s.t.}\ \ x_1Q_1+\cdots+x_nQ_n \preceq Q_0, A\mathbf{x}=\mathbf{b}$$其中$x_1Q_1+\cdots+x_nQ_n \preceq Q_0 \Leftrightarrow Q_0-(x_1Q_1+\cdots+x_nQ_n) \succeq 0$被称为线性矩阵不等式(Linear matrix inequality).