Некрасова М.Г. Методы оптимизации - файл n1.doc

приобрести
Некрасова М.Г. Методы оптимизации
скачать (3013.5 kb.)
Доступные файлы (1):
n1.doc3014kb.22.08.2012 14:29скачать

n1.doc

1   2   3   4   5   6   7   8   9   ...   12

Вопросы к главе 5


 

1.    Дайте определение функции многих переменных.

2.    Приведите примеры функций многих переменных, используемых в экономике.

3.    Что называется графиком функции двух переменных? Приведите примеры.

4.    Сформулируйте определение множества (линии) уровня функции двух переменных. Может ли множество уровня функции двух переменных не быть линией?

5.    Опишите взаимосвязь между градиентом функции двух переменных и ее линией уровня.

6.    Перечислите основные свойства градиента функции.

7.    Дайте определение возрастающей (убывающей) функции многих переменных.

8.    В каком случае функция является вогнутой?

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

10.         Дайте определение экстремума функции двух переменных.

11.         Сформулируйте достаточные условия максимума и минимума функции двух переменных.

Глава 6. МНОГОМЕРНАЯ БЕЗУСЛОВНАЯ ГРАДИЕНТНАЯ ОПТИМИЗАЦИЯ

6.1. Концепция методов

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

Определение. Активными называют ограничения, на границе которых находится решение.

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

Замечание. Ограничения типа равенств всегда активные.

Величина шага х в рекуррентном соотношении



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

,

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

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

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

В отличие от других рассмотренных выше вычислительных мето­дов поисковые методы оптимизации содержат неформально (т.е. субъ­ективно) задаваемые па­раметры, которые су­щественно влияют на эффективность поиска, вследствие чего один и тот же метод может дать совершенно различные траектории поиска. По­этому для всех методов, рассматриваемых далее, на рис. 39  приводится лишь одна из возможных траекторий: 1 – оптимум; 2 – траектория метода градиента; 3 – траектория метода тяжелого шарика; 4 – траектория метода наискорейшего спуска; 5 – траектория метода сопряженных градиентов; 6 – начальные точки траектории. Кроме того, для всех приве­денных траекторий выбраны различные начальные условия, с тем, чтобы не загромождать построения. На этом и последующих ри­сунках зависимость R1, х2) приведена в виде линий уровня на плоскости в координатах х1 - х2.

6.2. Метод градиентного спуска

Метод градиента в чистом виде формирует шаг по перемен­ным как функцию от градиента f(х) в текущей точке поиска. Про­стейший алгоритм поиска min f(x) записывается в векторной форме следующим образом:



или в скалярном виде:



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

Поиск каждой новой точки состоит из двух этапов:

1) оценка градиента f(x) путем вычисления частных произ­водных от f(х) по каждой переменной хj;

2) рабочий шаг по всем переменным одновременно.

Величина h сильно влияет на эффективность метода. Большей эффективностью обладает вариант метода, когда шаг по каждой переменной определяется направляющими косинусами градиента



где

В этом случае величина рабочего шага не зависит от величи­ны модуля градиента, и ею легче управлять изменением h. В рай­оне оптимума может возникать значительное "рыскание", поэто­му используют различные алгоритмы коррекции h.

Наибольшее распространение получили следующие алгоритмы:

1)              (без коррекции);

2)            

3)            

где  - угол между градиентами на предыдущем и текущем шаге; 1 и 2 – заданные пороговые значения выбираются субъективно (например, 1=/6, 2=/3).

Вдали от оптимума направление градиента меняется мало, поэтому шаг можно увеличить (второе выражение), вблизи от оптимума направление резко меняется (угол между градиентами f(x) большой), поэтому h сокращается (третье выражение).

Для оценки частных производных используются разностные методы:

          алгоритм с центральной пробой



          алгоритм с парными пробами



где gi – пробный шаг по i переменной, выбираемый достаточно малым для разностной оценки производной.

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

Условием окончания поиска может являться малость модуля градиента f(x), т. е. |gradf(x)| < .

