Нелинейное программирование
- Автор метода
- Jorge Nocedal & Stephen Wright
- Год
- 2006
- Тип
- Continuous mathematical optimization
- Семейство
- Mathematical programming
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Нелинейное программирование (НЛП) — это раздел математической оптимизации, занимающийся задачами, в которых целевая функция или хотя бы одно ограничение нелинейны.
Всесторонне формализованное Хорхе Носедалом и Стивеном Райтом в их основополагающем тексте 2006 года, НЛП включает градиентные алгоритмы — в том числе последовательное квадратичное программирование (SQP), методы внутренней точки и квазиньютоновские подходы — для нахождения локально или глобально оптимальных решений непрерывных задач принятия решений, возникающих в инженерии, экономике и естественных науках.
Интуиция метода
Представьте себе спуск по холмистой, покрытой туманом местности, оставаясь при этом внутри огороженной области. Вы не можете видеть весь рельеф, поэтому вы чувствуете уклон под ногами (градиент), корректируете направление шага, чтобы спускаться вниз, и при каждом движении проверяете, не пересекли ли вы ограждение (ограничения). Если ограждение изгибается или холмы перекрываются, простые прямолинейные пути не сработают — вы должны изгибать свой путь. Нелинейное программирование формализует именно этот процесс, заменяя интуитивную ходьбу по холмам математически строгими правилами размера шага и направления.
История
Теоретические основы нелинейного программирования восходят к условиям KKT, выведенным Карушем (1939) и Куном и Таккером (1951). Практические алгоритмы ускорились в 1960–1980-х годах с развитием методов SQP, расширенных лагранжевых подходов и квазиньютоновских обновлений, включая BFGS (1970). Второе издание книги Носедала и Райта «Численная оптимизация» 2006 года стало определяющим справочником, синтезирующим теорию сходимости, фреймворки линейного поиска и доверительной области, а также методы внутренней точки в связное современное изложение.
Когда применять
Используйте нелинейное программирование, когда целевая функция или ограничения не могут быть линеаризованы без существенной потери точности, а переменные решения являются непрерывными. Типичные применения включают инженерное проектирование с ограничениями физических законов, оптимизацию портфеля с нелинейными мерами риска и регрессию с нелинейными формами моделей. Ключевые предположения заключаются в том, что f и c по крайней мере дважды непрерывно дифференцируемы (для градиентных решателей) и что выполняются квалификации ограничений. Когда переменные являются целочисленными, применяются расширения смешанно-целочисленного нелинейного программирования (MINLP). Для выпуклых задач методы внутренней точки гарантируют глобальную оптимальность; для невыпуклых задач существуют только локальные гарантии.
Ограничения и замечания
- Невыпуклые задачи предлагают только гарантии локальной оптимальности; глобальные решения требуют дополнительных стратегий глобального поиска.
- Требует, чтобы целевая функция и ограничения были гладкими (по крайней мере, дифференцируемыми); негладкие задачи требуют специализированных субдифференциальных методов.
- Вычислительная стоимость существенно возрастает с увеличением размера задачи, когда требуется точное вычисление гессиана.
- Квалификации ограничений могут не выполняться (например, в вырожденных допустимых точках), что приводит к потере теоретического обоснования условий KKT.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Обрабатывает широкий класс реальных задач, где линейные или квадратичные аппроксимации недостаточны.
- Зрелая алгоритмическая теория с хорошо изученными гарантиями сходимости для выпуклых случаев.
- Эффективные градиентные решатели (SQP, внутренняя точка) на практике масштабируются до тысяч переменных.
- Единая лагранжева структура естественным образом учитывает смешанные ограничения-равенства и неравенства.
Применение
- Строительная и аэрокосмическая инженерия: минимизация веса при ограничениях на напряжения и деформации.
- Управление портфелем: максимизация ожидаемой доходности при нелинейном бюджете дисперсии (риска).
- Проектирование химических процессов: оптимизация выхода реактора при термодинамических ограничениях и ограничениях безопасности.
- Машинное обучение: обучение нейронных сетей и ядерных моделей с помощью решателей НЛП без ограничений или с ограничениями.
- Энергетические системы: задачи оптимального потока мощности в диспетчеризации электросетей с нелинейными физическими ограничениями.
Как это работает
Как это работает
Аналитик определяет скалярную целевую функцию f(x), которую нужно минимизировать или максимизировать по переменным решения x в R^n, вместе с ограничениями-равенствами c_i(x) = 0 и ограничениями-неравенствами c_j(x) >= 0. Определение того, какие ограничения активны в потенциальном решении, и выполняются ли условия регулярности (квалификации ограничений), является критически важным на этом этапе и определяет, какая теория оптимальности применима.
Формула
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}Условия Каруша-Куна-Таккера (KKT) предоставляют необходимые условия первого порядка для локального оптимума. Они требуют стационарности лагранжиана, дополнительной нежёсткости для множителей неравенств (lambda_j c_j = 0), двойственной допустимости (lambda_j >= 0) и прямой допустимости. Алгоритмы итеративно строят итерации, которые удовлетворяют этим условиям всё более строго, при этом условия достаточности второго порядка подтверждают, что стационарная точка действительно является локальным минимумом.
Формула
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}На каждой итерации k алгоритм вычисляет направление поиска p_k — обычно с помощью квазиньютоновской аппроксимации B_k гессиана (например, BFGS) или точной системы вторых производных — и длину шага alpha_k, удовлетворяющую условиям Вольфе или Армихо. Методы SQP решают квадратичную подзадачу для p_k, в то время как методы внутренней точки добавляют барьерные члены для обработки ограничений-неравенств и направляют итерации к допустимой внутренней области.
Формула
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)Завершение происходит, когда как норма градиента лагранжиана, так и максимальное нарушение ограничений падают ниже заданных допусков (epsilon и delta). Поскольку НЛП обычно невыпукло, алгоритмы могут сходиться к локальным оптимумам; при необходимости глобальной оптимальности рекомендуются многократные перезапуски из разных начальных точек или стратегии глобального поиска (метод ветвей и границ, мультистарт).
Формула
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \deltaЧастые ошибки
- Игнорирование квалификаций ограничений и слепое применение условий KKT в вырожденных или недопустимых точках приводит к ложным решениям.
- Использование плохо масштабированных переменных вызывает плохо обусловленные аппроксимации гессиана и медленную или неудачную сходимость.
- Принятие первого найденного локального минимума без многократных перезапусков в невыпуклых условиях может значительно упустить глобальный оптимум.
- Конечно-разностные аппроксимации градиента вносят численную ошибку; аналитическое или автоматическое дифференцирование настоятельно предпочтительнее.
Часто задаваемые вопросы
Является ли каждая линейная программа также нелинейной программой?
Да. Линейное программирование — это частный случай НЛП, где как целевая функция, так и все ограничения являются аффинными. Однако ЛП допускает симплекс-метод и алгоритмы внутренней точки, которые используют линейность и гораздо более эффективны, чем общие решатели НЛП; использование общего решателя НЛП для ЛП расточительно, но математически корректно.
Когда я могу быть уверен, что точка KKT является глобальным минимумом?
Когда НЛП выпукло — то есть f выпукла, а допустимое множество является выпуклым множеством — любая точка KKT является глобальным минимумом. Для невыпуклых задач эта гарантия не действует, и точка KKT является только локальным минимумом (при условиях достаточности второго порядка). В противном случае необходимы методы глобальной оптимизации, такие как метод ветвей и границ или выпуклые релаксации.
В чем разница между методами SQP и методами внутренней точки?
SQP итеративно решает подзадачи квадратичного программирования, которые локально аппроксимируют НЛП, и часто предпочтителен для задач малого и среднего размера с большим количеством активных ограничений. Методы внутренней точки (барьерные) остаются строго внутри допустимой области и, как правило, лучше масштабируются для больших разреженных задач. Оба сходятся сверхлинейно при соответствующих условиях регулярности.
Похожие методы
Источники
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
ISBN: 978-0-387-30303-1Скопировано.