Метод еліпсоїдів для мінімізації опуклої функції
Loading...
Date
2019
Authors
Стецюк, Петро
Фішер, Андреас
Ляшко, Володимир
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Розглянуто метод еліпсоїдів та його застосування для знаходження наближення до точки мінімуму опуклої функції: критерій зупинки гарантує знаходження такої точки, в якій значення функції відрізняється від мінімального не більше, ніж на задану достатньо малу величину. Метод є частковим випадком субградієнтних методів із розтягом простору в напрямку субградієнта з коефіцієнтом, який залежить тільки від вимірності простору змінних. Він може бути використаний для мінімізації гладких та негладких опуклих функцій від декількох десятків змінних.
We consider the generalized ellipsoid method – an algorithm with the space dilation. For a certain choice of the dilation coefficient, this is a method of outer approximation of semi-ellipsoids by ellipsoids with a monotonous decrease in their volume. The Yudin-Nemirovski-Shor ellipsoid method is a specific case. The paper provides properties of two algorithmic realizations of the generalized ellipsoid method. The first algorithm is based on updating nonsymmetric matrix B, as in the Shor ellipsoid method, and the second is based on updating symmetric matrix H = BBT, as in the Yudin-Nemirovski ellipsoid method We present the Emshor algorithm (Ellipsoid Method of Shor) for computing a solution of the problem of unconstrained minimization of a convex function. It updates nonsymmetric matrix B and uses a stopping criterion that, for a convex function, guarantees to find a point at which the function value does not deviate more than a specified tolerance from the optimal function value. It is shown that the Emshor algorithm finds sufficiently accurate approximations to the minimum point of a ravine convex function, and for functions of twenty variables it takes no longer than a few seconds on a usual PC. Hence, the algorithm can be useful for solving small optimization problems The Emshor algorithm is planned to be used to develop a dual method for solving a two-stage transportation problem, when the number of intermediate points is not greater than twenty. The computational complexity of the dual method is determined by the complexity of calculating the value of the dual function and its supergradient, for which we need not more than twenty times to find the minimum elements in two one-dimensional arrays whose lengths m and n correspond to the numbers of suppliers and consumers. This means that the dual method can be oriented to the case of large m and n (thousands, tens of thousands), for which solving linear programming problems corresponding to the two-stage transportation problem by general-purpose programs is impossible or requires significant computational resources.
We consider the generalized ellipsoid method – an algorithm with the space dilation. For a certain choice of the dilation coefficient, this is a method of outer approximation of semi-ellipsoids by ellipsoids with a monotonous decrease in their volume. The Yudin-Nemirovski-Shor ellipsoid method is a specific case. The paper provides properties of two algorithmic realizations of the generalized ellipsoid method. The first algorithm is based on updating nonsymmetric matrix B, as in the Shor ellipsoid method, and the second is based on updating symmetric matrix H = BBT, as in the Yudin-Nemirovski ellipsoid method We present the Emshor algorithm (Ellipsoid Method of Shor) for computing a solution of the problem of unconstrained minimization of a convex function. It updates nonsymmetric matrix B and uses a stopping criterion that, for a convex function, guarantees to find a point at which the function value does not deviate more than a specified tolerance from the optimal function value. It is shown that the Emshor algorithm finds sufficiently accurate approximations to the minimum point of a ravine convex function, and for functions of twenty variables it takes no longer than a few seconds on a usual PC. Hence, the algorithm can be useful for solving small optimization problems The Emshor algorithm is planned to be used to develop a dual method for solving a two-stage transportation problem, when the number of intermediate points is not greater than twenty. The computational complexity of the dual method is determined by the complexity of calculating the value of the dual function and its supergradient, for which we need not more than twenty times to find the minimum elements in two one-dimensional arrays whose lengths m and n correspond to the numbers of suppliers and consumers. This means that the dual method can be oriented to the case of large m and n (thousands, tens of thousands), for which solving linear programming problems corresponding to the two-stage transportation problem by general-purpose programs is impossible or requires significant computational resources.
Description
Keywords
метод еліпсоїдів, перетворення простору, коефіцієнт розтягу простору, опукла функція, субградієнт, яружна негладка функція, стаття, ellipsoid method, space transformation, coefficient of space dilation, convex function, subgradient, ravine non-smooth function, article
Citation
Стецюк П. І. Метод еліпсоїдів для мінімізації опуклої функції / Стецюк П. І., Фішер А., Ляшко В. І. // Наукові записки НаУКМА. Комп'ютерні науки. - 2019. - Т. 2. - С. 16-21.