Пример 60. Требуется найти минимум функции f(x, y) = x3+2y2-3x-4y, завершив вычисления при погрешности = 0,01,  выбрав начальное приближение х(0) = - 0,5  и у(0) = -1,  коэффициент шага h = 0.1.

Решение. Необходимые начальные данные приведены в условии задачи. Для вычислений выберем работу с шагом без коррекции  (h = const).

Найдем частные производные функции:



Следовательно,



Значит,

Переменные определяются по формулам:

Результаты вычислений занесем в табл. 17

Таблица 17

п

x

y

f(x, y)

df/dx

df/dy

|grad f|

1

2

3

4

5

6

7

1

-0,500

-1,000

7,3750

-2,2500

-8,0000

8,3104

2

-0,275

-0,200

1,6842

-2,7731

-4,8000

5,5435

3

0,002

0,280

-0,9701

-3,0000

-2,8800

4,1586

4

0,302

0,568

-2,5061

-2,7258

-1,7280

3,2274

5

0,575

0,741

-3,4003

-2,0085

-1,0368

2,2603

   Продолжение табл. 17

1

2

3

4

5

6

7

6

0,776

0,844

-3,8120

-1,1947

-0,6221

1,3469

7

0,895

0,907

-3,9508

-0,5958

-0,3732

0,7031

8

0,955

0,944

-3,9877

-0,2651

-0,2239

0,3471

9

0,981

0,966

-3,9967

-0,1111

-0,1344

0,1744

10

0,992

0,980

-3,9990

-0,0453

-0,0806

0,0925

11

0,997

0,988

-3,9997

-0,0183

-0,0484

0,0517

12

0,999

0,993

-3,9999

-0,0073

-0,0290

0,0299

13

1,000

0,996

-4,0000

-0,0029

-0,0174

0,0177

14

1,000

0,997

-4,0000

-0,0012

-0,0104

0,0105

15

1,000

0,998

-4,0000

-0,0005

-0,0063

0,0063

 

В последней точке модуль градиента меньше заданной погрешности

(0,0063 < 0.01), поэтому поиск прекращается.

Итак, и

Пример 61. Требуется найти минимум функции  завершив вычисления при погрешности = 0,5,  выбрав начальное приближение х(0) = 0  и у(0) = 0,  коэффициент шага h = 0.1.

Решение. Необходимые начальные данные приведены в условии задачи. Для вычислений выберем работу с шагом без коррекции  (h = const).

Результаты вычислений занесем в табл. 18.

    Таблица 18

п

x1

x2

f(x1, x2)

df/d x1

df/d x2

|grad f|

1

0,0000

0,0000

1,0000

1,0000

1,0000

1,4142

2

-0,1000

-0,1000

0,8487

0,6187

0,4187

0,7471

3

-0,1619

-0,1419

0,8045

0,4143

0,1706

0,4480

4

-0,2033

-0,1589

0,7880

0,2895

0,0604

0,2957

5

-0,2323

-0,1650

0,7806

0,2077

0,0123

0,2080

6

-0,2530

-0,1662

0,7768

0,1515

-0,0072

0,1517

7

-0,2682

-0,1655

0,7748

0,1118

-0,0138

0,1126

8

-0,2794

-0,1641

0,7737

0,0831

-0,0146

0,0844

9

-0,2877

-0,1626

0,7731

0,0621

-0,0131

0,0635

10

-0,2939

-0,1613

0,7727

0,0466

-0,0110

0,0479

 

В последней точке модуль градиента меньше заданной погрешности, поэтому поиск прекращается.

Итак, и

Рассмотрим градиентный метод минимизации функции с дроблением шага.

Пусть f(x) выпуклая дифференцируемая во всем n-мерном пространстве функция и требуется найти её точку минимума х*. Выбрав произвольное начальное приближение , построим последовательность

                                                (9)

где величины hk (параметрические шаги) выбираются достаточно малыми для того, чтобы выполнялось условие

                                                    (10)

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

или                        (11)

( - заданное достаточно малое число), после чего полагают

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

Пример 62. Минимизировать функцию методом градиентного спуска с дроблением шага, завершив вычисления при

Решение. Выбрав начальное приближение х(0) = (0, 0) и h0 = 1, построим последовательность (9), записывая результаты вычислений в табл. 19

Таблица 19

k





f(x(k))





hk



Примечание

0

0

0

1

1

1

1

 

Условие (10) нарушено. Уменьшаем h0 в 2 раза.

 

-1

-1

3,1353

-

-

 

 

 

 

0

0

1

1

1

0,5

 

Условие (10) нарушено. Уменьшаем h0 в 2 раза.

 

-0,5

-0,5

1,118

-

-

 

 

 

1

0

0

1

1

1

0,25

 

Условие (10) выполнено

-0,25

-0,25

0,794

0,1065

-0,3935

0,25

0,4077

2

-0,2766

-0,1516

0,7741

0,0984

0,0451

0,25

0,1082

Условие (10) выполнено

3

-0,3012

-0,1629

0,7725

0,0262

-0,023

0,25

0,0349

Точность достигнута(11)

 

Итак,

Пример 63. Минимизировать функцию f(x, y) = x3+2y2-3x-4y, методом градиентного спуска с дроблением шага, завершив вычисления при

Решение. Выбрав начальное приближение х(0) = (-0.5, -1) и h0 = 0.1, построим последовательность (9), записывая результаты вычислений в табл. 20.

Таблица 20

k

x

y

f(x, y)





hk



Примечание

1

2

3

4

5

6

7

8

9

1

-0,5000

-1,0000

7,3750

-2,2500

-8,0000

0,1

 

 

-0,2750

-0,2000

1,6842

-2,7731

-4,8000

0,1

5,5435

Условие (10) выполнено

2

0,0023

0,2800

-0,9701

-3,0000

-2,8800

0,1

4,1586

Условие (10) выполнено

Продолжение табл. 20

1

2

3

4

5

6

7

8

9

3

0,3023

0,5680

-2,5061

-2,7258

-1,7280

0,1

3,2274

Условие (10) выполнено

4

0,5749

0,7408

-3,4003

-2,0085

-1,0368

0,1

2,2603

Условие (10) выполнено

5

0,7757

0,8445

-3,8120

-1,1947

-0,6221

0,1

1,3469

Условие (10) выполнено

6

0,8952

0,9067

-3,9508

-0,5958

-0,3732

0,1

0,7031

Условие (10) выполнено

7

0,9548

0,9440

-3,9877

-0,2651

-0,2239

0,1

0,3471

Условие (10) выполнено

8

0,9813

0,9664

-3,9967

-0,1111

-0,1344

0,1

0,1744

Условие (10) выполнено

9

0,9924

0,9798

-3,9990

-0,0453

-0,0806

0,1

0,0925

Условие (10) выполнено

10

0,9969

0,9879

-3,9997

-0,0183

-0,0484

0,1

0,0517

Условие (10) выполнено

11

0,9988

0,9927

-3,9999

-0,0073

-0,0290

0,1

0,0299

Точность достигнута(11)

 

Итак,

6.3. Метод наискорейшего спуска

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

В текущей точке вычисляется  grad f(x), и затем в направлении градиента ищется min f(x). Практически это может быть осуществлено любым методом одномерной оптимизации (поиск по одному направлению – направление градиента), наиболее часто используется сканирование до первого локального минимума по направлению grad f(x).

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

В ряде случаев можно повысить скорость выхода в район оптимума предъявлением невысоких требований к точности поиска min по направлению (задается величиной h – шагом поиска по направлению). Условием окончания может являться малость модуля градиента  функции f(x): |grad f(x)| < . Можно также использовать и малость приращений по переменным в результате шага, но только в том случае, если на данном шаге мы «проскочили» оптимум, иначе может оказаться, что малость шага обусловлена не близостью к оптимуму, а малостью коэффициента пропорциональности шага h.

В ряде случаев используют уменьшение шага поиска оптимума по направлению после каждой смены направления. Условием окончания поиска в этом случае является достижение заданной малой величины шага.

