R~n中构形和单纯复形的一个最优度量不等式

对于R~n中一般位置的点构形,定义了第r个极小凸包距离的概念,证明了极小凸包距离和极小点-超平面距离之间的一个最优不等式.该不等式的一个直接推论是:对于R~n中一个k-维单纯复形K,我们能用其顶点集的极小点-超平面距离下估计K的Gromov-Guth厚度.进一步,在每一个维数k,构造了例子说明该下界几乎是最优的.     

一般欧氏空间点集凸包的快速实时算法

点集凸包算法是被Shmaos等称之为计算几何中的基本问题之一,这是由于它在计算机辅助设计、计算机图形学、模式识别和运筹学等领域中有着十分广泛的应用。 对于2、3维凸包算法的研究已有许多成果,给出了各种不同意义下的最佳算法(参见[2])。但是对于高维空间点集凸包算法的研究却甚少,目前只有两种算法在计算几何中得到应用。造成这种局面的因素乃是高维空间的抽象性质,缺少2,3维空间的那种几     

次限制拟阵基的排序算法

§1 引言本文对一般的拟阵,给出在一个子集上具有次限制所有拟阵基的排序算法。著名的“greedy”算法是求连通图最小权的支撑树的好算法。在连通图上特别指定了一个顶点,求在该顶点次限制的最小权的支撑树,Glover—Klingman也给出了好算法。Burns—Haff给出了图的支撑树权的大小进行排序的生成算法,并且指出能够把它推广为拟阵基的排序算法。本文对一般的拟阵,给出在一个集上具次限制的所有拟阵基的按权的大小进行排序的生成算法。     

解线性规划改进的Bartels-Golub算法

其中A是秩为m的m×n矩阵,c、x是n维向量,b是m维向量,由凸性理论知,约束(1.2)构成一个n维欧几里德空间的凸多面集,这个凸多面集的顶点就是约束的基本可行解,线性函数z=c~Tx在这个凸多面集的顶点上取得它的极值。根据这个理论,线性规划的单纯形法就是从某个基本可行解过渡到另一个基本可行解,而使目标函数值下降。     

“凸包”的应用

定义1 对于平面图形内的任意两点A、B,线段AB上的所有点都在形内,这样的平面图形叫做凸形。显然,平面几何中研究的线段,三角形、凸多边形等都是凸形。定义2 对于平面上的有限个点所组成的平面点集,存在一个凸多边形,它包含这整个点集,且其顶点与这集的点重合。这样的凸多边形称为已知点集的凸包。特殊地,当平面上的点在一直线上时,凸包为线段。平面上有限点集的凸包的存在性从直观上看是显然的。在给定的有限个点的每个点插上大头针,用一根线圈上这些针,拉紧后构成的图形就是凸包。自然,这个直观的考虑不是凸包存在性的严格证明,     

一个求外平面图最小顶点赋权反馈点集的线性时间算法

若从一个图中去掉某些顶点后得到的导出子图是无圈图,则所去的那些顶点组成的集合就是原图的反馈点集.本文主要考虑外平面图中的反馈点集并给出了一个求外平面图最小顶点赋权反馈点集的线性时间算法.     

确定Ramsey数下界值的随机算法

文[1—2]借助于计算机得到了几个Ramsey数的下界值,但由于计算机确定Ramsey数的下界值往往需要判断多达指数级的各种情况,因此所需的计算时间常使人难以接受.本文提出了一种确定Ramsey数r(k,l)下界值的随机算法,该算法试图随机而有针对性地构造一个有n个顶点的简单图G,使G中既无k个顶点的团又无l个顶点的独立集,从而确定n+1是r     

基于CCH的SVM几何算法及其应用

支持向量机(support vector machine(SVM))是一种数据挖掘中新型机器学习方法.提出了基于压缩凸包(compressed convex hull(CCH))的SVM分类问题的几何算法.对比简约凸包(reducedconvex hull(RCH)),CCH保持了数据的几何体形状,并且易于得到确定其极点的充要条件.作为CCH的实际应用,讨论了该几何算法的稀疏化方法及概率加速算法.数值试验结果表明所讨论的算法可降低核计算并取得较好的性能.     

顶点覆盖约束下的同类机排序算法研究

给定m台同类机和n个工件,其中第j台机器的速度为s_j,第i个工件的加工时间为p_i并且在第j台机器上的负载为p_i/s_j.构造一个顶点赋权无向图G=(V,E;w),其中图G的n个顶点代表这n个工件,顶点权重代表相应工件的加工时间.本文研究顶点覆盖约束下的同类机排序问题.该问题是两个组合最优化问题的组合问题,其目标为首先确定图G的一个顶点覆盖,即图的一个顶点子集,使得图中每一条边都至少存在一个顶点属于该子集;然后把这个子集所代表的相应工件集放到m台同类机上加工,使得最大完工时间最小.该问题是NP-hard的.本文基于分层算法和LSPT算法设计一个■-近似算法,当所有机器的速度都相差不大时,该算法的近似效果较好.     

一种新的求解变分不等式的惯性双次梯度外梯度算法（英文）

当可行集为一光滑凸函数的下水平集时,文献[Optimization,2020,69(6):1237-1253]提出了一种惯性双次梯度外梯度算法来求解Hilbert空间中的单调且Lipschitz连续的变分不等式问题.该算法在每次迭代中仅需向一个半空间计算两次投影,并得到了算法的弱收敛结果.本文通过使用黏性方法以及在惯性步采用新的步长来修正该算法.在适当的假设条件下证明了新算法所生成的序列能强收敛到变分不等式的一个解.此外,新算法在每次迭代中也仅需向半空间计算两次投影.     

最小权点覆盖问题的一个近似算法

在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.     

单位球面S~(n-1)上球凸集的分析研究方法（英文）

本文研究了欧式空间单位球面S~(n-1)上秋凸集的定义与基本性质.利用径向函数,定义了空间中有限个点的凸组合运算,并由此给出了S~(n-1)上球凸集的分析定义和集合球凸包的定义.讨论了球凸集和球凸包的基础性质.最后证明了任一闭球凸集都可以表示为其端点集的球凸包.这个结论的形成与获证完全得益于本文采用的分析方法.     

2-控制数和连通2-控制数相等的图(英文)

任意一个图G =(V ,E) ,S是V(G)的子集 ,如果对每一个顶点u∈V-S都存在顶点v∈S ,使得d(u ,v) ≤ 2 ,则称S为G的一个 2 控制 .称最小的 2 控制集的顶点个数为G的 2 控制数 ,记为γ2 (G) .如果G的一个 2 控制集S的生成子集〈S〉是一个连通图 ,则称S为G的一个连通 2 控制集 .称最小的连通 2 控制集的顶点个数为G的连通 2 控制数 ,记为γc2 (G) .本文论述了树和单圈图中 2 控制数和连通 2 控制数相等的充分必要条件 .     

赋权树状网络中r-控制集问题和k-中心问题

图G=(V, E;f,ω)是顶点和边都赋权的树,f:V→R+,ω:E→R+.本文给出了顶点u与v之间距离的一种新的定义.在顶点和边都赋权的树中,研究在新距离条件下的r-控制集问题与k-中心问题.对于r-控制集问题,设计出了复杂性为Ο(n)的多项式时间算法;对于k-中心问题,设计出了Ο(n2log n)的多项式时间算法.     

无单调性集值变分不等式的一种投影算法

本文给出了求解无单调性集值变分不等式的一个新的投影算法,该算法所产生的迭代序列在Minty变分不等式解集非空且映射满足一定的连续性条件下收敛到解.对比文献[10]中的算法,本文中的算法使用了不同的线性搜索和半空间,在计算本文所引的两个数值例子时,该算法比文献[10]中的算法所需迭代步更少.     

一种面向图像识别的神经网络通用扰动生成算法

近年来,基于深度神经网络的图像识别技术表现出良好的性能,然而研究表明神经网络容易受到对抗扰动攻击而发生分类错误,施加一个小的通用扰动就能使神经网络在整个数据集上失效.为构建更加健壮的神经网络,对通用扰动生成的研究显得至关重要.通用扰动生成问题要求得到一个扰动向量对整个数据集产生指定扰动率的攻击效果,相较于单张图片扰动生成问题其约束条件更严格,计算难度更大.目前已有算法得到的通用扰动范数较大,容易被人眼识别.文章基于优化理论提出新的通用扰动生成算法,在达到指定扰动率的同时能产生更小的通用扰动.算法结合PCA降维思想克服了问题的规模性带来的困难;然后利用单张对抗扰动向量的均值叠加随机噪声,得到满足扰动率的初始通用扰动;最后改进梯度下降方法在保证扰动率的同时得到更小的通用扰动.实验表明,该方法可有效攻击各类先进神经网络:在达到相同扰动率的情况下,所得通用扰动的范数较Uni.Perturbation算法的结果平均降低了54%.     

字典序地生成有序根树的一个算法

§1.引言由于树的生成在计算机科学中有着重要应用,近年来许多文章研究了树的生成,其中大多数文章是讨论2分树及 k 分树的生成.研究一般有序根树的文章尚少.文献[1]给出了有序根树的一个序列表示法,并描述了一个生成有序根树的算法.文献[2]及[3]讨论了生成2分树及 k 分树的算法.本文用0,1序列表示有序根树,并给出了一个字典序地生成具有 n 个顶点的所有有序根树的算法.本文的表示法及算法与文献[1]中所提方法不同.本算法亦可用来生成具有 n 个叶子的所有2分树.它比[2]中的算法更简单.本文中未加说明的术语皆见[1].     

字典序地生成有序森林的一个算法

本文给出有序森林的一种序列表示法,并描述了一个字典序地生成具有n个顶点的所有有序森林的一个算法.它是[1]中算法的推广.§1 有序森林的序列表示法文献[1]给出了有序根树的一种序列表示法.本文利用[1]中的表示法给出有序森林的一种序列表示法及生成它们的算法.本文中未加说明的术语皆见[1].若F的每一个连通     

凸多胞形的保顶单纯剖分

通过引进凸多胞形对其外部一点的阴面、阳面与平射面等概念,借助两个屏蔽引理证明Rn中任何n维凸多胞形都可以剖分为内部互不相交、以原凸多胞形的顶点集的子集为顶点集的有限个n维单纯形之并,克服了相关文献中剖分的不足,为单纯形算法提供了一种比较理想的剖分工具.     

一种无恢复过程的SQP-滤子法

本文研究非线性不等式约束优化问题,构造一个新的SQP-滤子法.该方法将滤子技术有机融合到简金宝提出的可行SQP方法中,利用转轴运算的思想,产生一个近似积极约束集,当QP子问题不相容时,利用广义投影技术获得可行搜索方向.该算法既能避免罚函数的选择,又能避免常规滤子算法中的恢复算法,一定程度上简化了计算.最后,在合理的条件下,证明了算法的全局收敛性.