Sıralı ikinci dereceden programlama - Sequential quadratic programming

Bu makale konuya aşina olmayanlar için yetersiz bağlam sağlar. Lütfen yardım et makaleyi geliştirmek tarafından okuyucu için daha fazla bağlam sağlamak. (Ekim 2009) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Sıralı ikinci dereceden programlama (SQP) bir yinelemeli yöntem için kısıtlı doğrusal olmayan optimizasyon. SQP yöntemleri matematiksel hangi sorunlar için amaç fonksiyonu ve kısıtlamalar iki kez sürekli türevlenebilir.

SQP yöntemleri, her biri kısıtlamaların doğrusallaştırılmasına tabi olan hedefin ikinci dereceden bir modelini optimize eden bir dizi optimizasyon alt problemini çözer. Sorun sınırlandırılmamışsa, yöntem Newton yöntemi hedefin eğiminin kaybolduğu bir noktayı bulmak için. Problemin yalnızca eşitlik kısıtlamaları varsa, yöntem uygulamaya eşdeğerdir Newton yöntemi birinci dereceden optimallik koşullarına veya Karush – Kuhn – Tucker koşulları, problemin.

Algoritmanın temelleri

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

${displaystyle {egin {dizi} {rl} min limitleri _ {x} & f (x) {mbox {s.t.}} & b (x) geq 0 & c (x) = 0.end {dizi}}}$

Lagrange bu problem için^[1]

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

nerede ${displaystyle lambda}$ ve ${displaystyle sigma}$ vardır Lagrange çarpanları. Bir yinelemede ${displaystyle x_ {k}}$temel bir sıralı ikinci dereceden programlama algoritması, uygun bir arama yönünü tanımlar ${displaystyle d_ {k}}$ bir çözüm olarak ikinci dereceden programlama alt problem

${displaystyle {egin {dizi} {rl} min limitleri _ {d} & f (x_ {k}) + abla f (x_ {k}) ^ {T} d + {frac {1} {2}} d ^ {T } abla _ {xx} ^ {2} {mathcal {L}} (x_ {k}, lambda _ {k}, sigma _ {k}) d mathrm {st} & b (x_ {k}) + abla b (x_ {k}) ^ {T} dgeq 0 & c (x_ {k}) + abla c (x_ {k}) ^ {T} d = 0.son {dizi}}}$

Terimin ${displaystyle f (x_ {k})}$ Yukarıdaki ifadede, aşağıdaki ifadenin altında sabit olduğu için minimizasyon problemi için dışarıda bırakılabilir. ${görüntü stili minimum sınırları _ {d}}$ Şebeke.

Alternatif yaklaşımlar

• Sıralı doğrusal programlama
• Sıralı doğrusal karesel programlama
• Artırılmış Lagrangian yöntemi

Uygulamalar

SQP yöntemleri, aşağıdakiler gibi iyi bilinen sayısal ortamlarda uygulanmıştır: MATLAB ve GNU Oktav. Açık kaynak dahil olmak üzere çok sayıda yazılım kitaplığı da vardır:

• SciPy (bilimsel Python için fiili standart) scipy.optimize.minimize (method = ’SLSQP’) çözücüsüne sahiptir.
• NLopt (Julia, Python, R, MATLAB / Octave dahil olmak üzere çeşitli arayüzlerle C / C ++ uygulaması), Dieter Kraft tarafından optimum kontrol için bir paketin parçası olarak uygulanan ve S.G. Johnson tarafından değiştirilen.^[2][3]
• LabVIEW
• KNITRO^[4] (C, C ++, C #, Java, Python, Fortran)
• NPSOL (Fortran)
• SNOPT (Fortran)
• NLPQL (Fortran)
• MATLAB
• SuanShu (Java)

Ayrıca bakınız

• Josephy-Newton algoritması
• Newton yöntemi
• Sekant yöntemi

Notlar

Referanslar

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Sayısal optimizasyon: Teorik ve pratik yönler. Universitext (1997 Fransızca baskısının ikinci gözden geçirilmiş baskısı). Berlin: Springer-Verlag. s. xiv + 490. doi:10.1007/978-3-540-35447-5. ISBN  978-3-540-35445-1. BAY  2265882.
• Jorge Nocedal ve Stephen J. Wright (2006). Sayısal Optimizasyon. Springer. ISBN  978-0-387-30303-1.

Dış bağlantılar

• NEOS rehberinde Sıralı Kuadratik Programlama

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