Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- \paragraph{18.10}
- \textbf{(a)} Это задача выпукла, как и было сказано. Ограничения $1^T x = B$ и $x \ge 0$, очевидно, выпуклы. Покажем, что задача вогнута. Поскольку известно, что $1^T x = B$, оставшееся выражение - известная константа, $P = (1 - c)(1^T a + B).$ Задача представляет из себя выпуклую комбинацию выражений вида: $U(\frac{P x_i}{x_i + a_i})$, каждое из которых вогнуто по $x$, так как $\frac{x_i}{x_i + a_i}$ вогнуто по $x_i$ для $x_i \ge 0$, и, по правилам композиции, применение вогнутой возрастающей функции к другой вогнутой функции сохраняет вогнутость. \\
- \textbf{(b)} Задача может быть представлена так:
- $$\begin{cases}
- max \overset{n}{\underset{i = 1}{\sum}} f_i(x_i) \\
- 1^T x = B, x \ge 0, \\
- \end{cases}
- $$
- где $f_i(x_i) = \pi_i U(\frac{P x_i}{x_i + a_i})$ - вогнутые по $x$ функции, как было показано в предыдущем пункте. Запишем частичный Лагранжиан:
- $$L(x, \mu) = \overset{n}{\underset{i = 1}{\sum}} f_i(x_i) + \mu (B - 1^T x),$$
- с $\textbf{dom} L = \textbf{R}^n_+ \times \textbf{R}$. Будем максимизировать по каждому из $x_i$ отдельно: $x_i = \underset{x_i \ge 0}{argmax} (f_i(x_i) - \mu x_i)$. \\
- Наше предположение что $U$ строго вогнута подразумевает, что $f_i$ тоже строго вогнута, поэтому решение задачи будет единственным. Также скалярные задачи максимизации легко решаются, в соответствии со вторым предположением, поэтому, необходимо найти такое $\mu$, что $1^T x = B$. Поскольку каждое $x_i$ монотонно невозрастает по $\mu$, можно для решения воспользоваться методом бисекции. \\
- Когда $\mu < 0$, задача неограничена сверху, поэтому $\mu \ge 0$. Когда $\mu \ge max_i f'_i(0)$, имеем $b = 0$. Значит, можно начать алгоритм с начального отрезка $\mu \in [0, max_i f'_i(0)]$.\\
- Каждый шаг алгоритма потребует решения $n$ скалярных задач оптимизации, и для нахождения решения необходимо выполнить достаточное число шагов, например, 20.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement