# Темы задач в ДЗ 1 и на мидтерм

1. Посчитать субдифференциал для
$$f(x) = \|x\|_\infty$$

2. Определить является ли функция
$$f(x_1,x_2) = x_1^2 + 2 x_2^2 + \sqrt{3}x_1x_2$$
* выпуклой
* $\mu$-сильно выпуклой
* $L$-Липшицево гладкой (имеет $L$-Липшицев градент)
В случае положительного ответа найти константы $\mu$ и $L$. Какой метод стоит выбрать для минимизации этой функции на $R^2$? Привести его скорость сходимости.

3. Для задачи логистической регрессии
$$\min\limits_{x\in S_n(1)}\frac{1}{m}\sum_{t=1}^m \log(1+\exp(-a_t^\top x))$$
выписать в явном виде формулы стохастического зеркального спуска. Сравнить стоимость вычисления честного градиента и его стохастической аппроксимации. Получить итоговую сложность стохастического зеркального спуска.

<!-- дз: получить явные формулы для зеркального спуска на симплексе с дивергенцией Брэгмана $V= KL$
кр: доказать, что зеркальный спуск на $R^n$ с дивергенцией Брэгмана $V= \frac{1}{2}\|x-y\|_2^2$ является субградиентным методом -->

<!-- - Аналогичная (ещё более простая) задача на тему композитной оптимизации: выписать явно шаг для композита $\|x\|_1$ -->

4. Задача на приведение функции к DCP виду
https://nbviewer.org/github/cvxgrp/cvx_short_course/blob/master/exercises/DCP_analysis.ipynb
2.1 В дз: уже была в контесте

<!-- 4. Найти оптимальный шаг для данного метода для данной задачи. Чтобы нужно было понимать формулы шага и уметь посчитать $L$ или $\mu$. Чтобы не заставлять учить формулы, можно разбить задачу на две: тест на выбрать формулу для шага из готовых вариантов + расчет констант
-->

# КР

1. Вычислите субдифференциал $\partial f(x)$ для функции
$$f(x) = \sum_{i=1}^m | a_i^\top x - b_i |, ~~a_i \in R^n,~ b_i \in R.$$
2. Являются ли следующие функции $\mu$-сильно выпуклыми в Евклидовой норме? В случае положительного ответа вычислить $\mu$.
* $f(x) = \frac{1}{2}\|x\|_2^2$ на $R^n$
* $f(x) = \sum_{i=1}^n x_i\ln x_i$ на вероятностном симплексе $S_n(1)$

3. Постройте двойственную задачу к задаче обучения SVM для линейно-отделимых множеств:
$$\begin{align}
&f(w, b) = \frac12 w^\top w \to \min_{w, b}\\
\text{s.t. } & (w^\top x_j + b)y_j \geq 1 ~~\forall j\in\{1,\ldots,m\}
\end{align}$$
$w, x_j \in R^n$; $~~b, y_j \in R$ $~~\forall j\in\{1,\ldots,m\}.$

4. Пусть $f$ - выпуклая функция по правилам DCP. Объясните, почему следующая задача не является выпуклой по правилам DCP, и перепишите её в виде, удовлетворяющем DCP:
$$\begin{align}
&f(x) \to \min_x\\
\text{s.t. } &\exp(2x) + \exp(3x) \leq \exp(5x)
\end{align}$$

5. Пусть дана задача SVM, записанная в следующей форме

$$ f(x)=\frac{1}{m} \sum_{i=1}^m \max\{0, 1-y_i \langle x, a_i \rangle\} \to \min_{x \in R^n} $$

* Каким методом вы бы решали данную задачу?
* Выписать итерационную формулу этого метода для данной задачи
* Выписать скорость сходимости и итоговую сложность метода для данной задачи

Решения:
1. If $f$ is closed and convex, and $g(x) = f(Ax +b)$, then $\partial g(x) = A^\top \partial f(Ax +b)$.
Введем обозначения
$$
\begin{aligned}
&I_{-}(x)=\left\{i \mid\left\langle a_i, x\right\rangle-b_i<0\right\}, \\
&I_{+}(x)=\left\{i \mid\left\langle a_i, x\right\rangle-b_i>0\right\}, \\
&I_0(x)=\left\{i \mid\left\langle a_i, x\right\rangle-b_i=0\right\} .
\end{aligned}
$$
Тогда $\partial f(x)=\sum_{i \in I_{+}(x)} a_i-\sum_{i \in I_{-}(x)} a_i+\sum_{i \in I_0(x)}\left[-a_i, a_i\right]$.

2. 1. $\mu$=1
2. $\nabla^2 f(x) = diag(\frac1x)\Rightarrow \mu_2$ на симплексе = 1 т.к. $x_i \leq 1$

3. $$L(w, b, \lambda) =\frac12 w^\top w + \lambda^T (1 - (Xw + b)\odot y) \to \min_{w, b}$$
$$\nabla_wL = w - X^T (\lambda y) = 0$$

$$\nabla_bL = \lambda^T y = 0$$

$$\varphi(\lambda) = -\frac12\|X^T (\lambda y)\|^2 + 1^T \lambda =\sum_i^m \lambda_i - \frac12\sum_{ij}^m \lambda_iy_i\lambda_j y_j x^T_i x_j \to \max_{\lambda \geq0, y^T \lambda = 0}$$

4. выпуклая + выпуклая - выпулкая = non-DCP
$$e^{2x} + e^{3x} - e^{5x} =e^{-5x}\left(e^{-3x} + e^{-x} -1 \right) \leq 0 \Leftrightarrow e^{-3x} + e^{-x} -1 \leq 0$$
выпуклая + выпуклая - аффинная = выпуклая

5.
$$f(x)=\frac{1}{m} \sum_{i=1}^m \max\{0, 1-y_i \langle x, a_i \rangle\} \to \min_{x \in R^n}$$
$$\partial f(x) = \frac1m\sum_i -y_ia_i \frac{sign(1-y_ia_i^Tx) + 1}{2}$$

# КР2

1. Вычислите субдифференциал $\partial f(x)$ для функции
$$f(x) = e^{\|x\|_2}, ~~ x \in R.$$
2. Являются ли следующие функции $\mu$-сильно выпуклыми в Евклидовой норме? В случае положительного ответа вычислить $\mu$.
* $f(x) = \frac{1}{2}\|x\|_2^2$ на $R^n$
* $f(x) = \sum_{i=1}^n x_i\ln x_i$ на вероятностном симплексе $S_n(1)$

3. Постройте двойственную задачу к задаче обучения SVM для линейно-отделимых множеств:
$$\begin{align}
&f(w, b) = \frac12 w^\top w \to \min_{w, b}\\
\text{s.t. } & (w^\top x_j + b)y_j \geq 1 ~~\forall j\in\{1,\ldots,m\}
\end{align}$$
$w, x_j \in R^n$; $~~b, y_j \in R$ $~~\forall j\in\{1,\ldots,m\}.$

4. Пусть $f$ - выпуклая функция по правилам DCP. Объясните, почему следующая задача не является выпуклой по правилам DCP, и перепишите её в виде, удовлетворяющем DCP:
$$\begin{align}
&f(x) \to \min_x\\
\text{s.t. } &\exp(2x) + \exp(3x) \leq \exp(5x)
\end{align}$$

5. Пусть дана задача SVM, записанная в следующей форме

$$ f(x)=\frac{1}{m} \sum_{i=1}^m \max\{0, 1-y_i \langle x, a_i \rangle\} \to \min_{x \in R^n} $$

* Каким методом вы бы решали данную задачу?
* Выписать итерационную формулу этого метода для данной задачи
* Выписать скорость сходимости и итоговую сложность метода для данной задачи

# Проекты