二维抛物型方程参数反演模型的拟牛顿法

讨论了二维变系数抛物型方程的参数识别反问题,将其归为最优化问题,指定待定参数的函数类形式,用拟牛顿法来演化待求参数的最优估计值,并将该方法运用于线性扩散方程和具有分段函数系数的二维抛物型方程的参数识别反问题的数值模拟中,数值结果表明拟牛顿法（BFGS）解决此类问题是有效的和可行的。     

On the convergence of Newton-type methods using recurrent functions

We introduce the new idea of recurrent functions to provide a new semilocal convergence analysis for Newton-type methods. It turns out that our sufficient convergence conditions are weaker, and the error bounds are tighter than in earlier studies in many interesting cases [X. Chen, On the convergence of Broyden-like methods for nonlinear equations with nondifferentiable terms, Ann. Inst. Statist. Math. 42 (1990), pp. 387–401; X. Chen and T. Yamamoto, Convergence domains of certain iterative methods for solving nonlinear equations, Numer. Funct. Anal. Optim. 10 (1989), pp. 37–48; Y. Chen and D. Cai, Inexact overlapped block Broyden methods for solving nonlinear equations, Appl. Math. Comput. 136 (2003), pp. 215–228; J.E. Dennis, Toward a unified convergence theory for Newton-like methods, in Nonlinear Functional Analysis and Applications, L.B. Rall, ed., Academic Press, New York, 1971, pp. 425–472; P. Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms, Springer Series in Computational Mathematics, Vol. 35, Springer-Verlag, Berlin, 2004; P. Deuflhard and G. Heindl, Affine invariant convergence theorems for Newton's method and extensions to related methods, SIAM J. Numer. Anal. 16 (1979), pp. 1–10; Z. Huang, A note of Kantorovich theorem for Newton iteration, J. Comput. Appl. Math. 47 (1993), pp. 211–217; L.V. Kantorovich and G.P. Akilov, Functional Analysis, Pergamon Press, Oxford, 1982; D. Li and M. Fukushima, Globally Convergent Broyden-like Methods for Semismooth Equations and Applications to VIP, NCP and MCP, Optimization and Numerical Algebra (Nanjing, 1999), Ann. Oper. Res. 103 (2001), pp. 71–97; C. Ma, A smoothing Broyden-like method for the mixed complementarity problems, Math. Comput. Modelling 41 (2005), pp. 523–538; G.J. Miel, Unified error analysis for Newton-type methods, Numer. Math. 33 (1979), pp. 391–396; G.J. Miel, Majorizing sequences and error bounds for iterative methods, Math. Comp. 34 (1980), pp. 185–202; I. Moret, A note on Newton type iterative methods, Computing 33 (1984), pp. 65–73; F.A. Potra, Sharp error bounds for a class of Newton-like methods, Libertas Math. 5 (1985), pp. 71–84; W.C. Rheinboldt, A unified convergence theory for a class of iterative processes, SIAM J. Numer. Anal. 5 (1968), pp. 42–63; T. Yamamoto, A convergence theorem for Newton-like methods in Banach spaces, Numer. Math. 51 (1987), pp. 545–557; P.P. Zabrejko and D.F. Nguen, The majorant method in the theory of Newton–Kantorovich approximations and the Pták error estimates, Numer. Funct. Anal. Optim. 9 (1987), pp. 671–684; A.I. Zin[cbreve]enko, Some approximate methods of solving equations with non-differentiable operators, (Ukrainian), Dopovidi Akad. Nauk Ukraïn. RSR (1963), pp. 156–161]. Applications and numerical examples, involving a nonlinear integral equation of Chandrasekhar-type, and a differential equation are also provided in this study.     

拟Newton法在高阶矩阵中的应用——求解最大特征值及特征向量

将求解高阶矩阵的最大特征值及其对应的特征向量问题转化为高阶非线性方程组的求解问题。在此基础上,提出了求解矩阵最大特征值及其对应特征向量的拟Newton法,给出求解矩阵最大特征值及其单位化向量重新整理后的Broyden方法公式、BFS方法公式、DFP方法公式及其对应的Broyden算法,BFS算法,DFP算法。以层次分析法中高阶判断矩阵为例验证了该方法的可行性,说明了该方法相对收敛速度快的优势。     

Fourth-order convergence theorem by using majorizing functions for super-Halley method in Banach spaces

In this paper, we study the semilocal convergence of a multipoint fourth-order super-Halley method for solving nonlinear equations in Banach spaces. We establish the Newton–Kantorovich-type convergence theorem for the method by using majorizing functions. We also get the error estimate. In comparison with the results obtained in Wang et al. [X.H. Wang, C.Q. Gu, and J.S. Kou, Semilocal convergence of a multipoint fourth-order super-Halley method in Banach spaces, Numer. Algorithms 56 (2011), pp. 497–516], we can provide a larger convergence radius. Finally, we report some numerical applications to demonstrate our approach.     

Efficiently preconditioned inexact Newton methods for large symmetric eigenvalue problems

In this paper, we propose an efficiently preconditioned Newton method for the computation of the leftmost eigenpairs of large and sparse symmetric positive definite matrices. A sequence of preconditioners based on the BFGS update formula is proposed, for the preconditioned conjugate gradient solution of the linearized Newton system to solve Au=q(u) u, q(u) being the Rayleigh quotient. We give theoretical evidence that the sequence of preconditioned Jacobians remains close to the identity matrix if the initial preconditioned Jacobian is so. Numerical results onto matrices arising from various realistic problems with size up to one million unknowns account for the efficiency of the proposed algorithm which reveals competitive with the Jacobi–Davidson method on all the test problems.     

求解非线性方程组的BFGS差分进化算法

针对差分进化算法进化后期收敛缓慢和稳定性不强的缺陷,将BFGS算法插入差分进化算法当中,提出了一种BFGS差分进化算法,用来求解非线性方程组。通过5个非线性方程组和一个工程实例的实验,说明：算法收敛精度较高、收敛速度较快、鲁棒性强、收敛成功率高,是一种较好的解决非线性方程组的方法。     

Interior-point methods for symmetric optimization based on a class of non-coercive kernel functions

In this paper, we generalize polynomial-time primal–dual interior-point methods for symmetric optimization based on a class of kernel functions, which is not coercive. The corresponding barrier functions have a finite value at the boundary of the feasible region. They are not exponentially convex and also not strongly convex like many usual barrier functions. Moreover, we analyse the accuracy of the algorithm for this class of functions and we obtain an upper bound for the accuracy which depends on a parameter of the class.     

Numerical evaluation of Hilbert transforms for oscillatory functions: A convergence accelerator approach

The numerical evaluation of Hilbert transforms on the real line for functions that exhibit oscillatory behavior is investigated. A fairly robust numerical procedure is developed that is based on the use of convergence accelerator techniques. Several different types of oscillatory behavior are examined that can be successfully treated by the approach given. A few examples of functions whose oscillations are too extreme to deal with are also discussed.     

Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity

Many recent applications in machine learning and data fitting call for the algorithmic solution of structured smooth convex optimization problems. Although the gradient descent method is a natural choice for this task, it requires exact gradient computations and hence can be inefficient when the problem size is large or the gradient is difficult to evaluate. Therefore, there has been much interest in inexact gradient methods (IGMs), in which an efficiently computable approximate gradient is used to perform the update in each iteration. Currently, non-asymptotic linear convergence results for IGMs are typically established under the assumption that the objective function is strongly convex, which is not satisfied in many applications of interest; while linear convergence results that do not require the strong convexity assumption are usually asymptotic in nature. In this paper, we combine the best of these two types of results by developing a framework for analysing the non-asymptotic convergence rates of IGMs when they are applied to a class of structured convex optimization problems that includes least squares regression and logistic regression. We then demonstrate the power of our framework by proving, in a unified manner, new linear convergence results for three recently proposed algorithms—the incremental gradient method with increasing sample size [R.H. Byrd, G.M. Chin, J. Nocedal, and Y. Wu, Sample size selection in optimization methods for machine learning, Math. Program. Ser. B 134 (2012), pp. 127–155; M.P. Friedlander and M. Schmidt, Hybrid deterministic–stochastic methods for data fitting, SIAM J. Sci. Comput. 34 (2012), pp. A1380–A1405], the stochastic variance-reduced gradient (SVRG) method [R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction, Advances in Neural Information Processing Systems 26: Proceedings of the 2013 Conference, 2013, pp. 315–323], and the incremental aggregated gradient (IAG) method [D. Blatt, A.O. Hero, and H. Gauchman, A convergent incremental gradient method with a constant step size, SIAM J. Optim. 18 (2007), pp. 29–51]. We believe that our techniques will find further applications in the non-asymptotic convergence analysis of other first-order methods.     

Aggregation functions: Construction methods, conjunctive, disjunctive and mixed classes

In this second part of our state-of-the-art overview on aggregation theory, based again on our recent monograph on aggregation functions, we focus on several construction methods for aggregation functions and on special classes of aggregation functions, covering the well-known conjunctive, disjunctive, and mixed aggregation functions. Some fields of applications are included.     

Comparative tests of solution methods for signal-controlled road networks

In this paper, we consider a signal-controlled road network with link capacity expansions. This network design problem can be formulated as a constrained optimization subject to equilibrium flows. A projected Quasi-Newton method is proposed to find good local optimal solutions. Numerical calculations are conducted using a real data road network and large-scale grid networks.     

Extended sufficient semilocal convergence for the Secant method

We establish new sufficient convergence conditions for the Secant method to a locally unique solution of a nonlinear equation in a Banach space. Using our new concept of recurrent functions, and combining Lipschitz and center-Lipschitz conditions on the divided difference operator, we obtain a new semilocal convergence analysis of the Secant method. Moreover, our sufficient convergence conditions expand the applicability of the Secant method in cases not covered before (Dennis, 1971 [9], Hernández et al., 2005 [8], Laasonen, 1969 [15], Ortega and Rheinboldt, 1970 [11], Potra, 1982 [5], Potra, 1985 [7], Schmidt, 1978 [18], Yamamoto, 1987 [12], Wolfe, 1978 [19]). Numerical examples are also provided in this study.     

An experimental study on methods for the selection of basis functions in regression

A comparative study is carried out in the problem of selecting a subset of basis functions in regression tasks. The emphasis is put on practical requirements, such as the sparsity of the solution or the computational effort. A distinction is made according to the implicit or explicit nature of the selection process. In explicit selection methods the basis functions are selected from a set of candidates with a search process. In implicit methods a model with all the basis functions is considered and the model parameters are computed in such a way that several of them become zero. The former methods have the advantage that both the sparsity and the computational effort can be controlled. We build on earlier work on Bayesian interpolation to design efficient methods for explicit selection guided by model evidence, since there is strong indication that the evidence prefers simple models that generalize fairly well. Our experimental results indicate that very similar results between implicit and explicit methods can be obtained regarding generalization performance. However, they make use of different numbers of basis functions and are obtained at very different computational costs. It is also reported that the models with the highest evidence are not necessarily those with the best generalization performance.     

On the convergence of the Bl-LSQR algorithm for solving matrix equations

Karimi and Toutounian [The block least squares method for solving nonsymmetric linear system with multiple right-hand sides, Appl. Math. Comput. 177 (2006), pp. 852–862], proposed a block version of the LSQR algorithm, say Bl-LSQR, for solving linear system of equations with multiple right-hand sides. In this paper, the convergence of the Bl-LSQR algorithm is studied. We deal with some computational aspects of the Bl-LSQR algorithm for solving matrix equations. Some numerical experiments on test matrices are presented.     

A Newton method for solving continuous multiple material minimum compliance problems

This paper presents an implementation of an active-set line-search Newton method intended for solving large-scale instances of a class of multiple material minimum compliance problems. The problem is modeled with a convex objective function and linear constraints. At each iteration of the Newton method, one or two linear saddle point systems are solved. These systems involve the Hessian of the objective function, which is both expensive to compute and completely dense. Therefore, the linear algebra is arranged such that the Hessian is not explicitly formed. The main concern is to solve a sequence of closely related problems appearing as the continuous relaxations in a nonlinear branch and bound framework for solving discrete minimum compliance problems. A test-set consisting of eight discrete instances originating from the design of laminated composite structures is presented. Computational experiments with a branch and bound method indicate that the proposed Newton method can, on most instances in the test-set, take advantage of the available starting point information in an enumeration tree and resolve the relaxations after branching with few additional function evaluations. Discrete feasible designs are obtained by a rounding heuristic. Designs with provably good objective functions are presented.     

Efficient computation of higher order frequency response functions for nonlinear systems with,and without,a constant term

The behaviour of a nonlinear system can be profoundly affected by the presence of a constant or dc term in the system governing equation. These changes are reflected in the nonlinear frequency response characteristics of the system which provide a powerful insight into the system's dynamics. In this article, a new and efficient algorithm is presented for computing the higher order Volterra frequency response functions from nonlinear time-domain models that may contain a constant term. A comparison with previous methods is included to demonstrate the significant gains in computational efficiency that are achieved using the new method. The algorithm is applicable to systems modelled by nonlinear differential, or difference, equations and is easily automated. Several examples are used to illustrate the method, and to highlight the importance of dc terms in nonlinear system analysis.     

Robust filtering for uncertain linear systems: LMI based methods with parametric Lyapunov functions

This paper addresses the design of robust filters for linear continuous-time systems subject to parameter uncertainty in the state-space model. The uncertain parameters are supposed to belong to a given convex bounded polyhedral domain. Two methods based on parameter-dependent Lyapunov functions are proposed for designing linear stationary asymptotically stable filters that assure asymptotic stability and a guaranteed performance, irrespective of the uncertain parameters. The proposed filter designs are given in terms of linear matrix inequalities which depend on a scalar parameter that should be searched for in order to optimize the filter performance.     

On a third order family of methods for solving nonlinear equations

In this article we present a third-order family of methods for solving nonlinear equations. Some well-known methods belong to our family, for example Halley's method, method (24) from [M. Basto, V. Semiao, and F.L. Calheiros, A new iterative method to compute nonlinear equations, Appl. Math. Comput. 173 (2006), pp. 468–483] and the super-Halley method from [J.M. Gutierrez and M.A. Hernandez, An acceleration of Newton's method: Super-Halley method, Appl. Math. Comput. 117 (2001), pp. 223–239]. The convergence analysis shows the third order of our family. We also give sufficient conditions for the stopping inequality |x _n+1?α|≤|x _n+1?x _n | for this family. Comparison of the family members shows that there are no significant differences between them. Several examples are presented and compared.