scipy.optimize.

shgo#

scipy.optimize.shgo(функция, границы, args=(), ограничения=None, n=100, итераторы=1, callback=None, minimizer_kwargs=None, опции=None, sampling_method='simplicial', *, workers=1)[источник]#

Находит глобальный минимум функции с использованием оптимизации SHG.

SHGO означает "симплициальная гомологическая глобальная оптимизация".

Параметры:

функцияcallable

Целевая функция для минимизации. Должна быть в форме f(x, *args), где x является аргументом в виде одномерного массива и args является кортежем любых дополнительных фиксированных параметров, необходимых для полного определения функции.

границыпоследовательность или Bounds

Границы для переменных. Есть два способа указать границы:

Экземпляр Bounds класс.
Последовательность (min, max) пары для каждого элемента в x.

argsкортеж, необязательный

Любые дополнительные фиксированные параметры, необходимые для полного определения целевой функции.

ограничения{Constraint, dict} или список {Constraint, dict}, необязательно

Определение ограничений. Только для COBYLA, COBYQA, SLSQP и trust-constr. См. учебник [5] для дополнительных сведений о задании ограничений.

Примечание

Только методы локальной минимизации COBYLA, COBYQA, SLSQP и trust-constr в настоящее время поддерживают аргументы ограничений. Если constraints последовательность, используемая в локальной задаче оптимизации, не определена в minimizer_kwargs и используется ограниченный метод, то глобальный constraints будет использоваться. (Определение constraints последовательность в minimizer_kwargs означает, что constraints не будет добавлен, поэтому если необходимо добавить ограничения равенства и т.д., то следует использовать функции неравенства в constraints : MAINT: упрощение detrend minimizer_kwargs тоже). COBYLA поддерживает только ограничения-неравенства.

Изменено в версии 1.11.0: constraints принимает NonlinearConstraint, LinearConstraint.

nint, необязательный

Количество точек выборки, используемых при построении симплициального комплекса. Для значения по умолчанию simplicial метод выборки 2**dim + 1 генерируются точки выборки вместо стандартных n=100. Для всех других указанных значений n генерируются точки выборки. Для sobol, halton и другие произвольные методы_выборки n=100 или генерируется другое указанное количество точек выборки.

итераторыint, необязательный

Количество итераций, используемых при построении симплициального комплекса. По умолчанию: 1.

callbackвызываемый объект, необязательный

Вызывается после каждой итерации, как callback(xk), где xk является текущим вектором параметров.

minimizer_kwargsdict, optional

Дополнительные ключевые аргументы для передачи минимизатору scipy.optimize.minimize. Некоторые важные опции могут быть:

методstr: Метод минимизации. Если не задан, выбирается один из BFGS, L-BFGS-B, SLSQP в зависимости от наличия ограничений или границ.
argsкортеж: Дополнительные аргументы, передаваемые в целевую функцию (func) и его производные (Якобиан, Гессиан).
опцииdict, optional: Обратите внимание, что по умолчанию допуск указывается как {ftol: 1e-12}

опцииdict, optional

Словарь опций решателя. Многие из опций, указанных для глобальной процедуры, также передаются в scipy.optimize.minimize подпрограммы. Опции, которые также передаются в локальную подпрограмму, помечены "(L)".

Критерии остановки: алгоритм завершится при выполнении любого из указанных критериев. Однако алгоритм по умолчанию не требует указания каких-либо критериев:

maxfevint (L): Максимальное количество вычислений функции в допустимой области. (Примечание: только методы, поддерживающие эту опцию, завершат процедуру точно по указанному значению. В противном случае критерий завершится только во время глобальной итерации)
f_minfloat: Укажите минимальное значение целевой функции, если оно известно.
f_tolfloat: Целевая точность для значения f в критерии остановки. Обратите внимание, что глобальная процедура также завершится, если точка выборки в глобальной процедуре находится в пределах этого допуска.
maxiterint: Максимальное количество итераций для выполнения.
maxevint: Максимальное количество выполняемых оценок выборки (включает поиск в недопустимых точках).
maxtimefloat: Максимально допустимое время выполнения обработки
minhgrdint: Минимальный дифференциал ранга группы гомологий. Группа гомологий целевой функции вычисляется (приблизительно) на каждой итерации. Ранг этой группы имеет взаимно-однозначное соответствие с количеством локально выпуклых подобластей в целевой функции (после адекватной выборки точек каждая из этих подобластей содержит уникальный глобальный минимум). Если разница в hgr равна 0 между итерациями для maxhgrd указанное количество итераций, после которого алгоритм завершится.

