Квадраттық бағдарламалау және оптимизация мәселелері

Кіріспе

Квадраттық мақсатты функциямен оңтайландыру мәселесін шешу

Квадраттық бағдарламалау (QP) – квадраттық функцияларды қамтитын нақты математикалық оңтайландыру мәселелерін шешу процесі. Атап айтқанда, көп айнымалы квадраттық функцияны айнымалыларға назардағы сызықтық шектеулермен оңтайландыруға (минимизациялауға немесе максимизациялауға) ұмтылу қарастырылады. Квадраттық бағдарламалау – сызықтық емес бағдарламалаудың бір түрі. Осы контексте "бағдарламалау" математикалық мәселелерді шешудің формалды процедурасын білдіреді. Бұл терминнің қолданысы 1940-шы жылдарға дейін жетеді және ол "компьютерлік бағдарламалау" деп аталатын қазіргі заманғы түсінікпен тікелей байланысты емес. Сандарды шатастырмау үшін кейбір мамандар "оптимизация" терминін қолдануды ұсынады, мысалы, "квадраттық оптимизация".

Жалпылау

f функциясын x0 нүктесінің маңайында минимумға жеткізу үшін Q оның Гессиан матрицасына 'H'(f('x'0)) тең болып, ал 'c' оның градиентіне ∇f('x'0) тең болады. Анықталған есеп, квадраттық шектеулі квадраттық бағдарламалау, айнымалыларға квадраттық шектеулер қосу арқылы құрастырылуы мүмкін.

Конвекстік квадраттық бағдарламалау

Позитивті нақты Q үшін, мәселе дөңес болғанда, эллипсоидтық әдіс мәселені (әлсіз) полиномиалдық уақытта шешеді. Е және Цэ сызықтық бағдарламалаудан дөңес квадраттық бағдарламалауға дейін Кармаркар алгоритмін кеңейтетін көпмүшелік уақыт алгоритмін ұсынады. n айнымалысы және L кіріс биті бар жүйеде олардың алгоритмі O(L n) итерацияны қажет етеді, олардың әрқайсысы O(L n3) арифметикалық операцияларды қолдану арқылы орындалуы мүмкін, бұл жалпы орындалу уақытының күрделілігі O(L2 n4) болады. Капур және Вайдия O(L * log L * n3.67 * log n) арифметикалық операцияларды қажет ететін тағы бір алгоритм ұсынады.

Квадраттық емес конвекстік бағдарламалау

Егер Q анықталмаған болса (яғни мәселе дөңес емес), онда мәселе NP қиын. Мұны көрудің қарапайым жолы – дөңес емес квадраттық шектеуді қарастыру: xi² = xi. Бұл шектеу xi-дің {0,1} жиынында болуын талап етуге тең, яғни xi – екілік бүтін сан айнымалысы. Сондықтан, мұндай шектеулер екілік айнымалылары бар кез келген бүтін сандық бағдарламаны модельдеу үшін қолданылуы мүмкін, ал ол NP қиын екені белгілі. Сонымен қатар, мұндай дөңес емес проблемаларда бірнеше стационарлық нүктелер мен жергілікті минимумдар болуы мүмкін. Шындығында, егер Q тек бір теріс өзіндік мәнге ие болса да, мәселе (күшті) NP қиын болады. Сонымен қатар, дөңес емес квадраттық бағдарламаның ККТ нүктесін табу CLS қиын.

Аралас бүтін сандық квадраттық бағдарламалау

Кейбір жағдайларда вектордың "x" бір немесе бірнеше элементтері бүтін сан мәнін қабылдауы қажет болады. Бұл аралас бүтін санды квадраттық бағдарламалау (MIQP) мәселесін тудырады. MIQP-ның қолданылу аясы су ресурстарын басқару және индекстік қорларды құру сияқты салаларды қамтиды.

Скрипттік (бағдарламалау) тілдер мен шешімдерді шығарушылар

AIMMS Оптимизациялау және жоспарлау типті мәселелерді модельдеу және шешуге арналған бағдарламалық жүйе. ALGLIB Екі лицензиялы (GPL/меншік) сандық кітапхана (C++, NET). AMPL Үлкен көлемді математикалық оптимизация үшін танымал модельдеу тілі. APMonitor LP, QP, NLP, MILP, MINLP және DAE жүйелері үшін MATLAB және Python-да модельдеу және оптимизациялау жиынтығы. Artelys Knitro Сызықтық емес оптимизацияның интегралды пакеті. CGAL Квадраттық бағдарламалауды шешуге мүмкіндік беретін ашық бастапқы кодты есептеу геометриясы пакеті. CPLEX API (C, C++, Java, Net, Python, Matlab және R) бар танымал шешуші. Академиялық мақсатта тегін. Excel Solver Function Функцияларды бағалау қайта есептеу ұяшықтарына негізделген электрондық кестелерге бейімделген сызықтық емес шешуші. Бастапқы нұсқасы Excel-ге стандартты қосымша ретінде қолжетімді. GAMS Математикалық оптимизация үшін жоғары деңгейдегі модельдеу жүйесі. GNU Octave Тегін (лицензиясы GPLv3) жалпы мақсаттағы және MATLAB-қа ұқсас сандық есептеулерге бағдарланған матрицалық бағдарламалау тілі. GNU Octave-дегі квадраттық бағдарламалау оның qp командасы арқылы қолжетімді. HiGHS Линейлік бағдарламалауды (LP), аралас бүтін сандық бағдарламалауды (MIP) және дөңгелек квадраттық бағдарламалауды (QP) шешуге арналған ашық бастапқы кодты бағдарламалық қамтамасыз ету. IMSL Бағдарламалаушылар өздерінің бағдарламалық қосымшаларына енгізе алатын математикалық және статистикалық функциялар жиынтығы. IPOPT IPOPT (Interior Point OPTimizer) – ірі көлемді сызықтық емес оптимизацияға арналған бағдарламалық жасақтама. Julia Математикаға арналған жоғары деңгейдегі бағдарламалау тілі, сонымен қатар JuMP бағдарламалау пакеті бар. Maple Жоғары деңгейдегі бағдарламалау тілі, QPSolve командасы арқылы квадраттық мәселені шешуге мүмкіндік береді. MATLAB Сандық есептеулер үшін жалпы мақсаттағы және матрицаға бағдарланған бағдарламалау тілі. MATLAB-тағы квадратикалық бағдарламалау үшін негізгі MATLAB өнімінен басқа Optimization Toolbox қажет. Mathematica Символикалық және сандық мүмкіндіктері бар математикаға арналған жоғары деңгейдегі бағдарламалау тілі. MOSEK Бірнеше тілдерге арналған (C++, Java, Net, Matlab және Python) API-мен кең ауқымды оптимизация үшін шешуші. NAG Сандық кітапханасы – Сандық алгоритмдер тобының бірнеше бағдарламалау тілдері (C, C++, Fortran, Visual Basic, Java және C#) және пакеттер (MATLAB, Excel, R, LabVIEW) үшін әзірлеген математикалық және статистикалық процедуралар жинағы. NAG кітапханасының Оптимизация бөлімінде сызықтық және сызықтық емес шектеуіш матрицалары бар квадраттық бағдарламалау мәселелері үшін, сызықтық, сызықтық емес, сызықтық немесе сызықтық емес функциялардың квадраттарының қосындыларын сызықтық емес, шектелген немесе шектеусіз оптимизациялау үшін процедуралар бар. NAG кітапханасында жергілікті және жаһандық оптимизация үшін, сондай-ақ үздіксіз немесе бүтін сандық мәселелер үшін процедуралар бар. Python Жоғары деңгейдегі бағдарламалау тілі, көптеген қолжетімді шешушілерге байланыстар бар. Квадраттық бағдарламалау solve qp функциясы арқылы немесе нақты шешушіге тікелей шалу арқылы қолжетімді. R (Fortran) GPL лицензиясы бар, платформааралық статистикалық есептеудің универсалды жүйесі. SAS/OR Сызықтық, бүтін сандық, сызықтық емес, туындысыз, желілік, комбинаторлық және шектеулерді оптимизациялауға арналған шешушілер жиынтығы; OPTMODEL алгебралық модельдеу тілі; және SAS жүйесімен толықтай біріктірілген, белгілі бір проблемаларға/нарықтарға бағытталған әртүрлі тік шешімдер. SuanShu – Java-да LP, QP, SOCP, SDP, SQP-ді шешуге арналған оптимизация алгоритмдерінің ашық кодты жиынтығы. TK Solver Декларативті, ережеге негізделген тілге негізделген математикалық модельдеу және мәселелерді шешуге арналған бағдарламалық жүйе, Universal Technical Systems, Inc. компаниясымен коммерцияландырылған. TOMLAB CPLEX, SNOPT және KNITRO сияқты шешушілерді қолдайды, MATLAB үшін жаһандық оптимизация, бүтін сандық бағдарламалау, барлық типтегі ең кіші квадраттар, сызықтық, квадраттық және шектеусіз бағдарламалауды қолдайды. XPRESS Ірі масштабтағы сызықтық бағдарламаларды, квадраттық бағдарламаларды, жалпы сызықтық емес және аралас бүтін сандық бағдарламаларды шешуші. Бірнеше бағдарламалау тілдеріне арналған API бар, сонымен қатар Mosel модельдеу тілі бар және AMPL, GAMS-пен жұмыс істейді. Академиялық мақсатта тегін.

NameBrief infoAIMMS A software system for modeling and solving optimization and scheduling type problemsALGLIB Dual licensed (GPL/proprietary) numerical library (C++, NET). AMPL A popular modeling language for large scale mathematical optimization. APMonitor Modeling and optimization suite for LP, QP, NLP, MILP, MINLP, and DAE systems in MATLAB and Python. Artelys Knitro An Integrated Package for Nonlinear OptimizationCGAL An open source computational geometry package which includes a quadratic programming solver. CPLEX Popular solver with an API (C, C++, Java, Net, Python, Matlab and R). Free for academics. Excel Solver Function A nonlinear solver adjusted to spreadsheets in which function evaluations are based on the recalculating cells. Basic version available as a standard add on for Excel. GAMS A high level modeling system for mathematical optimizationGNU Octave A free (its licence is GPLv3) general purpose and matrix oriented programming language for numerical computing, similar to MATLAB. Quadratic programming in GNU Octave is available via its qp commandHiGHS Open source software for solving linear programming (LP), mixed integer programming (MIP), and convex quadratic programming (QP) modelsIMSL A set of mathematical and statistical functions that programmers can embed into their software applications. IPOPT IPOPT (Interior Point OPTimizer) is a software package for large scale nonlinear optimization. JuliaA high level programming language with notable solving package being JuMPMaple General purpose programming language for mathematics. Solving a quadratic problem in Maple is accomplished via its QPSolve command. MATLAB A general purpose and matrix oriented programming language for numerical computing. Quadratic programming in MATLAB requires the Optimization Toolbox in addition to the base MATLAB productMathematica A general purpose programming language for mathematics, including symbolic and numerical capabilities. MOSEK A solver for large scale optimization with API for several languages (C++, Java, Net, Matlab and Python). NAG Numerical Library A collection of mathematical and statistical routines developed by the Numerical Algorithms Group for multiple programming languages (C, C++, Fortran, Visual Basic, Java and C#) and packages (MATLAB, Excel, R, LabVIEW). The Optimization chapter of the NAG Library includes routines for quadratic programming problems with both sparse and non sparse linear constraint matrices, together with routines for the optimization of linear, nonlinear, sums of squares of linear or nonlinear functions with nonlinear, bounded or no constraints. The NAG Library has routines for both local and global optimization, and for continuous or integer problems. PythonHigh level programming language with bindings for most available solvers. Quadratic programming is available via the solve qp function or by calling a specific solver directly. R (Fortran)GPL licensed universal cross platform statistical computation framework. SAS/OR A suite of solvers for Linear, Integer, Nonlinear, Derivative Free, Network, Combinatorial and Constraint Optimization; the Algebraic modeling language OPTMODEL; and a variety of vertical solutions aimed at specific problems/markets, all of which are fully integrated with the SAS System. SuanShu an open source suite of optimization algorithms to solve LP, QP, SOCP, SDP, SQP in JavaTK Solver Mathematical modeling and problem solving software system based on a declarative, rule based language, commercialized by Universal Technical Systems, Inc TOMLABSupports global optimization, integer programming, all types of least squares, linear, quadratic and unconstrained programming for MATLAB. TOMLAB supports solvers like CPLEX, SNOPT and KNITRO. XPRESSSolver for large scale linear programs, quadratic programs, general nonlinear and mixed integer programs. Has API for several programming languages, also has a modelling language Mosel and works with AMPL, GAMS. Free for academic use.

Ұзартулар

Полиномиялық оңтайландыру – бұл одан да жалпы жағдай, онда шектеулер кез келген дәрежедегі полиномиялық функциялар түрінде болуы мүмкін, емес 2-ге ғана.