实例:近似点算法解 LASSO 问题
对于 LASSO 问题
其对应于等价问题
利用近似点算法进行求解。对于近似点子问题利用梯度法不精确求解,并考虑半光滑牛顿法加速。
目录
构造 LASSO 问题
设定随机种子。
clear; seed = 97006855; ss = RandStream('mt19937ar','Seed',seed); RandStream.setGlobalStream(ss);
构造 LASSO 优化问题
生成随机的矩阵 和向量
以使得
。正则化系数
。随机迭代初始点。
m = 512; n = 1024; A = randn(m, n); u = sprandn(n, 1, 0.1); b = A * u; x0 = randn(n, 1); mu = 1e-3;
利用近似点算法(PPA)求解 LASSO 问题
首先在更严格的停机准则下进行试验,将收敛时得到的历史最优函数值作为真实的最优值的参考 。
opts = struct(); opts.verbose = 0; opts.maxit = 20; opts.ftol = 1e-14; opts.gtol = 1e-10; [x, out] = LASSO_ppa(x0, A, b, mu, opts); f_star = min(out.fvec);
利用 PPA 求解 LASSO 问题。
opts = struct();
opts.verbose = 0;
opts.ftol = 2e-8;
opts.gtol = 2e-6;
opts.maxit = 10;
opts.step_type = 'fixed';
[x, out] = LASSO_ppa(x0, A, b, mu, opts);
data1 = (out.fvec - f_star)/f_star;
k1 = length(data1);
令正则化系数 ,重复实验。在更严格的停机准则下进行试验, 将收敛时得到的历史最优函数值作为真实的最优值的参考
。
mu = 1e-2; opts = struct(); opts.verbose = 0; opts.maxit = 20; opts.ftol = 1e-14; opts.gtol = 1e-10; [x, out] = LASSO_ppa(x0, A, b, mu, opts); f_star = min(out.fvec);
利用 PPA 求解 LASSO 问题。
opts = struct();
opts.verbose = 0;
opts.ftol = 2e-8;
opts.gtol = 2e-6;
opts.maxit = 10;
mu = 1e-2;
opts.step_type = 'fixed';
[x, out] = LASSO_ppa(x0, A, b, mu, opts);
data2 = (out.fvec - f_star)/f_star;
k2 = length(data2);
结果可视化
对每一步的函数值与最优函数值之间的相对误差进行可视化。
fig = figure; semilogy(0:k1-1, data1, '-o', 'Color',[0.2 0.1 0.99], 'LineWidth',2); hold on semilogy(0:k2-1, data2, '-.*','Color',[0.99 0.1 0.2], 'LineWidth',2); set(gca,'xtick',1:max(k1,k2)); legend('\mu = 10^{-3}','\mu = 10^{-2}'); ylabel('$(f(x^k) - f^*)/f^*$', 'fontsize', 14, 'interpreter', 'latex'); xlabel('迭代步'); print(fig, '-depsc','ppa.eps');
![](demo_ppa_01.png)
结果分析
上图展示了在 LASSO 问题上近似点法的数值表现。固定步长时,每一次外层迭代, 目标函数值都有明显下降,外层迭代仅 次目标函数已经接近收敛。
注意,每一次外层迭代都需要求解关于 的子问题,算法的主要运算量在内迭代子问题的求解上。 因此有必要对子问题使用半光滑牛顿法进行加速。
参考页面
算法请参考 LASSO问题的近似点算法。
此页面的源代码请见: demo_ppa.m。
版权声明
此页面为《最优化:建模、算法与理论》、《最优化计算方法》配套代码。 代码作者:文再文、刘浩洋、户将,代码整理与页面制作:杨昊桐。
著作权所有 (C) 2020 文再文、刘浩洋、户将