Метод барьерных функций python

Метод штрафных функций

Функция является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции Z будет находиться внутри области ограничений. Функция , удовлетворяющая этому условию, может быть не единственной. Задачу минимизации можно сформулировать следующим образом:

Функцию удобно записать следующим образом:

где r – положительная величина.

Тогда функция принимает вид

Если х принимает допустимые значения, т.е. значения, для которых , то Z принимает значения, которые больше соответствующих значений (истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций близка к нулю, тогда значения функции , и следовательно значения функции Z станут очень велики. Таким образом, влияние функции состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние было малым в точке минимума, мы можем сделать точку минимума функции без ограничений совпадающей с точкой минимума задачи с ограничениями.

Алгоритм метода штрафных функций

Пусть имеется следующая задача: Минимизировать при ограничениях ,.

Начальный этап Выбрать в качестве константы остановки, начальную допустимую точку ∈, для которой , , скаляр и . Положить k=1 и перейти к основному этапу.

Основной этап. k-я итерация.

Первый шаг. При исходной точке решить следующую задачу безусловной оптимизации:

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

Примерами штрафных функций являются:

2) логарифмическая функция

Положить равным оптимальному решению задачи минимизации и перейти ко второму шагу.

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

Если , то остановиться. Решение является искомым.

В противном случае положить . Изменить и перейти к первому шагу (k+1)-й итерации.

Метод барьерных функций

Изложение метода

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

Пусть имеется задача минимизировать при ограничениях

В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:

— непрерывные функции, которые удовлетворяют условиям: , если и , если , , если и , если .

Типичными являются следующие выражения для функций :

, , где р – целое положительное число.

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

Пусть α– непрерывная функция. Обозначим .

Подход, связанный с барьерной функцией состоит в решении задачи вида:

максимизировать при ограничении

Алгоритм метода барьерных функций

Пусть имеется следующая задача:

Минимизировать при ограничениях ,, где функции .

Начальный этап Выбрать Выбрать начальную точку , параметр штрафа и число . Положить k=1 и перейти к основному этапу.

Основной этап. k-я итерация.

Первый шаг. При начальной точке и параметре штрафа решить следующую задачу:

Положить равным оптимальному решению задачи и перейти ко второму шагу.

В противном случае положить . Заменить k на k+1 и перейти к первому шагу.

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

Рассмотрим задачу Розена-Сузуки и реализуем её решение с помощью метода штрафных функций. Задача Розена-Сузуки заключается в следующем: необходимо минимизировать функцию

со следующими ограничениями

Ниже приведена таблица промежуточных результатов алгоритма.

Число итераций	Значение миимизируемой функции	Координаты первой точки	Координаты второй точки	Координаты третьей точки	Координаты четвертой точки
0	nfmin=-43.739500	x1=-0.010000	x2=0.990000	x3=1.990000	x4=-0.990000
10	nfmin=-43.762449	x1=-0.009498	x2=0.990302	x3=1.991304	x4=-0.990502
20	nfmin=-43.785381	x1=-0.008996	x2=0.990604	x3=1.992607	x4=-0.991004
30	nfmin=-43.808298	x1=-0.008494	x2=0.990906	x3=1.993910	x4=-0.991506
40	nfmin=-43.831199	x1=-0.007993	x2=0.991208	x3=1.995212	x4=-0.992007
50	nfmin=-43.854084	x1=-0.007491	x2=0.991509	x3=1.996514	x4=-0.992509

Оптимальную точку мы получаем на 114й итерации с оптимальным значением функции

Рекомендация программисту

Использование штрафных функций для решения задач связано с определенной вычислительной трудностью. Прежде всего поиск может начинаться с допустимой точки х, для которой , .Для некоторых задач находить такую точку довольно сложно. Кроме того, вследствие использования в алгоритме оптимизации дискретных шагов около границы возможен шаг, который выводит за границы допустимой области. Он приводит к уменьшению значений функции , т.е. к фиктивному успеху. Таким образом, нужна явная проверка допустимости каждой последующей точки, для чего на каждой итерации необходимо вычислять значения функции ,.

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

Список литературы

См. также

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Метод барьерных функций с правилом скорейшего спуска

alex0parhomenko/MethodOfBarrierFunctionsWithTheQuickestDescentRule

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Метод барьерных функций с правилом скорейшего спуска

helpers.py - класс для функции с градиентом settings.py - специализация для конкретного запуска ( python3.6 main.py) fast_descent_method.py - метод скорейшего спуска tests.py - тесты 

python3.6 -m pytest tests.py

About

Метод барьерных функций с правилом скорейшего спуска

Источник

Метод барьерных функций. Нюансы

Всем привет!
Я реализовал методы барьерных и штрафных функций. Функция двух переменных. Решение частное — имеется только одно ограничение вида . Методы не сложные. Воспользовался библиотекой SciPy ( python ). Поиск минимума делаю методом Нелдера — Мида.
Так-же в алгоритме проверяю каждую найденную точку на принадлеженость к допустимой области.
Граница:
Функции штрафа:
1) В методе штрафных функций:
2) В методе барьерных функций:

Вот в чем вопрос. Пока как то точно определить минимум не получается ( сравниваю с wolframalpha ). Подбирая различные исходные точки и различные значения коэффициента штрафа r получается иногда попасть в минимум. В методе штрафных функций это происходит чаще =).
1)Правильно ли я выбрал метод поиска минимума?
2)Как все таки выбирать точки и коэф. штрафа?
3)Нормально ли такое поведения метода штрафов?

Текст программы на python

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

from scipy.optimize import * def penalty_method(func, h, H, x0, eps=1e-4, r=1.0, delta=0.2): """ Минимизация функции с ограничениями методом штрафных функций Алгоритм использует поиск нулевого порядка Нелдера — Мида Параметры -------------- func : функция, которую надо минимизировать h : ограничение на функцию. Решение задачи частное, ограничение одно, вида g(x)  H : штрафная(барьерная) функция x0 : начальное приближение eps : точность вычислений r : коэфицент масштабирования штрафа delta : коэфицент масштабирования r """ res = [] while abs(r*H(h(x0))) > eps: temp = fmin(lambda x: func(x) + r*H(h(x)), x0, maxiter=100) #проверка, лежит ли точка в допустимой области if h(temp)  0.0: x0 = temp r *= delta return x0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

from penalty_method import * #Исходная функция def func(x): A = -2.0/(1.0 + ((x[0] - 2.0)/3.0)**2 + (x[1]-2.0)**2) B = -1.0/(1.0+(x[0]-3.0)**2 + ((x[1]-1.0)/3.0)**2) return A+B #Ограничение функции def g(x): return 3*x[0]+4*x[1]-3 def G1(x): return 0.5*(x + abs(x)) def G2(x): return -1.0 / x res = penalty_method(func=func, h=g, H=G1, x0=[4,8], delta=1.0, eps=1e-4, r=2.0) res = penalty_method(func=func, h=g, H=G2, x0=[-0.7, -0.7], delta=0.1, eps=1e-7, r=3.0) print(func(res))

Источник

Метод штрафных функций Python

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

Основы метода штрафных функций

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

Пример использования метода штрафных функций в Python

Рассмотрим пример оптимизации функции с ограничениями с помощью метода штрафных функций на Python. Задача: минимизировать функцию f(x) = x^2 с ограничением g(x) = x — 2 >= 0 .

import numpy as np from scipy.optimize import minimize def f(x): return x**2 def g(x): return x - 2 def penalty_function(x, r): return f(x) + r * np.maximum(-g(x), 0)**2 r = 1 x0 = 0 res = minimize(lambda x: penalty_function(x, r), x0) while -g(res.x) > 1e-4: r *= 10 res = minimize(lambda x: penalty_function(x, r), x0) print("Оптимальное значение x:", res.x) print("Минимальное значение функции f(x):", f(res.x)) 

В приведенном коде функция penalty_function представляет собой штрафную функцию, которая используется для оптимизации с ограничениями. Параметр r контролирует силу штрафа. Значение x0 является начальной точкой для оптимизации.

Сначала оптимизируется штрафная функция с некоторым начальным значением r . Если ограничение не выполняется (т.е. -g(x) > 1e-4 ), значение r увеличивается, и оптимизация повторяется. Процесс продолжается до тех пор, пока ограничение не будет выполнено с заданной точностью.

Заключение

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

Источник