Есть ли качественный решатель нелинейного программирования для Python?

У меня есть несколько сложных невыпуклых задач глобальной оптимизации. В настоящее время я использую MATLAB Optimization Toolbox (в частности, fmincon()с алгоритмом = 'sqp'), что довольно эффективно . Тем не менее, большая часть моего кода написана на Python, и я бы тоже хотел провести оптимизацию на Python. Есть ли решатель НЛП с привязками Python, с которым можно конкурировать fmincon()? Это должно

• уметь обрабатывать нелинейные ограничения равенства и неравенства
• не требовать от пользователя предоставления якобиана.

Это нормально, если это не гарантирует глобального оптимума ( fmincon()не дает). Я ищу что-то, что сильно сходится к локальному оптимуму даже для сложных задач, и даже если это немного медленнее, чем fmincon().

Я попробовал несколько решателей, доступных через OpenOpt, и обнаружил, что они уступают MATLAB fmincon/sqp.

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

Джефф указывает, что некоторые характеристики проблемы могут быть актуальны. Они есть:

• 10-400 переменных решения
• 4-100 ограничений на полиномиальное равенство (степень полинома варьируется от 1 до 8)
• Количество ограничений рационального неравенства, равных примерно удвоенному числу переменных решения
• Целевая функция является одной из переменных решения

Якобиан ограничений равенства плотен, как и якобиан ограничений неравенства.

fmincon()Как вы упомянули, используется несколько стратегий, хорошо известных в нелинейной оптимизации, которые пытаются найти локальный минимум, не обращая особого внимания на то, был ли найден глобальный оптимум. Если вы согласны с этим, то я думаю, что вы правильно сформулировали вопрос (нелинейная оптимизация).

Лучший пакет, который мне известен для общей нелинейной оптимизации, - это IPOPT [1]. Очевидно, Мэтью Сюй поддерживает набор привязок Python к IPOPT , так что это может быть где-то для начала.

[1]: Андреас Вахтер - личный друг, поэтому я могу быть немного предвзятым.

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

Если вы можете сформулировать свою задачу в виде явной системы уравнений и вам нужен свободный решатель, то, как сказал Арон, вам лучше всего выбрать IPOPT. Другие бесплатные решатели можно найти на веб-сайте COIN-OR . Насколько мне известно, нелинейные решатели не имеют привязки Python, предоставленные разработчиками; любые привязки, которые вы найдете, будут сторонними. Чтобы получить хорошие решения, вы также должны были бы обернуть любой нелинейный выпуклый решатель, который вы нашли в соответствующей стохастической эвристике глобальной оптимизации или в детерминированном алгоритме глобальной оптимизации, таком как ветвление и ограничение. В качестве альтернативы вы могли бы использовать Bonmin или Couenne, оба из которых являются детерминированными невыпуклыми решателями оптимизации, которые хорошо работают по сравнению с современным решателем BARON .

Если вы можете приобрести коммерческий решатель оптимизации, вы можете рассмотреть язык моделирования GAMS , который включает в себя несколько решателей нелинейной оптимизации. Особо следует отметить интерфейсы для решателей CONOPT, SNOPT и BARON. (CONOPT и SNOPT являются выпуклыми решателями.) Клуджевое решение, которое я использовал в прошлом, заключается в использовании привязок языка Fortran (или Matlab) к GAMS для написания файла GAMS и вызова GAMS из Fortran (или Matlab) для вычисления решение задачи оптимизации. GAMS имеет привязки к языку Python и очень отзывчивый персонал поддержки, готовый помочь, если возникнут проблемы. (Отказ от ответственности: я не имею отношения к GAMS, но моя лаборатория действительно имеет лицензию GAMS.) Коммерческие решатели должны быть не хуже, чемfmincon; на самом деле, я бы удивился, если бы они не были намного лучше. Если ваши проблемы достаточно малы по размеру, вам может даже не понадобиться приобретать лицензию GAMS и лицензии для решателей, поскольку ознакомительную копию GAMS можно загрузить с их веб-сайта. В противном случае вы, вероятно, захотите решить, какие решатели приобрести вместе с лицензией GAMS. Стоит отметить, что BARON требует смешанного целочисленного решения для линейного программирования, и что лицензии на два лучших смешанных целочисленных решения для линейного программирования CPLEX и GUROBI бесплатны для академиков, так что вы можете просто обойтись без покупки только интерфейсов GAMS. чем интерфейсы и решающие лицензии, которые могут сэкономить вам немало денег.

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

