Оптимизация, зазор двойстенности для лог регрессии

[Verbery]

Здравствуйте! Решил разобраться с темой двойственности в математической оптимизации и построить зазор двойственности для функции логистической регрессии, вот так она описывается:

$$\min_{w\in \mathbb{R}^n} \frac{1}{m} \sum\limits_{i=1}^m \log \left(1+\exp(-y_i \langle w, x_i \rangle)\right) + \frac{\alpha}{2}\|w\|_2^2,$$

, тут $x_i$ - это строка из матрицы $X$ (не квадратная!), $\alpha$ - константа

Чтобы построить двойственную функцию, добавим искусственное ограничение:
$u_i=y_i \langle w, x_i\rangle, \forall i=\overline{1,m}$, а сама функция станет такой $\frac{1}{m} \sum\limits_{i=1}^m \log \left(1+\exp(-u_i)\right) + \frac{\alpha}{2}\|w\|_2^2$

Теперь сама двойственная функция:

$$g(\nu) = \min_{u, \omega} \frac{1}{m} \sum\limits_{i=1}^m \log \left(1+\exp(-u_i)\right) + \frac{\alpha}{2}\|w\|_2^2 - \nu^\top(u - y \ \circ \ X \omega)$$

Теперь через производную нашёл такую точку минимума (несколько раз перепроверил):

$$\begin{equation} \left\{\begin{split} \omega_{\min} = -\frac{1}{\alpha}(\nu \ \circ \ y)^\top X \\ u_{i \ \min} = - \ln{\frac{\nu_i}{1 - \nu_i m}} \\ \end{split}\right.\end{equation}$$

Дальше мне надо выразить $\nu$ через $\omega$ для того, чтобы образовать функцию $g(\nu(\omega))$ и тогда я смогу получить критерий приближения к минимуму вот так $f(\omega) - g(\nu(\omega))$.

Теперь сам вопрос. Как мне выразить $\nu$ через $\omega$ в (1)? Я не понимаю как это сделать, так как $X$ может быть не квадратной и нельзя эту матрицу просто перебросить в правую часть уравнения

Так же я ещё не решил как обойти проблему отрицательного значения под логарифмом в $u_{\min}$, но это уже дальше...

[Verbery]

Никто не знает? Нашёл вот такую штуку https://en.wikipedia.org/wiki/Moore%E2% ... se_inverse. Если её использовать, то можно записать:

$$\nu = - (\frac{\alpha}{y} \circ \omega) X^{-1}$$

Просто основное затруднения были в том, что матрица не квадратная. Но если это преобразование по ссылке применить, то вроде бы всё получается

[Alex Krylov]

Эта оптимизационная задача выпуклая или нет?

[Verbery]

Alex Krylov в сообщении #1640912 писал(а):

Эта оптимизационная задача выпуклая или нет?

Она вогнутая. Значит со знаком "-" будет выпуклой

[Alex Krylov]

Я имею в виду, что в вашем заглавном сообщении в самом верху целевая функция - выпуклая (если $\alpha$ положительная константа). Далее у вас возникают искусственные афинные ограничения. По определению это задача выпуклого программирования (convex optimization problem). Теперь надо обратиться к понятию сильной двойтсвенности и условию Слейтера.

[Verbery]

Alex Krylov в сообщении #1641477 писал(а):

Я имею в виду, что в вашем заглавном сообщении в самом верху целевая функция - выпуклая (если $\alpha$ положительная константа). Далее у вас возникают искусственные афинные ограничения. По определению это задача выпуклого программирования (convex optimization problem). Теперь надо обратиться к понятию сильной двойтсвенности и условию Слейтера.

Я хотел минимизировать функцию из заглавного сообщения с помощью кода на Python. Для этого в моём алгоритме градиентного спуска в качестве критерия приближения к минимуму я хотел использовать зазор двойственности: $f(\omega) - g(\nu(\omega))$. $\omega$ мне известна на каждой итерации алгоритма. Вопрос тут был в том как мне получить $\nu(\omega)$ отсюда:

Verbery в сообщении #1640356 писал(а):

Теперь через производную нашёл такую точку минимума (несколько раз перепроверил):

$$\begin{equation} \left\{\begin{split} \omega_{\min} = -\frac{1}{\alpha}(\nu \ \circ \ y)^\top X \\ u_{i \ \min} = - \ln{\frac{\nu_i}{1 - \nu_i m}} \\ \end{split}\right.\end{equation}$$