Кто знает вычислительную сложность функции quadprog в MATLAB?

Question

Задача QP является выпуклой. Для Wiki проблема может быть решена за полиномиальное время. Но что именно заказ?

Answer 1

Это интересный вопрос (на мой взгляд) без четкого ответа. Я собираюсь предположить, что ваша проблема является выпуклой, и вы заинтересованы в сложности во время выполнения (в отличие от сложности итерации).

• Как ты можешь знать, QuadProg это не один алгоритм, а скорее общее название для чего-то, что решает квадратичные задачи. Он использует набор алгоритмов, а именно. Внутренняя точка (по умолчанию), область доверия и активный набор. Источник
• В зависимости от того, что вы выберете, каждый из этих алгоритмов будет иметь свой собственный анализ сложности. Для методов Trust-Region и Active-Set анализ сложности чрезвычайно сложен. Фактически, методы Active-Set не являются полиномиальными с самого начала. Контрпримеры существуют там, где методы активного набора требуют экспоненциального "времени", чтобы сходиться (это также верно для симплексного метода для линейных программ). Источник
• Теперь, предполагая, что вы выбираете методы Внутренней Точки, ответ все еще не прост, потому что есть различные варианты этих методов. Когда Кармаркар впервые предложил этот метод, он был первым известным полиномиальным алгоритмом для решения линейных программ и имел сложность O(n^3.5). Источник Эти границы были улучшены довольно много позже. Тем не менее, это для линейных программ.
• Наконец, чтобы ответить на ваш вопрос, в 1989 году Е и Тсе доказали, что у нас может быть метод внутренней точки со сложностью O(n^3). Тем не менее, будет ли MATLAB использовать этот точный вариант метода Внутренней Точки, немного сложно понять, но O (n ^ 3) будет моим лучшим предположением.

Конечно, мой ответ довольно теоретический; если вы хотите эмпирически проверить это, вы можете сделать это, постепенно увеличивая количество переменных и нанося на график время процессора, необходимое для получения оценки.