Упростить минимизацию с несколькими Лагранж коэффициентами

[ilghiz]

Добрый день,

где-то когда-то видел, но запамятовал как правильно решать такие задачи, а именно

$$\min_{x,y, ||x||_2=1, ||y||_2=1, x^T y = 0} x^T A x + 2 x^T B y + y^T C y, ~~ A, B, C \in \R^{N \times N}, ~~ A = A^T, ~~ C = C^T, ~~ x,y \in \R^N$$

Особенно интересует решение для $n=3$, хотя как я помню, задача должна сводиться к задаче на собственные значения какой-то расширенной матрицы, но я совсем запамятовал какой именно.

Понятно можно ввести три Лагранжевых множителя и получить какую-то довольно "кривую" линейную задачу с тремя Лагранжевыми множителями.

Для случая $n=3$ оба неизвестных вектора можно выразить через тригонометрические функции, чтобы условия выполнялись автоматически, но тогда сама минимизация будет довольно громоздкой и очень не тривиальной и нет понимания на сколько хорошо оно будет сходиться.

ИМХО, вроде был какой-то метод сведения нескольких Лагранжевых множителей в один с повышением размерности матрицы задачи на собственные значения, но я подзабыл как это делалось. Вдруг кто помнит, пожалуйста, напомните!

Спасибо!

[alcoholist]

Функция Лагранжа

$$L(x,y,a,b,c)= x^T A x + 2 x^T B y + y^T C y-2a\left(x^Tx-1\right)-2c\left(y^Ty-1\right)-2bx^Ty.$$

И вперед, решаем систему из пяти уравнений.

[svv]

ilghiz в сообщении #1562011 писал(а):

задача должна сводиться к задаче на собственные значения какой-то расширенной матрицы, но я совсем запамятовал какой именно

Чтобы совсем сводилась — у меня не получается, но это примерно так.

Поскольку $x^TBy$ — это просто число, то
$x^TBy=(x^TBy)^T=y^TB^Tx$
Введём вектор $z\in\mathbb R^{2N}$ и матрицу $Q\in\mathbb R^{2N\times 2N}$ по формулам
$z=\begin{bmatrix}x\\y\end{bmatrix}, \quad Q=\begin{bmatrix}A&B\\B^T&C\end{bmatrix}$
Тогда

$$x^T A x + 2 x^T B y + y^T C y=x^TAx+x^TBy+y^TB^Tx+y^TCy = \begin{bmatrix}x^T&y^T\end{bmatrix} \begin{bmatrix}A&B\\B^T&C\end{bmatrix} \begin{bmatrix}x\\y\end{bmatrix} = z^TQz$$

Более того,
$z^Tz= \begin{bmatrix}x^T&y^T\end{bmatrix} \begin{bmatrix}x\\y\end{bmatrix}=x^Tx+y^Ty=2$

Получается, надо искать минимум $z^TQz$ при условии $z^Tz=2$. Такая задача действительно сводилась бы к задаче на собственные значения симметричной матрицы $Q$. К сожалению, есть ещё условие $x^Ty=0$, которое портит картину.

-- Вс авг 07, 2022 19:26:32 --

Уточнение: из условия $x^Tx=1 \wedge y^Ty=1$ следует $z^Tz=x^Tx+y^Ty=2$, но не наоборот. Поэтому из условий $x^Tx=1, y^Ty=1, z^Tz=2$ надо взять любые два.

[ilghiz]

Спасибо большое, alcoholist и svv за ответы!!!

Тут просто свести к Лагранжу, ИМХО, очень не правильно, так как сходимость такой минимизации будет совсем не предсказуемой, лагранжевы множители могут быть очень разных порядков, как друг с другом, так и со значением самого решения, и все будет идти юзом и плохо сходиться. Более того, у задачи ИМХО, много локальных минимумов, и имеется вероятность сесть в какой-то локальный минимум и не оценить есть ли другой, более низкий по значению минимум.

Схлопнуть в один вектор $x$ и $y$, как предлагает svv, ИМХО, тоже не факт, что хорошо, так как и условие их ортогональности портит картину, и найденный минимум не факт, что даст равнозначные нормы $x$ и $y$.

Пока была идея разложить $A=Q_A^T D_A Q_A$, $A=Q_C^T D_C Q_C$, так, что $D_A$ и $D_C$ - диагональные (на диагонали соответствующие собственные значения), а $Q_A$ и $Q_C$ - матрицы собственных векторов, тогда исходную задачу можно переписать в виде

