TY - JOUR

T1 - Charged ball method for solving some computational geometry problems

AU - Abbasov, M. E.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - The concept of replacement of the initial stationary optimization problem with some nonstationary mechanical system tending with time to the position of equilibrium, which coincides with the solution of the initial problem, makes it possible to construct effective numerical algorithms. First, differential equations of the movement should be derived. Then we pass to the difference scheme and define the iteration algorithm. There is a wide class of optimization methods constructed in such a way. One of the most known representatives of this class is the heavy ball method. As a rule, such type of algorithms includes parameters that highly affect the convergence rate. In this paper, the charged ball method, belonging to this class, is proposed and investigated. It is a new effective optimization method that allows solving some computational geometry problems. A problem of orthogonal projection of a point onto a convex closed set with a smooth boundary and the problem of finding the minimum distance between two such sets are considered in detail. The convergence theorems are proved, and the estimates for the convergence rate are found. Numerical examples illustrating the work of the proposed algorithms are given.

AB - The concept of replacement of the initial stationary optimization problem with some nonstationary mechanical system tending with time to the position of equilibrium, which coincides with the solution of the initial problem, makes it possible to construct effective numerical algorithms. First, differential equations of the movement should be derived. Then we pass to the difference scheme and define the iteration algorithm. There is a wide class of optimization methods constructed in such a way. One of the most known representatives of this class is the heavy ball method. As a rule, such type of algorithms includes parameters that highly affect the convergence rate. In this paper, the charged ball method, belonging to this class, is proposed and investigated. It is a new effective optimization method that allows solving some computational geometry problems. A problem of orthogonal projection of a point onto a convex closed set with a smooth boundary and the problem of finding the minimum distance between two such sets are considered in detail. The convergence theorems are proved, and the estimates for the convergence rate are found. Numerical examples illustrating the work of the proposed algorithms are given.

KW - charged ball method

KW - computational geometry

KW - convex optimization

KW - minimal distance

UR - http://www.scopus.com/inward/record.url?scp=85029174509&partnerID=8YFLogxK

U2 - 10.3103/S1063454117030025

DO - 10.3103/S1063454117030025

M3 - Article

AN - SCOPUS:85029174509

VL - 50

SP - 209

EP - 216

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 3

ER -