ТЕЗИСЫ ЛЕКЦИЙ И ЛАБОРОТОРНЫХ ЗАНЯТИЙ

Стр 1 из 4Следующая ⇒

ЗАДАЧИ ДОПОЛНИТЕЛЬНЫЕ ПО ТЕМЕ ТЕОРИЯ НЕЛИНЕЙНОЙ ОПТИМИЗАЦИИ

Всюду – найти все экстремумы функций! И только их: остальные, в том числе геометрические задания, не делать

БЛОК 1.

Безусловные экстремумы (БУ)

1. ,

2. ,

3. ,

4. ,

5. ,

6. ,

7. ,

10. ,

11. ,

12. .

13.

Условные экстремумы с ограничениями равенствами (УОР)

1) .

2) .

3) .

4. .

БЛОК 2.

Равенства, кроме №3.

Условные экстремумы с ограничениями неравенствами (УОН)

БЛОК 3. (Равенства – № 1, . Не надо № 5-7, 10, 18-21)

БЛОК 4.

1) f (x) = − 2x2 − 3x2 + x1 − 6 − → maxX ,

X = {x | x2 + x1 − 3 ≤ 0, 2x1 + x2 − 5 ≤ 0, x2 ≥ 0},

x1 = (1, 1), x2 = (2, 1), x3 = (1/4, 0), x4 = (0, 0);

2) f (x) = x2 + 3x1 − → minX ,

X = {x | x2 + x2 − 2x1 + 8x2 + 16 ≤ 0, x1 − x2 ≤ 5},

x1 = (1, − 4), x2 = (0, − 4), x3 = (2, − 4);

3) f (x) = 7x2 + 2x2 − x1x2 + x1 − x2 − → minX ,

X = {x | x1 + x2 ≤ 2, x1 − 3x2 ≤ 4, − 2x1 + x2 ≤ − 3},

x1 = (5/2, − 1/2), x2 = (1, − 1), x3 = (2, 0);

4) f (x) = x2/2 + x2 − 5x1 + x2 − → minX ,

X = {x | x1 + x2 − 2x3 ≤ 3, 2x1 − x2 − 3x3 ≥ − 11, x1 ≥ 0, x2 ≥ 0, x3 ≥ 0},

x1 = (1, 0, 2), x2 = (0, 0, − 1), x3 = (1, 3, 0), x4 = (2, 1, 1), x5 = (5, 0, 1);

5) f (x) = ex1+x2 + x2 − 2x2 − → minX , X = {x | x2 ≤ ln x1, x1 ≥ 1, x2 ≥ 0}, x1 = (2, ln 2), x2 = (e, 0), x3 = (1, 0);

6) f (x) = ex1+x2 + x2 + 2x1 + 2x2 − → minX ,

X = {x | x2 + x2 + x2 ≤ 18, 2x1 + x2 − x3 + 3 ≤ 0},

x1 = (− 3, 3, 0), x2 = (1, − 1, 4), x3 = (− 3, − 3, 0), x4 = (0, 0, 3);

7) f (x) = − 5x2 − 6x2 − x2 + 8x1x2 + x1 − → maxX ,

X = {x | x2 − x2 + x3 ≤ 5, x1 + 5x2 ≤ 8, x1 ≥ 0, x2 ≥ 0},

x1 = (0, 0, 0), x2 = (1, 0, 4), x3 = (3/14, 1/7, 0), x4 = (4, 0, − 11);

s) f (x) = − x2 − 2x2 + x1x2 − 26 − → maxX ,

X = {x | x2 ≤ 25, x1 + 2x2 − 5 ≤ 0, x2 ≥ 0},

x1 = (0, 0), x2 = (− 1, 2), x3 = (0, − 6), x4 = (3, 0);

9) f (x) = 10x2 + 5x2 − x1 + 2x2 − 10 − → minX ,

X = {x | 2x2 + x2 ≤ 4, x1 + x2 ≤ 8, x1 ≥ 0},

x1 = (0, 0), x2 = (1, 1), x3 = (0, − 1);

1n) f (x) = 4x2 + 3x2 + 4x1x2 − x1 + 6x2 − 5 − → minX ,

