Нелинейное программирование - Nonlinear programming

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

Применимость

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

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

Определение

Пусть n , m и p - натуральные числа. Пусть X - подмножество R n , пусть f , g i и h j - действительные функции на X для каждого i в { 1 ,…, m } и каждого j в { 1 ,…, p }, с at хотя бы одно из f , g i и h j является нелинейным.

Задача нелинейной минимизации - это задача оптимизации вида

Аналогично определяется задача нелинейной максимизации.

Возможные типы набора ограничений

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

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

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

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

Способы решения проблемы

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

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

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

Для решения невыпуклых задач доступно несколько методов. Один из подходов - использовать специальные постановки задач линейного программирования. Другой метод включает использование методов ветвей и границ , где программа делится на подклассы, которые должны быть решены с помощью выпуклых (задача минимизации) или линейных аппроксимаций, которые образуют нижнюю границу общей стоимости в рамках подразделения. При последующих делениях в какой-то момент будет получено реальное решение, стоимость которого будет равна наилучшей нижней оценке, полученной для любого из приближенных решений. Это решение оптимальное, хотя, возможно, и не уникальное. Алгоритм также может быть остановлен раньше, с гарантией того, что наилучшее возможное решение находится в пределах допуска от найденной наилучшей точки; такие точки называются ε-оптимальными. Завершение до ε-оптимальных точек обычно необходимо для обеспечения конечного завершения. Это особенно полезно для больших, сложных проблем и проблем с неопределенными затратами или значениями, где неопределенность можно оценить с помощью соответствующей оценки надежности.

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

Примеры

2-мерный пример

Синяя область - допустимая область . Касание линии с допустимой областью представляет собой раствор. Линия - это наилучшая достижимая горизонтальная линия (геометрическое место с заданным значением целевой функции).

Простая задача (показанная на диаграмме) может быть определена ограничениями

х 1 ≥ 0
х 2 ≥ 0
х 1 2 + х 2 2 ≥ 1
х 1 2 + х 2 2 ≤ 2

с максимальной целевой функцией

е ( х ) = х 1 + х 2

где x = ( x 1 , x 2 ).

3-х мерный пример

Касание верхней поверхности с ограниченным пространством в центре представляет собой решение.

Еще одна простая задача (см. Диаграмму) может быть определена ограничениями

Икс 1 2 - Икс 2 2 + Икс 3 2 ≤ 2
Икс 1 2 + Икс 2 2 + Икс 3 2 ≤ 10

с максимальной целевой функцией

е ( х ) = х 1 х 2 + х 2 х 3

где x = ( x 1 , x 2 , x 3 ).

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки