On the convergence of the generalized Weiszfeld algorithm

In this paper we consider Weber-like location problems. The objective function is a sum of terms, each a function of the Euclidean distance from a demand point. We prove that a Weiszfeld-like iterative procedure for the solution of such problems converges to a local minimum (or a saddle point) when three conditions are met. Many location problems can be solved by the generalized Weiszfeld algorithm. There are many problem instances for which convergence is observed empirically. The proof in this paper shows that many of these algorithms indeed converge.     

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.     

Weber problems with mixed distances and regional demand

We consider a location problem where the distribution of the existing facilities is described by a probability distribution and the transportation cost is given by a combination of transportation cost in a network and continuous distance. The motivation is that in many cases transportation cost is partly given by the cost of travel in a transportation network whereas the access to the network and the travel from the exit of the network to the new facility is given by a continuous distance.      

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.     

On the use of the Varignon frame for single facility Weber problems in the presence of convex barriers

This paper presents a new experimental approach to the Weber problem in the presence of convex barriers by using the Varignon frame. The Varignon frame is a mechanical system of strings, weights and a board with holes that has been used to identify an optimal location for the classical Weber problem. We show through analytical results that the same analog can also be used for some of the Weber problems in the presence of barriers. Some examples from the literature are revisited through experiments. Findings are compared to those found in the literature. Practical use of the analog is discussed as it provides rapid solutions, allows for flexibility, and enables one to visualize the problem.     

On the local convergence of an iterative approach for inverse singular value problems

The purpose of this paper is to provide the convergence theory for the iterative approach given by M.T. Chu [Numerical methods for inverse singular value problems, SIAM J. Numer. Anal. 29 (1992), pp. 885–903] in the context of solving inverse singular value problems. We provide a detailed convergence analysis and show that the ultimate rate of convergence is quadratic in the root sense. Numerical results which confirm our theory are presented. It is still an open issue to prove that the method is Q-quadratic convergent as claimed by M.T. Chu.     

Fast convergence of the simplified largest step path following algorithm

Each master iteration of a simplified Newton algorithm for solving a system of equations starts by computing the Jacobian matrix and then uses this matrix in the computation ofp Newton steps: the first of these steps is exact, and the other are called “simplified”. In this paper we apply this approach to a large step path following algorithm for monotone linear complementarity problems. The resulting method generates sequences of objective values (duality gaps) that converge to zero with Q-orderp+1 in the number of master iterations, and with a complexity of iterations. Corresponding author. Research done while visiting the Delft Technical University, and supported in part by CAPES — Brazil.     

A truncated aggregate smoothing Newton method for minimax problems

Aggregate function is a useful smoothing function to the max-function of some smooth functions and has been used to solve minimax problems, linear and nonlinear programming, generalized complementarity problems, etc. The aggregate function is a single smooth but complex function, its gradient and Hessian calculations are time-consuming. In this paper, a truncated aggregate smoothing stabilized Newton method for solving minimax problems is presented. At each iteration, only a small subset of the components in the max-function are aggregated, hence the number of gradient and Hessian calculations is reduced dramatically. The subset is adaptively updated with some truncating criterions, concerning only with computation of function values and not their gradients or Hessians, to guarantee the global convergence and, for the inner iteration, locally quadratic convergence with as few computational cost as possible. Numerical results show the efficiency of the proposed algorithm.     

The rectilinear distance Weber problem in the presence of a probabilistic line barrier

This paper considers the problem of locating a single facility in the presence of a line barrier that occurs randomly on a given horizontal route on the plane. The objective is to locate this new facility such that the sum of the expected rectilinear distances from the facility to the demand points in the presence of the probabilistic barrier is minimized. Some properties of the problem are reported, a solution algorithm is provided with an example problem, and some future extensions to the problem are discussed.     

Strong convergence of a general iterative algorithm for equilibrium problems and variational inequality problems

The purpose of this paper is to study the strong convergence of a general iterative scheme to find a common element of the set of common fixed points of a finite family of nonexpansive mappings, the set of solutions of variation inequalities for a relaxed cocoercive mapping and the set of solutions of an equilibrium problem. Our results extend recent results announced by many others.     

The core and the Weber set of games on augmenting systems

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. In their model, the feasible coalitions are those that induce connected subgraphs. Another type of model is introduced in Gilles, Owen and van den Brink. In their model, the possibilities of coalition formation are determined by the positions of the players in a so-called permission structure. Faigle proposed a general model for cooperative games defined on lattice structures. In this paper, the restrictions to the cooperation are given by a combinatorial structure called augmenting system which generalizes antimatroid structure and the system of connected subgraphs of a graph. In this framework, the core and the Weber set of games on augmenting systems are introduced and it is proved that monotone convex games have a non-empty core. Moreover, we obtain a characterization of the convexity of these games in terms of the core of the game and the Weber set of the extended game.     

On convergence of iterative methods for maximal correlation problems

Several iterative methods for maximal correlation problems (MCPs) have been proposed in the literature. This paper deals with the convergence of these iterations and contains three contributions. Firstly, a unified and concise proof of the monotone convergence of these iterative methods is presented. Secondly, a starting point strategy is analysed. Thirdly, some error estimates are presented to test the quality of a computed solution. Both theoretical results and numerical tests suggest that combining with this starting point strategy these methods converge rapidly and are more likely converging to a global maximizer of MCP. Copyright © 2016 John Wiley & Sons, Ltd.     

A note on the convergence of the MSMAOR method for linear complementarity problems

Modulus‐based splitting, as well as multisplitting iteration methods, for linear complementarity problems are developed by Zhong‐Zhi Bai. In related papers (see Bai, Z.‐Z., Zhang, L.‐L.: Modulus‐Based Synchronous Multisplitting Iteration Methods for Linear Complementarity Problems. Numerical Linear Algebra with Applications 20 (2013) 425–439, and the references cited therein), the problem of convergence for two‐parameter relaxation methods (accelerated overrelaxation‐type methods) is analyzed under the assumption that one parameter is greater than the other. Here, we will show how we can avoid this assumption and, consequently, improve the convergence area. Copyright © 2013 John Wiley & Sons, Ltd.     

Semilocal and global convergence of the Newton‐HSS method for systems of nonlinear equations

Newton‐HSS methods, which are variants of inexact Newton methods different from the Newton–Krylov methods, have been shown to be competitive methods for solving large sparse systems of nonlinear equations with positive‐definite Jacobian matrices (J. Comp. Math. 2010; 28 :235–260). In that paper, only local convergence was proved. In this paper, we prove a Kantorovich‐type semilocal convergence. Then we introduce Newton‐HSS methods with a backtracking strategy and analyse their global convergence. Finally, these globally convergent Newton‐HSS methods are shown to work well on several typical examples using different forcing terms to stop the inner iterations. Copyright © 2010 John Wiley & Sons, Ltd.     

A universal constant for the convergence of Newton's method and an application to the classical homotopy method

We give a new theorem concerning the convergence of Newton's method to compute an approximate zero of a system of equations. In this result, the constanth ₀=0.162434... appears, which plays a fundamental role in the localization of good initial points for the Newton iteration. We apply it to the determination of an appropriate discretization of the time interval in the classical homotopy method.     

Strong convergence of a new composite iterative method for equilibrium problems and fixed point problems

In this paper, we propose a new composite iterative method for finding a common point of the set of solutions of an equilibrium problem and the set of fixed points of a countable family of nonexpansive mappings in a Hilbert space. It is proved that the sequence generated by the iterative scheme converges strongly to a common point of the set of solutions of an equilibrium problem and the set of fixed points of a countable family of nonexpansive mappings. Our results improve and extend the corresponding ones announced by many others.     

Strong convergence of composite iterative methods for equilibrium problems and fixed point problems

We introduce a new composite iterative scheme by viscosity approximation method for finding a common point of the set of solutions of an equilibrium problem and the set of fixed points of a nonexpansive mapping in a Hilbert space. It is proved that the sequence generated by the iterative scheme converges strongly to a common point of the set of solutions of an equilibrium problem and the set of fixed points of a nonexpansive mapping. Our results substantially improve the corresponding results of Takahashi and Takahashi [A. Takahashi, W. Takahashi, Viscosity approximation methods for equilibrium problems and fixed point problems in Hilbert spaces, J. Math. Anal. Appl. 331 (2007) 506-515]. Essentially a new approach for finding solutions of equilibrium problems and the fixed points of nonexpansive mappings is provided.     

Postprocessing and higher order convergence for the mixed finite element approximations of the Stokes eigenvalue problems

In this paper we propose a method for improving the convergence rate of the mixed finite element approximations for the Stokes eigenvalue problem. It is based on a postprocessing strategy that consists of solving an additional Stokes source problem on an augmented mixed finite element space which can be constructed either by refining the mesh or by using the same mesh but increasing the order of the mixed finite element space. Dedicated to Ivan Hlaváček on the occasion of his 75th birthday     

Abstract convergence theorem for quasi-convex optimization problems with applications

Abstract

Quasi-convex optimization is fundamental to the modelling of many practical problems in various fields such as economics, finance and industrial organization. Subgradient methods are practical iterative algorithms for solving large-scale quasi-convex optimization problems. In the present paper, focusing on quasi-convex optimization, we develop an abstract convergence theorem for a class of sequences, which satisfy a general basic inequality, under some suitable assumptions on parameters. The convergence properties in both function values and distances of iterates from the optimal solution set are discussed. The abstract convergence theorem covers relevant results of many types of subgradient methods studied in the literature, for either convex or quasi-convex optimization. Furthermore, we propose a new subgradient method, in which a perturbation of the successive direction is employed at each iteration. As an application of the abstract convergence theorem, we obtain the convergence results of the proposed subgradient method under the assumption of the Hölder condition of order p and by using the constant, diminishing or dynamic stepsize rules, respectively. A preliminary numerical study shows that the proposed method outperforms the standard, stochastic and primal-dual subgradient methods in solving the Cobb–Douglas production efficiency problem.     

A convergence analysis of nonlinear implicit iterative method for nonlinear ill-posed problems

Implicit iterative method acquires good effect in solving linear ill-posed problems. We have ever applied the idea of implicit iterative method to solve nonlinear ill-posed problems, under the restriction that α is appropriate large, we proved the monotonicity of iterative error and obtained the convergence and stability of iterative sequence, numerical results show that the implicit iterative method for nonlinear ill-posed problems is efficient. In this paper, we analyze the convergence and stability of the corresponding nonlinear implicit iterative method when α_k are determined by Hanke criterion.