Метод наискорейшего спуска отличается от градиентного спуска способом определения величины hk, которая находится из условия:

                               (*)

Такой выбор hk обеспечивает максимально возможное уменьшение функции f(x) вдоль направления ее антиградиента  в точке х(k).

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

Пример 64. Минимизировать функцию  методом наискорейшего спуска, завершив вычисления при , i = 1, 2.

Решение. Найдем частные производные:

1-й шаг. Положим х(0) = (0, 0), тогда



Функцию Ф0(h) находим, используя соотношение (*). Для нахождения точки минимума функции Ф0(h) используем метод Пауэлла. Поскольку шаг h изменяется в пределах 0 < h < 1, то за первоначальное значение примем h = 0,  а h = 0.5. Таким образом находим h0 = 0.22.

Значит, х(1) =(0, 0) – 0.22(1, 1) = (-0.22, -0.22).

Вычислим значение производных: f(-0.22, -0.22) = (0.204, -0.236). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

2-й шаг. Составим функцию:



Снова используем метод Пауэлла, полагая h = 0 и h = 0.5, находим h1 = 0.32.

Значит, х(2) =(-0.22,-0.22) – 0.32(0.204, -0.236) = (-0.2853, -0.1445).

Вычислим значение производных: f(-0.2853, -0.1445) = (0.08, 0.0726). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

3-й шаг. Составим функцию:



Используем метод Пауэлла, полагая h = 0 и h = 0.5, находим h2 = 0.24.

Значит, х(3) =(-0.2853-0.240.08, -0.1445-0.240.0726) = (-0.3045, -0.1619).

Вычислим значение производных: f(3)) = (0.0182, -0.0205). Условия завершения поиска выполняются, поэтому требуемая точность достигнута и



Пример 65. Минимизировать функцию f(x, y) = x3+2y2-3x-4y, методом градиентного спуска с дроблением шага, завершив вычисления при

Решение. Найдем частные производные:

1-й шаг. Положим х(0) = (0, 0), тогда



Функцию Ф0(h) находим, используя соотношение (*). Для нахождения точки минимума функции Ф0(h) используем метод Пауэлла. Поскольку шаг h изменяется в пределах 0 < h < 1, то за первоначальное значение примем h = 0,  а h = 0.5. Таким образом находим h0 = 0.281.

Значит, х(1) =(0, 0) – 0.281(-3, -4) = (0.843, 1.124).

Вычислим значение производных: f(1)) = (-0.8681, 0.496). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

2-й шаг. Составим функцию:



Снова используем метод Пауэлла, полагая h = 0 и h = 0.5, находим h1 = 0.2121.

Значит, х(2) =(0.833+0.21210.8681, 1.124-0.21210.496) = (1.0171, 1.0188).

Вычислим значение производных: f( х(2)) = (0.1035, 0.0752). Условия завершения поиска не выполняются, следовательно, переходим к следующему шагу.

3-й шаг. Составим функцию:



Используем метод Пауэлла, полагая h = 0 и h = 0.5, находим h2 = 0.2196.

Значит, х(3) =(1.0171-0.21960.1035, 1.0188-0.21960.0752) = (0.9944, 1.002).

Вычислим значение производных: f(3)) = (-0.0335, 0.008). Условия завершения поиска выполняются, поэтому требуемая точность достигнута и



Вопросы к главе 6

Метод градиента

1.        Что называется градиентом функции двух переменных?

2.        Как оценивается эффективность поиска градиентным методом?

3.        Какой алгоритм коррекции шага предпочтительнее вблизи оптимума?

4.        Почему в районе оптимума величина шага х убывает при использовании

алгоритма ?

5.        Исходя из определения gradf(x) как вектора, указывающего направление

возрастания функции, что лучше искать: min или max?

Метод наискорейшего спуска

1.        В чем основные отличия метода наискорейшего спуска от метода градиента?

2.        По какому направлению осуществляется поиск из каждой текущей точки при

