О сходимости локально Парето-оптимального поиска
Исследованы условия сходимости прямых методов непрерывной векторной оптимизации, которые не сводятся к скалярной оптимизации. Практические варианты этих методов предполагают дискретизацию допустимой области, аппроксимацию целевых функций и решение последовательности дискретных задач векторной оптими...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2015 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/112397 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О сходимости локально Парето-оптимального поиска / Б.В. Норкин // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 52-57. — Бібліогр.: 13 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859471704392204288 |
|---|---|
| author | Норкин, Б.В. |
| author_facet | Норкин, Б.В. |
| citation_txt | О сходимости локально Парето-оптимального поиска / Б.В. Норкин // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 52-57. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Исследованы условия сходимости прямых методов непрерывной векторной оптимизации, которые не сводятся к скалярной оптимизации. Практические варианты этих методов предполагают дискретизацию допустимой области, аппроксимацию целевых функций и решение последовательности дискретных задач векторной оптимизации. При небольших размерностях пространства решений дискретные задачи могут быть решены перебором. Приведены достаточные условия, при которых локально Парето-оптимальные решения приближенных задач аппроксимируют локально Парето-оптимальные решения исходной задачи (с некоторой точностью).
Досліджено умови збіжності прямих методів неперервної векторної оптимізації, які не зводяться до скалярної оптимізації. Практичні варіанти цих методів припускають дискретизацію допустимої області, апроксимацію цільових функцій і розв’язання послідовності дискретних задач векторної оптимізації. При невеликій вимірності простору рішень дискретні задачі можуть бути вирішені перебором. Наведено достатні умови, за яких локально Парето-оптимальні розв’язки наближених задач апроксимують локально Парето-оптимальні розв’язки вихідної задачі (з деякою точністю).
Direct methods for continuous vector optimization not reducible to a scalar optimization are studied. Practical implementations of these methods assume sampling the feasible region, approximation of the objective functions and solving a sequence of discrete vector optimization problems. With small dimensions of the solution space discrete problem can be solved by enumeration. We give sufficient conditions under which Pareto optimal solutions of approximate problems approximate the Pareto optimal solution of the original problem (with some accuracy).
|
| first_indexed | 2025-11-24T10:12:49Z |
| format | Article |
| fulltext |
52 Теорія оптимальних рішень. 2015
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Исследованы условия сходимости
прямых методов непрерывной
векторной оптимизации, которые
не сводятся к скалярной оптими-
зации. Практические варианты
этих методов предполагают дис-
кретизацию допустимой области,
аппроксимацию целевых функций
и решение последовательности
дискретных задач векторной оп-
тимизации. При небольших раз-
мерностях пространства реше-
ний дискретные задачи могут
быть решены перебором. Приве-
дены достаточные условия, при
которых локально Парето-опти-
мальные решения приближенных
задач аппроксимируют локально
Парето-оптимальные решения
ис-ходной задачи (с некоторой
точностью).
Б.В. Норкин, 2015
УДК 519.8; 368; 65.0
Б.В. НОРКИН
О СХОДИМОСТИ ЛОКАЛЬНОГО
ПАРЕТО-ОПТИМАЛЬНОГО ПОИСКА
Введение. Задача векторной оптимизации
состоит в нахождении части или всего мно-
жества Парето-оптимальных решений. В ра-
боте изучаются условия сходимости прямых
методов векторной оптимизации, не сводя-
щихся к скалярной оптимизации, а порож-
дающих последовательность недоминируе-
мых приближений к Парето-оптимальному
множеству задачи. Общая задача векторной
оптимизации имеет вид
1 R
( ) { ( ),..., ( )} max ,nm x X
F x F x F x
(1)
где функции ( ), 1,..., ,if x i m предполагают-
ся непрерывными на счетно компактном
множестве X . Задача состоит (а) в нахожде-
нии отдельных элементов или (б) всего мно-
жества слабо Парето-оптимальных точек
* ,X X таких, что для любого *x X не
существует x X , ( ) ( )F x F x (покомпо-
нентно). Задачи векторной оптимизации
имеют огромное поле приложений и суще-
ствует большое число подходов к их реше-
нию [1 – 7]. Наиболее известные из них со-
стоят максимизации одной из функций iF
при ограничениях на значения других функ-
ций или в свертке критериев iF в один с по-
мощью линейной или нелинейной функции
полезности и решении получающихся задач
оптимизации методами нелинейного про-
граммирования [1]. Однако для невыпуклых
функций iF таким путем, вообще говоря,
нельзя
получить все Парето-оптимальные решения.
Поэтому получили развитие и другие (пря-
мые) подходы к решению задачи (1), не сво-
дящиеся к оптимизации скалярного критерия,
например, методы дискретного поиска [2],
О СХОДИМОСТИ ЛОКАЛЬНОГО ПАРЕТО-ОРТИМАЛЬНОГО ПОИСКА
Теорія оптимальних рішень. 2015 53
эволюционного программирования [3], методы покрытий [4], дифференциально-
го локального спуска [5 – 7]. Прямые методы [2, 3] часто являются вариантами
управляемого итерационного случайного поиска. В них на каждой итерации
формируется приближенное дискретное решение * ,NX состоящее из конечного
числа точек; затем на основе информации *( )NF X о значениях целевых функций
в точках *
NX некоторым образом генерируется новое поколение точек NY и из
множества *( , )N N
NX X Y отбирается новое дискретное приближенное реше-
ние *
1,NX например, недоминируемых точек и т. д. Установление условий схо-
димости алгоритмов эволюционного программирования к множеству Парето-
оптимальных точек представляет определенную проблему и является предметом
активных исследований [8, 9]. Даже сходимость простейших алгоритмов этого
типа исследована только для дискретных допустимых множеств X [9]. Настоя-
щая работа посвящена исследованию условий сходимости методов этого типа.
Уточнение постановки задачи. На практике постановка задачи векторной
оптимизации может быть более сложной, чем (1). Например, в случае задачи
стохастической векторной оптимизации функции F имеют вид математических
ожиданий, ( ) E ( , )F x f x , где случайная переменная задана на некотором
вероятностном пространстве , , P , E обозначает математическое ожида-
ние (интеграл) по мере P [10, 11]. Обычно, в практических задачах математиче-
ские ожидания невозможно вычислить аналитически, поэтому их приближенно
оценивают численно с помощью квадратур или методом Монте-Карло [11].
В качестве компонент векторной целевой функции ( )F x в (1) могут выступать
квантили случайных величин ( , )iF x , для вычисления которых существуют
разнообразные приближенные методы. Тогда вместо задачи (1) приходится рас-
сматривать последовательность приближенных задач векторной оптимизации
вида
1 R
( ) { ( ),..., ( )} max ,N n
N N N
m x X
F x F x F x
1,2,...N , (2)
где множество допустимых решений ,NX вообще говоря, также может менять-
ся от задачи к задаче, например, множество NX может быть дискретной
аппроксимацией исходного допустимого множества X [2]. В последнем случае
аппроксимирующие функции 1 ( ),..., ( )N N
mF x F x могут быть определены только
на дискретном множестве .NX Очевидно, для конечного дискретного допусти-
мого множества NX задача (2) поиска Парето-оптимальных точек *
NX легко
разрешима. Проблема состоит в том, чтобы установить условия, при которых
множество
*
NX приближает множество решений *X .
Б.В. НОРКИН
54 Теорія оптимальних рішень. 2015
Сходимость аппроксимаций задач векторной оптимизации. Как отмеча-
ется в [2] вопрос о сходимости дискретной аппроксимации задачи (1) является
непростым. В нашей постановке (2) он осложняется еще и тем, что аппроксими-
руются не только допустимое множество, но и целевые функции. Для формули-
ровки результата о сходимости решений приближенных задач (2) к решению
исходной задачи (1) нам понадобятся некоторые определения.
Определение 1 [12, Sec. 4A]. Для последовательности множеств
{ , 1,2,...}NZ X N определим такие предельные множества:
limsup { : , lim }
k k kN kN N N NZ z z Z z z ,
liminf { : , lim }N NN NN NZ z z Z z z ,
lim liminf limsupN i N N NNZ Z Z .
Определение 2 ( -оптимальные решения задач (1) и (2)). Множество
*( )X называется -оптимальным решением задачи (1), если для любого
* *( )x X не существует ,x X такой, что *( ) ( ) .F x F x Аналогично, мно-
жество * ( )NX называется -оптимальным решением задачи (2), если для любо-
го * * ( )Nx X не существует ,Nx X такой, что *( ) ( ) .N NF x F x
Сделаем следующие предположения о связи задач (1) и (2):
П1. Для любой последовательности N NX x x выполнено
( ) ( )N NF x F x , N .
П2. Последовательность допустимых множеств { , 1,2,...}NX N задачи (2)
удовлетворяет условиям: NX X и для некоторого Rm выполнено
*( ) liminf ,N
NX X т. е. к каждой точке *( )x X сходится некоторая по-
следовательность допустимых точек .N Nx X
Теорема 1 ([14], о сходимости решений приближенных задач (2) к решени-
ям исходной задачи (1)). Предположим, что вектор-функция ( )F x непрерывна
на компактном множестве ,X выполнены условия П1-П2, и lim 0.N
N
Тогда для любого , 0 , выполнено
* * * * *( ) liminf ( ) limsup ( ) ( ).N N
N N N NX X X X X
Замечание 1. В работе [13] аналогичное теореме 1 утверждение доказано
при предположении lim .N
N X X Если множество NX является дискрет-
ной аппроксимацией допустимого множества ,X то условие П2 показывает, что
для справедливости теоремы о сходимости решений * ( )N
NX к *( )X достаточ-
но улучшать аппроксимацию допустимого множества только в окрестности
приближенно локально Парето-оптимальных точек *( ).X
О СХОДИМОСТИ ЛОКАЛЬНОГО ПАРЕТО-ОРТИМАЛЬНОГО ПОИСКА
Теорія оптимальних рішень. 2015 55
Сходимость прямого локального Парето-оптимального поиска. Локаль-
ный Парето-оптимальный поиск состоит в решении последовательности связан-
ных задач (2) с некоторым образом связанными целевыми вектор-функциями
( )NF и определенным образом построенными допустимыми множествами
NX . В частности, все целевые функции ( )NF могут быть одинаковыми.
Определение 3. Под окрестным отображением : 2 2X XV будем пони-
мать произвольное монотонное не убывающее отображение, непрерывное отно-
сительно сходимости множеств, т. е. для которого из limN NZ Z следует
lim ( ) ( )N NV Z V Z , и такое, что ( )X V X для любого 2XX .
Определение 4 (сходимость окрестных отображений). Последовательность
окрестных отображений NV будем называть сходящейся к некоторому окрест-
ному отображению ,V если для любой последовательности сходящихся мно-
жеств NZ Z выполнено lim ( ) ( )N N NV Z V Z .
Пусть NV – некоторая последовательность окрестных отображений, схо-
дящихся к окрестному отображению .V Пусть последовательные задачи (2) свя-
заны так, что
1,N NF F
*
1( )N
N NX V x , где
* * 1
1 1( )N
N Nx X
такова, что
1 * 1 * 1
1 2( ) ( ) ,N N N
N NF x F x
если
* * 1
2 1( )N
N Nx X
, и NF – новая целевая
функция, а *
1Nx X – любое, в противном случае;
*
1x – произвольная началь-
ная точка из допустимого множества X исходной задачи (1).
Суть этого прямого алгоритма локального Парето-оптимального поиска со-
стоит в том, что он стартует из произвольной начальной точки
*
1x X и с неиз-
менной целевой функцией 1F доходит до первой 1N -недоминируемой точки
1
1 1
* *
1 ( ),N
N Nx X затем стартует из новой произвольной начальной точки
1
*
Nx
(или, в частности, продолжает оптимизацию из
1
*
1Nx ) и снова при новой неиз-
менной функции 1NF ( 1 1N ) находит 2N -недоминируемую точку
2
2 2
* *
1 ( )N
N Nx X , и т. д.
Теорема 2 (о сходимости локального Парето-оптимального поиска).
Предположим, что функция ( )F x непрерывна на секвенциально компактном
множестве ,X последовательность полунепрерывных сверху вектор-функций
{ }NF равномерно сходится к целевой функции F на ,X а окрестные отобра-
жения NV сходятся к отображению V на 2 ,X
lim 0.N
N Тогда
существует бесконечная подпоследовательность решений
*{ ( )},k
k
N
NX такая,
Б.В. НОРКИН
56 Теорія оптимальних рішень. 2015
что
* *
1 ( ),k
k k
N
N Nx X и любая предельная точка x такой подпоследовательно-
сти *
1{ }
kNx является -оптимальной (по Парето) в своей ( )V x окрестности,
т. е. не существует другой точки ( ),z V x такой, что ( ) ( ) .F z F x
Доказательство. Предположим противное, что не существует бесконечной
подпоследовательности
* *
1{ ( )},k
k k
N
N Nx X тогда
* *
1 ( )N
N Nx X для всех
достаточно больших .N N Из построения алгоритма следует, что тогда
* 1 * 1 * 1
1( ) ( ) ( )N N N N
N N NF x F x F x
для всех ,N N что невозможно
в силу ограниченности ( )NF на X и условия lim 0.N
N Пусть
*
1{ },
kNx x такова, что
* *
1{ ( ), k 1,2,...}.k
k k
N
N Nx X Предположим
противное, что x не является -оптимальной на множестве ( )V x . Тогда
найдется ( ),z V x такая, что ( ) ( ) .F z F x Так как *
1kNx x и
*
1( ) ( )
k kN NV x V x , то существуют *
1( )
k k kN N NV x z z . Таким образом,
1 1*
1( ) lim ( ) ( ) lim ( ( ) )k k k
k k
N N N
k N k NF z F z F x F x
и
1 1*
1( ) ( ) ,k k k
k k
N N N
N NF z F x
*
1( ) ,k
k k k
N
N N Nz V x X для всех достаточно
больших ,k т. е.
* *
1 ( ).k
k k
N
N Nx X Полученное противоречие доказывает теорему.
Выводы. В работе исследованы условия сходимости прямых методов век-
торной оптимизации, не сводящихся к скалярной оптимизации. Практические
варианты этих методов предполагают дискретизацию допустимой области, ап-
проксимацию целевых функций и решение последовательности дискретных за-
дач векторной оптимизации. Необходимость аппроксимаций целевых функций
возникает в тех случаях, когда невозможно точно вычислить их значения за ко-
нечное (разумное) время и, поэтому приходится довольствоваться их аппрокси-
мациями. Эта ситуация типична для задач стохастической многокритериальной
оптимизации. Дискретная аппроксимация допустимого множества мотивируется
тем, что получающаяся дискретная задача векторной оптимизации, в принципе,
может быть точно решена перебором за конечное число шагов. Дискретная сет-
ка может быть регулярной, случайной или другой квазирегулярной, заполняю-
щей допустимую область. Подобный подход к векторной оптимизации широко
применяется в инженерных приложениях. В случае локальной итерационной
оптимизации поиск лучших точек происходит в некоторой, возможно, дискрет-
ной окрестности текущей точки и продолжается до получения недоминируемых
(с некоторой точностью) точек.
О СХОДИМОСТИ ЛОКАЛЬНОГО ПАРЕТО-ОРТИМАЛЬНОГО ПОИСКА
Теорія оптимальних рішень. 2015 57
Б.В. Норкін
ПРО ЗБІЖНІСТЬ ПРЯМИХ МЕТОДІВ НЕПЕРЕРВНОЇ ВЕКТОРНОЇ ОПТИМІЗАЦІЇ
Досліджено умови збіжності прямих методів неперервної векторної оптимізації, які не зво-
дяться до скалярної оптимізації. Практичні варіанти цих методів припускають дискретизацію
допустимої області, апроксимацію цільових функцій і розв’язання послідовності дискретних
задач векторної оптимізації. При невеликій вимірності простору рішень дискретні задачі мо-
жуть бути вирішені перебором. Наведено достатні умови, за яких локально Парето-
оптимальні розв’язки наближених задач апроксимують локально Парето-оптимальні
розв’язки вихідної задачі (з деякою точністю).
B.V. Norkin
ON CONVERGENCE OF DIRECT METHODS FOR CONTINUOUS VECTOR OPTIMIZATION
Direct methods for continuous vector optimization not reducible to a scalar optimization are stud-
ied. Practical implementations of these methods assume sampling the feasible region, approximation
of the objective functions and solving a sequence of discrete vector optimization problems. With
small dimensions of the solution space discrete problem can be solved by enumeration. We give
sufficient conditions under which Pareto optimal solutions of approximate problems approximate
the Pareto optimal solution of the original problem (with some accuracy).
Miettinen K. Nonlinear multiobjective optimization. – Boston/London/Dordrecht: Kluwer Academic Publishers, 1999. – 298 p.
1. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими
критериями. 2-е изд., перераб. и доп. – М.: Дрофа, 2006. – 176 с.
2. Deb K. Multi-objective optimization using evolutionary algorithms. – Chichester: John Willey
& Sons, 2001. – 497 p.
3. Евтушенко Ю.Г., Посыпкин М.А. Метод неравномерных покрытий для решения задач
многокритериальной оптимизации с гарантированной точностью // Вычислительная ма-
тематика и математическая физика. – 2013. – 53, № 2. – С. 209 – 224.
4. Fliege J., Svatier B.F. Steepest descent methods for multicriteria optimization // Math. Methods
Oper. Res. – 2000. – 51, N 3. – P. 479 – 494.
5. Ляшко С.I., Семенов В.В. Алгоритми векторної оптимiзацiї лiнiйних систем з узагаль-
неним керуванням // Доп. НАН України. – 2010. – № 4. – С. 35 – 41.
6. Семенов В.В. Методы градиентного типа для решения задач векторной оптимизации //
Теорія оптимальних рішень. – К.: Інститут кібернетики імені В.М. Глушкова
НАН України, 2010. – С. 145 – 152.
7. Li Z., Li Zhe., Rudolph G. On the convergence properties of quantum-inspired multi-objective
evolutionary algorithms. In: Advanced intelligent computing theories and applications. With
aspects of contemporary intelligent computing techniques. – Berlin, Heidelberg: Springer,
2007. – P. 245 – 255.
8. Laumanns M., Zenklusen R. Stochastic convergence of random search methods to fixed size
Pareto front approximations // European J. Oper. Res. – 2011. – 213. – P. 414 – 421.
9. Ben Abdelaziz F. Solution approaches for the multiobjective stochastic programming // Euro-
pean J. Oper. Res. – 2012. – 216. – P. 1 – 16.
10. Gutjahr W., Pichler A. Stochastic multi-objective optimization: a survey on non-scalarizing
methods // Ann. Oper. Res. – 2013. – P. 1 – 25.
11. Rockafellar R.T., Wets R.J-B. Variational Analysis. – Berlin: Springer, 1998. – 734 p.
12. Norkin B.V. Sample approximations of multiobjective stochastic optimization problems //
www://optimization-online.org. Electronic preprint. – November 2014. – Access:
http://www.optimization-online.org/DB_HTML/2014/11/4655.html
13. Norkin B.V. On the approximation of vector optimization problems // Кибернетика и вычис-
лительная техника. – Вып. 179. – К.: Академперіодика, 2015.
Получено 15.04.2015
http://www.optimization-online.org/DB_HTML/2014/11/4655.html
|
| id | nasplib_isofts_kiev_ua-123456789-112397 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-11-24T10:12:49Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Норкин, Б.В. 2017-01-20T21:26:18Z 2017-01-20T21:26:18Z 2015 О сходимости локально Парето-оптимального поиска / Б.В. Норкин // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 52-57. — Бібліогр.: 13 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/112397 519.8; 368; 65.0 Исследованы условия сходимости прямых методов непрерывной векторной оптимизации, которые не сводятся к скалярной оптимизации. Практические варианты этих методов предполагают дискретизацию допустимой области, аппроксимацию целевых функций и решение последовательности дискретных задач векторной оптимизации. При небольших размерностях пространства решений дискретные задачи могут быть решены перебором. Приведены достаточные условия, при которых локально Парето-оптимальные решения приближенных задач аппроксимируют локально Парето-оптимальные решения исходной задачи (с некоторой точностью). Досліджено умови збіжності прямих методів неперервної векторної оптимізації, які не зводяться до скалярної оптимізації. Практичні варіанти цих методів припускають дискретизацію допустимої області, апроксимацію цільових функцій і розв’язання послідовності дискретних задач векторної оптимізації. При невеликій вимірності простору рішень дискретні задачі можуть бути вирішені перебором. Наведено достатні умови, за яких локально Парето-оптимальні розв’язки наближених задач апроксимують локально Парето-оптимальні розв’язки вихідної задачі (з деякою точністю). Direct methods for continuous vector optimization not reducible to a scalar optimization are studied. Practical implementations of these methods assume sampling the feasible region, approximation of the objective functions and solving a sequence of discrete vector optimization problems. With small dimensions of the solution space discrete problem can be solved by enumeration. We give sufficient conditions under which Pareto optimal solutions of approximate problems approximate the Pareto optimal solution of the original problem (with some accuracy). ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень О сходимости локально Парето-оптимального поиска Про збіжність прямих методів неперервної векторної оптимізації On convergence of direct methods for continuous vector optimization Article published earlier |
| spellingShingle | О сходимости локально Парето-оптимального поиска Норкин, Б.В. |
| title | О сходимости локально Парето-оптимального поиска |
| title_alt | Про збіжність прямих методів неперервної векторної оптимізації On convergence of direct methods for continuous vector optimization |
| title_full | О сходимости локально Парето-оптимального поиска |
| title_fullStr | О сходимости локально Парето-оптимального поиска |
| title_full_unstemmed | О сходимости локально Парето-оптимального поиска |
| title_short | О сходимости локально Парето-оптимального поиска |
| title_sort | о сходимости локально парето-оптимального поиска |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/112397 |
| work_keys_str_mv | AT norkinbv oshodimostilokalʹnoparetooptimalʹnogopoiska AT norkinbv prozbížnístʹprâmihmetodívneperervnoívektornoíoptimízacíí AT norkinbv onconvergenceofdirectmethodsforcontinuousvectoroptimization |