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

5.2. методы безусловной оптимизации: Исследование операций в экономике, И.Н. Мастяева, 2003 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Рекомендовано Учебно-методическим объединением по образованию в области статистики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 061700 «Статистика» и другим экономическим специальностям.

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

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

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

Обсуждение Исследование операций в экономике

Комментарии, рецензии и отзывы

5.2. методы безусловной оптимизации: Исследование операций в экономике, И.Н. Мастяева, 2003 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Рекомендовано Учебно-методическим объединением по образованию в области статистики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 061700 «Статистика» и другим экономическим специальностям.