Гамма-2-норма: второе доказательство

Продолжение; начало здесь.

Мы приведём доказательство, основанное на технике полуопределённого программирования (Semidefinite programming, SDP), следуя статье T.Lee, A.Shraibman, R.Spalek, «A Direct Product Theorem for Discrepancy», 2008.

Введём некоторые обозначения. Начнём с того, что работать придётся с симметричными матрицами, а наша матрица M размера m\times n может даже не быть квадратной! Применим следующий приём для симметризации:
\widehat M := \begin{pmatrix} 0_m & M \\ M^t & 0_n \end{pmatrix}.
Здесь 0_n и 0_m — нулевые матрицы соответствующего размера. Ясно, что \widehat M симметрична и имеет размер (n+m)\times(n+m). Нам также пригодится матрица F:= \widehat 1_{m,n} — симметризация матрицы, состоящей из одних единиц. Через I обозначаем единичную матрицу (тождественный оператор).

Пусть A — квадратная матрица. Пишем A\ge 0, если матрица A — неотрицательно определённая, то есть симметричная и x^tAx\ge 0 для любого вектора x. Запись A\ge B эквивалентна A-B\ge 0. Для матриц вводится стандартное скалярное произведение: \langle A,B\rangle = \sum A_{i,j}B_{i,j} = \mathrm{tr}\,(AB^t).


Следующая простая лемма лежит в основе SDP:

Лемма. Пусть A=A^t. Тогда
\displaystyle \inf_{X\ge 0}\langle A,X\rangle = \begin{cases} 0,&\quad A\ge 0,\\ -\infty,&\quad A\not\ge0. \end{cases}

Докажем это утверждение. Если A\not\ge 0 и x^tAx<0 для некоторого вектора x, то взяв X=cxx^t и устремив c\to+\infty, мы получим минус бесконечность.

Обратно, если A\ge0 и X\ge 0, то \langle A,X\rangle\ge 0 хотя бы потому, что \langle A,X\rangle=\mathbf{1}^t(A\circ X)\mathbf{1}, а матрица A\circ X\ge 0 по теореме Шура. Следовательно, минимум достигается при X=0.

Полуопределённая оптимизация — частный случай выпуклой оптимизации. Напомним принцип Лагранжа для выпуклых задач — теорему Каруша-Куна-Таккера. Пусть дана выпуклая задача
f_0(x)\to\min,\;f_j(x)\le 0,\,j=1,\ldots,m,\;x\in\mathcal A,
где все f_j — выпуклые функции, \mathcal A\subset\mathbb R^d — выпуклое множество.
Предположим также, что выполнено условие Слейтера: \exists x_0\colon f_j(x_0)<0,\,j=1,\ldots,m. Тогда решение задачи \hat x характеризуется тем, что существуют множители Лагранжа \hat\lambda=(1,\hat\lambda_1,\ldots,\hat\lambda_m), \hat\lambda_j\ge 0, такие что функция Лагранжа L(x,\hat\lambda)=\sum_{j=0}^m\hat\lambda_j f_j(x) достигает минимума в \hat x. Более того, пара (\hat x,\hat \lambda) является седловой точкой:
L(\hat x,\lambda) \le L(\hat x,\hat\lambda) \le L(x,\hat\lambda),\quad x\in \mathcal A,\;\lambda=(1,\lambda_1,\ldots,\lambda_m),\;\lambda_j\ge 0.
Последнее означает, что \hat\lambda является решением двойственной задачи:
\displaystyle g(\lambda):=\min_{x\in\mathcal A}L(x,\lambda)\to\max,\;\lambda=(1,\lambda_1,\ldots,\lambda_m),\;\lambda_j\ge 0,
причём значения этих задач совпадают (и равны L(\hat x,\hat\lambda)).

Типичная задача SDP записывается следующим образом:
f_0(X) := \langle C,X\rangle \to\min,
f_j(X) := \langle A_j,X\rangle - b_j \le 0,\;j=1,\ldots,m,
X\ge 0.
Параметры задачи составляют симметричные матрицы C, A_j и вектор b.
Выписывая двойственную задачу, получаем выражение
\displaystyle g(\lambda) = \min_{X\ge 0} \langle C+\sum_{j=1}^m\lambda_jA_j, X\rangle - \sum_{j=1}^m \lambda_jb_j.
Применяя доказанную лемму, видим, что для того, чтобы g\neq -\infty, необходимо, чтобы матрица C+\sum_{j=1}^m \lambda_jA_j была неотрицательно определённой; при этом g(\lambda) = -\sum_{j=1}^m\lambda_jb_j. Отсюда получаем следующую двойственную задачу:
-\sum_{j=1}^m b_j\lambda_j\to\max,
C + \sum_{j=1}^m \lambda_jA_j \ge 0,
\lambda_j \ge 0,\;j=1,\ldots,m.


