Текст подпрограммы и версий ( Фортран ) 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