Метод состоит из 2-х этапов:
1)исследовательский поиск (поиск направления)
2)поиск по образцу (по определенному направлению)
1. задаем x0, , h, и k=0.
2. Введем точку z для сравнения новой и предыдущей точки, = |
. j=1 |
||||
2.1. |
, если f( ) |
f( |
), то |
и переход к шагу2.3 |
|
иначе к шагу2.2 |
|
|
|
|
|
2.2. |
, если f( |
) |
f( ), то |
, иначе к шагу2.3 |
|
2.3. j=j+1 Если j<n, то к шагу2.1 иначе к шагу3 |
|
|
|||
3.если = , то h=h/2, проверяем останов, т.е. если |
, то |
и останов, иначе |
|||
переходим к шагу2 |
|
|
|
|
|
Иначе если |
, то переход к шагу 4(поиск по образцу). |
|
|||
4. Направление поиска |
|
|
|
|
|
|
, |
|
|
|
|
k=k+1 переход к шагу 2. |
|
|
|
|
|
Метод вращающихся координат |
|
|
|
|
|
Шаг 1. |
и k = 0. |
|
|
|
|
Шаг 2. |
; |
|
|
|
|
|
; |
|
|
|
|
………………………… |
|
|
|
|
|
|
; |
|
|
|
|
Шаг 3. Если |
, то |
и остановка |
|
|
|
Иначе к шагу4. |
|
|
|
|
|
Шаг 4. Используя процедуру Грамма – Шмидта находим |
|
||||
k =k+1, переходим к шагу2 |
|
|
|
|
|
Процедура Грамма-Шмидта |
|
|
|
|
|
(над всем кроме |
поставить вектора) |
|
|
|
|
Пусть |
–полученная С.К. на шаге k |
|
|
||
|
– новая С.К. |
|
|
|
|
Введем систему вспомогательных векторов
……………
Введем еще вспомогательные вектора
- вектор ортогональный S1
Аналогично
l=2..n
Таким образом получим новую С.К.
Если |
=0 => оставляем старые |
11
Метод деформирующего многогранника.
1.Построение исходного многогранника k=0
2.(отражение) выч-м |
i=1..n |
||
|
|
– центр тяжести, i max |
|
|
|
||
|
|
|
; α – коэффициент отражения α >= 1. Обычно α=1. |
a) |
Шаг 3.2 |
||
б) |
Шаг 3.1 |
||
a) |
Шаг 3.2 |
||
3. |
|
|
|
3.1(растяжение) |
|
|
|
|
; β – коэффициент растяжения, β |
2 (обычно=2) |
|
Если |
, то строим новый симплекс |
( |
), переход к шагу 2 |
Иначе |
|
|
|
3.2(сжатие) |
если условие а) |
|
|
|
если условие б); |
– коэффициент сжатия, обычно j=0,5 |
|
Если |
, то выполняется редукция |
|
|
переход к шагу 3.3 |
|
|
|
|
||
иначе новый симплекс |
(замена) и переход к шагу2 |
|
||||
3.3 Если |
|
|
|
, то |
, f( |
) и остановка |
|
|
|
||||
|
||||||
Иначе k=k+1 переход к шагу 2. |
|
|
|
|
||
12
7. Сопряженные направления и особенности их использования при решении задач многомерной безусловной оптимизации. Суть методов прямого поиска и градиентных методов, основанных на сопряженных направлениях. Их сравнительный анализ.
–система направлений.
Эта система будет сопряженной, если
H – некоторая положительно определенная квадратичная матрица
Теорема 1:Если задана система сопр. направлений и целевая функция квадратична, то поиск экстремума требует n шагов, при этом порядок использования направлений значения не имеет.
Теорема 2 Для матрицы H существует хотя бы одна система сопряженных направлений, и в качестве этой системы могут выступать собственные вектора.
Метод сопряженного градиента. Задано xo => первое направление
; - выбирается так, что и – сопряженные
;
– т.к. они перпендикуляры
Алгоритм: |
|
1.Задаем |
, k = 0. |
13
2.
,
3. j=1
3.1
3.2 Если , то j=j+1 и переход к шагу 3.1 Иначе – переход к шагу 4.
4.Если |
, то |
Иначе - |
, k=k+1 и переход к шагу 2. |
Сравнительный анализ
Особенности методов прямого поиска состоят в следующем:
1.Знание целевой функции не требуется. Достаточно умение вычислять ее значение в нужных точках
2.Не требуется регулярность и непрерывность функции
3.Не требуется вычисления (наличия) производной 1 порядка
Адля градиентных методов надо:
1.Знать целевую функцию
2.Уметь вычислять ее 1 производную
3.Вычислять ее градиент
Также стоит отметить, что если целевая функция квадратична, то для рассмотренного градиентного метода, основанного на сопряженных направлениях, определение экстремума осуществляется за n шагов.
14
8. Постановка задачи многомерной безусловной оптимизации и классификация методов ее решения. Методы первого порядка: наискорейшего спуска, покоординатного спуска, Гаусса-Зейделя. Их сравнительный анализ.
Постановка задачи
,, задана функция . Необходимо найти min (или max)
исходные данные: Классификация методов: 1) Прямые методы поиска
Знание целевой ф-ии не нужно, необходимо только уметь вычислять ее в точках 2) Методы первого порядка (градиентные методы)
Нужно знать вид функции, уметь вычислять первую производную. Выбор направления основан на вычислении градиента 3) Методы второго порядка
Нужно знать вид функции, уметь вычислять градиент и матрицу Гесса Метод наискорейшего спуска.
1. |
|
k = 0 |
|
2. |
выч-м |
, где |
|
3. |
выч-м |
|
|
4. |
если |
=> |
- min, иначе k=k+1 и переход к шагу2 |
Метод покоординатного спуска. |
|
||
1. |
k = 0, |
= |
|
2. |
|
|
|
...
3. , если , то и останов, иначе k=k+1 и переход к шагу2 Метод Гаусса-Зейделя
1.
2. Осуществляем циклический поиск по j=1,...,n
3.если |
, то |
, иначе k=k+1 и переход |
к шагу 2. |
|
|
Сравнительный анализ |
|
|
Метод наскорейшего спуска: |
|
|
1)В каждой точке вычисляется градиент функции => много вычислений
2)Плохо ищет экстремум для овражной функции
3)При большой точности поиск может остановиться, не достигнув минимума.
Другие 2 метода уменьшают объем вычислений. Методы покоординатного спуска и ГауссаЗейделя по сути одинаковы, но в Гаусса-Зейделе меньше вычислений. В покоординатном спуске - более оптимальный поиск. Все 3 метода плохо ищут экстремум овражной функции.
15
9. Постановка задачи многомерной безусловной оптимизации и классификация методов ее решения. Методы второго порядка: метод Ньютона и его модификации, методы переменной метрики.
Постановка задачи
,, задана функция . Необходимо найти min (или max)
исходные данные: Классификация методов: 1) Прямые методы поиска
Знание целевой ф-ии не нужно, необходимо только уметь вычислять ее в точках 2) Методы первого порядка (градиентные методы)
Нужно знать вид функции, уметь вычислять первую производную. Выбор направления основан на вычислении градиента 3) Методы второго порядка
Нужно знать вид функции, уметь вычислять градиент и матрицу Гессе Метод Ньютона.
1. |
, k = 0, выч-м |
|
–матрица Гессе |
2.Вычисляем |
|
|
|
3. |
|
|
|
4.выч-м |
|
|
|
2.Вычисляем |
|
|
|
5. |
Если |
, то |
, останов, иначе k=k+1 и переход к |
шагу 2. |
|
|
|
Модификации: |
|
|
|
Метод Ньютона-Рафсона (с опт. выбором шага) |
|||
|
, где |
|
– минимум ф-ии вдоль направления |
Первая модификация метода Ньютона. |
|
||
Модификация 2 метода Ньютона
Через m итераций вычисляем , т.е. Н не изменяется m итераций, потом вычисляется, потом снова m раз не изменяется и т.д.
16
10. Задача линейного программирования. Основные определения. Лексикографический вариант прямого симплекс-метода. Вырожденность в задачах линейного программирования. Геометрическая интерпретация симплекс-метода.
Общая форма ЗЛП:
,–целевая ф-ия
–вектор-строка
–вектор-столбец
n–размерность пространства
– ограничения Х
,
кол-во ограничений m
- неотрицательные переменные (остальные - свободные)
– матрица mxn
–вектор-столбец Основные определения
–столбец Опр.Любой набор линейно-независимых столбцов ( ,…, ) называется базисом
А=[B,N], где В-матрица, состоящая из линейно-независимых столбцов N-все остальные.
число базисов
x= |
, |
|
|
|
|
Опр. Переменные , являющиеся компонентами |
называются базисными переменными |
||||
Переменные , не являющиеся компонентами |
называются небазисными переменными |
||||
Опр.Решение системы |
называется базисным решением. |
|
|||
Каждому базису соответствует базисное решение, но базисное решение может |
|||||
соответсвовать немкольким базисам. |
|
|
|
||
Утв. |
является базисным решением |
<=> множество столбцов, которые образуют |
|||
базис ({ |
}) являются линейно-независимыми. |
|
|||
Опр.Базисным допустимым решением называется любой элемент мн-ва |
|||||
Утв. является базисно-допустимым решением (бдр) <=> когда |
явл. крайней точкой |
||||
Опр.Симплекс-таблица называется прямо допустимой, если |
, i=1..m |
||||
Опр.Симплекс-таблица называется двойственно допустимой, если |
, j=1..n |
||||
Утв.Если ЗЛП разрешима, то существует прямо и двойственно допустимая симплекс-таблица (ЗЛП разрешима, если х не и ф-ия ограничена снизу)
Утв.(достаточное условие оптимальности) если симплекс-таблица явл прямо и двойственно допустимой, то соответствующее базисное решение оптимальное.
Опр.Базисное решение называется вырожденным, если , для которого |
|
|
|
Утв.Пусть базисно допустимое решение х невырожденное |
, |
, |
, то |
тогда существует другое б.д.р., у которого целевая ф-ия меньше |
|
|
|
Опр.ЗЛП называется вырожденной, если вырожденное б.д.р. |
|
|
|
Утв.В случае невырожденной ЗЛП прямой симплекс-метод является конечным, а если ЗЛП
вырожденная, то зацикливание возможно |
|
|
|
Лексографический вариант |
|
|
|
Опр.Пусть задан вектор =( |
), тогда вектор лексиграфически положительный |
||
,если первый отличный от нуля компонент вектора положительный. (0,0,0,1,-1,0…) , |
|||
т.е. если |
|
|
|
Утв.Пусть заданы 2 вектора , |
, тогда |
, если |
. |
|
|
17 |
|
Если задано множество таких векторов, то среди них всегда можно найти вектор, который будет лексикографическим минимумом : lexmin
Опр.Симплекс-таблица называется нормальной, если все её строки лексографически положительны Утв.Прямую с.-т. всегда можно преобразовать в нормальную с.-т. путем переобозначения
переменных и изменения порядка расположения столбцов Лексикографический вариант прямого симплекс-метода алгоритма: 0.построить нормальную симплекс-таблицу
1.если с.-т. является двойственно допустимой (т.е. |
, j=1..n), то решение оптимальное и |
||
конец, иначе переход к шагу2 |
|
|
|
2.определяем ведущий столбец, т.е. находим такое j=s, что |
(если их несколько, то |
||
выбираем любой из них) |
|
|
|
3. если |
, то конец (ЗЛП решения не имеет), иначе определяем ведущую строку |
||
r: |
(если 2 одинаковых, то любой) |
|
|
4.преобразуем симплекс-таблицу с ведущим элементом |
. |
(Заменяем |
|
соответствующую базисную переменную на небазисную) и переходим к шагу1 (в результате с.-т. остается всегда прямо допустимой)
Утв.Если ЗЛП вырождена, то алгоритм будет конечным (всегда) Геометрическая интерпретация симплекс-метода.
Решение лежит на границе области
18