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.