基于FFT求解带约束条件的W(x)的技术咨询
各位好,我目前碰到一个带约束的卷积反演问题,想求解最优的$W(x)$,先跟大家详细说说我的问题和已经尝试过的思路,希望能得到指点:
问题背景
已知两个函数$I(x)$和$d(x)$,$I(x)$是$W(x)$与$d(x)$的卷积:
$$I(x) = \int_{-\infty}^{\infty} W(x_0) d(x-x_0) dx_0$$
如果没有约束的话,这个问题很简单,直接用傅里叶变换就能解:
$$F(I) = F(W)F(d)$$
$$W(x) = F^{-1}\left(\frac{F(I)}{F(d)}\right)$$
但现在我需要找到满足约束的最优$W(x)$,约束条件是$0 \leq N(\Psi) \leq 1$,其中$N$是关于$W$的已知函数:
$$N=G(W)=\int_{-\infty}{\infty}W(x_0)e{-kg(x_0,\Psi)^2} dx_0$$
这里$k$是一个较大的常数,$g(x_0,\Psi)$也是已知函数。另外补充一下,所有$x$都满足$0\leq I\leq1$、$0<d\leq 1$。
我尝试过的三种思路(均未成功)
思路一:带约束的非线性最小二乘+欧拉-拉格朗日方程
我首先把问题转化为带不等式约束的非线性最小二乘问题:
$$\textrm{min} \int_{-\infty}^{\infty}
\left(I(x) - \int_{-\infty}^{\infty} W(x_0) d(x-x_0) dx_0\right)^2
dx$$
约束条件:
$$\begin{cases}
-N\leq 0 \
N-1 \leq 0
\end{cases}$$
为了简化,我定义$\Delta(x,W(x)) = I(x) - \int_{-\infty}^{\infty} W(x_0) d(x-x_0) dx_0$,然后构造拉格朗日函数,把约束加入目标:
$$\textrm{min} \int_{-\infty}^{\infty}
\Delta^2 dx
- \mu_1(-G(W)) + \mu_2(G(W)-1)$$
本来想调用欧拉-拉格朗日方程来求解,但这个方程要求目标函数是$\int_{-\infty}^{\infty} L(x,W,W') dx$的形式,这里的拉格朗日函数里没有$W'$($W$的导数),理论上可以简化为$\frac{\partial L}{\partial W}=0$,但我完全不知道怎么把当前的拉格朗日表达式拆成符合要求的$L$形式,到这里就卡壳了。
思路二:逐点最小二乘+对偶问题
这次我换了个角度,尝试对每个$x$单独做最小二乘(把$x$当作常数),目标函数和约束和之前一致,构造拉格朗日函数:
$$L(W,\mu_1,\mu_2) = \Delta(W)^2+\mu_1(-G(W)) + \mu_2(G(W)-1)$$
然后我想到用对偶问题来转换,把原问题转为:
$$\textrm{max } h(\mu_1,\mu_2)$$
约束条件是$\mu_1>0, \mu_2>0$,其中$h(\mu_1,\mu_2) = \textrm{min } L(W,\mu_1,\mu_2)$
要计算$h$的话,需要对$W$求导并令导数为0,得到:
$$\frac{\partial L}{\partial W} = 2\Delta \frac{\partial \Delta}{\partial W}
- \frac{\partial G}{\partial W} (\mu_2 - \mu_1) - \mu_2 = 0$$
但这里我完全搞不清怎么计算$\frac{\partial \Delta}{\partial W}$和$\frac{\partial G}{\partial W}$,又没法继续推进了。
思路三:离散化优化+修改目标向量
后来我想把问题离散化,把$I(x)$、$W(x)$表示成向量$\boldsymbol{I}$、$\boldsymbol{W}$,$d(x)$对应循环矩阵$\boldsymbol{D}$,这样最小二乘问题可以写成:
$$\textrm{min }||\boldsymbol{I}-\boldsymbol{D}\boldsymbol{W}||^2 + \boldsymbol{\mu}^T \boldsymbol{C}$$
其中$\boldsymbol{\mu} = \begin{bmatrix}\mu_1 \ \mu_2\end{bmatrix}$,$\boldsymbol{C} = \begin{bmatrix}-G(\boldsymbol{W}) \ G(\boldsymbol{W})-1\end{bmatrix}$
我的想法是把这个带约束的问题转换成无约束的形式:$\textrm{min }||\tilde{\boldsymbol{I}}-\boldsymbol{D}\boldsymbol{W}||^2$,通过展开对比两种形式的系数,我得到了修改后的目标向量:
$$\tilde{\boldsymbol{I}} = \boldsymbol{I} - \frac{1}{2} (\boldsymbol{D}T){-1}\boldsymbol{C}^T\boldsymbol{\mu}$$
这样最优的$\boldsymbol{W}$就可以写成$\boldsymbol{W} = (\boldsymbol{D}T\boldsymbol{D}){-1}\boldsymbol{D}^T \tilde{\boldsymbol{I}}$,但现在的问题是我完全不知道该怎么确定$\boldsymbol{\mu}$,这个思路还是走不通。
有没有大佬能给我指条路?或者有没有其他更合适的方法来解决这个带约束的卷积反演问题?
备注:内容来源于stack exchange,提问作者Matthew James

