本文介绍到标准单纯型集(The Standard Simplex Set) 1. 简介
在优化算法当中,我们的目标问题常常带有各种各样的限制条件。例如在某项投资活动中,我们想计算投入为多少时收益最大,那么我们的投入应该是被限制为大于等于零的,而不能为负数,并且我们能投资的最大金额也是有限制的。为了得到符合条件的解,我们将不合条件的“待选解”家用投影(可看作一种调整方式)到条件限制的范围内是我们做带限制优化的一台重要方法。本文中,我们介绍两种如何将n维空间中一点家用投影到标准单纯型(The Standard Simplex)上的方法。具体地,我们讨论将点p\in \mathbb{R}^n(其中,p=(p_1,\dots,p_n)且对i=1,\dots,n, p_i\geq 0)家用投影到集合
C=\{p\in \mathbb{R}^n: \sum_{i=1}^np_i=1, p_i\geq 0\} \\
中。限制为C的优化问题在许多应用中都有出现。例如,在量化投资中,我们常常需要计算投资组合的权重。假设有n支股票,我们用n维空间中的一点p=(p1,\dots,p_n)来表示投资的权重,即p_i表示我们将在第i支股票投资的比例。因此,我们需要将p限制在集合C中。限制为集合C的优化问题也出目前微分方程和最优传输等领域中。
在第一台算法中,我们找到两个集合C_0和C_1,使得C=C_0\cap C_1。然后,我们通过交替家用投影到集合C_0和C_1上,来实现家用投影到C上的目的。接着,我们改变度量距离的方式,探讨归一化操作,即p/\sum_{i=1}^np_i,如何解释为点p到集合C的基于Bregman距离的家用投影。
我们需要提醒的是,交替家用投影的算法并不是解决这一问题的最高效的办法。有兴趣的读者可以参考下面论文及其相关论文:https://arxiv.org/pdf/1101.6081.pdf。
2. 家用投影算法
这里,我们定义集合C_0和C_1,使得
C_0=\{p\in \mathbb{R}^n: \sum_{i=1}^np_i=1\} \\
并且
C_1=\{p\in \mathbb{R}^n: p_i\geq 0, i=1,\dots,n\}。 \\
我们注意到C=C_0\cap C_1。我们先分别考虑到C_0与C_1的家用投影,然后讨论家用投影到C的交替家用投影。
2.1 p到C_0的家用投影
观察C_0的定义,我们可知C_0是以向量\mathbf{1}_n=(1,\dots,1)\in \mathbb{R}^n为法向量的超平面(超平面可以想象成二维平面在高维中的拓展。想象成二维平面即可)。将点p家用投影到C_0上相当于将p家用投影在C_0定义的超平面上。根据家用投影的定义,家用投影点p^*为超平面C_0中离点p最近的点。因此,p^*为下列优化问题的最优解:
\min_{p'\in C_0}|p-p'|^2。\quad (1.0) \\
这里,我们并不直接求解上述优化问题,而是通过几何的的办法来求p^*。假设p^*=(p_1^*,\dots,p_n^*)为家用投影点。那么向量\overset{\longrightarrow}{p^*p}平行于超平面C_0的法线\mathbf{1}_n,即
\frac{p_1-p_1^*}{1}=\dots=\frac{p_n-p_n^*}{1}。\quad(1.1) \\
同时,因为点p^*在超平面C_0内,我们有
p_1^*+\dots+p_n^*=1。\quad(1.2) \\
让\lambda=\frac{p_1-p_1^*}{1}=\dots=\frac{p_n-p_n^*}{1}。因此,对于所有i=1,\dots,n,p_i^*=p_i-\lambda 。将上式带入(1.2),我们得到
\sum_{i=1}^np_i-n\lambda=1。 \\
我们得到\lambda=\frac{1}{n}(\sum_{i=1}^np_i-1)。因此,p^*满足公式:
p^*=p-\frac{1}{n}(\sum_{i=1}^np_i-1)\mathbf{1}_n。\quad(1.3) \\
我们得到了p^*的表达式。但从(1.3)可以看出,我们并不能保证公式(1.3)求得的p^*在集合C_1中。我们需要考虑p到C_1的家用投影。
2.2 p到C_1的家用投影
根据C_1的定义,我们可知C_1包含了n维空间中的正象限围成的区域。如在n=2时,为下图中x与y轴中值为正的部分围成的阴影区域。
因此,将p家用投影到C_1办法相对简单,只需要将p小于0的分量变成0即可。即,p_i^*=\max\{p_i,0\}。我们注意到将p家用投影到C_1上并不能保证p在超平面C_0上。
2.3 交替家用投影
目前我们考虑将p家用投影到集合C。我们注意到C=C_0\cap C_1并且我们已经知道了如何将p分别家用投影到C_0和C_1。我们用交替家用投影,将p家用投影到C_0\cap C_1。具体地,我们将p家用投影到C_0上,得到点p_1。再将p_1家用投影到C_1上,得到点p_2。接下来,我们将点p_2再家用投影到C_0上,依次重复,直到得到的家用投影点收敛。
下列为Matlab代码,实现将随机生成的10维正向量p交替家用投影到集合C的过程。
%这里考虑10维的点,即n=10
n=10;
%生成一台随机的正向量p
rand('seed',5);
p=1+rand(1,n);
%normal: C0的法向量
normal=ones(1,n);
error=10^3;
threshold=10^(-12);
%定义中间变量
p0=p; p1=p;
while error>threshold
%家用投影到C0上
p1=p0-1/n*(sum(p0)-1)*normal;
%家用投影到C1上
p1=max(p1,0);
%计算误差
error=sum((p1-p0).^2);
p0=p1;
end
pstar=p0
3. 基于Bregman距离的家用投影
这一节,我们假设点p的所有分量满足p_i\geq 0,\sum_{i=1}^np_i\not=0。让我们回到家用投影的定义。将p家用投影到C意思是在C中找到一台点p^*,使得p到点p^*的距离比点p到C上其它点的距离都近。在前面的讨论中,例如问题(1.1)中,我们使用欧几里得距离。因此,我们需要找到p^*,使得其为下列优化问题的解:
\min_{p'\in C}|p-p'|^2。\quad(4.1) \\
这里,我们使用Bregman距离来代替欧几里得距离。具体地,我们将基于可微的凸函数\varphi的Bregman距离,记做D_\varphi,定义为
D_{\varphi}(p,p')=\sum_{i=1}^n\varphi(p_i)-\varphi(p'_i)-\varphi'(p')(p_i-p_i')。\quad(4.2) \\
其中,\varphi'为\varphi的导数,p=(p_1,\dots,p_n)与p_i=(p_1',\dots,p_n')为n维空间中的点,并且p_i\geq 0,p_i'\geq 0。因为\varphi是凸函数,根据凸函数的定义,对任意满足p_i\geq 0,p_i'\geq 0的点p, p',我们有D_{\varphi}(p,p')\geq 0。并且D_{\varphi}(p,p)=0。因此,D_{\varphi}(p,p')可以看成p与p'之间的距离。基于(4.2)定义的Bregman距离,我们将p家用投影到C上,亦即,我们试图找到p^*使得其为下列问题的最小值点:
\min_{p'\in C}D_\varphi(p,p')。\quad(4.3) \\
这里,我们取\varphi(x)=x\ln(x)-x,我们有\varphi'(x)=\ln(x)。因此,
D_{\varphi}(p,p')=\sum_{i=1}^n p_i\ln(p_i)-p'_i \ln(p'_i)-\ln(p')(p_i-p_i')。\\
因此,化简后,问题(4.3)等价于 \min_{p'\in C}-\sum_{i=1}^n p_i\ln(p'_i)。\quad(4.4)\\
注意到(4.4)中,\ln函数保证了在最小值点处,最小值点的坐标值为非负数。所以,我们可以省略掉C_1中的限制。因此,(4.4)等价于下列优化问题:
\min_{p'\in C_0}-\sum_{i=1}^n p_i\ln(p'_i)。\quad(4.5)。 \\
为求解(4.5),我们利用拉格朗日乘子法。我们定义函数,
L(p',\lambda)=-\sum_{i=1}^n p_i\ln(p'_i)+\lambda(\sum_{i=1}^np'_i-1)。 \\
在最小值点处,我们有\frac{\partial L}{\partial p'_i}=-\frac{p_i}{p'_i}+\lambda=0,\frac{\partial L}{\partial \lambda}=\sum_{i=1}^np'_i-1=0。所以,我们有p'_i=\frac{p_i}{\lambda},进而,我们有\sum_{i=1}^n\frac{p_i}{\lambda}=1。所以,\lambda={\sum_{i=1}^np_i}。因此,问题(4.5)的最小值点p^*满足
p_i^*=\frac{p_i}{\sum_{i=1}^np_i}。\quad(4.6) \\
从(4.6)中可以看出,归一化操作,即p/\sum_{i=1}^np_i,可以解释为点p到集合C的基于Bregman距离的家用投影。 |