月度归档：2016年08月

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$保证了一维搜索的结果在可行域中。
继续阅读 →