Пакет программ для ограниченной оптимизации?

21

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

\arg min_{u} f (u, x)

$\arg \min_u f(u,x)$

при условии

c (u, x) = 0

$c(u,x) = 0$

a \leq d (u, x) \leq b

$a \le d(u,x) \le b$

где $u$ - вектор переменных проектирования, $x$ - вектор переменных состояния, а $c(u,x)$ - ограничение равенства (обычно PDE). Нижние и верхние ограничения $a$ и $b$ могут быть пространственно-переменными.

Какие пакеты могут обрабатывать системы этой формы?

pde optimization nonlinear-programming Шон Фарли
источник

1

Отредактированная версия не похожа на проблему оптимизации с ограничением по рамкам. Задача оптимизации с ограничением на ячейки будет иметь

a \leq u \leq b

$a \leq u \leq b$ в качестве ограничения. Есть

u

$u$ должен быть функцией

x

$x$ ? Является ли

c

$c$ линейным в

u

$u$ ? Если это не так, это дважды дифференцируемо? Является

f

$f$ выпукло в

u

$u$ ? Это дважды дифференцируемо в

u

$u$ ? Наконец,

\arg min_{u}

$\arg \min_{u}$ обозначает множество точек в

u

$u$ в которых достигается минимальное значение

f

$f$ . Вы имеете в виду

min_{u}

$\min_{u}$ вместо этого?

Джефф Оксберри

d (u, x) = u

$d(u,x) = u$ является одним частным случаем, но эта более общая форма на самом деле распространена на практике. Вы всегда можете ввести дополнительные переменные, если ваш метод может работать только с ограничениями непосредственно на

u

$u$ . Нас, как правило, больше интересует значение

u

$u$ при котором достигается минимум, чем минимальное значение

f

$f$ . Шон добавил тег [pde], так что вы можете получить некоторую регулярность от этого. Он не указал, была ли система гиперболической или нет, поэтому не будем предполагать. Давайте не будем предполагать, что

f

$f$ является выпуклым, поскольку это часто не так.

Джед Браун

Это весьма характерно для привлечь или упорядочению, поэтому мы не должны принимать два производных.

f

$f$

L^{1}

$L^1$

W^{1, 1}

$W^{1,1}$

Джед Браун

@JedBrown: это имеет смысл; было странно видеть упомянутое «ограничение блока» без, ну, в общем, явного ограничения блока. Для типов проблем, о которых вы говорите (проблемы проектирования, проблемы управления), определенно более интересны, но проблемы оптимизации обычно задаются с использованием нотации , а наборы их решений описываются с помощью нотации .

u

$u$

m i n

$min$

\arg min

$\arg \min$

Джефф Оксберри

Может быть полезно указать, на каком языке / среде вы моделируете PDE. Это может ограничить выбор оптимизаторов.

Доминик

18

Я решил радикально отредактировать свой ответ, основываясь на некоторых комментариях.

Я не использовал TAO. Из рассмотрения документации кажется, что единственный способ, которым TAO может решить ограниченные задачи оптимизации (исключая особый случай только рамочных ограничений), состоит в том, чтобы преобразовать задачу в вариационное неравенство, используя условия Каруша-Куна-Такера (KKT) , которые необходимы при квалификации ограничений (тип, который я обычно вижу, это условие точки Слейтера ), и достаточны при выпуклости цели и ограничений (в более общем случае - тип 1). Если $f$ Если он невыпуклый, то формулировка вариационного неравенства с использованием условий KKT НЕ эквивалентна исходной задаче оптимизации, поэтому, строго говоря, если вам нужен глобальный оптимум для задачи оптимизации, вы не должны выражать его как вариационное неравенство. В любом случае было бы трудно найти глобальный оптимум для оптимизации с ограничением по PDE (см. Ниже), поэтому, возможно, игнорирование этой детали хорошо. Учитывая то, что сказал Вольфганг, я бы скептически относился к использованию TAO; Я уже настроен скептически, потому что он не реализует методы решения нелинейных программ (НЛП) как НЛП, а не вариационные неравенства.

Я не эксперт по оптимизации с ограничением PDE; коллеги и сотрудники шахты работают над проблемами оптимизации, связанными с ODE. Я знаю, что для навязчивых формулировок Ларри Биглер (и другие) будет использовать методы коллокации, чтобы дискретизировать PDE и сделать его очень большим, разреженным НЛП, а затем он решит его, используя методы внутренней точки. Чтобы действительно решить проблему с глобальной оптимальностью, вам также необходимо генерировать выпуклые релаксации, но, насколько я знаю, этот подход не используется, потому что проблемы оптимизации, связанные с PDE, приводят к таким большим НЛП, что было бы трудно решить их глобальная оптимальность. Я упоминаю эти детали только потому, что формулировка проблемы сильно влияет на выбор пакета решения. Для неинтрузивных формулировок повторные решения PDE дают информацию о градиенте для алгоритмов оптимизации.

