大范围求解非线性方程组的指数同伦法

为了解决关于奇异的非线性方程组求根问题,提出了一种由同伦算法推出大范围收敛的连续型方法-指数同伦法,构造了一类指数同伦方程,克服了Jacobi矩阵的奇异,分析了指数同伦方     

弱拟法锥条件下非凸优化问题的同伦算法

本文给出弱拟法锥条件的定义,并针对非线性组合同伦方程,得到在弱拟法锥条件下求解约束非凸优化问题的同伦内点算法.证明了该算法对于可行域的某个子集中几乎所有的点,同伦路径存在,并且同伦路径收敛于问题的K-K-T点,通过数值例子验证了该算法是有效的.     

用Eaves－Saigal不动点算法求解不可微优化

本文通过修改向量标号改造Ｅａｖｅｓ－Ｓａｉｇａｌ单纯同伦算法为上半连续集值映射零点的同伦算法，并给出了这一算法收敛的条件．最后，应用该方法到不可做优化问题的求解，得到一些收敛性结果．数值结果表明计算效果良好．     

关于二次规划问题分段线性同伦算法的改进

本文利用Ｃｈｏｌｅｓｋｙ分解，Ｇａｕｓｓ消去等技术和定义适当的同伦映射，将关于二次规划问题的分段线性同伦算法加以改进，改进后的算法，对于严格凸二次规划来说，计算效率与Ｇｏｌｄｆａｒｂ－Ｉｄｎａｎｉ的对偶法相当。     

同伦方法求解无界域上非凸规划问题的收敛性定理

利用同伦方法求解非凸规划时,一般只能得到问题的K-K-T点.本文得到无界域上同伦方法求解非凸规划的几个收敛性定理,证明在一定条件下,通过构造合适的同伦方程,同伦算法收敛到问题的局部最优解.     

用Eaves—Saigal不动点算法求解不可微优化

本文通过修改向量标号改造Ｅａｖｅｓ－Ｓａｉｇａｌ单纯用伦算法为上半连续集值映射零点的同伦算法，并给出了这一算法收敛的条件，最后，应用该方法到不可微优化问题的求解，得到一些收敛性结果，数值结果表明计算效果良好。     

线性规划基于预-校正的组合同伦多项式算法

本文针对线性规划问题提出了一个新的内点方法——组合同伦内点方法，并采用预估校正算法来跟踪组合同伦路径从而得到问题的ε-解.最后讨论了该算法的收敛性，并证明了该算法为多项式算法。     

基于Bregman距离函数的可靠性分析

针对概率结构可靠性问题,引入Bregman距离函数,建立了基于同伦算法(HM)的可靠性分析模型.利用极限状态方程,将可靠性指标求解转化为一个非线性约束优化问题.结合同伦思想的基本理论和Bregman距离函数,构造同伦方程组,采用路径跟踪算法对该方程组进行求解.通过相应的数值算例探讨了不同函数形式以及不同程度非线性问题的可靠性计算,并与其他方法计算结果进行了对比,分析结果表明该模型能够有效求解概率结构可靠性问题.     

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

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

空间-时间分数阶变系数对流扩散方程微分阶数的数值反演

考虑终值数据条件下一维空间-时间分数阶变系数对流扩散方程中同时确定空间微分阶数与时间微分阶数的反问题.基于对空间-时间分数阶导数的离散,给出求解正问题的一个隐式差分格式,通过对系数矩阵谱半径的估计,证明差分格式的无条件稳定性和收敛性.联合最佳摄动量算法和同伦方法引入同伦正则化算法,应用一种单调下降的Sigmoid型传输函数作为同伦参数,对所提微分阶数反问题进行精确数据与扰动数据情形下的数值反演.结果表明同伦正则化算法对于空间-时问分数阶反常扩散的参数反演问题是有效的.     

Probability-one homotopies in computational science

Probability-one homotopy algorithms are a class of methods for solving nonlinear systems of equations that, under mild assumptions, are globally convergent for a wide range of problems in science and engineering. Convergence theory, robust numerical algorithms, and production quality mathematical software exist for general nonlinear systems of equations, and special cases such as Brouwer fixed point problems, polynomial systems, and nonlinear constrained optimization. Using a sample of challenging scientific problems as motivation, some pertinent homotopy theory and algorithms are presented. The problems considered are analog circuit simulation (for nonlinear systems), reconfigurable space trusses (for polynomial systems), and fuel-optimal orbital rendezvous (for nonlinear constrained optimization). The mathematical software packages HOMPACK90 and POLSYS_PLP are also briefly described.     

Solution of Delay Differential Equation by Means of Homotopy Analysis Method

The algorithm of approximate analytical solution for delay differential equations (DDE) is obtained via homotopy analysis method (HAM) and modified homotopy analysis method (MHAM). Various examples of linear, nonlinear and system of initial value problems of DDE are solved and the results obtained show that these algorithms are accurate and efficient for the DDE. The convergence of this algorithm is also proved.     

Some computational methods for systems of nonlinear equations and systems of polynomial equations

This paper gives a brief survey and assessment of computational methods for finding solutions to systems of nonlinear equations and systems of polynomial equations. Starting from methods which converge locally and which find one solution, we progress to methods which are globally convergent and find an a priori determinable number of solutions. We will concentrate on simplicial algorithms and homotopy methods. Enhancements of published methods are included and further developments are discussed.     

An adaptation of homotopy analysis method for reliable treatment of strongly nonlinear problems: construction of homotopy polynomials

In this paper, a new adaption of homotopy analysis method is presented to handle nonlinear problems. The proposed approach is capable of reducing the size of calculations and easily overcome the difficulty arising in calculating complicated integrals. Furthermore, the homotopy polynomials that decompose the nonlinear term of the problem as a series of polynomials are introduced. Then, an algorithm of calculating such polynomials, which makes the solution procedure more straightforward and more effective, is constructed. Numerical examples are examined to highlight the significant features of the developed techniques. The algorithms described in this paper are expected to be further employed to solve nonlinear problems in mathematical physics. Copyright © 2014 John Wiley & Sons, Ltd.     

Randomized and quantum algorithms yield a speed-up for initial-value problems

Quantum algorithms and complexity have recently been studied not only for discrete, but also for some numerical problems. Most attention has been paid so far to the integration and approximation problems, for which a speed-up is shown in many important cases by quantum computers with respect to deterministic and randomized algorithms on a classical computer. In this paper, we deal with the randomized and quantum complexity of initial-value problems. For this nonlinear problem, we show that both randomized and quantum algorithms yield a speed-up over deterministic algorithms. Upper bounds on the complexity in the randomized and quantum settings are shown by constructing algorithms with a suitable cost, where the construction is based on integral information. Lower bounds result from the respective bounds for the integration problem.     

On Legendre polynomial approximation with the VIM or HAM for numerical treatment of nonlinear fractional differential equations

The variational iteration method and the homotopy analysis method, as alternative methods, have been widely used to handle linear and nonlinear models. The main property of the methods is their flexibility and ability to solve nonlinear equations accurately and conveniently. This paper deals with the numerical solutions of nonlinear fractional differential equations, where the fractional derivatives are considered in Caputo sense. The main aim is to introduce efficient algorithms of variational iteration and homotopy analysis methods that can be simply used to deal with nonlinear fractional differential equations. In these algorithms, Legendre polynomials are effectively implemented to achieve better approximation for the nonhomogeneous and nonlinear terms that leads to facilitate the computational work. The proposed algorithms are capable of reducing the size of calculations, improving the accuracy and easily overcome the difficulty arising in calculating complicated integrals. Numerical examples are examined to show the efficiency of the algorithms.     

结构动力学逆特征值问题的同伦解法

将结构动力学反问题视为拟乘法逆特征值问题,利用求解非线性方程组的同伦方法来解决结构动力学逆特征值问题,这种方法由于沿同伦路径求解,对初值的选取没有本质的要求,算例说明了这种方法是可行的．     

Probability-one homotopy maps for mixed complementarity problems

Probability-one homotopy algorithms have strong convergence characteristics under mild assumptions. Such algorithms for mixed complementarity problems (MCPs) have potentially wide impact because MCPs are pervasive in science and engineering. A probability-one homotopy algorithm for MCPs was developed earlier by Billups and Watson based on the default homotopy mapping. This algorithm had guaranteed global convergence under some mild conditions, and was able to solve most of the MCPs from the MCPLIB test library. This paper extends that work by presenting some other homotopy mappings, enabling the solution of all the remaining problems from MCPLIB. The homotopy maps employed are the Newton homotopy and homotopy parameter embeddings.     

Approximate nonlinear programming algorithms for solving stochastic programs with recourse

This paper summarizes the main results on approximate nonlinear programming algorithms investigated by the author. These algorithms are obtained by combining approximation and nonlinear programming algorithms. They are designed for programs in which the evaluation of the objective functions is very difficult so that only their approximate values can be obtained. Therefore, these algorithms are particularly suitable for stochastic programming problems with recourse.Project supported by the National Natural Science Foundation of China.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25