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

Общая задача нелинейного программирования имеет вид:

,

(6.6.1)

где все функции предполагаются дифференцируемыми.

1. Необходимые условия минимума. Для произвольной допустимой точки введем множества индексов

, (активные ограничения неравенства)

, (все активные ограничения). (6.6.2)

Теорема 21 (Каруш-Джон). Пусть – точка локального минимума в (6.6.1), а функции непрерывно дифференцируемы в окрестности . Тогда найдутся числа не все равные 0, такие, что и

. (6.6.3)

Введем функцию Лагранжа

где , .

Выражение (6.6.3) называется условием стационарности. Его можно записать в виде

(6.6.3)

Согласно теореме 1 в точке локального минимума должны выполняться условия:

1) условия стационарности

2) условия допустимости

3) условия неотрицательности

4) условие нетривиальности ,

5) условие дополняющей нежесткости

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

Сформулируем условия, при которых можно гарантировать .

Условие регулярности. Векторы , линейно независимы.

Теорема 22. Пусть – точка локального минимума в (6.6.1), функции непрерывно дифференцируемы в окрестности , и выполнены условия регулярности. Тогда найдутся числа , такие, что

, (6.6.4)

где

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

Теорема 23. Пусть – допустимая точка, функции дважды дифференцируемы в . Пусть для некоторого выполняется (6.6.4) и для некоторого , для которого

, ,

, , (6.6.5)

, ,

выполняется неравенство

.

Тогда – точка локального минимума в задаче (6.6.1).

Пример 1. Пусть требуется решить задачу минимизации

, (6.6.6)

при ограничениях

. (6.6.7)

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

, (6.6.8)

для функции Лагранжа, записанной в виде

.

В результате получим

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

На основе условия допустимости, т.е. выполнимости ограничения (6.6.7), с учетом взаимосвязи , получим , т.е. .

Матрица вторых производных функции Лагранжа имеет вид

.

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

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

Глава 7. Основы вариационного исчисления (ВИ)

Постановка задачи, примеры и основные понятия

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

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

 

Рис. 1. Задача о брахистохроне

 

Поместим начало координат в точку и направим оси координат как показано на рис. 1. Предположим, что тело находится в момент начала падения в состоянии покоя. Из закона сохранения энергии следует, что

,

откуда для скорости имеем , и тем самым время падения (с учетом, что ) выражается интегралом

.

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

Пример 2. Найти кратчайшее расстояние между двумя точками и в плоскости , , т.е. найти функцию , при которой

принимает наименьшее значение. При этом должна удовлетворять условиям и .

В приведенных примерах отыскиваются функции , которые минимизируют функционал вида:

(7.1.1)

при граничных условиях:

, . (7.1.2)

Задача (7.1.1), (7.1.2) - так называемая простейшая задача вариационного исчисления.

Будем рассматривать функции из класса непрерывных и непрерывно дифференцируемых функций на , которые будем обозначать и соответственно. Определим нормы в и . Аналогом расстояния между двумя функциями в каждом из классов является норма разности этих функций. Понятие нормы определяется следующим образом:

в : ; (7.1.3)

в : . (7.1.4)

В качестве –окрестности функции понимают тождество

(7.1.5)

Если для функции из области определения существует окрестность такая, что

или , (7.1.6)

то называют (локальным) минимумом или максимумом. Элементы из называются также функциями сравнения.

Максимум (минимум) называется сильным, если в (7.1.6) принята норма на . Максимум (минимум) называется слабым если в (7.1.6) сравнение кривых происходит в смысле нормы .

Глобальным максимумом (минимумом) называют число для функции , если

. (7.1.7)

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

Основным элементом исследования в ВИ являются понятия первой и второй вариации функционала.

Положим и рассмотрим первую и вторую производные функции по параметру при . Величины и называются первой и второй вариацией функционала и обозначают соответственно и .

Условия и могут быть использованы при формулировке необходимых условий экстремума функционала .