APPLICATION OF INTERVAL SLOPES IN NONSMOOTH ONE-DIMENSIONAL OPTIMIZATION PROBLEMS

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The interval interpretation of a first-order divided difference, namely, interval slope is considered. Some properties of interval slopes, including ones for convex (concave) functions are proved. Based on the interval slope, necessary and sufficient conditions for the monotonicity of a function are formulated and proved. These criteria are used to propose an algorithm for the global optimization of a one-variable function taking into account its monotonicity. Numerical experiments are conducted that show that the developed global optimization method is applicable in the nondifferentiable case and significantly accelerates finding an approximate global optimum as compared with the basic version.

About the authors

M. A. Posypkin

Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences; Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University

Email: mposypkin@frccsc.ru
Moscow, 119333 Russia; Moscow, 119991 Russia

D. A. Sidnev

National Research University of Electronic Technology (MIET)

Email: sidnew2001@gmail.com
Zelenograd, Moscow, 124498 Russia

References

  1. Johnson D.E. Introduction to filter theory. Prentice Hall, 1976.
  2. Zilinskas A. Optimization of one-dimensional multimodal functions // J. Royal Statistic. Soc., Ser. C (Applied Statistics). 1978. V. 27. № 3.
  3. Kvasov D.E., Menniti D., Pinnarelli A., et al. Tuning fuzzy power-system stabilizers in multi-machine systems by global optimization algorithms based on efficient domain partitions // Electric Power Syst. Res. 2008. V. 78. № 7. P. 1217–1229.
  4. Bedrosian D., Vlach J. Time-domain analysis of networks with internally controlled switches // IEEE Transact. on Circuits and Systems I: Fundament. Theory and Appl. 1992. V. 39. № 3. P. 199–212.
  5. Femia N., Tucci V. On the modeling of PWM converters for large signal analysis in discontinuous conduction mode // IEEE Transact. on Power Electronics. 1994. V. 9. № 5. P. 487–496.
  6. Fasano G., Pint’er J.D. Efficient piecewise linearization for a class of nonconvex optimization problems: comparative results and extensions // Model. and Optimizat.: Theory and Appl.: MOPTA, Bethlehem, PA, USA, August 2017, Selected Contributions / Springer. 2019. P. 39–56.
  7. Lassere J.B. Connecting optimization with spectral analysis of tridiagonal matrices // Math. Program. 2020. https://doi.org/10.1007/s10107-020-01549-3.
  8. Jensen P.A., Bard J.F., Jensen P. Operations research models and methods. John Wiley & Sons, 2003.
  9. Pint’er J. Extended univariate algorithms for n-dimensional global optimization // Computing. 1986. V. 36. № 1–2. P. 91–103.
  10. Strongin R.G., Sergeyev Y.D. Global optimization with non-convex constraints: Sequential and parallel algorithms. Springer Science & Business Media, 2013. V. 45.
  11. Gergel V., Grishagin V., Gergel A. Adaptive nested optimization scheme for multidimensional global search // J. Global Optimizat. 2016. V. 66. P. 35–51.
  12. Sergeyev Y.D., Nasso M.C., Lera D. Numerical methods using two different approximations of space-filling curves for black-box global optimization // J. Global Optimizat. 2024. V. 88. № 3. P. 707–722.
  13. Calvin J.M., Chen Y., Zilinskas A. An adaptive univariate global optimization algorithm and its convergence rate for twice continuously differentiable functions // J. Optimizat. Theory and Appl. 2012. V. 155. P. 628–636.
  14. Sergeyev Y.D., Candelieri A., Kvasov D.E., Perego R. Safe global optimization of expensive noisy black-box functions in the δLipschitz framework // Soft Comput. 2020. V. 24. № 23. P. 17715–17735.
  15. Posypkin M., Usov A., Khamisov O. Piecewise linear bounding functions in univariate global optimization // Soft Comput. 2020. V. 24. P. 17631–17647.
  16. Posypkin M., Khamisov O. Automatic Convexity Deduction for Efficient Function’s Range Bounding // Mathematics. 2021. V. 9. № 2. P. 134.
  17. Sergeyev Y.D., Nasso M.C., Mukhametzhanov M.S., Kvasov D.E. Novel local tuning techniques for speeding up onedimensional algorithms in expensive global optimization using Lipschitz derivatives // J. Comput. and Appl. Math. 2021. V. 383. P. 113134.
  18. Posypkin M.A., Sergeyev Y.D. Efficient smooth minorants for global optimization of univariate functions with the first derivative satisfying the interval Lipschitz condition // J. Global Optimizat. 2022. P. 1–29.
  19. Moore R.E., Kearfott R.B., Cloud M.J. Introduction to interval analysis/Ramon E // Moore, R. Baker Kearfott, Michael J. Cloud. Philadelphia, 2009.
  20. Шарый С.П. Конечномерный интервальный анализ. Новосибирск: ИВТ СО РАН, 2022.
  21. Neumaier A. Interval methods for systems of equations. Cambridge Univer. Press, 1990.
  22. Хансен Э., Уолстер Дж.У. Глобальная оптимизация с помощью методов интервального анализа / Ed. by Шарой, С.П. 2-е изд., перевод с англ. М., Ижевск: Ин-т компьют. исслед.: R&C Dynamics, 2012.
  23. Ratschek H., Rokne J. New computer methods for global optimization. Halsted Press, 1988.
  24. Kearfott R.B. Rigorous global search: continuous problems. Springer Science & Business Media, 2013. V. 13.
  25. Баженов А.Н., Жилин С.И., Кумков С.И., Шарый С.П. Обработка и анализ интервальных данных. М.: НИЦ “Регулярная и хаотическая динамика”, 2024.
  26. Jafarpour S., Harapanahalli A., Coogan S. Efficient interaction-aware interval analysis of neural network feedback loops // IEEE Transactions on Automatic Control. 2024.
  27. A branch and prune algorithm for the computation of generalized aspects of parallel robots / Caro S., Chablat D., Goldsztejn A. et al. // Artificial Intelligence. 2014. V. 211. P. 34–50. URL: https://www.sciencedirect.com/science/article/pii/S0004370214000125.
  28. Евтушенко Ю.Г., Посыпкин М.А. Метод неравномерных покрытий для решения задач многокритериальной оптимизации с гарантированной точностью // Ж. вычисл. матем. и матем. физ. 2013. Т. 53. № 2. С. 209–224.
  29. Kvasov, D., Sergeev, Y. et al. Lipschitz expensive global optimization // Encyclopedia of Optimization. Springer, 2023.
  30. Stripinis L., Paulavicius R. Lipschitz-inspired HALRECT algorithm for derivative-free global optimization // J. of Global Optimization. 2024. V. 88. № 1. P. 139–169.
  31. Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // Ж. вычисл. матем. и матем. физ. 1971. Т. 11. № 6. С. 1390–1403.
  32. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
  33. Ratz D. A nonsmooth global optimization technique using slopes: the one-dimensional case // J. of Global Optimization. 1999. V. 14. P. 365–393.
  34. Ratz D. An Optimized Interval Slope Arithmetic and its Application // Inst. fur Angewandte Mathematik. 1996.
  35. Kearfott R.B., Nakao M., Neumaier A. и др. Standardized notation in interval analysis // Вычисл. технологии. 2010. Т. 15. № 1. С. 7–13.
  36. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. 1987.
  37. Ильин В.А., Садовничий В.А., Сендов Бл.Х. Математического анализ: Начальный курс. М.: МГУ, 1985.
  38. Рокафеллар Р. Выпуклый анализ. М.: МИР, 1973.
  39. Skelboe Stig. Computation of rational interval functions // BIT Numerical Mathematics. 1974. V. 14. № 1. P. 87–95.
  40. Grant M., Boyd S., Ye Y. Disciplined convex programming. London: Springer, 2006.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Russian Academy of Sciences

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».