Метод еліпсоїдів для мінімізації опуклої функції

Simple item page
dc.contributor.authorСтецюк, Петро
dc.contributor.authorФішер, Андреас
dc.contributor.authorЛяшко, Володимир
dc.date.accessioned2019-12-04T23:58:20Z
dc.date.available2019-12-04T23:58:20Z
dc.date.issued2019
dc.description.abstractРозглянуто метод еліпсоїдів та його застосування для знаходження наближення до точки мінімуму опуклої функції: критерій зупинки гарантує знаходження такої точки, в якій значення функції відрізняється від мінімального не більше, ніж на задану достатньо малу величину. Метод є частковим випадком субградієнтних методів із розтягом простору в напрямку субградієнта з коефіцієнтом, який залежить тільки від вимірності простору змінних. Він може бути використаний для мінімізації гладких та негладких опуклих функцій від декількох десятків змінних.uk_UA
dc.description.abstractWe 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.en_US
dc.identifier.citationСтецюк П. І. Метод еліпсоїдів для мінімізації опуклої функції / Стецюк П. І., Фішер А., Ляшко В. І. // Наукові записки НаУКМА. Комп'ютерні науки. - 2019. - Т. 2. - С. 16-21.uk_UA
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/16710
dc.language.isoukuk_UA
dc.relation.sourceНаукові записки НаУКМА. Комп'ютерні наукиuk_UA
dc.statusfirst publisheduk_UA
dc.subjectметод еліпсоїдівuk_UA
dc.subjectперетворення просторуuk_UA
dc.subjectкоефіцієнт розтягу просторуuk_UA
dc.subjectопукла функціяuk_UA
dc.subjectсубградієнтuk_UA
dc.subjectяружна негладка функціяuk_UA
dc.subjectстаттяuk_UA
dc.subjectellipsoid methoden_US
dc.subjectspace transformationen_US
dc.subjectcoefficient of space dilationen_US
dc.subjectconvex functionen_US
dc.subjectsubgradienten_US
dc.subjectravine non-smooth functionen_US
dc.subjectarticleen_US
dc.titleМетод еліпсоїдів для мінімізації опуклої функціїuk_UA
dc.title.alternativeAn ellipsoid method for minimization of convex functionen_US
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Metod_elipsoidiv_dlia_minimizatsii_opukloi_funktsii.pdf
Size:
482.47 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 2