一个Newton-PCG型算法和它的效率分析

大量的数值实验表明Newton-PCG型算法很有效，但缺乏理论上的保证，最近在文[7]中，从理论上证明了该类算法比Newton法有效，本文取消了文[7]中的过程的假设条件，在标准假设下得到了一个更有效的算法。     

Newton-PCG算法的效率的理论分析

为了从理论上研究在标准条件下光滑无约束问题的不精确Newton类型算法的效率,对一个具体的Newton-PCG算法进行了讨论. 为了比较该算法与Newton法的效率, 引入了两者的近似效率之比值.在很弱的条件下证明了该比值大于1, 这表明Newton-PCG算法比Newton法的效率高.同时, 当无约束问题的维数n®∞时, 该比值至少以lnn/ln2 的速度增加, 因而从理论上证明了Newton-PCG算法对大中型问题更有效. 数值实验也支持了上述理论结果.     

初等微分几何的机械化证明

本文系文献[1]关于初等几何机械化证明的继续,文中指出,应用同样的原理可给出一个算法,足以判定初等微分几何中一个适当的叙述是否是一真实的定理,方法是依据Riquier-Ritt-Thomas的理论^[2,3],这些理论本身就是算法性的。     

微分多项式系统的约化算法理论

本文中，作者推广了纯代数形式的特征列集理论（吴方法）为微分形式的相应理论，即建立了在机器证明了诸多微分问题中非常重要的微分多项式组的约化算法理论。引入了一些新的概念和观点使函数微分（导数）具有直观的代数几何表示。给出了Coherent条件下的特征列集的算法。给出的算法易于在计算机上实现并适合应用于广泛的微分问题，如微分方程对称计算，各种微分关系的自动推理等问题。     

利用改进的同伦算法求解特征值问题

矩阵特征值问题是机器学习、数据处理以及工程分析和计算中经常需要解决的问题之一.同伦算法是求解矩阵特征值的经典方法;自动微分可以有效、快速地计算出大规模问题相关函数的导数项,并且可以达到机器精度.充分利用自动微分的优点,设计自动微分技术与同伦算法相结合的方法求解矩阵特征值问题.数值实验验证了该算法的有效性.     

高阶中立型方程渐近稳定性的代数判定

微分差分方程渐近稳定性的代数判据在应用时比较方便。最近,文[1]给出了滞后型方程渐近稳定的代数判据,文[2]给出了一阶中立型方程渐近稳定的代数判据。本文旨在推广文[2]的结果,给出高阶中立型方程渐近稳定的代数判据。 考虑中立型微分差分方程     

有限区间上积分-微分算子的逆结点问题

研究Dirichlet边界条件下的积分-微分算子逆结点问题.证明了积分-微分算子稠定的结点子集能够唯一确定[0,π]上的势函数q(x)和区域Do上的积分扰动核M(x-t)且给出了这个逆结点问题的解的重构算法.     

多复变数微分从属的最优控制

讨论了多复变函数中的微分从属的最优控制的问题，取得了一些结果，得到了一些应用．它是单复变函数论中的相应结果[1，2]的推广．     

不等式约束二次规划的一新算法

文献[1]提出了一般等式约束非线性规划问题一种求解途径．文献[2]应用这一途径给出了等式约束二次规划问题的一种算法，本文在文献[1]和[2]的基础上对不等式约束二次规划问题提出了一种新算法．     

Ungar微分变换在弹性动力学中的一个应用

近些年来,在求解弹性波方面的一些问题时,许多著者都应用了Cagniard—de Hoop方法[1][2].但是,在使用该法时,定要进行一些比较复杂的改变积分路径的工作.A.Ungar所提出的一种微分变换[3~6]可以避免这种困难.本文应用Ungar微分变换来求解Lamb问题[1][2]的一情形.     

A theoretical analysis on efficiency of some Newton-PCG methods

In this paper, we study the efficiency issue of inexact Newton-type methods for smooth unconstrained optimization problems under standard assumptions from theoretical point of view by discussing a concrete Newton-PCG algorithm. In order to compare the algorithm with Newton's method, a ratio between the measures of their approximate efficiencies is investigated. Under mild conditions, it is shown that first, this ratio is larger than 1, which implies that the Newton-PCG algorithm is more efficient than Newton's method, and second, this ratio increases when the dimension n of the problem increases and tends to infinity at least at a rate In n/In 2 when n→∞, which implies that in theory the Newton-PCG algorithm is much more efficient for middle- and large-scale problems. These theoretical results are also supported by our preliminary numerical experiments.     

An Inexact Newton Method Derived from Efficiency Analysis

We consider solving an unconstrained optimization problem by Newton-PCG like methods in which the preconditioned conjugate gradient method is applied to solve the Newton equations. The main question to be investigated is how efficient Newton-PCG like methods can be from theoretical point of view. An algorithmic model with several parameters is established. Furthermore, a lower bound of the efficiency measure of the algorithmic model is derived as a function of the parameters. By maximizing this lower bound function, the parameters are specified and therefore an implementable algorithm is obtained. The efficiency of the implementable algorithm is compared with Newtons method by theoretical analysis and numerical experiments. The results show that this algorithm is competitive.Mathematics Subject Classification: 90C30, 65K05.This work was supported by the National Science Foundation of China Grant No. 10371131, and Hong Kong Competitive Earmarked Research Grant CityU 1066/00P from Hong Kong University Grant Council     

