Hardprob/Maximum Quadratic Programming — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
* Положительное целое <em>n</em>, набор линейных ограничений заданных в виде <em>m×n</em> матрицы, и <em>m</em>-вектора <em>b</em>, задающие область <m>S⊆ R^n</m> ограничениями <m>S=\{x∈  [0,1]^n: Ax≤b\}</m>.
 
* Положительное целое <em>n</em>, набор линейных ограничений заданных в виде <em>m×n</em> матрицы, и <em>m</em>-вектора <em>b</em>, задающие область <m>S⊆ R^n</m> ограничениями <m>S=\{x∈  [0,1]^n: Ax≤b\}</m>.
* [https://en.wikipedia.org/wiki/Polynomial многомерный многочлен] <em>f<em>, максимальной степени не больше 2.
+
* [https://en.wikipedia.org/wiki/Polynomial многомерный многочлен] <em>f<em>, максимальной степени не больше 2. Имея
 +
** <em>Q</em> — симметричная положительно-полуопределенная матрица,
 +
** <em>c</em> — вектор линейных коэффициентов
 +
* Можно представить его в виде:
 +
<m>
 +
  f(x) = x^{T} Q x + c^{T} x
 +
</m>
 
* Максимизировать значение <em>f</em> в области заданной линейными ограничениями, т.е. <m>\max_{x∈  S} f(x) → \max</m>.
 
* Максимизировать значение <em>f</em> в области заданной линейными ограничениями, т.е. <m>\max_{x∈  S} f(x) → \max</m>.
  

Версия 13:35, 27 апреля 2023

  • Положительное целое n, набор линейных ограничений заданных в виде m×n матрицы, и m-вектора b, задающие область ограничениями .
  • многомерный многочлен f, максимальной степени не больше 2. Имея
    • Q — симметричная положительно-полуопределенная матрица,
    • c — вектор линейных коэффициентов
  • Можно представить его в виде:

  • Максимизировать значение f в области заданной линейными ограничениями, т.е. .

Задача в лаб22 (рид-онли просмотр)