Квадратичное программирование

• Определение и применение

  • Квадратичное программирование — это процесс решения задач математической оптимизации с использованием квадратичных функций. 
  • Оно является разновидностью нелинейного программирования и используется с 1940-х годов. 

• Формулировка задачи

  • Задача квадратичного программирования заключается в нахождении вектора x, который минимизирует или максимизирует квадратичную функцию при линейных ограничениях. 

• Ограниченные наименьшие квадраты и обобщения

  • В случае симметричной положительно определенной матрицы Q функция затрат сводится к наименьшим квадратам. 
  • Существуют методы решения задач квадратичного программирования, включая внутреннюю точку, активный набор и другие. 

• Ограничения на равенство и лагранжева двойственность

  • При положительно определенной Q и ограничениях на равенство процесс решения является линейным. 
  • Лагранжева двойственность позволяет найти нижнюю границу функции Лагранжа. 

• Сложность во время выполнения

  • Выпуклое квадратичное программирование с положительно определенной Q может быть решено за полиномиальное время. 
  • Невыпуклое квадратичное программирование является NP-сложным, даже если Q имеет одно отрицательное собственное значение. 

• Квадратичное программирование со смешанными целыми числами

  • MIQP включает задачи, в которых некоторые элементы вектора x должны принимать целые значения. 

• Решатели и скриптовые языки

  • Существуют расширения квадратичного программирования, такие как полиномиальная оптимизация. 
  • Для решения задач квадратичного программирования используются различные методы и скриптовые языки.