Смекни!
smekni.com

Нелинейное программирование (стр. 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=u0 безусловный минимум функ­ции L(x,u) по х достигается в точке

и
удовлетворяет урав­нению
. Тогда, как нетрудно видеть, x0 минимизирует (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.