A projected Weiszfeld algorithm for the box-constrained Weber location problem

The Weber problem consists of finding a point in Rⁿ that minimizes the weighted sum of distances from m points in Rⁿ that are not collinear. An application that motivated this problem is the optimal location of facilities in the 2-dimensional case. A classical method to solve the Weber problem, proposed by Weiszfeld in 1937, is based on a fixed-point iteration.In this work we generalize the Weber location problem considering box constraints. We propose a fixed-point iteration with projections on the constraints and demonstrate descending properties. It is also proved that the limit of the sequence generated by the method is a feasible point and satisfies the KKT optimality conditions. Numerical experiments are presented to validate the theoretical results.     

A generalized Weiszfeld method for the multi-facility location problem

An iterative method is proposed for the K facilities location problem. The problem is relaxed using probabilistic assignments, depending on the distances to the facilities. The probabilities, that decompose the problem into K single-facility location problems, are updated at each iteration together with the facility locations. The proposed method is a natural generalization of the Weiszfeld method to several facilities.     

A smoothing inexact Newton method for nonlinear complementarity problems

In this article, we propose a new smoothing inexact Newton algorithm for solving nonlinear complementarity problems (NCP) base on the smoothed Fischer-Burmeister function. In each iteration, the corresponding linear system is solved only approximately. The global convergence and local superlinear convergence are established without strict complementarity assumption at the NCP solution. Preliminary numerical results indicate that the method is effective for large-scale NCP.     

Globally and Quadratically Convergent Algorithm for Minimizing the Sum of Euclidean Norms

For the problem of minimizing the sum of Euclidean norms (MSN), most existing quadratically convergent algorithms require a strict complementarity assumption. However, this assumption is not satisfied for a number of MSN problems. In this paper, we present a globally and quadratically convergent algorithm for the MSN problem. In particular, the quadratic convergence result is obtained without assuming strict complementarity. Examples without strictly complementary solutions are given to show that our algorithm can indeed achieve quadratic convergence. Preliminary numerical results are reported.     

A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems

A new algorithm for the solation of large-scale nonlinear complementarity problems is introduced. The algorithm is based on a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems with up to 10 000 variables are presented. Partially supported by Agenzia Spaziale Italiana, Roma, Italy.     

Rates of convergence for adaptive Newton methods

We consider Newton-type methods for constrained optimization problems in infinite-dimensional spaces, where at each iteration the first and second derivatives and the feasible set are approximated. The approximations can change at each iteration and conditions are given under which linear and superlinear rates of convergence of the iterates to the optimal point hold. Several applications are discussed.     

An Exterior Newton Method for Strictly Convex Quadratic Programming

We propose an exterior Newton method for strictly convex quadratic programming (QP) problems. This method is based on a dual formulation: a sequence of points is generated which monotonically decreases the dual objective function. We show that the generated sequence converges globally and quadratically to the solution (if the QP is feasible and certain nondegeneracy assumptions are satisfied). Measures for detecting infeasibility are provided. The major computation in each iteration is to solve a KKT-like system. Therefore, given an effective symmetric sparse linear solver, the proposed method is suitable for large sparse problems. Preliminary numerical results are reported.     

The Adjoint Newton Algorithm for Large-Scale Unconstrained Optimization in Meteorology Applications

A new algorithm is presented for carrying out large-scale unconstrained optimization required in variational data assimilation using the Newton method. The algorithm is referred to as the adjoint Newton algorithm. The adjoint Newton algorithm is based on the first- and second-order adjoint techniques allowing us to obtain the Newton line search direction by integrating a tangent linear equations model backwards in time (starting from a final condition with negative time steps). The error present in approximating the Hessian (the matrix of second-order derivatives) of the cost function with respect to the control variables in the quasi-Newton type algorithm is thus completely eliminated, while the storage problem related to the Hessian no longer exists since the explicit Hessian is not required in this algorithm. The adjoint Newton algorithm is applied to three one-dimensional models and to a two-dimensional limited-area shallow water equations model with both model generated and First Global Geophysical Experiment data. We compare the performance of the adjoint Newton algorithm with that of truncated Newton, adjoint truncated Newton, and LBFGS methods. Our numerical tests indicate that the adjoint Newton algorithm is very efficient and could find the minima within three or four iterations for problems tested here. In the case of the two-dimensional shallow water equations model, the adjoint Newton algorithm improves upon the efficiencies of the truncated Newton and LBFGS methods by a factor of at least 14 in terms of the CPU time required to satisfy the same convergence criterion.The Newton, truncated Newton and LBFGS methods are general purpose unconstrained minimization methods. The adjoint Newton algorithm is only useful for optimal control problems where the model equations serve as strong constraints and their corresponding tangent linear model may be integrated backwards in time. When the backwards integration of the tangent linear model is ill-posed in the sense of Hadamard, the adjoint Newton algorithm may not work. Thus, the adjoint Newton algorithm must be used with some caution. A possible solution to avoid the current weakness of the adjoint Newton algorithm is proposed.     

An inexact Newton method for nonlinear two-point boundary-value problems

