- •Экзаменационные вопросы
- •1 Постановка задачи. Локальные и глобальные экстремумы
- •2 Задача максимизации функции
- •3 Необходимые и достаточные условия локального экстремума. Классический метод нахождения экстремумов функций
- •3.1 Классический метод
- •4 Метод деления отрезка пополам
- •5 Метод золотого сечения
- •5.1 Модификация метода золотого сечения
- •6 Симметричные методы
- •6.1 Постановка задачи об оптимальных методах
- •6.2 Оптимальный пассивный метод для задачи А (метод равномерного перебора)
- •6.3 Оптимальный последовательный метод для задачи А (метод Фибоначчи)
- •7 Метод ломаных
- •7.1 Описание метода ломаных
- •7.2 Сходимость метода ломаных
- •7.3 Определение константы L
- •7.4 Достоинства и недостатки метода ломаных
- •9 Линейные пространства
- •10 Постановка задачи минимизации
- •12 Численные методы безусловной минимизации
- •13 Общая схема градиентого спуска
- •13.1 Градиентые методы с дроблением шага
- •13.2 Метод наискорейшего спуска
- •13.3.1 О сходимости градиентого метода
- •13.4 Методы покоординатного спуска (для отыскания безусловного экстремума)
- •13.4.1 Метод покоординатного спуска без вычисления производных
- •13.4.2 Рекомендации по применению этого метода
- •14 Относительный (условный) экстремум
- •15.1 Метод исключения
- •15.3 Метод Лагранжа
- •17 Обобщенная функция Лагранжа
- •17.1 Обобщеный метод множителей Лагранжа
- •17.2 Единственность вектора Лагранжа для нормального оптимального плана
- •18 Общая задача математического программирования
- •19 Выпуклые множества
- •19.1 Выпуклые функции
- •20 Дифференциальные условия оптимальности в задаче математического программирования
- •21.2 Метод проекции градиента
- •21.3 Проекция точки на гиперплоскость
- •21.4 Проекция точки на аффинное множество
- •21.5 Проекция точки на шар
- •21.6 Проекция точки на замкнутое полупространство
- •21.8 Метод покоординатного спуска для отыскания условного экстремума
- •22 Метод штрафных ф-ий
- •22.1 Метод внешних штрафных функций
- •22.2 Метод барьерных функций
- •22.2.1 Описание метода барьерных функций (для решения задачи 6.1)
- •23 Общая задача ЛП и ее канонические формы
- •23.1.3 Переход к эквивалентой системе неравенств
- •23.1.4 Переход от задачи минимизации к задаче максимизации
- •24 Различные формы записи задачи ЛП
- •24.1 Развернутая форма задачи ЛП
- •24.2 Векторная форма
- •24.3 Матричная форма
- •24.4 План. Опорный план. Оптимальный план
- •25 Выпуклые многогранники
- •26 Геометрическая интерпретация задачи ЛП
- •26.1 Свойства решения задачи ЛП
- •26.2 Графический метод решения задачи ЛП
- •27 Симплексный метод решения задач ЛП
- •27.1 Построение опорных планов
- •27.2 Отыскание оптимального плана. Условия оптимальности
- •27.3 Алгоритм симплексного метода. Симплексная таблица
- •27.3.1 Правила заполнения таблицы
- •27.3.2 Анализ симплексной таблицыx
- •27.3.3 Переход к новому опорному плану
- •27.3.4 Замечание к решению задачи на максимум
- •28 Методы искусcтвенного базиса
- •28.1 Метод больших штрафов
- •28.2 Двухэтапный метод
- •29 Вариация и ее свойства
- •30 Уравнение Эйлера
- •31 Простейшие случаи интегрируемости уравнения Эйлера
5Метод золотого сечения
Метод позволяет найти локальный экстремум ф-и при меньшем кол-ве вычислений ее значений, чем метод деления отрезка пополам. Золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длины большей части равнялось отношению большей части к длине меньшей части отрезка. Золотое сечение производится двумя точками
(x2 |
= a + |
1 |
(3 + p5)(b |
a) = a + 0:61803(b |
a) |
||
|
|
21 |
(3 p |
|
|
|
|
x1 |
= a + |
5)(b |
a) = a + 0:38196(b |
a) (1) |
|||
|
|
2 |
|
|
|
|
|
расположенными симметрично относительно середины отрезка. Для точек x1 и x2(a < x1 < x2 < b) выполняются соотношения
b a |
= b x1 |
|
b a |
= x2 a = |
p |
|
|
|
= |
5+1 |
= 1:61803 (2) |
||||||
|
||||||||
b x1 x1 a |
|
x2 a |
b x2 |
2 |
|
В свою очередь точка x1 производит золотое сечение отрезка [a; x2] т.к.
x2 a |
= |
x1 a |
l2 |
= |
l1 |
x1 a |
|
x2 x1 |
l1 |
|
l2 l1 |
Аналогично точка x2производит золотое сечение отрезка [x1; b] Определение минимума унимодальной f(x) на отрезка [a; b] выглядит так. Положим
a1 = a b1 = b
на отрезке [a1; b1] возьмем точки x1 x2, производящие золотое сечение и вычислим значение f(x1) f(x2).
Если
f(x1) 6 f(x2)
то примем
a2 = a1 b2 = x2 x2 = x1
если
f(x1) > f(x2)
то примем
a2 = x2 b2 = x1 x2 = x2
Так как ф-я f(x) унимодальна на на отрезке [a; b], то получившийся отрезок [a2; b2] имеет хотя бы одну общую точку со множеством точек минимума ф-и f(x) X . Кроме того
p
b2 a2 = 12 ( 5 1)(b a)
и внутри отрезка [a2; b2] содержится точка x2 с вычисленным значением
f(x2) = min(f(x1); f(x2))
которая производит золотое сечение отрезка [a2; b2].
Предположим, что уже определены точки x1; x2; :::; xn 1, вычислены f(x1); f(x2); :::; f(xn 1), найден отрезок [an 1; bn 1] такой, что пересечение с множеством точек X не пусто.
p
= ( 52 1 )n 2(b a)
и известна точка xn 1, производящая золотое сечение отрезка [an 1; bn 1] такая, что f(xn 1) = min(f(xi))1 6 i 6 n 1 n > 2.
Тогда в кач-ве следующей точки возьмем точку
xn = an 1 + bn 1 xn 1
8
так же производящую золотое сечение отрезка [an 1; bn 1] и вычислим значение f(xn). Пусть для определенности
Cлучай xn 1 Если
то
Если же
то
an 1 < xn < xn 1 < bn 1
< xn рассматривается аналогично.
f(xn) 6 f(xn 1)
an = an 1 bn = xn 1 xn = xn
f(xn) > f(xn 1)
an = xnbn = bn 1 xn = xn 1
Новый отрезок [an; bn] таков, что его пересечение с X непусто, длина отрезка
|
|
|
p |
|
|
|
|
|
|
|
b |
n |
a = ( |
5 1 |
)n 1 |
|
(b |
|
a) |
||
|
n |
2 |
|
|
|
а точка xn производит сечение отрезка [an; bn] и
f(xn) = min(f(xi)) 1 6 i 6 n.
Если число вычислений значений ф-и f(x) не ограничено, то процесс приближений можно продолжать до тех пор, пока не выполнится неравенство bn an < " заданная погрешность, после этого в кач-ве решения задачи второго типа можно взять пару f(xn), xn, где первое приближение для
f = inf f(x)
x2[a;b]
а точка xn служит приближением для локального минимума.
Если погрешность " не задана, то погрешность на n-ом шаге оценивают по формуле
|
|
|
|
j 6 |
|
|
|
|
|
|
|
|
|
p |
|
|
|
|
|
|
|
n |
v |
max[b |
n |
|
|
; |
|
|
a |
] = ( |
5 1 |
)n(b |
|
a) |
|||
|
x |
x |
n |
x |
|
|
|||||||||||||
j |
|
|
|
|
n |
n |
|
2 |
|
|
Недостаток в таком классическом виде метод золотого сечения уже при небольших n имеет большую погрешность (с большими погрешностями определяются точки, осуществляющие золотое сечение).
5.1Модификация метода золотого сечения
Заключается в следующем: на каждом отрезке [an; bn] (на каждом шаге) содержащем xn с предыдущего шага при выборе следующей точки xn+1 не пользуются формулой
xn+1 = an + bn xn
вместо этого непосредственно производят золотое сечение отрезка [an; bn].
9