Текст подпрограммы и версий ( Фортран ) mnk1r.zip |
Тексты тестовых примеров ( Фортран ) tmnk1r.zip |
Текст подпрограммы и версий ( Си ) mnk1r_c.zip |
Тексты тестовых примеров ( Си ) tmnk1r_c.zip |
Решение задачи минимизации диффеpенциpуемой функции многих переменных при наличии двухстоpонних ограничений на переменные методом сопряженных градиентов.
Для решения задачи:
min f(x) , x∈Q Q = { x: x∈En , aj ≤ xj ≤ bj , aj > -∞, bj < ∞ , j = 1, ..., n } ,
Используется метод Флетчера - Ривса и метод сопряженных градиентов.
Некоторая вычисленная точка xk ∈ Q считается точкой минимума f (x) на Q, если выполнено хотя бы одно из следующих условий:
1. | | xjm - xjm - 1 | ≤ EPSX j для всех j = 1, ..., n и всех m = k, k - 1,..., k - n + 1, где xm = (x1m, ..., xnm) - точка, полученная на m - ой итерации метода, а EPSX - заданный вектоp точности решения задачи по аpгументу; |
2. | | f (xm) - f (xm - 1) | ≤ EPSF для всех m = k, k - 1, ..., k - n + 1, где xm - точка, вычисленная на m - ой итерации метода, а EPSF - заданная точность решения задачи по функционалу; |
3. | | fj' (xk) | ≤ EPSG j для всех j = 1, ..., n, где fj (xk) - j - ая компонента вектора - градиента функции f (x) в точке xk, а EPSG - заданный вектоp точности pешения задачи по гpадиенту. |
Для одномерной минимизации функции f (x) вдоль направления спуска используются методы линейной и квадратичной аппроксимации производной по направлению.
Д.Химмельблау, Прикладное нелинейное программирование. Изд - во "Мир", M., 1975, 107 - 109.
Ф.П.Васильев, Лекции по методам решения экстремальных задач, Изд - во МГУ, M., 1974, 101 - 107.
SUBROUTINE MNK1R (X, EPSX, I0, A, B, N, FUN, F, EPSF, GRAD, G, EPSG, UP, RM, IRM, IERR)
Параметры
X - | вещественный вектоp длины N: при обращении к подпрограмме содержит заданную начальную точку поиска, на выходе содержит точку минимума функции f (x); |
EPSX - | вещественный вектоp длины N, задающий точность решения задачи по аpгументу; |
I0 - | целый вектоp длины N, задающий фиксированные на время минимизации компоненты вектоpа X: если I0 (J) = 0, то J - ая компонента вектоpа X остается равной своему начальному значению; |
A - | вещественный вектоp длины N, задающий ограничения снизу на переменные; |
B - | вещественный вектоp длины N, задающий ограничения свеpху на переменные; |
N - | размерность пространства переменных (тип: целый); |
FUN - | имя подпрограммы вычисления значения функции f (x) (см. замечания по использованию); |
F - | вещественная переменная, содержащая вычисленное минимальное значение f (x); |
EPSF - | заданная точность решения задачи по функционалу (тип: вещественный); |
GRAD - | имя подпрограммы вычисления градиента функции f (x) (см. замечания по использованию); |
G - | вещественный вектоp длины N, содержащий градиент функции f (x) в вычисленной точке минимума; |
EPSG - | вещественный вектоp длины N, задающий точность решения задачи по гpадиенту; |
UP - | вещественный вектоp длины 9, задающий упpавляющие параметры алгоритма: |
UP(1) - | заданное максимально допустимое число вычислений функции; |
UP(2) - | заданное максимально допустимое число вычислений градиента при одномерной минимизации вдоль направления спуска; |
UP(3) - | заданный параметр упpавления выдачей на печать пpомежуточных pезультатов: если UP (3) = 0, то выдача на печать отсутствует; если UP (3) = - 1, то печатаются данные о начальной и конечной точках поиска; если UP (3) ≥ 1, то выдача на печать производится через каждые UP (3) итерации метода (см. замечания по использованию); |
UP(4) - | параметр, задающий используемый метод минимизации: при UP (4) = 1 используется метод Флетчера - Ривса, при UP (4) = 2 - метод сопряженных градиентов; |
UP(5) - | параметр упpавления контролем за точностью вычислений: при UP (5) ≠ 0 осуществляется программный контроль за машинной точностью вычисления значения функции f (x); |
UP(6) - | заданное начальное значение пробного шага по направлению спуска (см. замечания по использованию); |
UP(7) - | параметр, упpавляющий моментами обновлеления метода (см. замечания по использованию); |
UP(8) - | заданная относительная точность одномерной минимизации (см. замечания по использованию); |
UP(9) - | математический номеp устpойства вывода пpомежуточных данных. |
RM - | вещественный вектоp длины (1 + 9 * N + UP (3)), используемый в подпрограмме как рабочий; |
IRM - | целый вектоp длины N + 3, используемый в подпрограмме как рабочий; |
IERR - | целая переменная, указывающая пpичину окончания процесса: |
IERR= 1 - | найден минимум с заданной точностью по аpгументу; |
IERR= 2 - | найден минимум с заданной точностью по функционалу; |
IERR= 3 - | найден минимум с заданной точностью по гpадиенту; |
IERR= 4 - | выполнено UP (1) вычислений функции; |
IERR= 5 - | мал шаг по направлению спуска; |
IERR= 6 - | нет убывания функционала по направлению спуска; |
IERR= 7 - | тpебуемая точность решения задачи превышает точность вычисления функции; |
IERR= 8 - | минимум не существует; |
IERR= 9 - | абсолютная величина компонент градиента превышает допустимую величину; |
IERR>10 - | одновременно выполнены несколько критериев прекращения процесса. |
Версии: нет
Вызываемые подпрограммы: нет
Замечания по использованию
Подпрограммы FUN и GRAD составляются пользователем. Первый оператор подпрограммы вычисления функции должен иметь вид: SUBROUTINE FUN (X, F, FE) Параметры X - вещественный вектор длины задающий точку пространства, в которой вычисляется значение функции; F - вещественная переменная, содержащая вычисленное значение функции в точке X; FE - вещественная переменная, содержащая на входе заданную точность вычисления значения функции в точке X, а на выходе - достигнутую точность. Если значение достигнутой точности вычисления функции неизвестно, то в теле подпрограммы FUN параметр FE не должен переопределяться. Точность решения задачи по функционалу EPSF и достигнутая точность FE должны быть согласованы, т.е. не следует требовать высокой точности EPSF, если FE невысока. Первый оператор подпрограммы вычисления градиента функции f (x) должен иметь вид: SUBROUTINE GRAD (X, G, GE, I0) Параметры X - вещественный вектор длины N, задающий точку пространства, в которой вычисляется градиент; G - вещественный вектоp длины N, содержащий градиент функции в точке X; GE - вещественный вектоp длины N, содержащий на входе заданную покомпонентную точность вычисления градиента функции, на выходе - достигнутую точность вычисления градиента по всем компонентам; I0 - целый вектоp фиксированных компонент, упpавляющий вычислением компонент градиента: если I0(J) = 0, то полагается G(J) = 0 (тип: целый). Если значение достигнутой точности GE (J) для некоторого J неизвестно, то в теле подпрограммы GRAD параметр GE (J) не должен переопределяться. Точность решения задачи по гpадиенту EPSG и достигнутая точность GE должны быть согласованы, т.е. не следует требовать высокой точности EPSG, если известно, что GE невысока. Имена подпрограмм вычисления значения функции f (x) и ее градиента должны быть определены в вызывающей программе оператором EXTERNAL. Если решается задача безусловной минимизации (т.е. Q = En), то следует задать A (J) = - C и B (J) = C, где C - достаточно большое представимое в машине вещественное число. Подпрограммой пpедусмотpена возможность выдачи значений компонент текущей точки X, значения функции f (x), значений компонент градиента функции f (x), значения нормы градиента. Пробный шаг h по направлению спуска определяется соотношением h = UP (6) * ||G||, где G - градиент функции в начальной точке. В общем случае pекомендуется задавать UP (6) = 0.01 . Обновление метода происходит каждый раз, когда (S, G) < UP (7) * ||G||2, где G - градиент функции f (x), а S - направление спуска. В этом случае делается шаг по антигpадиенту. Рекомендуется при обращении к подпрограмме задавать UP (7) = 0.125 . В общем случае наибольшее влияние на эффективность программы оказывают выбор метода оптимизации (параметр UP (4)) и выбор точности одномерной минимизации (параметp UP (8)). Рекомендуется задавать UP (8) = 0.1 . Если по мнению пользователя метод остановился слишком pано, то следует уменьшить значение UP (8), например, положить его равным 0.01 и повторить счет. Если вычисление значений функции и градиента тpебует значительных затрат, то можно подобрать оптимальные значения параметров упpавления с помощью библиотечной подпрограммы UTMN01. Используются служебные подпрограммы: MNKO1, MNKO2, MNKU1, MNKU2, MNKU3, MNKU4, MNKU5, MNKU6, MNKU7, MNKU8, MNK10, MNK11, MNK12, MNK13, MNK14, MNK15, MNKP0, MNKP1. |
min f(x) , x ∈ Q = { x: x ∈ E4 , -5 ≤ xj ≤ 5 , j = 1, 2, 3, 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
EXTERNAL FUNDO1, GRDDO1 DIMENSION XF(4), XE(4), I0(4), A(4), B(4), G(4), GE(4), UP(9), * RM(40), IRM(7) DATA UP /200., 200., -1., 1., 0., 0.01, 0.125, 0.1, 6./ N = 4 DO 2 I1 = 1, 2 UP(4) = I1 DO 1 I = 1, N A(I) = -5. B(I) = 5. I0(I) = 1 XE(I) = 1.E-04 GE(I) = 1.E-10 1 CONTINUE FE = 1.E-08 XF(1) = -3. XF(2) = -1. XF(3) = 0. XF(4) = 1. CALL MNK1R (XF, XE, I0, A, B, N, FUNDO1, F, FE, GRDDO1, * G, GE, UP, RM, IRM, IERR) 2 CONTINUE Подпрограмма вычисления функции: SUBROUTINE FUNDO1 (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 Подпрограмма вычисления градиента: SUBROUTINE GRDDO1 (X, G, GE, I0) DIMENSION X(4), G(4), GE(4), I0(4) G(1) = 2*( X(1) + 10*X(2) ) + 40*( X(1) - X(4) )**3 G(2) = 20*( X(1) + 10*X(2) ) + 4*( X(2) - 2*X(3) )**3 G(3) = 10*( X(3) - X(4) ) - 8*( X(2) - 2*X(3) )**3 G(4) = 10*( X(4) - X(3) ) - 40*( X(1) - X(4) )**3 RETURN END Результаты: для метода сопряженных градиентов: APГУMEHT(X) ГPAДИEHT(G) -0.7851-02 -0.1815-05 0.7850-03 0.6659-06 -0.7985-02 -0.8042-05 -2.7988-02 -0.2959-04 ЗHAЧEHИE ФYHKЦИИ - ФУНКЦИОНАЛ = 0.789-07 , KОЛИЧЕСТВО ИTEPAЦИЙ 28 , BЫЧИСЛЕНИЙ ФУНКЦИОНАЛА 29 , BЫЧИСЛЕНИЙ ГPАДИЕНТА 134 ;