поиске minf(x)?

3.        Как вычисляется градиент f(x) в методе наискорейшего спуска?

4.        Каковы условия окончания поиска?

5.        Можно ли методом наискорейшего спуска найти maxf(x)?

Глава 7. КРИТЕРИИ ОПТИМАЛЬНОСТИ В ЗАДАЧАХ

С ОГРАНИЧЕНИЯМИ

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

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

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

минимизировать f(x1, x2, …, xN)

при ограничениях hk(x1, x2, …,xN) = 0, k = 1, … K.

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

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

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

Для начала рассмотрим случай для функции двух переменных.

Определение. Условным экстремумом функции z=f(x, y) называется экстремум этой функции, достигнутый при условии, что переменные x и y связаны уравнением (x, y)=0 (уравнение связи).

Отыскание условного экстремума можно свести к исследованию на обычный экстремум так называемой функции Лагранжа u=f(xy)+(x, y), где - неопределенный постоянный множитель.

Необходимые условия экстремума функции Лагранжа имеют вид



Из этой системы из трех уравнений можно найти неизвестные x, y, .

Для того, чтобы  найти наибольшее и наименьшее значения функции в замкнутой области, надо:

1) найти стационарные точки, расположенные в данной области, и вычислить значения функции в этих точках;

2) найти наибольшее и наименьшее значения функции на линиях, образующих границу области;

3) из всех найденных значений выбрать наибольшее и наименьшее.

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

минимизировать f(x1, x2, …, xN)

при ограничениях h1(x1, x2, …,xN) = 0

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

минимизировать L(x; v) = f(x) – vh1(x).

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

Пусть при заданном значении v = v0 безусловный минимум функции L(x; v) по x достигается в точке x = x0 и x0 удовлетворяет уравнению h1(x0) = 0. Тогда x0 минимизирует f(x1, x2, …, xN) с учетом h1(x1, x2, …,xN) = 0, поскольку для всех значений x, удовлетворяющих h1(x1, x2, …,xN) = 0, h1(x) = 0 и min L(x; v) = min f(x).

Необходимо подобрать значение v = v0 таким образом, чтобы координата точки безусловного минимума x0 удовлетворяла равенству   h1(x1, x2, …,xN) = 0. Это можно сделать, если, рассматривая v как переменную, найти безусловный минимум функции L(x; v) = f(x) – vh1(x) в виде функции v, а затем выбрать значение v, при котором выполняется равенство h1(x1, x2, …,xN) = 0.

Пример 66. Минимизировать

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

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

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

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



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



которая оказывается положительно определенной. Это означает, что L(x; v) – выпуклая функция х. Следовательно, координаты  определяют точку глобального минимума. Оптимальное значение v находится путем подстановки значений  в уравнение 1 + х2 = 2, откуда 2v +v/2 = 2 или v0 = 4/5. Таким образом, условный минимум достигается при



При решении задачи из Примера 66 мы рассматривали L(x; v) как функцию двух переменных х1 и х2 и, кроме того, предполагали, что значение параметра v выбрано так, чтобы выполнялось ограничение. Если же решение системы



в виде явных функций v получить нельзя, то значения x и v находятся путем решения следующей системы, состоящей из N + 1 уравнений с N + 1 неизвестными:



Для нахождения всех возможных решений данной системы можно использовать численные методы поиска. Для каждого из решений (x0; v0) следует вычислить элементы матрицы Гессе функции L, рассматриваемой как функция х, и выяснить, является ли эта матрица положительно определенной (локальный минимум) или отрицательно определенной (локальный максимум).

Пример 67. Минимизировать

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

Решение.





Эта система трех уравнений с тремя неизвестными имеет два решения:



Матрица Гессе функции L(x; v), рассматриваемой как функция х, равна



Вычислив элементы матрицы H для каждого из двух решений, находим, что матрица

 положительна определена,

а матрица  отрицательно определена.

Следовательно, (x(2); v2) соответствует максимуму функции L, рассматриваемой как функция х; оптимальное решение



Заметим, что (x(1); v1) соответствует минимуму L.

Здесь необходимо подчеркнуть, что если мы рассмотрим L как функцию трех переменных, а именно переменных х1, х2 и v, то точки (x(1); v1) и (x(2); v2) не окажутся точками минимума или максимума L как функции x и v. На самом деле они являются седловыми точками функции L(x; v).

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

минимизировать f(x)

при ограничениях hk(x) = 0,   k = 1, 2, …, K.

Функция Лагранжа принимает следующий вид:



Здесь v1, v2, …, vk – множители Лагранжа, т.е. неизвестные параметры, значения которых необходимо определить. Приравнивая частные производные L по х к нулю, получаем следующую систему N уравнений с N неизвестными:



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



Решение расширенной системы, состоящей из N + K уравнений с N + K неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением.

Для некоторых задач расширенная система N + K уравнений с N + K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что на практике такие задачи встречаются достаточно редко.

7.3. Экономическая интерпретация множителей Лагранжа

Множители Лагранжа рассматривались выше как параметры, значения которых выбираются таким образом, чтобы выполнялись ограничения задачи. С экономической точки зрения множители Лагранжа интерпретируются как неявные (теневые) цены ресурсов, определяемых ограничениями; оптимальные значения множителей Лагранжа играют важную роль в анализе чувствительности решений. Для того, чтобы пояснить эту интерпретационную схему, рассмотрим следующую оптимизационную задачу с двумя переменными и одним ограничением в виде равенства:

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

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

где постоянная величина b1 характеризует наличие некоторого ресурса.



Предположим, что стационарная точка функции L соответствует глобальному минимуму.



Пусть  - оптимальное значения множителя Лагранжа, а  - оптимальное решение задачи. Далее, пусть минимум функции L(x; v1) при  достигается в точке , причем  и . Очевидно, что оптимальные значения  связаны функциональной зависимостью с величиной b1, задающей границу наличия дефицитного ресурса.

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

.                                                  (14)

Дифференцируя обе части ограничений , получаем

.                                                (15)

Умножим обе части равенства (15)  на  и вычтем из (14):

.                                          (16)

Так как х0 и  удовлетворяют уравнениям (12) и (13), равенство (16) приводится  к виду

.                                                              (17)

Таким образом, из формулы (17) следует, что скорость изменения оптимального значения f, вызываемого изменением b1, определяется оптимальным значением множителя Лагранжа . Другими словами, величина изменения оптимального значения целевой функции,

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

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

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

минимизировать f(x)                                                        (18)

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



Определение. Ограничение в виде неравенства  называется активным, или связывающим, в точке , если  и неактивным, или несвязывающим, если .

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

Кун и Таккер построили необходимые и достаточные условия оптимальности для задач нелинейного программирования, исходя из предположения о дифференцируемости функций f, gj, hk. Эти условия оптимальности, широко известны как условия Куна - Таккера, можно сформулировать в виде задачи нахождения решения некоторой системы нелинейных уравнений и неравенств, или, как иногда говорят, задачи Куна – Таккера.

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

Найти векторы , удовлетворяющие следующим условиям:

                                       (21)



Прежде всего, проиллюстрируем условия Куна – Таккера на примере.

Пример 68. Минимизировать

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

Решение. Записав данную задачу в виде задачи нелинейного программирования (18) – (20), получим



Уравнение (21), входящее в состав условий Куна – Таккера, принимает следующий вид:



Неравенства (22) и уравнения (23) задачи Куна – Таккера в данном случае записываются в виде



Уравнения (24), известные как условие дополняющей нежесткости принимают вид



Заметим, что на переменные u1, u2 накладывается требование неотрицательности, тогда как ограничение на знак v1 отсутствует.

Таким образом, для данной задачи условия Куна – Таккера записываются в следующем виде:



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

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

Теорема 1. Необходимость условий Куна – Таккера.

