基于迭代投影的梯度硬阈值追踪算法

梯度硬阈值追踪算法是求解稀疏优化问题的有效算法之一.考虑到算法中投影对最优解的影响,提出一种比贪婪策略更好的投影算法是很有必要的.针对一般的稀疏约束优化问题,利用整数规划提出一种迭代投影策略,将梯度投影算法中的投影作为一个子问题求解.通过迭代求解该子问题得到投影的指标集,并以此继续求解原问题,以提高梯度硬阈值追踪算法的计算效果.证明了算法的收敛性,并通过数值实例验证了算法的有效性.     

考虑帕累托最优解的多目标优化进化算法

大多数现有的进化算法在处理多目标优化问题(multi-objective optimization problem,MOP)时会遇到Pareto最优解稀疏的困难,特别是当决策变量的数目很大时,如旨在从大量候选特征中找出小部分特征的特征选择.为此,提出了一种求解大规模稀疏MOP的进化算法.算法考虑Pareto最优解的稀疏性,提出了一种新的种群初始化策略和遗传算子,以保证解的稀疏性.此外,还设计了一个测试套件来评估该算法在大规模稀疏MOP中的性能,实验结果和应用实例证明了该算法在处理大规模稀疏MOP问题上的优越性.     

《数值计算与计算机应用》2020年第41卷第4期摘要

刘伟峰.高可扩展、高性能和高实用的稀疏矩阵计算研究进展与挑战[J].数值计算与计算机应用,2020,41(3):259-281.摘要:稀疏矩阵算法是超级计算领域的热点和难点研究内容之一.本文从高可扩展、高性能和高实用这三个角度,对过去30年来国内外稀疏矩阵计算的部分主要研究工作进行了综述.并配合在三个GPU上十余个稀疏BLAS算法的测试数据.     

求解非对称线性方程组的不完全最小联合向后扰动法

正1引言在许多应用科学和工程计算中,经常需要求解大型非对称稀疏线性方程组Ax=b,(1)其中A∈R~(n×n)非奇异,x,b∈R~n.Krylov子空间方法~([1,19,20])是求解(1)的一类很有效的方法.Krylov子空间方法通常用残量范数作为判断算法终止的条件.若近似解是精确的,残量范数是小的,但是反过来残量范数小并不意味着近似解就是精确的,尤其当A是病态矩阵时~([21]).为了克服残量范数作为终止条件的不足,文[2]提出了利用向     

线性流形上对称正交反对称矩阵反问题的最小二乘解

设P是n阶对称正交矩阵,如果n阶矩阵A满足AT=A和(PA)T=-PA,则称A为对称正交反对称矩阵,所有n阶对称正交反对称矩阵的全体记为SARnp.令S={A∈SARnp f(A)=‖AX-B‖=m in,X,B〗∈Rn×m本文讨论了下面两个问题问题Ⅰ给定C∈Rn×p,D∈Rp×p,求A∈S使得CTAC=D问题Ⅱ已知A~∈Rn×n,求A∧∈SE使得‖A~-A∧‖=m inA∈SE‖A~-A‖其中SE是问题Ⅰ的解集合.文中给出了问题Ⅰ有解的充要条件及其通解表达式.进而,指出了集合SE非空时,问题Ⅱ存在唯一解,并给出了解的表达式,从而得到了求解A∧的数值算法.     

基于加速梯度算法的高维协方差矩阵估计的研究

稀疏性和正定性是高维稀疏协方差矩阵估计中要保证的两个重要性质.为了保证这两个性质被高效的实现,我们使用一个正定的l₁惩罚来估计高维协方差矩阵,并使用一个有竞争力的加速梯度算法去实现估计.实验结果表明,与其他方法相比,该方法在计算时间、正确率、错误率、F范数等指标上具有较好的表现,同时实现了最优解达到O(1/k~2)的收敛速率.     

矩阵方程AX=B的双反对称最佳逼近解

本文主要讨论下而两个问题并得到相关结果:问题Ⅰ:给定A ∈ R~(k×n),B ∈ R~(k×n),求X ∈ BASR~(n×n),使得AX=B.问题Ⅱ:给定X* ∈R~(n×n),求X使得‖X-X~*‖=minX∈S_E‖X-X~*‖,其中S_E是问题Ⅰ的解集合,‖·‖是Frobenius范数.通过对上述问题的讨论给出了问题Ⅰ解存在的充分必要条件和其解的一般表达式同时给出了问题Ⅱ的解,算法,和数值例子.     

求解稀疏分裂可行问题的一种投影算法

本文研究了稀疏分裂可行问题.通过将分裂可行问题转化为一个目标函数为凸函数的稀疏约束优化问题,设计一种梯度投影算法来求解此问题,获得了算法产生的点列可以收敛到稀疏分裂可行问题的一个解.用数值例子说明了算法的有效性.     

利用半群代数中良序基构造解稀疏多项式方程组特征值方法

本文利用半群代数k[A]中良序基,构造了求稀疏多项式方程组解的特征值矩阵,并给出了可以构造方阵的条件.     

稀疏线性规划研究

稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题;其次采用交替方向乘子法(ADMM)求解该问题;最后证明了算法在近似问题上的收敛性.数值实验表明,算法在大规模数值算例上的表现优于已有的混合遗传算法;同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性.     

一个求大规模非负不可约稀疏矩阵的谱半径及特征向量的新算法

本文设计了一个计算非负不可约矩阵的谱半径及其特征向量的新算法,并证明了其收敛性.该算法计算晕不大,占用内存少,有相同的0元模式,从而在大规模稀疏矩阵的计算中优势明显.最后用实例验证了此算法的可行性.     

大规模稀疏线性规划问题的初等矩阵解法

当线性规划约束条件的系数矩阵A为稀疏矩阵时,一般称为稀疏线性规划问题.解这类问题有分解原则及一般上界法,我们这里讨论初等矩阵法。 §1.齐次线性不等式的初等矩阵解法 [3] 中给出x≥0满足Ax≥0的充要条件是x=K(A)ω,ω≥0.     

固定时间梯度流在?_1-?_2范数中的稀疏重构

压缩感知(compressed sensing,CS)是一种全新的信号采样技术,对于稀疏信号,它能够以远小于传统的Nyquist采样定理的采样点来重构信号.在压缩感知中,采用动态连续系统,对?_1-?_2范数的稀疏信号重构问题进行了研究.提出了一种基于固定时间梯度流的稀疏信号重构算法,证明了该算法在Lyapunov意义上的稳定性并且收敛于问题的最优解.最后通过与现有的投影神经网络算法的对比,体现了该算法的可行性以及在收敛速度上的优势.     

含高次逆幂的矩阵方程对称解的双迭代算法

本文研究了在控制理论和随机滤波等领域中遇到的一类含高次逆幂的矩阵方程的等价矩阵方程对称解的数值计算问题.采用牛顿算法求等价矩阵方程的对称解,并采用修正共轭梯度法求由牛顿算法每一步迭代计算导出的线性矩阵方程的对称解或者对称最小二乘解,建立了求这类矩阵方程对称解的双迭代算法,数值算例验证了双迭代算法是有效的.     

计算大规模矩阵最大最小奇异值和奇异向量的两个精化Lanczos算法

1.引言 在科学工程计算中经常需要计算大规模矩阵的少数最大或最小的奇异值及其所对应的奇异子空间。例如图像处理中要计算矩阵端部奇异值之比作为图像的分辨率,诸如此类的问题还存在于最小二乘问题、控制理论、量子化学中等等。然而大多实际问题中的矩阵是大型稀疏矩阵,且需要的是矩阵的部分奇异对。如果计算A的完全奇异值分解(SVD),则运算量和存储量极大,甚至不可能。因此必须寻求其它有效可靠的算法。 假设A的SVD为     

基于SCN函数共轭梯度方向的稀疏向量特征提取算法

稀疏向量特征提取是指在优化时利用各种范数对解进行约束,从而获得带有稀疏特征的最优解,其广泛应用于复杂系统中的机器学习、深度学习和大数据分析等领域的特征提取问题.大量的研究表明各种范数如L₀范数、L₁范数和L₂范数的方法都存在各自的缺点,主要表现在越容易求解的范数越不精准稀疏,越精准稀疏的范数越难求解.文章提出了一种基于SCN函数共轭梯度方向的稀疏向量特征发现算法(CGDL),稀疏向量特征发现可以用一个稀疏特征提取优化模型建立,其目标函数是一个SCN函数,对其中的L₀范数进行转换,形成一个具有特殊结构优化问题,这个问题等价于双层规划的凸-凹极小极大化问题,这类问题可以解决稀疏回归、图像特征和压缩感知等问题.文章给出了上述模型的稀疏特征提取算法的详细计算步骤和收敛性分析证明,并且对给定的实际数据集和高维模拟数据集对算法的有效性、复杂性和收敛速度进行了数值对比实验,表明了该算法在精准度和稀疏性上显著优于其他对比方法,并且具有较好的收敛速度.     

基于固定序的Bellman-Ford算法的改进

固定序算法是Bellman-Ford算法的一种基本改进算法。为了改变固定序算法在稀疏图上的劣势,本文通过预先订制参与迭代的点的计算顺序,对该算法进行了改进。实验表明,在稀疏图上, 改进后的算法相对于原算法计算效率提高了近50%, 并能够与国际流行的先进先出算法相媲美。本文的工作表明,固定序算法不仅在大规模稠密图上具有明显的优势,而且在稀疏图上也具有很强的竞争力。     

美式看跌期权定价中的小波方法

本文采用有限差分格式和 Daubechies正交小波 ,提出了一种求解 Black- Scholes方程数值解新算法 .为美式看跌期定价提供了一条新的途径 .利用小波基的自适应性和消失矩特性 ,使偏微分算子矩阵和小波级数稀疏化 ,大大减少了计算量 .     

基于SCAD罚函数的有噪压缩感知

研究有噪声的压缩感知,提出了基于SCAD罚函数的压缩感知策略,并给出一种高效的阈值迭代算法,从理论上证明了算法的有效性.大量实验验证基于SCAD罚函数的压缩感知策略解的稀疏性及稳健性.     

用单纯算法求解三解定理

在不动点的计算中,人们越来越注意单纯算法,特别是各种基于Brouwer不动点原理的定理,都可以有相应的单纯算法.本文讨论三解定理的单纯算法.§1介绍三解定理,它是由Amann最早提出的;§2介绍用单纯算法计算Brouwer不动点;§ 3考虑Amann三解定理的计算方案.