ОБНОВЛЕНИЕ: Одна мысль, которая сначала не пришла мне в голову, заключалась в том, что вы также можете вызывать Инструментарий для расширенной оптимизации ( TAO ) и PETSc, используя tao4py и petsc4py , что могло бы принести дополнительное преимущество в виде упрощения распараллеливания и использования знакомства с PETSc. и инструменты ACTS .

ОБНОВЛЕНИЕ № 2: На основании упомянутой вами дополнительной информации, методы последовательного квадратичного программирования (SQP) будут вашим лучшим выбором. Методы SQP обычно считаются более надежными, чем методы внутренней точки, но они имеют недостаток, заключающийся в необходимости плотных линейных решений. Так как вы больше заботитесь о надежности, чем о скорости, SQP будет вашим лучшим выбором. Я не могу найти хорошего решателя SQP там, написанного на Python (и, по-видимому, в этом техническом отчете Свен Лейффер из Аргонна тоже не смог ). Я предполагаю, что алгоритмы, реализованные в таких пакетах, как SciPy и OpenOpt, имеют основной каркас некоторых реализованных алгоритмов SQP, но без специальной эвристики, которую используют более продвинутые коды для преодоления проблем сходимости. Вы можете попробовать NLopt, написанный Стивеном Джонсоном в MIT. Я не возлагаю на это больших надежд, потому что у него нет репутации, о которой я знаю, но Стивен Джонсон - замечательный парень, который пишет хорошее программное обеспечение (в конце концов, он соавтор FFTW). Он реализует версию SQP; если это хорошее программное обеспечение, дайте мне знать.

Я надеялся, что у TAO будет что-то вроде ограниченного решения для оптимизации, но это не так. Вы, конечно, можете использовать то, что они должны создать; у них там много компонентов. Однако, как вы указали, для вас было бы гораздо больше работы, и, если вы столкнетесь с подобными проблемами, вы с таким же успехом можете стать разработчиком TAO.

С этой дополнительной информацией вы, скорее всего, получите лучшие результаты, вызывая GAMS из Python (если это вообще возможно) или пытаясь исправить интерфейс Python IPOPT. Поскольку IPOPT использует метод внутренней точки, он не будет таким надежным, но, возможно, реализация Андреасом метода внутренней точки значительно лучше, чем реализация SQP в Matlab, и в этом случае вы можете вообще не жертвовать устойчивостью. Вы должны были бы провести некоторые тематические исследования, чтобы знать наверняка.

Вы уже знаете, как переформулировать ограничения рационального неравенства как ограничения полиномиального неравенства (это в вашей книге); Причина, по которой это поможет BARON и некоторым другим невыпуклым решателям, заключается в том, что он может использовать анализ терминов для генерации дополнительных допустимых неравенств, которые он может использовать в качестве сокращений для улучшения и ускорения сходимости решателя.

Исключая привязки GAMS Python и интерфейс Python к IPOPT, ответ - нет, пока еще нет высококачественных решателей нелинейного программирования для Python. Может быть @Dominique изменит это с NLPy.

ОБНОВЛЕНИЕ № 3: Более неожиданные попытки найти решатель на основе Python привели к появлению PyGMO , который представляет собой набор привязок Python к PaGMO, глобальному многоцелевому решателю оптимизации на основе C ++. Хотя он был создан для многоцелевой оптимизации, он также может быть использован для единого объективного нелинейного программирования и имеет интерфейсы Python для IPOPT и SNOPT, среди других решателей. Он был разработан в рамках Европейского космического агентства , так что, надеюсь, за этим стоит сообщество. Это было также выпущено относительно недавно (24 ноября 2011).

Обновление: посмотрите новый пакет GEKKO, который мы только что выпустили.

APM Python - это бесплатный инструментарий для оптимизации, имеющий интерфейсы для APOPT, BPOPT, IPOPT и других решателей. Он предоставляет решателям первую (якобианскую) и вторую (гессианскую) информацию и предоставляет дополнительный веб-интерфейс для просмотра результатов. Клиент APM Python устанавливается вместе с pip:

 pip install APMonitor

Он также может быть установлен в скрипте Python с помощью:

try:
    from APMonitor.apm import *
except:
    # Automatically install APMonitor
    import pip
    pip.main(['install','APMonitor'])
    from APMonitor.apm import *

Мы провели несколько тестов производительности и обнаружили, что комбинация APOPT (метод активного набора) и IPOPT (метод внутренней точки) может решить большой процент проблем с тестами. Существует ряд примеров проблем, которые включены в загрузочный ZIP-файл. Вероятно, вам стоит начать с проблемы Hock Schittkowski # 71. Это простейший пример, демонстрирующий, как решать ограниченные задачи оптимизации.

Есть интерфейс браузера и API для Python / MATLAB. API для Python - это отдельный скрипт (apm.py), который можно загрузить с домашней страницы apmonitor.com. Как только скрипт загружается в код Python, он дает возможность решать проблемы:

• Нелинейные уравнения
• Смешанное целочисленное нелинейное программирование
• Дифференциальные и алгебраические уравнения
• Примерка модели наименьших квадратов
• Оценка движущегося горизонта
• Нелинейная модель прогностического контроля
• и т.п.

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

Ниже приведен пример проблемы оптимизации (hs71.apm).

Model
  Variables
    x[1] = 1, >=1, <=5
    x[2] = 5, >=1, <=5
    x[3] = 5, >=1, <=5
    x[4] = 1, >=1, <=5
  End Variables

  Equations
    x[1] * x[2] * x[3] * x[4] > 25
    x[1]^2 + x[2]^2 + x[3]^2 + x[4]^2 = 40

    minimize  x[1] * x[4] * (x[1]+x[2]+x[3]) + x[3]
  End Equations
End Model

Задача оптимизации решается с помощью следующего скрипта Python:

from APMonitor.apm import *
server = 'http://byu.apmonitor.com'

# Application name
app = 'eqn'

# Clear previous application
apm(server,app,'clear all')

# Load model file
apm_load(server,app,'hs71.apm')

# Option to select solver (1=APOPT, 2=BPOPT, 3=IPOPT)
apm_option(server,app,'nlc.solver',3)

# Solve on APM server
solver_output = apm(server,app,'solve')

# Display solver output
print(solver_output)

# Retrieve results
results = apm_sol(server,app)

# Display results
print('--- Results of the Optimization Problem ---')
print(results)

# Display Results in Web Viewer 
url = apm_var(server,app)
print("Opened Web Viewer: " + url)

APM Python - бесплатный веб-сервис для оптимизации. Задачи оптимизации решаются на удаленных серверах, а результаты возвращаются в локальный скрипт Python. Локальный сервер APMonitor также доступен для загрузки, поэтому подключение к Интернету не требуется ( сервер загрузки ). Недавно мы добавили поддержку параллельной обработки для MATLAB и Python. Модуль Python совместим с Python 2.7 или Python 3+.

Хотя это не полностью отвечает на ваш вопрос, я пишу пакет Python для нелинейного программирования с именем NLPy. Самую последнюю версию можно получить по адресу https://github.com/dpo/nlpy.

Я должен подчеркнуть, что NLPy является исследовательским классом, и включенные решатели отнюдь не так надежны, как более опытные коды, такие как IPOPT. Более того, в настоящее время они требуют предоставления якобинцев. Тем не менее, цель NLPy состоит в том, чтобы предоставить инструменты, необходимые исследователям для сборки пользовательских решателей, если это необходимо. В любом случае, мне будет интересно услышать ваши комментарии в автономном режиме, если вы попробуете. Вы также можете найти соответствующие пакеты https://github.com/dpo/pykrylov и https://github.com/dpo/pyorder полезными. В настоящее время документация по NLPy определенно отсутствует. Два других должны быть разумными.

pyomo - это полная GAMS / AMPL-подобная среда моделирования для оптимизации в python. Он чрезвычайно мощный, имеет интерфейсы для всех решателей, поддерживаемых AMPL, и автоматически генерирует якобианы и т. Д. Однако из-за того, что он работает в «виртуальной среде Python», связать его с существующим кодом не так просто.

Недавно мы выпустили (2018) пакет Python GEKKOдля нелинейного программирования с помощью решателей, таких как IPOPT, APOPT, BPOPT, MINOS и SNOPT с методами активного набора и внутренней точки. Одна из проблем, возникающих при использовании этих решателей, заключается в том, что обычно требуется предоставить по крайней мере первые производные и, возможно, вторые производные. Есть несколько хороших языков моделирования, которые могут сделать это для вас, как уже упоминалось в других ответах. GEKKO компилирует уравнения в байт-код так, что вы написали модель на языке Fortran или C ++ с точки зрения скорости. Автоматическое дифференцирование обеспечивает 1-ю и 2-ю производные в разреженной форме для решателей на основе градиента. Мы разработали GEKKO для задач оптимального управления, но она также может решать проблемы, аналогичные fmincon. Ниже приведен краткий пример задачи нелинейного программирования с ограничениями равенства и неравенства. Ты первый'

pip install gekko

Задача Хока-Щитковского № 71 показана ниже в качестве примера целевой функции, ограничения неравенства, ограничения равенства и четырех переменных с верхними и нижними границами.

from gekko import GEKKO
m = GEKKO() # Initialize gekko
# Initialize variables
x1 = m.Var(value=1,lb=1,ub=5)
x2 = m.Var(value=5,lb=1,ub=5)
x3 = m.Var(value=5,lb=1,ub=5)
x4 = m.Var(value=1,lb=1,ub=5)
# Equations
m.Equation(x1*x2*x3*x4>=25)
m.Equation(x1**2+x2**2+x3**2+x4**2==40)
m.Obj(x1*x4*(x1+x2+x3)+x3) # Objective
m.options.IMODE = 3 # Steady state optimization
m.solve() # Solve
print('Results')
print('x1: ' + str(x1.value))
print('x2: ' + str(x2.value))
print('x3: ' + str(x3.value))
print('x4: ' + str(x4.value))    

GEKKO работает на всех платформах (Windows, MacOS, Linux, ARM) и с Python 2.7 и 3+. Полностью локальная опция доступна без подключения к Интернету, установив опцию «remote = False». Локальная опция в настоящее время доступна только для Windows, и мы работаем над другими версиями, такими как Linux, MacOS, ARM, для локального запуска без подключения к Интернету. Локальная версия включает в себя только бесплатные решатели, которые не требуют лицензии. По умолчанию проблема отправляется на публичный сервер, где решение вычисляется и возвращается в Python.

Хотя этот вопрос конкретно касается решения нелинейного программирования на Python, я также выделю несколько других типов проблем, которые GEKKO может решить, и некоторые ресурсы для оптимизации обучения. GEKKO также решает смешанные целочисленные и дифференциальные алгебраические уравнения и имеет несколько предварительно запрограммированных объектов для расширенного управления (аналогично DMC, RMPCT и т. Д.). Режимы работы включают в себя сверку данных, оптимизацию в реальном времени, динамическое моделирование и нелинейный прогностический контроль.

Я преподаю два курса по оптимизации (оптимизация дизайна и динамическая оптимизация ) и разместил материал курса в Интернете. Курс динамической оптимизации предлагается каждый год, начиная с января, и мы используем пакет GEKKO Python (и MATLAB) для курса. GEKKO является расширением пакета APMonitor Optimization Suite, но интегрировала моделирование и визуализацию решения непосредственно в Python. В ссылках APMonitor и GEKKO приведены примеры типов приложений, которые можно решить с помощью этого пакета. GEKKO разработан в рамках исследовательского гранта Национального научного фонда № 1547110 .

Как насчет scipy.fmin_slsqp?

http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fmin_slsqp.html

PyGMO содержит несколько решателей, предоставляя им одинаковый интерфейс. IPOPT и scipy slsqp включены, если вы компилируете код и загружаете / устанавливаете сторонний код самостоятельно.

В качестве бонуса, параллельное использование решателя стало действительно простым (мультистарт) с помощью класса архипелага!

Есть cvxmod , обертка Python вокруг выпуклой программы оптимизации Стивена Бойда. Это часть пакета Sage .

fmincon теперь можно использовать из Python через платформу OpenOpt, опционально с плотной / разреженной автоматической дифференциацией FuncDesigner http://openopt.org/fmincon

$\to$ $\to$

Достаточно ли прыгать в бассейне через scipy для ваших нужд? Если он возвращает локальный минимум, а не глобальный минимум, вы можете изменить количество итераций и / или применить границы.

Как насчет CMA-ES? Он имеет привязки Python и хорошо подходит для невыпуклых, нелинейных задач оптимизации, и я использовал его довольно редко: https://www.lri.fr/~hansen/cmaesintro.html

Установка через пипс:

pip install cma

Вот пример кода с их сайта:

import cma
help(cma)  # "this" help message, use cma? in ipython
help(cma.fmin)
help(cma.CMAEvolutionStrategy)
help(cma.CMAOptions)
cma.CMAOptions('tol')  # display 'tolerance' termination options
cma.CMAOptions('verb') # display verbosity options
res = cma.fmin(cma.Fcts.tablet, 15 * [1], 1)
res[0]  # best evaluated solution
res[5]  # mean solution, presumably better with noise

Поскольку MATLAB имеет JIT-компилятор, а CPython еще нет (по крайней мере, пока pypy не получит полную поддержку numpy). Похоже, вам нужен бесплатный решатель, который превосходит коммерческий продукт fmincon. Не слишком ли это много?

Среди коммерческих решателей НЛП IIRC до сих пор только snopt предоставил API-интерфейс Python (хотя это довольно уродливо).

Какие решатели OpenOpt вы пробовали? Сколько переменных и ограничений у вас в невыпуклой задаче?

Вы можете попробовать IPOPT через OpenOpt / Funcdesigner API без установки на сервер OpenOpt Sage (обратите внимание на рисунок «переключение с sage на python»).

$10^{300}(x-0.1)^2 + 10^{-300}(y-0.2)^2$$(x,y) = (1,1)$

для решения глобальных проблем вас могут заинтересовать http://openopt.org/interalg и другие глобальные решатели openopt (http://openopt.org/GLP) для локальной оптимизации. openopt также предлагает множество решателей: http://openopt.org / NLP

Здесь стоит упомянуть, что Google Ceres Solver на самом деле является очень мощным нелинейным оптимизатором, который используется во многих проектах.

Здесь также доступна оболочка для Python: https://github.com/rll/cyres

KNITRO имеет интерфейсы Python и MATLAB, среди других. Думайте об этом как о замене FMINCON, но гораздо более эффективной и более дорогой. https://www.artelys.com/en/optimization-tools/knitro#doc-tab .

Я пользователь KNITRO, но никак не связан с продуктом.