Найти экстремум функции, заданной квадратичной формой

[danildushistov]

Здравствуйте!

Есть задача условной оптимизации $(P)$ для функции, заданной квадратичной формой $(Ax,x)$, где $A$ - матрица квадратичной формы, при условии $\|x\|=1$, где $x \in \mathbb{R}^n$.

Более формально,

$$(P): \begin{cases} (Ax,x) \to \text{extr} \\ \|x\|=1, x \in \mathbb{R}^n \end{cases}$$

Преобразуем немного ограничение: $\|x\|=1 \Leftrightarrow |x|=1 \Leftrightarrow |x|^2=1 \Leftrightarrow (x,x)-1=0 \Leftrightarrow (Ex,x)-1=0$.

Составим функцию Лагранжа: $L(x,\lambda)=\lambda_0(Ax,x)+\lambda_1((Ex,x)-1)$.

Вычислим ее частные производные с помощью градиента:

$(Ax,x)'= \operatorname{grad}(Ax,x)=2Ax$.
$(Ex,x)'= \operatorname{grad}(Ex,x)=2Ex=2x$.
$L(x,\lambda)'=\lambda_02Ax+\lambda_12x$.

Приравняем к нулю последнее выражение: $\lambda_02Ax+\lambda_12x=0$.

1) Пусть $\lambda_0=0$. Тогда $\lambda_12x=0$, а так как $x \neq 0$ в силу ограничения в условии задачи (так как норма нулевого вектора не равна единице), то $\lambda_1=0$, что противоречит принципу Лагранжа. Значит, $\lambda_0 \neq 0$.

2) Пусть $\lambda_0=1$

Тогда $2Ax+\lambda_12x=0 \Leftrightarrow Ax + \lambda_1x=0 \Leftrightarrow Ax = -\lambda_1x$.

А из линейной алгебры известно, что $-\lambda_1$ является собственным значением линейного отображения $A$. Это значит, что все решения уравнения находятся во множестве решений характеристического уравнения для линейного отображения $A$: $|A-\lambda E|=0$.

Так как ограничение $\|x\|=1$ формирует сферу, то есть ограниченное и замкнутое множество, то по обобщенной теореме Вейерштрасса в данной задаче существует абсолютный минимум и абсолютный максимум. Следовательно, чтобы найти их, нам необходимо найти все вектора $x_i$, соответствующие значениям $-\lambda_i, i=1,...,n$, и, непосредственно подставляя их в $(Ax,x)$, отбором найти значения абсолютного минимума и максимума.

Вопросы:

1) Все правильно? :)
2) Я не разобрался, что представляет собой математический объект $2Ax$. Если $2x$ - это вектор, то для предыдущего объекта его смысл мне не понятен...

Спасибо!

[provincialka]

1.

danildushistov в сообщении #816349 писал(а):

что $-\lambda_1$ является значением, противоположным собственному значению линейного отображения

Точнее, $-\lambda_1$ является собственным значением, но дальше вы это исправили.
2. Вы зачем двойку за собой таскаете, сократите на нее.
3.

danildushistov в сообщении #816349 писал(а):

что представляет собой математический объект $2Ax$.

Ну, что - преобразованный вектор $x$. Но, с учетом того, что $x$ - собственный вектор этого преобразования, то $Ax=(-\lambda_1)x$.

Не очень понятно, чего вы хотите добиться. Решить задачу в общем виде? Ну, это вряд ли.

[danildushistov]

provincialka в сообщении #816354 писал(а):

Точнее, $-\lambda_1$ является собственным значением, но дальше вы это исправили.

Спасибо, теперь исправил с самого начала. Я неправильно представлял себе определение собственного значения...

provincialka в сообщении #816354 писал(а):

Не очень понятно, чего вы хотите добиться. Решить задачу в общем виде? Ну, это вряд ли.

Почему вряд ли? Кроме того, таким было требование самой задачи. Или в решении что-то неправильно?

[provincialka]

Тут вопрос в том, что считать решением. Если просто описание алгоритма, как у вас - да, вы решили. Другое дело - выписать ответы. Конечн численно это не получится.

Впрочем, я, кажется, поторопилась. Можно выразить ответ в терминах собственных значений.

danildushistov в сообщении #816349 писал(а):

непосредственно подставляя их в $(Ax,x)$, отбором найти значения абсолютного минимума и максимума.

Немного доведите эту мысль до ума.

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

Ну, вообще-то решение прямо следует из одного из определений собственных значений.

[ewert]

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

вообще-то решение прямо следует из одного из определений собственных значений.

Не следует: определение собственных значений единственно. А то, что для эрмитовых матриц есть спектральное разложение, из которого всё действительно следует (и что вообще отношение Рэлея $\frac{(Ax,x)}{\|x\|^2}$ свято) -- это вопрос уже другой; и, судя по контексту, предполагалось решение всё-таки не через Рэлея, а именно через Лагранжа.

[danildushistov]

Нашел у себя ошибку и решил доделать пример. В итоге пришлось переписать.

Есть задача условной оптимизации $(P)$ для функции, заданной квадратичной формой $(Ax,x)$, где $A$ - некоторая матрица $n$-ного порядка, при условии $\|x\|=1$, где $x \in \mathbb{R}^n$.

Более формально,

$$(P): \begin{cases} (Ax,x) \to \text{extr} \\ \|x\|=1, x \in \mathbb{R}^n \end{cases}$$

