Введение

Решение задачи оптимизации с квадратичной целевой функцией

Квадратное программирование (QP) — это процесс решения определенных математических задач оптимизации, включающих квадратичные функции. В частности, требуется оптимизировать (минимизировать или максимизировать) многомерную квадратичную функцию при линейных ограничениях на переменные. Квадратное программирование является разновидностью нелинейного программирования. Термин "программирование" в данном контексте обозначает формализованную процедуру решения математических задач. Это употребление восходит к 1940-м годам и не связано с более современным понятием "компьютерного программирования". Чтобы избежать недоразумений, некоторые специалисты предпочитают термин "оптимизация", например, "квадратичная оптимизация".

Обобщения

При минимизации функции f в окрестности некоторой опорной точки x0, Q устанавливается равной её гессиану H(f(x0)), а c – её градиенту ∇f(x0). Связанная задача программирования, квадратичное программирование с квадратичными ограничениями, может быть сформулирована путем добавления квадратичных ограничений на переменные.

Выпуклые квадратные программирование

Для положительно определенного Q, когда задача выпуклая, эллипсоидный метод решает задачу за (слабо) полиномиальное время. Ye и Tse представляют алгоритм, работающий за полиномиальное время, который расширяет алгоритм Кармаркара с линейного программирования на выпуклое квадратичное программирование. На системе с n переменными и L входными битами их алгоритм требует O(L n) итераций, каждая из которых может быть выполнена с использованием O(L n³) арифметических операций, что дает общую сложность по времени O(L² n⁴). Kapoor и Vaidya представляют другой алгоритм, требующий O(L * log L * n³.⁶⁷ * 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 Нелинейный решатель, адаптированный для работы с электронными таблицами, где вычисление функций основано на пересчете ячеек. Базовая версия доступна как стандартное дополнение для Excel.
GAMS Система моделирования высокого уровня для математической оптимизации.
GNU Octave Бесплатный (лицензия GPLv3) язык программирования общего назначения, ориентированный на матричные операции, для численных вычислений, аналогичный MATLAB. Квадратичное программирование в GNU Octave доступно через команду qp.
HiGHS Открытое программное обеспечение для решения задач линейного программирования (LP), смешанного целочисленного программирования (MIP) и выпуклого квадратичного программирования (QP).
IMSL Набор математических и статистических функций, которые программисты могут встраивать в свои программные приложения.
IPOPT IPOPT (Interior Point OPTimizer) – программный пакет для крупномасштабной нелинейной оптимизации.
Julia Язык программирования высокого уровня с заметным пакетом для решения задач JuMP.
Maple Язык программирования общего назначения для математики. Решение квадратичной задачи в Maple выполняется с помощью команды QPSolve.
MATLAB Язык программирования общего назначения, ориентированный на матричные операции, для численных вычислений. Для квадратичного программирования в MATLAB требуется Optimization Toolbox в дополнение к базовому продукту MATLAB.
Mathematica Язык программирования общего назначения для математики, включающий символьные и численные возможности.
MOSEK Решатель для оптимизации больших масштабов с API для нескольких языков (C++, Java, .Net, Matlab и Python).
NAG Numerical Library – коллекция математических и статистических процедур, разработанная Numerical Algorithms Group для различных языков программирования (C, C++, Fortran, Visual Basic, Java и C#) и пакетов (MATLAB, Excel, R, LabVIEW). Раздел оптимизации NAG Library включает процедуры для задач квадратичного программирования с разреженными и плотными линейными матрицами ограничений, а также процедуры для оптимизации линейных, нелинейных, сумм квадратов линейных или нелинейных функций с нелинейными, ограниченными или без ограничений. NAG Library содержит процедуры как для локальной, так и для глобальной оптимизации, а также для непрерывных и целочисленных задач.
Python Язык программирования высокого уровня с привязками к большинству доступных решателей. Квадратичное программирование доступно через функцию solve qp или путем непосредственного вызова конкретного решателя.
R (Fortran) Универсальная кроссплатформенная статистическая вычислительная среда с лицензией GPL.
SAS/OR Пакет решателей для линейной, целочисленной, нелинейной, оптимизации без производных, сетевой, комбинаторной и оптимизации с ограничениями; алгебраический язык моделирования OPTMODEL; и множество специализированных решений, ориентированных на конкретные проблемы/рынки, полностью интегрированных с системой SAS.
SuanShu Пакет алгоритмов оптимизации с открытым исходным кодом для решения LP, QP, SOCP, SDP, SQP на Java.
TK Solver Система математического моделирования и решения задач, основанная на декларативном языке, основанном на правилах, коммерциализированная Universal Technical Systems, Inc.
TOMLAB Поддерживает глобальную оптимизацию, целочисленное программирование, все типы задач наименьших квадратов, линейное, квадратичное и нелинейное программирование без ограничений для MATLAB. TOMLAB поддерживает решатели, такие как CPLEX, SNOPT и KNITRO.
XPRESS Решатель для крупномасштабных линейных программ, квадратичных программ, общих нелинейных и смешанных целочисленных программ. Имеет API для нескольких языков программирования, а также язык моделирования Mosel и работает с AMPL, GAMS. Бесплатен для академического использования.

Расширения

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