Почему IPOPT сходится быстрее при использовании ограничений пути вместо границ переменных?

Я использую GPOPS-II (к сожалению, коммерческое программное обеспечение для оптимизации) для решения задачи оптимизации траектории самолета. GPOPS-II преобразовывает проблему в проблему НЛП, которая впоследствии решается IPOPT, решателем НЛП.

Пытаясь решить свою проблему, я ограничиваю высоту полета самолета. Ставлю верхнюю границу 5500 м по высоте. Теперь я могу сделать это двумя способами. Прежде всего, я могу установить прямую верхнюю границу высоты переменной состояния в 5500 м. Для этого IPOPT требуется примерно 1000 итераций и 438 секунд, пока не будет найдено оптимальное решение. Во-вторых, я могу наложить ограничение пути на высоту переменной состояния 5500 м. Одновременно ослабляю прямую границу государственной переменной высоты до 5750 м. Эти формулировки задач логически эквивалентны, но не математически: на этот раз IPOPT занимает всего 150 итераций и 240 секунд, чтобы прийти к точно такому же оптимальному решению.

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

Мои вопросы следующие:

  1. Чем отличаются математические формулировки ограничений и ограничений пути в методе внутренней точки?
  2. Почему установка границы ограничения пути на 5500 м не замедляет сходимость так же, как ограничение переменной замедляет сходимость?

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

P.s. Оптимальное решение находится вблизи границы ограничения высоты 5500 м; в оптимальном решении самолет должен достичь h = 5500 м в последний момент времени, и, как следствие, он пролетит около этой высоты за некоторое время до t_f.


optimization convergence ipopt boundary convex-optimization
person Sam    schedule 11.12.2019    source источник
comment
Может просто невезение: другой путь решения. Обычно границы лучше, чем явные ограничения, поскольку они уменьшают проблему.   -  person Erwin Kalvelagen    schedule 11.12.2019
comment
Я тоже так думал изначально. Я узнал об этом только из-за того, что дурачился и случайно. Дело в том, что я просто не понимаю, чем одно ограничение будет отличаться от другого в алгоритме внутренней точки: алгоритм преобразует все ограничения в барьер стоимости, верно?   -  person Sam    schedule 12.12.2019
comment
Одна модель о многом не говорит. Вот модель, на которую я смотрю прямо сейчас: верхние границы как ограничения: 40 секунд, как правильные верхние границы: 13 секунд. Это немного экстремально, но демонстрирует мою точку зрения.   -  person Erwin Kalvelagen    schedule 12.12.2019
comment
Теперь я вижу, что забыл добавить, что оптимальное решение требует, чтобы самолет летел рядом с границей; в последний момент он должен достичь высоты 5500 м. Может быть, это проливает новый свет на то, что я пытался объяснить об алгоритме, пытающемся обойти границы ограничений?   -  person Sam    schedule 13.12.2019

Ответы (1)


arrow_upward
-1
arrow_downward

Я нашел ответ на свой первый вопрос в этом Почта. Я думал, что IPOPT одинаково обрабатывает ограничения пути и границы переменных. Оказывается, что «Единственными ограничениями, которым Ipopt гарантированно удовлетворяет на всех промежуточных итерациях, являются простые верхние и нижние границы для переменных. Любое другое линейное или нелинейное ограничение равенства или неравенства не обязательно будет выполняться до тех пор, пока решающая программа не закончит схождение в конечном итерация (если она может достичь точки, удовлетворяющей условиям завершения) ".

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

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

person Sam    schedule 19.12.2019