X = {x | − x2 − x2 ≥ − 3, 3x2 + x2 ≤ 4, x1 ≥ 0, x2 ≥ 0},

x1 = (0, 0), x2 = (5, 0), x3 = (1, − 1), x4 = (1, 1);

11) f (x) = x2 + 5/2x2 − x1x2 − → minX ,

X = {x | x2 − 4x1 − x2 ≤ − 5, − x2 + 6x1 − x2 ≥ 7},

x1 = (2, 1), x2 = (3, 2).

БЛОК 5. (№ 13-15 – без ограничений, №1-12 – неравенства)

1) f (x) = x1x2 − x2 − 2x2 + x1,

X = {x | x1 ∈ [0, 1], x2 ∈ [0, 1]};

2) f (x) = x3 − 4x2 + 2x1x2 − x2,

X = {x | |x1| ≤ 5, |x2| ≤ 1};

3) f (x) = x3 + x3 − 3x1x2,

X = {x | x1 ∈ [0, 2], x2 ∈ [− 1, 2]};

4) f (x) = (x1 − 5)2 + (x2 − 7)2,

X = {x | x1 + 2x2 ≤ 12, x1 + x2 ≤ 9, x1 ≥ 0, x2 ≥ 0};

5) f (x) = (x1 − 3)2 + (x2 − 5)2,

X = {x | x2 + x2 ≤ 10, 2x1 + 2x2 = 5};

6) f (x) = x1(π − x1) sin x2 + x2 cos x1, X = {x | x1 ∈ [0, π ], x2 ≥ 0};

7) f (x) = x1 + x2 + x3,

X = {x | x2 + x2 ≤ x3, x3 ≤ 1};

s) f (x) = 2x1x2 + x3,

X = {x | x2 + x2 = 1, 0 ≤ x3 ≤ 2x1 + 1};

9) f (x) = x2 − x2,

X = {x | x2 + x2 ≤ 16};

10) f (x) = x2 + x2 − 12x1 + 16x2,

X = {x | x2 + x2 ≤ 25};

11) f (x) = arctg x1 − ln x2,

X = {x | x2 + x2 ≤ 4, x1 ≥ 0, x2 ≥ 1};

12) f (x) = x1 + x2 − x3,

X = {x | x1x2x3 ≤ 1, − x1 + x2 − x3 ≤ 0};

13) f (x) = x2 + x1x2 + x2 + 3|x1 + x2 + 2|,

X = R² = E2;

14) f (x) = x2 + x2 + 2α |x1 + x2 − 1|, α > 0,

X = R² = E2;

15) f (x) = x2 + x2 + 2 max{x1, x2},

X = R² = E2.

БЛОК 6.

Ограничения равенства.

Ограничения неравенства.

ЗАНЯТИЕ № 6 – 14 марта 2013.

Глава 2. Численные методы поиска безусловного экстремума

§4. Принципы построения численных методов поиска безусловного экстремума.

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

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

Достаточно часто итерационная последовательность строиться по формуле

где – направление движения (спуска) и величина шага.

Для выполнения условия убывание функции необходимо

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

Величина шага часто определяется из условия

Сходящаяся к минимуму функции f последовательность называется «минимизирующей», а в случае сходимости , к точке , эта точка называется точкой минимума.

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

§5.1. Методы нулевого порядка в одномерном случае.

5.1.1 Постановка задачи и стратегия поиска

Большинство методов предполагает нахождение аргумента в интервале и унимодальность (т.е. наличие единственного локального минимума на этом интервале) функции.

Замечания. 1) Непрерывная строго выпуклая функция – унимодальна, 2) Методы одномерной оптимизации широко используются при нахождении шага интерационного процесса.

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

Последовательная стратегия имеет следующие способы реализации:

1. Применение квадратичной и кубической интерполяции для выбранных точек и поиска минимума построенной интерполяционной кривой в качестве текущего приближения искомого минимума.

2. Построение последовательности вложенных друг в друга интервалов, содержащих точку минимума.

Стратегия состоит из трёх этапов:

1. Выбор начального интервала.

2. Построение последовательности интервалов, содержащих минимум.

3. Проверку условия окончания процесса поиска.

Алгоритм Свенна [Swann W.H.] определения начального интервала .

1. Задать произвольно следующие параметры: номер , начальную точку , величину шага .

2. Вычислить значения функции в трёх точках: .

3. Проверить условие окончания:

- ;

- условие окончания не выполняется – перейти к шагу 4.

4. Определить величину :

- ;

5. Найти следующую точку .

6. Проверить условие убывания функции:

- ;

- k=k+1 и перейти к шагу 5;

- .

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

5.1.2 Метод равномерного поиска

Задать – начальный интервал, N – число точек, где вычисляется функция f(x). Точки – равноотстоящие. Делаем: .

5.1.3 Метод деления интервала пополам

Задать – начальный интервал, l – требуемая точность, k=0. Вычислить точки .

Сравнить эти значения в трёх точках:

1. ;

2. ;

3. .

5.1.4 Метод дихотомии

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

1. ,

2. ,

3. ,

5.1.5 Метод золотого сечения

Идея этого метода отличается от предыдущего только тем, что в качестве двух сравниваемых точек выбираются точки золотого сечения.

Определение. Золотое сечение отрезка точкой такое, что отношение всего отрезка к большей части равно отношению большей части к меньшей. Таких точек имеется две , симметричные относительно середины отрезка:

. (*)

Дополнительно точки производят золотые сечения отрезков , соответственно.

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

- ,

- .

5.1.6 Метод Фибоначчи

Идея этого метода аналогична методу золотого сечения и состоит в том, что из двух выбираемых точек одна остаётся такой точкой сравнения и для следующего интервала. Такая стратегия реализует максимальное гарантированное сокращение интервала при заданном количестве вычислений функции и претендует на оптимальность. Параметром метода является количество вычислений функции N. Точки вычисления функции находятся с использованием последовательности из N+1 числа Фибонччи.

Определение. Числа Фибоначчи определяются по формуле

Начальные конкретные значения: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

Алгоритм вычислений имеет вид:

1. найти количество вычислений N по формуле , где – N-ое число Фибоначчи, начальный интервал, допустимая длина конечного интервала, соответственно,

2. ,

3. ,

4. .

5.1.7 Метод квадратичной интерполяции (Пауэлла [Powell M.J.D.])

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

1. параметры метода: начальная точка , величина шага , – характеристики точности,

2. ,

3. ,

4. ,

5. найти ,

6. вычислить точку минимума и значение функции в этой точке: .

ЗАНЯТИЕ №7 – 21 марта 2013 – пропущено по болезни.

ЗАНЯТИЕ №8 – 28 марта 2013.

«Многомерный случай безусловных экстремумов. Методы нулевого порядка»

5.2 «Метод конфигураций (Хука-Дживса [R. Hook, T.A. Jeeves])».

Исследование ведётся от текущей базовой точки вариациями сдвигов , по координатам в обе стороны (+ и –). В случае успешного результата делается движение по вектору, идущему из старой базовой точки в новую . В случае успешного результата спуска по вектору – делается следующий аналогичный цикл. В случае неуспешного – возврат в старую точку и уменьшение параметров «координатных» и «векторных» сдвигов.

5.3 «Метод деформируемого многогранника (Нелдера-Мида [J.A. Nelder, R. Mead])».

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

Параметрами метода являются:

1. координаты вершин многогранника , где n – размерность пространства координат;

2. – параметры отражения, сжатия, растяжения, соответственно;

3. – точность решения;

4. k – номер итерации.

5. Рекомендации по использованию параметров:

6. – Нелдер и Мид;

7. – Павиани (D. Paviani);

8. – Паркинсон и Хатчисон [J.M. Parkinson, D. Hutchinson].

АЛГОРИТМ.

1. Задать параметры метода.

2. Найти «минимальную» (наилучшую) и «максимальную» и следующую по максимуму (наихудшие) вершины.

3. Найти центр тяжести всех вершин многогранника.

4. Проверить условие завершения – евклидова норма расстояний от вершин до центра < .

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

6. Проверить выполнение условий и сделать модификации вершин:

– сжатие,

– редукция.

5.4 «Метод Розенброка [H.H. Rosenbrok].

