线性方程组l_1范数问题的松弛投影算法及其应用

考虑线性方程组l_1范数问题的求解,在分别将其转化为一个分裂可行问题和凸可行问题的基础上,设计了几种松弛投影算法,然后将所设计的求解方法用于信号处理问题的求解上.     

黄金分割法在求解线性方程组中的应用

把线性方程组转化成为其等价的变分问题 ,借助黄金分割法的思想对该变分问题进行求解 ,给出的算例结果表明 ,本文方法不仅对良态线性方程组的求解有效 ,而且对于病态线性方程组的求解同样是有效实用的 .     

关于位移线性方程组的加速超松弛迭代算法

本文研究关于系数矩阵为位移埃尔米特和位移反埃尔米特矩阵的复线性方程组的简便而有效的分裂迭代算法及其收敛性质.由于复系数线性方程组的系数矩阵由实部和虚部组成,运用松弛加速技术,我们得到了求解位移线性方程组的加速超松弛迭代算法,并分析了这类算法的收敛性质.数值算例表明,这类加速超松弛迭代算法是可行且有效的.     

线性互补问题的异步并行多分裂松弛迭代算法

将求解线性方程组的异步并行多分裂松弛迭代算法推广到线性互补问题.当问题的系数矩阵为H-矩阵类时,证明了算法的全局收敛性.     

矫正低秩相关系数矩阵的松弛序列凸近似方法

本文主要讨论带有秩约束以及简单上下界约束的相关系数矩阵矫正问题的求解方法.该问题可以写成一个含有DC(两个凸函数之差)约束的优化问题,于是考虑利用求解DC优化问题的序列凸近似(SCA)方法求解.然而对本文讨论的问题,经典的序列凸近似方法收敛所需的约束规范不成立,于是,本文提出一种松弛的序列凸近似方法.本文证明当松弛参数趋于零时,松弛的DC问题的稳定点趋于原问题的稳定点.另一方面,可以利用序列凸近似方法求解松弛的DC问题.可以证明,序列凸近似方法生成的一系列凸子问题的解的聚点就是该松弛DC问题的稳定点.数值实验验证了该方法的有效性.     

求解不等式约束优化问题无严格互补松弛条件的QP-Free新算法

本文针对不等式约束优化问题,结合Facchinei-Fischer-Kanzow精确有效集识别技术,给出—个新的线性方程组与辅助方向相结合的可行下降算法.算法每步迭代只需求解一个降维的线性方程组或计算一次辅助方向,且获取辅助方向的投影矩阵只涉及近似有效约束集中的元素,问题规模大为减少,且当迭代次数充分大时,只需求解一个降维的线性方程组.无需严格互补松弛条件,算法全局且一步超线性收敛.     

一种求解分布控制问题的含参预处理最小残量法(英文)

近年来,提出了一些求解约束优化分布控制问题的方法,其中最常用的方法是先离散偏微分方程,然后求解离散得到的线性方程组.文献中提出了一些Krylov子空间预处理方法用来求解该线性方程组.通过分析张晓莹等提出的块对角预处理矩阵(Zhang X Y,Yan H Y.Huang Y M.On preconditionedMINRES method for solving the distributed control problems.Commun Appl Math Comput,2014,28:128-132.),构造了一个含参数的块对角预处理线性方程组,并运用含参数预处理最小残量方法求解该线性方程组.预处理矩阵的谱分析表明当参数大于1时,含参预处理线性方程组的谱分布更加集中.数值实验结果验证了含参数的预处理最小残量方法对于求解分布式控制问题是有效的.     

求解弱线性双层规划问题的一种全局优化方法

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.     

求解Hilbert矩阵线性方程组的SOR迭代预处理方法

选择了求解Hilbert矩阵线性方程组的三种数值解方法,提出了SOR迭代中的松弛因子的预处理方法,比较了高斯-赛德尔迭代和SOR迭代数值解的迭代收敛次数,并给出了SOR迭代收敛最快时的松弛因子取值.最后通过SOR迭代解分量及误差范围,说明了提出的SOR迭代预处理方法是有效的.     

非线性极大极小问题一个新的QP-free算法

本文研究非线性无约束极大极小优化问题. QP-free算法是求解光滑约束优化问题的有效方法之一,但用于求解极大极小优化问题的成果甚少.基于原问题的稳定点条件,既不需含参数的指数型光滑化函数,也不要等价光滑化,提出了求解非线性极大极小问题一个新的QP-free算法.新算法在每一次迭代中,通过求解两个相同系数矩阵的线性方程组获得搜索方向.在合适的假设条件下,该算法具有全局收敛性.最后,初步的数值试验验证了算法的有效性.     

广义鞍点问题的改进的类SOR算法

针对广义鞍点问题,本文提出了一个改进的类逐次超松弛迭代算法,在较弱的条件下,分析了算法的收敛性及线性收敛率.新算法的每步计算量与已有的算法类似,都是需要（近似）求解线性方程组,但新算法有更好的灵活度通过合适地选取参数矩阵,每一步子问题可以容易地求解,甚至可以有闭式解（closed-form solution）.数值实验结果显示了新算法的有效性.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

Numerical solution of the finite horizon stochastic linear quadratic control problem

The treatment of the stochastic linear quadratic optimal control problem with finite time horizon requires the solution of stochastic differential Riccati equations. We propose efficient numerical methods, which exploit the particular structure and can be applied for large‐scale systems. They are based on numerical methods for ordinary differential equations such as Rosenbrock methods, backward differentiation formulas, and splitting methods. The performance of our approach is tested in numerical experiments.     

Increasing efficiency of inverse iteration

Inverse iteration is simple but not very efficient method for computing few eigenvalues with minimal absolute values and corresponding eigenvectors of a symmetric matrix. The idea is to increase its efficiency by technique similar to multigrid methods used for solving linear systems. This approach is not new, but until now multigrid was mostly used for solving linear system which appear in Rayleigh quotient iteration, inverse iteration and related iterative methods. Instead of choosing appropriate coordinates (grids), our algorithm performs inverse iteration on a sequence of subspaces with decreasing dimensions (multispace). Block Lanczos method is used for the selection of a smaller subspace. This will produce a banded matrix, which makes inverse iteration even faster in the smaller dimensions.      

Efficient decomposition and linearization methods for the stochastic transportation problem

The stochastic transportation problem can be formulated as a convex transportation problem with nonlinear objective function and linear constraints. We compare several different methods based on decomposition techniques and linearization techniques for this problem, trying to find the most efficient method or combination of methods. We discuss and test a separable programming approach, the Frank-Wolfe method with and without modifications, the new technique of mean value cross decomposition and the more well known Lagrangean relaxation with subgradient optimization, as well as combinations of these approaches. Computational tests are presented, indicating that some new combination methods are quite efficient for large scale problems.     

A coupled finite element-differential quadrature element method and its accuracy for moving load problem

In this paper a mixed method, which combines the finite element method and the differential quadrature element method (DQEM), is presented for solving the time dependent problems. In this study, the finite element method is first used to discretize the spatial domain. The DQEM is then employed as a step-by-step DQM in time domain to solve the resulting initial value problem. The resulting algebraic equations can be solved by either direct or iterative methods. Two general formulations using the DQM are also presented for solving a system of linear second-order ordinary differential equations in time. The application of the formulation is then shown by solving a sample moving load problem. Numerical results show that the present mixed method is very efficient and reliable.     

Determination of the source parameter in a heat equation with a non-local boundary condition

In this article we consider the inverse problem of identifying a time dependent unknown coefficient in a parabolic problem subject to initial and non-local boundary conditions along with an overspecified condition defined at a specific point in the spatial domain. Due to the non-local boundary condition, the system of linear equations resulting from the backward Euler approximation have a coefficient matrix that is a quasi-tridiagonal matrix. We consider an efficient method for solving the linear system and the predictor–corrector method for calculating the solution and updating the estimate of the unknown coefficient. Two model problems are solved to demonstrate the performance of the methods.     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

EXPERIMENTAL STUDY OF THE ASYNCHRONOUS MULTISPLITTING RELAXATION METHODS FOR THE LINEAR COMPLEMENTARITY PROBLEMS

We study the numerical behaviours of the relaxed asynchronous multisplitting methods for the linear complementarity problems by solving some typical problems from practical applications on a real multiprocessor system. Numerical results show that the parallel multisplitting relaxation methods always perform much better than the corresponding sequential alternatives, and that the asynchronous multisplitting relaxation methods often outperform their corresponding synchronous counterparts. Moreover, the two-sweep relaxed multisplitting methods have better convergence properties than their corresponding one-sweep relaxed ones in the sense that they have larger convergence domains and faster convergence speeds. Hence, the asynchronous multisplitting unsymmetric relaxation iterations should be the methods of choice for solving the large sparse linear complementarity problems in the parallel computing environments.     

Ninth-order,explicit, two-step methods for second-order inhomogeneous linear IVPs

In the present paper, the second-order linear inhomogeneous initial value problems (LI-IVP) with constant coefficients is of our interest. Two-step hybrid methods (ie, of Numerov-type) are considered for addressing this problem. Thus, a special set of order conditions is given and solved for derivation a low cost new method. Actually, we manage to save two stages per step. This is crucial as shown in various numerical tests where our new proposal outperforms standard methods in the relevant literature.