Том 29, номер 3, 2022 г., Стр. 24-44
УДК 519.8
Крутиков В. Н., Станимирович П. С., Инденко О. Н., Товбис Е. М., Казаковцев Л. А.
Оптимизация параметров субградиентного метода на основе двухранговой коррекции матриц метрики
Аннотация:
Предлагается релаксационный субградиентный метод, включающий оптимизацию параметров с использованием коррекции матриц метрики второго ранга, со структурой, аналогичной квазиньютоновским методам. Преобразование матрицы метрики заключается в подавлении ортогональных и усилении коллинеарных компонентов вектора субградиента минимальной длины. Задача построения матрицы метрики формулируется как задача решения системы неравенств. Решение такой системы основано на новом алгоритме обучения. Получена оценка скорости его сходимости в зависимости от параметров множества субградиентов. На этой основе разработан и исследован новый релаксационный субградиентный метод. Вычислительные эксперименты над сложными функциями большой размерности подтверждают эффективность предложенного алгоритма.
Табл. 4, библиогр. 32.
Ключевые слова: выпуклая оптимизация, негладкая оптимизация, релаксационный субградиентный метод.
DOI: 10.33048/daio.2022.29.739
Крутиков Владимир Николаевич 1
Станимирович Предраг 2
Инденко Оксана Николаевна 1
Товбис Елена Михайловна 3
Казаковцев Лев Александрович 3
1. Кемеровский гос. университет,
ул. Красная, 6, 650043 Кемерово, Россия
2. Факультет естественных наук и математики, Нишский университет,
ул. Вышеградска, 33, 18000 Ниш, Сербия
3. Сибирский гос. университет науки и технологий им. акад. Решетнёва,
пр. Красноярский рабочий, 31, 660031 Красноярск, Россия
е-mail: krutikovvn@rambler.ru, pecko@pmf.ni.ac.rs, oksana230805@mail.ru, sibstu2006@rambler.ru, levk@bk.ru
Статья поступила 10 мая 2022 г.
После доработки — 10 мая 2022 г.
Принята к публикации 12 мая 2022 г.
Литература
[1] Шор Н. З. Применение метода градиентного спуска для решения сетевой транспортной задачи // Мат. науч. семинара по теор. и прикл. вопросам кибернетики и исследования операций. Вып. 1. К.: Науч. совет по кибернетике АН УССР, 1962. С. 9–17.
[2] Поляк Б. Т. Один общий метод решения экстремальных задач // Докл. АН СССР. 1967. Т. 174, вып. 1. С. 33–36.
[3] Поляк Б. Т. Введение в оптимизацию. М.: Наука, 1983.
[4] Wolfe P. Note on a method of conjugate subgradients for minimizing nondifferentiable functions // Math. Program. 1974. V. 7, No. 1. P. 380–383.
[5] Гольштейн Е. Г., Немировский А. С., Нестеров Ю. Е. Метод уровней, его обобщения и приложения // Экономика и мат. методы. 1983. Т. 31, вып. 3. С. 164–180.
[6] Nesterov Yu. E. Universal gradient methods for convex optimization problems // Math. Program. Ser. A. 2015. V. 152. P. 381–404.
[7] Gasnikov A. V., Nesterov Yu. E. Universal method for stochastic composite optimization. Ithaca, NY: Cornell Univ., 2016. (Cornell Univ. Libr. e-Print Archive; arXiv:1604.05275).
[8] Ouyang H., Gray A. Stochastic smoothing for nonsmooth minimizations: Accelerating SGD by exploiting structure // Proc. 29th Int. Conf. Machine Learning (Edinburgh, Scotland, June 26–July 1, 2012). Madison, WI: Omni-press, 2012. P. 33–40.
[9] Boob D., Deng Q., Lan G. Stochastic first-order methods for convex and nonconvex functional constrained optimization // Math. Program. 2022. [in print].
Available at doi.org/10.1007/s10107-021-01742-y (accessed June 17, 2022).
[10] Lan G. First-order and stochastic optimization methods for machine learning. Cham: Springer, 2020.
[11] Ghadimi S., Lan G. Accelerated gradient methods for nonconvex nonlinear and stochastic programming // Math. Program. 2016. V. 156, No. 1–2. P. 59–99.
[12] Fang C., Li C. J., Lin Z., Zhang T. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator // Advances in Neural Information Processing Systems 31. 32nd Annual Conf. (Montréal, Canada, Dec. 3–8, 2018). Red Hook, NY: Curran Associates, 2018. P. 687–697.
[13] Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979.
[14] Шор Н. З. Методы минимизации недифференцируемых функций и их приложения. К.: Наук. думка, 1979.
[15] Cao H., Song Y., Khan K. Convergence of subtangent-based relaxations of non-linear programs // Processes. 2019. V. 7, No. 4. P. 221.
[16] Поляк Б. Т. Минимизация негладких функционалов // Журн. вычисл. математики и мат. физики. 1969. Т. 9, вып. 3. С. 509–521.
[17] Крутиков В. Н., Самойленко Н. С., Мешечкин В. В. О свойствах метода минимизации выпуклых функций, релаксационного по расстоянию до экстремума // Автоматика и телемеханика. 2019. Т. 80, вып. 1. С. 126–137.
[18] Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. М.: Наука, 1981.
[19] Lemarechal C. An extension of Davidon methods to non-differentiable problems // Math. Program. Study. 1975. V. 3. P. 95–109.
[20] Крутиков В. Н., Петрова Т. В. Релаксационный метод минимизации с растяжением пространства в направлении субградиента // Экономика и мат. методы. 2003. Т. 39, вып. 1. С. 106–119.
[21] Крутиков В. Н., Горская Т. А. Семейство релаксационных субградиентных методов с двухранговой коррекцией матриц метрики // Экономика и мат. методы. 2009. Т. 45, вып. 4. С. 37–80.
[22] Скоков В. А. Замечание к методам оптимизации, использующим операцию растяжения пространства // Кибернетика и систем. анализ. 1974. № 4. С. 115–117.
[23] Крутиков В. Н., Самойленко Н. С. О скорости сходимости субградиентного метода с изменением метрики и его приложения в схемах нейросетевых приближений // Вестн. Томск. гос. ун-та. Сер. Математика и механика. 2018. № 55. С. 22–37.
[24] Nocedal J., Wright S. J. Numerical optimization. New York: Springer, 2006.
[25] Avriel M. Nonlinear programming: Analysis and methods. Mineola: Dover Publ., 2003.
[26] Нурминский Е. А., Тьен Д. Метод сопряжённых субградиентов с ограниченной памятью // Автоматика и телемеханика. 2014. Т. 75, вып. 4. С. 646–656.
[27] Цыпкин Я. З. Основы теории обучающихся систем. М.: Наука, 1970.
[28] Жуковский Е. Л., Липцер Р. Ш. О рекуррентном способе вычисления нормальных решений линейных алгебраических уравнений // Журн. вычисл. математики и мат. физики. 1972. Т. 12, вып. 4. С. 843–857.
[29] Krutikov V. N., Kazakovtsev L. A., Kazakovtsev V. L. Non-smooth regularization in radial artificial neural networks // IOP Conf. Ser.: Materials Science and Engineering. 2018. V. 450, No. 4, ID 042010. 7 p.
[30] Krutikov V. N., Kazakovtsev L. A., Shkaberina G. Sh., Kazakovtsev V. L. New method of training two-layer sigmoid neural networks using regularization // IOP Conf. Ser.: Materials Science and Engineering. 2019. V. 537, No. 4, ID 042055. 6 p.
[31] Tibshirani R. J. Regression shrinkage and selection via the Lasso // J. Royal Stat. Soc. Ser. B (Methodological). 1996. V. 58. P. 267–288.
[32] Frostig R., Ge R., Kakade S. M., Sidford A. Un-regularizing: Approximate proximal point and faster stochastic algorithms for empirical risk minimization // Proc. Mach. Learn. Res. 2015. V. 37. P. 2540–2548.
