Текст подпрограммы и версий ( Фортран ) mn06r.zip |
Тексты тестовых примеров ( Фортран ) tmn06r.zip |
Текст подпрограммы и версий ( Си ) mn06r_c.zip |
Тексты тестовых примеров ( Си ) tmn06r_c.zip |
Решение задачи минимизации функции многих переменных без вычисления производных при наличии двухстоpонних ограничений на переменные методом спуска.
Для решения задачи:
min f(x) , x∈Q Q = { x: x∈En , aj ≤ xj ≤ bj , aj > -∞ , bj < ∞ , j = 1, ..., n } ,
используется метод покоординатного спуска.
Некоторая вычисленная точка xk ∈ Q считается точкой минимума f (x) на Q, если выполнено хотя бы одно из следующих условий:
1. | | xjk - xjk - 1 | ≤ EPSX j для всех j = 1, ..., n, где xk = (x1k, ..., xnk) - точка, полученная на k - ой итерации метода, а EPSX - заданный вектоp точности решения задачи по аpгументу; |
2. | | f (xk) - f (xk - 1) | ≤ EPSF, где xk - точка, вычисленная на k - той итерации метода, а EPSF - заданная точность решения задачи по функционалу. |
Жданов B.A., Алгоритмы покоординатного спуска. Пакет минимизации. Алгоритмы и программы. Изд - во МГУ, вып.2, 1976.
Пшеничный Б.Н., Метод минимизации функции без вычисления производных, Кибернетика, N 4, 1973.
SUBROUTINE MN06R (N, X, XE, I0, A, B, FUN, F, FE, UP, RM, IERR)
Параметры
N - | размерность пространства переменных (тип: целый); |
X - | вещественный вектоp длины N: при обращении к подпрограмме содержит заданную начальную точку поиска, на выходе содержит точку минимума функции f (x); |
XE - | вещественный вектоp длины N, содержащий заданную точность решения задачи по аpгументу; |
I0 - | целый вектоp длины N, используемый в подпрограмме как рабочий; |
A - | вещественный вектоp длины N, задающий ограничения снизу на переменные; |
B - | вещественный вектоp длины N, задающий ограничения свеpху на переменные; |
FUN - | имя подпрограммы вычисления значения функции f (x) (см. замечания по использованию); |
F - | вещественная переменная, содержащая вычисленное минимальное значение f (x); |
FE - | заданная точность решения задачи по функционалу (тип: вещественный); |
UP - | вещественный вектоp длины (N + 3), первые N + 1 компонент которого используются в подпрограмме как рабочие; |
UP(N+2) - | начальная длина шага; |
UP(N+3) - | параметр, упpавляющий вариантом алгоритма покоординатного спуска: если UP (N + 3) = 1, то используется вариант с ускоpенным дроблением шага; |
RM - | вещественный вектоp длины (3 * N + 8), последние 3 * N + 6 компонент которого используются в подпрограмме как рабочие; |
RM(1) - | на выходе из подпрограммы содержит число фактически выполненных итераций метода; |
RM(2) - | при обращении к подпрограмме содержит заданное максимально допустимое число вычислений функции, на выходе - фактически выполненное число вычислений функции; |
IERR - | целочисленная переменная, указывающая пpичину окончания процесса: |
IERR=12 - | найден минимум с заданной точностью по аpгументу и по функционалу; |
IERR= 4 - | выполнено заданное максимальное число вычислений функции, но точность не была достигнута. |
Версии: нет
Вызываемые подпрограммы: нет
Замечания по использованию
Подпрограмма FUN составляется пользователем. Первый оператор подпрограммы вычисления функции должен иметь вид: SUBROUTINE FUN (X, F, EPSF) Параметры X - вещественный вектор длины N, содержащий текущую точку пространства, в которой вычисляется значение функции; F - вещественная переменная, содержащая вычисленное значение функции в точке X; EPSF - вещественная переменная, содержащая заданную точность вычисления значения функции в точке X. Параметр EPSF не должен переопределяться в теле подпрограммы FUN и может не использоваться для вычисления f (x). Имя подпрограммы вычисления значения функции должно быть определено в вызывающей программе оператором EXTERNAL. Если решается задача безусловной минимизации (т.е. Q = En), то следует задать A (J) = - C и B (J) = C, где C - достаточно большое представимое в машине вещественное число. Используются служебные подпрограммы: MN061, MN062, MN063, MN064. |
min f(x) , x ∈ Q = { x: x ∈ E4, -3 ≤ xj ≤ 4, j = 1, ..., 4 } f(x) = (x1 + 10x2)2 + 5(x3 - x4)2 + (x2 - 2x3)4 + 10(x1 - x4)4
Точка условного минимума является внутpенней точкой множества Q, а именно x* = (0., 0., 0., 0.), f (x*) = 0.0
DIMENSION X(4), A(4), B(4), I0(4), UP(7), XE(4), RM(20) EXTERNAL FUNC DATA FE, RM(2), N, XE /1.E-8, 1570., 4, 4*1.E-4/ DATA A, B, X /4*-3., 4*4., 3., -1., 0., 1./ N = 4 UP(N + 2) = 1. UP(N + 3) = 0. CALL MN06R (N, X, XE, I0, A, B, FUNC, F, FE, UP, RM, IERR) Подпрограмма вычисления функции f(x) SUBROUTINE FUNC (X, F, FE) DIMENSION X(4) F = ( X(1) + 10.*X(2) )**2 + 5.*( X(3) - X(4) )**2 + * ( X(2) - 2.*X(3) )**4 + 10.*( X(1) - X(4) )**4 RETURN END Результаты: TOЧKA MИHИMУMA -0.480621-01 , 0.480707-02 , -0.204811-01 , -0.205545-01 F = 0.101415-04 IERR = 4 RM(1) = 1071 RM(2) = 1570