标签归档：优化

交叉通道先验简介

发表于由

交叉通道先验是Heide13年论文中提出的一种RGB彩色图像统计先验，常被用于图像复原的优化目标函数中。

交叉通道先验的物理意义

我们提出在反卷积过程中共享不同通道的信息，从而一个通道保留的频率信息可以帮助其他通道重建。交叉通道先验基于这样的假设：图象所有通道在相同位置的边缘和色调变化是稀疏的。[1]这个假设可以导出两个通道$l,k$之间的先验
\begin{equation}
\begin{aligned}
& \nabla i_k ./ i_k \approx \nabla i_l ./ i_l \\
\Leftrightarrow & \nabla i_k \cdot i_l \approx \nabla i_l \cdot i_k
\end{aligned}
\end{equation}
其中乘法$\cdot$除法$./$都是元素操作。注意使用时我们用$\mathcal{l}_1$范数的形式。

最小化问题

通过交叉通道先验，全通道反卷积可以形式化为一个优化问题
\begin{equation}
(i_{1,2,3})_{opt} = \text{argmin}_{i_{1,2,3}} \sum_{c=1}^3 (
\Vert B_c ic - j_c \Vert_2^2 + \lambda_c \sum\{a=1}^5 \Vert H_a i_c \Vert_1 \\

  • \sum_{l \neq c} \beta_{cl} \sum_{a=1}^2 \Vert H_a i_c \cdot i_l - H_a i_l \cdot i_c \Vert_1
    )
    \tag{1}
    \end{equation}
    其中卷积矩阵$H_{1,2}$实现一阶导数，$H_{3,4,5}$实现二阶导数。式(1)中第一项是数据保真项，第二项确保梯度和边缘服从重尾分布（heavey-tailed distribution），最后一项表示交叉通道先验。
    继续阅读 →

线性约束最优化问题的Frank-Wolfe方法

发表于由

在无约束最优化问题的基础上，我们可以进一步来求解约束最优化问题。约束最优化问题的一般形式为：
$$
\begin{aligned}
&\min f(x) \\
&s.t. \quad g_i(x)\ge0, i=1,...,m
\end{aligned}
$$

先考虑$g_i(x)$均为线性函数的情况，此时问题与线性规划的约束条件相同，仅仅是目标函数变成了非线性的。我们可以用泰勒展开对目标函数进行近似，将它线性化。将$f(x)$在$x_k$处展开，有
$$
f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k)
$$
故原问题近似于
$$
\begin{aligned}
&\min f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k) \\
&s.t.\quad x \in S
\end{aligned}
$$
其中$S$为线性约束构成的可行域。去掉常量后，问题可以写为
$$
\begin{aligned}
&\min f(x)\approx \nabla f(x_k)^Tx \\
&s.t.\quad x \in S
\end{aligned}
$$
设此问题的最优解为$y_k$，则直观上$d_k=y_k-x_k$ 应当为原问题的可行下降方向。沿着此方向做一维搜索则可进行一次迭代。为了防止一维搜索的结果超出可行域，我们限制步长$0\leq\lambda\leq1$。注意到线性规划的可行域为凸集，由于$x_k$和$y_k$均为可行点，它们确定的连线均在可行域中。限制步长$0\leq\lambda\leq1$保证了一维搜索的结果在可行域中。

Frank-Wolfe算法的步骤总结如下：

  1. 选择初值。初始点$x_0\in S$，给定允许误差$\epsilon>0$，令$k=0$。
  2. 求解近似线性规划：$$ \begin{aligned}&\min \nabla f(x_k)^Tx \\ &s.t.\quad x \in S\end{aligned}$$ 得最优解$y_k$。
  3. 构造可行下降方向。令$d_k=y_k-x_k$。若$||\nabla f(x_k)^Td_k \leq \epsilon||$，停止计算，输出$x_k$；否则，转4。
  4. 进行一维搜索：$$\min_{0\leq \lambda \leq 1} f(x_k+\lambda d_k)$$得步长$\lambda_k$。令$$x_{k+1}=x_k+\lambda_k d_k \\ k \leftarrow k+1 $$，转2。

Frank-Wolfe方法将线性约束最优化问题转化为一系列线性规划问题和一维搜索问题求解。可以证明，当$f$具有连续一阶偏导数，且可行域$S$有界，Frank-Wolfe方法是收敛的。

无约束最优化方法学习笔记

发表于由

这一段时间学习优化理论中的一些经典方法，写下一些要点和体会，帮助自己和有需要的人理解最优化方法。

１.基础知识

首先来看无约束最优化问题：
\begin{equation}
\min f(x)
\end{equation}
其中函数 $f:R^n\rightarrow R$.求解此问题的方法方法分为两大类：最优条件法和迭代法。

所谓的最优条件法，是指当函数存在解析形式，能够通过最优性条件求解出显式最优解。对于无约束最优化问题，如果$f(x)$在最优点$\bar{x}$附近可微，那么$\bar{x}$是局部极小点的必要条件为：
\begin{equation}
\nabla f(\bar{x})=0
\end{equation}

我们常常就是通过这个必要条件去求取可能的极小值点，再验证这些点是否真的是极小值点。当上式方程可以求解的时候，无约束最优化问题基本就解决了。实际中，这个方程往往难以求解。这就引出了第二大类方法：迭代法。

迭代法，也称为“搜索”法，主要思想是通过简单的运算构造点列，逐渐逼近问题的最优解。这里说的“点”是多维空间中的点，也称为“向量”。还有少部分算法通过构造点的集合来逼近问题的最优解，如单纯形调优法。

用于求解无约束最优化问题的方法可以分为解析法和直接法两大类。解析法在构造迭代公式的过程中往往使用了泰勒展开来作近似或者推导，因此迭代步骤中含有梯度$\nabla f(x)$或黑塞(Hessian)矩阵$\nabla^2f(x)$，在问题的解析形态较好的情况下使用往往能获得比较快的收敛速度。而直接法则从物理角度思考如何递推，不会用到梯度或者黑塞矩阵，它对问题的解析形态几乎没有要求，只要能计算出函数值即可。当然，它的收敛速度往往难于保证。
继续阅读 →

Matlab实现FR共轭梯度法

发表于由

前一段时间学习了无约束最优化方法，今天用Matlab实现了求解无约束最优化问题的FR共轭梯度法。关于共轭梯度法的理论介绍，请参考我的另一篇文章 无约束最优化方法学习笔记。

文件testConjungateGradient.m用于测试共轭梯度法函数。测试文件需要定义函数$f$和自变量$x$，给定迭代初值$x_0$和允许误差$\epsilon$。函数设置了show_detail变量用于控制是否显示每一步的迭代信息。

% test conjungate gradient method
% by TomHeaven, hanlin_tan@nudt.edu.cn, 2015.08.25

%% define function and variable
syms x1 x2;
%f = xs^2+2*ys^2-2*xs*ys + 2*ys + 2;
f = (x1-1)^4 + (x1 - x2)^2;
%f = (1-x1)^2 + 2*(x2 - x1^2)^2;
x = {x1, x2};

% initial value
x0 = [0 0];
% tolerance
epsilon = 1e-1;

%% call conjungate gradient method
show_detail = true;
[bestf, bestx, count] = conjungate_gradient(f, x, x0, epsilon, show_detail);
% print result
fprintf('bestx = %s, bestf = %f, count = %d\n', num2str(bestx), bestf, count);

继续阅读 →

线性约束最优化问题的Frank-Wolfe方法

发表于由

在无约束最优化问题的基础上，我们可以进一步来求解约束最优化问题。约束最优化问题的一般形式为：
$$
\begin{aligned}
&\min f(x) \\
&s.t. \quad g_i(x)\ge0, i=1,...,m
\end{aligned}
$$

先考虑$g_i(x)$均为线性函数的情况，此时问题与线性规划的约束条件相同，仅仅是目标函数变成了非线性的。我们可以用泰勒展开对目标函数进行近似，将它线性化。将$f(x)$在$x_k$处展开，有
$$
f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k)
$$
故原问题近似于
$$
\begin{aligned}
&\min f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k) \\
&s.t.\quad x \in S
\end{aligned}
$$
其中$S$为线性约束构成的可行域。去掉常量后，问题可以写为
$$
\begin{aligned}
&\min f(x)\approx \nabla f(x_k)^Tx \\
&s.t.\quad x \in S
\end{aligned}
$$
设此问题的最优解为$y_k$，则直观上$d_k=y_k-x_k$ 应当为原问题的可行下降方向。沿着此方向做一维搜索则可进行一次迭代。为了防止一维搜索的结果超出可行域，我们限制步长$0\leq\lambda\leq1$。注意到线性规划的可行域为凸集，由于$x_k$和$y_k$均为可行点，它们确定的连线均在可行域中。限制步长$0\leq\lambda\leq1$保证了一维搜索的结果在可行域中。
继续阅读 →