Метод Стронгина — метод решения одномерных задач условной липшицевой оптимизации. Позволяет находить глобально оптимальное решение в задачах с ограничениями неравенствами при условии, что целевая функция задачи и левые части неравенств удовлетворяют условию Липшица в области поиска.
Постановка задачи оптимизации
Требуется найти точку x ∗ ∈ [ a ; b ] {displaystyle x^{*}in [a;;b]} такую, что f ( x ∗ ) = min { f ( x ) : x ∈ [ a ; b ] , g j ( x ) ⩽ 0 , 1 ⩽ j ⩽ m } {displaystyle f(x^{*})=min left{f(x)colon xin [a;;b],;g_{j}(x)leqslant 0,;1leqslant jleqslant m ight}} . Предполагается, что функции f ( x ) {displaystyle f(x)} и g j ( x ) , j = 1 , m ¯ {displaystyle g_{j}(x),;j={overline {1,;m}}} удовлетворяют условию Липшица на отрезке [ a ; b ] {displaystyle [a;;b]} .
Обозначим g m + 1 ( x ) = f ( x ) {displaystyle g_{m+1}(x)=f(x)} , тогда для j = 1 , m + 1 ¯ {displaystyle j={overline {1,;m+1}}} выполняются следующие неравенства:
| g j ( x + Δ x ) − g j ( x ) | ⩽ L j Δ x , a ⩽ x + Δ x ⩽ b , {displaystyle |g_{j}(x+Delta x)-g_{j}(x)|leqslant L_{j}Delta x,;aleqslant x+Delta xleqslant b,}где L j ⩾ 0 {displaystyle L_{j}geqslant 0} — константы Липшица.
Описание схемы учета ограничений
Пусть Q 0 = [ a ; b ] {displaystyle Q_{0}=[a;;b]} . Ограничение, имеющее номер j {displaystyle j} , выполняется во всех точках области Q j = { x ∈ [ a ; b ] : g j ( x ) ⩽ 0 } {displaystyle Q_{j}=left{xin [a;;b]colon g_{j}(x)leqslant 0 ight}} , которая называется допустимой для этого ограничения. При этом допустимая область Q {displaystyle Q} исходной задачи определяется равенством:
Q = ⋂ j = 0 m Q j . {displaystyle Q=igcap _{j=0}^{m}Q_{j}.}Испытание в точке x ∈ [ a ; b ] {displaystyle xin [a;;b]} состоит в последовательном вычислении значений величин g 1 ( x ) , … , g ν ( x ) {displaystyle g_{1}(x),;ldots ,;g_{ u }(x)} , где значение индекса ν {displaystyle u } определяется условиями:
x ∈ Q j , 0 ⩽ j < ν , x ∉ Q ν . {displaystyle xin Q_{j},;0leqslant j< u ,;x otin Q_{ u }.}Выявление первого нарушенного ограничения прерывает испытание в точке x {displaystyle x} . В случае, когда точка x {displaystyle x} допустима, то есть x ∈ Q {displaystyle xin Q} испытание включает в себя вычисление всех функций задачи. При этом значение индекса принимается равным величине ν = m + 1 {displaystyle u =m+1} .
Пара ν = ν ( x ) , z = g ν ( x ) {displaystyle u = u (x),;z=g_{ u }(x)} , где индекс ν {displaystyle u } лежит в границах 1 ⩽ ν ⩽ m + 1 {displaystyle 1leqslant u leqslant m+1} , называется результатом испытания в точке x {displaystyle x} .
Такой подход к проведению испытаний позволяет свести исходную задачу с функциональными ограничениями к безусловной задаче минимизации разрывной функции:
ψ ( x ∗ ) = min x ∈ [ a ; b ] ψ ( x ) , {displaystyle psi (x^{*})=min _{xin [a;;b]}psi (x),} ψ ( x ) = { g ν ( x ) / L ν ν < M , ( g M ( x ) − g M ∗ ) / L M ν = M . {displaystyle psi (x)={egin{cases}g_{ u }(x)/L_{ u }& u <M,(g_{M}(x)-g_{M}^{*})/L_{M}& u =M.end{cases}}}Здесь M = max { ν ( x ) : x ∈ [ a ; b ] } {displaystyle M=max left{ u (x)colon xin [a;;b] ight}} , а g M ∗ = min { g M ( x ) : x ∈ ⋂ i = 0 M − 1 Q i } {displaystyle g_{M}^{*}=min left{g_{M}(x)colon xin igcap _{i=0}^{M-1}Q_{i} ight}} .
В силу определения числа M {displaystyle M} , задача отыскания g M ∗ {displaystyle g_{M}^{*}} всегда имеет решение, а если M = m + 1 {displaystyle M=m+1} , то g M ∗ = f ( x ∗ ) {displaystyle g_{M}^{*}=f(x^{*})} .
Дуги функции ψ ( x ) {displaystyle psi (x)} липшицевы на множествах ⋂ i = 0 j Q i , 0 ⩽ j ⩽ M − 1 {displaystyle igcap _{i=0}^{j}Q_{i},;0leqslant jleqslant M-1} с константой 1, а сама ψ ( x ) {displaystyle psi (x)} может иметь разрывы первого рода на границах этих множеств.
Несмотря на то, что значения констант Липшица и величина g M ∗ {displaystyle g_{M}^{*}} заранее неизвестны, они могут быть оценены в процессе решения задачи.
Описание метода
Пусть x 0 = a , x 1 = b {displaystyle x^{0}=a,;x^{1}=b} . Индексы концевых точек считаются нулевыми, а значения z {displaystyle z} в них не определены. Первое испытание осуществляется в точке x 3 = ( a + b ) / 2 {displaystyle x^{3}=(a+b)/2} . Выбор точки x k + 1 , k ⩾ 3 {displaystyle x^{k+1},;kgeqslant 3} любого последующего испытания определяется следующими правилами:
Достаточные условия сходимости
Пусть исходная задача оптимизации имеет решение x ∗ {displaystyle x^{*}} и выполняются следующие условия:
Тогда верно следующее:
Модификации метода
Параллельная модификация
Общая схема последовательного метода выглядит следующим образом:
Параллельная модификация заключается в том, что на шаге 3 вместо одного интервала с наилучшей характеристикой выбирать p > 1 {displaystyle p>1} интервалов в порядке убывания характеристик и параллельно проводить в каждом из них испытания.
Схема параллельного алгоритма:
Такая схема распараллеливания целесообразна, если проведение испытания (то есть вычисление функций задачи) — трудоемкий процесс.
Модификация для решения задач c гёльдеровыми функциями
Метод достаточно просто обобщается на случай, когда функции g j ( x ) , j = 1 , m + 1 ¯ {displaystyle g_{j}(x),;j={overline {1,;m+1}}} удовлетворяют условию Гёльдера с показателем 1 / n {displaystyle 1/n} , где n ∈ N {displaystyle nin mathbb {N} } , то есть
| g j ( x + Δ x ) − g j ( x ) | ⩽ H j ( Δ x ) 1 / n , a ⩽ x + Δ x ⩽ b {displaystyle |g_{j}(x+Delta x)-g_{j}(x)|leqslant H_{j}(Delta x)^{1/n},;aleqslant x+Delta xleqslant b} .На шаге 3 значения μ ν {displaystyle mu _{ u }} вычисляются по формуле:
μ ν = max { | g ν ( x i ) − g ν ( x j ) | / ( x i − x j ) 1 / n : i , j ∈ I ν , i > j } . {displaystyle mu _{ u }=max{|g_{ u }(x_{i})-g_{ u }(x_{j})|/(x_{i}-x_{j})^{1/n}colon i,;jin I_{ u },;i>j}.}На шаге 5 Δ i = ( x i − x i − 1 ) 1 / n {displaystyle Delta _{i}=(x_{i}-x_{i-1})^{1/n}} .
На шаге 7 в случае совпадения индексов концевых точек
x k + 1 = 1 2 ( x t + x t − 1 ) − sgn ( z t − z t − 1 ) | z t − z t − 1 | n 2 r ν μ ν n , ν = ν ( x t ) = ν ( x t − 1 ) . {displaystyle x^{k+1}={frac {1}{2}}(x_{t}+x_{t-1})-operatorname {sgn}(z_{t}-z_{t-1}){frac {|z_{t}-z_{t-1}|^{n}}{2r_{ u }mu _{ u }^{n}}},; u = u (x_{t})= u (x_{t-1}).}На шаге 8 критерий остановки принимает вид ( x t − x t − 1 ) 1 / n < ε {displaystyle (x_{t}-x_{t-1})^{1/n}<varepsilon } .
Замечания
- Параметры r ν {displaystyle r_{ u }} отвечают за надежность метода. Чем больше их значения, тем больше итераций метода требуется для достижения заданной точности и тем вероятнее выполнение условия сходимости 4. Если устремить все r ν {displaystyle r_{ u }} к бесконечности, то R ( i ) = Δ i {displaystyle R(i)=Delta _{i}} , то есть метод превращается в перебор по равномерной сетке.
- Использование ненулевого вектора резервов позволяет ускорить сходимость метода, однако при этом необходимо оценить возможность выполнения условия сходимости 3.
- Одномерный метод может быть применен для решения многомерных задач без ограничений. Многомерная задача на множестве S = { ( x 1 , … , x n ) ∈ R n : a i ⩽ x i ⩽ b i , i = 1 , n ¯ } {displaystyle S={(x_{1},;ldots ,;x_{n})in mathbb {R} ^{n}colon a_{i}leqslant x_{i}leqslant b_{i},;i={overline {1,;n}}}} представляется в виде
Для решения задачи min a 1 ⩽ x 1 ⩽ b 1 ϕ ( x 1 ) {displaystyle min _{a_{1}leqslant x_{1}leqslant b_{1}}phi (x_{1})} , где ϕ ( x 1 ) = min a 2 ⩽ x 2 ⩽ b 2 … min a n ⩽ x n ⩽ a n f ( x 1 , … , x n ) {displaystyle phi (x_{1})=min _{a_{2}leqslant x_{2}leqslant b_{2}}ldots min _{a_{n}leqslant x_{n}leqslant a_{n}}f(x_{1},;ldots ,;x_{n})} можно использовать одномерный алгоритм, но, чтобы вычислить значение функции ϕ ( x 1 ) {displaystyle phi (x_{1})} , необходимо решить задачу оптимизации размерности n − 1 {displaystyle n-1} .
Если n = 2 {displaystyle n=2} , то задача min a 2 ⩽ x 2 ⩽ b 2 f ( x 1 , x 2 ) {displaystyle min _{a_{2}leqslant x_{2}leqslant b_{2}}f(x_{1},;x_{2})} решается одномерным методом (значение переменной x 1 {displaystyle x_{1}} при этом зафиксировано), иначе к ней также применяется процедура снижения размерности. Такой способ решения многомерных задач довольно трудоемкий, поэтому на практике применим при n ⩽ 5 {displaystyle nleqslant 5} . Наличие нелинейных функциональных ограничений может привести к потере липшицевости во вспомогательных одномерных задачах.