The method of quasilinearization for nonlinear two-point boundary-value problems is an application of Newton's method to a nonlinear differential operator equation. Since the linear boundary-value problem to be solved at each iteration must be discretized, it is natural to consider quasilinearization in the framework of an inexact Newton method. More importantly, each linear problem is only a local model of the nonlinear problem, and so it is inefficient to try to solve the linear problems to full accuracy. Conditions on size of the relative residual of the linear differential equation can then be specified to guarantee rapid local convergence to the solution of the nonlinear continuous problem. If initial-value techniques are used to solve the linear boundary-value problems, then an integration step selection scheme is proposed so that the residual criteria are satisfied by the approximate solutions. Numerical results are presented that demonstrate substantial computational savings by this type of economizing on the intermediate problems.This work was supported in part by DOE Contract DE-AS05-82-ER13016 and NSF Grant RII-89-17691 and was part of the author's doctoral thesis at Rice University. It is a pleasure to thank the author's thesis advisors, Professor R. A. Tapia and Professor J. E. Dennis, Jr.     

A modified Newton method for minimization

Some promising ideas for minimizing a nonlinear function, whose first and second derivatives are given, by a modified Newton method, were introduced by Fiacco and McCormick (Ref. 1). Unfortunately, in developing a method around these ideas, Fiacco and McCormick used a potentially unstable, or even impossible, matrix factorization. Using some recently developed techniques for factorizing an indefinite symmetric matrix, we are able to produce a method which is similar to Fiacco and McCormick's original method, but avoids the difficulties of the original method.Both authors gratefully acknowledge the award of a research fellowship from the British Science Research Council.     

A generalized Newton method for absolute value equations

A direct generalized Newton method is proposed for solving the NP-hard absolute value equation (AVE) Ax − |x| = b when the singular values of A exceed 1. A simple MATLAB implementation of the method solved 100 randomly generated 1,000-dimensional AVEs to an accuracy of 10⁻⁶ in less than 10 s each. Similarly, AVEs corresponding to 100 randomly generated linear complementarity problems with 1,000 × 1,000 nonsymmetric positive definite matrices were also solved to the same accuracy in less than 29 s each.     

Feasible Semismooth Newton Method for a Class of Stochastic Linear Complementarity Problems

We consider a class of stochastic linear complementarity problems (SLCPs) with finitely many realizations. In this paper we reformulate this class of SLCPs as a constrained minimization (CM) problem. Then, we present a feasible semismooth Newton method to solve this CM problem. Preliminary numerical results show that this CM reformulation may yield a solution with high safety for SLCPs.     

Convergence Analysis of Gauss–Newton Methods for the Complementarity Problem

In a recent paper (Ref. 1), the first author presented a damped Gauss–Newton algorithm to solve the complementarity problem. Although the conclusions of the convergence theorems in the paper are valid, the proofs contain minor errors. The aim of this paper is to give correct proofs and also to show that they are valid under milder conditions.     

求解一类约束优化问题的Newton分裂算法

本文给出了求解一类约束优化问题的一个Newton分裂算法，并证明了算法的局部平方收敛性，该算法与已有算法相比，具有计算量小的特点，因而特别适合于求解大规模问题，为进一步降低算法的计算复杂性，我们结合Broyden算法，给出了两类Broyden类分裂算法。     

二次规划逆问题的牛顿方法

针对二次规划逆问题,将其表达为带有互补约束的锥约束优化问题.借助于对偶理论,将问题转化为变量更少的线性互补约束非光滑优化问题.通过扰动的方法求解转化后的问题并证明了收敛性.采用非精确牛顿法求解扰动问题,给出了算法的全局收敛性与局部二阶收敛速度.最后通过数值实验验证了该算法的可行性.     

Smoothing Functions and Smoothing Newton Method for Complementarity and Variational Inequality Problems

This paper provides for the first time some computable smoothing functions for variational inequality problems with general constraints. This paper proposes also a new version of the smoothing Newton method and establishes its global and superlinear (quadratic) convergence under conditions weaker than those previously used in the literature. These are achieved by introducing a general definition for smoothing functions, which include almost all the existing smoothing functions as special cases.     

Newton iteration for partial differential equations and the approximation of the identity

It is known that the critical condition which guarantees quadratic convergence of approximate Newton methods is an approximation of the identity condition. This requires that the composition of the numerical inversion of the Fréchet derivative with the derivative itself approximate the identity to an accuracy calibrated by the residual. For example, the celebrated quadratic convergence theorem of Kantorovich can be proven when this holds, subject to regularity and stability of the derivative map. In this paper, we study what happens when this condition is not evident a priori but is observed a posteriori. Through an in-depth example involving a semilinear elliptic boundary value problem, and some general theory, we study the condition in the context of dual norms, and the effect upon convergence. We also discuss the connection to Nash iteration.     

On the Newton Interior-Point Method for Nonlinear Programming Problems

Interior-point methods have been developed largely for nonlinear programming problems. In this paper, we generalize the global Newton interior-point method introduced in Ref. 1 and we establish a global convergence theory for it, under the same assumptions as those stated in Ref. 1. The generalized algorithm gives the possibility of choosing different descent directions for a merit function so that difficulties due to small steplength for the perturbed Newton direction can be avoided. The particular choice of the perturbation enables us to interpret the generalized method as an inexact Newton method. Also, we suggest a more general criterion for backtracking, which is useful when the perturbed Newton system is not solved exactly. We include numerical experimentation on discrete optimal control problems.     

非光滑非线性互补问题的牛顿法

研究了非光滑的非线性互补问题. 首先将非光滑的非线性互补问题转化为一个非光滑方程组,然后用牛顿法求解这个非光滑方程组. 在该牛顿法中,每次迭代只需一个原始函数B-微分中的一个元素. 最后证明了该牛顿法的超线性收敛性.