Рассмотрим задачу нелинейного программирования (18) – (20). Пусть f, g, h – дифференцируемые функции, а х* - допустимое решение данной задачи. Положим  I={j| gj(x*)=0}. Далее пусть  при при k=1, . . . , K линейно независимы. Если х* - оптимальное решение задачи нелинейного программирования, то существует такая пара векторов (u*, v*), что (x*, u*, v*) является решением задачи Куна – Таккера (21) – (25).

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

      все ограничения в виде равенств и неравенств содержат линейные функции;

      все ограничения в виде неравенств содержат вогнутые функции, все ограничения-равенства – линейные функции, а также сществует по крайней мере одна допустимая точка х, которая расположена во внутренней части области, определяемой ограничениями-неравенствами. Другими словами, существует такая точка , что

Если условие линейной независимости в точке оптимума не выполняется, то задача Куна – Таккера может не иметь решения.

Пример 69. Минимизировать

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













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

Так как  то I = {1, 3}. Далее



Видно, что векторы  и  линейно зависимы, т.е. условие линейной независимости в точке х* = (1, 0) не выполняется.

Запишем условия Куна – Таккера и проверим, выполняются ли они в точке (1, 0). Условия (21), (24) и (25) принимают следующий вид:



При х* = (1, 0) из уравнения (26) следует, что u2 = -4, тогда как уравнение (27) дает u2 = 0. Следовательно, точка оптимума не является точкой Куна – Таккера.

Замечание. Нарушение условия линейной независимости не обязательно означает, что точка Куна – Таккера не существует.

Теорему Куна – Таккера можно использовать для доказательства того, что заданная допустимая точка, удовлетворяющая условию линейной независимости, не является оптимальной, если она не удовлетворяет условиям Куна – Таккера. С другой стороны, если в этой точке условия Куна – Таккера выполняются, то нет гарантии, что найдено оптимальное решение нелинейной задачи. В качестве примера рассмотрим следующую задачу нелинейного программирования.

Пример 70. Минимизировать f(x) = 1 – x2

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

Решение. Здесь

Запишем условия Куна – Таккера:



Так как ограничения содержат линейные функции, условие линейной независимости выполняется во всех допустимых точках. Видно, что х = 3 – точка оптимума. Рассмотрим допустимое решение х = 2. Для того, чтобы доказать его неоптимальность, проверим выполнение полученных условий Куна – Таккера. Из уравнений (28), (29) следует, что  u1 = u2 = 0; однако значения х = 2,         u1 = u2 = 0 не удовлетворяют исходному уравнению. Следовательно, по теореме 1, точка   х = 2 не может быть оптимальной.

С другой стороны, решение х = u1 = u2 = 0 удовлетворяет системе всех полученных первоначально неравенств и уравнений и, следовательно, определяет точку Куна – Таккера, однако оптимальным не является. Согласно теореме 1, условия Куна – Таккера должны выполняться в точке оптимума х = 3. Нетрудно проверить, что решение х = 3, u1 = 0, u2 = 6 удовлетворяет условиям Куна – Таккера.

Следующая теорема устанавливает условия, при выполнении которых точка Куна – Таккера автоматически соответствует оптимальному решению задачи нелинейного программирования.

Теорема 2. Достаточность условий Куна – Таккера

Рассмотрим задачу нелинейного программирования

минимизировать f(x)

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



Пусть целевая функция f(x) выпуклая, все ограничения в виде неравенств содержат вогнутые функции gj(x), j=1, … , J, а ограничения в виде равенств содержат линейные функции hk(x), удовлетворяющие условиям Куна – Таккера





то х* - оптимальное решение задачи нелинейного программирования.

Замечание. Если условия теоремы 2 выполняются, то нахождение точки Куна – Таккера обеспечивает получение оптимального решения задачи нелинейного программирования. Теорему можно использовать для доказательства оптимальности данного решения.

Пример 71. Минимизировать

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



Решение. С помощью теоремы 2 докажем, что решение  является оптимальным. Имеем



Так как матрица Hf(x) положительно полуопределена при всех х, функция f(x) оказывается выпуклой. Первое ограничение в виде неравенства содержит линейную функцию g1(x), которая одновременно является как выпуклой, так и вогнутой. Для того, чтобы показать, что функция g2(x) является вогнутой, вычислим