Знание целевой функции:

симметриясписок или булево значение

Укажите, содержит ли целевая функция симметричные переменные. Пространство поиска (и, следовательно, производительность) уменьшается до O(n!) раз в полностью симметричном случае. Если True если указано, то все переменные будут установлены симметрично первой переменной. По умолчанию установлено значение False.

Например, f(x) = (x_1 + x_2 + x_3) + (x_4)**2 + (x_5)**2 + (x_6)**2

В этом уравнении x_2 и x_3 симметричны x_1, а x_5 и x_6 симметричны x_4, это можно указать решателю как:

symmetry = [0,  # Variable 1
            0,  # symmetric to variable 1
            0,  # symmetric to variable 1
            3,  # Variable 4
            3,  # symmetric to variable 4
            3,  # symmetric to variable 4
            ]

jacbool или callable, необязательно

Якобиан (градиент) целевой функции. Только для CG, BFGS, Newton-CG, L-BFGS-B, TNC, SLSQP, dogleg, trust-ncg. Если jac является логическим значением и равен True, fun предполагается, что возвращает градиент вместе с целевой функцией. Если False, градиент будет оценен численно. jac также может быть вызываемым объектом, возвращающим градиент целевой функции. В этом случае он должен принимать те же аргументы, что и fun. (Передаётся в scipy.optimize.minimize автоматически)

hess, hesspвызываемый объект, необязательный

Матрица Гессе (матрица вторых производных) целевой функции или матрица Гессе целевой функции, умноженная на произвольный вектор p. Только для Newton-CG, dogleg, trust-ncg. Только один из hessp или hess должен быть задан. Если hess предоставляется, тогда hessp будет проигнорировано. Если ни hess ни hessp предоставлен, то произведение Гессе будет аппроксимировано с использованием конечных разностей на jac. hessp должен вычислять матрицу Гессе, умноженную на произвольный вектор. (Передается в scipy.optimize.minimize автоматически)

Настройки алгоритма:

minimize_every_iterbool: Если True, то перспективные глобальные точки выборки будут передаваться в локальную процедуру минимизации на каждой итерации. Если True, то только финальный пул минимизаторов будет запущен. По умолчанию True.
local_iterint: Оценивайте только несколько лучших кандидатов из пула минимизаторов на каждой итерации. Если False, все потенциальные точки передаются в локальную процедуру минимизации.
infty_constraintsbool: Если True, то любые сгенерированные точки выборки, находящиеся вне допустимой области, будут сохранены и им будет присвоено значение целевой функции inf. Если False, то эти точки будут отброшены. Использование этой функции может привести к повышению производительности с точки зрения вычислений функции до нахождения глобального минимума, указание False будет использовать меньше памяти за счет небольшого снижения производительности. По умолчанию True.

Обратная связь:

dispbool (L): Установите True для вывода сообщений о сходимости.

sampling_methodstr или функция, опционально

Текущие встроенные варианты методов выборки: halton, sobol и simplicial. По умолчанию simplicial обеспечивает теоретическую гарантию сходимости к глобальному минимуму за конечное время. halton и sobol метод быстрее с точки зрения генерации точек выборки за счёт потери гарантированной сходимости. Он более подходит для большинства «простых» задач, где сходимость относительно быстрая. Пользовательские функции выборки должны принимать два аргумента n точки выборки размерности dim за вызов и выводит массив точек дискретизации с формой n x dim.

workersint или вызываемый объект, подобный отображению, необязательный

Запускайте локальные серийные минимизации параллельно. Укажите -1 для использования всех доступных ядер CPU, или целое число для использования указанного количества процессов (использует multiprocessing.Pool).

Альтернативно предоставьте вызываемый объект, подобный map, такой как multiprocessing.Pool.map для параллельного вычисления. Это вычисление выполняется как workers(func, iterable). Требует, чтобы функция быть сериализуемым через pickle.

Добавлено в версии 1.11.0.

Возвращает:

resOptimizeResult: Результат оптимизации, представленный как OptimizeResult объект. Важные атрибуты: x массив решений, соответствующий глобальному минимуму, fun выход функции в глобальном решении, xl упорядоченный список локальных минимумов решений, funl выход функции в соответствующих локальных решениях, success логический флаг, указывающий на успешный выход оптимизатора, message которое описывает причину завершения, nfev общее количество вычислений целевой функции, включая вызовы выборки, nlfev общее количество вычислений целевой функции, накопленное в результате всех локальных поисковых оптимизаций, nit количество итераций, выполненных глобальной процедурой.

Примечания

Глобальная оптимизация с использованием симплициальной гомологической глобальной оптимизации [1]. Подходит для решения общих задач НЛП и задач оптимизации черного ящика до глобального оптимума (низкоразмерные задачи).

В общем случае задачи оптимизации имеют вид:

minimize f(x) subject to

g_i(x) >= 0,  i = 1,...,m
h_j(x)  = 0,  j = 1,...,p

где x — вектор одной или нескольких переменных. f(x) является целевой функцией R^n -> R, g_i(x) являются ограничениями-неравенствами, и h_j(x) являются ограничениями равенства.

Опционально, нижние и верхние границы для каждого элемента в x также могут быть указаны с помощью границы аргумент.

Хотя большинство теоретических преимуществ SHGO доказаны только для случаев, когда f(x) является липшицевой гладкой функцией, алгоритм также доказанно сходится к глобальному оптимуму для более общего случая, когда f(x) является непрерывным, невыпуклым и негладким, если используется метод выборки по умолчанию [1].

Метод локального поиска может быть указан с помощью minimizer_kwargs параметр, который передаётся в scipy.optimize.minimize. По умолчанию, SLSQP используется метод. В общем случае рекомендуется использовать SLSQP, COBYLA, или COBYQA локальной минимизации, если определены ограничения-неравенства для задачи, поскольку другие методы не используют ограничения.

The halton и sobol метод точки генерируются с использованием scipy.stats.qmc. Может использоваться любой другой метод QMC.

Ссылки

[1] (1,2)

Эндрес, SC, Сандрок, C, Фоке, WW (2018) "Алгоритм симплициальной гомологии для липшицевой оптимизации", Journal of Global Optimization.

[2]

Джо, SW и Куо, FY (2008) «Построение последовательностей Соболя с лучшими двумерными проекциями», SIAM J. Sci. Comput. 30, 2635-2654.

[3] (1,2)

Hock, W и Schittkowski, K (1981) "Тестовые примеры для кодов нелинейного программирования", Лекционные заметки по экономике и математическим системам, 187. Springer-Verlag, Нью-Йорк. http://www.ai7.uni-bayreuth.de/test_problem_coll.pdf

[4]

Wales, DJ (2015) "Perspective: Insight into reaction coordinates and dynamics from the potential energy landscape", Journal of Chemical Physics, 142(13), 2015.

[5]

https://docs.scipy.org/doc/scipy/tutorial/optimize.html#constrained-minimization-of-multivariate-scalar-functions-minimize

Примеры

Сначала рассмотрим задачу минимизации функции Розенброка, rosen:

>>> from scipy.optimize import rosen, shgo
>>> bounds = [(0,2), (0, 2), (0, 2), (0, 2), (0, 2)]
>>> result = shgo(rosen, bounds)
>>> result.x, result.fun
(array([1., 1., 1., 1., 1.]), 2.920392374190081e-18)

Обратите внимание, что границы определяют размерность целевой функции и поэтому являются обязательным входным параметром, однако вы можете указать пустые границы, используя None или объекты, такие как np.inf которые будут преобразованы в большие числа с плавающей запятой.

>>> bounds = [(None, None), ]*4
>>> result = shgo(rosen, bounds)
>>> result.x
array([0.99999851, 0.99999704, 0.99999411, 0.9999882 ])

Далее рассмотрим функцию Eggholder — задачу с несколькими локальными минимумами и одним глобальным минимумом. Мы продемонстрируем использование аргументов и возможности shgo. (https://en.wikipedia.org/wiki/Test_functions_for_optimization)

>>> import numpy as np
>>> def eggholder(x):
...     return (-(x[1] + 47.0)
...             * np.sin(np.sqrt(abs(x[0]/2.0 + (x[1] + 47.0))))
...             - x[0] * np.sin(np.sqrt(abs(x[0] - (x[1] + 47.0))))
...             )
...
>>> bounds = [(-512, 512), (-512, 512)]

shgo имеет встроенные последовательности выборки с низкой дисперсией. Сначала мы введем 64 начальные точки выборки Соболя последовательность:

>>> result = shgo(eggholder, bounds, n=64, sampling_method='sobol')
>>> result.x, result.fun
(array([512.        , 404.23180824]), -959.6406627208397)

shgo также возвращает любые другие найденные локальные минимумы, их можно вызвать с помощью:

>>> result.xl
array([[ 512.        ,  404.23180824],
       [ 283.0759062 , -487.12565635],
       [-294.66820039, -462.01964031],
       [-105.87688911,  423.15323845],
       [-242.97926   ,  274.38030925],
       [-506.25823477,    6.3131022 ],
       [-408.71980731, -156.10116949],
       [ 150.23207937,  301.31376595],
       [  91.00920901, -391.283763  ],
       [ 202.89662724, -269.38043241],
       [ 361.66623976, -106.96493868],
       [-219.40612786, -244.06020508]])

>>> result.funl
array([-959.64066272, -718.16745962, -704.80659592, -565.99778097,
       -559.78685655, -557.36868733, -507.87385942, -493.9605115 ,
       -426.48799655, -421.15571437, -419.31194957, -410.98477763])

Эти результаты полезны в приложениях, где существует много глобальных минимумов и требуются значения других глобальных минимумов или где локальные минимумы могут дать представление о системе (например, морфологии в физической химии [4]).

Если мы хотим найти больше локальных минимумов, мы можем увеличить количество точек выборки или количество итераций. Мы увеличим количество точек выборки до 64 и количество итераций с значения по умолчанию 1 до 3. Используя simplicial это дало бы нам 64 x 3 = 192 начальные точки выборки.

>>> result_2 = shgo(eggholder,
...                 bounds, n=64, iters=3, sampling_method='sobol')
>>> len(result.xl), len(result_2.xl)
(12, 23)

Обратите внимание на разницу между, например, n=192, iters=1 и n=64, iters=3. В первом случае перспективные точки, содержащиеся в пуле минимизатора, обрабатываются только один раз. Во втором случае они обрабатываются каждые 64 точки выборки, всего 3 раза.

Для демонстрации решения задач с нелинейными ограничениями рассмотрим следующий пример из задачи 73 Хока и Шитковски (корм для скота) [3]:

minimize: f = 24.55 * x_1 + 26.75 * x_2 + 39 * x_3 + 40.50 * x_4

subject to: 2.3 * x_1 + 5.6 * x_2 + 11.1 * x_3 + 1.3 * x_4 - 5    >= 0,

            12 * x_1 + 11.9 * x_2 + 41.8 * x_3 + 52.1 * x_4 - 21
                -1.645 * sqrt(0.28 * x_1**2 + 0.19 * x_2**2 +
                              20.5 * x_3**2 + 0.62 * x_4**2)      >= 0,

            x_1 + x_2 + x_3 + x_4 - 1                             == 0,

            1 >= x_i >= 0 for all i

Приблизительный ответ, данный в [3] равен:

f([0.6355216, -0.12e-11, 0.3127019, 0.05177655]) = 29.894378

>>> def f(x):  # (cattle-feed)
...     return 24.55*x[0] + 26.75*x[1] + 39*x[2] + 40.50*x[3]
...
>>> def g1(x):
...     return 2.3*x[0] + 5.6*x[1] + 11.1*x[2] + 1.3*x[3] - 5  # >=0
...
>>> def g2(x):
...     return (12*x[0] + 11.9*x[1] +41.8*x[2] + 52.1*x[3] - 21
...             - 1.645 * np.sqrt(0.28*x[0]**2 + 0.19*x[1]**2
...                             + 20.5*x[2]**2 + 0.62*x[3]**2)
...             ) # >=0
...
>>> def h1(x):
...     return x[0] + x[1] + x[2] + x[3] - 1  # == 0
...
>>> cons = ({'type': 'ineq', 'fun': g1},
...         {'type': 'ineq', 'fun': g2},
...         {'type': 'eq', 'fun': h1})
>>> bounds = [(0, 1.0),]*4
>>> res = shgo(f, bounds, n=150, constraints=cons)
>>> res
 message: Optimization terminated successfully.
 success: True
     fun: 29.894378159142136
    funl: [ 2.989e+01]
       x: [ 6.355e-01  1.137e-13  3.127e-01  5.178e-02] # may vary
      xl: [[ 6.355e-01  1.137e-13  3.127e-01  5.178e-02]] # may vary
     nit: 1
    nfev: 142 # may vary
   nlfev: 35 # may vary
   nljev: 5
   nlhev: 0

>>> g1(res.x), g2(res.x), h1(res.x)
(-5.062616992290714e-14, -2.9594104944408173e-12, 0.0)