Существует ли более простое условие раннего завершения в простом двойственном алгоритме для ограниченной квадратичной функции

Question

В настоящее время я использую простой двойственный метод для минимизации квадратичной задачи с простыми линейными ограничениями (в частности, x >= 0). Для условия завершения я в настоящее время использую стандарт: т. Е. Ошибка "e" должна быть меньше порогового значения.

Однако вычислить термин "е" относительно дорого, так как мне нужно оценить полную квадратичную функцию. Возможно ли иметь более простое / быстрое условие завершения, например одно из следующих:

1) если сумма всех изменений в x ниже определенного порога, то завершается; или 2) если максимальное изменение x ниже определенного порога, тогда прекратить?

Интуитивно, это имеет смысл для меня, но я обнаружил, что моя интуиция наполовину неверна с этими проблемами минимизации, поэтому я не уверен, является ли моя интуиция теоретически правильной или нет....

Answer 1

Практика 1:

For the termination condition, I'm currently using the standard: ie error "e" term must be less than a threshold value. Разве вы не предполагаете, что цель может быть увеличена до 0 здесь? Как вы определяете этот порог априори?

Что касается теории:

• 1) if the sum of all the changes in x is below a certain threshold, then terminate
  • это эвристика (может быть хорошей идеей взять внешнее абсолютное значение), и я думаю, что я видел нечто подобное в других кодах)
  • не имеет теоретических гарантий; не достаточно, но необходимое условие
• 2) if the max change in x is below a certain threshold, then terminate
  • часто используемый эвристический
  • опять же: нет теоретических гарантий; не достаточно, но необходимое условие

• Вы должны посмотреть на условия Каруша-Куна-Такера (необходимые условия первого порядка для решения)

  • Тип KKT-условий, которые вам могут понадобиться, зависит от вашей задачи: выпуклый или невыпуклый -> Q psd или нет (редактируйте, кажется, ваше выпуклое в соответствии с вашими тегами!)
  • Интересное чтение с особым вниманием к вашей проблеме

  • Замечание: ваша проблема - QP с ограничением на блоки, который на самом деле проще, чем QP с ограничением по неравенству! Это важно!

    • Почему важно?: потому что спроектированные подходы без ограничений будут работать, а без ограничений гораздо проще. Кроме того, важно в этом случае: ваша проекция кажется дешевой по сравнению с вычислением цели (в вашем случае проекция линейна)!
    • Проверьте страницы 8- 11

Теперь это может повлиять на некоторые тяжелые теоретические работы, сопровождаемые некоторой реализацией. Рассмотрите возможность использования уже доступных инструментов!

Практика 2:

Обратите внимание на QP-решатели с ограничениями на блоки (выпуклые или невыпуклые; в зависимости от вашей задачи). Они должны быть доступны и избавят вас от неприятностей!

Вы могли бы даже использовать почти везде доступный LBFGS-B, который может быть уже трудно победить, если вы дадите ему градиенты (в отличие от численного дифференцирования). Хотя это гораздо более общее, часто очень мощное! (в python, используя scipy, это будет несколько строк)

L-BFGS-B - это квазиньютоновский код с ограниченной памятью для оптимизации с ограничениями по границам, т. Е. Для задач, в которых единственные ограничения имеют вид l<= x <= u.

Возможно, есть и другие доступные альтернативы. Доверие Регион Светоотражающий и Ко.

(Примечание: мне интересно, как стоимость оценки может быть такой высокой, как вы описываете, по сравнению с другими операциями в вашем алгоритме primal-dual (IPM?))