Алгоритм метода покоординатного спуска
1. Задается точность вычисления 
, начальный шаг 
, минимально допустимый шаг 
, точка начального приближения 
, порядковый номер итерации k=0 и вычисляется 
.
2. Запоминаем 
.
3. Начинаем поиск параллельно оси Охi : 
,если 
, переходим к п. 11 , иначе к п. 4.
4. Задаем шаг 
.
5. Задаем знак 
.
6. Вычисляем 
в соответствии с формулой (1.6) и значение функции в новой точке.
7. Если новое значение функции меньше предыдущего, то принимаем 
как , 
запоминаем как 
и возвращаемся к п. 6, иначе меняем знак 
на противоположный.
8. Если знак 
,то переходим к п. 6, иначе к п. 9.
9. Уменьшим величину шага 
.
10. Если текущий шаг 
, то переходим к п. 3, иначе к п. 5.
11. Проверка условия достижения заданной точности: 
и если оно выполняется, то переходим к п. 12, иначе к п. 2.
12. Завершить вычисления, приняв за точку минимума 
последнее значение Хk, 
4. Текст программы.
Смотри приложение №1.
- Метод деформируемого многогранника (метод Нелдера — Мида).
Метод Нелдера — Мида, также известный как метод деформируемого многогранника и симплекс-метод, — метод безусловной оптимизации функции от нескольких переменных, не использующий градиентов функции, а поэтому легко применим к негладким и/или зашумлённым функциям.
В методе Нелдера и Мида минимизируется функция n независимых переменных с использованием n+1 вершин деформируемого многогранника в En. Каждая вершина может быть идентифицирована вектором x. Вершина (точка) в En, в которой значение f(x) максимально, проектируется через центр тяжести (центроид) оставшихся вершин. Улучшенные (более низкие) значения целевой функции находятся последовательной заменой точки с максимальным значением f(x) на более «хорошие точки», пока не будет найден минимум f(x).
Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума. Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.
Параметрами метода являются:
· коэффициент отражения α > 0, обычно выбирается равным 1.
· коэффициент сжатия β > 0, обычно выбирается равным 0,5.
· коэффициент растяжения γ > 0, обычно выбирается равным 2.
Алгоритм метода.
Пусть 
, является i-й вершиной (точкой) в En на k-м этапе поиска, k=0, 1, …, и пусть значение целевой функции в x(k)i равно f(x(k)i). Кроме того, отметим те векторы x многогранника, которые дают максимальное и минимальное значения f(x).
Определим
Поскольку многогранник в En состоит из (n+1) вершин x1, …,xn+1, пусть xn+2 будет центром тяжести всех вершин, исключая xh.
Тогда координаты этого центра определяются формулой
(1.7)
где индекс j обозначает координатное направление.
Начальный многогранник обычно выбирается в виде регулярного симплекса (но это не обязательно) с точкой 1 в качестве начала координат; можно начало координат поместить в центр тяжести. Процедура отыскания вершины в En, в которой f(x) имеет лучшее значение, состоит из следующих операций:
1. Отражение – проектирование 
через центр тяжести в соответствии с соотношением
(1.8)
где a>0 является коэффициентом отражения; 
– центр тяжести, вычисляемый по формуле (1); 
– вершина, в которой функция f(x) принимает наибольшее из n+1 значений на k-м этапе.
2. Растяжение. Эта операция заключается в следующем: если 
, то вектор 
растягивается в соответствии с соотношением
(1.9)
где g>1 представляет собой коэффициент растяжения. Если 
, то заменяется на 
и процедура продолжается снова с операции 1 при k=k+1. В противном случае заменяется на 
и также осуществляется переход к операции 1 при k=k+1.
3. Сжатие. Если 
для всех i¹h, то вектор 
сжимается в соответствии с формулой
(1.10)
где 0<b<1 представляет собой коэффициент сжатия. Затем заменяем на 
и возвращаемся к операции 1 для продолжения поиска на (k+1)-м шаге.
4. Редукция. Если 
, все векторы 
уменьшаются в 2 раза с отсчётом от 
в соответствии с формулой
(1.11)
Затем возвращаемся к операции 1 для продолжения поиска на (k+1)-м шаге.
Критерий окончания поиска, использованный Нелдером и Мидом, состоял в проверке условия
(1.12)
где e – произвольное малое число, а 
– значение целевой функции в центре тяжести .
На рис.2 приведена блок-схема поиска методом деформируемого многогранника
Пуск
 |
Вычислить начальные значения
xi(0), i = 1, 2, …, n+1, и f(x(0))
начального симплекса
 |
Вычислить xh и xl и c
 |
Отражение: вычислить
xn+3 = xn+2 + a(xn+2 - xn)
 |
Вычислить
f(xn+3)
 | |||
 |
|
неравенство
f(xn+3) < f(xh) ?
 | |||
| |||
Растяжение: вычислить
xn+4 = xn+2 + g(xn+3 - xn+2)
 |
Вычислить f(xn+4)
 |
Выполняется ли
неравенство
f(xn+4) < f(xl) ?
 |
Заменить
xh на xn+4
 | |||||||
| |||||||
 | |||||||
 |
Выполняется ли
неравенство f(xn+3) < f(xi)
для всех i ¹ h ?
 | |||||||||||
| |||||||||||
 | |||||||||||
| |||||||||||
| |||||||||||
|
Заменить
xh на xn+3
| |||||
 | |||||
 |
Рис. 2
Выполняется ли
неравенство
f(xn+3) < f(xh) ?
| |||||||
 |  | ||||||
| |||||||
Заменить
xh на xn+3
Сжатие: вычислить
xn+5 = xn+2 + b(xh - xn+2)
 |
Вычислить f(xn+5)
 |
Выполняется ли
неравенство
f(xn+5) > f(xh) ?
 |  | ||
Заменить
|
 | |||
 | |||
Редукция: заменить
все xi на xl + 1/2(xi - xl)
 | |||||
| |||||
 | |||||
Останов
7. Текст программы.
Смотри приложение №1.
Задание.
Используя метод покоординатного спуска или метод деформированного многогранника, реализовав их в виде программ на Turbo Pascal, найти минимум следующих функций:
1) f(X)=x12+ x22 +x32+ x1–x1 *x2-2x3
2) f(X)=100( x2 –x12) 2+ (1-x1)2
3) f(X)=( x2 –x12) 2+ (1-x1*x2)2
4) f(X)=5x12+ x22 + 4x1 *x2-16x1-12x2
5) f(X= х12 + 4х22 –4х1 –8х2 + 5
Лабораторная работа №2.