Информационный портал по безопасности » Программирование » Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python

 

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python

Автор: admin от 13-08-2017, 08:25, посмотрело: 944

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python


Trust-region метод (TRM) является одним из самых важных численных методов оптимизации в решении проблем нелинейного программирования (nonlinear programming problems). Метод базируется на определении региона вокруг лучшего решения, в котором квадратичная модель аппроксимирует целевую функцию.



Методы линейного поиска (line search) и методы trust-region генерируют шаги с помощью аппроксимации целевой функции квадратичной моделью, но использую они эту модель по-разному. Линейный поиск использует её для получения направления поиска и дальнейшего нахождения оптимального шага вдоль направления. Trust-region метод определяет область (регион) вокруг текущей итерации, в котором модель достаточно аппроксимирует целевую функцию. В целях повышения эффективности направление и длина шага выбираются одновременно.



Trust-region методы надежны и устойчивы, могут быть применены к плохо обусловленным задачам и имеют очень хорошие свойства сходимости. Хорошая сходимость обусловлена тем, что размер области TR (обычно определяется модулем радиус-вектора) на каждой итерации зависит от улучшений сделанных на предыдущих итерациях.



Если вычисления показывают достаточно хорошее приближение аппроксимирующей модели к целевой функции, тогда trust-region может быть увеличен. В противном случае, если аппроксимирующая модель работает недостаточно хорошо, trust-region должен быть сокращен.



В итоге получаем приблизительно такую картину:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python


Алгоритм



Шаг №1



Trust-region метод использует квадратичную модель. На каждой итерации шаг вычисляется путем решения следующей квадратичной задачи (subproblem):

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



где Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python;

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python0$" data-tex="inline"> — trust-region радиус;



Таким образом trust-region требует последовательного вычисления аппроксимаций квадратичной модели в которых целевая функция и условие (которое может быть записано Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python) тоже квадратично. Когда гессиан (Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python) положительно определен и Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python решение легко определить — это безусловный минимум Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python. В данном случае Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python называют полным шагом. Решение не так очевидно в других случаях, однако поиск его не стоит слишком дорого. Нам необходимо найти лишь приблизительное решение, чтобы получить достаточную сходимость и хорошее поведение алгоритма на практике.



Существует несколько стратегий аппроксимации квадратичной модели, среди которых следующие:



Алгоритм Cauchy point



Концепция метода схожа с логикой работы алгоритма наискорейшего спуска (steepest descent). Точка Cauchy лежит на градиенте, который минимизирует квадратичную модель при условии наличия шага в trust-region. Посредством последовательного нахождения точек Cauchy, может быть найден локальный минимум. Метод имеет неэффективную сходимость подобно методу наискорейшего спуска.



Алгоритм Steihaug



Метод носит название его исследователя — Steihaug. Представляет из себя модифицированный метод сопряженных градиентов (conjugate gradient approach). Для каждого шага алгоритм определяет итеративную технику, которая практически соответствует стандартной процедуре метода сопряженных градиентов за исключением двух дополнительных условий окончания алгоритма: если следующий шаг находится вне trust-region, если встречается нулевое или отрицательное направление.



Алгоритм Dogleg



В статье будет подробно рассмотрен метод аппроксимации квадратичной модели dogleg, который является одним из самых распространенных и эффективных методов. Используется в случае, если матрица Гессе (или ее приближение) положительна определена.

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



Шаг №2



Первая проблема, которая возникает при определении trust-region алгоритма — это выбор стратегии для поиска оптимального trust-region радиуса Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python на каждой итерации. Выбор основывается на сходстве функции Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python и целевой функции Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python на предыдущей итерации. После нахождения Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python мы определяем следующее соотношение:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Знаменатель всегда должен быть положительно определен, поскольку шаг Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python получается путем минимизации квадратичной модели Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python по региону, который включает в себя шаг Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python. Отношение используется для определения преемственности шага и последующего обновления trust-region радиуса.



Если Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python или Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python мы уменьшаем размер trust-region области.



Если Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python, тогда модель хорошо соответствует целевой функции. В данном случае следует расширить trust-region на следующей итерации.



В других случаяx trust-region остается неизменным.



Шаг №3



Следующий алгоритм описывает процесс:



Определяем стартовую точку Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python, максимальный trust-region радиус Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python, начальный trust-region радиус Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python и константу Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



for k = 0, 1, 2,… пока Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python не оптимум.



Решаем:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



где Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python-решение.

Вычисляем отношение:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Обновляем текущую точку:

$$display$$x_{k+1} = begin{equation*} begin{cases} x_k + p_k & if rho_k>eta, x_k&text{otherwise.} end{cases} end{equation*}$$display$$



Обновляем trust-region радиус:

$$display$$Delta_{k+1}=begin{equation*} begin{cases} frac{1}{4}Delta_k & if rho_kfrac{3}{4} and |p_k|=Delta_k, Delta_k&otherwise. end{cases} end{equation*}$$display$$



