Нелинейное программирование (стр. 1 из 7)

Южно-Уральский Государственный Университет

Кафедра АиУ

реферат на тему:

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

Выполнил: Пушников А. А., ПС-263.

Проверил: Разнополов О.А.

Челябинск – 2003.

Оглавление

1. Постановка задачи нелинейного программирования

2. Критерии оптимальности в задачах с ограничениями

2.1. Задачи с ограничением в виде равенств

2.2. Множители Лагранжа

3. Условия Куна-Таккера

3.1. Условия Куна-Таккера и задача Куна-Таккера

3.2. Интерпретация условий Куна-Таккера

3.3. Теоремы Куна-Таккера

4. Функции нескольких переменных

4.1. Методы прямого поиска

4.1.1.Метод поиска по симплексу (S2 - метод)

4.1.2.Метод поиска Хука-Дживса

1. Постановка задачи нелинейного программирования.

В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=(

), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств

, i=1,2,…,m (1)

а переменные

, т.е. компоненты вектора х, неотрицательны:

(2)

Иногда в формулировке задачи ограничения (1) имеют противоположные знаки неравенств. Учитывая, однако, что если

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

2. Критерии оптимальности в задачах с ограничениями.

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

имеет место в стационарной точке х=2. Но если задача минимизации решается с учетом ограничения , то будет найден условный минимум, которому соответствует точка x=4. Эта точка не является стационарной точкой функции f, так как (4)=4. Далее исследуются необходимые и достаточные условия оптимальности решений задач с ограничениями. Изложение начинается с рассмотрения задач оптимизации, которые содержат только ограничения в виде равенств.

2.1. Задачи с ограничениями в виде равенств

Рассмотрим общую задачу оптимизации, содержащую несколько ограничений в виде равенств:

Минимизировать

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

, k=1,…,n

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

Пример 1

Минимизировать

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

Исключив переменную

, с помощью уравнения , получим

оптимизационную задачу с двумя переменными без ограничений

min

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

задать в виде

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

2.2. Множители Лагранжа

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

Рассмотрим задачу минимизации функции n переменных с учетом одного ограничения в виде равенства:

Минимизировать

(3)

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

(4)

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации:

минимизировать L(x,u)=f(x)-u*h(x) (5)

Функция L(х;u) называется функцией Лагранжа, u— неизвестная постоянная, которая носит название множителя Лагранжа. На знак uникаких требований не накладывается.

Пусть при заданном значении u=u⁰ безусловный минимум функции L(x,u) по х достигается в точке

и удовлетворяет уравнению . Тогда, как нетрудно видеть, x⁰ минимизирует (1) с учетом (4), поскольку для всех значений х, удовлетворяющих (4), и L(x,u)=minf(x).

Разумеется, необходимо подобрать значение u=u° таким образом, чтобы координата точки безусловного минимума х° удовлетворяла равенству (4). Это можно сделать, если, рассматривая uкак переменную, найти безусловный минимум функции (5) в виде функции u, а затем выбрать значение u, при котором выполняется равенство (4). Проиллюстрируем это на конкретном примере.

Пример 2

Минимизировать

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

=0

Соответствующая задача безусловной оптимизации записывается в следующем виде:

минимизировать L(x,u)=

-u

Решение. Приравняв две компоненты градиента Lк нулю, получим

Для того чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L(х;u), рассматриваемой как функция х,

,

которая оказывается положительно определенной. Это означает, что L(х,,u) — выпуклая функция х. Следовательно, координаты

, определяют точку глобального минимума. Оптимальное значение uнаходится путем подстановки значений и в уравнение =2, откуда 2u+u/2=2 или . Таким образом, условный минимум достигается при и и равен minf(x)=4/5.