Abstract
The problem of finding a point inRn, from which the sum-of-distances to a finite number of non-empty, closed, and convex sets is minimum is called the generalized Fermat-Torricelli Problem (FTP). In applications, along with the point that minimizes sum-of-distances, it is important to know the points in the convex sets at which the minimum sum-of-distances is achieved. Various formulations existing in literature do not involve finding the optimal points in the convex sets. In this work, we formulate a non-smooth convex optimization problem, with both the point/set of points which yields the minimum sum-of-distances as well as the corresponding points in the convex sets as primal variables. We term this problem as extended FTP (eFTP). We adopt a non-smooth projected primal-dual dynamical approach to solve this problem. The proposed dynamical system can exhibit a continuum of equilibria. Hence we show semistability of the set of optimal points, which is the pertinent notion of stability for such systems. A distributed implementation of the primal-dualdynamical system is also presented in this work. Four illustrative examples are considered for the simulation-based validation of the solution proposed for eFTP.
-
Author Keywords
- Optimization algorithms ,
- Lyapunov methods ,
- stability of nonlinear systems
-
IEEE Keywords
- Dynamical systems ,
- Convex functions ,
- Optimization ,
- Approximation algorithms ,
- Stability criteria ,
- Electrical engineering
Introduction
IN the sixteenth century, Pierre de Fermat formulated an optimization problem to determine a point in a plane such that the sum-of-distances from the point to three given points is minimal. Evangelista Torricelli devised a geometric solution to this problem [1], following which, the problem was named the asFermat-Torricelli problem (FTP). The problem has since then been generalized toRnwithNpoints. In the first century ad, Heron from Alexandria posed a problem that involves finding a point on a straight line in a plane, which minimizes the sum-of-distances to two given points. This has later been generalized torn with the straight line replaced by a convex set (target set) and the two points replaced byNnon-empty, closed, and convex sets. This problem goes by the names generalized FTP [2], [3] and generalized Heron problem [4]and finds application in the areas of location science [5]and logistics [6], where problems such as distributed network design, three factory problem [7], localization of customer service points, public service facilities, etc. are addressed.
Given a finite number of non-empty, closed, and convex sets, we consider the problem of finding a point inRn, from which the sum-of-distances to the sets is minimized. Moreover, our formulation involves finding the corresponding points in the convex sets, where the minima is reached. We term this problem as extended FTP (eFTP). The generalizedHeron problem can also be extended in this manner and the theoretical and simulation results presented in the paper hold true for it. The early geometrical and analytical understandings and solutions of FTP can be found in [5] and the references therein.Weiszfeld algorithm [8] which uses successive approximation was the first numerical algorithm to solve the FTP inRntoNpoints. In [9], the authors use Nesterov’s smoothing techniques to construct smooth approximations to non-smooth FTP and anon-smooth stochastic subgradient algorithm. This paper also contains a comprehensive survey of research articles on the FTP and its variants. The analytical and numerical approaches pursued so far do not find the optimal points in each of the convex sets, which are crucial from the applications point of view [6]. In this work, we propose a continuous-time non-smooth projected primal-dual dynamical system to solve theeFTP. Irrespective of the initial conditions, the trajectories of this dynamical system converge to one of the optimal points of the eFTP.The primal-dual dynamical approach for a smooth convex optimization has been explored in [10]–[13] and non-smooth projected primal-dual dynamics is presented in [14]–[16]. Thenon-smooth dynamics presented in [14] is based on augmented Lagrangian constructed by eliminating the inequality constraints using the exact penalty method. The exact knowledge of the penalty parameter is avoided by using a discontinuoussaddle-point like dynamics. Our work differs from [15], [16]with respect to the definition of the projection operator in the dynamics corresponding to the dual variables and the analysis of the stability of the dynamical system. In our work, instead of the asymptotic pointwise convergence to the set of optimal points, we adopt the notion of semistability to analyze the system behavior. The concept of semistability[17] finds relevance in systems that possess a continuum of(or non-isolated) equilibria. Since the eFTP is viable to have a continuum of equilibria, the notion of semistability is used in our work to analyse the stability of the equilibrium points.
Statement of Contributions: The main contributions of this work are the following. Motivated by the applications[6], where along with the point that minimizes the sum of- distances, it is equally essential to find the optimal points on the convex sets, we present a formulation of the eFTP that caters to this need. Then we adopt the primal-dual dynamical system approach, which to the best of our knowledge, has not been considered for the FTP. The proposed dynamical system is a non-smooth projected primal-dual dynamical system. These equilibrium points of the dynamical system (same as the set of optimal points of the eFTP) are shown to be semistable, in the sense that the trajectories of the dynamical system con-verge to one of the optimal point of the eFTP. Our formulation and the solution method assumes that the inequality constraints characterizing the convex sets are smooth and nonlinear. When the work by implementing a distributed version of the thenon-smooth dynamical system.
Conclusion
The eFTP in both centralized and distributed settings wasalso solved using discrete-time subgradient algorithms [20].To compare the performance of these algorithms with (9) and(14), the initial conditions were set at the optimal points. Itwas found that solutions of (9) and (14) stay at the optimalpoints since the dynamics is designed such that the equilibriumpoints are optimal points. Whereas, the trajectories of thediscrete-time subgradient algorithms initially escape from theoptimal points and eventually converge to it, irrespectiveof the step sizes chosen. This transient behaviour of thetrajectories reveals that the continuous-time systems (9) and(14) performed better in comparison with the discrete-timesubgradient algorithms. Future work is to extend the eFTP for non-stationary, closed and convex sets.
About KSRA
The Kavian Scientific Research Association (KSRA) is a non-profit research organization to provide research / educational services in December 2013. The members of the community had formed a virtual group on the Viber social network. The core of the Kavian Scientific Association was formed with these members as founders. These individuals, led by Professor Siavosh Kaviani, decided to launch a scientific / research association with an emphasis on education.
KSRA research association, as a non-profit research firm, is committed to providing research services in the field of knowledge. The main beneficiaries of this association are public or private knowledge-based companies, students, researchers, researchers, professors, universities, and industrial and semi-industrial centers around the world.
Our main services Based on Education for all Spectrum people in the world. We want to make an integration between researches and educations. We believe education is the main right of Human beings. So our services should be concentrated on inclusive education.
The KSRA team partners with local under-served communities around the world to improve the access to and quality of knowledge based on education, amplify and augment learning programs where they exist, and create new opportunities for e-learning where traditional education systems are lacking or non-existent.
FULL Paper PDF file:
Non-smooth Projected Primal-Dual DynamicalApproach to Solve the Extended Fermat-TorricelliProblemBibliography
author
Year
2021
Title
Non-smooth Projected Primal-Dual DynamicalApproach to Solve the Extended Fermat-TorricelliProblem
Publish in
in IEEE Control Systems Letters, vol. 5, no. 3, pp. 1109-1114, July 2021,
Doi
10.1109/LCSYS.2020.3006822.
PDF reference and original file: Click here
Somayeh Nosrati was born in 1982 in Tehran. She holds a Master's degree in artificial intelligence from Khatam University of Tehran.
Professor Siavosh Kaviani was born in 1961 in Tehran. He had a professorship. He holds a Ph.D. in Software Engineering from the QL University of Software Development Methodology and an honorary Ph.D. from the University of Chelsea.
Nasim Gazerani was born in 1983 in Arak. She holds a Master's degree in Software Engineering from UM University of Malaysia.
