一种改进的求解矩阵补全问题的原始-对偶算法

低秩矩阵补全问题作为一类在机器学习和图像处理等信息科学领域中都十分重要的问题已被广泛研究.一阶原始-对偶算法是求解该问题的经典算法之一.然而实际应用中处理的数据往往是大规模的.针对大规模矩阵补全问题,本文在原始-对偶算法的框架下,应用变步长校正技术,提出了一种改进的求解矩阵补全问题的原始-对偶算法.该算法在每一步迭代过程中,首先利用原始-对偶算法对原始变量和对偶变量进行更新,然后采用变步长校正技术对这两块变量进行进一步的校正更新.在一定的假设条件下,证明了新算法的全局收敛性.最后通过求解随机低秩矩阵补全问题及图像修复的实例验证新算法的有效性.     

群零模正则化问题的等价Lipschitz优化模型

针对群零模正则化问题, 从零模函数的变分刻画入手, 将其等价地表示为带有 互补约束的数学规划问题(简称MPCC问题), 然后证明将互补约束直接罚到MPCC的目标函数而得到的罚问题是MPCC问题的全局精确罚. 此精确罚问题的目标函数不仅在可行集上全局Lipschitz连续而且还具有满意的双线性结构, 为设计群零模正则化问题的序列凸松弛算法提供了满意的等价Lipschitz优化模型.     

鲁棒稀疏重构问题的凝聚同伦算法

鲁棒稀疏重构问题是信号处理领域的重要问题,该问题的数学本质是一个NP难的数学优化问题.同伦算法是一类典型的路径跟踪算法,该算法是解非线性问题的一类成熟算法,具有全局收敛性,且易于并行实现.本文考虑同伦算法在鲁棒稀疏重构问题中的数值求解.基于l_∞范数及罚函数策略,我们首先将原始的基于l_0范数的最优化模型,转化为含参数的无约束极大极小值问题,进而构造凝聚函数光滑化模型中的极大值函数,并构造凝聚同伦算法数值求解.数值仿真实验验证了新方法的有效性,为大规模鲁棒重构问题的并行化数值求解奠定基础.     

具有Log型惩罚函数的稀疏正则化

研究具有Log型惩罚函数的稀疏正则化,给出一种新的非凸变量选择及压缩感知策略,提出一种高效快速阈值迭代算法.并通过变量选择问题和稀疏信号重建验证了所提出的Log型稀疏正则化模型的有效性.     

求解低秩矩阵恢复问题的非单调交替梯度方向法

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了...     

同伦摄动稀疏正则化方法及其应用

稀疏正则化方法在参数重构中起到了越来越重要的作用.与传统的正则化方法相比,稀疏正则化方法能较好地重构稀疏变量.由于稀疏正则化的不可微性,需要对已有的经典算法进行改进.本文构建同伦摄动稀疏正则化方法克服标准稀疏正则化的不可微性,并将该方法应用到基于布莱克一斯科尔斯期权定价模型重构隐含波动率和基于托达罗模型重构政策参数.数值实验表明,所提出的方法是收敛和稳定的.     

求最优权对集的一个对偶算法

1.引言 Edmonds给出了求一个图的最大权对集的算法它是从一个满足原始对偶可行的解出发使其逐步满足互补松驰条件。[1]描述了一个求最大权完美对集原始算法。它是从一个满足互补松驰条件的原始可行解出发,使其逐步满足对偶可行条件。我们给出一个求图的最大权完美对集的对偶算法,它是从一个满足互补松驰条件的对偶可行解出发使其逐步满足可行条件。本算法开始不要求给出图的一个完全对集,其对偶变量的改变法则也较[1]中的法则简单得多。其基本方法仍是用Edmonds的花的算法[2]。我们将说明本文的算法可用来解其他的最优对集问题。本文中采用的术语参看[2]。     

线性约束两分块非凸优化的ADMM-SQP算法

