Задача 3669 из Демидовича

[Verbery]

Здравствуйте! Возник вопрос по задаче 3669 из Демидовича с вот таким условием:
Найти минимум функции $u = \sum_{i=1}^n \frac{\alpha_i}{x_i}$, если $\sum_{i=1}^n \beta_i x_i = 1$ и $\alpha_i, \beta_i, x_i > 0$

Я не совсем понимаю как мне связать моё решение с ограничениями данными в задаче. Может ли кто подсказать? Я делаю вот так:
1) Составляю функцию Лагранжа
2) Чтобы найти стационарные точки, нахожу производную функции лагранжа, приравниваю к 0, получаю СЛУ:

$$\begin{equation} \left\{\begin{split} \frac{\alpha_1}{x_1^2} - \lambda \beta_1 = 0 \\ ... \\ \frac{\alpha_n}{x_n^2} - \lambda \beta_n = 0 \\ \end{split}\right.\end{equation}$$

(Я тут выкинул ограничения $\sum_{i=1}^n \beta_i x_i = 1$, чтобы составить характеристическое уравнение)
3) Перегруппируем строки СЛУ из п.2 так: $\frac{\alpha_i}{x_i^2 \beta_i} - \lambda = 0$
4) Заметим, что в п.3 можно найти $\frac{1}{x_i^2}$ с помощью характеристического уравнения относительно $(A - \lambda I)x=0$: $\prod\limits_{i = 1}^n (\frac{\alpha_i}{\beta_i} - \lambda) = 0$, его корни $\lambda = \frac{\alpha_i}{\beta_i}$
5) Подставляя каждое решение из п.4 в п.2 найдём: $x_j = \sqrt \frac{\alpha_i \beta_j}{\beta_i \alpha_j}$, как отсюда теперь отобрать те, что будут соответствовать $\sum_{i=1}^n \beta_i x_i = 1$? Или нужно идти совсем другим путём?

[Евгений Машеров]

До п.3 включительно всё так. Затем выражаем икс через альфа, бета, лямбда. Выписываем ограничение на взвешенную сумму иксов и рассматриваем, как уравнение для лямбды.

[Alex Krylov]

Причем, такая последовательность действий ("выразить $x$, подставить в ограничение, получить уравнение для множителя Лагранжа") носит универсальный характер. См. напр. "G.Golub, Matrix Computations, 12.1 Constrained Least squares". Голуб, кстати говоря, использует термин "секулярное уравнение" (синоним характеристического) в отношении подобных уравнений для множителя Лагранжа.

[Verbery]

Евгений Машеров в сообщении #1637543 писал(а):

До п.3 включительно всё так. Затем выражаем икс через альфа, бета, лямбда. Выписываем ограничение на взвешенную сумму иксов и рассматриваем, как уравнение для лямбды.

Спасибо! Сделал по вашему и мой ответ полностью совпал с тем, что дано в задачнике

[Alex Krylov]

Есть такая важная оптимизационная задача, как "задача квадратичного программирования с одним квадратичным ограничением в форме равенства", к которой многие вещи из области радиотехники, обработки сигналов итд сводятся:

$\min\limits_{x} \left\lbrace x^T A x-2b^Tx\right\rbrace, x^T B x = 1$
здесь $A,B$ - положительно определенные матрицы

И подход к ее решению тот же, что и выше.

Функция Лагранжа:
$L=x^T A x-2b^Tx - \lambda(x^T B x - 1)$

