- Метод переменного отображения близости для выпукло-вогнутых задач с седловой точкой (arXiv)
Автор: Хуэй Оуян
Аннотация: Предложена итерационная схема решения выпукло-вогнутых седловых задач, связанных с общими выпукло-вогнутыми функциями. Мы продемонстрировали, что когда наша итерационная схема применяется к специальному классу выпукло-вогнутых функций, которые строятся с помощью билинейного члена связи плюс разности двух выпуклых функций, она становится обобщением нескольких популярных прямо-двойственных алгоритмов с постоянными задействованными параметрами к задействованным параметрам как общие последовательности. Для этого конкретного класса выпукло-вогнутых функций мы доказали, что последовательность значений функции, взятая по средним значениям итераций, сгенерированных нашей схемой, сходится к значению функции в седловой точке. Кроме того, мы предоставили результаты сходимости как для последовательности средних наших итераций, так и для последовательности наших итераций. В наших численных экспериментах мы реализовали наш алгоритм в матричной игре, линейной программе в форме неравенства и задаче наименьших квадратов с регуляризацией ℓ1. В этих примерах мы также сравнили наш алгоритм с другими первично-двойственными алгоритмами, в которых параметры в их итерационных схемах оставались постоянными. Наши экспериментальные результаты подтвердили наши теоретические выводы. Кроме того, на основе наших экспериментов мы заметили, что когда мы рассматриваем один из трех примеров, упомянутых выше, либо последовательность вычислений функции на средних значениях итераций, либо последовательность вычислений функций на итерациях превосходит другую, независимо от изменений. в итерационных схемах, данных задачи и начальных точках. Мы также отметили, что некоторые задействованные параметры в некоторых случаях не влияют на скорость сходимости, и что наш алгоритм постоянно работает очень хорошо по сравнению с различными схемами итерации с постоянными задействованными параметрами.
2. Методы чередующихся субградиентов для выпукло-вогнутых задач с седловой точкой (arXiv)
Автор: Хуэй Оуян
Аннотация: Предлагается альтернирующий субградиентный метод с непостоянными размерами шага для решения выпукло-вогнутых седловых задач, связанных с общими выпукло-вогнутыми функциями. Мы предполагаем, что последовательность размеров наших шагов является не суммируемой, а суммируемой с квадратами. Затем в популярном предположении о равномерно ограниченных субградиентах мы доказываем, что последовательность выпуклых комбинаций значений функции на наших итерациях сходится к значению функции в седловой точке. Кроме того, основываясь на нашем результате об ограниченности последовательности наших итераций, мы показываем, что последовательность функции, оцениваемой в выпуклых комбинациях наших итераций, также сходится к значению функции в седловой точке. Мы реализуем наши алгоритмы на примерах линейной программы в форме неравенства, задачи наименьших квадратов с ℓ1 регуляризацией, матричной игры и надежной задачи построения портфеля Марковица. Чтобы ускорить сходимость, мы переупорядочили последовательность размеров шагов в порядке убывания, что оказалось очень хорошим в наших примерах. Наши результаты сходимости подтверждаются нашими численными экспериментами. Более того, мы также численно сравниваем нашу итерационную схему с итерационными схемами, связанными с постоянными размерами шага. Наши численные результаты подтверждают наш выбор размера шага. Кроме того, мы наблюдаем сходимость последовательности значений функции на наших итерациях в нескольких экспериментах, что в настоящее время не имеет теоретической поддержки.
