Найти глобальный минимум, используя scipy.optimize.minimize

Question

Учитывая двумерную точку p, я пытаюсь вычислить наименьшее расстояние между этой точкой и функциональной кривой, т. Е. Найти точку на кривой, которая дает мне наименьшее расстояние до p, а затем вычислить это расстояние. Пример функция, которые я использую

f(x) = 2*sin(x) 

Моей функции расстояния для расстояния между некоторой точкой p и предоставленной функцией

def dist(p, x, func): 
    x = np.append(x, func(x)) 
    return sum([[i - j]**2 for i,j in zip(x,p)]) 

Он принимает в качестве входных данных, точка p, положение x на функцию и дескриптор функции func. Заметим, что это квадратичное евклидово расстояние (так как минимизация в евклидовом пространстве совпадает с минимизацией в квадратичном евклидовом пространстве).

Важнейшая часть этого заключается в том, что я хочу иметь возможность предоставлять ограничения для своей функции, поэтому я нахожу самое близкое расстояние до функционального сегмента. Для этого примера мои оценки являются

bounds = [0, 2*np.pi] 

Я использую функцию scipy.optimize.minimize, чтобы минимизировать свою функцию расстояния, используя границы. Результат вышеуказанного процесса показан на графике ниже.

Это контурный график, показывающий расстояние от функции греха. Обратите внимание на то, что в контурах наблюдается разрыв. Для удобства я нарисовал несколько точек вокруг этого разрыва и точки «шкафа» на кривой, на которую они ориентируются.

Что здесь происходит, так это то, что функция scipy находит локальный минимум (с учетом некоторого начального предположения), но не глобальный, и это вызывает разрыв. Я знаю, что найти глобальный минимум любой функции невозможно, но я ищу более надежный способ найти глобальный минимум.

Возможные методы нахождения глобального минимума будет

1. Выберите смарт начальное предположение, но это сводится к знанию, примерно там, где глобальный минимум должен начаться с, который использует решение проблемы для решения Это.
2. Используйте несколько исходных догадок и выберите ответ, который будет иметь наилучший минимум. Это, однако, кажется плохим выбором, особенно когда мои функции усложняются (и более высокие размеры).
3. Найдите минимум, затем нарушите решение и снова найдите минимум, надеясь, что я, возможно, сбил его с минимальным минимумом. Я надеюсь, что, возможно, есть способ сделать это просто, не вызывая сложный алгоритм MCMC или что-то в этом роде. Скорость рассчитывается для этого процесса.

Любые предложения по лучшему способу об этом, или, возможно, указания на полезные функции, которые могут решить эту проблему, были бы замечательными!

Answer 1

Как подскажите в комментарии, вы можете попробовать глобальный алгоритм оптимизации, такой как scipy.optimize.differential_evolution. Однако в этом случае, когда у вас есть четко определенная и аналитически приемлемая целевая функция, вы можете использовать полуаналитический подход, воспользовавшись необходимыми условиями первого порядка для минимума.

Следующая функция - это метрика расстояния, а вторая функция (числитель) ее производной w.r.t. x, который должен быть равен нулю, если минимум составляет примерно 0<x<2*np.pi.

import numpy as np  
def d(x, p): 
    return np.sum((p-np.array([x,2*np.sin(x)]))**2) 

def diff_d(x, p): 
    return -2 * p[0] + 2 * x - 4 * p[1] * np.cos(x) + 4 * np.sin(2*x) 

Теперь, учитывая точку p, единственные потенциальные минимайзеров d(x,p) корни diff_d(x,p) (если таковые имеются), а также граничные точки x=0 и x=2*np.pi. Оказывается, что diff_d может иметь более одного корня. Отмечая, что производная является непрерывной функцией, библиотека pychebfun предлагает очень эффективный метод поиска всех корней, избегая громоздких подходов, основанных на алгоритмах корневого поиска scipy.

Следующая функция обеспечивает минимум d(x, p) для данной точки p:

import pychebfun 
def min_dist(p): 
    f_cheb = pychebfun.Chebfun.from_function(lambda x: diff_d(x, p), domain = (0,2*np.pi)) 
    potential_minimizers = np.r_[0, f_cheb.roots(), 2*np.pi] 
    return np.min([d(x, p) for x in potential_minimizers]) 

Вот результат: