大规模图上深度优化编码算法

§1 引言 当用直接方法解一个具有稀疏矩阵的大型线性代数方程组时,如果它的系数矩阵所对应的是一类具有大量节点的无向连通图,图上节点的编码是提高效率的一个关键。对此,国内外很多人提出了一些有实用价值的算法(见[3]、[4]、[5]、[6]等),其中很大一类是出于带宽(bandwidth)极小化的思想。众所周知,减少存贮和工作量的关键在于使矩阵的轮廓(envelope)极小化。在许多情况下,减小带宽可以导致轮廓的减小,但     

解一般线性规划逆问题的一个O（n^3L）算法

本文讨论了一般线性规划逆问题在各种情况下的求解，并基于解凸二次规划的原对偶内点算法，给出了一个O（n3L）算法和一个实用算法．     

Karmarkar算法及其变形

研究如下形式的LP minc~Tx, s.t.Ax=0,(1) e~Tx=1,x≥0。其中A为m×n的行满秩矩阵,e=(1,…,1)~T∈R~n。已知x~0=(x_1~0,…,x_n~0)~T为(1)的一个严格可行内点。令Ω={x|x∈R~n,Ax=0},S={x|x∈R~n,e~Tx=1,x≥0},D=diag{x_1~0,…,x_n~0}。我们用统一的观点和方法导出K法和MK法。对(1)进行投影变换T: (?)x∈R~n,有 T(x)=y=(D~(-1)x/(e~TD~(-1)x))。 (2)     

Karmarkar算法的一个变形

本文给出了一个解线性规划问题的Karmarkar算法的变形。根据一个不涉及势函数的优化原则,导出一个新的搜索方向,然后将其正交投影得出本文所给算法。该算法的优点是在整个迭代过程中无须对目标函数值加以限制,无须增加对偶变量和对偶约束,也不必采用滑动目标函数技术,且在最优解邻域内的收敛速度与Karmarkar算法相同。     

半定规划的逆问题

本文提出了半定规划的逆问题,利用半定规划的最优性条件,分别给出了其在ｌ∞,ｌ１,ｌ２ 模意义下的数学模型,它们仍为半定规划问题．     

凸二次规划问题逆问题的模型与解法

本文分别考虑带非负约束和不带大量负约束凸二次规划问题逆问题。首先得到各个逆问题的数学模型,然后对不同的模型给出不同的求解方法。     

一般线性规划问题的限制逆问题

本文提出了一般线性规划问题的限制逆问题,利用线性规划的最优性条件,分别给出了其在l∞,l1,l2模意义下的数学模型,它们分别为线性规划和二次规划问题。     

Karmarkar算法的一点注记

Karmarkar算法是解如下形式的LP: min c~Tx s.t.Ax=0 (1) e~Tx=1,x≥0。其中A∈Z~(m×n)为行满秩矩阵,c∈Z~n,e=(1,…,1)∈Z~n,x∈R~n。设(1)有内点可行解且其最优值为零。文[1]中给出解(1)的基本算法和改进算法,并通过势函数给出了证明。其证明过程是复杂的,且决定迭代步长的参数α=0.25。文[2]论证了α取值可增为1/3。文     

内点算法和动力系统

本文以动力系统的理论统一处理各种解线性规划的内点算法.在一般情况下讨论了此类系统的构成和基本的附加条件.对轨线的几何特征,尤其是它们在靠近边界处的动态作了进一步研究.     

第一类弗莱特霍姆积分方程的线性规划解法

1 引 言在地球物理勘探、最佳控制系统中常要解一个具有正核的第一类弗莱特霍姆积分方