Имя материала: Исследование операций в экономике

Автор: И.Н. Мастяева

5.2. методы безусловной оптимизации

 

Задачей безусловной оптимизации функции нескольких переменных будем называть задачу, в которой требуется найти

шіп f (x), x є En (5.2)

при отсутствии ограничений на x, где x = (x^...^)- вектор управляемых переменных, f - скалярная целевая функция.

 

Определение. Решением, или точкой минимума, задачи безусловной оптимизации будем называть такой вектор x * є En, что

f (x*) < f (x) для всех x є En, и писать

f (x*) = mm f (x),x є En (5.3)

Определение. Вектор S называется направлением спуска функции f (х) в точке х, если существует такое 8 > 0, что f (х + AS) < f (х), для всех Л є (0;8).

Сущность рассматриваемых в данном разделе методов решения задачи (5.2) состоит в построении последовательности точек х13 х2,... хк

принадлежащих En, монотонно уменьшающих значение функции f (х).

Такие методы называют методами спуска.

 

Алгоритм метода спуска.

Начальный этап. Задать х1 є En - начальную точку, є> 0- параметр

окончания счета; положить k=1. Основной этап

Шаг 1. В точке хк проверить условие окончания счета; если оно выполняется, то положить х* = хк и остановиться.

Шаг 2. В точке хк выбрать направление спуска Sk.

Шаг 3.  Положить   хк+1 = хк +ЛkSk,  где   Лк - длина шага вдоль

направления Sk, положить k=k+1 и перейти к шагу 1.

Различные методы спуска отличаются друг от друга способом выбора направления спуска Sk и шага вдоль этого направления Лк.

Естественно, что трудоемкость вычисления величины   Лк следует

согласовывать с трудоемкости определения направления спуска Sk.

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

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

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

Методы второго порядка, в которых используются первые и вторые производные функции f(х), т.е. значения f (х),Vf(х),H(х), где H(х)-матрица Гессе, элементами которой являются частные производные второго порядка функции f (х).

Методы оптимизации квадратичных функций.

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

Метод скорейшего спуска - метод Коши - метод первого порядка.

 

Методы безусловной оптимизации, в которых в качестве направления поиска берется градиент функции f (x), называются градиентными. Градиентные методы являются методами первого порядка. Таким образом, последовательность точек генерируется градиентным методом в соответствии с формулой:

xk+1 = xk -ХкVf (xk) (5.4)

где   Ak -   параметр,   характеризующий   величину   шага вдоль

направления. Величина шага Ak может выбираться разными способами.

Если значение параметра  Лк   вычисляется путем решения задачи

одномерной оптимизации, то градиентный метод называется методом скорейшего спуска, или методом Коши.

 

Алгоритм метода Коши.

 

Начальный этап. Выбрать x1 - начальную точку, а > 0- параметр окончания счета; положить k=1. Основной этап.

Шаг 1. Если ||Vf (xk )|| < а, то x * = xk, остановиться.

Шаг2.Положить Sk =-Vf (xk), вычислить Ak = argmin f (xk + ASk),

положить k=k+1 и перейти к шагу 1.

Пример 5.3. Найти минимум функции методом Коши.

f (x) = 10 xf +10 x1 x2 + 3x22

Начальный этап. Пусть x1 = (-0,6;1),а = 0,1; k = 1.

Vf (x ) = (20 x1 +10 x2;10 x1 + 6 x2) Основной этап.

Шаг 1. Вычислим Vf (x1) = (-2;0), так как ||Vf (x1 )|| = 2 > а, переходим к шагу 2.

Шаг2. Положим S1 = -Vf (x1) = (2;0), вычислим Л1 = arg min f (x1 + AS 1) = 0,05, x2 = (-0,5;1) ,положим k=2 и перейдем к шагу 1.

Шаг 1. Vf (x2) = (0;1), т.к. ||Vf (x2 )|| = 1 > а, переходим к шагу 2.

Шаг 2. Положим S 2 =-Vf (x2) = (0;-1), вычислим A2 = argminf(x2 +AS2) = 0,167,x3 = (-0,5;0,167), положим k=3 и перейдем к шагу 1.

Результаты всех вычислений приведены в таблице, из которой следует, что значение функции f (x) становится меньше а = 0,1 на 11-й итерации, а значение нормы градиента уменьшается в 5/6 раза каждые две итерации (см. таблицу).

Скорость сходимости метода Копій является довольно низкой, хотя на   каждой    итерации    обеспечивается    выполнение неравенства

Домашнее задание 5.2.

 

Решить задачу безусловной оптимизации методом Коши с точностью є=0,1. Решение сопроводить геометрической интерпретацией

2 2

-x1 + 6x2 -2x1 - 3x2 + 3x1x2 — max

22

6x1 + 4x2 - x1   - 0,5x2  - x1x2 — max

22

3x1 - 2x2 - 0,5x1 - x2 + x1x2 — max

22

-4x1 + 8x2 - x1 -1.5x2 + 2x1x2 — max

22

x1 + 4x2 - x1 - 3x2 + 2x1x2 — max

22

-2x1 + x2 - 3x1 - 2x2 + x1x2 — max

22

x1 - 2x2 - x1 - 3x2 - x1x2 — max

22

8.         3x1 + 6x2 - x1 - 2x2 + 2x1x2 — max

22

9. -3x1 + 2x2 - 2x1 - x2 + 2x1x2 — max

22

10. 4x1 + x2 - 3x1 - x2 + x1x2 — max

5.3. Методы условной оптимизации

В дальнейшем будем рассматривать следующую задачу:

 

f (x ) — max (5.5) на множестве P:

P = {x є En : g, (x) < 0, i = ХЇк, x} > 0, j = и) (5.6) где f (x) и gt (x) - нелинейные функции.

 

При решении задач нелинейного программирования ввиду нелинейности  функции   gt (x)   выпуклость  допустимого множества

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

 

Определение. Решением или точкой максимума задачи условной оптимизации будем называть такой вектор x є P a En, что f (x ) > f (x)

для всех x є P, т.е. f (x ) = max f (x).

 

Определение. Будем называть направление S ^ 0 возможным в точке x є P, если существует такое действительное число /?0 > 0, что

(xk +eS) єP для всех в є (0,в0).

 

Определение. Вектор Sk будем называть возможным направлением подъема функции f (x) в точке Xk є P , если существует такое действительное число в0 > 0, что для всех в є (0, в0):

(xk +eSk)єp и f+eSk)>f(xk).

 

Методы решения задачи условной оптимизации можно представить как итерационный процесс, в котором исходя из начальной точки x 0 є P, получают последовательность точек xk єP, монотонно увеличивающих значения функции f (x). Это так называемые методы подъема. Элементы этой последовательности точек определяются следующим образом: xk+1 = xk +ekSk,

где Sk - возможное направление подъема функции в точке хк, авк находится при решении задачи одномерной оптимизации:

f (хк + PSк ) — max .

Если точка хк - внутренняя точка множества P, т.е. для i = 1,m : g(хк) <0, то всякое направление в ней является возможным (пример на рис. 5.2).

Если точка хк - граничная точка области P, то возможные направления определяются ограничениями g(хк) = 0 (направление S на рис. 5.3 возможным не является).

Прежде чем определять направление подъема функции f (х) в точке

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

 

Общая схема методов условной оптимизации.

Начальный этап. Задать є > 0 и выбрать начальную точку х0 єP. Основной этап.

Шаг 1. Выбрать Sk (k-я итерация) - возможное направление подъема функции f (х) в точке хк. Если такого направления нет, то

х* к = хк - решение задачи. В противном случае перейти к шагу 2. Шаг 2. Положить хк+1 = хк + fiSk, где вк находим, решая задачу

f (хк + fikS к) — max

(хк +pkSk) є p

Шаг 3. Заменить k на k+1 и перейти к шагу 1.

 

Конкретные методы условной оптимизации различаются способом выбора возможного направления подъема Sk функции f (х) в точке хк.

Подпись:

Метод Зойтендейка.

 

Пусть требуется найти максимальное значение вогнутой функции

f ((X): _

f (x ) — max

при условиях

Р = -- (5.7)

I x > 0 v '

fAx < b

> I

Характерной особенностью этой задачи является то, что ее система ограничений содержит только линейные неравенства.

Предположим также для любой допустимой точки x, что А1 x = bi и А2x < b2, где A = (A1,A2) и b = (bi,b2). Далее приводится алгоритм метода Зойтендейка для случая линейных ограничений.

 

Алгоритм метода Зойтендейка.

 

Начальный этап. Выбрать начальную точку x о є Р, для которой

А=( a, A), b=(bi, b),

А1 : А1 xо = bi, А2 : А2 xо < b2. Положить k=0. Основной этап.

Шаг 1. Для xk єР предполагаем, что А = (Ak,Ak),

b = (b, b2), A xk = b1, A xk < b2.

Шаг 2. Определить возможное направление подъема, решая следующую задачу:

ф) = (Vf (xk ),S) — max         (5.8)

при условиях:

Pk ={S: S є En, AS < 0,

Г          —)       (5.9)

 

Шаг 3. Если все <p(S) = (Vf(xk ),Sk) = 0, то x = xk - задача решена. Шаг 4. Определить рк (шаг в направлении Sk), решая задачу одномерной оптимизации:

f (xk + PSk ) — max

0<p<p

Шаг 5. Положить хк+і = хк + j3kSk, заменить к на к+1 и перейти к

шагу 1.

Пример.

f (x) = 4x1 + 6x2 + 2x1 x2 - 2x12 - 2x

2

2

—» max

Гx1 + x2 < 2 x1 + 5x2 < 5

x1 < 0

x2 < 0

Начальный этап.

Выбираем начальную точку x0 = (0,0), для которой:

4° =

 

1

(-1   0 Л

0

 

V 0 J

(0Л 40 (1

V1 5J

, b20 =

f 2 Л

V 5 J

Vf (x) = (4 + 2x2 -4x1,6 + 2x1 -4x2), положить k=0.

 

Основной этап. Итерация 1.

Шаг 1. Для x0 = (0,0) заданы 410, b10,420, b2 .

Шаг 2. Vf (x0) = (4,6).

Решаем задачу

<p(S) = (Vf(x0),S) = 4S1 + 6S2 max

при условиях

Г- S1 < 0

S 2 < 0 1 < S1 < 1 1 < S 2 < 1

При решении этой задачи получаем S 0 = (1,1), <p(S 0) = 10. Шаг 3. Так как <p(S 0) = 10 ф 0, переходим к шагу 4. Шаг 4. Решаем одномерную задачу:

f (x0 +PS0) = 10-2Р2 max

0<р<р*

5 6

Определяем р*:

о*      .  Г 2 5

 

т. е. решаем задачу:

10 - 2р2 — max

0 <р< 5

6

Очевидно, что решением является р0 = —

6

55

Шаг 5. Положить x 1 = x0 + р0S0 = (0,0) + -(1,1) = (-,-)

6          6 6

к=1 и перейти к шагу 1.

Итерация 2.

Шаг 1. Для x 1 =        A1 = (1 5) b1 = (0).

6 6

—       7 13 Шаг 2. Vf (x 1) = (-, —). Решаем задачу

7 13

—S, +  S 2 — max

3  1    3 2

при условиях

S1 + 5S 2 < 0 -1 < S1 < 1

- 1 < S 2 < 1

—        1        — 22

Решение этой ЗЛП - S1 = (1, - 5); cp(S1) = - —.

— 22

Шаг 3. Так как cp(S1) = - — ф 0, переходим к шагу 4. Шаг 4. Решаем задачу:

f (x1 +eS1) =125 + 22 в-62 в2 — max

8     15      25 0<в<в*

Определяем   в*:

. Г1/3 5/6І 5

в = шіп <        ,           > = —,

[4/5  1/5 J 12

Таким образом, решая задачу

125      22  в    62 в2

            +          в          в   — max ,

8       15 ^     25 ^        0<в<^

12

получим оптимальное значение в: в = —

1 186

55

эное значение в: в1 =

Шаг 5. Положить: —    —      —     35 24

x 2 = x 1 + в1S 1 = (—, -31). K=2 и перейти к шагу 1. Итерация 3.

—      35  24    —2

Шаг 1. Для x2 = (31,-31): A2 = (1 5) b1 = (0). Шаг 2. Vf (= (32,160)

31 31

Решаем задачу

при условиях

—S, +  S 2 — max

31 1   31 2

 

S1 +5S2 0

-1 < S1 < 1 -1 < S 2 < 1.

 

Решение:

^2 = (1; - ±).  cp{S2) = 0.

_          _*   _     35 24

Шаг 3. Так как ср( S 2) = 0, задача решена и x = x з = (—, —).

На рис. 5.4 проиллюстрирован процесс решения задачи.

 

Домашнее задание 5.3.

 

Решить задачу нелинейного программирования методом Зойтендейка. Решение проверить графически.

 

1. 3x1 - 2x2 - 0.5x1  - x2 + x1x2 — max 2x1 + x2 < 2 x1 + x2 < 2

x1, x2 > 0

22

3x1 - 2x2 - 0.5x1  - x2 + x1x2 — max

x1 < 3

x2 < 6

x1, x2 > 0

22

-4x1 + 8x2 - x1 - 1.5x2 + 2x1x2 — max

x1 + x2 < 3 x1 - x2 < 1

x1, x2 > 0

22

4.         - 4x1 + 8x2 - x1  - 1.5x2 + 2x1x2 — max

-x1 + x2 < 1 x1 < 4

x1, x2 > 0

22

5.   3x1 - 2x2 - 0.5x1  - x2 + x1x2 — max -x1 + 2x2 2 2 x1 - x2 2

x1, x2 > 0

22

- x1 + 6x2 - x1  - 3x2 - 3x1x2 — max

x1 - x2 > 0

x2 5

x1, x2 > 0

6x1 - x2 - 1.5x2 + 2x1x2 — max

-x1 + 2x2 2

x1 4

x1, x2 > 0

22

6x1 + 4x2 - x1  - 0.5x2 - x1x2 — max

x1 + 2x2 2

-2 x1 + x2 0

x1, x2 > 0

22

6x1 + 4x2 - x1 - 0.5x2 - x1x2 — max

2x1 + x2 2

x2 1

 

22

10.   6x1 + 4x2 - x1 - 0.5x2 - x1x2 — max

3x1 + 2x2 6 3x1 + x2 3

x1, x2 > 0

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |