凸问题

问题定义

凸优化问题

一般优化问题的描述：

$$\begin{array}{lll}\min&f_0(x)\\\\s.t.&f_i(x)\leq0&i=1,\ldots,m\\\\&h_i(x)=0&i=1,\ldots,p\end{array}$$

广义凸问题：凸目标，凸集约束
狭义凸问题：

$$\begin{aligned}&\min\quad f_{0}(x)&&f_{0}(x)\text{为凸}\\&s.t.\quad f_{i}(x)\leq0\quad i=1,\ldots,m&&f_{i}(x)\text{均为凸}\\&a_{i}^{T}x=b_{i}\quad i=1,\ldots,p&&\text{等式约束为仿射函数}\end{aligned}$$

常用定义

• 优化问题的域(domain)：$\text{D=}\bigcap\limits_{i=0}^mdom f_i \cap \bigcap\limits_{i=1}^pdom h_i$

• 可行解集(feasibleset)：X_f = {x ∣ x ∈ D, f_i(x) ≤ 0, i = 1, …, m, h_i(x) = 0, i = 1, …, p}

• 最优值(optimizationvalue)：p^* = inf {f₀(x) ∣ x ∈ X_f]

• 最优解(optimizationpoint/solution)：若 x^* 可行,且 f₀(x^*) = p^*,称 x^* 为最优解

• 局部最优解(locallyoptional):$f_0(x)=\inf \left\{\begin{array}{ll} \quad \quad \quad f_i(x)\leq0,i=1,\dots,m\\[1ex]f_0(z) | \quad h_i(z)=0,i=1,\dots,p\\ \quad \quad \quad \|z-x\|\leq R\end{array}\right\}$

1725112752619.png

问题性质

常用等价变换

BoxConstraint(箱约束)转化为标准形式

$$l_i\leq x\leq u_i\Rightarrow\begin{cases}l_i-x_i\leq0\\[2ex]x_i-u_i\leq0\end{cases}$$

缩放，给目标函数或约束条件乘上一些正系数，类似于数据清洗

$$\begin{aligned}\operatorname*{min}& \alpha_0 f_0(x)\\[2ex]s.t.& \alpha_i f_i(x)\leq0\quad i=1,\dots,m\\[2ex]& \beta_i h_i(x)=0\quad i=1,\dots,p\end{aligned}$$

消除等式约束，可以把等式约束当做方程解出来带入其他部分

引入松弛变量

$$\begin{aligned}&\operatorname*{min}\quad f_{0}(x)\\&s.t.\quad s_{i}\leq0\\&f_{i}(x)-s_{i}=0\quad i=1,\ldots,m\\&a_{i}^{T}x=b_{i}\quad i=1,\ldots,p\end{aligned}$$

许多优化算法（如线性规划、二次规划等）都是针对具有特定形式（如线性约束、凸目标函数）的问题设计的。通过引入松弛变量，可以将原始问题转化为这些算法能够处理的形式，从而利用这些算法来求解问题。

局部最优即是全局最优

证明：若找到了局部最优解x,用反证法证明x一定是全局最优解 $$\begin{aligned}&\text{设 x 不是全局最优,那么必然}\exists y\in X_f, s.t. f_0(y)<f_0(x)\\&\because\text{x 为局部最优,}\Rightarrow\|y-x\|_2>R\\&\text{令 }z=\theta y+(1-\theta)x\text{,取 }\theta=\frac R{2\|y-x\|_2}\in[0,1]\\&\therefore\text{z 为凸组合,}z\in X_f\text{ 且 }f_0(z)\leq\theta f_0(y)+(1-\theta)f_0(x)\\&\|z-x\|_2=\theta\|x-y\|_2=\frac R2<R\text{,由 x 局部最优有 }f_0(x)\leq f_0(z)\\&\text{由此应该有 }f_0(y)<f_0(x)\leq f_0(z)\text{ (两条结论矛盾,因此原假设成立)}\end{aligned}$$

对千拟凸优化问题，局部最优解是全局朵优解这一性质不成立

最优解处的一阶条件

设凸优化问题的目标函数是可微的，记最优解为x^*,可行域为X_f对于任意的y ∈ X_f,均满足 ∇f₀^T(x^*)(y − x^*) ≥ 0

简单证明一下，我们都知道凸函数的一阶性质是 f(y) ≥ f(x) + ∇f^T(x)(y − x)    （1）

如果最优解处的一阶条件是满足∇f₀^T(x^*)(y − x^*) ≥ 0的，那么代入（1）可以得到f(y) ≥ f(x^*),符合x^*是最优解得要求

如果最优解处的一阶条件不满足∇f₀^T(x^*)(y − x^*) ≥ 0
考虑点 z(t) = ty + (1 − t)x, 其中 t ∈ (0, 1] 为参数。因为 z(t) 在 x 和 y 之间的线段上， 而可行集是凸集，因此 z(t) 可行。我们可断言对于总有小正数t, 使得f₀(z(t)) < f₀(x), 这证 明了x不是最优的。为说明这一点，注意 $$\left.\frac{d}{dt}f_0(z(t))\right|_{t=0}=\nabla f_0(x)^T(y-x)<0,$$

综上所述，最优解处的一阶条件成立

看看上述式子的几何意义，设X为可行域，x为最优解，图中虚线簇为优化函数f₀的等高线，则最优解处的一阶条件给出了一个超平面∇f₀(x)^T(y − x) = 0，可行域作为一个凸集总在超平面的一侧,也就是∇f₀(x)^T(y − x) < 0

仅有等式约束

$$\begin{array}{ll}\min&f_0(x)\quad dom\mathrm{~}f_0=\mathbb{R}^n\\s.t.&Ax=b\end{array}$$

带入一阶最优条件 令v = y − x^*,约束条件化为∇f₀^T(x^*)v ≥ 0,v ∈ 𝒩(A),则 ∇f₀^T(x^*) ⟂ v

为何由∇f₀^T(x^*)v ≥ 0便可以断言∇f₀^T(x^*) ⟂ v?,不妨从几何的角度来理解。图上看结果是：最优解处函数梯度垂直于A的化零空间

1725114468739.png

可以想象:无论如何调整∇f₀(t)方向，也无法使所有的v ∈ 𝒩(A)(对应Ax = 0)都做到∇f₀^T(x^*)v ≥ 0,因此只能是 ∇f₀^T(x^*) ⟂ v

仅有非负约束

$$\begin{aligned}&\min f_0(x)\\&s.t. x\geq0\\&\nabla f_0^T(x^*)y-\nabla f_0^T(x^*)x^*\geq0 \quad \quad (1)\end{aligned}$$

上式是关于任意y ≥ 0的线性函数(y的约束与x相同)，若想要(1)式子大于等于0恒成立，则系数必然有 ∇f₀(x^*) ≥ 0    (2) 为什么？倘若∇f₀^T(x^*)有负数分量∇f_0i^T(x^*),由于y在正数范围内任取，令y_i取到足够大的正无穷，其余分量为0，则(1)不成立。因此∇f₀^T(x^*)是不能有负数分量的

再看看其他有用的性质，令y = 0，由(1)可以得到.−∇f₀^T(x^*)x^* ≥ 0    (3)

结合(2)(3)和x非负的约束，可以得到∇f₀^T(x^*)x^* = 0，这两项内积为0，且都非负，所以(∇f₀(x^*))_ix_i^* = 0, ∀i。，注意这里得出了一个重要性质，最优解处考察每一个维度，要么梯度值分量为0，要么约束取等号，这个条件叫做互补条件(complementary)。以下图为例检验一下,蓝色线为目标函数等高线，约束为第一象限ℝ₊₊²，此时满足互补条件

1725115176564.png

问题举例

线性规划

$$\begin{aligned} &\mathrm{min} c^{T}x+d \\ &s.t. Gx+s=h \\ &Ax=b \\ &s\geq0 \end{aligned}$$

等价变换

$$\begin{aligned}&\mathrm{min}&&c^{T}x^{+}-c^{T}x^{-}+d\\&s.t.&&Gx^{+}-Gx^{-}+s=h\\&&&Ax^{+}-Ax^{-}=b\\&&&s\geq0, x^{+}\geq0, x^{-}\geq0\end{aligned}$$

其中x⁺和x⁻是只有0分量和正分量的向量，举个例子： x=[-2,1,-2,3],则x⁺=[0,1,0,3],x⁻=[2,0,2,0]

通过这种变换能够将问题化为线性约束以及非负约束，这方便使用函数(linprog)进行求解。
根据一阶最优条件线性规划的解在边界上

1725157239220.png

线性分数规划

$$\begin{aligned} &\mathrm{min}&& \frac{c^{T}x+d}{e^{T}x+f} \\ &s.t.&& Gx\leq h \\ &&&Ax=b \\ &&&e^{T}x+f>0 \end{aligned}$$ 这个问题不是凸优化问题，但是可以化为线性规划问题

取$y=\frac{x}{e^{T}x+f}, z=\frac{1}{e^{T}x+f}$，得到等价问题

$$\begin{aligned} &\mathrm{min}&& c^{T}y+dz \\ &s.t.&& Gy-hz\leq0 \\ &&&Ay-bz=0 \\ &&&e^{T}y+fz=1 \\ &&&z\geq0 \end{aligned}$$

【如何判断两个优化问题等价？】

【在一个优化问题里面找一个可行解，使得能在另一个那里找到对应的可行集，且这两个解对应的目标函数值是相等的】

二次规划

(quadratic programming, QP)目标函数为二次函数，约束为放射约束

$$\begin{array}{rl}\min&\frac{1}{2}X^TPX+q^Tx+r\\\\s.t.&Qx\leq h\quad P\in S_+^n\\\\&Ax=b\end{array}$$

线性规划问题的最优解只能在边界点取到，二次规划问题的最优解可能在内部取到

1725157839000.png

二次约束的二次规划(Quadratically Constrained Quadratic Programing, QCQP)

$$\begin{aligned}&\text{min}&&\frac{1}{2}X^{T}PX+q^{T}x+r\\&s.t.&&\frac{1}{2}X^{T}P_{i}X+q_{i}^{T}x+r\leq0&&P\in S_{++}^{n}\\&&&Ax=b&&P_{i}\in S_{+}^{n}, i=1,\ldots,m\end{aligned}$$

稀疏约束的最小二乘

之前提到可以使用1范数取代0范数

$$\begin{array}{ll}\hat{x}=\arg\min_x&\|b-Ax\|_2^2+\lambda_0\|x\|_0\\\\=\arg\min_x&\|b-Ax\|_2^2+\lambda_1\|x\|_1&(l_1-regularized least squares)\end{array}$$

但是带有绝对值的目标函数显然是不好优化的，为此做一些变换

令x = x⁺ − x⁻,则λ₁∥x⁺ − x⁻∥₁ = λ₁1^Tx⁺ + λ₁1^Tx⁻，从而消除绝对值，化为二次规划的问题

$$\begin{array}{rl}\hat{x}=\arg\min_x&\|b-Ax^+-Ax^-\|_2^2+\lambda_11^Tx^++\lambda_11^Tx^-\\\\s.t.&x^+,x^-\geq0\end{array}$$

半正定规划

半正定规划有两种形式，一种是矩阵形式，一种是向量形式
半正定规划的矩阵形式，这实际上是矩阵空间的线性规划（因为trace 的操作实际上是线性操作， 可从特例对角矩阵理解）

$$\begin{array}{rl}\mathrm{min}&tr(CX)\\\\s.t.&tr(A_iX)=b_i, i=1,\ldots,p\\\\&X\succeq0, X\in S_{+}^{n}, C\in R^{n\times n}, A_{i}\in R^{n\times n}, b_{i}\in R\end{array}$$

向量形式

$$\begin{array}{ll}\min&c^Tx\\\\s.t.&x_1A_1+\cdots+x_nA_n\preceq B\\\\&x\in R^n, B,A_1,\ldots,A_n\in S^k, C\in R^n\end{array}$$

经典的问题：谱范数(最大奇异值)问题
谱范数指的是矩阵的最大奇异值
求A(x) = A + x₁A₁ + ⋯ + x_nA_n, A_i ∈ ℝ^p × q最小谱范数？ 由于谱范数恒正，记优化函数为$\sqrt{S}$,问题表述为

$$\begin{aligned} \mathrm{min}& \sqrt{S} (\text{非凸})\quad\Leftrightarrow\quad S (\text{凸}) \\ s.t.& A(x)^TA(x)\preceq SI \\ \Rightarrow\mathrm{min}& \text{t} \\ s.t.& A(x)^TA(x)\preceq t^2I, t\geq0 \\ \Rightarrow\mathrm{min}& \text{t} \\ s.t.& \left.\left[\begin{array}{cc}tI&A(x)\\\\A^T(x)&tI\end{array}\right.\right]\succeq0, t\geq0 \\ &&\Rightarrow\mathrm{min} t \text{:} \\ s.t.& Y=\left[\begin{array}{cc}tI&A(x)\\[0.3em]A^T(x)&tI\end{array}\right], Y\succeq0, t\geq0 \end{aligned}$$

具体的等价证明参见附录

多目标优化

• 例如，投资要在总成本限制下，最小化风险，最大化收益；发展要在一定资源限制下，最大化发展速度与发展质量。
• 此时有多个目标，通常在某个指标上变好，就会在另外一个指标上变差，权衡不同目标，得出最优解的集合称为帕累托曲面(Pareto front)

1725176582131.png

帕累托曲面通常很难找到，因此多目标优化事实上是个很难做的问题，我们一般会定住某些目标将问题变为单目标优化问题，比如使用罚函数的思想。以岭回归为例
$$\begin{array}{l}\min\|b-Ax\|_2^2\text{,}\min\|x\|_2^2\\\min\|b-Ax\|_2^2+\lambda\|x\|_2^2\end{array}$$

遍历不同的超参数λ即可得到帕累托曲面

1725176724670.png