17 Метод проекции (суб)градиента. Метод условного градиента (метод Франк - Вульфа). МФТИ 2023

• Обсуждение методов оптимизации с ограничениями, таких как функция Лагранжа и двойственность.  

• Обсуждение более дешевого подхода к оптимизации с ограничениями, основанного на методе градиентного спуска.  

• Введение понятия проекции и евклидовой проекции как решения задачи оптимизации с ограничениями.  

• Обсуждение условий существования проекции и ее использования в методе градиентного спуска.  

• Если множество открыто, то проекция не существует.  

• Если точка лежит внутри множества, то ее проекция - это сама точка.  

• Вектор из точки игрек в проекцию на множество с называется антиградиентом.  

• Скалярное произведение антиградиента и вектора из точки икс в икс должно быть отрицательным.  

• Оператор проекции не растягивающий, если константа Липшица равна единице.  

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

• Автор объясняет, что метод проекции градиента можно использовать для доказательства сходимости в выпуклом и гладком случае.  

• Он приводит пример, как можно оценить скалярное произведение икс к плюс первая и икс со звездочкой, используя неравенство Каши-Буковского-Шварца.  

• Автор объясняет, что теоремы сходимости основаны на доказательстве этого факта, который является важным результатом.  

• Он также приводит пример, как этот факт можно использовать для доказательства сходимости метода проекции градиента.  

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

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

• В видео приводятся примеры проекций на различные множества, такие как шар, гиперплоскость и симплекс.  

• Стоимость каждой проекции может быть дорогой, так как это оптимизационная задача.  

• В видео представлен алгоритм франко-вульфа, который позволяет эффективно находить проекции на сложные множества.  

• Идея алгоритма заключается в поиске условного минимума линейной аппроксимации функции в точке.  

• В видео объясняется алгоритм Франк-Вульфа, который используется для оптимизации линейных функций.  

• Итерация алгоритма состоит из линейной комбинации предыдущих точек и оптимизации линейной модели функции.  

• Видео иллюстрирует геометрическую интерпретацию алгоритма, где итерация представляет собой точку между двумя точками, являющимися выпуклой комбинацией предыдущих точек.  

• В видео обсуждаются скорость сходимости и модификации алгоритма Франк-Вульфа.  

• В гладком случае скорость сходимости равна 1/корень из k, что аналогично скорости сходимости для метода проекции градиента.  

• В сильно выпуклом случае скорость сходимости также равна 1/корень из k.