Теперь мы можем приступить к доказательству основной теоремы: \gamma_2(M)=\max_{\|A\|\le 1} \|A\circ M\|. По определению, \gamma_2(M)\le \eta тогда и только тогда, когда найдутся вектора x_1,\ldots,x_m и y_1,\ldots,y_n длины не более \sqrt{\eta}, такие что M_{i,j}=\langle x_i,y_j\rangle. Рассмотрим матрицу Грама X системы (x_1,\ldots,x_m,y_1,\ldots,y_n): мы видим, что X_{i,i}\le \eta для всех i, и что X\circ F = \widehat M (напомним, что F=\widehat 1_{m,n}). Отсюда ясно, что \gamma_2-норма равна значению следующей SDP-задачи:
\eta\to\min,
X_{i,i} \le \eta,\;i=1,\ldots,m+n,
X\ge 0,
X\circ F = \widehat M.

Далее мы составляем функцию Лагранжа:
L = \eta + \sum\limits_{j=1}^{m+n}\lambda_j(\langle e_je_j^t, X\rangle - \eta) + \langle Q, \widehat M-X\rangle, где Q\circ F= Q, Q^t=Q,
и стандартным образом приходим к двойственной задаче:
\langle Q,\widehat M\rangle \to \max,
\mathrm{diag}\,(\lambda) - Q \ge 0,
Q\circ F = Q,
\lambda_j \ge 0,\; \sum\lambda_j = 1.

Поскольку \mathrm{diag}\,(\lambda) \ge Q, то если какой-то \lambda_j=0, то j-й столбец и j-я строка матрицы Q нулевые; мы можем их «вычеркнуть» так как они не влияют на значение задачи; следовательно, можно считать что все \lambda_j>0. Положим Q'_{i,j}:=Q_{i,j}\lambda_i^{-1/2}\lambda_j^{-1/2}. Тогда условие \mathrm{diag}\,(\lambda) \ge Q равносильно условию I\ge Q'. По построению Q' имеет вид Q'=\widehat S для некоторой матрицы S. Условие I\ge Q'  равносильно условию \|S\|\le 1; это мы оставим читателю в качестве упражнения (см. ниже).

Наконец, пусть \alpha_j = \lambda_j^{1/2}, тогда целевая функция задачи принимает вид
\langle Q,\widehat M\rangle = \langle Q'\circ\alpha\alpha^t, \widehat M\rangle = \alpha^t(\widehat S\circ \widehat M)\alpha.
При этом условие на \lambda означает что \alpha — единичный вектор с неотрицательными координатами. Максимизируя по \alpha, получаем
\displaystyle \max_{|\alpha|=1,\alpha_j\ge 0} \alpha^t(\widehat S\circ\widehat M)\alpha = \max_{|\beta|=|\gamma|=1,\beta_i\ge 0,\gamma_j\ge 0}\beta^t(S\circ M)\gamma.
Осталось максимизировать по S\colon \|S\|\le 1; при этом условие неотрицательности координат \beta,\gamma пропадёт, т.к. умножение строки или столбца S на минус единицу не меняет норму. Итак, значение задачи равно
\displaystyle \max_{\|S\|\le 1,|\beta|=|\gamma|=1}\beta^t(S\circ M)\gamma = \max_{\|S\|\le 1}\|S\circ M\|.

Итак, мы доказали, что \gamma_2-норма равна значению SDP-задачи, а норма оператора Шура равна значению двойственной задачи. Поскольку условие Слейтера выполнено, эти значения совпадают и теорема доказана!

Упражнение. Докажите, что следующие неравенства равносильны:
(i) I\ge \widehat S; (ii) \|S\|\le 1; (iii) \|\widehat S\|\le 1.
(Указание: в (i) и (iii) речь идёт о симметричной матрице \widehat S и всё зависит от её спектра. Покажите, что он симметричен относительно нуля.)

Реклама
Стандартный

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s