==Полиномиальная оптимизация== ~~TOC~~ Настоящий раздел очень "сырой": он был создан в проекте чуть ли не первым, когда еще не было понятно, как организовать наполнение ресурса информацией. Оставил его в исходном виде --- как памятник собственным неудачам; для переделки еще очень долго идти... Найти $$ \max_{\mathbb S} F(X) $$ где множество $ {\mathbb S} \subset {\mathbb R}^n $ определяется как множество решений системы неравенств $$ g_1(X) \ge 0, \dots, g_K(X) \ge 0 \ . $$ Здесь $ \{F(X), g_1(X), \dots, g_K(X) \} \subset {\mathbb R}[X] $ (т.е. ((:polynomialm полиномы)) с вещественными коэффициентами от $ X=(x_1,\dots,x_n) $). ===Линейный случай == В частном случае, когда минимизируемая функция $ F(X) $, а также каждое ограничение, накладываемое системой неравенств, являются линейными по $ X $ функциями, рассматриваемую оптимизационную задачу называют задачей **линейного программирования** (не совсем удачный перевод английского выражения //linear programming//[[Не имеющий ничего общего с программированием в обычном понимании этого слова!]]). Основоположником теории линейного программирования считается лауреат Нобелевской премии, академик ((http://ru.wikipedia.org/wiki/Канторович,_Леонид_Витальевич Л.В.Канторович)). !!П!! **Пример.** Предприятие выпускает $ n $ видов продукции с использованием $ m $ видов ресурсов. На производство $ k $-го вида продукции требуется $ a_{1k} $ единиц первого ресурса, $ a_{2k} $ единиц второго ресурса, и т.д., $ a_{mk} $ единиц $ m $-го ресурса. Заданы предельные объемы $ b_1, \dots, b_m $ расхода каждого ресурса и величины прибылей $ c_1,\dots,c_n $ от продаж каждого вида продукции. Требуется указать сколько продукции какого вида следует выпустить для получения максимальной прибыли. Если предприятие произведет $ x_k $ единиц продукции $ k $-го вида, то оно израсходует $$ a_{j1}x_1+\dots + a_{jn} x_n $$ единиц $ j $-го ресурса. Этот расход не должен превышать предельно возможного расхода $ b_j $: $$ a_{j1}x_1+\dots + a_{jn} x_n \le b_j \ npu \ j\in \{1,\dots, m \} \ . $$ Общая прибыль от выпуска всей продукции будет равна $$ F(X)=c_1x_1+\dots + c_n x_n \ . $$ Требуется подобрать __неотрицательные__ величины $ x_1,\dots, x_n $, удовлетворяющие заданной системе линейных неравенств и обеспечивающие максимальное значение функции прибыли $ F(X) $. >**Источник.** \\ > **Канторович Л.В.** //Математические методы организации и планирования производства//. Л. Изд-во ЛГУ, 1959 \\ >**Беклемишев Д.В.** //Дополнительные главы линейной алгебры.// М.Наука. 1983 !!П!! **Пример.** На железнодорожных станциях отправления $ A_1 $ и $ A_2 $ находятся соответственно 20 и 30 одинаковых единиц груза. Этот груз следует доставить на три станции назначения $ B_1, B_2 $ и $ B_3 $, причем в каждый из них должно быть завезено соответственно 5, 30 и 15 единиц груза. Известны стоимости $ c_{jk} $ перевозки груза из пункта $ A_j $ в пункт $ B_k $: $$ c_{11}=4, \ c_{12}=9,\ c_{13}=3, $$ $$ c_{21}=4, \ c_{22}=8,\ c_{23}=1. $$ Пусть $ x_{jk} $ означает количество единиц груза, предназначенного к отправке со станции $ A_j $ на станцию $ B_k $. При каких значениях $ x_{jk} $ общая стоимость перевозок груза будет наименьшей? **Решение.** Задача сводится к нахождению такого решения системы линейных уравнений $$ \left\{\begin{array}{lcl} x_{11}+x_{21} & = & 5, \\ x_{12}+x_{22} & = & 30, \\ x_{13}+x_{23} & = & 15, \\ x_{11}+x_{12}+x_{13} & = & 20, \\ x_{21}+x_{22}+x_{23} & = & 30 \end{array} \right. $$ с неотрицательными значениями переменных, при которых функция $$ F=4x_{11}+9x_{12}+3x_{13}+4x_{21}+8x_{22}+x_{23} $$ принимает минимальное значение. Система линейных уравнений является неопределенной с общим решением, содеращим 2 основные переменные. Выберем в качестве этих основных переменных $ x_{13} $ и $ x_{21} $, тогда общее решение системы имеет вид: $$ x_{11}=5-x_{21},\ x_{12}=15-x_{13}+x_{21},\ x_{22}=15+x_{13}-x_{21},\ x_{23}=15-x_{13} \ . $$ Подставляем эти выражения в функцию $ F $: $$ F=290+x_{13}+x_{21} \ . $$ По условию задачи переменные $ x_{13} $ и $ x_{21} $ неотрицательны. Понятно, что $ \min F $ достигается при $ x_{13}=0, x_{21}=0 $. **Ответ.** $ x_{11}=5, x_{12}=15, x_{13}=0, x_{21}=0, x_{22}=15, x_{23}=15 $. >**Источник.** Пример взят из \\ > **Окунев Л.Я.** //Сборник задач по высшей алгебре.// М. Просвещение. 1964 **Каноническая форма задачи линейного программирования** : найти $$ \max (c_1x_1+\dots+c_nx_n) $$ при всевозможных **неотрицательных** значениях переменных $ x_1,\dots,x_n $, удовлетворяющих системе уравнений $$ \left\{ \begin{array}{lllll} a_{11}x_1 &+a_{12}x_2&+ \ldots&+a_{1n}x_n &=b_1,\\ a_{21}x_1 &+a_{22}x_2&+ \ldots&+a_{2n}x_n &=b_2,\\ \dots & & & \dots & \\ a_{m1}x_1 &+a_{m2}x_2&+ \ldots&+a_{mn}x_n &=b_m. \end{array} \right. $$ Геометрически, область допустимых значений $ x_1,\dots,x_n $, определяемая этими условиями, представляет собой многогранник в пространстве $ \mathbb R^n $. !!!!! Идея решения задачи: экстремум линейной функции $$ F(X)= c_1x_1+\dots+c_nx_n $$ -- если существует -- то достигается на границе указанного многогранника, т.е., __как правило__, в его вершине, или в исключительных случаях -- на ребре или грани. Грубо говоря, для нахождения максимума функции $ F(X) $ достаточно перебрать все вершины многогранника и сравнить в них значения $ F(X) $. Однако, в практических приложениях количество переменных $ n $ и ограничений $ m $ может быть настолько велико, что простой перебор вершин многогранника не будет эффективен. Для более направленного перебора --- так, чтобы на каждом шаге переходить к новой вершине с увеличением значения $ F(X) $ придуман === Симплекс-метод == ===Условия знакоопределенности полиномов== Пусть область $ \mathbb{S} \subset \mathbb{R}^{n} $ содержит начало координат: $ \mathbb{O} \in \mathbb{S} $. Функция $ F_{}(X) $ называется **положительно** (**отрицательно**) **определенной в области** $ \mathbb{S}_{} $ если $ F(X)\ge 0 $ (соответственно $ F(X)\le 0 $) всюду в $ \mathbb{S}_{} $ и $ F_{}(X)=0 $ тогда и только тогда, когда $ X=\mathbb{O} $. При этом функцию $ F_{}(X) $ будем называть глобально положительной (отрицательной), если $ \mathbb{S}=\mathbb{R}^n $. Функция $ F_{}(X) $ называется **знакопостоянной** (положительной или отрицательной) если в области $ \mathbb{S}_{} $ она может принимать значения только одного определенного знака, и $ F(\mathbb{O})=0 $ (но $ F_{}(X) $ может обращаться в нуль и при $ X\ne \mathbb{O},X\in \mathbb{S} $). В дальнейшем мы рассматриваем в качестве функции $ F_{} $ __только полиномы__. !!П!! **Пример.** При $ n_{}=3 $ функция **а)** $ x_1^2+3\,x_2^2+4x_3^6 $ будет положительно определенной; **б)** $ x_1^2+x_3^2x_4^2 $ или $ (x_1+{\sqrt 2} x_2-x_3)^2 $ будет неотрицательной, но не положительно определенной; **в)** $ -x_1^2 $ будет неположительной, но не отрицательно определенной; **г)** $ -x_1^2-2x_2^2-4\,x_3^2 $ будет отрицательно определенной; **д)** $ x_1x_2+x_2x_3 $ будет неопределенной. !!Т!! **Теорема.** //Разложим полином// $ F(X) $ //по степеням переменных. Допустим, что в этом разложении минимальная степень мономов равна// $ m $, //так что можно записать// $$ F(X)=F_m(X)+F_*(X), $$ //Здесь// $ F_m(X) $ -- //((:polynomial#однородный_полином однородный полином)) (форма) порядка// $ m $, //а// $ F_*(X) $ -- //полином, содержащий мономы более высоких порядков. Тогда, если// $ F_m $ //есть форма знакоопределенная (-переменная), то и функция// $ F(X) $ //будет знакоопределенной (-переменной) в некоторой области// $ \mathbb{S} \subset \mathbb{R}^n $. В виду этой теоремы начнем с установления коэффициентного критерия знакоопределенности формы $ F_m(X) $. Заметим, что для формы свойство положительной (отрицательной) определенности в некоторой области $ \mathbb{S} $ эквивалентно глобальной положительности (отрицательности), т.к. $ F_m(cx_1,\dots,cx_n) \equiv c^m F_m(x_1,\dots,x_n) $. Поэтому слова "в некоторой области $ \mathbb{S} $" будем опускать. Без ограничения общности можно исследовать $ F_m(X) $ на положительную определенность (**п.о.**) Очевидно, что для того чтобы $ F_m(X) $ была п.о. необходимо чтобы ее степень $ m $ была четной, а коэффициенты всех мономов $ x_1^m,\dots,x_n^m $ -- положительными. В дальнейшем это и будем предполагать. ====Знакоопределенность квадратичной формы: критерий Сильвестра== !!§!! Более подробное изложение материалов пункта ☞ ((:2form ЗДЕСЬ)). !!Т!! **Теорема.** //Квадратичная форма// $$ \begin{array}{rllll} F_2(x_1,\dots,x_n)=&a_{11}x_1^2&+2a_{12}x_1x_2&+ \dots & +2a_{1n}x_1x_n+ \\ & &+a_{22}x_2^2 &+ \dots & +2a_{2n}x_2x_n+ \\ & &+\dots &+2a_{jk}x_jx_k & +\dots + \\ & & & &+a_{nn}x_n^2 \end{array} $$ //будет положительно определенной тогда и только тогда, когда все ((algebra2:dets#теорема_лапласа главные миноры)) ее матрицы положительны//: $$ a_{11}>0, \ \left| \begin{array}{cc} a_{11} & a_{12} \\ a_{12} & a_{22} \end{array} \right| >0, \ \left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{array} \right| >0, \dots, \det A >0 \ . $$ В этом случае будем также говорить о **положительной определенности матрицы** $ A_{} $. !!=>!! Квадратичная форма будет отрицательно определенной тогда и только тогда, когда знаки главных миноров ее матрицы будут чередоваться следующим образом: $$ a_{11}<0, \ \left| \begin{array}{cc} a_{11} & a_{12} \\ a_{12} & a_{22} \end{array} \right| >0, \ \left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{array} \right| <0, \dots, (-1)^n\det A >0 \ . $$ !!П!! **Пример.** Можно ли получить условия __неотрицательности__ квадратичной формы: $$ F_2(X) \ge 0 \ npu \ \forall X \in {\mathbb R}^n $$ превращением всех неравенств из критерий Сильвестра в нестрогие? --- Вообще говоря, нет. Квадратичная форма $$f(x_1,x_2,x_3,x_4)=x_1^2+2x_1x_3+2x_2x_4+x_4^2= X^{\top} \left( \begin{array}{cccc} 1&0&1 &0 \\ 0&0&0&1 \\ 1&0&0&0 \\ 0&1&0&1 \end{array} \right)X $$ -- неопределенная, т.к. $ f(1,0,-1,0)=-1_{}<0 $, а $ f(1,0,0,0)=1_{}>0 $. Тем не менее, все главные миноры ее матрицы неотрицательны. ♦ ====Знакоопределенность однородного полинома от двух переменных (бинарной формы) == !!Т!! **Теорема.** //Форма// $$ F_m(x_1,x_2)=A_0x_1^m+A_1x_1^{m-1}x_2+\dots+A_mx_2^m $$ //будет п.о. тогда и только тогда, когда// $ A_0>0, A_m>0 $, //а полином// $ f(z)\equiv F_m(z,1) $ //не имеет вещественных корней.// Последнее условие легко проверяется с помощью ((dets:discrim#вещественность_корней == теоремы Якоби)). Вычислим ((dets:discrim#субдискриминанты)) полинома $ f(z) $. !!Т!! **Теорема.** //Для того, чтобы полином // $ f(z) $ //четной степени// $ m $ //не имел вещественных и кратных корней// **a)** //необходимо, чтобы// $ (-1)^{m/2}{\mathcal D} (f) > 0 $; **b)** //достаточно, чтобы// $ {\mathcal V}(1,{\mathcal D}_{m-1},\dots,{\mathcal D}_0)=m/2 $. //Если же// $ {\mathcal D} (f) =0 $, //то для того чтобы// $ f(z) $ //был положителен при всех// $ z\in \mathbb{R} $ **c)** //необходимо, чтобы// $ {\mathcal D}_{1}=0 $; //а если// $ {\mathcal D}_0={\mathcal D}_{1}=\dots={\mathcal D}_{k-1}=0, {\mathcal D}_{k}\ne 0 $ то **d)** //необходимо, чтобы// $ k $ //было четным, а// $ (-1)^{k/2}{\mathcal D}_{k} >0 $; **e)** //достаточно, чтобы// $ {\mathcal V}(1,{\mathcal D}_{m-1},\dots,{\mathcal D}_k)=(m-k)/2 $. //Здесь// $ {\mathcal V} $ -- //число ((algebra2:notations#число знакопостоянств (знакоперемен) == перемен знака))// в //соответствующей последовательности//. !!П!! **Пример.** Условия положительной определенности биквадратной формы $$ F_4(x,y)=A_0x^4+A_1x^3y+A_2x^2y^2+A_3xy^3+A_4y^4 $$ Обозначим $$ S_2=3A_1^2-8A_0A_2,\ S_3=36I_3+2S_2I_2,\ S_4=4I_2^3-27I_3^2\, $$ Здесь $$ I_2=4A_0A_4-A_1A_3 +\frac{1}{3}A_2^2 \ , $$ $$ I_3=-A_0A_3^2-A_1^2A_4+\frac{8}{3}A_0A_2A_4+ \frac{1}{3}A_1A_2A_3-\frac{2}{27}A_2^3 \ . $$ !!Т!! **Теорема 1.** Форма $ F_4(x,y) $ положительно определена тогда и только тогда, когда $ A_0>0 $ и \\ a) при условии $ S_4>0 $ выполняется хотя бы одно из условий: $ S_2<0 $ или $ S_3<0 $ ; \\ б) при условии $ S_4=0 $ выполняются условия: $ S_3=0 $ и $ S_2<0 $. >**Источник.** Условия из теоремы 1 известны давно. Хороший обзор приведен в решении задачи E 2878 \\ >//When does a real quartic have no real zeros?// American Math.Monthly 1984. Vol. 91, № 3. !!§!! Cмысл выражений $ I_2 $ и $ I_3 $ ☞ ((((:algebra2:optimiz:invariant ЗДЕСЬ)). ====Случай трех переменных== {{users:au:scriber.jpg |}} \\ \\ \\ Статья не закончена! \\ \\ \\ \\ \\ \\ !!П!! **Пример.** Условия положительной определенности биквадратной формы $$ F_4(x_1,x_2,x_3)=x_1^4+x_2^4+x_3^4+\zeta x_1^2x_2x_3+\eta x_1x_2^2x_3 \ . $$ Обозначим $$ H_5=2^{16}(A+B-64)^4 - $$ $$ - AB[(A+B-512)^3-(A+B+256)((A+B-93056)^2-27AB-8755167232)]. $$ Здесь $ A=\zeta^4,\ B=\eta^4 $. Форма $ F_{4}(x_1,x_2,x_3) $ положительно определена тогда и только тогда, когда $ H_{5}>0 $ и $ A+B <64_{} $. {{ algebra2:sign_def1.png |}} Кривая $ H_5(A,B)=0 $ касается осей $ A=0 $ и $ B=0 $ в точках $ (0,64) $ и $ (64,0) $ соответственно. В частном случае $ A=B_{} \ (\zeta=\pm \eta) $, условие положительной определенности формы $$ F_4(x_1,x_2,x_3)=x_1^4+x_2^4+x_3^4+\zeta (x_1^2x_2x_3 \pm x_1x_2^2x_3) $$ заключается в выполнении неравенства $$ |\zeta| < 4/ \sqrt[4]{54} \approx 1.475575\ . $$ В частном случае $ B=0 \ (\eta=0)_{} $, условие положительной определенности формы $$ F_4(x_1,x_2,x_3)=x_1^4+x_2^4+x_3^4+\zeta x_1^2x_2x_3 $$ заключается в выполнении неравенства $ |\zeta| < 2\sqrt{2}_{} $. >**Источник.** \\ > **Утешев А.Ю.** //Использование символьных методов локализации решений для анализа полиномиальных систем//. Диссертация на соискание ученой степени доктора физ.-мат. наук. СПб.1998 !!§!! Критический случай: форма $ F_{m} $ знакопостоянна, но не знакоопределенна ☞ ((:algebra2:optimiz:sd_cr ЗДЕСЬ)) == Глобальный максимум полинома == {{users:au:scriber.jpg |}} \\ \\ \\ Статья не закончена! \\ \\ \\ \\ \\ \\ !!П!! **Пример.** Найти максимум полинома $$ F(x,y) = $$ $$ =-x^4+8\,x^3 y - 24\,x^2 y^2 +24\,x y^3 - 8\,y^4 -\frac{4}{3}\,x^3 - 8\,x^2 y +24\,x y^2- \frac{56}{3}\,y^3 + 10\,x^2 + 16\,x y + 60\,x + 32\,y \ . $$ **Решение.** Максимум $ F(x,y) $ совпадает с максимальным положительным корнем полинома $$ \begin{matrix} \mathcal F (z) &= & - 2460375\, z^9 + 13046305743\, z^8 - 20953332885564\, z^7 + 10858379628617100\, z^6-\\ &&- 1199221437495632850\, z^5 - 369773782407882562734\, z^4 + 33574934405487787787124\, z^3 + \\ &&+8363310121361184850064700\, z^2 + 438702308762940646094396529\, z + 6672685776490188470056561943. \end{matrix} $$ **Ответ.** $ \max F=2797.86763 \pm 10^{-5} $. Координаты соответствующей стационарной точки $$ (-8.07285 \pm 10^{-5}, -11.50294 \pm 10^{-5}). $$ ==Источники== **Uteshev A.Yu., Cherkasov T.M.** //The search for the maximum of a polynomial.// J. Symbolic Computation. 1998. Vol. 25, N 5. P. 587-618.