求解稀疏子空间聚类问题的块坐标下降算法研究

发布时间：2024-03-08 19:56

　　块坐标下降法(BCD)循环使用不同的块坐标方向求解问题的最优解.由于此类算法具有迭代成本低、内存需求小、易于并行化等特点,在大规模数值优化中得到了广泛应用.给定一组来自多个子空间的数据,子空间聚类的目的是将这组数据分割到各自的子空间中,并同时清除可能存在的噪声.子空间聚类算法是实现高维数据集聚类的有效方法,最新研究表明聚类任务可以刻画为带有块对角正则项的非光滑非凸优化问题.本文研究求解稀疏子空间聚类问题的BCD算法,分析算法的收敛性,测试算法的数值有效性,并与著名算法做效率比较.第一章,首先,给出本文所需的优化知识,介绍临近块坐标下降法(PBCD),对称GaussSeidel技术以及交替方向乘子法(ADMM).然后,简单介绍子空间聚类问题的部分优化模型,并给出关于此问题的部分研究成果.最后,简单陈述本文的主要贡献,同时给出本文所用的符号.第二章,使用PBCD来提高块对角正则化算法(BDR)的效率,使用对称Gauss-Seidel技术使每个子问题易于求解,并在一定的条件下分析PBCD算法的收敛性.最后采用Nesterov的加速技术(命名为APBCD₁),并给出其迭代...

【文章页数】：59 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 基本概念
    1.2 块坐标下降法
        1.2.1 传统块坐标下降法
        1.2.2 临近块坐标下降法
    1.3 对称Gauss-Seidel技术(sGS)
    1.4 交替方向乘子法
        1.4.1 经典交替方向乘子法
        1.4.2 半临近交替方向乘子法
        1.4.3 耦合交替方向乘子法
    1.5 子空间聚类问题及其部分研究进展
    1.6 本文主要贡献
    1.7 本文所用符号
第二章 求解惩罚模型的临近块坐标下降法
    2.1 算法设计
    2.2 子问题求解
    2.3 Nesterov加速
    2.4 加速临近块坐标下降法
第三章 求解原模型的临近块坐标下降法和交替方向乘子法
    3.1 求解原模型的临近块坐标下降法
    3.2 求解原模型的交替方向乘子法
第四章 数值实验
    4.1 实验说明
    4.2 算法BDR和APBCD 1的测试
    4.3 算法C-ADMM和APBCD 2的测试
第五章 结论
参考文献
致谢



本文编号：3922316