Комментарии 20
Жаль, что материал на такую тему исключительно справочный… Есть ли ссылки на адекватные программные реализации? (Без симплекса — его и так много)
Смотря для каких целей. Если для прикладных — не стоит задумываться о том, как и какой метод реализован, лучше просто использовать готовый пакет оптимизации типа гуроби, cvxopt или scipy.optimize. Есть например хороший интерфейс на питон — cvxpy. В matlab точно что-то есть, скорее всего и в подобных математических продуктах тоже.
Если нужно «пощупать» руками, я могу дать свои реализации, по которым анимации строил.
Если нужно «пощупать» руками, я могу дать свои реализации, по которым анимации строил.
Спасибо. Я много лет использую библиотеку PuLP, вдруг пригодится… Кстати, какой метод реализован — на больших размерностях бывает важно… Во всяком случае, если вы хотите знать сколько времени (хотя бы порядок) может занять сам расчет. Вообще, у меня есть небольшая претензия к названию статьи (излишне обобщили), но это мелочи с учётом того, что вы продемонстрировали ;) Спасибо
Спасибо за статью. Добавьте, пожалуйста, список используемой литературы.
Отличная статья!
По методу внутренней точки для линейного программирования:
— логарифмический барьер — правильный? (шаг метода Ньютона генерирует точку, которая остается внутри нашего множества)
— шаг метода L-BFGS с логарифмическим барьером генерирует точку, которая остается внутри нашего множества?
— какие обычно значения берутся для t0 и a?
По методу внутренней точки для линейного программирования:
— логарифмический барьер — правильный? (шаг метода Ньютона генерирует точку, которая остается внутри нашего множества)
— шаг метода L-BFGS с логарифмическим барьером генерирует точку, которая остается внутри нашего множества?
— какие обычно значения берутся для t0 и a?
Логарифмический барьер — правильный. К сожалению тут есть небольшие тонкости с выбором начальных данных. Готового рецепта на все случаи жизни я к сожалению не готов дать. Когда готовил анимации у меня возникла проблема, что Ньютон разваливался. Тогда я это решил методом научного тыка.
Про BFGS и все его вариации не могу ничего сказать, лично я пробовал применять градиентный спуск вместо Ньютона — ничего хорошего не выходило. Всегда можно самому попробовать, но думаю, что уже пробовали не один раз. Метод внутренней точки придумали давно и Ньютон там засел намертво.
Про BFGS и все его вариации не могу ничего сказать, лично я пробовал применять градиентный спуск вместо Ньютона — ничего хорошего не выходило. Всегда можно самому попробовать, но думаю, что уже пробовали не один раз. Метод внутренней точки придумали давно и Ньютон там засел намертво.
Что значит, Ньютон разваливался?
Еще не пробовал. Ищу методы с адекватной сложностью. Ваша статья очень помогла мне.
Какие значения t0 и a вы брали для демонстрации?
Еще не пробовал. Ищу методы с адекватной сложностью. Ваша статья очень помогла мне.
Какие значения t0 и a вы брали для демонстрации?
А симплекс-метод работает только для линейных ограничений и линейных функций?
Если не ошибаюсь, проективные градиенты и подобные ему — первого порядка сходимости, поэтому на практике, c общими нелинейными функциями, работают медленнее, чем, например, SQP, где локально решается задача квадратичного программирования. Я сам это наблюдал, когда использовал его с коробочными ограничениями. Если не присобачить поправку второго порядка, сходиться будет как черепаха.
А вообще классная тема. Обогнали меня, сам хотел что-то такое в перспективе написать!:)
А вообще классная тема. Обогнали меня, сам хотел что-то такое в перспективе написать!:)
Если говорить о количестве итераций до достижения определенной точности, то да — чем выше порядок метода, тем быстрее он сходится. Однако есть и другая сторона медали — чем выше порядок метода, тем сложнее одна итерация, и тем сложнее применять эти методы в пространствах очень больших размерностей. Например, градиентный спуск очень распространен в нейронных сетях, где обычно не меньше миллиона параметров, причем в основном его «стохастический» вариант, который очень хорошо укладывается в парадигму ML. Применять его в пространствах размера < 10000 практически бессмысленно, есть достаточно методов, которые будут работать быстрее.
Если не секрет, не подскажете, каким софтом рисовали анимацию сходящихся итераций для этого поста? Очень-очень полезная вещь!
Не секрет, это python/matplotlib. Я хотел приложить ноутбук к статье, но в итоге недооформил адекватно. Сейчас могу только выложить черновик
Уточните, пожалуйста, обоснованность «Выбрать новое приближение методом Ньютона». Вы его применяете так, будто хотите найти не минимум, а 0 от функции fi(x,t).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Обзор основных методов математической оптимизации для задач с ограничениями