Алгоритм в развернутом виде



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python
Заметьте, что радиус увеличивается только если Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python достигает границы trust-region. Если шаг остается строго в регионе, тогда текущее значение не влияет на работу алгоритма и нет необходимости изменять значение радиуса на следующей итерации.



Алгоритм Dogleg



Метод начинается с проверки эффективности trust-region радиуса в решении Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python квадратичной модели Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python. Когда Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python положительна определена, как уже было отмечено, оптимальным решением будет полный шаг Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python. Когда эта точка может быть найдена, очевидно, она будет являться решением.

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Когда Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python весьма мало, ограничение Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python гарантирует, что квадратный член в модели Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python оказывает небольшое влияние на решение. Реальное решение Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python аппроксимируется также, как если бы мы оптимизировали линейную функцию Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python при условии Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python, тогда:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Когда Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python достаточно мало.



Для средних значений Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python решение Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python, как правило, следует за криволинейной траекторией, как показано на картинке:



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python


Dogleg метод аппроксимирует криволинейную траекторию Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python линией состоящей из двух прямыx. Первый отрезок начинается с начала и простирается вдоль направления наискорейшего спуска (steepest descent direction) и определяется следующим образом:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Второй начинается с Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python и продолжается до Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python.



Формально мы обозначим траекторию Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python, где Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python;

$$display$$tilde p(tau) = begin{equation*} begin{cases} tau p^U, &0leqtauleq1, p^U + (tau - 1)(p^B-p^U), &1leqtauleq2. end{cases} end{equation*}$$display$$



Для поиска Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python необходимо решить квадратное уравнение, следующего вида:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Находим дискриминант уравнения:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Корень уравнения равен:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Dogleg метод выбирает Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python, чтобы минимизировать модель Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python вдоль этого пути. В действительности нет необходимости выполнять поиск, поскольку dogleg путь пересекает границу trust-region только один раз и точка пересечения может быть найдена аналитически.



Пример



С использованием алгоритма trust-region (dogleg) оптимизировать следующую функцию (функция Розенброка):

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Находим градиент, якобиан и гессиан функции:



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Инициализируем необходимые переменные для работы алгоритма:



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python = 1.0,

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python = 100.0,

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python,

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python (необходимая точность),

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python.



Итерация 1



Находим оптимальное решение квадратичной модели Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



Поскольку Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python и Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python Delta_k$" data-tex="inline">



Следовательно:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Вычисляем Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



actual reduction = Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



predicted reduction = Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python — остается неизменным.



Обновляем Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Итерация 2



Находим оптимальное решение квадратичной модели Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



Поскольку Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python и Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python Delta_k$" data-tex="inline">.



Следовательно:

Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Вычисляем Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



actual reduction = Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



predicted reduction = Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Т.к. Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python 0.75$" data-tex="inline"> и Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Обновляем Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Итерация 3



Находим оптимальное решение квадратичной модели Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





где Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python.



Вычисляем Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



actual reduction = Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



predicted reduction = Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python — остается прежним.



Обновляем Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python:



Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python





Алгоритм продолжается до тех пока Метод оптимизации Trust-Region DOGLEG. Пример реализации на Pythongtol или не произведено заданное количество итераций.



Таблица результатов работы алгоритма для функции Розенброка:


























































































































































































kМетод оптимизации Trust-Region DOGLEG. Пример реализации на PythonМетод оптимизации Trust-Region DOGLEG. Пример реализации на PythonМетод оптимизации Trust-Region DOGLEG. Пример реализации на PythonМетод оптимизации Trust-Region DOGLEG. Пример реализации на Python
0--1.0[5, 5]
1[-0.9950, 0.0994]1.0721.0[4.0049, 5.0994]
2[-0.9923, 0.1238]1.16592.0[3.0126, 5.2233]
3[-0.2575, 1.9833]1.03262.0[2.7551, 7.2066]
4[-0.0225, 0.2597]1.00262.0[ 2.7325, 7.4663]
5[-0.3605, -1.9672]-0.45870.5[2.7325, 7.4663]
6[-0.0906, -0.4917]0.99661.0[ 2.6419, 6.9746]
7[-0.1873, -0.9822]0.87152.0[ 2.4546, 5.9923]
8[-0.1925, -0.9126]1.27222.0[ 2.2620, 5.0796]
9[-0.1499, -0.6411]1.35562.0[ 2.1121, 4.4385]
10[-0.2023, -0.8323]1.05942.0[ 1.9097, 3.6061]
11[-0.0989, -0.3370]1.27402.0[ 1.8107, 3.2690]
12[-0.2739, -0.9823]-0.79630.25495[ 1.8107, 3.2690]
13[-0.0707, -0.2449]1.08110.5099[ 1.7399, 3.0240]
14[-0.1421, -0.4897]0.87951.0198[1.5978, 2.5343]
15[-0.1254, -0.3821]1.31221.0198[ 1.4724, 2.1522]
16[-0.1138, -0.3196]1.30551.0198[ 1.3585, 1.8326]
17[-0.0997, -0.2580]1.30251.0198[ 1.2587, 1.5745]
18[-0.0865, -0.2079]1.28781.0198[ 1.1722, 1.3666]
19[-0.0689, -0.1541]1.27801.0198[ 1.1032, 1.2124]
20[-0.0529, -0.1120]1.24321.0198[ 1.0503, 1.1004]
21[-0.0322, -0.0649]1.19711.0198[1.0180, 1.0354]
22[-0.0149, -0.0294]1.10971.0198[ 1.0031, 1.0060]
23[-0.0001, -0.0002]1.00121.0198[ 1.00000024, 1.00000046]
24[-2.37065e-07, -4.56344e-07]1.00001.0198[ 1.0, 1.0]




Аналитически находим минимум функции Розенброка, он достигается в точке Метод оптимизации Trust-Region DOGLEG. Пример реализации на Python. Таким образом можно убедиться в эффективности алгоритма.



Пример реализации на Python



Алгоритм реализован с использованием библиотеки numpy. В примере наложено ограничение на количество итераций.



#!/usr/bin/python
# -*- coding: utf-8 -*-
import numpy as np
import numpy.linalg as ln
from math import sqrt

def f(x):
    return (1-x[0])**2 + 100*(x[1]-x[0]**2)**2

def jac(x):
    return np.array([-400*(x[1] - x[0]**2)*x[0] - 2 + 2*x[0], 200*x[1] - 200*x[0]**2])

def hess(x):
    return np.array([[1200*x[0]**2 - 400*x[1]+2, -400*x[0]], [-400*x[0], 200]])


def dogleg_update(Hk, gk, Bk, trust_radius):

    # Calculate the full step and its norm.
    pB = -np.dot(Hk, gk)
    norm_pB = sqrt(np.dot(pB, pB))

    # Test if the full step is within the trust region.
    if norm_pB <= trust_radius:
        return pB

    # Calculate pU.
    pU = - (np.dot(gk, gk) / np.dot(gk, np.dot(Bk, gk))) * gk
    dot_pU = np.dot(pU, pU)
    norm_pU = sqrt(dot_pU)

    # Test if the step pU exits the trust region.
    if norm_pU >= trust_radius:
        return trust_radius * pU / norm_pU

    # Find the solution to the scalar quadratic equation.
    pB_pU = pB - pU
    dot_pB_pU = np.dot(pB_pU, pB_pU)
    dot_pU_pB_pU = np.dot(pU, pB_pU)
    fact = dot_pU_pB_pU**2 - dot_pB_pU * (dot_pU - trust_radius**2)
    tau = (-dot_pU_pB_pU + sqrt(fact)) / dot_pB_pU
    
    # Decide on which part of the trajectory to take.
    return pU + tau * pB_pU
    

def trust_region_dogleg(func, jac, hess, x0, initial_trust_radius=1.0,
                        max_trust_radius=100.0, eta=0.15, gtol=1e-4,
                        maxiter=400):
    xk = x0
    trust_radius = initial_trust_radius
    k = 0
    while True:
        
        # Initialize the search
        gk = jac(xk)
        Bk = hess(xk)
        Hk = np.linalg.inv(Bk)
        
        # Solve the sub-problem.
        pk = dogleg_update(Hk, gk, Bk, trust_radius)
       
        act_red = func(xk) - func(xk + pk)

        pred_red = -(np.dot(gk, pk) + 0.5 * np.dot(pk, np.dot(Bk, pk)))
        
        # Evaluate the ratio
        rhok = act_red / pred_red
        if pred_red == 0.0:
            rhok = 1e99
        else:
            rhok = act_red / pred_red
        norm_pk = sqrt(np.dot(pk, pk))
        
        # Update the trust radius according to the actual/predicted ratio
        if rhok < 0.25:
            trust_radius = 0.25 * norm_pk
        else: 
            if rhok > 0.75 and norm_pk == trust_radius:
                trust_radius = min(2.0*trust_radius, max_trust_radius)
            else:
                trust_radius = trust_radius
        
        if rhok > eta:
            xk = xk + pk
        else:
            xk = xk
            
        # Check if the gradient is small enough to stop
        if ln.norm(gk) < gtol:
            break
        
        # Check if we have looked at enough iterations
        if k >= maxiter:
            break
        k = k + 1
    return xk
    
result = trust_region_dogleg(f, jac, hess, [5, 5])
print("Result of trust region dogleg method:")
print(result)
print("Value of function at a point:")
print(f(result))


Спасибо за интерес проявленный к моей статье. Надеюсь она была Вам полезна и Вы узнали много нового. Самый лучший способ отблагодарить автора — оценить статью.



О всех неточностях сообщайте, пожалуйста, в личных сообщениях.

Источник: Хабрахабр

Категория: Программирование

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent