Послідовне квадратичне програмування ( SQP ) - це ітеративний метод обмеженої нелінійної оптимізації. Методи SQP використовуються для математичних задач, для яких цільова функція та обмеження двічі безперервно диференціюються.
Методи SQP вирішують послідовність підпроблем оптимізації, кожна з яких оптимізує квадратичну модель об'єкта, що підлягає лінеаризації обмежень. Якщо проблема не обмежена, то метод зводиться до методу Ньютона для пошуку точки, де градієнт об'єкта зникає. Якщо проблема має лише обмеження рівності, то метод еквівалентний застосуванню методу Ньютона до умов оптимальності першого порядку або умов Каруша — Куна — Таккера.
Основи алгоритму
Розглянемо нелінійну задачу програмування даної форми:
Лагранжан для цієї проблеми є
де і є множниками Лагранжа. На ітерації , основний алгоритм послідовного квадратичного програмування визначає відповідний напрямок пошуку як рішення підпрограми квадратичного програмування
Зауважимо, що функція у рівнянні вище може бути залишена для проблеми мінімізації, оскільки вона є постійною.
Альтернативні підходи
- Послідовне лінійне програмування
- Послідовне лінійно-квадратичне програмування
- Доповнений метод Лагрангія
Впровадження
Методами SQP були реалізовані такі добре відомі числові середовища, як MATLAB і GNU Octave. Існують також численні бібліотеки програмного забезпечення, в тому числі з відкритим кодом
- SciPy (фактично стандарт для наукового Python) має розв'язувач scipy.optimize.minimize (метод = 'SLSQP').
- NLopt [ 19 грудня 2017 у Wayback Machine.] (реалізація C / C ++, з численними інтерфейсами, включаючи Python, R, MATLAB / Octave), реалізований Dieter Kraft як частина пакету для оптимального управління та модифікований SG Johnson.
- LabVIEW
- KNITRO (C, C ++, C #, Java, Python, Fortran)
- NPSOL (Фортран)
- SNOPT (Фортран)
- NLPQL (Fortran)
- MATLAB
SuanShu [ 24 грудня 2019 у Wayback Machine.] (Java)
Див. також
Примітки
- Jorge Nocedal and Stephen J. Wright (2006). . Springer. ISBN . Архів оригіналу за 30 травня 2008. Процитовано 24 грудня 2019.
- Kraft, Dieter (Sep 1994). . Transactions on Mathematical Software. 20 (3): 262—281. CiteSeerX 10.1.1.512.2567. doi:10.1145/192115.192124. Архів оригіналу за 6 травня 2021. Процитовано 1 лютого 2019.
- Kraft, Dieter (July 1988). . Oberpfaffenhofen: Institut für Dynamik der Flugsysteme. Архів оригіналу за 25 березня 2019. Процитовано 1 лютого 2019.
- . Архів оригіналу за 3 січня 2018. Процитовано 24 грудня 2019.
Література
- Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). . Universitext (вид. Second revised ed. of translation of 1997 French). Berlin: Springer-Verlag. с. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN . MR 2265882. Архів оригіналу за 19 липня 2013. Процитовано 24 грудня 2019.
- Jorge Nocedal and Stephen J. Wright (2006). . Springer. ISBN . Архів оригіналу за 30 травня 2008. Процитовано 24 грудня 2019.
Посилання
- Послідовне квадратичне програмування в путівнику NEOS [ 24 грудня 2019 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Poslidovne kvadratichne programuvannya SQP ce iterativnij metod obmezhenoyi nelinijnoyi optimizaciyi Metodi SQP vikoristovuyutsya dlya matematichnih zadach dlya yakih cilova funkciya ta obmezhennya dvichi bezperervno diferenciyuyutsya Metodi SQP virishuyut poslidovnist pidproblem optimizaciyi kozhna z yakih optimizuye kvadratichnu model ob yekta sho pidlyagaye linearizaciyi obmezhen Yaksho problema ne obmezhena to metod zvoditsya do metodu Nyutona dlya poshuku tochki de gradiyent ob yekta znikaye Yaksho problema maye lishe obmezhennya rivnosti to metod ekvivalentnij zastosuvannyu metodu Nyutona do umov optimalnosti pershogo poryadku abo umov Karusha Kuna Takkera Osnovi algoritmuRozglyanemo nelinijnu zadachu programuvannya danoyi formi minxf x s t b x 0c x 0 displaystyle begin array rl min limits x amp f x mbox s t amp b x geq 0 amp c x 0 end array Lagranzhan dlya ciyeyi problemi ye L x l s f x lT b x yi 2 sTc x displaystyle mathcal L x lambda sigma f x lambda T b x y i 2 sigma T c x de l displaystyle lambda i s displaystyle sigma ye mnozhnikami Lagranzha Na iteraciyi xk displaystyle x k osnovnij algoritm poslidovnogo kvadratichnogo programuvannya viznachaye vidpovidnij napryamok poshuku dk displaystyle d k yak rishennya pidprogrami kvadratichnogo programuvannya mindf xk f xk Td 12dT xx2L xk lk sk ds t b xk b xk Td 0c xk c xk Td 0 displaystyle begin array rl min limits d amp 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 s t amp b x k nabla b x k T d geq 0 amp c x k nabla c x k T d 0 end array Zauvazhimo sho funkciya f xk displaystyle f x k u rivnyanni vishe mozhe buti zalishena dlya problemi minimizaciyi oskilki vona ye postijnoyu Alternativni pidhodiPoslidovne linijne programuvannya Poslidovne linijno kvadratichne programuvannya Dopovnenij metod LagrangiyaVprovadzhennyaMetodami SQP buli realizovani taki dobre vidomi chislovi seredovisha yak MATLAB i GNU Octave Isnuyut takozh chislenni biblioteki programnogo zabezpechennya v tomu chisli z vidkritim kodom SciPy faktichno standart dlya naukovogo Python maye rozv yazuvach scipy optimize minimize metod SLSQP NLopt 19 grudnya 2017 u Wayback Machine realizaciya C C z chislennimi interfejsami vklyuchayuchi Python R MATLAB Octave realizovanij Dieter Kraft yak chastina paketu dlya optimalnogo upravlinnya ta modifikovanij SG Johnson LabVIEW KNITRO C C C Java Python Fortran NPSOL Fortran SNOPT Fortran NLPQL Fortran MATLAB SuanShu 24 grudnya 2019 u Wayback Machine Java Div takozh fr Metod Nyutona Sekretnij metodPrimitkiJorge Nocedal and Stephen J Wright 2006 Springer ISBN 978 0 387 30303 1 Arhiv originalu za 30 travnya 2008 Procitovano 24 grudnya 2019 Kraft Dieter Sep 1994 Transactions on Mathematical Software 20 3 262 281 CiteSeerX 10 1 1 512 2567 doi 10 1145 192115 192124 Arhiv originalu za 6 travnya 2021 Procitovano 1 lyutogo 2019 Kraft Dieter July 1988 Oberpfaffenhofen Institut fur Dynamik der Flugsysteme Arhiv originalu za 25 bereznya 2019 Procitovano 1 lyutogo 2019 Arhiv originalu za 3 sichnya 2018 Procitovano 24 grudnya 2019 LiteraturaBonnans J Frederic Gilbert J Charles Lemarechal Claude Sagastizabal Claudia A 2006 Universitext vid Second revised ed of translation of 1997 French Berlin Springer Verlag s xiv 490 doi 10 1007 978 3 540 35447 5 ISBN 978 3 540 35445 1 MR 2265882 Arhiv originalu za 19 lipnya 2013 Procitovano 24 grudnya 2019 Jorge Nocedal and Stephen J Wright 2006 Springer ISBN 978 0 387 30303 1 Arhiv originalu za 30 travnya 2008 Procitovano 24 grudnya 2019 PosilannyaPoslidovne kvadratichne programuvannya v putivniku NEOS 24 grudnya 2019 u Wayback Machine