Поскольку матрица  отрицательно определена, функция g2(x) является вогнутой. Функция h1(x) входит в линейное ограничение в виде равенства. Следовательно, все условия теоремы 2 выполнены; если мы покажем, что х* = (1, 5) – точка Куна – Таккера, то действительно установим оптимальность решения х*.

Условия Куна – Таккера для данного примера имеют вид



Точка х* = (1, 5) удовлетворяет полученным ограничениям и, следовательно, является допустимой. Полученные уравнения принимают следующий вид:



Положив v1 = 0, получим u2 = 0.1 и u1 = 2.2. Таким образом, решение х* = (1, 5),   u* = (2.2, 0.1) и v1 = 0 удовлетворяет условиям Куна – Таккера. Поскольку условия теоремы 2 выполнены, то х* = (1, 5) – оптимальное решение задачи. Заметим, что существуют также и другие значения u1, u2, v1, которые удовлетворяют условиям Куна – Таккера, построенным для задачи.

Замечание.

1) Для встречающихся на практике задач условие линейной независимости, как правило, выполняется. Если в задаче все функции дифференцируемы, то точку Куна – Таккера следует рассматривать как возможную точку оптимума. Таким образом, многие из методов нелинейного программирования сходятся к точке Куна – Таккера.

2) Если условия теоремы 2 выполнены, точка Куна – Таккера в то же время оказывается точкой глобального минимума. К сожалению, проверка достаточных условий весьма затруднительна, и, кроме того, прикладные задачи часто не обладают требуемыми свойствами. Следует отметить, что наличие хотя бы одного нелинейного ограничения в виде равенства приводит к нарушению предположений теоремы 2.

3) Достаточные условия, установленные теоремой 2, можно обобщить на случай задач с невыпуклыми функциями, входящими в ограничения в виде неравенств, невыпуклыми целевыми функциями и нелинейными ограничениями-равенствами.

7.6. Условия существования седловой точки

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

Определение. Говорят, что функция f(x, y) имеет седловую точку (х*, у*), если   для всех х и у.

В определении седловой точки подразумевается, что при х* минимизирует функцию f(x, y*) по всем х,  а у* максимизирует функцию f(x*, y) по всем у.

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

Минимизировать f(x)

при ограничениях hk(x) = 0, k = 1, … , K.

Определим функцию Лагранжа



Предположим, что при v = v* минимум L(x; v*) достигается в точке х = х*, причем hk(x*)=0. В соответствии с методом множителей Лагранжа известно, что х* есть оптимальное решение задачи нелинейного программирования. Можно показать, что  (x*; v*) – седловая точка функции Лагранжа, т. е.



при любых x и v.

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

минимизировать f(x)

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

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

Задача Куна – Таккера о седловой точке формулируется следующим образом: найти такой вектор (x*; u*), чтобы неравенство



имело место для всех  и всех x S. При этом



Теорема 3. Достаточные условия оптимальности

Если (x*;u*) – решение задачи Куна – Таккера о седловой точке, то х* есть оптимальное решение задачи нелинейного программирования.

Замечание.

1) В теореме 3 не требуется выполнения предположений о выпуклости или вогнутости соответствующих функций.

2) Теорема 3 не опирается на условие регулярности допустимой области.

3) Учет нелинейных ограничений-равенств в виде hk(x*)=0,  k=1, . . . , K, можно осуществить путем переопределения функции Лагранжа:  Здесь  переменные vk, k=1, …, K, не ограничены по знаку.

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

Рассмотрим условие существования седловых точек. Несколько теорем устанавливают необходимые условия оптимальности, которые гарантируют существование седловой точки при отсутствии предположения о дифференцируемости соответствующих функций. Однако формулировки таких теорем базируются не предположениях о выполнении условий регулярности допустимой области и выпуклости функций.
1   2   3   4   5   6   7   8   9   ...   12


Вопросы к главе 5
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации