Максимизация выпуклой функции с линейным ограничением

где

$\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1}$ и .$\mathbf{A} \in \mathbb{R}^{M\times N}$

Мы можем видеть, что является выпуклым и имеет вид . Также можно показать, что ограничена в . Я знаю, что проблема выпуклой максимизации, вообще говоря, NP-сложна.$f$ f[$\sqrt{1+y^2}$$f$$[\sqrt{2}, 2]$

Однако, учитывая специфику проблемы, можно ли решить ее, используя любое стандартное программное обеспечение / пакет для выпуклой оптимизации?

Да, выпуклая оптимизация с ограничением равенства в целом является NP-Hard. Тем не менее, существуют зрелые методы, которые находят очень хорошие приближенные решения для выпуклых задач оптимизации, такие как Coordinate Descent.

Предположим, вы используете координату спуска и матрица A имеет ранг . Вы можете зафиксировать nk-1 координат вашего возможного решения и тогда векторы решения в пространстве решений однозначно определяются одной координатой, например, . В этом случае вы можете просто взять производную от по чтобы найти максимум в этой итерации.х = ( х 1 , х 2 , х 3 , . . . , х п ) х я е ( ⋅ ) х $k$$x = (x_1, x_2, x_3, ..., x_n)$$x_i$$f(\cdot)$$x_i$

Затем мы итеративно фиксируем координату nk-1 и улучшаем решение до тех пор, пока не будет найдена приблизительно оптимальная.