基于乘子交替方向法(ADMM)和序列二次规划(SQP)方法思想, 致力于研究线 性约束两分块非凸优化的新型高效算法. 首先, 以SQP思想为主线, 在其二次规划(QP)子问题的求解中引入ADMM思想, 将QP分解为两个相互独立的小规模QP求解. 其次, 借助增广拉格朗日函数和Armijo线搜索产生原始变量新迭代点. 最后, 以显式解析式更新对偶变量. 因此, 构建了一个新型ADMM-SQP算法. 在较弱条件下, 分析了算法通常意义下的全局收敛性, 并对算法进行了初步的数值试验.     

一种新的求解带约束的有限极大极小问题的精确罚函数

提出了一种新的精确光滑罚函数求解带约束的极大极小问题．仅仅添加一个额外的变量,利用这个精确光滑罚函数,将带约束的极大极小问题转化为无约束优化问题． 证明了在合理的假设条件下,当罚参数充分大,罚问题的极小值点就是原问题的极小值点．进一步,研究了局部精确性质．数值结果表明这种罚函数算法是求解带约束有限极大极小问题的一种有效算法．     

不等式约束优化问题的低阶精确罚函数的光滑化算法

对不等式约束优化问题提出了一个低阶精确罚函数的光滑化算法. 首先给出了光滑罚问题、非光滑罚问题及原问题的目标函数值之间的误差估计,进而在弱的假
设之下证明了光滑罚问题的全局最优解是原问题的近似全局最优解. 最后给出了一个基于光滑罚函数的求解原问题的算法,证明了算法的收敛性,并给出数值算例说明算法的可行性.     

含参原始与对偶弱向量近似平衡问题的稳定性北大核心CSCD

借助于标量化技巧讨论了含参原始与对偶弱向量近似平衡问题的稳定性.首先,在邻近C-次似凸性假设下获得原始平衡问题近似解集的连通性和近似解集映射的Hausdorff上(下)半连续性.然后,利用标量化方法,在较弱假设下获得了含参对偶弱向量平衡问题近似解集的连通性及近似解集映射的Hausdorff连续性的充分性条件.最后,给出了在向量优化问题中的一个应用.所得结果推广和改进了已有文献中相应结论.     

含参原始与对偶弱向量近似平衡问题的稳定性

借助于标量化技巧讨论了含参原始与对偶弱向量近似平衡问题的稳定性.首先,在邻近C-次似凸性假设下获得原始平衡问题近似解集的连通性和近似解集映射的Hausdorff上(下)半连续性.然后,利用标量化方法,在较弱假设下获得了含参对偶弱向量平衡问题近似解集的连通性及近似解集映射的Hausdorff连续性的充分性条件.最后,给出了在向量优化问题中的一个应用.所得结果推广和改进了已有文献中相应结论.     

一类非线性半向量二层规划问题的罚函数方法

本文研究了一类非线性-线性半向量二层规划问题的罚函数求解方法.对于该类半向量二层规划问题,首先基于下层问题的加权标量化方法和Karush-Kuhn-Tucker最优性条件,将其转化为一般的二层规划问题,并取下层问题的互补约束为罚项,构造出相应的罚问题;然后分析罚问题最优解的相关特征以及最优性条件,进而设计了相应的罚函数算法;最后以相关算例验证了罚函数算法的可行、有效性.     

一种基于正则化的稀疏表示方法

提出了一种基于正则化技术的信号稀疏表示方法.该方法与经典稀疏表示算法的主要区别可概括为两点:其一,直接使用e_0模而不是被广泛采用的e_1模来度量稀疏性;其二,正则化项的引入使得该模型得到的信号表达是所有表示中最优稀疏的.在本文中,正则化项采用框架势来描述稀疏表示的"最优性",利用二次可微的凹函数来逼近e_0模,得到了求解所提出的正则化模型的近似算法,并给出了收敛性分析.此外,数值实验也显现了本文所提模型及算法相比于经典算法的优越性.     

基于二次函数光滑化逼近的修正低阶罚函数

针对不等式约束优化问题, 给出了通过二次函数对低阶精确罚函数进行光滑化逼近的两种函数形式, 得到修正的光滑罚函数. 证明了在一定条件下, 当罚参数充分大, 修正的光滑罚问题的全局最优解是原优化问题的全局最优解. 给出的两个数值例子说明了所提出的光滑化方法的有效性.     

一种内外迭代方法求解三凸函数和优化问题

近年来,关于多个凸函数和的优化问题受到广泛关注.本文研究三个凸函数和f(x)+g(x)+h(Bx)的一类凸优化问题,其中f (x)可微且具有Lipschitz连续梯度, g(x)和h(x)是正则下半连续简单凸函数, B是一个有界线性算子.此类优化问题在信号恢复和图像处理等实际问题中有着广泛的应用.为充分利用问题中的可微函数,本文基于向前向后分裂算法和三算子分裂算法框架,建立若干具有内外迭代形式的算法.在推导迭代算法的过程中,本文提出基于对偶和原始对偶方法求解函数g+h?B和h?B的邻近算子.在对参数一定假设条件下,本文证明所提出的迭代算法收敛性.通过与Condat和Vu算法、原始对偶不动点(primal-dual?xed point, PDFP)算法和原始对偶三算子(primal-dual three-operator, PD3O)算法比较,建立三种迭代算法与本文提出的迭代算法之间的联系.最后,通过对融合Lasso问题、约束全变分正则化问题和低秩全变分图像超分辨率重建问题实施一系列数值实验,验证所提出的迭代算法的有效性.     

双层规划问题基于对偶理论的遗传算法

针对下层为线性规划的非线性双层规划问题，提出了一种基于下层对偶理论的遗传算法。首先利用下层对偶问题可行域的极点对上层变量的取值域进行划分，使得每一个划分区域对应一个极点。根据原一对偶问题最优解的关系，确定每个划分区域对应的下层最优解。其次利用罚函数方法处理了上层约束，设计了一个依赖于种群变化的动态罚因子。对20个测试问题的数值结果表明，所提出的算法是可行有效的。     

组稀疏优化问题精确连续Capped-L_(1)松弛北大核心CSCD

本文主要研究损失函数为凸函数且带有约束的组稀疏正则回归问题及组稀疏正则项的精确连续Capped-L_(1)松弛问题.首先对组Capped-L_(1)松弛问题定义了三类稳定点:D(irectional)-稳定点、C(ritical)-稳定点、L(ifted)-稳定点,然后刻画了这三类稳定点之间的关系.进一步,给出了组Capped-L_(1)松弛问题和原始组稀疏正则问题的最优性条件,并从全局解和局部解角度讨论了松弛问题和原问题解的等价关系.     

求解正定二次规划的一个全局收敛的滤子内点算法

现有的大多数分类问题都能转化成一个正定二次规划问题的求解.通过引入滤子方法,并结合求解非线性规划的原始对偶内点法,给出求解正定二次规划的滤子内点算法.该算法避免了使用效益函数时选取罚因子的困难,在较弱的假设条件下,算法具有全局收敛性.     

基于两种非凸惩罚函数的稀疏组变量选择

利用正则化方法来进行变量选择是近年来研究的热点.在实际应用中解释变量常常以组的形式存在,通常我们希望将重要的组和组内重要的协变量选择出来,即双重变量选择.基于两种非凸惩罚函数SCAD和MCP,分别提出了稀疏Group SCAD和稀疏Group MCP估计方法,通过分块坐标下降迭代算法,达到组内和组间变量同时稀疏的效果.数值模拟结果表明本文提出的两种方法在模型预测和变量选择能力上优于Group Lasso和稀疏Group Lasso算法.并将该算法有效地应用于实际的初生儿体重数据集分析中.