$$\min_{\tilde x, \tilde y, ||\tilde x||_2=1, ||\tilde y||_2=1, \tilde x^T \tilde y=0} \tilde x^T D_A \tilde x + \tilde y^T D_C \tilde y + \tilde x^T \tilde B \tilde y,$$

где $\tilde B = Q_A^T B Q_C,$ но пока это не сильно добавляет оптимизма.

Для задачи $N=2$ исходная задача сводится к задаче на собственные значения для матрицы $2 \times 2$ (я уверен в этом факте, но не уверен в правильности получения матрицы, поэтому ее не привожу здесь).

Для задачи $N=3$ есть подозрение, что будет все так же, только размер матрицы, будет больше трех, но строгого доказательства у меня пока нет.

На данный момент я попробовал пооптимизировать задачу с $N=3$ и гарантированно нахожу три локальных минимума (а сколько реально их там - оценить сложно), и лагранжева минимизация в лоб сходится просто ужасно. Лучше всего сходимость наблюдается, если в качестве варьируемых параметров взять все координаты из $x$ и $y$ и перед вычислением функции на их основе их нормировать и друг к другу ортогонализировать.

Еще для случая $N=3$ видится вариант, когда $x$ фиксируем, и решаем по $y$, в этом случае задача будет одномерной, но как-то формулы получаются многоэтажные, что оценить сколько для фиксированного значения $x$ будет минимумов не получается. Если бы там был бы всегда один минимум и аналитическое решение, то по крайней мере, можно было бы его туда подставить, и попытаться все переформулировать для $x$, с надеждой на то, что получится полиномиальная задача на собственные значения, но, ИМХО, должно быть решение красивей.

[Doctor Boom]

svv в сообщении #1562049 писал(а):

Уточнение: из условия $x^Tx=1 \wedge y^Ty=1$ следует $z^Tz=x^Tx+y^Ty=2$, но не наоборот. Поэтому из условий $x^Tx=1, y^Ty=1, z^Tz=2$ надо взять любые два.

Полученные при этом минимумы будут минимумы исходной задачи, но не наоборот

[ilghiz]

Doctor Boom в сообщении #1562066 писал(а):

Полученные при этом минимумы будут минимумы исходной задачи, но не наоборот

тут ключевая проблема - не учет ортогональности векторов $x$ и $y$ друг к другу, из-за которой решения не будут, к сожалению, эквивалентны и сравнивать минимумы исходной задачи и такой, к сожалению, нельзя.

[Doctor Boom]

ilghiz в сообщении #1562069 писал(а):

тут ключевая проблема - не учет ортогональности векторов $x$ и $y$ друг к другу, из-за которой решения не будут, к сожалению, эквивалентны и сравнивать минимумы исходной задачи и такой, к сожалению, нельзя.

И это тоже

-- 07.08.2022, 21:47 --

ilghiz в сообщении #1562059 писал(а):

и найденный минимум не факт, что даст равнозначные нормы $x$ и $y$.

Дык на это

svv в сообщении #1562049 писал(а):

Поэтому из условий $x^Tx=1, y^Ty=1, z^Tz=2$ надо взять любые два.

[svv]

Просто чтобы было — вдруг какие-то идеи придут.
Функцию Лагранжа предлагается писать в виде
$L = x^T A x + 2 x^T B y + y^T C y - a(x^T x - 1) - 2 b x^T y-c(y^T y - 1)$
(обратите внимание, где множители Лагранжа включают двойки, а где нет)
Тогда получаются уравнения
$\begin{array}{r}Ax+By=ax+by\\B^Tx+Cy=bx+cy\end{array}$
$x^Tx=1$
$x^Ty=0$
$y^Ty=1$

[alcoholist]

кажется, каких-то надежд на "решение в общем виде" нет, https://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_program

[ilghiz]

Спасибо большое, svv за переформулировку!

alcoholist в сообщении #1562287 писал(а):

кажется, каких-то надежд на "решение в общем виде" нет, https://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_program

Спасибо большое за комментарий. Не, не согласен с Вами, там все-таки неравенства, и это однозначно задача оптимизации, как там было замечено, с np-полнотой, а в моем случае, для случая $N=2$ - есть решение через задачу на собственные значения с матрицей размера $2 \times 2$, для $N=3$ - похоже можно получить полиномиальую задачу по 3-м неизвестным, повидимому как-то упрощаемую до задачи на собственые значения (но я пока это не осилил), и есть гипотеза, что и в общем виде задача тоже сведется к задаче на собственные значения. Возможно с матрицей размера $N^2 \times N^2$, с последующим отбросом не правильных решений.