|
Текст подпрограммы и версий ( Фортран ) mna5r.zip , mna5d.zip |
Тексты тестовых примеров ( Фортран ) tmna5r.zip , tmna5d.zip |
|
Текст подпрограммы и версий ( Си ) mna5r_c.zip , mna5d_c.zip |
Тексты тестовых примеров ( Си ) tmna5r_c.zip , tmna5d_c.zip |
Поиск локального минимума функции многих переменных методом деформируемого многогранника без вычисления производной.
Пусть задана функция N переменных F (x1, x2, ..., xN) и пусть известны координаты N + 1 вершин многогранника, задаваемых в виде матрицы P (N + 1, N), каждая строка которой содержит координаты соответствующей вершины многогранника в пространстве En. Вершины многогранника рассматриваются в качестве пробных векторов при поиске локального минимума функции F.
В подпрограмме MNA5R выполняется итерационный процесс, на каждом этапе которого к многограннику применяются операции отражения, растяжения или сжатия в зависимости от топографии функции F. Итерационный процесс продолжается до тех пор, пока модуль разности между наибольшим и наименьшим значениями, которые функция F принимает в вершинах текущего деформируемого многогранника, не станет меньше EPS. В качестве искомой точки минимума может быть взята любая вершина многогранника, полученного на последней итерации.
Если по каким - либо причинам затруднительно указать вершины исходного многогранника, то можно установить такой режим работы подпрограммы, когда достаточно задать в первой строке матрицы P координаты начальной точки поиска минимума (x*1, x*2, ..., x*N). В этом случае в качестве исходного в подпрограмме строится правильный многогранник (регулярный симплекс) следующим образом:
| x*1 x*2 x*3 ... x*n |
| x*1 + d1 x*2 + d2 x*3 + d2 ... x*n + d2 |
P = | x*1 + d2 x*2 + d1 x*3 + d2 ... x*n + d2 | ,
| . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
| x*1 + d2 x*2 + d2 x*3 + d1 ... x*n + d1 |
где d1 = ((n + 1)1/2 + n - 1) / (n √2) , d2 = ((n + 1)1/2 - 1) / (n √2)
Д.Химмельблау. Прикладное нелинейное программирование. Изд - во "Мир", 1975.
SUBROUTINE MNA5R (F, N, P, MP, Y, PR, PRR, PBAR, EPS,
IREGIM, IFLAG, ITMAX)
Параметры
| F - | имя вещественной подпрограммы - функции вычисления F (x1, x2, ..., xN), имеющей два следующих формальных параметра: |
| X - | вещественный вектор длины N, содержащий координаты точки, в которой вычисляется значение функции F; |
| N - | количество переменных (тип: целый) |
| N - | количество переменных (тип: целый); |
| P - | вещественный двумерный массив размеров MP на N, содержащий на входе в подпрограмму, либо в своих первых N + 1 строках координаты вершин исходного многогранника (случай, когда IREGIM = 1), либо в своей первой строке координаты начальной точки поиска минимума (случай, когда IREGIM = 0); на выходе из подпрограммы содержит координаты вершин многогранника, полученного на последней итерации; в качестве искомой точки минимума может быть взята его любая вершина, если IFLAG = 1; |
| MP - | первая размерность двумерного массива P в вызывающей программе, MP ≥ N + 1 (тип: целый); |
| Y - | вещественный вектор длины N, на выходе из подпрограммы содержащий значения функции F в вершинах многогранника, полученного на последней итерации; |
|
PR - PRR PBAR | вещественные векторы длины N, используемые в подпрограмме в качестве рабочих; |
| EPS - | заданное допустимое отклонение между наибольшим и наименьшим значениями, которые функция F принимает в вершинах текущего деформируемого многогранника (тип: вещественный); |
| IREGIM - | задает режим работы подпрограммы (тип: целый); если IREGIM = 0, то в первой строке массива P задаются координаты начальной точки поиска минимума (в этом случае подпрограмма сама строит исходный многогранник); если IREGIM = 1, то в массиве P следует задать все вершины исходного многогранника; |
| IFLAG - | целая переменная, служащая для сообщения о том, удалось ли найти локальный минимум за ITMAX или меньше итераций; при этом: |
| IFLAG=0 - | когда минимум функции F не найден; тогда массив P содержит координаты вершин многогранника, полученного на последней итерации; |
| IFLAG=1 - | когда точка минимума найдена; |
| ITMAX - | заданное максимальное количество итераций (тип: целый). |
Версии
| MNA5D - | поиск минимума функции многих переменных методом деформируемого многогранника без вычисления производной; при этом все вещественные параметры должны иметь тип DOUBLE PRECISION, а подпрограмма - функция F должна быть описана как DOUBLE PRECISION FUNCTION. |
Вызываемые подпрограммы: нет
Замечания по использованию
|
В подпрограммах MNA5R и MNA5D имеется общий блок COMMON /MNA5RR/ ITER. Переменная ITER полагается равной количеству итераций, выполненных при поиске минимума функции. Если IFLAG = 0, то ITER = ITMAX. В этом случае следует либо увеличить ITMAX, либо увеличить EPS. Необходимо иметь в виду, что точка минимума, как правило, вычисляется с точностью на 2 - 3 порядка худшей, чем EPS. |
REAL P(10, 2), Y(2), PR(2), PRR(2), PBAR(2)
EXTERNAL F
COMMON /MNA5RR/ ITER
N = 2
P(1, 1) = 8.0
P(1, 2) = 9.0
P(2, 2) = 10.0
P(2, 2) = 11.0
P(3, 1) = 8.0
P(3, 2) = 11.0
MP = 10
EPS = 1.E - 6
IREGIM = 1
ITMAX = 500
CALL MNA5R (F, N, P, MP, Y, PR, PRR, PBAR, EPS, IREGIM,
* IFLAG, ITMAX)
P(1, 1) = 8.0
P(1, 2) = 9.0
IFLAG = 0
CALL MNA5R (F, N, P, MP, Y, PR, PRR, PBAR, EPS, IREGIM,
* IFLAG, ITMAX)
FUNCTION F (X, N)
DIMENSION X(N)
F = 4.0*(X(1) - 0.5)**2 + (X(2) - 6.0)**2
RETURN
END
Результаты:
- после первого обращения к подпрограмме:
P(1, 1) = 0.500369 , P(1, 2) = 6.00074
P(2, 1) = 0.500333 , P(2, 2) = 5.99983
P(3, 1) = 0.499807 , P(3, 2) = 5.99971
Y = (0.109821E - 5, 0.472409E - 6)
IFLAG = 1 , ITER = 32
- после второго обращения к подпрограмме:
P(1, 1) = 0.499617 , P(1, 2) = 5.99909
P(2, 1) = 0.500631 , P(2, 2) = 5.99939
P(3, 1) = 0.500202 , P(3, 2) = 6.00099
Y = (0.140809E - 5, 0.196219E - 5)
IFLAG = 1 , ITER = 32