|
Текст подпрограммы и версий ( Фортран ) mne1r.zip , mne1d.zip |
Тексты тестовых примеров ( Фортран ) tmne1r.zip , tmne1d.zip |
|
Текст подпрограммы и версий ( Си ) mne1r_c.zip , mne1d_c.zip |
Тексты тестовых примеров ( Си ) tmne1r_c.zip , tmne1d_c.zip |
|
Текст подпрограммы и версий ( Паскаль ) mne1r_p.zip , mne1e_p.zip |
Тексты тестовых примеров ( Паскаль ) tmne1r_p.zip , tmne1e_p.zip |
Решение задачи безусловной минимизации выпуклой недифференцируемой функции многих переменных субградиентным методом.
Для решения задачи:
min f(x) , x ∈ En ,
где f (x) - выпуклая недифференцируемая функция, применяется субградиентный метод последовательной релаксации с построением сопряженных направлений. Для ускорения сходимости и уточнения длины шага может проводиться одномерная минимизация по направлению.
Коннов И.В. Субградиентный метод последовательной релаксации для решения задач оптимизации. Деп.ВИНИТИ, N 531 - 83.
Демьянов В.Ф., Васильев Л.Ф. Недифференцируемая оптимизация. М.: Наука, 1981.
SUBROUTINE MNE1R (F, FE, FUNC, G, GE, IERR, I0, N, RM,
SUBG, UP, X, XE)
Параметры
| F - | вещественная переменная, содержащая вычисленное минимальное значение F (x); |
| FE - | заданная точность решения задачи по функции (тип: вещественный); |
| FUNC - | имя подпрограммы вычисления значения функции F (x) (см. замечания по использованию); |
| G - | вещественный вектор длины N, содержащий субградиент функции F в вычисленной точке X; |
| GE - | вещественный вектор длины N, задающий точность решения задачи по субградиенту; |
| IERR - | целая переменная, указывающая причину окончания процесса; |
| IERR=1 - | найден минимум с заданной точностью по аргументу; |
| IERR=2 - | найден минимум с заданной точностью по функции; |
| IERR=3 - | найден минимум с заданной точностью по субградиенту; |
| IERR=4 - | выполнено максимальное (см. UP (4)) количество вычислений функции; |
| IERR=5 - | истекло заданное время, отведенное пользователем на решение задачи (см. UP (5)); |
| IERR=6 - | произошло замедление счета (см.замечания по использованию); |
| I0 - | целый вектор длины N, задающий фиксированные на время минимизации компоненты вектора X: если I0 (I) = 0, то I - ая компонента вектора X остается равной своему начальному значению; |
| N - | размерность пространства переменных (тип: целый); |
| RM - | вещественный вектор длины 2N, используемый в подпрограмме как рабочий; |
| SUBG - | имя подпрограммы вычисления субградиента функции F (x) (см.замечания по использованию); |
| UP - | вещественный вектор длины 9, задающий управляющие параметры алгоритма; |
| UP(1) - | заданная начальная длина шага; |
| UP(2) - | заданная константа дробления шага, 0 < UP (2) < 1; |
| UP(3) - | заданный коэффициент, определяющий величину убывания функции на одной итерации, 0 < UP (3) < 1; |
| UP(4) - | заданное максимально допустимое количество вычислений функции; |
| UP(5) - | время, отведенное центральному процессору на решение задачи, задается пользователем в секундах; |
| UP(6),UP(7) - | параметры, формирующие критерий замедления счета; рекомендуется задавать на входе UP (6) = 0, тогда эти параметры вычисляются автоматически внутри подпрограммы; |
| UP(8) - | заданный параметр, определяющий, через сколько итераций проводится одномерная минимизация (см. замечания по использованию); |
| UP(9) - | заданный признак печати сообщения об окончании счета: UP (9) = 1 - печатается сообщение о выполнившемся критерии останова, UP (9) = 0 - сообщение не печатается; |
| X - | вещественный вектор длины N; при обращении к подпрограмме содержит заданную начальную точку поиска, при выходе содержит точку минимума функции f (x); |
| XE - | вещественный вектор длины N, задающий точность решения задачи по аргументу. |
Версии
| MNE1D - | решение задачи безусловной минимизации выпуклой недифференцируемой функции многих переменных субградиентным методом, при этом вычисления проводятся с удвоенной точностью. Параметры F, FE, G, GE, RM, X, XE подпрограммы MNE1D и подпрограмм FUNC, SUBG должны иметь тип DOUBLE PRECISION. Тип остальных параметров не изменяется. |
Вызываемые подпрограммы
| MNB8R - | подпрограмма минимизации функции многих переменных по заданному направлению методом золотого сечения; вызывается при работе подпрограммы MNE1R; |
| MNB8D - | подпрограмма минимизации по заданному направлению методом золотого сечения; вычисления проводятся с двойной точностью; вызывается при работе подпрограммы MNE1D . |
Замечания по использованию
|
Подпрограммы FUN и SUBG составляются пользователем. Первый оператор подпрограммы вычисления функции должен иметь вид: SUBROUTINE FUN (X, F, FE) Параметры: |
| X - | вещественный вектор длины N, содержащий текущую точку пространства, в которой вычисляется значение функции; |
| F - | вещественная переменная, содержащая вычисленное значение функции в точке X; |
| FE - | вещественная переменная, содержащая на входе заданную точность вычисления значения функции в точке X, а на выходе - достигнутую точность. |
|
Если значение достигнутой точности вычисления функции
неизвестно, то в теле подпрограммы FUN параметр FE не должен
переопределяться. Первый оператор подпрограммы вычисления субградиента должен иметь вид: SUBROUTINE SUBG (X, G, GE, I0) Параметры: |
| X - | вещественный вектор длины N, содержащий текущую точку пространства, в которой вычисляется субградиент; |
| G - | вещественный вектор длины N, содержащий вычисленный субградиент (произвольный из множества субградиентов) в точке X; |
| GE - | вещественный вектор длины N, содержащий на входе заданную покомпонентную точность вычисления субградиента функции, а на выходе - достигнутую точность вычисления субградиента; |
| I0 - | целый вектор фиксированных компонент, управляющий вычислением компонент субградиента: если I0 (I) = 0, то полагается G (I) = 0 . |
|
Если значение достигнутой точности GE (I) для
некоторого I неизвестно, то в теле подпрограммы SUBG
параметр GE (I) не должен переопределяться.
Имена подпрограмм вычисления значения функции и ее субградиента должны быть определены в вызывающей программе оператором EXTERNAL. Не рекомендуется проводить одномерную минимизацию на каждой итерации, так как построенное направление не является, вообще говоря, направлением наискорейшего убывания. Рекомендуется задавать UP (8) > 4, либо UP (8) = 0 (в этом случае одномерная минимизация не проводится). Для лучшего согласования управляющих параметров в процессе счета полезно задавать начальный шаг достаточно большим. Признак выхода из подпрограммы по замедлению счета IERR = 6 указывает на слишком медленную сходимость алгоритма, то есть изменение функции на каждой итерации оказывается на несколько порядков меньше, чем разность между текущим значением и минимальным. При работе подпрограммы MNE1R используются следующие
служебные подпрограммы и общие блоки: MNE1D1, MNE1D2, MNE1D3, MNE1D4, MNE1D5, MMKRID, MNR1ND, UTMN05, UTMNE1 COMMON /MMKRD/ ZF, KR, AKR, DF |
Найти минимальное значение функции
f(x) = | x1 + 2 | + | 4x2 - 6 | ;
начальное приближение x = (- 3., 1.)
DIMENSION X(2), G(2), RM(4), UP(9), GE(2), XE(2)
DIMENSION I0(2)
REAL X, G, RM, UP, GE, XE
INTEGER I0
EXTERNAL CONUS, SUBCON
DATA FE /1.E - 7/, XE /2*1.E - 8/, GE /2*1.E - 3/
DATA UP /5., 0.7, 0.3, 500, 600, 0., 0., 10, 1/
DATA I0 /2*1/
DATA N /2/, X /- 3., 1./
CALL MNE1R (F, FE, CONUS, G, GE, IERR, I0, N, RM, SUBCON,
* UP, X, XE)
END
Подпрограмма вычисления значений функции f(x):
SUBROUTINE CONUS (X, F, FE)
REAL X(1), A(2), B(2)
DATA A /1., 4./
DATA B /- 2., 6./
F = 0.
DO 1 I = 1, 2
ARG = A(I)*X(I) - B(I)
F = F + ABS(ARG)
1 CONTINUE
RETURN
END
Подпрограмма вычисления субградиента функции f(x)
SUBROUTINE SUBCON (X, G, GE, I0)
C BЫЧИCЛЯET CУБГPAДИEHT Ф-ЦИИ CONUS
REAL X(1), G(1), GE(1), A(2), B(2)
INTEGER I0(1)
DATA A /1., 4./
DATA B /- 2., 6./
DO 1 I = 1, 2
IF (I0(I) .EQ. 0) GO TO 2
ARG = A(I)*X(I) - B(I)
G(I) = SIGN(1., ARG)*A(I)
GO TO 1
2 G(I) = 0.
1 CONTINUE
RETURN
END
Результаты счета:
Библиотека НИВЦ МГУ, подпрограмма MNE1R
Выполнено максимальное количество вычислений функции
X = - 2.0000001 1.5000000
F = 0.0000001
IERR = 4