A Modified Quasi-Newton Method for Structured Optimization with Partial Information on the Hessian

This paper develops a modified quasi-Newton method for structured unconstrained optimization with partial information on the Hessian, based on a better approximation to the Hessian in current search direction. The new approximation is decided by both function values and gradients at the last two iterations unlike the original one which only uses the gradients at the last two iterations. The modified method owns local and superlinear convergence. Numerical experiments show that the proposed method is encouraging comparing with the methods proposed in [4] for structured unconstrained optimization Presented at the 6th International Conference on Optimization: Techniques and Applications, Ballarat, Australia, December 9–11, 2004     

二维椭圆型方程反问题中优化算法的比较

近年来，决定椭圆型方程系数反问题在地磁、地球物理、冶金和生物等实际问题上有着广泛的应用．本文讨论了二维的决定椭圆型方程系数反问题的数值求解方法．由误差平方和最小原则，这个反问题可化为一个变分问题，并进一步离散化为一个最优化问题，其目标函数依赖于要决定的方程系数．本文着重考察非线性共轭梯度法在此最优化问题数值计算中的表现，并与拟牛顿法作为对比．为了提高算法的效率我们适当选择加快收敛速度的预处理矩阵．同时还考察了线搜索方法的不同对优化算法的影响．数值实验的结果表明，非线性共轭梯度法在这类大规模优化问题中相对于拟牛顿法更有效．     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

一类多体系统非完整运动最优规划的拟牛顿算法

研究带有非完整约束的一类多体系统运动规划问题。多体系统中的非完整约束通常是由不可积的速度约束或不可积的守恒律引起。在系统动量和动量矩守恒情况下,动力学方程降阶为非完整形式约束方程,系统的控制问题可转化为无漂移系统的非完整运动规划问题。文中首先导出具有多体开链系统的非完整运动模型。利用最优控制理论和最优化技术,采用输入参数化的方法将连续的最优控制问题转化为离散的最优控制问题,提出一种非完整多体系统运动规划的拟牛顿算法。最后将该方法用于自由漂浮的空间三连杆机构,仿真结果验证了该方法的有效性。     

New Quasi-Newton Equation and Related Methods for Unconstrained Optimization

In unconstrained optimization, the usual quasi-Newton equation is B _k+1 s _k=y _k, where y _k is the difference of the gradients at the last two iterates. In this paper, we propose a new quasi-Newton equation, , in which is based on both the function values and gradients at the last two iterates. The new equation is superior to the old equation in the sense that better approximates ² f(x _k+1)s _k than y _k. Modified quasi-Newton methods based on the new quasi-Newton equation are locally and superlinearly convergent. Extensive numerical experiments have been conducted which show that the new quasi-Newton methods are encouraging.     

Local convergence of quasi-Newton methods for B-differentiable equations

We study local convergence of quasi-Newton methods for solving systems of nonlinear equations defined by B-differentiable functions. We extend the classical linear and superlinear convergence results for general quasi-Newton methods as well as for Broyden's method. We also show how Broyden's method may be applied to nonlinear complementarity problems and illustrate its computational performance on two small examples.     

Properties of updating methods for the multipliers in augmented Lagrangians

The convergence properties of different updating methods for the multipliers in augmented Lagrangians are considered. It is assumed that the updating of the multipliers takes place after each line search of a quasi-Newton method. Two of the updating methods are shown to be linearly convergent locally, while a third method has superlinear convergence locally. Modifications of the algorithms to ensure global convergence are considered. The results of a computational comparison with other methods are presented.This work was supported by the Swedish Institute of Applied Mathematics.     

A heuristic algorithm for the optimization of a retrial system with Bernoulli vacation

In this study, we consider an M/M/c retrial queue with Bernoulli vacation under a single vacation policy. When an arrived customer finds a free server, the customer receives the service immediately; otherwise the customer would enter into an orbit. After the server completes the service, the server may go on a vacation or become idle (waiting for the next arriving, retrying customer). The retrial system is analysed as a quasi-birth-and-death process. The sufficient and necessary condition of system equilibrium is obtained. The formulae for computing the rate matrix and stationary probabilities are derived. The explicit close forms for system performance measures are developed. A cost model is constructed to determine the optimal values of the number of servers, service rate, and vacation rate for minimizing the total expected cost per unit time. Numerical examples are given to demonstrate this optimization approach. The effects of various parameters in the cost model on system performance are investigated.     

Initial guess by improved population-based intelligent algorithms for large inter-frame deformation measurement using digital image correlation

Digital image correlation (DIC) has received a widespread research and application in experimental mechanics. In DIC, the performance of subpixel registration algorithm (e.g., Newton-Raphson method, quasi-Newton method) relies heavily on the initial guess of deformation. In the case of small inter-frame deformation, the initial guess could be found by simple search scheme, the coarse-fine search for instance. While for large inter-frame deformation, it is difficult for simple search scheme to robustly estimate displacement parameters and deformation parameters simultaneously with low computational cost. In this paper, we proposed three improving strategies, i.e. Q-stage evolutionary strategy (T), parameter control strategy (C) and space expanding strategy (E), and then combined them into three population-based intelligent algorithms (PIAs), i.e. genetic algorithm (GA), differential evolution (DE) and particle swarm optimization (PSO), and finally derived eighteen different algorithms to calculate the initial guess for qN. The eighteen algorithms were compared in three sets of experiments including large rigid body translation, finite uniaxial strain and large rigid body rotation, and the results showed the effectiveness of proposed improving strategies. Among all compared algorithms, DE-TCE is the best which is robust, convenient and efficient for large inter-frame deformation measurement.     

Broyden's method in Hilbert space

Broyden's method is formulated for the solution of nonlinear operator equations in Hilbert spaces. The algorithm is proven to be well defined and a linear rate of convergence is shown. Under an additional assumption on the initial approximation for the derivative we prove the superlinear rate of convergence.