On a one-dimensional optimization problem derived from the efficiency analysis of Newton-PCG-like algorithms

The Newton-PCG (preconditioned conjugate gradient) like algorithms are usually very efficient. However, their efficiency is mainly supported by the numerical experiments. Recently, a new kind of Newton-PCG-like algorithms is derived in (J. Optim. Theory Appl. 105 (2000) 97; Superiority analysis on truncated Newton method with preconditioned conjugate gradient technique for optimization, in preparation) by the efficiency analysis. It is proved from the theoretical point of view that their efficiency is superior to that of Newton's method for the special cases where Newton's method converges with precise Q-order 2 and α(⩾2), respectively. In the process of extending such kind of algorithms to the more general case where Newton's method has no fixed convergence order, the first is to get the solutions to the one-dimensional optimization problems with many different parameter values of α. If these problems were solved by numerical method one by one, the computation cost would reduce the efficiency of the Newton-PCG algorithm, and therefore is unacceptable. In this paper, we overcome the difficulty by deriving an analytic expression of the solution to the one-dimensional optimization problem with respect to the parameter α.     

在Newton-PCG方法中的一个一维整数最优化问题

本文研究在Newton-PCG方法中出现的一个一维整数最优化问题．通过引入和研究几个连续变量的辅助问题，我们建立了一个简单而有效的算法．这一算法的主要计算量是求解两次非线形方程zlnz—c=0，因此是非常小的．另外，我们还对这一问题的最优值进行了估计．     

Truncated Newton method for sparse unconstrained optimization using automatic differentiation

When solving large complex optimization problems, the user is faced with three major problems. These are (i) the cost in human time in obtaining accurate expressions for the derivatives involved; (ii) the need to store second derivative information; and (iii), of lessening importance, the time taken to solve the problem on the computer. For many problems, a significant part of the latter can be attributed to solving Newton-like equations. In the algorithm described, the equations are solved using a conjugate direction method that only needs the Hessian at the current point when it is multiplied by a trial vector. In this paper, we present a method that finds this product using automatic differentiation while only requiring vector storage. The method takes advantage of any sparsity in the Hessian matrix and computes exact derivatives. It avoids the complexity of symbolic differentiation, the inaccuracy of numerical differentiation, the labor of finding analytic derivatives, and the need for matrix store. When far from a minimum, an accurate solution to the Newton equations is not justified, so an approximate solution is obtained by using a version of Dembo and Steihaug's truncated Newton algorithm (Ref. 1).This paper was presented at the SIAM National Meeting, Boston, Massachusetts, 1986.     

一个无正则条件下一般约束最优化问题的信赖域算法的收敛性

本文我们对[1]的算法给出一个修正并在无正则条件下对这一算法给出了收敛性分析，与[1]不同，我们不需要(SBSQ)约束条件。因此本文的结果是[1]的结果的推广和加强。     

Accelerating the convergence in the single-source and multi-source Weber problems

The modified Weiszfeld method [Y. Vardi, C.H. Zhang, A modified Weiszfeld algorithm for the Fermat-Weber location problem, Mathematical Programming 90 (2001) 559-566] is perhaps the most widely-used algorithm for the single-source Weber problem (SWP). In this paper, in order to accelerate the efficiency for solving SWP, a new numerical method, called Weiszfeld-Newton method, is developed by combining the modified Weiszfeld method with the well-known Newton method. Global convergence of the new Weiszfeld-Newton method is proved under mild assumptions. For the multi-source Weber problem (MWP), a new location-allocation heuristic, Cooper-Weiszfeld-Newton method, is presented in the spirit of Cooper algorithm [L. Cooper, Heuristic methods for location-allocation problems, SIAM Review 6 (1964) 37-53], using the new Weiszfeld-Newton method in the location phase to locate facilities and adopting the nearest center reclassification algorithm (NCRA) in the allocation phase to allocate the customers. Preliminary numerical results are reported to verify the evident effectiveness of Weiszfeld-Newton method for SWP and Cooper-Weiszfeld-Newton method for MWP.     

Computational experience with an interior point algorithm on the satisfiability problem

We apply the zero-one integer programming algorithm described in Karmarkar [12] and Karmarkar, Resende and Ramakrishnan [13] to solve randomly generated instances of the satisfiability problem (SAT). The interior point algorithm is briefly reviewed and shown to be easily adapted to solve large instances of SAT. Hundreds of instances of SAT (having from 100 to 1000 variables and 100 to 32,000 clauses) are randomly generated and solved. For comparison, we attempt to solve the problems via linear programming relaxation with MINOS.     

A feasible SQP method for nonlinear programming

In this paper, a new SQP algorithm is presented to solve the general nonlinear programs with mixed equality and inequality constraints. Quoted from P. Spellucci (see [9]), this method maybe be named sequential equality constrained quadratic programming (SECQP) algorithm. Per single iteration, based on an active set strategy ( see [9]), this SECQP algorithm requires only to solve equality constrained quadratic programming subproblems or system of linear equations. The theoretical analysis shows that global and superlinear convergence can be induced under some suitable conditions.