$(Ax,x)$ - запись квадратичной формы с помощью скалярного произведения векторов $Ax$ и $x$.

Преобразуем немного ограничение: $\|x\|=1 \Leftrightarrow |x|=1 \Leftrightarrow |x|^2=1 \Leftrightarrow (x,x)-1=0 \Leftrightarrow (Ex,x)-1=0$.

Составим функцию Лагранжа: $L(x,\lambda)=\lambda_0(Ax,x)+\lambda_1((Ex,x)-1)$.

Вычислим ее частные производные с помощью градиента:

$(Ax,x)'= \operatorname{grad}(Ax,x)=2Ax$.
$(Ex,x)'= \operatorname{grad}(Ex,x)=2Ex=2x$.
$L(x,\lambda)'=\lambda_02Ax+\lambda_12x$.

Приравняем к нулю последнее выражение: $\lambda_02Ax+\lambda_12x=0$.

1) Пусть $\lambda_0=0$. Тогда $\lambda_12x=0$, а так как $x \neq 0$ в силу ограничения в условии задачи (так как норма нулевого вектора не равна единице), то $\lambda_1=0$, что противоречит принципу Лагранжа. Значит, $\lambda_0 \neq 0$.

2) Пусть $\lambda_0=1$

Тогда $2Ax+\lambda_12x=0 \Leftrightarrow Ax + \lambda_1x=0 \Leftrightarrow Ax = -\lambda_1x$.

А из линейной алгебры известно, что $-\lambda_1$ является собственным значением линейного отображения $A$. Это значит, что все решения уравнения находятся во множестве решений характеристического уравнения для линейного отображения $A$: $|A-\mu E|=0$.

$$|A-\mu E|=0 \Leftrightarrow \begin{vmatrix} a_{11}-\mu & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22}-\mu & \cdots & a_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ a_{n1} & a_{n2} & \cdots & a_{nn}-\mu \\ \end{vmatrix} = 0$$

Пусть это уравнение имеет $k$ решений.

Так как ограничение $\|x\|=1$ формирует сферу, то есть ограниченное и замкнутое множество, то по обобщенной теореме Вейерштрасса в данной задаче существует абсолютный минимум и абсолютный максимум. Следовательно, чтобы найти их, нам необходимо найти все вектора $x_i^*$, соответствующие значениям $\mu_i, i=1,...,k$, и, непосредственно подставляя их в $(Ax,x)$, отбором найти значения абсолютного минимума и максимума.

Чтобы найти собственный вектор, соответствующий собственному значению $\mu_i, i=1,...,k$, воспользуемся определением собственного вектора:

$$Ax=\mu x \Leftrightarrow \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \\ \end{pmatrix} = \begin{pmatrix} \mu_i x_1 \\ \mu_i x_2 \\ \vdots \\ \mu_i x_n \\ \end{pmatrix}$$

Перепишем эту систему в более удобном виде:

$$\begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n=\mu_i x_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n=\mu_i x_2 \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots\\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n=\mu_i x_n \end{cases} \Leftrightarrow \begin{cases} (a_{11}-\mu_i)x_1 + a_{12}x_2 + \cdots + a_{1n}x_n=x_1 \\ a_{21}x_1 + (a_{22}-\mu_i)x_2 + \cdots + a_{2n}x_n=x_2 \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots\\ a_{n1}x_1 + a_{n2}x_2 + \cdots + (a_{nn}-\mu_i)x_n=x_n \end{cases}$$

Пусть этой системе соответствует решение $x_i^*, i=1,...,k$. Если $\exists t, 1 \leqslant t \leqslant k: rank(A-\mu_t E)<n$, то есть в собственном векторе, соответствующем $\mu_t$, некоторые координаты будут зафиксированы, мы полагаем их равными 1.

Таким образом, получено $k$ собственных векторов линейного отображения $A: x_1^*,...,x_k^*$. Тогда, в силу обобщенной теоремы Вейерштрасса, решение задачи $(P)$ будет таким:

$$absmin(P)=\min\limits_{i = 1,...k}(Ax_i^*,x_i^*), absmax(P)=\max\limits_{i = 1,...k}(Ax_i^*,x_i^*)$$

Задача решена.

[ewert]

Как-то чересчур уж много лямбд и логических пируэтов. Если $L(x,\lambda)=(Ax,x)+\lambda(\|x\|^2-1)=((A+\lambda E)x,x)-\lambda$, то дифференцирование по иксам даёт уравнение $2(A+\lambda E)x=0$, а дифференцирование по лямбде снова возвращает к условию $(x,x)=1$. Это -- необходимые условия экстремума; и поскольку по теореме Вейерштрасса максимум и минимум на сфере заведомо достигаются -- достигаться они могут только на одном из собственных векторов, т.к. первое из уравнений равносильно $Ax=-\lambda x$ и в точности означает, что $x$ есть собственный вектор, отвечающий собственному числу $(-\lambda)$. Однако если этот вектор -- собственный, отвечающий какому угодно собственному числу $\mu$, то на нём целевая функция принимает вид $(Ax,x)=(\mu x,x)=\mu\|x\|^2=\mu\cdot1=\mu$, раз уж мы на сфере. Следовательно, минимальное значение равно наименьшему из собственных чисел и, соответственно, максимальное -- наибольшему (самих точек экстремума может оказаться бесконечно много, т.к. эти собственные числа могут оказаться вырожденными).

[provincialka]

Кстати, посмотрите в теории, сколько вещественных собственных значений у симметричной матрицы.