Некоторые люди, которые изучают проблемы оптимизации, связанные с ODE, используют аналогичный подход, заключающийся в дискретизации проблемы с использованием коллокации и численного метода, а затем ослаблении результирующей НЛП для получения выпуклой формулировки, используемой в алгоритме глобальной оптимизации. Альтернативный подход к оптимизации с ограничением ODE состоит в том, чтобы ослабить проблему и затем дискретизировать ODE, что является подходом, принятым в моей лаборатории. Можно было бы ослабить некоторые классы проблем оптимизации, связанных с PDE, но я не знаю какой-либо существующей работы, проделанной над этой проблемой. (В какой-то момент это был потенциальный проект в моей лаборатории.)

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

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

IPOPT - это программа для определения внутренних точек с открытым исходным кодом, разработанная Андреасом Вехтером из IBM. Это очень качественный код. Как решатель изнутри, он лучше подходит для целевых функций с большими разреженными матрицами Якоби и будет полезен для оптимизации с ограничением по PDE.
SNOPT - это коммерческий решатель последовательного квадратичного программирования, который является еще одним высококачественным кодом. Это лучше для целевых функций с небольшими, плотными якобиевыми матрицами, поэтому я не ожидаю, что это будет полезно для оптимизации с ограничением по PDE, но вы можете попробовать.
NLopt - это небольшой открытый исходный код, написанный Стивеном Джонсоном в MIT, который содержит базовые реализации ряда алгоритмов нелинейной оптимизации. Все алгоритмы должны быть адекватными для решения связанных задач.
fmincon В Matlab реализован ряд алгоритмов (включая внутреннюю точечное и последовательное квадратичное программирование) для нелинейной оптимизации
GAMS и AMPL являются коммерческими языками моделирования, используемыми для формулирования задач оптимизации, и содержат интерфейсы для большого числа решателей нелинейного программирования. Я знаю, что у GAMS есть пробная версия, которую можно использовать для небольших проблем, и экземпляры проблем также можно отправлять на сервер NEOS для решения.

Однако возможно, что дискретизация может быть дифференцирована только один раз по отношению к переменным решения, и в этом случае вы должны использовать прогнозируемый наибольший спуск или какой-либо другой метод оптимизации первого порядка при вычислении локального решения. Поскольку многие исследования сосредоточены на проблемах, где могут использоваться методы второго порядка (и когда вы можете их использовать, их превосходные свойства сходимости делают их лучшим выбором), я не смог найти много реализаций наискорейшего спуска, которые не были бы решениями. к домашним задачам. GNU Scientific Library имеет реализацию, но это только для демонстрационных целей. Вы, вероятно, должны были бы написать свою собственную реализацию.

Если проблема является непрерывной только по отношению к переменным решения, то вы можете использовать прямые методы для ее локального решения. Существует отличный обзор прямых методов Колды, Льюиса и Торсона . Наиболее широко известным из этих методов является симплекс-алгоритм Нелдера-Мида . Не гарантируется сходство к локальному минимуму в нескольких измерениях, но в любом случае оно нашло значительное практическое применение.

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

Джефф Оксберри
источник

4

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

Вольфганг Бангерт
источник

3

Другой альтернативой является OPT ++ . Он поддерживает линейные и нелинейные ограничения с помощью эффективного нелинейного решателя внутренних точек, обеспечивает контроль точности функций (если требуется численное дифференцирование), контроль размеров шагов и т. Д. Я обычно оптимизирую большие неявные функции (например, FEM), где эти типы элементы управления могут быть полезны.

Barron
источник

Не могли бы вы рассказать, почему OPT ++ является хорошим пакетом для использования? Есть ли у вас (или ваших коллег) какой-либо опыт с этим?

Джефф Оксберри

Чтобы быть ясным, у меня нет причин говорить, что OPT ++ превосходит любой из тех, что вы перечислили ранее, потому что у меня нет никакого опыта с ними (хотя я отметил несколько из них, чтобы проверить). Но у меня есть опыт работы с OPT ++, и я нашел его подходящим для моих нужд. Он поддерживает линейные и нелинейные ограничения с помощью эффективного нелинейного решателя внутренних точек, обеспечивает контроль точности функций (если требуется числовое дифференцирование), контроль размеров шагов и т. Д. Я обычно оптимизирую большие неявные функции (например, FEM), где эти типы элементы управления могут быть полезны.

Бэррон

2

@ Баррон: ты должен был указать это в своем ответе для начала. :)

JM

2

