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

Octave также может решать задачи квадратичного программирования, это

min 0.5 x'*H*x + x'*q

при условии

A*x = b
     lb <= x <= ub
     A_lb <= A_in*x <= A_ub

: [x, obj, info, lambda] = qp (x0, H) ¶

: [x, obj, info, lambda] = qp (x0, H, q) ¶

: [x, obj, info, lambda] = qp (x0, H, q, A, b) ¶

: [x, obj, info, lambda] = qp (x0, H, q, A, b, lb, ub) ¶

: [x, obj, info, lambda] = qp (x0, H, q, A, b, lb, ub, A_lb, A_in, A_ub) ¶

: [x, obj, info, lambda] = qp (…, options) ¶

Решить задачу квадратичного программирования (QP).

Решить задачу квадратичного программирования, определенную

min 0.5 x'*H*x + x'*q
 x

при условии

A*x = b
lb <= x <= ub
A_lb <= A_in*x <= A_ub

используя метод активных множеств нулевого пространства.

Любой предел (A, b, lb, ub, A_in, A_lb, A_ub) может быть установлен в пустую матрицу ([]) если отсутствует. Ограничения A и A_in являются матрицами, каждая строка которых представляет собой одно ограничение. Другие границы являются скалярами или векторами в зависимости от количества ограничений. Алгоритм работает быстрее, если начальное предположение является выполнимым.

options — структура, определяющая дополнительные параметры, которые контролируют алгоритм. В настоящее время qp распознаёт следующие параметры: "MaxIter", "TolX".

"MaxIter" предписывает максимальное количество итераций алгоритма до остановки оптимизации. Значение по умолчанию равно 200. Значение должно быть положительным целым числом.

"TolX" определяет толерантность завершения для неизвестных переменных x. По умолчанию sqrt (eps) или приблизительно 1e-8.

При возвращении x — местоположение минимума, а fval содержит значение целевой функции в x.

info

Структура, содержащая информацию о выполнении алгоритма. Определены следующие поля:

solveiter

Количество итераций, необходимых для получения решения.

info

Целое число, указывающее состояние решения.

0

Задача выполнима и выпуклая. Найдено глобальное решение.

1

Задача не является выпуклой. Найдено локальное решение.

2

Задача не выпуклая и неограниченная.

3

Достигнуто максимальное количество итераций.

6

Задача невыполнима.

См. также: sqp.

: x = pqpnonneg (c, d) ¶

: x = pqpnonneg (c, d, x0) ¶

: x = pqpnonneg (c, d, x0, options) ¶

: [x, minval] = pqpnonneg (…) ¶

: [x, minval, exitflag] = pqpnonneg (…) ¶

: [x, minval, exitflag, output] = pqpnonneg (…) ¶

: [x, minval, exitflag, output, lambda] = pqpnonneg (…) ¶

Минимизировать (1/2 * x' * c * x + d' * x) при условии x >= 0.

c и d должны быть вещественными матрицами, а c должна быть симметричной и положительно определённой.

x0 — необязательное начальное предположение для решения x.

options — структура параметров для изменения поведения алгоритма (см. optimset). pqpnonneg распознаёт один параметр: "MaxIter".

Результаты:

x

Матрица решения

minval

Достигнутое минимальное значение модели, 1/2*xmin'*c*xmin + d'*xmin

exitflag

Индикатор сходимости. 0 указывает, что количество итераций было превышено, и поэтому сходимость не достигнута; >0 указывает, что алгоритм сошёлся. (Алгоритм стабилен и сходится при достаточном количестве итераций.)

output

Структура с двумя полями:

• "algorithm": Используемый алгоритм ("nnls")
• "iterations": Количество выполненных итераций.

lambda

Лагранжевы множители. Если они не равны нулю, соответствующие значения x должны быть равны нулю, что указывает на то, что решение прижато к координатной плоскости. Величина указывает, насколько улучшится остаток, если ограничения x >= 0 будут ослаблены в этом направлении.

См. также: lsqnonneg, qp, optimset.