0000000000139010
AUTHOR
O. Lefebvre
Applications and numerical convergence of the partial inverse method
In 1983, J.E. Spingarn introduced what he called the Partial Inverse Method in the framework of Mathematical Programming. Since his initial articles, numerous applications have been given in various fields including Lagrangian multipliers methods, location theory, convex feasibility problems, analysis of data, economic equilibrium problems. In a first part of this paper we give a survey of these applications. Then by means of optimization problems relevant to location theory such as single and multifacility minimisum or minimax location problems, we examine the main advantages of the algorithm and we point out its drawbacks mainly concerning the rate of convergence. We study how different p…
About the finite convergence of the proximal point algorithm
We study the finite convergence property of the proximal point algorithm applied to the partial inverse, with respect to a subspace, of the subdifferential of a polyhedral convex function. Using examples we show how sufficient conditions providing the finite convergence can be realized and we give a case with non finite termination.
Sufficient conditions for coincidence in minisum multifacility location problems with a general metric
It is a well observed fact that in minisum multifacility location problems the optimal locations of several facilities often tend to coincide. Some sufficient conditions for this phenomenon, involving only the weights and applicable to any metric, have been published previously. The objective of this paper is to show how these conditions may be extended further and to obtain a more complete description of their implications, in particular, in the case of certain locational constraints.
Geometric interpretation of the optimality conditions in multifacility location and applications
Geometrical optimality conditions are developed for the minisum multifacility location problem involving any norm. These conditions are then used to derive sufficient conditions for coincidence of facilities at optimality; an example is given to show that these coincidence conditions seem difficult to generalize.
Duality for constrained multifacility location problems with mixed norms and applications
A dual problem is developed for the constrained multifacility minisum location problems involving mixed norms. General optimality conditions are also obtained providing new algorithms based on the concept of partial inverse of a multifunction. These algorithms which are decomposition methods, generate sequences globally converging to a primal and a dual solution respectively. Numerical results are reported.
A primal-dual algorithm for the fermat-weber problem involving mixed gauges
We give a new algorithm for solving the Fermat-Weber location problem involving mixed gauges. This algorithm, which is derived from the partial inverse method developed by J.E. Spingarn, simultaneously generates two sequences globally converging to a primal and a dual solution respectively. In addition, the updating formulae are very simple; a stopping rule can be defined though the method is not dual feasible and the entire set of optimal locations can be obtained from the dual solution by making use of optimality conditions. When polyhedral gauges are used, we show that the algorithm terminates in a finite number of steps, provided that the set of optimal locations has nonepty interior an…