Задача минимизации (проверьте решение, пожалуйста)

[aUruM]

Здравствуйте. Если не трудно, проверьте, пожалуйста, решение задачи минимизации. Я использовал метод Лагранжа, но буду очень благодарен, если кто-нибудь подскажет мне, как можно решить ее проще (если это возможно). Заранее спасибо.

Пусть $W$ -- симметричная неотрицательно определенная $n\times n$ матрица, ранг которой равен $r<n$, причем

$$ W=\left( \begin{array}{cc} W_1&W_{12}\\ W_{21}&W_2 \end{array} \right), $$

где $W_1$ -- симметричная положительно определенная $r\times r$ матрица.

Обозначим $z=(z_1,\dots,z_n)^T$. Пусть $z^{(1)}=(z_1,\dots,z_r)$ -- подвектор вектора $z$. Рассмотрим задачу минимизации:

$$ \left\{ \begin{array}{l} (W_1z^{(1)},z^{(1)})\to\min\limits_z\\ (z,\overline{1})=1,\quad Wz=\overline{0}. \end{array} \right. $$

Перепишем ее в виде:

$$ \label{mo_opt_1} \left\{ \begin{array}{l} \sum\limits_{i,j=1}^rw_{ij}z_iz_j\to\min\limits_z\\ \sum\limits_{j=1}^nz_j=1, \quad \sum\limits_{j=1}^nw_{ij}z_j=0\quad(i=\overline{1,n}). \end{array} \right. $$

Применим метод Лагранжа. Составим функцию Лагранжа:

$$ L(z_1,\dots,z_n,u,\lambda_1,\dots,\lambda_n)=\sum\limits_{i,j=1}^rw_{ij}z_iz_j-u\left(\sum\limits_{j=1}^nz_j-1\right)-\sum_{i,j=1}^nw_{ij}\lambda_iz_j. $$

Обозначим $\psi=(z_1, \dots, z_n, u, \lambda_1, \dots, \lambda_n)^T$. Дифференцируя фунцкию Лагранжа по аргументам и пользуясь симметричностью матрицы $W$, получим:

$$ \begin{array}{l} \frac{\partial L}{\partial z_k}=\left\{ \begin{array}{rl} \sum\limits_{j=1}^rw_{kj}z_j-u-\sum\limits_{j=1}^nw_{kj}\lambda_j,&1\le k \le r,\\ -u-\sum\limits_{j=1}^nw_{kj}\lambda_j,&r+1\le k\le n, \end{array} \right.\\ \frac{\partial L}{\partial u}=1-\sum\limits_{j=1}^nz_j,\\ \frac{\partial L}{\partial \lambda_k}=-\sum\limits_{j=1}^nw_{kj}z_j,\quad k=\overline{1,n}. \end{array} $$

Приравнивая частные производные к нулю, получим систему $2n+1$ линейных алгербаических уравнений относительно $2n+1$ неизвестных $z_1$, $\dots$, $z_n$, $u$, $\lambda_1$, $\dots$, $\lambda_n$:

$$ \left\{\begin{array}{rl} \sum\limits_{j=1}^rw_{kj}z_j-u-\sum\limits_{j=1}^nw_{kj}\lambda_j=0,&1\le k\le r,\\ -u-\sum\limits_{j=1}^nw_{kj}\lambda_j=0,&r+1\le k\le n,\\ \sum\limits_{j=1}^nz_j=1,&\\ -\sum\limits_{j=1}^nw_{ij}z_j=0,&i=\overline{1,n}. \end{array}\right. $$

Матрица этой системы имеет вид:

$$ A=\left( \begin{array}{cccccccccc} w_{11}&\cdots&w_{1r}&0&\cdots&0&-1&-w_{11}&\cdots&-w_{1n}\\ w_{21}&\cdots&w_{2r}&0&\cdots&0&-1&-w_{21}&\cdots&-w_{2n}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ w_{r1}&\cdots&w_{rr}&0&\cdots&0&-1&-w_{r1}&\cdots&-w_{rn}\\ 0&\cdots&0&0&\cdots&0&-1&-w_{r+1,1}&\cdots&-w_{r+1,n}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ 0&\cdots&0&0&\cdots&0&-1&-w_{n1}&\cdots&-w_{nn}\\ 1&\cdots&1&1&\cdots&1&0&0&\cdots&0\\ w_{11}&\cdots&w_{1r}&w_{1,r+1}&\cdots&w_{1n}&0&0&\cdots&0\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ w_{n1}&\cdots&w_{nr}&w_{n,r+1}&\cdots&w_{nn}&0&0&\cdots&0\\ \end{array} \right). $$

Вектор правой части $f$ состоит целиком из нулей, кроме $(n+1)$-го элемента, равного единице.

Пусть $A^+$ -- матрица, псевдообратная к матрице A. Известно, что данная система имеет решение тогда и только тогда, когда $AA^+f=f$, причем в этом случае все решения системы даются формулой:

$$ \psi=A^+f+\psi_0, $$

где $\psi_0$ -- любое решение соответствующей однородной системы: $A\psi_0=\overline{0}$.

Легко видеть, что ранг матрицы $A$ меньше $2n+1$. Это значит, что соответствующая однородная система имеет бесконечно много решений, тогда бесконечно много решений имеет и оптимизационная задача. Взяв в качестве $\psi_0$ тривиальное решение однородной системы, получим:

$$ \psi=A^+f. $$

Тем самым, мы фактически выделили $(n+1)$-й столбец матрицы $A^+$. В качестве искомого вектора $z$ возьмем первые $n$ элементов полученного вектора $\psi$.