В этом методе осуществляется итеративный поиск направления убывания функции с помощью изменяемых дискретных шагов вдоль n векторов ортогонального базиса. Для удачного шага он увеличивается на следующей итерации, для неудачного – уменьшается, с помощью коэффициента. Если зашли в тупик, то строиться новый ортогональный базис. Новый базис поворачивается относительно старого вытегиванием вдоль «оврагов».

Параметрами метода являются:

1. начальная точка ;

2. – ортогональный базис;

3. – длины шагов для направлений поиска;

4. – параметры растяжения, сжатия, соответственно;

5. – точность решения;

6. N – максимальное число неудачных серий шагов по всем направлениям на одной итерации.

АЛГОРИТМ.

1. Задать параметры метода.

2. – шаг по i-му направлению.

Дэвис, Свенн и Кемпи [Davies D., Swann W.H., Campey I.G.] модифицировали метод Розенброка, применив метод одномерной оптимизации при поиске вдоль каждого направления .

5.5 «Метод сопряжённых направлений (Пауэлла [M.J.D. Powell)».

5.6 «Методы случайного поиска (Нелдера-Мида [J.A. Nelder, R. Mead])».

ЗАНЯТИЕ №9 – 04 апреля 2013.

6. «Многомерный случай безусловных экстремумов. Методы первого порядка»

6.1 «Метод градиентного спуска с постоянным шагом».

Строиться последовательность точек по правилу Шаг – задаётся и остаётся постоянным, пока функция убывает. Иначе, например, делится попалам. Процесс оканчивается по условиям: 1) или 2) – максимальное число итераций, или 3) – для двух последних шагов.

Параметры метода .

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

Пример 6.1.

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

От предыдущего метода с постоянным шагом отличается определением оптимального шага: . Последняя скалярная задача решается аналитическим или численными методами для скалярной задачи.

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

От предыдущих методов спуска по градиенту здесь на каждом цикле вычислений (состоящем из шагов по всем координатам) производиться спуск по всем отдельным частным производным: .

6.4 «Метод Гаусса-Зейделя [Gauss-Seidel]».

От предыдущего метода покоординатного спуска с постоянным шагом отличается определением оптимального шага: , аналогично методу «наискорейшего градиентного спуска». Последняя скалярная задача решается аналитическим или численными методами для скалярной задачи.

6.5 «Метод Флетчера-Ривса [Fletcher R., Reeves C.M.]».

В этом методе итеративная последовательность точек строится по формуле: . Шаг определяется из условия оптимальности .

Рассмотрим физический смысл этого метода. Пусть минимизируемая функция является квадратичной формой , . Тогда вычисление величины обеспечивает построение последовательности H-сопряжённых направлений . При этом в точках последовательности последовательные пары градиентов функции взаимно ортогональны: . Для квадратичной функции и положительной матрицы H > 0 метод сходится не более, чем за n (размерность вектора x) шагов.

Для неквадратичных функций метод не является конечным, при этом нарушается ортогональность градиентов и H-сопряжённых направлений. В этом случае применяется модификация метода Полака-Рибьера [Polak E., Ribiere G.] с более сложным вычислением коэффициента . Кроме того, в отличие от метода Флетчера-Ривса метод Полака-Рибьера предусматривает использование итерации наискорейшего градиентного спуска после каждых n шагов.

6.6 «Метод Дэвидона-Флетчера-Пауэлла [Davidon W.C., Fletcher R., Powell M.J.D.]».

Это метод является обобщением метода наилучшего градиентного спуска, когда и . Вводится дополнительно матрица : и , которая определяется по правилу:

Рассмотрим физический смысл этого метода. Пусть минимизируемая

6.7 «Метод кубической интерполяции».

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

ЗАДАЧИ.

7. «Многомерный случай безусловных экстремумов. Методы второго порядка»

7.1 «Метод Ньютона».

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

Формула получена из следующих соображений. Напишем разложение в ряд Тейлора в точке x с точностью до второго порядка функции . – квадратичная форма. Направление (вектор) определяется из условия Ферма равенства 0 производной: . Таким образом, для последовательность является последовательностью минимумов квадратичных функций Для тех точек, где не выполнено требование дополним алгоритм шагом градиентного спуска с соблюдением условия убывания значений функции для :

Пример 7.1.

7.2 «Метод Ньютона-Рафсона».

Представляющий модификацию метода Ньютона имеет вид При этом .

7.3 «Метод Марквардта».

Представляющий модификацию метода Ньютона имеет вид При этом выбирается таким образом, чтобы матрица .

ЗАНЯТИЕ №10 – 11 апреля 2013.

Глава 3. Численные методы поиска условного экстремума

8. «Принципы построения численных методов поиска условного экстремума»

Существует две группы методов:

1. Методы последовательной безусловной оптимизации – преобразование условной задачи в последовательность безусловных задач и их решение.

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

Для первой группы существуют несколько подходов к решению задачи:

1. Метод штрафов (внешних штрафов).

2. Метод барьеров (внутренних штрафов).

3. Метод множителей. Использует модифицированную функцию Лагранжа вместо целевой.

4. Метод точных штрафов. Позволяет решать только одну задачу безусловной оптимизации.

Для второй группы существуют несколько подходов к решению задачи:

1. Метод проекции градиента. Градиент проектируется на касательную плоскость ограничений.

2. Метод возможных направлений Зонтейдейка. Строится возможное направление спуска (т.е. ) и оптимизируется целевая функция по этому направлению.

Пример линейных ограничений: . Здесь разделены ограничения равенства и неравенства.

Утверждение 8.1. Пусть x – допустимая точка, . Тогда вектор x – возможен . Если d – возможное направление спуска.

Пример 8.1. Конус возможных направлений, полупространство направлений спуска, конус возможных направлений спуска.

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

Утверждение 8.2. Если нет ограничений равенств и , то d – возможное направление спуска.

Поскольку движение по каждому из векторов антиградиентов должно привести на границу допустимой зоны, то можно для нахождения вектора d ввести и решать задачу

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

9. «Методы последовательной безусловной минимизации».

9.1. Метод штрафов.

Ищется минимум вспомогательной функции , где – функция штрафа.

При невыполнении ограничений и .

Часто , т.е. для ограничений равенств – квадрат, а для ограничений неравенств – квадрат срезки.

ЗАНЯТИЕ №11 – 18 апреля 2013.

Глава 4. Задачи линейного программирования

§ 11. «Методы решения задач линейного программирования»

Рассматривается задача («каноническая»):

Важным элементом в такой формулировке является неотрицательность переменных . Данное ограничение устраняется приёмом стандартным для теории линейного программирования, а именно, представлением этой переменной в виде разности двух неотрицательных переменных: .

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

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

Классический метод Гаусса решения систем линейных уравнений состоит в приведении её к виду с «базисными» переменными (остальные n-m переменных – небазисными, свободными):

Базисным решением называется решение . Базисное решение называется допустимым, если , и невырожденным, если .

Множество крайних точек политопа соответствует множеству допустимых базисных решений, и при этом одному базисному решению – одна крайняя точка.

Утверждение 11.1. достигает max на политопе – этот максимум достигается хотя бы в одной крайней точке. Для нескольких крайних точках – max достигается на их выпуклой комбинации.

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

Способы нахождение базисного решения:

1. Используем алгоритм Гаусса для приведения к приведённому выше нужному виду.

2. Переход к М-задаче. Для каждого уравнения вводится по 1-ой новой искусственной переменной.

Здесь – достаточно большое число, для унификации. Назначение дополнительного слагаемого состоит в том, чтобы в процессе решения вывести искусственные переменные из базиса. Если в результате окажется, что искусственные переменные входят в состав базисных и их значения не равны 0, то ограничения в задаче несовместны.

Начальное базисное решение при этом: . Геометрически этому соответствует начало координат в – пространстве переменных.

Переход от одного базиса к другому осуществляется переходом к новой вершине политопа (многогранника) в направлении возрастания целевой функции .

Алгоритм решения использует технологический приём: симплекс-таблицы для каждого текущего базиса. Пропуск вершины будет исключён, если базисы отличаются только на 1 вершину. Новая координата в базисе соответствует максимальному приросту целевой функции. Прирост целевой функции при введении в базис координаты равен: .

				…	–M
БП	БР			…

		…	…

БП – базисная переменная, БР – базисное решение.

12 3 4 Следующая ⇒