Библиотека C ++ для нелинейной минимизации с ограничениями

9

В настоящее время я пытаюсь решить проблему нелинейной минимизации с ограничениями, реализованную в функции "fmincon" в matlab. Мои ожидания: минимизировать (fun1, x0, uB, lB, fun2), где x0 - начальное состояние, fun1 - функция, которую нужно минимизировать, uB - верхние границы, lB - нижние границы, а fun2 - функция, которая обеспечивает векторы нелинейных равенств / неравенства, как описано в http://www.mathworks.com/help/optim/ug/fmincon.htmlкак неконтролируемая функция. Эти векторы также меняются итерациями (они нелинейно зависят от x_n, n-й итерации вектора решения). В реализации Matlab они имеют форму c (x) <= 0. Это последний кусок кода, который нужно перенести с matlab на c ++, и я много пытался найти подходящую библиотеку c ++, содержащую этот алгоритм. Вот почему я ищу здесь помощь, и я был бы очень признателен, если бы вы предоставили свой опыт.

Хороший пример того, что я хочу сделать, это первый на этой странице http://www.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-examples.html#f10960?s_tid=doc_12b Единственное отличие состоит в том, что я тоже нужны границы ...

Заранее спасибо.

Питер

Питер Коттас
источник
Существует возможность использования NLOPT ab-initio.mit.edu/wiki/index.php/NLopt_C-plus-plus_Reference, но мне нужно будет рассчитать конечные различия, используя множественные вызовы для «минимизированной» оценки функции из целевой функции, и я был любезен надеяться, что об этом позаботится сам алгоритм, чтобы улучшить производительность. Моя минимизированная функция очень дорога для вычисления. Для пояснения, минимизированная функция - логарифмическая вероятность оценочной модели с исходными данными при оценке модели маркового переключения во временных рядах.
Питер Коттас
1
Вы смотрели на ответы на этот вопрос ? Если ваши требования там недостаточно учтены, вам следует отредактировать вопрос, чтобы указать на него, чтобы получить полезные рекомендации.
Кристиан Клэйсон
Спасибо, там есть некоторая полезная информация. В настоящее время я дошел до локтей в библиотеке NLOPT, так как обнаружил, что это может удовлетворить и мою проблему. Я буду держать эту тему в курсе и предоставлю решение, когда я приду к ней. Любая помощь, которая может ускорить процесс, по-прежнему ценится. Фактическая реализация, например и т. Д.
Питер Коттас
1
Несколько вопросов: 1. Является ли ваша проблема выпуклой? 2. Являются ли цель и ограничения дифференцируемыми? Если так, сколько раз? Однажды? Дважды? 3. Можете ли вы легко рассчитать эти производные, если они существуют? Было бы легко вычислить аппроксимации конечных разностей, если бы у вас не было этих доступных производных? 4. Сколько у вас переменных решения? (т. е. сколько переменных вы пытаетесь минимизировать?) Достаточно приблизительной оценки. 5. Дорожны ли оценки функций? Было бы полезно иметь всю эту информацию, чтобы дать вам лучший ответ.
Джефф Оксберри
Привет! Прежде всего, спасибо за ответ. 1. Трудно сказать, но, скорее всего, нет, потому что минимизированной функцией является логарифмическая вероятность между марковской моделью переключения оценки временных рядов в финансовом приложении и, исходя из ее характера, я предполагаю своего рода шумный результат. 2. нет 3. только с использованием конечных разностей 4. вектор решения состоит из n переменных, где n зависит от параметров требуемой модели, в общем случае от 12 до, скажем, 30 5. логарифмическая вероятность между моделью и исходными данными стоит дорого, дополнительные нелинейные неравенства подсчитать
Питер Коттас

Ответы:

2

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

Двенадцать-тридцать переменных, вероятно, находятся в верхней части того, что выполнимо методами поиска по шаблону (также называемому прямым поиском). Недавний обзорный доклад Риоса и Сахинидиса в Журнале глобальной оптимизации о методах оптимизации без производных (таких как методы поиска по шаблону) можно найти здесь , наряду с сопутствующей веб-страницей . Менее недавний обзорный документ об этих методах Колды, Льюиса и Торцзона в SIAM Review можно найти здесь . Эти методы довольно хорошо работают с дорогими оценками функций и не обязательно требуют дифференцируемости или производной информации.

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

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

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

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

Анализ, выполненный @Geoff Oxberry, важен для выбора нелинейного решателя, который будет вызываться RobOptim. Обратите внимание, что при работе с такого рода решателями настройка параметров может оказать огромное влияние на производительность, и вы все равно можете застрять в локальных минимасах (это действительно зависит от типа проблемы, с которой вы сталкиваетесь).

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

BENČ
источник