Если проблема сформулирована как проблема взаимодополняемости, вы можете использовать TAO (Инструментарий для расширенной оптимизации). Некоторые из методов в TAO, такие как метод сокращенного пространства (вариант метода активного набора), в настоящее время доступны как часть SNES в PETSc ( SNESVI ).

Джунгхо Ли
источник

1

МИНУТЫ модуль CERNLIB (давно портирован ROOT ) использует преобразование на входном пространстве для визуализации ограничивает окно в пространство , где они работают и , таким образом , может быть обработан без особых случаев (по стоимости некоторой скорости, конечно). $[-\infty,+\infty]$

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

dmckee
источник

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

Джефф Оксберри

1

Как отметил @Geoff Oxberry, несколько пакетов позволяют найти локальное решение. Если вы хотите иметь возможность сравнить эти разные решатели NLP для одной и той же проблемы, вы можете использовать RobOptim .

Хотя RobOptim изначально разрабатывался с учетом проблем оптимизации робототехники, он подходит для любых задач нелинейной оптимизации. Он предоставляет простой интерфейс C ++ с плагинами для нескольких решателей NLP (например, Ipopt, NAG). Если вы не можете предоставить градиенты, вычисление с конечной разностью может быть выполнено автоматически.

Это открытый исходный код, поэтому вы можете проверить исходный код на GitHub: https://github.com/roboptim/

Примечание: я один из разработчиков этого проекта.

BENČ
источник

1

Следует отметить, что другие ответы описывают решатели , а не рамки. Легче найти приемлемую основу ( драйвер ), чем хороший решатель,

Deer Hunter

@DeerHunter Когда вы ищете решатель для решения данной проблемы, часто сложно априори определить, какой решатель найдет лучшее решение и / или будет самым быстрым. Вы говорите о «хорошем решателе», но это действительно зависит от того, что вы решаете: не существует единственного «лучшего общего» решателя. Более того, API-интерфейсы решателя, как правило, сильно отличаются друг от друга, поэтому очень полезно использовать хорошую среду, которая позволяет легко переключаться с одного решателя на другой. Речь шла о «программных пакетах для ограниченной оптимизации», и фреймворки также попадают в эту категорию.

BenC

1

Вот частичный список пакетов оптимизации с ограничением по PDE.

Dolfin Adjoint является частью FEniCS FEM:

http://dolfin-adjoint.org/

ROL, MOOCHO, Sundance являются частями Trilinos:

https://github.com/trilinos/trilinos/tree/master/packages/rol/

https://github.com/trilinos/trilinos/tree/master/packages/Sundance/

http://trilinos.org/packages/moocho/

Пример PYOMO для оптимизации по PDE:

https://software.sandia.gov/trac/pyomo/browser/pyomo/trunk/examples/dae

В руководстве TAO приводятся примеры решения задач оптимизации, связанных с PDE:

http://www.mcs.anl.gov/petsc/petsc-3.5/docs/tao_manual.pdf

denfromufa
источник

1

Добро пожаловать в SciComp.SE! Просто предоставление ссылки (как бы это ни было полезно) не очень хороший ответ; см. meta.stackexchange.com/questions/8231 . Не могли бы вы подробнее остановиться на этом (язык вычислений, какие ограничения можно устранить, какие методы реализованы и т. Д.)?

Кристиан Клэйсон

Я согласен с @ChristianClason. Существенно разрабатываются решатели для программного обеспечения оптимизации с ограничением по PDE; тем не менее, этот ответ по существу не дает представления о том, какие алгоритмы эти пакеты на самом деле реализуют.

Джефф Оксберри

0

В APM MATLAB и APM Python пакеты могут решить крупномасштабные (100,000 переменные) систем уравнений смешанного Integer Дифференциальных Алгебраическими. Программное обеспечение доступно в виде веб-службы для коммерческого или академического использования. Если вы решаете систему PDE, вы можете один раз дискретизировать ее, чтобы получить ее в форме DAE или ODE, чтобы перевести ее на язык моделирования APMonitor. Язык моделирования использует решатели APOPT , BPOPT, IPOPT, SNOPT и MINOS.

Джон Хеденгрен
источник

1

В этом и будущих ответах, в которых упоминается ваше программное обеспечение, сообщите о своей принадлежности в качестве разработчика APMonitor. Смотрите FAQ для деталей о нашей политике раскрытия.

Джефф Оксберри

Джефф, спасибо за совет. Я начал работать на платформе APMonitor в 2004 году в качестве аспиранта в Техасском университете в Остине. Сейчас мы используем его в нашей исследовательской группе в Университете имени Бригама Янга для управления процессами и оптимизации ( apm.byu.edu/prism ) биологических, химических, аэрокосмических и других применений. Я делаю это свободно доступным для коммерческих или академических пользователей.

Джон Хеденгрен

Пакет программ для ограниченной оптимизации?

Ответы: