УказательРазделыОбозначенияАвторО проекте


!

Настоящий раздел очень «сырой»: он был создан в проекте чуть ли не первым, когда еще не было понятно, как организовать наполнение ресурса информацией. Оставил его в исходном виде — как памятник собственным неудачам; для переделки еще очень долго идти…


Полиномиальная оптимизация

Найти

\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] (т.е. полиномы с вещественными коэффициентами от X=(x_1,\dots,x_n)).

Линейный случай

В частном случае, когда минимизируемая функция F(X), а также каждое ограничение, накладываемое системой неравенств, являются линейными по X функциями, рассматриваемую оптимизационную задачу называют задачей линейного программирования (не совсем удачный перевод английского выражения linear programming1)). Основоположником теории линейного программирования считается лауреат Нобелевской премии, академик Л.В.Канторович.

П

Пример. Предприятие выпускает 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)однородный полином (форма) порядка 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 – положительными. В дальнейшем это и будем предполагать.

Знакоопределенность квадратичной формы: критерий Сильвестра

§

Более подробное изложение материалов пункта ☞ ЗДЕСЬ.

Т

Теорема. Квадратичная форма

\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}

будет положительно определенной тогда и только тогда, когда все главные миноры ее матрицы положительны:

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) не имеет вещественных корней.

Последнее условие легко проверяется с помощью теоремы Якоби. Вычислим субдискриминанты полинома 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}число перемен знака в соответствующей последовательности.

П

Пример. Условия положительной определенности биквадратной формы

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ЗДЕСЬ.

Случай трех переменных




Статья не закончена!







П

Пример. Условия положительной определенности биквадратной формы

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_{}. Кривая 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} знакопостоянна, но не знакоопределенна ☞ ЗДЕСЬ

Глобальный максимум полинома




Статья не закончена!







П

Пример. Найти максимум полинома 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.
1) Не имеющий ничего общего с программированием в обычном понимании этого слова!

2016/09/08 09:59 редактировал au