Sıralı doğrusal karesel programlama - Sequential linear-quadratic programming

Sıralı doğrusal karesel programlama (SLQP) bir yinelemeli yöntem için doğrusal olmayan optimizasyon sorunları nerede amaç fonksiyonu ve kısıtlamalar iki katı sürekli türevlenebilir. Benzer şekilde sıralı ikinci dereceden programlama (SQP), SLQP, bir dizi optimizasyon alt problemini çözerek ilerler. İki yaklaşım arasındaki fark şudur:

SQP'de her alt problem bir ikinci dereceden program kısıtlamaların doğrusallaştırılmasına tabi olan hedefin ikinci dereceden bir modeli ile
SLQP'de her adımda iki alt problem çözülür: a doğrusal program (LP) bir aktif küme, ardından toplam adımı hesaplamak için kullanılan eşitlik kısıtlamalı ikinci dereceden bir program (EQP)

Bu ayrıştırma, SLQP'yi, verimli LP ve EQP çözücülerinin mevcut olduğu büyük ölçekli optimizasyon problemlerine uygun hale getirir, bu problemlerin ölçeklendirilmesi, tam kapsamlı kuadratik programlardan daha kolaydır.

Algoritmanın temelleri

Bir düşünün doğrusal olmayan programlama formun sorunu:

{ displaystyle { begin {array} {rl} min limits _ {x} & f (x) { mbox {st}} & b (x) geq 0 & c (x) = 0. son {dizi}}}

Bu problem için Lagrangian^[1]

{ displaystyle { mathcal {L}} (x, lambda, sigma) = f (x) - lambda ^ {T} b (x) - sigma ^ {T} c (x),}

nerede ${ displaystyle lambda}$ ve ${ displaystyle sigma}$ vardır Lagrange çarpanları.

LP aşaması

SLQP'nin LP aşamasında, aşağıdaki doğrusal program çözülmüştür:

{ displaystyle { begin {array} {rl} min limits _ {d} & f (x_ {k}) + nabla f (x_ {k}) ^ {T} d mathrm {st} & b (x_ {k}) + nabla b (x_ {k}) ^ {T} d geq 0 & c (x_ {k}) + nabla c (x_ {k}) ^ {T} d = 0 . end {dizi}}}

İzin Vermek ${ displaystyle { cal {A}} _ {k}}$ belirtmek aktif küme optimumda ${ displaystyle d _ { text {LP}} ^ {*}}$ bu problemin, yani sıfıra eşit olan kısıtlar kümesinin ${ displaystyle d _ { text {LP}} ^ {*}}$ . Gösteren ${ displaystyle b _ {{ cal {A}} _ {k}}}$ ve ${ displaystyle c _ {{ cal {A}} _ {k}}}$ alt vektörleri ${ displaystyle b}$ ve ${ displaystyle c}$ unsurlarına karşılık gelen ${ displaystyle { cal {A}} _ {k}}$ .

EQP aşaması

SLQP'nin EQP aşamasında, arama yönü ${ displaystyle d_ {k}}$ aşağıdaki ikinci dereceden program çözülerek adımın% 'si elde edilir:

{ displaystyle { begin {array} {rl} min limits _ {d} & f (x_ {k}) + nabla f (x_ {k}) ^ {T} d + { tfrac {1} {2 }} d ^ {T} nabla _ {xx} ^ {2} { mathcal {L}} (x_ {k}, lambda _ {k}, sigma _ {k}) d mathrm { st} & b _ {{ cal {A}} _ {k}} (x_ {k}) + nabla b _ {{ cal {A}} _ {k}} (x_ {k}) ^ {T} d = 0 & c _ {{ cal {A}} _ {k}} (x_ {k}) + nabla c _ {{ cal {A}} _ {k}} (x_ {k}) ^ {T } d = 0. end {dizi}}}

Terimin ${ displaystyle f (x_ {k})}$ Yukarıdaki amaç fonksiyonlarında, sabit olduğu için minimizasyon problemleri için dışarıda bırakılabilir.

Ayrıca bakınız

Notlar

^ Jorge Nocedal ve Stephen J. Wright (2006). Sayısal Optimizasyon. Springer. ISBN 0-387-30303-0.

Referanslar

Jorge Nocedal ve Stephen J. Wright (2006). Sayısal Optimizasyon. Springer. ISBN 0-387-30303-0.

Bu Uygulamalı matematik ile ilgili makale bir Taslak. Wikipedia'ya şu yolla yardım edebilirsiniz: genişletmek.

[1] Jorge Nocedal ve Stephen J. Wright (2006). Sayısal Optimizasyon. Springer. ISBN 0-387-30303-0.

[1]