论文部分内容阅读
最近,在交通、信号与图像处理、机器学习等应用领域中涌现出大量具有特殊结构的变分不等式问题和非凸非光滑优化问题,如结构变分不等式问题和具有凸函数的差（Difference-of-convex,DC）结构的优化问题.因此,如何根据这些问题的结构和性质,如大规模结构、DC结构、线性约束和目标函数可分离,来设计简单、高效的算法便成为热门的研究方向.本博士学位论文主要从交替方向乘子法（Alternating direction method of multipliers,ADMM）、预测-校正算法、凸函数的差算法（Difference-of-convex algorithm,DCA）、Moreau包络函数以及随机方差减小策略等几个方面研究这些特殊问题的算法设计.本博士学位论文的主要贡献和创新如下:1.提出基于交替投影的修正预测-校正算法（Alternating projection based mod-ified prediction correction method,AP-MPC）来求解结构变分不等式问题,并在一定的条件下证明其全局收敛性.在每一迭代步中,AP-MPC利用Armijo线搜索和交替投影技巧来生成预测点,并通过较小的计算量来计算下一迭代点.AP-MPC克服了已有的临近ADMM型算法需要求解隐式投影方程的困难,且松弛了已有的基于交替投影的预测-校正算法要求目标函数具有Lipschitz连续性这一假设条件.通过在交通平衡问题、可分离凸二次优化问题和校定最小二乘协方差问题的数值实验结果,我们验证了AP-MPC的有效性.2.提出混合Bregman交替方向乘子法（Hybrid Bregman alternating direction method of multipliers,H-BADMM）来求解线性约束DC优化问题.一方面,H-BADMM结合次梯度步和临近步来计算凹函数,利用外插值技巧来处理非光滑凸函数,从而来加速基于DCA的Bergman ADMM（BADMM-DCA）.另一方面,利用Kurdyka-?ojasiewicz（K?）性质等条件,证明了H-BADMM的全局收敛性,且松弛了BADMM-DCA需要凹函数梯度具有Lipschitz连续性的假设条件.我们通过对全变差图像储存问题、l1-2正则最小二乘问题的数值实验验证H-BADMM的有效性.3.基于随机路径积分的差分估计法（Stochastic Path-Integrated Differential Es-timato R,SPIDER）,我们提出一个随机方差减小临近DCA（Stochastic variance re-duction proximal difference-of-convex algorithm,SVRPDCA）来求解大规模DC优化问题.并给出SVRPDCA求解大规模DC优化问题?-平衡点的梯度复杂度和临近算子复杂度.随后,基于Moreau包络函数逼近技巧和SVRPDCA,我们提出修正的临近DCA（Modified stochastic proximal difference-of-convex algorithm,MSPDCA）来求解一类特殊的非凸非光滑问题.其目标函数为光滑函数、非光滑凸函数和非光滑非凸函数之和.并给出MSPDCA求解上述问题的?-静态点的梯度复杂度.SVRPDCA和MSPDCA方法降低了一些已有随机DCA型算法的梯度复杂度.最后,我们通过对非负稀疏主成分分析的数值实验来验证SVR-PDCA和MSPDCA的有效性.