Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв

Серед векторних задач лексикографічні задачі утворюють досить широкий і важливий клас задач оптимізації. Лексикографічне впорядкування використовується для встановлення правил субординації й пріоритету. Тому значна кількість задач, в тому числі задачі оптимізації складних систем, задачі стохастичног...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2020
Hauptverfasser:	Семенова, Н.В., Ломага, М.М., Семенов, В.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Видавничий дім "Академперіодика" НАН України 2020
Schriftenreihe:	Доповіді НАН України
Schlagworte:	Інформатика та кібернетика
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/174269
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв / Н.В. Семенова, М.М. Ломага, В.В. Семенов // Доповіді Національної академії наук України. — 2020. — № 12. — С. 19-27. — Бібліогр.: 14 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-174269
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1742692025-02-23T18:20:40Z Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв Existence of solutions and solving method of lexicographic problem of convex optimization with the linear criteria functions Семенова, Н.В. Ломага, М.М. Семенов, В.В. Інформатика та кібернетика Серед векторних задач лексикографічні задачі утворюють досить широкий і важливий клас задач оптимізації. Лексикографічне впорядкування використовується для встановлення правил субординації й пріоритету. Тому значна кількість задач, в тому числі задачі оптимізації складних систем, задачі стохастичного програмування в умовах ризику, задачі динамічного характеру та ін., можна подати у вигляді лексикографічних задач оптимізації. Встановлено умови існування розв'язків багатокритеріальних задач лексикографічної оптимізації з необмеженою множиною допустимих розв'язкiв на основі використання властивостей рецесивного конусу опуклої допустимої множини, конусу, що лексикографічно впорядковує її вiдносно критерiїв оптимiзацiї. Отримані умови можна успішно використовувати при розробці алгоритмів пошуку оптимальних розв'язків зазначених задач лексикографічної оптимізації. На основі ідей методів лінеаризації та відтинаючих площин Келлі побудовано та обґрунтовано метод знаходження лексикографічно оптимальних розв'язків опуклих лексикографічних задач з лінійними функціями критеріїв. Among vector problems, the lexicographic ones constitute a broad significant class of problems of optimization. Lexicographic ordering is applied to establish rules of subordination and priority. Hence, a lot of problems including the ones of complex system optimization, of stochastic programming under a risk, of the dynamic character, etc. may be presented in the form of lexicographic problems of optimization. We have revealed the conditions of existence of solutions of multicriteria of lexicographic optimization problems with an unbounded set of feasible solutions on the basis of applying the properties of a recession cone of a con vex feasible set, the cone which puts it in order lexicographically with respect to optimization criteria. The obtained conditions may be successfully used while developing algorithms for finding the optimal solutions of the mentioned problems of lexicographic optimization. A method of finding the optimal solutions of convex lexicographic problems with the linear functions of criteria is built and grounded on the basis of ideas of the method of linearization and the Kelley cutting plane method. 2020 Article Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв / Н.В. Семенова, М.М. Ломага, В.В. Семенов // Доповіді Національної академії наук України. — 2020. — № 12. — С. 19-27. — Бібліогр.: 14 назв. — укр. 1025-6415 DOI: doi.org/10.15407/dopovidi2020.12.019 https://nasplib.isofts.kiev.ua/handle/123456789/174269 519.8 uk Доповіді НАН України application/pdf Видавничий дім "Академперіодика" НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Інформатика та кібернетика Інформатика та кібернетика
spellingShingle	Інформатика та кібернетика Інформатика та кібернетика Семенова, Н.В. Ломага, М.М. Семенов, В.В. Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв Доповіді НАН України
description	Серед векторних задач лексикографічні задачі утворюють досить широкий і важливий клас задач оптимізації. Лексикографічне впорядкування використовується для встановлення правил субординації й пріоритету. Тому значна кількість задач, в тому числі задачі оптимізації складних систем, задачі стохастичного програмування в умовах ризику, задачі динамічного характеру та ін., можна подати у вигляді лексикографічних задач оптимізації. Встановлено умови існування розв'язків багатокритеріальних задач лексикографічної оптимізації з необмеженою множиною допустимих розв'язкiв на основі використання властивостей рецесивного конусу опуклої допустимої множини, конусу, що лексикографічно впорядковує її вiдносно критерiїв оптимiзацiї. Отримані умови можна успішно використовувати при розробці алгоритмів пошуку оптимальних розв'язків зазначених задач лексикографічної оптимізації. На основі ідей методів лінеаризації та відтинаючих площин Келлі побудовано та обґрунтовано метод знаходження лексикографічно оптимальних розв'язків опуклих лексикографічних задач з лінійними функціями критеріїв.
format	Article
author	Семенова, Н.В. Ломага, М.М. Семенов, В.В.
author_facet	Семенова, Н.В. Ломага, М.М. Семенов, В.В.
author_sort	Семенова, Н.В.
title	Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв
title_short	Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв
title_full	Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв
title_fullStr	Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв
title_full_unstemmed	Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв
title_sort	існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв
publisher	Видавничий дім "Академперіодика" НАН України
publishDate	2020
topic_facet	Інформатика та кібернетика
url	https://nasplib.isofts.kiev.ua/handle/123456789/174269
citation_txt	Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв / Н.В. Семенова, М.М. Ломага, В.В. Семенов // Доповіді Національної академії наук України. — 2020. — № 12. — С. 19-27. — Бібліогр.: 14 назв. — укр.
series	Доповіді НАН України
work_keys_str_mv	AT semenovanv ísnuvannârozvâzkívtametodrozvâzannâleksikografíčnoízadačíopukloíoptimízacíízlíníjnimifunkcíâmikriteríív AT lomagamm ísnuvannârozvâzkívtametodrozvâzannâleksikografíčnoízadačíopukloíoptimízacíízlíníjnimifunkcíâmikriteríív AT semenovvv ísnuvannârozvâzkívtametodrozvâzannâleksikografíčnoízadačíopukloíoptimízacíízlíníjnimifunkcíâmikriteríív AT semenovanv existenceofsolutionsandsolvingmethodoflexicographicproblemofconvexoptimizationwiththelinearcriteriafunctions AT lomagamm existenceofsolutionsandsolvingmethodoflexicographicproblemofconvexoptimizationwiththelinearcriteriafunctions AT semenovvv existenceofsolutionsandsolvingmethodoflexicographicproblemofconvexoptimizationwiththelinearcriteriafunctions
first_indexed	2025-11-24T09:23:22Z
last_indexed	2025-11-24T09:23:22Z
_version_	1849663110478036992
fulltext	19 ОПОВІДІ НАЦІОНАЛЬНОЇ АКАДЕМІЇ НАУК УКРАЇНИ Ц и т у в а н н я: Семенова Н.В., Ломага М.М., Семенов В.В. Існування розв’язків та метод розв’язання лек- сикографічної задачі опуклої оптимізації з лінійними функціями критеріїв. Допов. Нац. акад. наук Укр. 2020. № 12. С. 19—27. https://doi.org/10.15407/dopovidi2020.12.019 Лексикографічний підхід до розв’язання багатокритеріальних задач полягає в строгому ранжируванні критеріїв за відносною важливістю і дозволяє домогтися оптимізації більш важливого критерію за рахунок будь-яких втрат за всіма іншими менш важливими кри- те ріями. Найчастіше такі багатокритеріальні задачі зустрічаються при послідовному вве- денні додаткових критеріїв у звичайні скалярні задачі оптимізації, які можуть мати не єди- ний розв’язок. Задачі лексикографічної оптимізації виникають також при моделюванні ієрархічних структур, у стохастичному програмуванні, при розв’язанні деяких задач дина- мічного характеру тощо [1—3]. ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 12: 19—27 https://doi.org/10.15407/dopovidi2020.12.019 УДК 519.8 Н.В. Семенова 1, М.М. Ломага 2, В.В. Семенов 1 1 Інститут кібернетики ім. В.М. Глушкова НАН України, Київ 2 ДВНЗ “Ужгородський національний унiверситет” E-mail: nvsemenova.@meta.ua, marija_lomaga@ukr.net, semenov.jr@gmail.com Існування розв’язків та метод розв’язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв Представлено академіком НАН України І.В.Сергієнком Серед векторних задач лексикографічні задачі утворюють досить широкий і важливий клас задач оптимі- з ації. Лексикографічне впорядкування використовується для встановлення правил субординації й пріори- те ту. Тому значна кількість задач, в тому числі задачі оптимізації складних систем, задачі стохастичного програмування в умовах ризику, задачі динамічного характеру та ін., можна подати у вигляді лексикогра- фічних задач оптимізації. Встановлено умови існування розв’язків багатокритеріальних задач лексикогра- фічної оптимізації з необмеженою множиною допустимих розв’язкiв на основі використання властивос- тей рецесивного конусу опуклої допустимої множини, конусу, що лексикографічно впорядковує її вiдносно критерiїв оптимiзацiї. Отримані умови можна успішно використовувати при розробці алгоритмів пошуку оптимальних розв’язків зазначених задач лексикографічної оптимізації. На основі ідей методів лінеариза- ції та відтинаючих площин Келлі побудовано та обґрунтовано метод знаходження лексикографічно опти- мальних розв’язків опуклих лексикографічних задач з лінійними функціями критеріїв. Ключові слова: лексикографічна оптимізація, векторний критерій, існування розв’язків, умови опти маль- ності, метод лінеаризації, метод відтинаючих площин Келлі. ІНФОРМАТИКА ТА КІБЕРНЕТИКА 20 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2020. № 12 Н.В. Семенова, М.М. Ломага, В.В. Семенов У лексикографічному вигляді можна подати також векторні задачі динамічного ха- рактеру, які полягають у послідовному досягненні часткових цілей. У лексикографічній постановці формулюються задачі оптимізації складних систем, які полягають із взаємо- залежних підсистем, що відносяться до різних ієрархічних рівнів. До можливих методів розв’язання таких задач відноситься використання схеми ска- ляризації або згортки векторного критерію для одноетапного розв’язання [1—6]. У [2] для відшукання лексикографічного оптимуму лінійних багатокритеріальних задач оптиміза- ції було запропоновано використання симплекс-методу. У [4, 5] задача лексикографічної оптимізації з лінійними обмеженнями зводиться до послідовності лінійних лексикогра фіч- них задач шляхом апроксимації функцій критеріїв. У [6] представлено алгоритм, що доз- воляє звести розв’язок вхідної задачі лексикографічної оптимізації за допомогою апрок- симації допустимої множини до розв’язання послідовності лексикографічних задач ліній- ного програмування. В однокритеріальній оптимізації ряд алгоритмів пошуку екстремуму побудовано на використанні апарату теорії двоїстості. Це питання є цікавим і для задач багатокритеріальної оптимізації. У статті [7] досліджуються опуклі квадратичні задачі лек сикографічної оптимізації на множині, заданій системою лінійних нерівностей, і пи тан- ня побудови двоїстих до них задач. Двоїсті задачі до вхідної будуються за допомогою ві- доб раження Лагранжа, де множники Лагранжа — це векторні змінні, множиною значень кожної з яких є множина векторів простору, розмірність якого рівна кількості часткових кри теріїв з введеним на ньому лексикографічним порядком. Метою досліджень, представлених в даній статті, є встановлення умов існування оп- тимальних розв’язків багатокритеріальних задач лексикографічної оптимізації з необме- женою допустимою множиною на основі використання властивостей рецесивного конуса опуклої допустимої множини [8], конуса, що лексикографічно її впорядковує вiдносно кри- терiїв оптимізації [2], а також розробка та обґрунтування методу розв’язання лекси ко- графічної задачі опуклої оптимізації з лінійними функціями критеріїв. Постановка задачі. У критеріальному просторі R вводиться бінарне відношення лексикографічного порядку векторів 1 2( , , , )z z z z= …  і 1 2( , , , )z z z z′ ′ ′ ′= …  таке, що 1( ) ( : ( , ))L j j j i iz z z z j N i N z z z z−′ ′ ′ ′⇔ = ∨ ∃ ∈ ∀ ∈ > = , де 0N =∅ . Розглянемо задачу лексикографічної оптимізації наступного вигляду: ( , ) : max { ( ) }L LZ F X F x x X∈ , де 1( ) ( ( ), , ( ))F x f x f x= …  , 2 , ( ) ,k kf x c x= 〈 〉, n kc R∈ , {1, 2, , }k N∈ =   , { ( ) 0,n iX x R g x= ∈  0, }mx i N∈ , ( ),i mg x i N∈ , — опуклі функції. В задачі лексикографічної оптимізації част- кові критерії впорядковані за важливістю. При цьому виникає поняття лексикографічно- го оптимуму. Означення 1. Вектор x лексикографічно переважає вектор x′, коли виконується одна з  умов: 1) 1 1( ) ( )f x f x′> ; 2) 1 1( ) ( )f x f x′= , але 2 2( ) ( )f x f x′> ; ........................................  ) ( ) ( ), 1, , 1j jf x f x j′= = −  , але ( ) ( )f x f x′>  . 21ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 12 Існування розв’язків та метод розв’язання лексикографічної задачі опуклої оптимізації... Означення 2. Вектор x еквівалентний вектору x ′, коли за кожним критерієм вектори x та x′мають однакові оцінки, при цьому x x′≠ . Під розв’язанням задачі LZ F X( , ) будемо розуміти пошук елементів множини ( , )L F X лексикографічно оптимальних розв’язків, яку задамо в такий спосіб: ( , ) { \| ( , , ) }L F X x F Xx X= υ∈ =∅ , де ( , , ) { \| : ( ) ( ) min { : ( ) ( )}}j j i ix F X x X j N f x f x j i N f x f x′ ′ ′υ = ∈ ∃ ∈ > ∧ = ∈ ≠  . Безпосередньо з означення лексикографічно оптимальних розв’язків випливає, що множину ( , )L F X можна задати за допомогою рекурентних співвідношень Таким чином, 1Arg max ( )) {( , ( , ),:i iiL xF X L F Xf Nx i−∈= ∈  , (1) де }Arg m x{a ⋅ — множина всіх оптимальних розв’язків відповідної задачі максимізації, 0( , )L F X X= , ( , ) ( , )L F X L F X= . Із співвідношень (1) випливає, справедливість включень послідовності множин 1 2( , ) ( , ) ( , ) ( , )X L F X L F X L F X L F X⊇ ⊇ ⊇ ⊇ = , тобто кожен наступний частковий критерій звужує множину розв’язків, отриманих з ураху- ванням всіх попередніх часткових критеріїв. Як відомо [1, 2], множина ( , )L F X може бути визначена, як результат розв’язання по- слідовності  скалярних задач ( , ), iLZ F X i N∈  , опуклого програмування з лінійними цільовими функціями. Отже, задачу ( , )LZ F X можна розглядати як задачу послідовної оптимізації. Згідно з [2] введемо означення. Означення 3. Вектор z R∈  називається лексикографічно додатним, якщо перший йо- го ненульовий компонент у порядку зростання індексів компонент є додатним. Будемо позначати лексикографічну додатність вектора z R∈  як: 0Lz > , тут ( )L> — знак відношення лексикографічно більше. Вектор z R∈  лексикографічно більше вектора ∈ y R Lz y> , якщо вектор ( )z y− лек- сикографічно додатний, ( ) 0Lz y− > . При такому упорядкуванні будь-які два вектори однієї розмірності порівнювані між собою. Отже, для будь-яких векторів ,a b R∈  La b> , тоді й тільки тоді, коли існує 1 i   , таке що i ia b> , і якщо 1i > , то k ka b= , 1, 2, , 1k i= − . Вектор a лексикографічно не мен- ший за вектор b , La b , якщо La b> або a b= , ( )L — знак відношення лексикографічно не менший. Означення 4. Розв’язок x X∗ ∈ задачі ( , )LZ F X будемо називати лексикографічно оп- тимальним, якщо він не гірший будь-якого іншого допустимого розв’язку y X∈ в розу- мінні відношення L , тобто якщо ( ) ( ) 0LF x F y∗ −  . Отже, для довільного x X∈ справедливе твердження ( , ) { \| ( ) ( )}Lx L F X y X F y F x∈ ⇔ ∈ > =∅ . У лексикографічній задачі оптимізації досягають як завгодно малого приросту більш важливого критерію за рахунок будь-яких втрат за іншими менш важливими критеріями. 22 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2020. № 12 Н.В. Семенова, М.М. Ломага, В.В. Семенов З означення лексикографічно оптимального розв’язку задачі ( , )LZ F X випливає спра- ведливість таких властивостей. Властивість 1. Якщо для допустимого розв’язку 0x X∈ й 0\ { }x X x∀ ∈ задачі ( , )LZ F X виконується нерівність f x f x0 1 1( ) ( )< , то 0 ( , )x L F X∈ . Властивість 2. Якщо для допустимого розв’язку x X∈ задачі ( , )LZ F X \ { }x X x′∃ ∈ та- кий, що 1 1( ) ( )f x f x′ > , то ( , )x L F X∉ . Існування лексикографічно оптимальних розв’язків. Існування оптимальних розв’яз- ків на допустимій множині X і структура множини оптимальних розв’язків залежать від властивостей порядку відношення переваги, структури допустимої області X , природи її елементів тощо. Згідно з [2] скінченність множини Х є достатньою умовою існування оп- тимальних розв’язків лексикографічної задачі оптимізації. Також множина ( , )L F X не по- рожня, якщо множина векторних оцінок }( ){ \|Y F x x X= ∈ обмежена і замкнена. Однак у випадку нескінченної допустимої області X множина лексикографічно оптимальних роз- в’язків може бути порожньою. Актуальним є вивчення питань можливості розв’язання лексикографічних задач век- торної оптимізації, у яких множина допустимих розв’язків необмежена і опукла. Необмеженість опуклої множини X означає, що 0 \ {0}Х+ ≠ ∅ , де 0 { \|nХ y R x+ = ∈ ∀ ∈ : , 0}X x ty X t∈ + ∈  — рецесивний конус множини X . Аналіз задачі ( , )LZ F X проведемо з урахуванням властивостей рецесивного конусу 0 Х+ [8] й конусу { 0}L n LK x R Cx= ∈ > , що лексикографічно впорядковує допустиму мно- жину вiдносно критерiїв оптимізації, який назвемо також конусом перспективних [9] лек- сикографічних напрямків задачі ( , )LZ F X , оскільки перехід з будь-якої точки 1 nх R∈ в точ- ку 2 1x x y= + , де y належить конусу LK , приводить до нерівності 2 1 LCx Cx> , тобто до лек- сикографічного зростання значень векторного критерію задачі. Конус LK , є опуклим конусом напрямків лексикографічно додатних векторів і його можна подати у вигляді об’єднання множин, що не перетинаються: 1 2 LK K K K= ∪ ∪ ∪  , де 1 1{ \| 0}nK x R c x= ∈ > , 2 1 2{ \| 0, 0}nK x R c x c x= ∈ = > , ……………………………………………..…, 1 2 1{ \| 0, 0, , 0, 0}nK x R c x c x c x c x−= ∈ = = = >   . Для довільного x X∈ істинне висловлювання [2]: ( , ) ( )Lx L F X x XK+ =∅∩∈ ⇔ . (2) Продовжуючи дослідження питань існування різних видів оптимальних розв’язків векторних задач оптимізації [10—13], розпочаті в роботі [2] для лексикографічних задач, розглянемо необхідні й достатні умови існування лексикографічно оптимальних розв’язків задачі ( , )LZ F X . 23ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 12 Існування розв’язків та метод розв’язання лексикографічної задачі опуклої оптимізації... У випадку опуклої замкненої необмеженої допустимої множини X задачі ( , )LZ F X справедлива теорема. Теорема 1. Необхідною умовою існування лексикографічно оптимальних розв’язків задачі ( , )LZ F X є порожній перетин конуса LK перспективних лексикографічних напрямків і реце- сивного конуса 0 Х+ , тобто 0LK X+∩ =∅ . (3) Доведення. Припустимо від супротивного, що множина ( , )L F X ≠ ∅ , але не викону є- ться умова (3), тобто перетин конусів LK та 0 Х+ не порожній: 0LK X+∩ ≠∅ . Тоді x X∀ ∈ справедливі співвідношення: 0( ) ( )) (0( )L L LK X K X Kx Xx x x+ +∩ ⊇ ∩ ∩ ≠∅+ + + = + . Враховуючи формулу (2), можна зробити висновок, що множина =∅( , )L F X . Але це суперечить умові теореми й тим самим доводить її справедливість. Обернене твердження теореми в загальному випадку не вірне. У монографії [2, c.113] наведено приклад, у якому для допустимої множини X виконана умова (3), але множина її крайніх точок є необмеженою, і в результаті множина =∅( , )L F X . Напрямок лексикографічно додатного вектора будемо називати лексикографічно до- датним напрямком. Справедлива теорема [2, c.113]. Теорема 2. Нехай V — непорожня множина крайніх точок опуклої замкненої множини X . Якщо V — обмежена множина, то множина X має лексикографічний максимум тоді й тільки тоді, коли вона обмежена за всіма лексикографічно додатними напрямками. В наших позначеннях за умов теореми 2 множина ( , )L F X не порожня тоді й тільки тоді, коли виконується умова (3). У випадку опуклої необмеженої і багатогранної множини X справедливий наслідок з теореми 2 [2, c.114]. Наслідок. Замкнена опукла багатогранна множина X має лексикографічний макси- мум тоді й тільки тоді, коли вона обмежена за всіма лексикографічно додатними напрямками. З теореми 1 та наслідку з теореми 2 випливає справедливість наступної теореми. Теорема 3. Нехай допустима множина X задачі ( , )LZ F X є замкненою опуклою ба- га тогранною множиною. Необхідною і достатньою умовою існування лексикографічно оп- тимальних розв’язків цієї задачі є виконання рівності (3). Зазначимо, що умова багатогранності опуклої замкненої необмеженої множини X є іс- тотною для ствердження того факту, що умова (3) є необхідною й достатньою умовою іс- нування лексикографічно оптимальних розв’язків задачі ( , )LZ F X . Метод відтинаючих площин розв’язання лексикографічних задач опуклої оптимі- зації. Знаходження розв’язків задачі ( , )LZ F X можна звести до розв’язання послідовнос- ті лексикографічних задач лінійного програмування ( , ) : max { ( ) }L L p pZ F X F x x X∈ на багатогранній множині { ( ), ( ) 0, 0, , 0,1, , }n i j j i j p mX x R g x x x g x x i N j p= ∈ 〈∇ − 〉 + ∈ =   , 24 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2020. № 12 Н.В. Семенова, М.М. Ломага, В.В. Семенов j nx R+∈ , { 0, }n n i nR x R x i N+ = ∈ ∈ , що містить допустиму область X вхідної задачі. Твердження 1. Справедливе включення pX X⊂ . Доведення. Справедливість включення випливає безпосередньо з побудови багато- гран ної множини pX . Використовуючи властивості опуклої неперервно диференційовної функції ( )h x для будь-яких , nx y R∈ справедлива нерівність ( ), ( ) ( )h x x y h x h x〈∇ − 〉 +  . (4) Згідно (4) для деякого числа 0p > й будь-яких j nx R+∈ , 1, ,j p=  , можна записати ( ), ( ) ( )i j j i j ig x x x g x g x〈∇ − 〉 +  , mi N∈ , 0,1, ,j p=  . (5) Оскільки для довільного x X∈ виконуються нерівності ( ) 0ig x  , mi N∈ , то зі спів- відношення (5) випливає виконання нерівностей ( ), ( ) 0i j j i jg x x x g x〈∇ − 〉 +  , mi N∈ , 0,1, ,j p=  , (6) тобто px X∈ , що й було потрібно довести. Теорема 4. [2, с.190]. Якщо векторна функція F досягає на множині pX лексикогра- фічного максимуму, то серед точок цього максимуму є крайня точка множини pX . З теореми 4 випливає, що для розв’язання задачі ( , )L pZ F X можна використовувати симплексний алгоритм як алгоритм направленого перебору крайніх точок множини pX . Знаходження лексикографічно оптимальних розв’язків задачі ( , )L pZ F X будемо здій- снювати прямим (лексикографічним) пошуком [2], який зводиться до розв’язання задач максимізації ( , ) : max{ ( ) \| },ss p pZ f X f x x X s N∈ ∈  , в кожній з яких максимізується відпо- відна функція лексикографічно упорядкованого векторного критерію. Основна ідея запро- понованого методу полягає в наступному. Якщо оптимальний розв’язок задачі ( , )s pZ f X є недопустимим в задачі ( , )LZ F X , то він виключається з наступного розгляду додаванням нового лінійного обмеження до обмежень задачі ( , )s pZ f X . Таким чином, це обмеження має таку властивість, що відтинає недопустимий розв’язок, а також частину недопустимої об- ласті задачі ( , )LZ F X із усіх наступних розглядів. Усі додані обмеження є правильними від- тинаючими площинами, тобто такими, які не відсікають ніяку частину допустимої області опуклої задачі ( , )LZ F X . Якщо оптимальний розв’язок задачі ( , )s pZ f X належить множині X , і він єдиний оптимальний розв’язок на цій множині, то знайдений розв’язок — лексико- графічно оптимальний для задачі ( , )LZ F X . Позначимо FrB підмножину граничних точок деякої множини B . Алгоритм розв’язання задачі ( , )LZ F X 0-й крок. Нехай 1s = , 0k = . Вибираємо довільну точку Frkx X∈ . Будуємо багатогран- ник { \| ( ), ( ) 0, 0, }n i k k i k k mX x R g x x x g x x i N= ∈ 〈∇ − 〉 + ∈  1. Розв’язуємо задачу max{ ( ) \| }s kf x x X∈ (7) двоїстим симплекс алгоритмом. Нехай 1 arg max{ ( ) }+ = ∈k S kx f x x X . Якщо 1kx X+ ∈ , і 1kx + — єдиний оптимальний розв’язок на допустимій множині X , то 1 arg max{ ( ) \| }k s kx f x x X+ = ∈ , оскільки kX X⊆ . Задача ( , )LZ F X розв’язана. 25ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 12 Існування розв’язків та метод розв’язання лексикографічної задачі опуклої оптимізації... 2. Якщо 1kx X+ ∈ і 1kx + — оптимальний розв’язок на допустимій мно жині X , покладемо 1( )k s sf f x += , 1s s= + , 1 { \| ( ) , 1, 2, , 1}k k i iX x X f x f i s+ = ∈ = = − і пе реходимо до пункту 1. Якщо 1kx X+ ∈ , переходимо до пункту 3. 3. Визначаємо множину 1 1 { \| ( ) 0}i k kI i g x + + = > індексів обмежень задачі ( , )LZ F X , що порушуються в точці 1kx + . Будуємо багатогранник 1kX + , додавши до обме жень, що опису- ють множину kX нерівність 1 1 1( ), ( ) 0i k k i kg x x x g x+ + +〈∇ − 〉 +  , 1 1 1{ \| ( )j k k ki N j I g x + + +∈ = ∈ = 1 1max ( )} k i k i I g x + + ∈ = . Одержуємо нову багатогранну множину 1 1 1 { \| ( ),i k k k kX x X g x x x+ + + = ∈ 〈∇ − 〉 + 1 1( ) 0, }i k kg x i N+ ++ ∈ , переходимо до пункту 1, покла даючи 1k k= + . Для розв’язання допоміжних задач лінійної оптимізації вигляду (7) доцільно застосову- вати двоїстий симплекс-метод [2], який дозволяє використовувати отриманий на попере- дньому кроці розв’язок як базисний для оновленої допустимої області. Збіжність алгоритму встановлює наступна теорема. Теорема 5. Якщо функції ( )ig x , mi N∈ , — опуклі, неперервно диференційовні і задача ( , )LZ F X має скінченний розв’язок, то послідовність точок, породжувана даним алгоритмом, збігається до лексикографічно оптимального розв’язку задачі ( , )LZ F X . Доведення. Якщо задача ( , )LZ F X має скінченний лексикографічно оптимальний роз- в’язок x , то, починаючи з деякого номера 0p послідовність точок { }px міститься в обме- женій множині. Нехай { }kx — підпослідовність послідовності { }px , яка збігається до точки x . Розглянемо підпослідовність { }tx точок, для яких відтинаюча гіперплощина породже- на відносно i-го обмеження ( ), ( ) 0i t t i tg x x x g x〈∇ − 〉 +  , mi N∈ . Якщо на кожній ітерації додавати гіперплощину щодо найсильнішого ( si N∈ ) обмеження, то, починаючи з деякого номера 0k k виконається обмеження ( ) 0i kg x  , тобто kx належить множині допустимих розв’язків або підпослідовність { }tx нескінченна. У випадку, коли підпослідовність { }tx нескінченна, для кожного t t′ > виконується нерівність ( ), ( ) 0i t t t i tg x x x g x′〈∇ − 〉 +  , звідки згідно з нерівністю Коші—Буняковського одержуємо ( ) ( )i t i t t tg x g x x x′∇ − . Враховуючи, що 0t tx x′ − → , ( ) ( )i t ig x g x∗∇ → ∇ з останньої нерівності випливає ( )i tg x → ( ) 0ig x∗→  , тобто x — лексикографічно оптимальний розв’язок задачі ( , )LZ F X . З іншо- го боку, якщо x — оптимальний розв’язок задачі ( , )LZ F X , то на кожній ітерації алгоритму справедлива нерівність ( ) ( )t LF x F x , звідки при граничному переході випливає ( )F x∗  ( )LF x . Отже, x — лексикографічно оптимальний розв’язок задачі ( , )LZ F X . Теорема доведена. Побудова послідовності { }kx в запропонованому методі здійснюється таким чином, що кожна із точок kx є недопустимою точкою для вхідної задачі. Тому процес обчислення не можна зупиняти навіть при досить великих значеннях s , лише тоді, коли одержимо до- пустиму точку. Збіжність до лексикографічно оптимального розв’язку алгоритм гарантує у тому випадку, коли допустима множина опукла. Висновки та перспективи подальших досліджень. Досліджені питання існування та оптимальності розв’язків опуклих задач лексикографічної оптимізації з лінійними функ- ціями критеріїв на необмеженій допустимій множині. На основі проведеного аналізу за- значених задач з урахуванням властивостей конусів перспективних лексикографічних на- прямків та рецесивних напрямків встановлено необхідні та достатні умови існування 26 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2020. № 12 Н.В. Семенова, М.М. Ломага, В.В. Семенов розв’язків досліджених задач. Отримані умови можна успішно використовувати при роз- робці алгоритмів пошуку оптимальних розв’язків зазначених задач лексикографічної опти- мізації. На основі ідей методів лінеаризації та відтинаючих площин Келлі [14] побудовано та обґрунтовано метод знаходження лексикографічно оптимальних розв’язків опуклих лек- сикографічних задач з лінійними критеріями. ЦИТОВАНА ЛІТЕРАТУРА 1. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. Москва: Сов. радио, 1975. 192 с. 2. Червак Ю.Ю. Оптимізація. Непокращуваний вибір. Ужгород: Ужгород. нац. ун-т, 2002. 312 с. 3. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. 2-е изд., испр. и доп. Москва: Физматлит, 2007. 256 с. 4. Ломага М.М., Семенов В.В. Квадратичные задачи лексикографической оптимизации: свойства и ре- шения. Компьютерная математика. 2013. № 2. С. 134—143. 5. Семенова Н.В., Ломага М.М., Семенов В.В. Алгоритм решения многокритериальных задач лексико- графической оптимизации с выпуклыми функциями критериев. Int. J. Inform. Theories and Applications. 21, № 3. 2014. P. 254—262. 6. Ломага М.М. Розв’язання задач лексикографічної оптимізації з лінійними функціями критеріїв на опуклій множині. Наук. вісн. Ужгород. ун-ту. Сер. матем. і інформ. 2015. №2 (27). С. 66—72. 7. Ломага М.М., Семенова Н.В. Квадратичні лексикографічні задачі оптимізації і відображення Лагран- жа. Наук. вісн. Ужгород. ун-ту. Сер. матем. і інформ. 2019. № 2 (35). С. 127—133. 8. Рокафеллар Р. Выпуклый анализ. Москва: Мир, 1973. 470 с. 9. Сергиенко И.В., Козерацкая Л.Н., Лебедева T.T. Исследование устойчивости и параметрический ана- лиз дискретных оптимизационных задач. Киев: Наук. думка, 1995. 171 с. 10. Сергиенко И.В., Козерацкая Л.Н., Кононова А.А. Устойчивость и неограниченность задач векторной оптимизации. Кибернетика и систем. анализ. 1997. № 1. С. 3—10. 11. Сергиенко И.В., Лебедева Т.Т., Семенова Н.В. О существовании решений в задачах векторной оптими- зации. Кибернетика и систем. анализ. 2000. № 6. С. 39—46. 12. Сергiєнко Т.I. Про iснування парето-оптимальних розв’язкiв задачi векторної оптимiзацiї з необме- женою допустимою областю. Допов. Нац. акад. наук Укр. 2015. № 10. С. 27—31. 13. Лебєдєва Т.Т., Семенова Н.В., Сергiєнко Т.I. Умови оптимальностi та розв’язуваностi в задачах лiнiй- ної векторної оптимiзацiї з опуклою допустимою множиною. Допов. Нац. акад. наук Укр. 2003, № 10. С. 80—85. 14. Kelley I.E. The cutting plane method for solving convex programs. SIAM J. 1960. 8. P. 703—712. Надійшло до редакції 03.11.2020 REFERENCES 1. Podinovskyi, V. V. & Gavrilov, V. M. (1975). Optimization on the consistently applied criteria. Moscow: Sov. radio (in Russian). 2. Chervak, Yu. Yu. (2002). Optimization. Unimprovable choice. Uzhgorod: Nat. Univ., Uzhgorod (in Ukrai- nian). 3. Podinovskyi, V. V. & Nogin, V. D. (2007). Pareto-optimal solutions of multicriteria problems. 2-th publ. Moscow: Fizmatlit (in Russian). 4. Lomaha, M. M. & Semenov, V. V. (2013). Quadratic problems of lexicographic optimization: properties and solving. Komp’yuterna mathematica. No 2, pp. 134-143 (in Ukrainian). 5. Semenova, N. V., Lomaha, M. M. & Semenov, V. V. (2014). Algorithm of solving of multicriteria lexico- graphic optimization problems with the convex functions of criteria. Int. J. Inform. Theories and Applica- tions, 21, No. 3, pp. 254-262 (in Russian). 27ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 12 Існування розв’язків та метод розв’язання лексикографічної задачі опуклої оптимізації... 6. Lomaha, M. M. (2015). Solving lexicographic optimization problems with linear functions of criteria on a convex set. Uzhgorod Univ. Scientific Bulletin. Series: Mathematics and Informatics. No. 2 (27), pp. 70-75 (in Ukrainian). 7. Lomaha, M. M. & Semenova, N. V. (2019). Quadratic lexicographic problems of optimization and La- grange’s reflection. Uzhgorod Univ. Scientific Bulletin. Series: Mathematics and Informatics. No. 2 (35), pp. 127-133 (in Ukrainian). 8. Rockafellar, R. (1973) Convex analysis, Moscow: Mir (in Russian). 9. Sergienko, T. I., Kozeratskya, L. N. & Lebedeva, T. T. (1995). Investigation of stability and parametric analysis of discrete optimization problems. Kyiv: Naukova Dumka (in Russian). 171 с. 10. Sergienko, I. V., Kozeratskaya, L. N. & Kononova, A. A. (1997). Stability and unboundedness of vector optimization problems. Cybernetics and Systems Analysis. 33, No. 1, pp. 1-7. 11. Sergienko, I. V., Lebedeva, T. T. & Semenova, N. V. (2000). Existence of solutions in vector optimization problems. Cybernetics and Systems Analysis. 36, No. 6, pp. 823-828. 12. Sergienko, T. I. (2015). Existence of Pareto-optimal solutions to the vector optimization problem with an unbounded feasible set. Dopov. Nac. akad. nauk. Ukr., No. 10, pp. 27-31 (in Ukrainian). 13. Lebedeva, Т. Т., Semenova, N. V. & Sergienko, Т. I. (2003). Optimality and solvability conditions in linear vector optimization problems with convex feasible region. Dopov. Nac. akad. nauk. Ukr., No. 10, pp. 80-85 (in Ukrainian). 14. Kelley, I. E. (1960). The cutting plane method for solving convex programs. SIAM J. 8, pp. 703-712. Received 03.11.2020 N.V. Semenova 1, M.M. Lomaha 2, V.V. Semenov 1 1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv 2 Uzhhorod National University, Uzhhorod E-mail: nvsemenova.meta.ua, marija_lomaga@ukr.net, semenov.jr@gmail.com EXISTENCE OF SOLUTIONS AND SOLVING METHOD OF LEXICOGRAPHIC PROBLEM OF CONVEX OPTIMIZATION WITH THE LINEAR FUNCTIONS OF CRITERIA Among vector problems, the lexicographic ones constitute a broad significant class of problems of optimi- zation. Lexicographic ordering is applied to establish rules of subordination and priority. Hence, a lot of prob- lems including the ones of complex system optimization, of stochastic programming under a risk, of the dynamic character, etc. may be presented in the form of lexicographic problems of optimization. We have revealed the conditions of existence of solutions of multicriteria of lexicographic optimization problems with an unbounded set of feasible solutions on the basis of applying the properties of a recession cone of a con vex feasible set, the cone which puts it in order lexicographically with respect to optimization criteria. The obtained conditions may be successfully used while developing algorithms for finding the optimal solutions of the mentioned problems of lexicographic optimization. A method of finding the optimal solutions of convex lexico graphic problems with the linear functions of criteria is built and grounded on the basis of ideas of the method of linearization and the Kelley cutting plane method. Keywords: lexicographic optimization, vector criterion, existence of solutions, method of linearization, cutting plane method.

Існування розв'язків та метод розв'язання лексикографічної задачі опуклої оптимізації з лінійними функціями критеріїв

Institution

Ähnliche Einträge