Low Order-Value Optimization and applications

Given r real functions F ₁(x),...,F _r (x) and an integer p between 1 and r, the Low Order-Value Optimization problem (LOVO) consists of minimizing the sum of the functions that take the p smaller values. If (y ₁,...,y _r ) is a vector of data and T(x, t _i ) is the predicted value of the observation i with the parameters , it is natural to define F _i (x) =  (T(x, t _i ) − y _i )² (the quadratic error in observation i under the parameters x). When p =  r this LOVO problem coincides with the classical nonlinear least-squares problem. However, the interesting situation is when p is smaller than r. In that case, the solution of LOVO allows one to discard the influence of an estimated number of outliers. Thus, the LOVO problem is an interesting tool for robust estimation of parameters of nonlinear models. When p ≪ r the LOVO problem may be used to find hidden structures in data sets. One of the most successful applications includes the Protein Alignment problem. Fully documented algorithms for this application are available at www.ime.unicamp.br/~martinez/lovoalign. In this paper optimality conditions are discussed, algorithms for solving the LOVO problem are introduced and convergence theorems are proved. Finally, numerical experiments are presented.     

DRIC: A dynamic version of the RIC method

A new incomplete factorization method is proposed, differing from previous ones by the way in which the diagonal entries of the triangular factors are defined. A comparison is given with the dynamic modified incomplete factorization methods of Axelsson–Barker and Beauwens, and with the relaxed incomplete Cholesky method of Axelsson and Lindskog. Theoretical arguments show that the new method is at least as robust as both previous ones, while numerical experiments made in the discrete PDE context show an effective improvement in many practical circumstances, particularly for anisotropic problems.     

On the global convergence of Chebyshev's iterative method

In [A. Melman, Geometry and convergence of Euler's and Halley's methods, SIAM Rev. 39(4) (1997) 728–735] the geometry and global convergence of Euler's and Halley's methods was studied. Now we complete Melman's paper by considering other classical third-order method: Chebyshev's method. By using the geometric interpretation of this method a global convergence theorem is performed. A comparison of the different hypothesis of convergence is also presented.     

A simple proof of a primal affine scaling method

In this paper, we present a simpler proof of the result of Tsuchiya and Muramatsu on the convergence of the primal affine scaling method. We show that the primal sequence generated by the method converges to the interior of the optimum face and the dual sequence to the analytic center of the optimal dual face, when the step size implemented in the procedure is bounded by 2/3. We also prove the optimality of the limit of the primal sequence for a slightly larger step size of 2q/(3q–1), whereq is the number of zero variables in the limit. We show this by proving the dual feasibility of a cluster point of the dual sequence.Partially supported by the grant CCR-9321550 from NSF.     

两类变参数梯度法及收敛性

本文在ＬＭＩＮＮ方法的基础上,提出了两类变参数梯度法,然后证明了这两类方法在非精确线性搜索的Ｗｏｌｆｅ条件下是下降算法且具有全局收敛性。     

Newton-type methods of high order and domains of semilocal and global convergence

We present the geometric construction of some classical iterative methods that have global convergence and “infinite” speed of convergence when they are applied to solve certain nonlinear equations f(t)=0. In particular, for nonlinear equations with the degree of logarithmic convexity of f^′, L_f^′(t)=f^′(t)f^?(t)/f^″(t)², is constant, a family of Newton-type iterative methods of high orders of convergence is constructed. We see that this family of iterations includes the classical iterative methods. The convergence of the family is studied in the real line and the complex plane, and domains of semilocal and global convergence are located.     

Adaptive solution of infinite linear systems by Krylov subspace methods

In this paper we consider the problem of approximating the solution of infinite linear systems, finitely expressed by a sparse coefficient matrix. We analyse an algorithm based on Krylov subspace methods embedded in an adaptive enlargement scheme. The management of the algorithm is not trivial, due to the irregular convergence behaviour frequently displayed by Krylov subspace methods for nonsymmetric systems. Numerical experiments, carried out on several test problems, indicate that the more robust methods, such as GMRES and QMR, embedded in the adaptive enlargement scheme, exhibit good performances.     

A technique to choose the most efficient method between secant method and some variants

A few variants of the secant method for solving nonlinear equations are analyzed and studied. In order to compute the local order of convergence of these iterative methods a development of the inverse operator of the first order divided differences of a function of several variables in two points is presented using a direct symbolic computation. The computational efficiency and the approximated computational order of convergence are introduced and computed choosing the most efficient method among the presented ones. Furthermore, we give a technique in order to estimate the computational cost of any iterative method, and this measure allows us to choose the most efficient among them.     

非凸无约束优化问题的广义拟牛顿法的全局收敛性

本文对无约束优化问题提出一类新的广义拟牛顿法,并采用一类非精确线搜索证明了算法对一般非凸目标函数极小化问题的全局收敛性.     

Domain of existence for the solution of some IVP's and BVP's by using an efficient ninth-order iterative method

In this paper, we consider the problem of solving initial value problems and boundary value problems through the point of view of its continuous form. It is well known that in most cases these types of problems are solved numerically by performing a discretization and applying the finite difference technique to approximate the derivatives, transforming the equation into a finite-dimensional nonlinear system of equations. However, we would like to focus on the continuous problem, and therefore, we try to set the domain of existence and uniqueness for its analytic solution. For this purpose, we study the semilocal convergence of a Newton-type method with frozen first derivative in Banach spaces. We impose only the assumption that the Fréchet derivative satisfies the Lipschitz continuity condition and that it is bounded in the whole domain in order to obtain appropriate recurrence relations so that we may determine the domains of convergence and uniqueness for the solution. Our final aim is to apply these theoretical results to solve applied problems that come from integral equations, ordinary differential equations, and boundary value problems.     

A parallel method for finding the global minimum of univariate functions

We describe a new parallel method for solving global optimization problems. The formulation of the decision rules of this method is presented. We examine convergence conditions of the proposed algorithm and establish conditions which guarantee a considerable speedup with respect to the sequential version of the algorithm. We also present some numerical experiments executed on Alliant FX/80 for one class of multiextremal functions.The authors are greatly indebted to R. G. Strongin who stimulated the fulfillment of this research. They also would like to thank the anonymous referees for their useful suggestions.The research of the first author was partially supported by Grant 9494/NC/89 from the Italian Government under the Italian-Soviet Agreement about the Cultural and Scientific Exchange in 1990–1991. He thanks the Systems Department, University of Calabria, where he was a Visitor.     

Lower-dimensional linear complementarity problem approaches to the solution of a bi-obstacle problem

A globally convergent Broyden-like method for solving a bi-obstacle problem is proposed based on its equivalent lower-dimensional linear complementarity problem. A suitable line search technique is introduced here. The global and superlinear convergence of the method is verified under appropriate assumptions.     

A modified projection method with a new direction for solving variational inequalities

In this paper, we propose a new projection method for solving variational inequality problems, which can be viewed as an improvement of the method of Li et al. [M. Li, L.Z. Liao, X.M. Yuan, A modified projection method for co-coercive variational inequality, European Journal of Operational Research 189 (2008) 310-323], by adopting a new direction. Under the same assumptions as those in Li et al. (2008), we establish the global convergence of the proposed algorithm. Some preliminary computational results are reported, which illustrated that the new method is more efficient than the method of Li et al. (2008).     

A variant of Newton's method with accelerated third-order convergence

In the given method, we suggest an improvement to the iteration of Newton's method. Derivation of Newton's method involves an indefinite integral of the derivative of the function, and the relevant area is approximated by a rectangle. In the proposed scheme, we approximate this indefinite integral by a trapezoid instead of a rectangle, thereby reducing the error in the approximation. It is shown that the order of convergence of the new method is three, and computed results support this theory. Even though we have shown that the order of convergence is three, in several cases, computational order of convergence is even higher. For most of the functions we tested, the order of convergence in Newton's method was less than two and for our method, it was always close to three.     

The convergence of the perturbed Newton method and its application for ill-conditioned problems

Iterative methods, such as Newton’s, behave poorly when solving ill-conditioned problems: they become slow (first order), and decrease their accuracy. In this paper we analyze deeply and widely the convergence of a modified Newton method, which we call perturbed Newton, in order to overcome the usual disadvantages Newton’s one presents. The basic point of this method is the dependence of a parameter affording a degree of freedom that introduces regularization. Choices for that parameter are proposed. The theoretical analysis will be illustrated through examples.     

A graphical method for a class of Branin trajectories

The construction of Branin trajectories for locating the stationary points of a scalar function of many variables involves, in the general case, the numerical solution of a set of simultaneous ordinary differential equations, or some equivalent numerical procedure. For a function of only two variables which is separable in either the multiplicative or additive sense, it is shown that Branin trajectories may be obtained by a graphical method due to Volterra.The authors are indebted to Dr. L. C. W. Dixon for his helpful comments on the original draft of this paper.     

Cubic regularization of Newton method and its global performance

In this paper, we provide theoretical analysis for a cubic regularization of Newton method as applied to unconstrained minimization problem. For this scheme, we prove general local convergence results. However, the main contribution of the paper is related to global worst-case complexity bounds for different problem classes including some nonconvex cases. It is shown that the search direction can be computed by standard linear algebra technique.     

Implementation of a primal–dual method for SDP on a shared memory parallel architecture

Primal–dual interior point methods and the HKM method in particular have been implemented in a number of software packages for semidefinite programming. These methods have performed well in practice on small to medium sized SDPs. However, primal–dual codes have had some trouble in solving larger problems because of the storage requirements and required computational effort. In this paper we describe a parallel implementation of the primal–dual method on a shared memory system. Computational results are presented, including the solution of some large scale problems with over 50,000 constraints.     

Optimization under ordinal scales: When is a greedy solution optimal?

Mathematical formulation of an optimization problem often depends on data which can be measured in more than one acceptable way. If the conclusion of optimality depends on the choice of measure, then we should question whether it is meaningful to ask for an optimal solution. If a meaningful optimal solution exists and the objective function depends on data measured on an ordinal scale of measurement, then the greedy algorithm will give such a solution for a wide range of objective functions.