Iterative method generated by inverse interpolation with additional evaluations

An improvement of the iterative methods based on one point iteration function, with or without memory, using n points with the same amount of information in each point and generated by the inverse polynomial interpolation is given. The adaptation of the strategy presented here gives a new iteration function with a new evaluation of the function which increases the local order of convergence dramatically. This method is generalized to r evaluations of the function. This method for the computation of solutions of nonlinear equations is interesting when it is necessary to get high precision because it provides a lower cost when we use adaptive multi-precision arithmetics. AMS subject classification 65H05     

乘子方法中的参数选择

Di Pillo和Grippo提出的含参数C〉0的增广Lagrangian函数中，使用了最大函数，该函数可能在无穷多个点处不可微．为了克服这个问题，濮定国在2004年提出了一类带新的NCP函数的乘子法．该方法在增广Lagrangian函数和原问题之间存在很好的等价性；同时该方法具有全局收敛性，且在适当假设下，具有超线性收敛率．但是在该方法中，要求参数C充分大．为了实现算法及提高算法效率，本文给出了一个有效选择参数C的方法．     

一类线性约束下不可微最优化问题的可行下降方法

本文给出了一类线性约束下不可微量优化问题的可行下降方法，这类问题的目标函数是凸函数和可微函数的合成函数，算法通过解系列二次规划寻找可行下降方向，新的迭代点由不精确线搜索产生，在较弱的条件下，我们证明了算法的全局收敛性     

The constrained Fisher scoring method for maximum likelihood computation of a nonparametric mixing distribution

This paper proposes a new method for computing the nonparametric maximum likelihood estimate of a mixing distribution. It uses the Fisher scoring quadratic approximation to the log-likelihood function of the mixing proportions. At each iteration, new candidate support points are found and included, as guided by the gradient function, and bad support points are discarded, after being found redundant by optimizing the quadratic approximation. Numerical studies show that the CFS method is generally competitive with the fast and stable constrained Newton method; it may even have an advantage over the latter when the initial estimate is badly chosen.     

Simulated annealing for constrained global optimization

Hide-and-Seek is a powerful yet simple and easily implemented continuous simulated annealing algorithm for finding the maximum of a continuous function over an arbitrary closed, bounded and full-dimensional body. The function may be nondifferentiable and the feasible region may be nonconvex or even disconnected. The algorithm begins with any feasible interior point. In each iteration it generates a candidate successor point by generating a uniformly distributed point along a direction chosen at random from the current iteration point. In contrast to the discrete case, a single step of this algorithm may generateany point in the feasible region as a candidate point. The candidate point is then accepted as the next iteration point according to the Metropolis criterion parametrized by anadaptive cooling schedule. Again in contrast to discrete simulated annealing, the sequence of iteration points converges in probability to a global optimum regardless of how rapidly the temperatures converge to zero. Empirical comparisons with other algorithms suggest competitive performance by Hide-and-Seek.This material is based on work supported by a NATO Collaborative Research Grant, no. 0119/89.     

约束优化问题的一类光滑罚算法的全局收敛特性

对约束优化问题给出了一类光滑罚算法.它是基于一类光滑逼近精确罚函数 l_p(p\in(0,1]) 的光滑函数 L_p 而提出的.在非常弱的条件下, 建立了算法的一个摄动定理, 导出了算法的全局收敛性.特别地, 在广义Mangasarian-Fromovitz约束规范假设下, 证明了当 p=1 时, 算法经过有限步迭代后, 所有迭代点都是原问题的可行解; p\in(0,1) 时,算法经过有限迭代后, 所有迭代点都是原问题可行解集的内点.     

Approximate Greatest Descent Methods for Optimization with Equality Constraints

In an optimization problem with equality constraints the optimal value function divides the state space into two parts. At a point where the objective function is less than the optimal value, a good iteration must increase the value of the objective function. Thus, a good iteration must be a balance between increasing or decreasing the objective function and decreasing a constraint violation function. This implies that at a point where the constraint violation function is large, we should construct noninferior solutions relative to points in a local search region. By definition, an accessory function is a linear combination of the objective function and a constraint violation function. We show that a way to construct an acceptable iteration, at a point where the constraint violation function is large, is to minimize an accessory function. We develop a two-phases method. In Phase I some constraints may not be approximately satisfied or the current point is not close to the solution. Iterations are generated by minimizing an accessory function. Once all the constraints are approximately satisfied, the initial values of the Lagrange multipliers are defined. A test with a merit function is used to determine whether or not the current point and the Lagrange multipliers are both close to the optimal solution. If not, Phase I is continued. If otherwise, Phase II is activated and the Newton method is used to compute the optimal solution and fast convergence is achieved.     

线性权互补问题的新全牛顿步可行内点算法

基于一个连续可微函数,通过等价变换中心路径,给出求解线性权互补问题的一个新全牛顿步可行内点算法.该算法每步迭代只需求解一个线性方程组,且不需要进行线搜索.通过适当选取参数,分析了迭代点的严格可行性,并证明算法具有线性优化最好的多项式时间迭代复杂度.数值结果验证了算法的有效性.     

Readily implementable conjugate gradient methods

Conjugate gradient methods have been extensively used to locate unconstrained minimum points of real-valued functions. At present, there are several readily implementable conjugate gradient algorithms that do not require exact line search and yet are shown to be superlinearly convergent. However, these existing algorithms usually require several trials to find an acceptable stepsize at each iteration, and their inexact line search can be very timeconsuming.In this paper we present new readily implementable conjugate gradient algorithms that will eventually require only one trial stepsize to find an acceptable stepsize at each iteration.Making usual continuity assumptions on the function being minimized, we have established the following properties of the proposed algorithms. Without any convexity assumptions on the function being minimized, the algorithms are globally convergent in the sense that every accumulation point of the generated sequences is a stationary point. Furthermore, when the generated sequences converge to local minimum points satisfying second-order sufficient conditions for optimality, the algorithms eventually demand only one trial stepsize at each iteration, and their rate of convergence isn-step superlinear andn-step quadratic.This research was supported in part by the National Science Foundation under Grant No. ENG 76-09913.     

过两个样本点的最小一乘回归线

本文用一种选代法，求过两个样本点的最小一乘回归线．     

严格伪压缩映像族隐格式迭代逼近不动点几何结果

对非线性算子迭代序列逼近不动点过程的几何结构进行研究,在提出并证明了一个H ilbert空间中收敛序列的钝角原理基础上,应用这个钝角原理研究了严格伪压缩映像族的隐格式迭代序列逼近公共不动点的几何结构.并证明了相应的钝角原理.这个钝角原理表述了严格伪压缩映像族的隐格式迭代序列逼近公共不动点时与公共不动点集形成了钝角关系.这个钝角关系是使用相应内积序列的上极限表示的.事实上这个钝角结果的表述形式也是一个几何变分不等式,迭代序列的极限点即是这个几何变分不等式的解.一方面这个钝角结果表述了严格伪压缩映像族公共不动点隐格式逼近的几何过程,另一方面,这个钝角结果自然是隐格式迭代序列逼近严格伪压缩映像族公共不动点的必要条件.     

A minimization method with approximation of feasible set and epigraph of objective function

For a convex programming problem we propose a solution method which belongs to the class of cutting-plane methods. When constructing approximate solutions to the problem, this technique concurrently approximates its feasible set and the epigraph of the objective function. Planes for cutting the iteration points are being constructed with the help of subgradients of the objective function and left-hand sides of constraints. In this connection, one can find each iteration point by solving a linear programming problem. As distinct from most other well-known cuttingplane methods, the proposed technique allows the possibility to periodically update approximating sets by dropping accumulated constraints. We substantiate the convergence of the proposed method and discuss its numerical realization.     

Extragradient Methods and Linesearch Algorithms for Solving Ky Fan Inequalities and Fixed Point Problems

In this paper, we introduce some new iterative methods for finding a common element of the set of points satisfying a Ky Fan inequality, and the set of fixed points of a contraction mapping in a Hilbert space. The strong convergence of the iterates generated by each method is obtained thanks to a hybrid projection method, under the assumptions that the fixed-point mapping is a ??-strict pseudocontraction, and the function associated with the Ky Fan inequality is pseudomonotone and weakly continuous. A?Lipschitz-type condition is assumed to hold on this function when the basic iteration comes from the extragradient method. This assumption is unnecessary when an Armijo backtracking linesearch is incorporated in the extragradient method. The particular case of variational inequality problems is examined in a last section.     

On the Existence of Fixed Points for Approximate Value Iteration and Temporal-Difference Learning

Approximate value iteration is a simple algorithm that combats the curse of dimensionality in dynamic programs by approximating iterates of the classical value iteration algorithm in a spirit reminiscent of statistical regression. Each iteration of this algorithm can be viewed as an application of a modified dynamic programming operator to the current iterate. The hope is that the iterates converge to a fixed point of this operator, which will then serve as a useful approximation of the optimal value function. In this paper, we show that, in general, the modified dynamic programming operator need not possess a fixed point; therefore, approximate value iteration should not be expected to converge. We then propose a variant of approximate value iteration for which the associated operator is guaranteed to possess at least one fixed point. This variant is motivated by studies of temporal-difference (TD) learning, and existence of fixed points implies here existence of stationary points for the ordinary differential equation approximated by a version of TD that incorporates exploration.     

Randomized search directions in descent methods for minimizing certain quasidifferentiable functions

Several descent methods have recently been proposed for minimizing smooth compositions of max-type functions. The methods generate many search directions at each iteration. This paper shows that a random choice of only two search directions at each iteration suffices for retaining convergence to inf-stationary points with probability 1. This technique may decrease significantly the work in quadratic programming and line searches, thus enabling efficient implementations of the methods.     

CONVERGENCE OF AN ITERATION METHOD WITHOUT DERIVATIVE

In this paper, we give a convergence theorem and error estimates for an iteration method under new Kantorovitch-Ostrowski type condition using the information of higher derivatives at initial points. Compared with the corresponding study in [3],the convergence determination is established under one global condition, instead of two , on the function.     

Scattered data interpolation using minimum energy Powell-Sabin elements and data dependent triangulations

A popular approach for obtaining surfaces interpolating to scattered data is to define the interpolant in a piecewise manner over a triangulation with vertices at the data points. In most cases, the interpolant cannot be uniquely determined from the prescribed function values since it belongs to a space of functions of dimension greater than the number of data points. Thus, additional parameters are needed to define an interpolant and have to be estimated somehow from the available data. It is intuitively clear that the quality of approximation by the interpolant depends on the choice of the triangulation and on the method used to provide the additional parameters. In this paper we suggest basing the selection of the triangulation and the computation of the additional parameters on the idea of minimizing a given cost functional measuring the quality of the interpolant. We present a scheme that iteratively updates the triangulation and computes values of the additional parameters so that the quality of the interpolant, as measured by the cost functional, improves from iteration to iteration. This method is discussed and tested numerically using an energy functional and Powell-Sabin twelve split interpolants.     

集值非扩张映象不动点存在与收敛性

讨论了δ集值非扩张映象在一致凸Banach空间中不动点非空的充分必要条件与Ishikawa迭代序列的收敛性及确保迭代程序收敛到不动点的条件,所得结果是单值非扩张映象情形的推广和发展.     

A hyperbolic tangent identity and the geometry of Padé sign function iterations

The rational iterations obtained from certain Padé approximations associated with computing the matrix sign function are shown to be equivalent to iterations involving the hyperbolic tangent and its inverse. Using this equivalent formulation many results about these Padé iterations, such as global convergence, the semi-group property under composition, and explicit partial fraction decompositions can be obtained easily. In the second part of the paper it is shown that the behavior of points under the Padé iterations can be expressed, via the Cayley transform, as the combined result of a completely regular iteration and a chaotic iteration. These two iterations are decoupled, with the chaotic iteration taking the form of a multiplicative linear congruential random number generator where the multiplier is equal to the order of the Padé approximation.This research was supported in part by the National Science Foundation under Grant No. ECS-9120643, the Air Force Office of Scientific Research under Grant no. F49620-94-1-0104DEF, and the Office of Naval Research under Grant No. N00014-92-J-1706.