Как реализовать выпуклый пакет оптимизации?

Question

Я полностью понимаю, что пакеты Convex Optimization, такие как пакеты линейной алгебры, должны быть вещами, которые вы используете, а не внедряете. Однако для чисто образовательных целей - есть ли хороший ресурс - ссылка / книга о том, как реализовать выпуклый пакет оптимизации? (например, для квадратичных программ с квадратичными ограничениями?)

Спасибо!

Answer 1

В любом хорошем учебнике по выпуклой оптимизации есть то, что вы ищете.Один такой бесплатный, но отличный ресурс находится здесь: CO Book .Обратите внимание, что, как вы правильно заметили, для реализации алгоритмов, упомянутых в этой книге, безусловно, потребуются библиотеки линейной алгебры, которые вы можете или не можете реализовать также.

Answer 2

Существует соответствующая статья в Optima , информационный бюллетень общества математической оптимизации под названием "Быстрая разработка Minlp Solver с открытым исходным кодом с COIN-OR". ». Он описывает создание нелинейного решателя с использованием некоторых пакетов coin- или . Большая часть монет или вещей написана на С ++.

Для python вы можете рассмотреть возможность использования структуры данных и алгоритмов линейной алгебры, доступных в numpy . Связанный пакет scipy имеет несколько нелинейных оптимизаторов, но ничего особенного для выпуклой оптимизации.

И, наконец, вы можете взглянуть на выпуклый оптимизатор Boyd's GPL на основе Python cvxopt , чтобы получить представление о том, какие задачи у вас впереди.

Answer 3

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

Я реализовал решатели для нескольких задач, сводящихся к выпуклой оптимизации (http://cs229.stanford.edu/proj2017/)- cvx4ml, который работает быстрее, чем аналогичное решение от SkLearn, и я сдал 24-часовой экзамен Стивену Бойду, чтобы я мог дать совет, что вы можете сделать и описать для своего очень грубого плана:

Итак, вы собираетесьсоздайте собственный пакет напишу пошаговую инструкцию:

1. Вам необходимо создать библиотеку для работы с плотной матрицей / векторами
2. Вам необходимо создать библиотеку для работы с разреженной матрицей / векторами
3. Реализовать около 20 различных алгоритмов для решения системы линейных уравнений (поскольку в зависимости от ситуации вам понадобятся разные из них)
4. Ввести понятия, как описывать ограничения, функциональную область и т. Д. На вашем языке программирования илиВы система, которую вы создали.
5. Реализация нескольких норм и двойных норм оценкиКроме того, некоторые методы факторизации, такие как LU, Cholesky.

6. Реализация собственного простого конического решателя для неотрицательного конуса ортона.И это зависит от того, что вы собираетесь сделать.6.a - написать решатель на основе метода внутренней точки.6.b - запись решателя с поддержкой распределенной оптимизации. 6.c - запись решателя на основе некоторого спроецированного субградиентного метода.

7. Улучшение для поддержки других конусов

8. Улучшенный решатель с шагом "5"

А если вы хотите быть на уровне CVXPY, тогда

Реализовать синтаксический анализ описания программы, например, CVXPY do, и преобразовать проблему в коническую форму.

ps Если вы чувствуете неуверенность в некоторых из этих тем, то:

• Прочитайте книгу по линейной алгебре, в которой написано проф.из вашего университета

• Посмотрите на YouTube в EE263 с S.Boyd, EE364A с S.Boyd, EE364B с S.Boyd.