Главная
Новости
Строительство
Ремонт
Дизайн и интерьер
Ландшафтный дизайн
Все про мебель
Сантехника

















Яндекс.Метрика





Метод Стронгина

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

Постановка задачи оптимизации

Требуется найти точку 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 0 , … , x k {displaystyle x^{0},;ldots ,;x^{k}} k {displaystyle k} предшествующих испытаний нижними индексами в порядке увеличения значений координаты: a = x 0 < … < x i < … < x k = b {displaystyle a=x_{0}<ldots <x_{i}<ldots <x_{k}=b} и сопоставить им значения z i = g ν ( x i ) , ν = ν ( x i ) , i = 1 , k ¯ {displaystyle z_{i}=g_{ u }(x_{i}),; u = u (x_{i}),;i={overline {1,;k}}} .
  • Для каждого целого числа ν , 1 ⩽ ν ⩽ m + 1 {displaystyle u ,;1leqslant u leqslant m+1} определить соответствующее ему множество I ν {displaystyle I_{ u }} нижних индексов точек, в которых вычислялись значения функций g ν ( x ) {displaystyle g_{ u }(x)} : I ν = { i : ν ( x i ) = ν , 1 ⩽ i ⩽ k } , 1 ⩽ ν ⩽ m + 1. {displaystyle I_{ u }={icolon u (x_{i})= u ,;1leqslant ileqslant k},;1leqslant u leqslant m+1.} Также определить максимальное значение индекса M = max { ν ( x i ) , 1 ⩽ i ⩽ k } . {displaystyle M=max{ u (x_{i}),;1leqslant ileqslant k}.}
  • Вычислить текущие оценки для неизвестных констант Липшица: μ ν = max { | g ν ( x i ) − g ν ( x j ) | / ( x i − x j ) : i , j ∈ I ν , i > j } . {displaystyle mu _{ u }=max{|g_{ u }(x_{i})-g_{ u }(x_{j})|/(x_{i}-x_{j})colon i,;jin I_{ u },;i>j}.} Если множество I ν {displaystyle I_{ u }} содержит менее двух элементов или если значение μ ν {displaystyle mu _{ u }} оказывается равным нулю, то принять μ ν = 1 {displaystyle mu _{ u }=1} .
  • Для всех непустых множеств I ν , ν = 1 , M ¯ {displaystyle I_{ u },; u ={overline {1,;M}}} вычислить оценки z ν ∗ = { min { g ν ( x i ) : x i ∈ I ν } ν = M , − ε ν ν < M , {displaystyle z_{ u }^{*}={egin{cases}min{g_{ u }(x_{i})colon x_{i}in I_{ u }}& u =M,-varepsilon _{ u }& u <M,end{cases}}} где вектор с неотрицательными координатами ε R = ( ε 1 , … , ε m ) {displaystyle varepsilon _{R}=(varepsilon _{1},;ldots ,;varepsilon _{m})} называется вектором резервов.
  • Для каждого интервала ( x i − 1 ; x i ) , 1 ⩽ i ⩽ k {displaystyle (x_{i-1};;x_{i}),;1leqslant ileqslant k} вычислить характеристику R ( i ) = { Δ i + ( z i − z i − 1 ) 2 ( r ν μ ν ) 2 Δ i − 2 z i + z i − 1 − 2 z ν ∗ r ν μ ν ν = ν ( x i ) = ν ( x i − 1 ) , 2 Δ i − 4 z i − 1 − z ν ∗ r ν μ ν ν = ν ( x i − 1 ) > ν ( x i ) , 2 Δ i − 4 z i − z ν ∗ r ν μ ν ν = ν ( x i ) > ν ( x i − 1 ) , {displaystyle R(i)={egin{cases}Delta _{i}+{frac {(z_{i}-z_{i-1})^{2}}{(r_{ u }mu _{ u })^{2}Delta _{i}}}-2{frac {z_{i}+z_{i-1}-2z_{ u }^{*}}{r_{ u }mu _{ u }}}& u = u (x_{i})= u (x_{i-1}),2Delta _{i}-4{frac {z_{i-1}-z_{ u }^{*}}{r_{ u }mu _{ u }}}& u = u (x_{i-1})> u (x_{i}),2Delta _{i}-4{frac {z_{i}-z_{ u }^{*}}{r_{ u }mu _{ u }}}& u = u (x_{i})> u (x_{i-1}),end{cases}}} где Δ i = x i − x i − 1 {displaystyle Delta _{i}=x_{i}-x_{i-1}} . Величины r ν > 1 , ν = 1 , m ¯ {displaystyle r_{ u }>1,; u ={overline {1,;m}}} являются параметрами алгоритма. От них зависят произведения r ν μ ν {displaystyle r_{ u }mu _{ u }} , используемые при вычислении характеристик в качестве оценок неизвестных констант Липшица.
  • Определить интервал ( x t − 1 ; x t ) {displaystyle (x_{t-1};;x_{t})} , которому соответствует максимальная характеристика R ( t ) = max { R ( i ) , 1 ⩽ i ⩽ k } {displaystyle R(t)=max{R(i),;1leqslant ileqslant k}} .
  • Провести очередное испытание в середине интервала ( x t − 1 ; x t ) {displaystyle (x_{t-1};;x_{t})} , если индексы его концевых точек не совпадают: x k + 1 = 1 2 ( x t + x t − 1 ) . {displaystyle x^{k+1}={frac {1}{2}}(x_{t}+x_{t-1}).} В противном случае провести испытание в точке x k + 1 = 1 2 ( x t + x t − 1 ) − z t − z t − 1 2 r ν μ ν , ν = ν ( x t ) = ν ( x t − 1 ) , {displaystyle x^{k+1}={frac {1}{2}}(x_{t}+x_{t-1})-{frac {z_{t}-z_{t-1}}{2r_{ u }mu _{ u }}},; u = u (x_{t})= u (x_{t-1}),} увеличить k {displaystyle k} на 1.
  • Если x t − x t − 1 < ε {displaystyle x_{t}-x_{t-1}<varepsilon } ( ε > 0 {displaystyle varepsilon >0} — заданная точность метода), то прекратить выполнение алгоритма, иначе перейти на шаг 1.
  • Достаточные условия сходимости

    Пусть исходная задача оптимизации имеет решение x ∗ {displaystyle x^{*}} и выполняются следующие условия:

  • каждая область Q j , j = 1 , m ¯ {displaystyle Q_{j},;j={overline {1,;m}}} представляет собой объединение конечного числа отрезков, имеющих положительную длину;
  • каждая функция g j ( x ) , j = 1 , m + 1 ¯ {displaystyle g_{j}(x),;j={overline {1,;m+1}}} удовлетворяет условию Липшица с соответствующей константой L j {displaystyle L_{j}} ;
  • компоненты вектора резервов удовлетворяют неравенствам 0 ⩽ 2 ε ν < L ν ( β − α ) {displaystyle 0leqslant 2varepsilon _{ u }<L_{ u }(eta -alpha )} , где β − α {displaystyle eta -alpha } — длина отрезка [ α ; β ] {displaystyle [alpha ;;eta ]} , лежащего в допустимой области Q {displaystyle Q} и содержащего точку x ∗ {displaystyle x^{*}} ;
  • начиная с некоторого значения k {displaystyle k} величины μ ν {displaystyle mu _{ u }} , соответствующие непустым множествам I ν {displaystyle I_{ u }} , удовлетворяют неравенствам r ν μ ν > 2 L ν {displaystyle r_{ u }mu _{ u }>2L_{ u }} .
  • Тогда верно следующее:

  • точка x ∗ {displaystyle x^{*}} является предельной точкой последовательности { x k } {displaystyle {x^{k}}} , порождаемой методом при ε = 0 {displaystyle varepsilon =0} в условии остановки;
  • любая предельная точка x 0 {displaystyle x^{0}} последовательности { x k } {displaystyle {x^{k}}} является решением исходной задачи оптимизации;
  • сходимость к предельной точке x 0 {displaystyle x^{0}} является двухсторонней, если x 0 ≠ a , x 0 ≠ b {displaystyle x^{0} eq a,;x^{0} eq b} .
  • Модификации метода

    Параллельная модификация

    Общая схема последовательного метода выглядит следующим образом:

  • Упорядочить точки предшествующих испытаний в порядке возрастания их координат: a = x 0 < … < x i < … < x k = b {displaystyle a=x_{0}<ldots <x_{i}<ldots <x_{k}=b} .
  • Вычислить для каждого интервала ( x i − 1 ; x i ) , 1 ⩽ i ⩽ k {displaystyle (x_{i-1};;x_{i}),;1leqslant ileqslant k} характеристику R ( i ) {displaystyle R(i)} .
  • Определить интервал ( x t − 1 ; x t ) {displaystyle (x_{t-1};;x_{t})} , которому соответствует максимальная характеристика R ( t ) = max { R ( i ) , 1 ⩽ i ⩽ k } {displaystyle R(t)=max{R(i),;1leqslant ileqslant k}} .
  • Провести следующее испытание в точке x k + 1 = d ( t ) ∈ ( x t − 1 ; x t ) {displaystyle x^{k+1}=d(t)in (x_{t-1};;x_{t})} , где d ( t ) {displaystyle d(t)} — правило размещения точки следующего испытания в интервале с номером t {displaystyle t} .
  • Проверить выполнение критерия остановки x t − x t − 1 < ε {displaystyle x_{t}-x_{t-1}<varepsilon } .
  • Параллельная модификация заключается в том, что на шаге 3 вместо одного интервала с наилучшей характеристикой выбирать p > 1 {displaystyle p>1} интервалов в порядке убывания характеристик и параллельно проводить в каждом из них испытания.

    Схема параллельного алгоритма:

  • Упорядочить точки предшествующих испытаний в порядке возрастания их координат: a = x 0 < … < x i < … < x k = b {displaystyle a=x_{0}<ldots <x_{i}<ldots <x_{k}=b} .
  • Вычислить для каждого интервала ( x i − 1 ; x i ) , 1 ⩽ i ⩽ k {displaystyle (x_{i-1};;x_{i}),;1leqslant ileqslant k} характеристику R ( i ) {displaystyle R(i)} .
  • Характеристики интервалов упорядочить по убыванию: R ( i 1 ) > … > R ( i k ) {displaystyle R(i_{1})>ldots >R(i_{k})} .
  • Для всех интервалов с номерами i 1 , … , i p {displaystyle i_{1},;ldots ,;i_{p}} провести испытания в точках x k + j = d ( i j ) ∈ ( x i j − 1 ; x i j ) , j = 1 , p ¯ {displaystyle x^{k+j}=d(i_{j})in (x_{i_{j}-1};;x_{i_{j}}),;j={overline {1,;p}}} .
  • Проверить выполнение критерия остановки: ∃ j , 1 ⩽ j ⩽ p : x i j − x i j − 1 < ε {displaystyle exists j,;1leqslant jleqslant pcolon x_{i_{j}}-x_{i_{j}-1}<varepsilon } .
  • Такая схема распараллеливания целесообразна, если проведение испытания (то есть вычисление функций задачи) — трудоемкий процесс.

    Модификация для решения задач 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 ( x 1 , … , x n ) ∈ S f ( x 1 , … , x n ) = min a 1 ⩽ x 1 ⩽ b 1 min a 2 ⩽ x 2 ⩽ b 2 … min a n ⩽ x n ⩽ b n f ( x 1 , … , x n ) . {displaystyle min _{(x_{1},;ldots ,;x_{n})in S}f(x_{1},;ldots ,;x_{n})=min _{a_{1}leqslant x_{1}leqslant b_{1}}min _{a_{2}leqslant x_{2}leqslant b_{2}}ldots min _{a_{n}leqslant x_{n}leqslant b_{n}}f(x_{1},;ldots ,;x_{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} . Наличие нелинейных функциональных ограничений может привести к потере липшицевости во вспомогательных одномерных задачах.