Условие равенства нулю частных производных:
$\left\{ \begin{array}{rcl} (A-\lambda B)x= b\\ x^T B x=1 \\ \end{array} \right.$

И далее надо выразить $x$ из первого равенства системы и подставить во 2-е. А для этого надо осуществить инверсию матрицы $A-\lambda B$ в явном виде

Пусть $B=C_B C_B$, где $C_B = C_B^T$, тогда
$(A-\lambda C_B C_B)x=C_B(C_B^{-1}AC_B^{-1}-\lambda E)C_B x=b$
Пусть $C_B^{-1}AC_B^{-1} = VDV^T$, тогда
$C_B(VDV^T-\lambda E)C_B x=C_B V(D-\lambda E)V^T C_B x = b$
$x = C_B^{-1}V(D-\lambda E)^{-1}V^T C_B^{-1}b$

После подстановки во 2-е равенство, имеем следующее секулярное уравнение для $\lambda$:
$b^TC_B^{-1}V(D-\lambda E)^{-2}V^T C_B^{-1}b=1$

[Alex Krylov]

В дополнение к сообщению выше...

При $b=0$ имеем $A x = \lambda B x$. Перед нами обобщенная задача на собственные значения. Решением оптимизационной задачи при $b=0$ является (обобщенный) собственный вектор, соответствующий минимальному собственному значению.

При $b=0$ исходная оптимизационная задача эквивалента задаче минимизации обобщенного отношения Рэлея: $\min\limits_{x\ne0} \frac{x^T A x}{x^T B x}$. Кстати, своего максимума отношение Рэлея достигает на собственном векторе (и любой его ненулевой масштабной копии), соответствующем максимальному собственному значению. Многие полезные характеристики качества могут естественным образом быть сформулированы в виде отошения двух квадратичных форм: отношение "сигнал/шум", отношение пиковой энергии к интегральному уровню боковых лепестков, отношение квадрата крутизны дискриминационной характеристики частотного дискриминатора к дисперсии шумовой компоненты ошибки на выходе (https://dxdy.ru/topic155367-90.html) итд.

[Verbery]

Alex Krylov
Спасибо! Интересно

[Alex Krylov]

Тут еще вот что можно сказать... Когда речь идет о радиотехнических приложениях, то, как известно, основная форма представления низкочастотного сигнала - это комплекснозначное представление (baseband signal в англоязычной литературе).

И соответственно аргументами оптимизируемых целевых функций при этом являются комплекснозначные величины - комплекснозначные векторы (а в примере выше обычные квадратичные формы заменяются эрмитовыми квадратичными формами). Естественно, что при этом сама целевая функция по прежнему остается вещественнозначной! Т.е. перед нами вещественнозначная функция комплекснозначного аргумента: $\mathbb{C}^n\to\mathbb{R}$. Но эту функцию можно рассматривать и как вещественнозначную функцию вещественнозначных аргументов - вещественных и мнимых частей изначального комплекснозначного вектора: $\mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}$. Ограничения могут быть тоже изначально сформулированы в комплекснозначном виде. И естественно одно комплекснозначное ограничение эквивалентно двум вещественнозначным (относительно мнимых и вещественных частей исходного). Т.е. надо понимать, что оптимизационная задача, в которой фигурируют комлекснозначные аргументы и комплекснозначные ограничения - это на самом деле оптимизационная задача с вещественнозначными аргументами и вещественнозначными ограничениямми! Однако!!!! Однако, ввиду удобства целесообразней все же работать с комплекснозначными агрументами и ограничениями (помня, что на самом деле речь идет о вещественнозначных аргументах и ограничениях)! Для этого необходимо выработать некий ФОРМАЛИЗМ, который бы делал комплекснозначное представление (и все манипуляции с комплекснозначными величинами) эквивалентным вещественнозначному. Этот формализм естественно уже давно выработан и состоит из двух ингредиентов:
1) Исчисление Виртингера [1]
2) Небольшая модификация в методе множителей Лагранжа для инкорпорирования (корректным образом) комплекснозначных ограничений.

Целевая функция, будучи вещественнозначной функцией комплекснозначного аргумента, является функцией НЕГОЛОМОРФНОЙ, т.е. в смысле Коши-Римана недифференцируемой, т.е. обычная "комплексная производная" тут вообще не имеет никакого смысла. А если целевую функцию рассматривать, как вещественнозначную функцию вещественнозначных аргументов (вещественных и мнимых частей) и дифференцировать по ним (по вещественным и мнимым частям), то такие производные имеют обычный смысл (смысл обычных частных производных). Так вот, исчисление Виртингера - это по сути формализм, позволяющий (формальным образом) вычислять эти обычные частные производные (по вещественным и мнимым частям), но при этом оставаясь в рамках удобного комплекснозначного представления и оперируя комплекснозначными аргументами. Если $z=x+j y$ и имеется функция $f(z)=f(z,\bar{z})=f(x,y)$, то пара производных Виртингера $\frac{\partial f}{\partial z}, \frac{\partial f}{\partial \bar{z}}$ определяется следующим образом:
$\frac{\partial f}{\partial z}=\left.\frac{\partial f(z,\bar{z})}{\partial z}\right|_{\bar{z}=\operatorname{const}}=\frac{1}{2}(\frac{\partial f(x,y)}{\partial x} - j \frac{\partial f(x,y)}{\partial y})$
$\frac{\partial f}{\partial \bar{z}}=\left.\frac{\partial f(z,\bar{z})}{\partial \bar{z}}\right|_{z=\operatorname{const}}=\frac{1}{2}(\frac{\partial f(x,y)}{\partial x} + j \frac{\partial f(x,y)}{\partial y})$
Обратите внимание, как связаны обычные частные производные, берущиеся по вещественной и мнимой частям, с производными Виртингера. Для многомерного случая все аналогично. И что еще из всего этого следует? А следует из всего сказанного то, что НЕОБХОДИМОЕ УСЛОВИЕ ЛОКАЛЬНОГО ЭКСТРЕМУМА может быть записано как равенство нулю одной из двух (любой на выбор) производных Виртингера! В многомерном случае - одного из двух градиентов (на выбор). Но обычно предпочитают $\frac{\partial f}{\partial \bar{z}}=0 \Leftrightarrow \left\lbrace \frac{\partial f(x,y)}{\partial x} =0, \frac{\partial f(x,y)}{\partial y} =0 \right\rbrace$, чтобы иметь в итоге дело с выражениями относительно обычных $z$, а не комплексно сопряженных $\bar{z}$ величин.

Пример

Если $f(z,\bar{z})=z\bar{z}$, то для (формального) вычисления $\frac{\partial f}{\partial z}$ переменная $\bar{z}$ принимается константой, не зависящей от $z$, и дальше производная вычисляется по обычным правилам (как будто $z$ обычная вещественная переменная): $\frac{\partial f}{\partial z}=\bar{z}$. Аналогично $\frac{\partial f}{\partial \bar{z}}=z$. В этом и состоит суть и удобство формализма.

Осталось слегка модифицировать метод множителей Лагранжа. Рассмотрим для примера оптимизационную задачу с одним комплекснозначным ограничением: $\min\limits_{}f(z), c(z)=0, z\in \mathbb{C}^n; f(z)\in\mathbb{R}, c(z)\in \mathbb{C}$

C учетом того, что одно комплекснозначное ограничение эквивалентно двум вещественным, (стандартная) функция Лагранжа запишется в виде: $L(z)=L(x,y)=f(z)-\lambda_1 Re(c(z)) - \lambda_2 Im(c(z))=f(z)-Re(\bar{\lambda} c(z))=$
$=f(z)-\frac{1}{2}(\bar{\lambda} c(z)+\lambda \overline{c(z)})$, где $\lambda=\lambda_1+j\lambda_2$
В последней строке множитель $1/2$ можно запихнуть в $\lambda$, т.е. в итоге иметь дело с выражениями вида $L(z)=L(x,y)=f(z)-\bar{\lambda} c(z)-\lambda \overline{c(z)}$, но это как говорится "на вкус и цвет". Собственно говоря, мы привели функцию Лагранжа к виду, пригодному для применения исчисления Виртингера и записи необходимых условий экстремума:
$\left\{ \begin{array}{rcl} \frac{\partial L}{\partial \bar{z}}=0\\ \\ \frac{\partial L}{\partial \overline{\lambda}}=0 \\ \end{array} \right. $
В случае нескольких ограничений все аналогично!

1. Ken Kreutz-Delgado
The Complex Gradient Operator and the CR-Calculus
https://arxiv.org/abs/0906.4835