Опукле продовження кубічних многочленів на переставленнях та його застосування у розв’язанні практичних задач оптимізації

Abstract

Представлено два методи побудови опуклого продовження кубічного многочлена на переставленнях — один метод аналітичний, другий — ітераційний, який є модифікацією метода Стояна-Яковлева побудови опуклих продовжень многочленів на вершинно розташованих множинах. Продемонстровано переваги аналітичного методу — можливість записати шукане опукле продовження в явному вигляді, використовуючи коефіцієнти вихідної функції й мультимножину, з якої формуються переставлення, а також суттєве зменшення кількості доданків у результуючому виразі порівняно з ітераційним методом. Побудова опуклих продовжень многочленів дозволяє використовувати апарат опуклого програмування для розв'язування практичних задач, що формулюються в вигляді оптимізаційних із поліноміальною цільовою функцією на переставленнях.

Two methods of constructing convex extension of cubic polynomials on permutations are presented. One of them is analytical method and the second iterative method is a modification of Stoyan-Yakovlev’s method of constructing convex extension of polynomials given on sets located in vertices. The advantages of the analytical method, such as the method make it possible to write the convex extension in the explicit form in terms of target function coefficients and multisets elements as well as essential reducing amount of items in resulting expression compare with the iterative method, is demonstrated. Constructing convex extension of polynomials allows to use convex programming for solving practical problems, formulated as optimization problems with polynomial target function on permutations.