Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации

Предложен алгоритм решения задач недифференцируемой оптимизации семейства методов отделяющих плоскостей с дополнительными отсечениями, порождаемыми решением вспомогательной задачи метода секущих плоскостей. Доказана сходимость данного алгоритма, приведены результаты вычислительных экспериментов при...

Full description

Saved in:

Bibliographic Details
Date:	2015
Main Authors:	Воронцова, Е.А., Нурминский, Е.А.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Series:	Кибернетика и системный анализ
Subjects:	Системный анализ
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/124845
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации / Е.А. Воронцова, Е.А. Нурминский // Кибернетика и системный анализ. — 2015. — Т. 51, № 4. — С. 137-150. — Бібліогр.: 37 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-124845
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1248452025-02-09T13:34:32Z Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации Синтез січних і відокремлювальних площин в одному методі негладкої оптимизації Synthesis of cutting and separating planes in a non-smooth optimization method Воронцова, Е.А. Нурминский, Е.А. Системный анализ Предложен алгоритм решения задач недифференцируемой оптимизации семейства методов отделяющих плоскостей с дополнительными отсечениями, порождаемыми решением вспомогательной задачи метода секущих плоскостей. Доказана сходимость данного алгоритма, приведены результаты вычислительных экспериментов при решении транспортных задач. Задачи транспортного типа с ограничениями на потоки сводятся к задачам проекции достаточно удаленной точки на допустимое множество. Запропоновано алгоритм розв’язання задач недиференційованої оптимізації сім’ї методів відокремлювальних площин з додатковими відсіканнями, породжуваними розв’язком допоміжної задачі методу січних площин. Доведено збіжність цього алгоритму і наведено результати обчислювальних експериментів при розв’язанні транспортних задач. Задачі транспортного типу з обмеженнями на потоки зводяться до задач проекції досить віддаленої точки на допустиму множину. A general scheme for non-smooth convex optimization based on the separating plane algorithm with additional clippings is considered. The convergence of the algorithm is proved. The results of numerical experiments are given, which demonstrated the overall computational efficiency compared to known leaders in this field. Of especial interest are the computational results applied to projection version of the transportation problems with flow constraints. Работа проводится в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014-2020 годы», соглашение 14.604.21.0052 от 30.06.2014 г. с МОН. Уникальный идентификатор проекта RFMEFI60414X0052. 2015 Article Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации / Е.А. Воронцова, Е.А. Нурминский // Кибернетика и системный анализ. — 2015. — Т. 51, № 4. — С. 137-150. — Бібліогр.: 37 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124845 519.8 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системный анализ Системный анализ
spellingShingle	Системный анализ Системный анализ Воронцова, Е.А. Нурминский, Е.А. Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации Кибернетика и системный анализ
description	Предложен алгоритм решения задач недифференцируемой оптимизации семейства методов отделяющих плоскостей с дополнительными отсечениями, порождаемыми решением вспомогательной задачи метода секущих плоскостей. Доказана сходимость данного алгоритма, приведены результаты вычислительных экспериментов при решении транспортных задач. Задачи транспортного типа с ограничениями на потоки сводятся к задачам проекции достаточно удаленной точки на допустимое множество.
format	Article
author	Воронцова, Е.А. Нурминский, Е.А.
author_facet	Воронцова, Е.А. Нурминский, Е.А.
author_sort	Воронцова, Е.А.
title	Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации
title_short	Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации
title_full	Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации
title_fullStr	Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации
title_full_unstemmed	Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации
title_sort	синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2015
topic_facet	Системный анализ
url	https://nasplib.isofts.kiev.ua/handle/123456789/124845
citation_txt	Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации / Е.А. Воронцова, Е.А. Нурминский // Кибернетика и системный анализ. — 2015. — Т. 51, № 4. — С. 137-150. — Бібліогр.: 37 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT voroncovaea sintezsekuŝihiotdelâûŝihploskostejvodnommetodenegladkojoptimizacii AT nurminskijea sintezsekuŝihiotdelâûŝihploskostejvodnommetodenegladkojoptimizacii AT voroncovaea sintezsíčnihívídokremlûvalʹnihploŝinvodnomumetodínegladkoíoptimizacíí AT nurminskijea sintezsíčnihívídokremlûvalʹnihploŝinvodnomumetodínegladkoíoptimizacíí AT voroncovaea synthesisofcuttingandseparatingplanesinanonsmoothoptimizationmethod AT nurminskijea synthesisofcuttingandseparatingplanesinanonsmoothoptimizationmethod
first_indexed	2025-11-26T06:26:46Z
last_indexed	2025-11-26T06:26:46Z
_version_	1849833199423717376
fulltext	ÓÄÊ 519.8 Å.À. ÂÎÐÎÍÖÎÂÀ, Å.À. ÍÓÐÌÈÍÑÊÈÉ ÑÈÍÒÅÇ ÑÅÊÓÙÈÕ È ÎÒÄÅËßÞÙÈÕ ÏËÎÑÊÎÑÒÅÉ Â ÎÄÍÎÌ ÌÅÒÎÄÅ ÍÅÃËÀÄÊÎÉ ÎÏÒÈÌÈÇÀÖÈÈ1 Àííîòàöèÿ. Ïðåäëîæåí àëãîðèòì ðåøåíèÿ çàäà÷ íåäèôôåðåíöèðóåìîé îïòèìèçàöèè ñåìåéñòâà ìåòîäîâ îòäåëÿþùèõ ïëîñêîñòåé ñ äîïîëíèòåëüíûìè îòñå÷åíèÿìè, ïîðîæäàå- ìûìè ðåøåíèåì âñïîìîãàòåëüíîé çàäà÷è ìåòîäà ñåêóùèõ ïëîñêîñòåé. Äîêàçàíà ñõîäè- ìîñòü äàííîãî àëãîðèòìà, ïðèâåäåíû ðåçóëüòàòû âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ ïðè ðå- øåíèè òðàíñïîðòíûõ çàäà÷. Çàäà÷è òðàíñïîðòíîãî òèïà ñ îãðàíè÷åíèÿìè íà ïîòîêè ñâî- äÿòñÿ ê çàäà÷àì ïðîåêöèè äîñòàòî÷íî óäàëåííîé òî÷êè íà äîïóñòèìîå ìíîæåñòâî. Êëþ÷åâûå ñëîâà: âûïóêëàÿ îïòèìèçàöèÿ, ìåòîäû îòäåëÿþùèõ ïëîñêîñòåé. ÂÂÅÄÅÍÈÅ Ïóñòü x x x n= ( , , )1 K — âåêòîð n-ìåðíîãî åâêëèäîâà ïðîñòðàíñòâà Ân ñ îáû÷íûì ñêàëÿðíûì ïðîèçâåäåíèåì xy . Â Ân ðàññìàòðèâàåòñÿ çàäà÷à áåçóñ- ëîâíîé âûïóêëîé íåäèôôåðåíöèðóåìîé îïòèìèçàöèè (ÍÄÎ): min ( ) x n f x ÎÂ , ãäå f x( ) — âûïóêëàÿ íåäèôôåðåíöèðóåìàÿ ôóíêöèÿ. Áóäåì ñ÷èòàòü, ÷òî äàííàÿ çàäà÷à ÿâëÿåòñÿ ðàçðåøèìîé. Ïðîáëåìû òàêîãî ðîäà âîçíèêàþò â ðàçëè÷íûõ îáëàñòÿõ íàóêè è òåõíèêè, íàïðèìåð ïðè ðåøåíèè çàäà÷ ìåõàíèêè ñïëîøíûõ ñðåä ñ ó÷åòîì òðåíèÿ [1], òåî- ðèè óïðàâëåíèÿ [2], ýêîíîìèêè [3–5] è äð. Êðîìå òîãî, ïðîãðåññ â îáëàñòè ðàçðà- áîòêè è ðåàëèçàöèè ìåòîäîâ ÍÄÎ äàñò âîçìîæíîñòü ïîñòðîèòü áîëåå ýôôåêòèâ- íûå ñïîñîáû ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ áîëüøîé ðàçìåðíîñòè. Äàííàÿ ñòàòüÿ ïîñâÿùåíà äàëüíåéøåìó èññëåäîâàíèþ ýôôåêòèâíîãî ìåòî- äà [21] ðåøåíèÿ çàäà÷ ìíîãîìåðíîé âûïóêëîé ÍÄÎ áåç îãðàíè÷åíèé, êîòîðûé íå òðåáóåò äîïîëíèòåëüíîé èíôîðìàöèè î âíóòðåííåé ñòðóêòóðå îïòèìèçèðóåìîé ôóíêöèè è ÿâëÿåòñÿ ïðåäñòàâèòåëåì òàê íàçûâàåìîé black-box îïòèìèçàöèè. Ïðåäïîëàãàåòñÿ, ÷òî âñÿ äîñòóïíàÿ èíôîðìàöèÿ î öåëåâîé ôóíêöèè f x( ) çàäà÷è ïðåäîñòàâëÿåòñÿ ñóáãðàäèåíòíûì îðàêóëîì — â ïðîèçâîëüíîé òî÷êå x nÎÂ ìîæ- íî îïðåäåëèòü òîëüêî çíà÷åíèå ôóíêöèè f x( ) è ñóáãðàäèåíò g f xÎ¶ ( ) , ïðîèç- âîëüíî âûáðàííûé èç ñóáäèôôåðåíöèàëà ¶f x( ) ôóíêöèè f x( ) . Ñõåìû îðàêóëüíîãî òèïà äëÿ ìèíèìèçàöèè ãëàäêèõ è íåãëàäêèõ ôóíêöèé èìå- þò ïðèíöèïèàëüíûå ðàçëè÷èÿ. Îðàêóëû äèôôåðåíöèðóåìûõ ôóíêöèé ïîçâîëÿþò ïîñòðîèòü ñõîäÿùèåñÿ ðåëàêñàöèîííûå ìèíèìèçèðóþùèå ïîñëåäîâàòåëüíîñòè (ñì., íàïðèìåð, [6]). Äëÿ íåãëàäêèõ ôóíêöèé òàêàÿ âîçìîæíîñòü íåïðèìåíèìà â ïðèíöèïå, ïîñêîëüêó ïðîèçâîëüíî âûáðàííûé ñóáãðàäèåíò íå îïðåäåëÿåò ðåëàêñà- öèîííîãî íàïðàâëåíèÿ [7]. Ïî ñóòè ìåòîäû âûïóêëîé ÍÄÎ èñïîëüçóþò òîëüêî ñâîé- ñòâà îòäåëèìîñòè, ÷òî çíà÷èòåëüíî óìåíüøàåò èõ ñêîðîñòü ñõîäèìîñòè. Â [8] áûëè óñòàíîâëåíû íèæíèå ãðàíèöû îöåíêè ñëîæíîñòè ìåòîäîâ, ïîëü- çóþùèõñÿ òîëüêî îðàêóëîì, äëÿ ðàçëè÷íûõ êëàññîâ çàäà÷ îïòèìèçàöèè. Îêàçà- ëîñü, ÷òî äëÿ ðàññìàòðèâàåìîãî êëàññà çàäà÷ âûïóêëîé ÍÄÎ íå ñóùåñòâóåò ìåòî- äà, êîòîðûé ñõîäèòñÿ áûñòðåå, ÷åì ñî ñêîðîñòüþ ïîðÿäêà O q k n( )/ , ãäå q < 1 — àáñîëþòíàÿ êîíñòàíòà, k — ÷èñëî èòåðàöèé ìåòîäà. Íè â îäíîì èç ìåòîäîâ îöåí- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 137 1Ðàáîòà ïðîâîäèòñÿ â ðàìêàõ ÔÖÏ «Èññëåäîâàíèÿ è ðàçðàáîòêè ïî ïðèîðèòåòíûì íàïðàâëåíèÿì ðàçâèòèÿ íàó÷íî-òåõíîëîãè÷åñêîãî êîìïëåêñà Ðîññèè íà 2014-2020 ãîäû», ñîãëàøåíèå 14.604.21.0052 îò 30.06.2014 ã. ñ ÌÎÍ. Óíèêàëüíûé èäåíòèôèêàòîð ïðîåêòà RFMEFI60414X0052. © Å.À. Âîðîíöîâà, Å.À. Íóðìèíñêèé, 2015 138 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 êà ñêîðîñòè ñõîäèìîñòè, ðàâíîìåðíàÿ ïî ðàçìåðíîñòè ïðîñòðàíñòâà n , íå ìîæåò áûòü ëó÷øå, ÷åì îöåíêà ñêîðîñòè ïîðÿäêà O k( )/-1 2 . Äîêàçàíî, ÷òî òàêèìè ñêî- ðîñòÿìè ñõîäèìîñòè îáëàäàþò ìåòîä öåíòðîâ òÿæåñòè [10, 11] è ñóáãðàäèåíòíûé ìåòîä [32]. Òàêèì îáðàçîì, äâà êîíêðåòíî ïåðâûõ ìåòîäà, ðàçðàáîòàííûå äëÿ ðå- øåíèÿ çàäà÷ íåãëàäêîé ìèíèìèçàöèè, îêàçàëèñü íåóëó÷øàåìûìè ïî ñâîèì ñêî- ðîñòíûì õàðàêòåðèñòèêàì. Ìåòîä öåíòðîâ òÿæåñòè íà ïðàêòèêå íå ÿâëÿåòñÿ ïðè- ìåíèìûì, ïîñêîëüêó îïåðàöèÿ íàõîæäåíèÿ öåíòðà òÿæåñòè âûïóêëîãî ìíîæå- ñòâà â ìíîãîìåðíîì ïðîñòðàíñòâå — âåñüìà ñëîæíàÿ çàäà÷à. Ñóáãðàäèåíòíûé ìåòîä, âïåðâûå ïðåäëîæåííûé Í.Ç. Øîðîì [32], èìååò ïðîñòåéøóþ âû÷èñëèòåëüíóþ ñõåìó x x g g f x kk k k k k k+ = - Î¶ =1 0 1l , ( ), , ,K , è ñõîäèòñÿ ïðè âåñüìà ïðèåìëåìûõ óñëîâèÿõ. Åãî ïðàêòè÷åñêàÿ âû÷èñëèòåëü- íàÿ ýôôåêòèâíîñòü çàâèñèò îò ñïîñîáîâ óïðàâëåíèÿ øàãîâûìè ìíîæèòåëÿ- ìè l . Íàèáîëåå óäà÷íûì ïðàâèëîì âûáîðà øàãîâîãî ìíîæèòåëÿ l ïðèçíàíî ïðàâèëî Á.Ò. Ïîëÿêà [12], îäíàêî ïðè óñëîâèè çàðàíåå èçâåñòíîãî çíà÷åíèÿ îïòèìóìà. Ñðåäè äðóãèõ ñïîñîáîâ ðåãóëèðîâêè øàãà ìîæíî îòìåòèòü òàêæå ñïîñîá èç [13]. Ñóáãðàäèåíòíûé ìåòîä ñ òàêîé ðåãóëèðîâêîé øàãà íà èçâåñò- íûõ òåñòàõ ïðîäåìîíñòðèðîâàë ïðàêòè÷åñêè ëèíåéíóþ ñêîðîñòü ñõîäèìîñòè. Îäíàêî ñëåäóåò îòìåòèòü, ÷òî äàííîå óòâåðæäåíèå î ñêîðîñòè ñõîäèìîñòè ìå- òîäîâ ÍÄÎ ÿâëÿåòñÿ âåðíûì ðàâíîìåðíî ïî ðàçìåðíîñòè ïðîñòðàíñòâà ïåðå- ìåííûõ. Äëÿ çàäà÷ óìåðåííîé ðàçìåðíîñòè ìîæíî ðàçðàáîòàòü áîëåå ýôôåê- òèâíûå ñõåìû [9]. Ñëåäóþùèì ýòàïîì ðàçâèòèÿ ìåòîäîâ ÍÄÎ ñòàëî ïîÿâëåíèå òàê íàçûâàåìûõ bundle-ìåòîäîâ (îò àíãë. bundle — ïó÷îê) [14–16], ïðåäñòàâèòåëåì êîòîðûõ ÿâëÿ- åòñÿ ìåòîä óðîâíåé [17], ðàçðàáîòàííûé â 1995 ã. Èç ïîñëåäíèõ ïóáëèêàöèé â îá- ëàñòè bundle-ìåòîäîâ ìîæíî îòìåòèòü èäåþ ðàñùåïëåíèÿ íà ïîäïðîñòðàíñòâà ãëàäêîñòè–íåãëàäêîñòè, íàçâàííóþ VU-àëãîðèòìîì [18]; â îáëàñòè ìåòîäîâ ÍÄÎ, íå îòíîñÿùèõñÿ ê îðàêóëüíîìó òèïó, îòìåòèì ñïåöèàëüíóþ òåõíèêó ñãëà- æèâàíèÿ ñ ïîñëåäóþùèì ïðèìåíåíèåì ãðàäèåíòíûõ ñõåì ãëàäêîé ìèíèìèçàöèè [19] äëÿ íåãëàäêèõ ôóíêöèé ñ îïðåäåëåííîé ñòðóêòóðîé [20]. Ïðåäëàãàåìûé â äàííîé ñòàòüå ïðîåêöèîííûé àëãîðèòì SPACLIP ðåøåíèÿ çàäà÷ ìèíèìèçàöèè íåãëàäêèõ ôóíêöèé ÿâëÿåòñÿ ðåçóëüòàòîì äàëüíåéøåãî ðàç- âèòèÿ è óñîâåðøåíñòâîâàíèÿ ìåòîäîâ îòäåëÿþùèõ ïëîñêîñòåé [21–23], èìåþùèõ ðÿä âàæíûõ òåîðåòè÷åñêèõ è âû÷èñëèòåëüíûõ îñîáåííîñòåé. Â âû÷èñëèòåëüíûõ ýêñïåðèìåíòàõ àëãîðèòì SPACLIP ïðèìåíåí äëÿ ðåøåíèÿ òðàíñïîðòíîé çàäà÷è, êîòîðàÿ íå òîëüêî ÿâëÿåòñÿ îäíîé èç íàèáîëåå ðàñïðîñòðà- íåííûõ â ýêîíîìè÷åñêèõ ïðèëîæåíèÿõ, íî è èìååò îïðåäåëåííóþ ñèìâîëè÷åñêóþ öåííîñòü, òàê êàê ðàçâèòèå ÍÄÎ íà÷àëîñü èìåííî ñ çàäà÷ ýòîãî òèïà [37]. Â ìàòðè÷íîé ïîñòàíîâêå äàííîé çàäà÷è, ðàññìàòðèâàåìîé â íàñòîÿùåé ñòàòüå, íà îáúåìû ïîñòàâîê íàëîæåíû îãðàíè÷åíèÿ ñâåðõó è ñíèçó, ÷òî çàòðóäíÿåò ïðèìå- íåíèå ìåòîäà ïîòåíöèàëîâ è ñèìïëåêñ-ìåòîäà äëÿ ðåøåíèÿ òàêèõ çàäà÷, îñîáåííî çàäà÷ áîëüøîé ðàçìåðíîñòè. Îïðåäåëåííûé èíòåðåñ ïðåäñòàâëÿåò ñâåäåíèå òðàíñ- ïîðòíîé çàäà÷è ê çàäà÷å íàõîæäåíèÿ ïðîåêöèè íà ñäâèã äîïóñòèìîãî ìíîæåñòâà. ÏÐÎÅÊÖÈÎÍÍÛÉ ÀËÃÎÐÈÒÌ SPACLIP Ìåòîäû îòäåëÿþùèõ ïëîñêîñòåé [21] îñíîâûâàþòñÿ íà èäåå çàìåíû èñõîäíîé çàäà÷è ìèíèìèçàöèè íà çàäà÷ó âû÷èñëåíèÿ ñîïðÿæåííîé ôóíêöèè Ôåíõåëÿ–Ìîðî â íóëå f x f x x f x f x x n ( ) min ( ) { ( )} ( ) ,* = = - × - = - ÎÂ sup 0 0 x f ( ) ,Î¶ 0 (1) ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 139 ãäå f g gx f x x ( ) { ( )}= -sup — ôóíêöèÿ, ñîïðÿæåííàÿ (ïî Ôåíõåëþ–Ìîðî) ê f x( ) . Çàäà÷ó (1) ìîæíî èíòåðïðåòèðîâàòü êàê çàäà÷ó íàõîæäåíèÿ òî÷êè ïåðåñå÷åíèÿ ãðàôèêà ñîïðÿæåííîé ôóíêöèè ñ âåðòèêàëüíîé ïðÿìîé 0´ Â+ (ðèñ. 1). Áóäåì ñ÷èòàòü, ÷òî f ( )0 0= è íà÷àëî êîîðäèíàò ïðîñòðàíñòâà ïðÿìûõ ïåðåìåííûõ ðåøåíèåì çàäà÷è ìèíèìèçàöèè íå ÿâëÿåòñÿ, ò.å. f x( )* < 0 . Íà ðèñ. 1 òî÷å÷íîé ëèíèåé ïîêàçàí ãðàôèê ñîïðÿæåííîé ôóíêöèè f g* ( ) . Îïîðíûé âåêòîð êàñà- òåëüíîé ãèïåðïëîñêîñòè â òî÷êå ( , ( ))0 0f ê íàäãðàôèêó ñîïðÿæåííîé ôóíê- öèè ñ òî÷íîñòüþ äî íîðìèðîâêè îïðåäåëÿåò ðåøåíèå çàäà÷è (1). Â ìåòîäå îòäåëÿþùèõ ïëîñêîñòåé (ÌÎÏ) íàäãðàôèê ñîïðÿæåííîé ôóíêöèè f àïïðîêñèìèðóåòñÿ âíóòðåííå è âíåøíå âûïóêëûìè ïîëèýäðàëü- íûìè ìíîæåñòâàìè D è U (ðèñ. 2). Óòî÷íÿÿ íà êàæäîé èòåðàöèè ýòè àïïðîêñè- ìàöèè â îêðåñòíîñòè âåðòèêàëüíîé ïðÿìîé 0´ Â+ , ïîëó÷àåì ñõîäÿùèåñÿ íèæ- íèå w è âåðõíèå u îöåíêè äëÿ f * ( )0 . Ìíîæåñòâà D è U ìîäèôèöèðóþòñÿ äîáàâëåíèåì ëèáî îòñå÷åíèé (äëÿ U ), ëèáî íîâûõ òî÷åê ( , ( ))e eg , ëåæàùèõ íà ãðàôèêå f * . Áàçîâûé âàðèàíò ÌÎÏ íå ãàðàíòèðóåò ìîíîòîííîñòè, îñîáåííî ïðè ïîäõîäå ê ýêñòðåìóìó. Äëÿ óëó÷øåíèÿ ñâîéñòâà ìîíîòîííîñòè ìåòîäà ââåäåì äîïîëíè- òåëüíîå îòñå÷åíèå ïî âåðõíåé îöåíêå u çíà÷åíèÿ f * ( )0 , ïîëó÷åííîé èç âíóòðåí- íåé àïïðîêñèìàöèè íàäãðàôèêà (ñì. ðèñ. 2): u e e e e e e = ³ = ³ Î Î Î min min ( ) min . ( , ) ( , ) * ( , )0 0 0 0 D f U f epi Òàêîå îòñå÷åíèå àïðèîðè áîëåå òî÷íî ëîêàëèçóåò ïîòåíöèàëüíûå òî÷êè íàäãðà- ôèêà f , êîòîðûå áóäóò â äàëüíåéøåì äîáàâëÿòüñÿ ïðè óòî÷íåíèè åãî àïïðîêñèìàöèè. Â âû÷èñëèòåëüíîì ïëàíå çíà÷åíèå u ìîæåò áûòü ïîëó÷åíî êàê ðåøåíèå çà- äà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ è ïðåäñòàâëÿåò ñîáîé îöåíêó, îïðåäåëÿåìóþ ïî ìåòîäó ñåêóùèõ ïëîñêîñòåé Êåëëè [36]: u t t t l = = Î = + ´Â = + min min ( , ) (( , ( )), , , , ) 0 1 2 0 co g f g k m k k k K f g g gk k m k k k m m k k k m m ( ), , , min = = = å å = å = Î = Î 1 1 1 0 0 l l l l t l D D k k k m f g* ( ) = = å 1 Ðèñ. 1. Ãðàôè÷åñêàÿ èíòåðïðåòàöèÿ çàäà÷è (1) Ðèñ. 2. Èëëþñòðàöèÿ ñòàíäàðòíîãî ìåòîäà îòäå- ëÿþùèõ ïëîñêîñòåé = - = - Î = åmax min ( ( ) ) max min{ ( )* * x k k k k m x k k m f g xg f g xg l l D 1 k } = = - - = - + -max min{ ( ) } min max{ ( ) ( ) x k k k k k x k k k kx g f x xg f x x x g } , (2) ãäå l l l= ( , , )1 K m , D m — ñòàíäàðòíûé ñèìïëåêñ, D m k= ³{l 0, k m=1, ,K ; l k k m = å = 1 1} . Äîáàâëåíèå ñëåäóþùåé òî÷êè ê àïïðîêñèìàöèè epi f * ïðè òàêîì îòñå÷åíèè çàêëþ÷àåòñÿ â ðåøåíèè çàäà÷è ïîñòðîåíèÿ îïîðíîé ãèïåðïëîñêîñòè ê óñå÷åííî- ìó íàäãðàôèêó f * : sup { } ( )g, f* gx e e u e Î £ - epi . (3) Äàííàÿ çàäà÷à îòëè÷àåòñÿ îò àíàëîãè÷- íîé çàäà÷è óòî÷íåíèÿ àïïðîêñèìàöèè íàäãðàôèêà ñîïðÿæåííîé ôóíêöèè â ñòàíäàðòíîì ÌÎÏ íàëè÷èåì äîïîë- íèòåëüíîãî îãðàíè÷åíèÿ e u£ . Â ýòîì ïëàíå àëãîðèòì ïîäîáåí ìåòîäó óðîâ- íåé [17], îäíàêî îòëè÷àåòñÿ òåì, ÷òî ïîñòðîåíèå àïïðîêñèìàöèé ïðîèñõî- äèò â ðàñøèðåííîì ïðîñòðàíñòâå Â +n 1. Ðèñ. 3 èëëþñòðèðóåò èäåþ òàêî- ãî äîïîëíèòåëüíîãî îòñå÷åíèÿ. Çàäà÷ó (3), êàê è â ñòàíäàðòíîì ÌÎÏ, ëåãêî ïåðåâåñòè â ïðîñòðàíñòâî ïðÿìûõ ïåðåìåííûõ x nÎÂ , îäíàêî ïðè ýòîì ïîÿâëÿåòñÿ âñïîìîãàòåëüíàÿ çàäà- ÷à îäíîìåðíîé ìèíèìèçàöèè ñ äîñòà- òî÷íî íåîæèäàííîé öåëåâîé ôóíêöèåé. Äåéñòâèòåëüíî, ââîäÿ äëÿ äîïîëíèòåëü- íîãî îãðàíè÷åíèÿ äâîéñòâåííóþ ïåðåìåííóþ l, ïîëó÷àåì sup sup inf epi( , ) ; * * { } { ( ) ( g f g gx gx f g f e e u l e l u Î £ ³ - = - + - 0 * ( ))}g = = + - + = + + +³ ³ inf sup inf l l lu l lu l 0 0 1 1 1 { { ( ) ( )}} ( )* g gx f g f x l æ è ç ö ø ÷ ì í î ü ý þ = = - + + = - + ³ - ³ u l u l u j l l l inf inf 1 1 1 { ( ( ))} ( , )f x x . (4) Ëåãêî ïîêàçàòü, ÷òî ôóíêöèÿ j l l l u( , ) ( ( ) )x f x= +-1 âûïóêëà ïî ñîâîêóï- íîñòè ïåðåìåííûõ ( , )l x . Îöåíêó ñâåðõó äëÿ j al a l a a( ( ) , ( ) )1 21 1+ - + -x y , ãäå 0 1£ £a , ìîæíî ïîëó÷èòü, èñïîëüçóÿ íåðàâåíñòâî Èåíñåíà äëÿ f : j al a l a a al a l a a a ( ( ) , ( ) ) ( ( ) ) ( ( ) 1 2 1 21 1 1 1 + - + - = + - + - x y f x y l a l u 1 21+ - + æ è çç ö ø ÷÷ = ( ) ) = + - + - × + - + - ( ( ) ) ( ) ( ) ( ) al a l al al a l l a l al a 1 2 1 1 2 1 2 1 1 1 1 1 f x l l u 2 2 × æ è çç ö ø ÷÷ + æ è ç ç ö ø ÷ ÷ £ y £ æ è çç ö ø ÷÷ + æ è ç ç ö ø ÷ ÷ + - æ è çç ö ø ÷÷ + æ è al l u a l l u1 1 2 2 1f x f x ( ) ç ç ö ø ÷ ÷ = + -aj l a j l( , ) ( ) ( , )1 21x y . 140 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 Ðèñ. 3. Èëëþñòðàöèÿ àëãîðèòìà SPACLIP–ÌÎÏ ñ äîïîëíèòåëüíûìè îòñå÷åíèÿìè Òàêèì îáðàçîì, ôóíêöèÿ j l( , )x âûïóêëà ïî ñîâîêóïíîñòè ïåðåìåííûõ ( , )l x , à ñëåäîâàòåëüíî, è ïî ïåðåìåííîé l . n Ðåøàòü çàäà÷ó îäíîìåðíîé ÍÄÎ (4) ïðåäëàãàåòñÿ ñ ïîìîùüþ áûñòðîãî àëãîðèò- ìà îäíîìåðíîãî ïîèñêà [27, 28], ïîñêîëüêó â áëàãîïðèÿòíûõ ñëó÷àÿõ îí èìååò ñâåðõ- ëèíåéíóþ èëè äàæå êâàäðàòè÷íóþ ñêîðîñòü ñõîäèìîñòè. Äëÿ àëãîðèòìà SPACLIP áûëà ñîçäàíà îòäåëüíàÿ ðåàëèçàöèÿ áûñòðîãî àëãîðèòìà îäíîìåðíîãî ïîèñêà. Â ðåçóëüòàòå àëãîðèòì ìåòîäà îòäåëÿþùèõ ïëîñêîñòåé ñ îòñå÷åíèÿìè (SPACLIP) èìååò ñëåäóþùèé âèä. Øàã 0. Èíèöèàëèçàöèÿ. Óñòàíîâèòü ñ÷åò÷èê èòåðàöèé k = 0 , îïðåäåëèòü íà÷àëüíóþ òî÷êó ìèíèìèçèðóþùåé ïîñëåäîâàòåëüíîñòè x0 . Øàã 1. Íàéòè inf 0 Î = U k k ( )w w w , ãäå U k — k-ÿ âíåøíÿÿ àïïðîêñèìàöèÿ íàä- ãðàôèêà ñîïðÿæåííîé ôóíêöèè f * . Äàííóþ çàäà÷ó ìîæíî ðåøèòü ðåêóððåíòíî: w w w w w w w k U U g gx f xk k k k = = Î Î Ç - £- - - inf inf 0 0 1 1 1( ) ( ) ( , ) \| ( ) = = = - Î ³- - - - - max{ , } max{ , ( ( ) ( ) inf inf 0 1 1 1U f x k k k k f x w w w w w 1 1)}, k ³ . (5) Ïðè ýòîì ìîæíî ñ÷èòàòü, ÷òî w 0 = - ¥ . Ôàêòè÷åñêè - w k ÿâëÿåòñÿ ðåêîðäîì ôóíêöèè f . Øàã 2. Íàéòè âåêòîð z zk k k= ( , )x — ïðîåêöèþ òî÷êè ( , )0 w k íà ïîëèýäð Dk âíóòðåííåé àïïðîêñèìàöèè íàäãðàôèêà ñîïðÿæåííîé ôóíêöèè z Pk D kk = (( , ))0 w , ãäå P aX ( ) — ðåøåíèå çàäà÷è ïðîåêöèè òî÷êè a íà ìíîæåñòâî X . Äëÿ ðåøåíèÿ äàííîé çàäà÷è èñïîëüçóåòñÿ ìåòîä ïîäõîäÿùèõ àôôèííûõ ïîäïðîñòðàíñòâ [26]. Äàííûé êîíå÷íûé ìåòîä ðåøàåò çàäà÷ó íàõîæäåíèÿ âåêòî- ðà ìèíèìàëüíîé äëèíû â ïîëèýäðå êîíå÷íîìåðíîãî åâêëèäîâà ïðîñòðàíñòâà è îáëàäàåò «ëó÷øå, ÷åì ëèíåéíîé» ãëîáàëüíîé ñêîðîñòüþ ñõîäèìîñòè. Øàã 3. Âû÷èñëèòü î÷åðåäíîå ïðèáëèæåíèå ê ðåøåíèþ çàäà÷è min ( ) x n f x ÎÂ : x zk k k= - / x . Ïðè òàêîé íîðìèðîâêå ïîñëåäíÿÿ êîîðäèíàòà â x z xk k k k= - = -/ ( , )x 1 áóäåò ðàâíà -1 , ÷òî è òðåáóåòñÿ (ñì. ðèñ. 1). Øàã 4. Îïðåäåëèòü u — óðîâåíü îòñå÷åíèÿ âåðõíåé ÷àñòè íàäãðàôèêà epi f , äëÿ ÷åãî íåîáõîäèìî ðåøèòü çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ (2). Çàìåòèì, ÷òî òàêîå îòñå÷åíèå íå ìåøàåò ðåøåíèþ çàäà÷è ïðîåêöèè íà Dk øàãà 2 è, ñëåäî- âàòåëüíî, ïîñòðîåíèþ ïðèáëèæåííîãî ðåøåíèÿ xk . Åñëè çàäà÷à (2) íå èìååò ðåøåíèÿ, ïåðåéòè ê øàãó 7. Øàã 5. Ðåøèòü çàäà÷ó îäíîìåðíîé ÍÄÎ (4). Ïóñòü l k — íàéäåííîå íà k-é èòåðàöèè ðåøåíèå äàííîé çàäà÷è. Øàã 6. Ìîäèôèöèðîâàòü ïðèáëèæåíèå xk ïî ôîðìóëå x xk k k= -l 1 . Â àëãîðèòìå SPACLIP, â îòëè÷èå îò ÌÎÏ, ïðè äîáàâëåíèè î÷åðåäíîé òî÷êè â àïïðîêñèìàöèþ epi f ñóáãðàäèåíò îïòèìèçèðóåìîé ôóíêöèè âû÷èñëÿåòñÿ íå â òåñòèðóåìîé òî÷êå x , à â ìàñøòàáèðóåìîé îòíîñèòåëüíî x òî÷êå l k x-1 . Øàã 7. Äîáàâèòü ïàðó ( ( ), ( ))g f x f gk k kÎ ¶ ê ïîëèýäðó Dk . Øàã 8. Åñëè âûïîëíÿåòñÿ êàêîå-ëèáî èç óñëîâèé ïðåêðàùåíèÿ ðàáîòû àëãî- ðèòìà, òî çàâåðøèòü ðàáîòó. Èíà÷å óâåëè÷èòü íà åäèíèöó ñ÷åò÷èê èòåðàöèé k è ïåðåéòè ê øàãó 1. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 141 Â ñëåäóþùèõ ðàçäåëàõ ïðèâåäåíû äîêàçàòåëüñòâî ñõîäèìîñòè äàííîãî àëãî- ðèòìà è ðåçóëüòàòû âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ. ÑÕÎÄÈÌÎÑÒÜ ÌÅÒÎÄÀ Ñõîäèìîñòü ïðîåêöèîííîãî àëãîðèòìà îòäåëÿþùèõ ïëîñêîñòåé ñ îòñå÷åíèÿìè óòâåðæäàåòñÿ ñëåäóþùåé òåîðåìîé. Òåîðåìà 1. Ïóñòü f x( ) — êîíå÷íàÿ âûïóêëàÿ ôóíêöèÿ, f ( )0 0= , w min ( )= - < < ¥f x W . Òîãäà lim * k k ®¥ =w w . Äîêàçàòåëüñòâî. Ïî èíäóêöèè ìîæíî äîêàçàòü, ÷òî w k f£ * ( )0 äëÿ ëþáîãî k. Äåéñòâèòåëüíî, ýòî íåðàâåíñòâî ïî îïðåäåëåíèþ âûïîëíÿåòñÿ äëÿ k = 0 . Ñîãëàñíî (5) w wk k kf x= -- -max{ , ( )}`1 1 . Äåëàÿ èíäóêòèâíûé ïåðåõîä è ó÷èòû- âàÿ, ÷òî - = × - £ × - =- - -f x x f x x f x fk k k x ( ) ( ) { ( )} ( )` * 1 1 10 0 0sup , ïîëó÷àåì w k f f f£ =max{ ( ), ( )} ( )* * 0 0 0 , ÷òî è òðåáîâàëîñü äîêàçàòü. Ïîñêîëüêó w k f£ ( )0 , à z D Dk k k k+ Î =( , ) { }0 w co , òî äëÿ äîêàçàòåëüñòâà óòâåðæäåíèÿ òåîðåìû äîñòàòî÷íî ïîêàçàòü, ÷òî \|\| \|\|zk k ® ®¥ 0 , òàê êàê ýòî îçíà÷àåò, ÷òî - ® ®¥ f x fk k ( ) ( )* 0 . Äëÿ äîêàçàòåëüñòâà ìîíîòîííîãî óáûâàíèÿ íîðìû âåêòîðîâ \|\| \|\|zk ðàññìîò- ðèì íåñêîëüêî ñëó÷àåâ. 1. Çàäà÷à (2) íà øàãå 4 íå èìååò ðåøåíèÿ äëÿ âñåõ k . Òîãäà ìîæíî ñ÷èòàòü, ÷òî u º ¥ è ÌÎÏ ñ äîïîëíèòåëüíûìè îòñå÷åíèÿìè ïðåîáðàçóåòñÿ â ñòàíäàðòíûé ÌÎÏ, ñõîäèìîñòü êîòîðîãî äîêàçàíà â [25]. 2. Çàäà÷à (2) íà øàãå 4 èìååò ðåøåíèå. Îáîçíà÷èì xk ðåøåíèå çàäà÷è (3), x xk k k k= ³-l l1 1, . Òîãäà âåêòîð zk ïðåäñòàâèì â âèäå z r xk k k k= - --( , )l 1 1 . Â çàâèñèìîñòè îò òîãî, ìåíÿåòñÿ ëè íà k-é èòåðàöèè òåêóùèé ðåêîðä öåëå- âîé ôóíêöèè w k , âîçìîæíû äâà âàðèàíòà. Âàðèàíò 1. w wk k= -1 . Òîãäà ïðîåêöèÿ âûïîëíÿåòñÿ èç îäíîé è òîé æå òî÷- êè: \|\| \|\| min \|\| \|\| min ( , ) ( , ) z zk z D z Dk k k k 2 0 2 0 1 = = + Î + Î¢ -w wco co - ¢ 1 2\|\| \|\|z . Çäåñü Dk ¢ — ïîëèòîï, ïîëó÷åííûé íà k-é èòåðàöèè ïîñëå îòñå÷åíèÿ (3). Ïðè ýòîì ñïðàâåäëèâî ñëåäóþ- ùåå íåðàâåíñòâî: \|\| \|\| min \|\| ( , ( )) \|\| [ , ] z z g f g zk k k k k 2 0 1 1 1 2£ + - Î - - l l . Ðåøåíèå çàäà÷è min \|\| ( , ( )) \|\| [ , ] l l Î - -+ - 0 1 1 1 2z g f g zk k k k ïðåäñòàâëÿåò ïðîåê- öèþ ìèíèìóìà îäíîìåðíîé êâàäðàòè÷íîé ôóíêöèè íà èíòåðâàë [ , ]0 1 : l* * min {( ( , ( ))) \|\| ( , ( )) \|\|/= - -- - -z g f g z g f g zk k k k k k k1 1 1 2 1, } . Òîãäà äëÿ ëþáîãî l £ - - - - - ( ( , ( ))) \|\| ( , ( )) \|\| * z g f g z g f g z k k k k k k k 1 1 1 2 (6) âûïîëíÿåòñÿ íåðàâåíñòâî \|\| \|\| \|\| (( , ( )) ) \|\|z z g f g zk k k k k 2 1 1 2£ + -- -l . Ïîñëå âîçâåäåíèÿ â ñòåïåíü ïîëó÷èì \|\| \|\| \|\| \|\| (( ( , ( ))) \|\| (z z z g f g z gk k k k k k 2 1 2 1 12 2 £ - - -- - -l l k k kf g z, ( )) \|\| ) .* - -1 2 (7) 142 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 Ñîãëàñíî (6) ( ( , ( ))) \|\| ( , ( )) \|\|* z g f g z g f g zk k k k k k k- - -- - - ³1 1 1 2 2 l ³ - > ¹- l l 2 01 2\|\| ( , ( )) \|\|g f g zk k k ïðè 0 . Äëÿ äîêàçàòåëüñòâà ìîíîòîííîãî óáûâàíèÿ äëÿ âàðèàíòà 1 íîðìû âåêòîðîâ \|\| \|\|zk äîñòàòî÷íî â (7) ó÷åñòü, ÷òî âû÷èòàåìîå ÷èñëî â ïðàâîé ÷àñòè ïîëîæèòåëü- íî ïî ïîñëåäíåìó íåðàâåíñòâó: \|\| \|\| \|\| \|\|z zk k 2 1 2< - . Âàðèàíò 2. w wk k kf x= - >- -( )`1 1 . Òîãäà \|\| \|\| min \|\| \|\| \|\| \|\| ( , ) z z zk z Dk k 2 0 2 2= £ + Î ¢w l co , (8) ãäå z z zk k k kl w w = - - < - - - W W 1 1 1. Ëåãêî óâèäåòü, ÷òî ïðè îïðåäåëåííîì òàêèì îáðàçîì z l ïîñëåäíåå íåðàâåí- ñòâî â (8) âûïîëíÿåòñÿ. Ïîýòîìó \|\| \|\| \|\| \|\|z zk k 2 1 2< - . Èç ìîíîòîííîñòè íîðìû âåêòîðîâ \|\| \|\|zk ñëåäóåò ñóùåñòâîâàíèå ïðåäåëà lim \|\| \|\| k kz ®¥ = r . Äëÿ äîêàçàòåëüñòâà òîãî, ÷òî r = 0 , ïðåäïîëîæèì ïðîòèâíîå. Ïóñòü \|\| \|\|z rk k³ t äëÿ íåêîòîðîãî t > 0 . Âûïîëíÿåòñÿ ñëåäóþùåå ðàâåíñòâî: lim (( , ( )) ( , )) \|\| \|\|* k k k k k kg f g z z ®¥ + +ë - - û =1 1 20 0w . Ïðåäïîëîæèì ïðîòèâíîå. Ïóñòü äëÿ íåêîòîðîé ïîäïîñëåäîâàòåëüíîñòè èìå- åì (( , ( )) ( , )) \|\| \|\| ,g f g z zk k k k k¢+ ¢+ ¢ ¢ ¢- £ - >1 1 20 0w g g . Òîãäà \|\| \|\| min ( , ) {{( , ( )), , , , zk z g f g i kk i i ¢+ + Î = ¢ = ¢ 1 2 0 0 1w co K + £ 1 0 2 }, ( , )} \|\| \|\| W z £ + = + -¢ ¢ ¢+ ¢+ min \|\| \|\| , ( , ) ~ ( )( , ( ))z g g f gk k k k z 0 1 2 1 1w l l l Î[ , ]0 1 . Ó÷èòûâàÿ, ÷òî ~ ( , )g zk k k¢ ¢ ¢= +0 w , ïîëó÷àåì \|\| \|\| min \|\| ( ) (( , ( ) [ , ] z z g f gk k k k¢+ Î ¢ ¢+ ¢+£ + -1 2 0 1 1 11 l l l ) ( , )) \|\|- ¢0 2w k . (9) Ïîñëå âîçâåäåíèÿ â êâàäðàò ïðàâîé ÷àñòè íåðàâåíñòâà (9) ïîëó÷èì \|\| \|\| min { \|\| \|\| ( ) (( [ , ] z z z gk k k k¢+ Î ¢ ¢ ¢+£ + -1 2 0 1 2 2 12 1 l l l l , ( )) ( , ))f gk k¢+ ¢- +1 0 w + - -¢+ ¢+ ¢( ) \|\| ( , ( )) ( , ) \|\| }1 02 1 1 2l wg f gk k k . (10) Ïðîäîëæèì ïðåîáðàçîâàíèÿ â ïðàâîé ÷àñòè íåðàâåíñòâà (10): \|\| \|\| min { \|\| \|\| ( ) \|\| \|\| [ , ] z z zk k k¢+ Î ¢ ¢£ + - -1 2 0 1 2 2 22 1 2 l l l l g l l( )1- + + - - =¢+ ¢+ ¢( ) \|\| ( , ( )) ( , ) \|\| }1 02 1 1 2l wg f gk k k (11) = - - - + - Î ¢ ¢+min {( ) \|\| \|\| ( ) ( ) \|\| ( [ , ]l l l g l l l 0 1 2 2 22 2 1 1z gk k 1 1 20, ( )) ( , ) \|\| }f gk k¢+ ¢- w . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 143 Èç (11) ïîëó÷åíà îöåíêà \|\| \|\|zk ¢+ £1 2 £ - - + - Î ¢ ¢+min {\|\| \|\| ( ) (( ) \|\| ( , ( [ , ] * l g l l l 0 1 2 2 12 1 1z g f gk k k k kz¢+ ¢ ¢- - £1 2 20)) ( , ) \|\| \|\| \|\| )}w £ - - + -¢\|\| \|\| ( ) ( )zk 2 2 22 1 1g l l l d äëÿ ëþáîãî l Î[ , ]0 1 . Ïîäñòàâèâ â äàííîå íåðàâåíñòâî âûðàæåíèå l d g d g= + + >( ) / ( )2 2 2 0 , ïîëó÷èì \|\| \|\| \|\| \|\| / ( )z zk k¢+ ¢£ - +1 2 2 2 2 2g d g . (12) Ïåðåõîäÿ â (12) ê ïðåäåëó ïðè k¢ ® ¥, ïîëó÷èì ïðîòèâîðå÷èå. Ïîýòîìó lim (( , ( )) ( , )) \|\| \|\|* k k k k k kg f g z z ®¥ + +ë - - û =1 1 20 0w . Ïîñêîëüêó 0 0 01 1£ + - ®+ +( ( , )) ( , ( ))z z g f g zk k k k k kw ïðè k ® ¥ , äëÿ äîñòàòî÷íî áîëüøèõ k âûïîëíÿåòñÿ íåðàâåíñòâî ( ( , ))z zk k k+ -0 w - £+ +( , ( ))g f g z rk k k k1 1 2 2e äëÿ ëþáîãî e > 0 . Ñëåäîâàòåëüíî, ( , ) ( , ( )) ( , ) \|\| \|\|0 01 1 1 2w w ek k k k k k k k kz g f g z z z r+ + +³ ³ + - ³ ³ + - ³ +( , ) ( , ) /0 0 22 2 2 2 2 2w t e w tk k k k k k k z r r z r äëÿ e t£ / 2 , ò.å. r r rk k k k k ( , ) ( , ) /0 0 21 2 2w w t+ ³ + . Äàëåå, f rk k k k ( ) ( , ) ( , ) ( , )0 0 0 01 2³ ³ + ³ ++w w t w d , ãäå d t³ ³rk 2 0 , ÷òî íåâîçìîæíî ïðè k ® ¥ . Äàííîå ïðîòèâîðå÷èå äîêàçûâàåò ðàâåíñòâî lim \|\| \|\| k kz ®¥ = 0 . Òåîðåìà äîêàçàíà. n ÏÐÈÌÅÍÅÍÈÅ ÀËÃÎÐÈÒÌÀ SPACLIP ÄËß ÐÅØÅÍÈß ÇÀÄÀ× ÒÐÀÍÑÏÎÐÒÍÎÃÎ ÒÈÏÀ Ðàññìîòðèì ìàòðè÷íóþ òðàíñïîðòíóþ çàäà÷ó ñ îãðàíè÷åíèÿìè íà îáúåìû ïî- ñòàâîê â ñòàíäàðòíîé ïîñòàíîâêå [30, 33]. Ïóñòü m1 — êîëè÷åñòâî ïîòðåáèòå- ëåé, n1 — êîëè÷åñòâî ïîñòàâùèêîâ, A i ni ( , , )=1 1K — çàïàñû ïðîäóêòà ó ïî- ñòàâùèêîâ, B j mj ( , , )=1 1K — ïîòðåáíîñòè â ïðîäóêòå ó ïîòðåáèòåëåé, cij — öåíà ïîñòàâêè åäèíèöû ïðîäóêòà îò i-ãî ïîñòàâùèêà j-ìó ïîòðåáèòåëþ, xij low è xij up — íèæíèå è âåðõíèå ãðàíèöû íà îáúåìû ïîñòàâîê xij . Ñ÷èòàåì çàäà÷ó ñáàëàíñèðîâàííîé: A Bi i n j j m = = å å= 1 1 1 1 . Ìèíèìèçàöèÿ òðàíñïîðòíûõ çàòðàò ñ óñòàíîâëåíèåì áàëàíñîâ ïî ïîñòàâùè- êàì è ïîòðåáèòåëÿì è äâóñòîðîííèìè ãðàíèöàìè íà ïåðåìåííûå ïðèâîäèò ê êëàññè÷åñêîé çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ: min x X ij ij j m i n ij ij c x Î == åå 11 11 , (13) ãäå ìíîæåñòâî X ij çàäàåò îãðàíè÷åíèÿ x A i n x B j mij j m i ij i n j = = å å= = = = 1 1 1 1 1 1 1 1, , , ; , , ,K K ; (14) x x xij low ij ij up£ £ , i n=1 1, ,K ; j m=1 1, ,K , (15) èëè â ìàòðè÷íî-âåêòîðíîì âèäå min , { \| x X cx X x Ax b Î = = , x x xlow up£ £ , b A Bi j= ( , )T } . 144 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 Âìåñòî (13)–(15) ðàññìîòðèì ýêâèâàëåíòíóþ êâàäðàòè÷íóþ çàäà÷ó ïðè òåõ æå îãðàíè÷åíèÿõ: min min x X ij ij j m i n x Xij ij x c x Î == Î + æ è ç ç ö ø ÷ ÷ = +åå e e2 2 11 11 c P c c X e e e 2 2 = - æ è ç ö ø ÷ + , (16) ãäå P aX ( ) — ðåçóëüòàò ðåøåíèÿ çàäà÷è ïðîåêöèè òî÷êè a íà ìíîæåñòâî X . Ðàçâèâàÿ ðåçóëüòàòû ðàáîòû [30], ìîæíî ïîêàçàòü, ÷òî â äåéñòâèòåëüíîñòè ñóùåñòâóåò òàêîå e > 0 , ÷òî äëÿ âñåõ 0< <e e çàäà÷à ëèíåéíîãî ïðîãðàììèðîâà- íèÿ (13)–(15) è çàäà÷à ïðîåêòèðîâàíèÿ (16) ýêâèâàëåíòíû, è P cX ( )- -e 1 ðåøàåò òðàíñïîðòíóþ çàäà÷ó (13)–(15). Äëÿ ôîðìóëèðîâêè ýòîãî ðåçóëüòàòà ââåäåì íåêîòîðûå äîïîëíèòåëüíûå îïðåäåëåíèÿ. Ïóñòü $x XÎ — íåêîòîðàÿ ôèêñèðîâàííàÿ òî÷êà. Îáîçíà÷èì K z x z Xx$ { \| $ , }= + Î >l l 0 êîíóñ äîïóñòèìûõ íàïðàâëåíèé â òî÷êå $x . Â ñëó÷àå ïî- ëèýäðàëüíîãî ìíîæåñòâà X êîíóñ Kx$ çàìêíóò. Îáîçíà÷èì Kx$ * êîíóñ, äâîéñòâåí- íûé êîíóñó Kx$ : K u uz z Kx x$ * ${ \| , }= £ Î0 . Çàìåòèì, ÷òî åñëè y x u u Kx= + Î$ , $ * , òî äëÿ ëþáîãî x XÎ âûïîëíÿåòñÿ íåðàâåíñòâî ( $ )( $ ) ( $ )y x x x u x x- - = - £ 0 , ïîñêîëüêó x x Kx- Î$ $ . Ñëåäîâàòåëüíî, $ ( )x P yX= , ò.å. $x ÿâëÿåòñÿ ïðîåêöèåé y íà X . Âî ââåäåííûõ îáîçíà÷åíèÿõ äàííûé ðåçóëüòàò ìîæåò áûòü ñôîðìóëèðîâàí êàê ñëåäóþùåå óòâåðæäåíèå. Òåîðåìà 2. Ïóñòü òðàíñïîðòíàÿ çàäà÷à (13)–(15) èìååò åäèíñòâåííîå ðåøå- íèå $x . Òîãäà ñóùåñòâóåò e > 0 òàêîå, ÷òî P c c x c x c X x X - æ è ç ö ø ÷ + = + = + Îe e e e 2 2 2 min $ äëÿ âñåõ 0< £e e. Äîêàçàòåëüñòâî. Îïðåäåëèì äëÿ $x ñîîòâåòñòâóþùèå êîíóñû Kx$ è Kx$ * . Â ñèëó åäèíñòâåííîñòè ðåøåíèÿ èìååì - - <c x x( $ ) 0 äëÿ ëþáîãî x XÎ . Ñëåäîâà- òåëüíî, - Îc Kxint $ * , ÷òî äîêàçûâàåò è íåïóñòîòó âíóòðåííîñòè int Kx$ * . Òîãäà - = - - = + - - = + c x c x x x c x z e e e e e e$ $ $ ( $ ) $ 1 1 , ãäå z c x Kxe e= - - Î$ $ int äëÿ äîñòàòî÷íî ìàëûõ e . Ñîîòâåòñòâåííî 1 e ez KxÎ $ è $ $x P x z P c X X= + æ è ç ö ø ÷ = - æ è ç ö ø ÷ 1 e e e , ÷òî è òðåáî- âàëîñü äîêàçàòü. n Ïðèâåäåííàÿ òåîðåìà ïîçâîëÿåò â óñëîâèÿõ åäèíñòâåííîñòè ðåøåíèÿ çàäà÷è ëè- íåéíîãî ïðîãðàììèðîâàíèÿ ñâåñòè åå ê ñïåöèàëüíîé çàäà÷å êâàäðàòè÷íîãî ïðîãðàì- ìèðîâàíèÿ ñ ïðîñòåéøåé êâàäðàòè÷íîé ôîðìîé, ÷òî íàìíîãî óïðîùàåò ðåøåíèå. ÂÛ×ÈÑËÈÒÅËÜÍÛÅ ÝÊÑÏÅÐÈÌÅÍÒÛ Òðàíñïîðòíàÿ çàäà÷à ñ òðåìÿ ïîñòàâùèêàìè. Ïðîåêöèîííûé àëãîðèòì SPACLIP áûë ðåàëèçîâàí íà ñâîáîäíî ðàñïðîñòðàíÿåìîé ñèñòåìå ìàòðè÷- íî-âåêòîðíûõ âû÷èñëåíèé Octave [35]. Ñèíòàêñèñ Octave âåñüìà áëèçîê ê MATLAB, è ýòà ñèñòåìà ÿâëÿåòñÿ óäîáíûì èíñòðóìåíòîì äëÿ ðàçðàáîòêè ïèëîòíûõ âåðñèé âû÷èñëèòåëüíûõ àëãîðèòìîâ è áûñòðîãî ïðîòîòèïèðîâàíèÿ. Ïîñëå ïðîâåðêè ðàáîòîñïîñîáíîñòè ðåàëèçîâàííîãî àëãîðèòìà íà ðÿäå çàäà÷ ÍÄÎ äàííûé ìåòîä áûë ïðèìåíåí äëÿ ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ òðàíñ- ïîðòíîé ëîãèñòèêè ñ ïîìîùüþ ïðèåìîâ, îïèñàííûõ â ïðåäûäóùåì ðàçäåëå. Âíà÷àëå áûëà ðåøåíà òðàíñïîðòíàÿ çàäà÷à ñ òðåìÿ ïîñòàâùèêàìè è ÷åòûðü- ìÿ ïîòðåáèòåëÿìè (ñîîòâåòñòâåííî n m1 13 4= =, , à âåêòîð x äëÿ ýòîé çàäà÷è ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 145 èìååò ðàçìåðíîñòü 3 4* = 12), ïðèâåäåííàÿ â [30]. Çàäàííàÿ ìàòðèöà òàðèôîâ { } , , cij i j=1 3 4 ïðåîáðàçóåòñÿ â âåêòîð c = ( , , , , , , , , , , , )7 8 1 2 4 5 9 8 9 2 3 6 . Ïî óñëîâèþ çàïàñû ïðîäóêòà ñîñòàâëÿþò Ai = [ , , ]200 180 190 , à ïîòðåáíîñòè â ïðîäóêòå — B j = [ , , , ]150 130 150 140 . Íèæíÿÿ ãðàíèöà xij low áûëà óñòàíîâëåíà ðàâíîé íóëþ, âåðõíÿÿ ãðàíèöà xij up = 200 , i n j m= =1 11 1, , , , ,K K . Ðåçóëüòàòû ðåøåíèÿ äàííîé òðàíñïîðòíîé çàäà÷è ïðèâåäåíû â òàáë. 1. Ïðè ðåøåíèè çàäà÷è îáà ìåòîäà çàâåðøàëè ñâîþ ðàáîòó ïî óñëîâèþ áëèçîñòè ê çíà- ÷åíèþ àðãóìåíòà. Óñëîâèå áëèçîñòè ê íóëþ íîðìû ãðàäèåíòà îïòèìàëüíîãî ðå- øåíèÿ âûïîëíåíî íå áûëî. Çíà÷åíèå e èç (16) ñîâïàäàåò ñ çàäàííîé òî÷íîñòüþ äëÿ âûáðàííûõ ìåòîäîâ íåãëàäêîé îïòèìèçàöèè — ÌÎÏ è SPACLIP — è ïðèâåäåíî â ïîñëåäíåì ñòîëáöå òàáëèöû. Óõóäøåíèå ðåçóëüòàòîâ ïðè e = -10 8 ñâÿçàíî ñ îãðà- íè÷åíèÿìè ðåàëèçàöèè ÿçûêà Octave íà ðàçðÿäíîñòü. Â öåëîì îáà ìåòîäà ñïðàâèëèñü ñ ðåøåíèåì äàííîé ìîäåëüíîé çàäà÷è, ïðàâèëüíî âû÷èñëèâ îïòèìàëüíîå ðàñïðåäåëå- íèå îáúåìîâ ïðîäóêòà. Ïðè ñðàâíåíèè äàííûõ ðåçóëüòàòîâ ñ ðåçóëüòàòàìè ðåøåíèÿ çàäà÷è èç [30] îêàçàëîñü, ÷òî ìåòîäû ñåìåéñòâà îòäåëÿþùèõ ïëîñêîñòåé áîëåå ÷óâ- ñòâèòåëüíû ê áëèçîñòè âåðõíåé ãðàíèöû xij up ê ðåøåíèþ, ÷åì r-àëãîðèòì Øîðà [32]. Èìåííî ïîýòîìó âåðõíÿÿ ãðàíèöà áûëà óñòàíîâëåíà ðàâíîé 200, ïðè ìåíüøåì çíà- ÷åíèè àëãîðèòìû ñåìåéñòâà îòäåëÿþùèõ ïëîñêîñòåé â êà÷åñòâå îïòèìàëüíîãî ðåøå- íèÿ âûäàâàëè âåêòîð-êîìáèíàöèþ èç çàäàííûõ ÷èñåë-îãðàíè÷åíèé. Ó r-àëãîðèòìà òàêèõ ïðîáëåì íå âîçíèêëî. Îòìåòèì, ÷òî â òàáëèöå ïðèâåäåíû îêðóãëåííûå äî öå- ëîãî çíà÷åíèÿ êîìïîíåíòû îïòèìàëüíîãî ðåøåíèÿ x, ïîýòîìó óêàçàííûå çàòðàòû íà òðàíñïîðòèðîâêó ïðîäóêöèè ìîãóò íåçíà÷èòåëüíî îòëè÷àòüñÿ îò ïðîèçâåäåíèÿ c x× . Òðàíñïîðòíûå çàäà÷è ìàëûõ è áîëüøèõ ðàçìåðíîñòåé. Ïîñëå ðåøåíèÿ ìîäåëüíîé çàäà÷è áûëî ïðîâåäåíî ìàññîâîå òåñòèðîâàíèå ïðîåêöèîííîãî àëãî- ðèòìà íà ñåðèè òðàíñïîðòíûõ çàäà÷ ìàëîé è áîëüøîé ðàçìåðíîñòè ñî ñëó÷àéíî ñãåíåðèðîâàííûìè äàííûìè. Äëÿ êàæäîé èç ýòèõ çàäà÷ n m n1 1= = ; âåêòîð òàðèôîâ c ãåíåðèðóåòñÿ ñëó- ÷àéíûì îáðàçîì êàê âåêòîð ðàçìåðíîñòè n2 , ñîñòîÿùèé èç ñëó÷àéíûõ ÷èñåë, ïðèíàäëåæàùèõ îòðåçêó [1, 101]. Çàòåì (òàêæå ñëó÷àéíûì îáðàçîì) ãåíåðèðîâàë- ñÿ âåêòîð xopt ðàçìåðíîñòè n2 — äîïóñòèìîå ðåøåíèå çàäà÷è (ñ êîìïîíåíòàìè èç äèàïàçîíà [1, 1001]). Òîãäà âåêòîð b , ðàâíûé [ , ]A Bi j T , âû÷èñëÿåòñÿ ïî ôîð- 146 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 Ò à á ë è ö à 1 . Ðåçóëüòàòû ðåøåíèÿ òðàíñïîðòíîé çàäà÷è ñ òðåìÿ ïîñòàâùèêà- ìè ñ ïîìîùüþ ÌÎÏ è SPACLIP Ìåòîä Êîìïîíåíòû âåêòîðà x Êîëè÷å- ñòâî èòåðà- öèé Òðàíñ- ïîðòíûå çàòðàòû (13) e x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 ÌÎÏ 0 0 61 136 150 27 0 0 0 97 90 0 75 1532 10 4- SPACLIP 0 0 56 141 146 28 0 0 0 101 87 0 63 1527 10 4- ÌÎÏ 0 0 57 136 145 28 0 0 0 104 83 0 60 1506 10 5- SPACLIP 0 0 55 145 146 24 0 0 0 99 90 0 54 1514 10 5- ÌÎÏ 0 0 54 148 148 24 0 0 0 101 83 0 46 1514 10 6- SPACLIP 0 0 96 167 123 61 0 0 0 166 154 0 53 2024 10 6- ÌÎÏ 0 0 65 154 166 19 0 0 0 106 95 0 41 1628 10 7- SPACLIP 0 0 30 59 81 54 0 0 0 108 200 0 100 1557 10 7- ÌÎÏ 0 0 61 152 138 62 0 0 0 103 83 0 35 1680 10 8- SPACLIP 0 0 200 100 100 0 0 0 0 0 200 0 38 1401 10 8- ìóëå b A x= × opt . Íèæíèå è âåðõíèå ãðàíèöû íà îáúåìû ïîñòàâîê çàäàþòñÿ óìíîæåíèåì äîïóñòèìîãî ðåøåíèÿ íà 0.1 è 20 ñîîòâåòñòâåííî. Çíà÷åíèå e èç (16) ïðèðàâíèâàåòñÿ ê çàäàííîé ïîëüçîâàòåëåì òðåáóåìîé òî÷íîñòè ðåøåíèÿ çàäà÷è. Â êà÷åñòâå íà÷àëüíîãî ïðèáëèæåíèÿ âîçüìåì ñëó÷àéíûé âåêòîð ðàçìåðíîñòè n2 ñ êîìïîíåíòàìè èç äèàïàçîíà [0, 10]. Äàëåå ïðîâîäèòñÿ òåñòèðîâàíèå íà òûñÿ÷àõ îäíîòèïíûõ çàäà÷ è ðåçóëüòàòû îáðàáàòûâàþòñÿ ïî ìåòîäèêå èç [34] ñ ïîñòðîå- íèåì ïðîôèëåé ïðîèçâîäèòåëüíîñòè. Ïðîôèëåì ïðîèçâîäèòåëüíîñòè (performance profile [34]) r s äëÿ ìåòîäà ðå- øåíèÿ îïòèìèçàöèîííîé çàäà÷è íàçûâàåòñÿ ôóíêöèÿ ðàñïðåäåëåíèÿ êàêîãî-ëèáî èçìåðèìîãî ïîêàçàòåëÿ ïðîèçâîäèòåëüíîñòè. Âû÷èñëåíèå ïðîôèëåé ïðîèçâîäè- òåëüíîñòè ïîçâîëÿåò âèçóàëèçèðîâàòü ðàçëè÷èÿ ïî ýôôåêòèâíîñòè íåñêîëüêèõ îïòèìèçàöèîííûõ ìåòîäîâ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 147 Ðèñ. 4. Ïðîôèëè ïðîèçâîäèòåëüíîñòè äëÿ ñòàíäàðòíîãî ÌÎÏ (SPA), àëãîðèòìà SPACLIP è r-àëãîðèòìà, òðàíñïîðòíàÿ çàäà÷à ðàçìåðíîñòè 100 ïåðåìåííûõ t Performance profile e = -10 10 Ðèñ. 5. Ïðîôèëè ïðîèçâîäèòåëüíîñòè äëÿ ñòàíäàðòíîãî ÌÎÏ (SPA), àëãîðèòìà SPACLIP è r-àëãîðèòìà, òðàíñïîðòíàÿ çàäà÷à ðàçìåðíîñòè 10000 ïåðåìåííûõ t Performance profile e = -10 10 Ôóíêöèÿ ðàñïðåäåëåíèÿ íàõîäèòñÿ ñëåäóþùèì îáðàçîì: r t ts p p s n p P r( ) \| : \|,= Î £ 1 ; r t t s S p s p s p s , , ,min{ : } = Î . Çäåñü S — ìíîæåñòâî ñðàâíèâàåìûõ ìåòîäîâ, P — ìíîæåñòâî ðåøàåìûõ ñ ïî- ìîùüþ ýòèõ ìåòîäîâ çàäà÷. Êîëè÷åñòâî ýëåìåíòîâ â P îáîçíà÷åíî ÷åðåç np , ns — êîëè÷åñòâî ýëåìåíòîâ â S . Â äàííîì ñëó÷àå ns = 3 (ñðàâíèâàþòñÿ òðè ìå- òîäà, â òîì ÷èñëå r-àëãîðèòì) èëè ns = 2 (ñðàâíèâàþòñÿ ñòàíäàðòíûé ÌÎÏ è SPACLIP), np = 5000 . Â êà÷åñòâå èçìåðèìîãî ïîêàçàòåëÿ ïðîèçâîäèòåëüíîñòè t p s, îöåíèâàëîñü çàòðà÷åííîå íà ðåøåíèå çàäà÷è ïðîöåññîðíîå âðåìÿ. Òåñòèðîâàíèå ïðîâîäèëîñü íà êîìïüþòåðå ïîä óïðàâëåíèåì ÎÑ Linux, äèñ- òðèáóòèâ openSUSE 12.3 Dartmouth, ïðîöåññîð AMD Athlon 64 3500+, 2 Ãá îïå- ðàòèâíîé ïàìÿòè; âåðñèÿ èíòåðïðåòàòîðà Octave 3.6.4. Ðåçóëüòàòû òåñòèðîâàíèÿ ïðèâåäåíû íà ðèñ. 4–7. Áûëè ðåøåíû çàäà÷è ñî 100 ïåðåìåííûìè (n =10), 10000 ïåðåìåííûìè (n =100), 40000 ïåðåìåííûìè (n = 200). Äëÿ êàæäîé ðàçìåð- íîñòè áûëî ðåøåíî 5000 òðàíñïîðòíûõ çàäà÷. 148 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 Ðèñ. 6. Ïðîôèëè ïðîèçâîäèòåëüíîñòè äëÿ ñòàíäàðòíîãî ÌÎÏ è àëãîðèòìà SPACLIP, òðàíñïîðòíàÿ çàäà÷à ðàçìåðíîñòè 10000 ïåðåìåííûõ t Performance profile e = -10 12 Ðèñ. 7. Ïðîôèëè ïðîèçâîäèòåëüíîñòè äëÿ ñòàíäàðòíîãî ÌÎÏ è ÌÎÏ ñ äîïîëíèòåëüíûìè îòñå÷åíè- ÿìè, òðàíñïîðòíàÿ çàäà÷à ðàçìåðíîñòè 40000 ïåðåìåííûõ t Performance profile e = -10 12 Àíàëèç ïîëó÷åííûõ ïðîôèëåé ïðîèçâîäèòåëüíîñòè ïîêàçûâàåò, ÷òî ïðè ðå- øåíèè òðàíñïîðòíûõ çàäà÷ ìàëûõ ðàçìåðíîñòåé r-àëãîðèòì ðàáîòàåò áûñòðåå, ÷åì ïðîåêöèîííûé àëãîðèòì SPACLIP. Còàíäàðòíûé ÌÎÏ äëÿ çàäà÷ òàêèõ ðàç- ìåðíîñòåé òàêæå îïåðåæàåò ïðîåêöèîííûé àëãîðèòì SPACLIP. Ýòî ñâÿçàíî ñ îòñóòñòâèåì íåîáõîäèìîñòè ðåøàòü çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ (2). Íî ÷åì áîëüøå ñòàíîâèòñÿ ðàçìåðíîñòü çàäà÷è è òðåáóåìàÿ òî÷íîñòü ðåøåíèÿ, òåì áîëüøå ïðåèìóùåñòâî SPACLIP ïî ñðàâíåíèþ ñ äðóãèìè ìåòîäàìè. ÇÀÊËÞ×ÅÍÈÅ Â íàñòîÿùåé ñòàòüå ïðåäëîæåí àëãîðèòì SPACLIP ðåøåíèÿ çàäà÷ âûïóêëîé ÍÄÎ ñåìåéñòâà ìåòîäîâ îòäåëÿþùèõ ïëîñêîñòåé ñ äîïîëíèòåëüíûìè îòñå÷åíèÿìè, ïî- ðîæäàåìûìè ðåøåíèåì âñïîìîãàòåëüíîé çàäà÷è ìåòîäà ñåêóùèõ ïëîñêîñòåé, è äîêàçàíà åãî ñõîäèìîñòü. Â êà÷åñòâå ïðàêòè÷åñêîãî ïðèìåíåíèÿ àëãîðèòìà ðàñ- ñìàòðèâàåòñÿ ðåøåíèå òðàíñïîðòíûõ çàäà÷ áîëüøîé ðàçìåðíîñòè. Â óñëîâèÿõ åäèíñòâåííîñòè ðåøåíèÿ òðàíñïîðòíîé çàäà÷è äîêàçàíà ýêâèâàëåíòíîñòü çàäà÷ ïðîåêöèè äîñòàòî÷íî óäàëåííîé òî÷êè íà äîïóñòèìîå ìíîæåñòâî è çàäà÷ òðàíñ- ïîðòíîãî òèïà. Âû÷èñëèòåëüíûå ýêñïåðèìåíòû äåìîíñòðèðóþò äîâîëüíî âûñî- êóþ ýôôåêòèâíîñòü SPACLIP ïðè ðåøåíèè çàäà÷ ïðîåêöèè. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. N a m m R . V . , W o o G . Introduction to the theory and solution method for variational inequalities. — Changwon: Changwon National University Press, 2002. — 117 p. 2. C l a r k e F . N . , L e d y a e v Y . S . , S t e r n R . J . a n d W o l e n s k i P . R . Nonsmooth analysis and control theory. — New York: Springer, 1998. — 278 p. 3. Ñ å ð ã è å í ê î È . Â . , Ì è õ à ë å â è ÷ Ì . Â . , Ñ ò å ö þ ê Ï . È . , Ê î ø ë à é Ë . Á . Ìîäåëè è èí- ôîðìàöèîííûå òåõíîëîãèè äëÿ ïîääåðæêè ïðèíÿòèÿ ðåøåíèé ïðè ïðîâåäåíèè ñòðóêòóð- íî-òåõíîëîãè÷åñêèõ ïðåîáðàçîâàíèé // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 2. — C. 26–49. 4. Ñ å ð ã è å í ê î È . Â . Ìåòîäû îïòèìèçàöèè è ñèñòåìíîãî àíàëèçà äëÿ çàäà÷ òðàíñâû÷èñëèòåëü- íîé ñëîæíîñòè. — Êèåâ: Àêàäåìïåðèîäèêà, 2010. — 296 ñ. (óêð.) 5. Ø î ð Í . Ç . , Ñ ò å ö å í ê î Ñ . È . Êâàäðàòè÷íûå ýêñòðåìàëüíûå çàäà÷è è íåäèôôåðåíöèðóåìàÿ îïòèìèçàöèÿ. — Êèåâ: Íàóê. äóìêà, 1989. — 208 ñ. 6. N o c e d a l J . , W r i g h t S . Numerical optimization. Series: Springer series in operations research and financial engineering. XXII. 2nd ed. — New York: Springer, 2006. — 664 p. 7. Ï î ë ÿ ê Á . Ò . Ââåäåíèå â îïòèìèçàöèþ. — 2-å èçä. — Ì.: ËÅÍÀÍÄ, 2014. — 392 ñ. 8. Í å ì è ð î â ñ ê è é À . Ñ . , Þ ä è í Ä . Á . Ñëîæíîñòü çàäà÷ è ýôôåêòèâíîñòü ìåòîäîâ îïòèìèçà- öèè. — Ì.: Íàóêà, 1979. — 383 ñ. 9. Í å ñ ò å ð î â Þ . Å . Ââåäåíèå â âûïóêëóþ îïòèìèçàöèþ. — Ì.: ÌÖÍÌÎ, 2010. — 280 ñ. 10. Ë å â è í À . Þ . Îá îäíîì àëãîðèòìå ìèíèìèçàöèè âûïóêëûõ ôóíêöèé // Äîêëàäû ÀÍ ÑÑÑÐ. — 1965. — 160, ¹ 6. — Ñ. 1244–1247. 11. N e w m a n D . J . Location of maximum on unimodal surfaces // Journal of ACM. — 1965. — 12. — P. 395–398. 12. Ï î ë ÿ ê Á . Ò . Ìèíèìèçàöèÿ íåãëàäêèõ ôóíêöèîíàëîâ // Æóðíàë âû÷èñëèòåëüíîé ìàòåìåìà- òèêè è ìàòåìàòè÷åñêîé ôèçèêè. — 1969. — 9, ¹ 3. — Ñ. 509–521. 13. N u r m i n s k i E . A . Envelope stepsize control for iterative algorithms based on Fejer processes with attractants // Optimization Methods and Software. — 2010. — 25, N 1. — P. 97–108. 14. K i w i e l K . C . An aggregate subgradient method for nonsmooth convex minimization // Mathematical Programming. — 1983. — N 27. — P. 320–341. 15. L e m a r e c h a l C . An extension of Davidon methods to nondiffentiable problems // Non- differentiable Optimization (M.L. Balinski, P. Wolfe, eds.). Mathematical Programming Study. — 1975. — N 3. — P. 95–109. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4 149 16. W o l f e P . A method of conjugate subgradients for minimizing nondifferentiable functions // Nondifferentiable Optimization (M.L. Balinski, P. Wolfe, eds.). Mathematical Programming Study. — 1975. — N 3. — P. 145–173. 17. L e m a r e c h a l C . , N e m i r o v s k i i A . a n d N e s t e r o v Y u . New variants of bundle methods // Mathematical Programmming. — 1995. — N 69. — P. 111–148. 18. M i f f l i n R . , S a g a s t i z a b a l C . A VU-algorithm for convex minimization // Mathematical Programming. — 2005. — N 104. — P. 583–608. 19. N e s t e r o v Y u . Introductory lectures on convex optimization: A basic course. — Boston: Kluwer Academic Publishers, 2004. — 236 p. 20. N e s t e r o v Y u . Smooth minimization of non-smooth functions // Mathematical Programming. — 2005. — N 103. — P. 127–152. 21. N u r m i n s k i E . A . Separating plane algorithms for convex optimization // Mathematical Programming. — 1997. — N 76. — P. 373–391. 22. Í ó ð ì è í ñ ê è é Å . À . Ìåòîä îòäåëÿþùèõ ïëîñêîñòåé ñ îãðàíè÷åííîé ïàìÿòüþ äëÿ ðåøåíèÿ çàäà÷ âûïóêëîé íåãëàäêîé îïòèìèçàöèè // Âû÷èñëèòåëüíûå ìåòîäû è ïðîãðàììèðîâàíèå. — 2006. — 7. — Ñ. 133–137. 23. V o r o n t s o v a E . A . A projective separating plane method with additional clipping for non-smooth optimization // WSEAS Transactions on Mathematics. — 2014. — 13. — P. 115–121. 24. Ä å ì ü ÿ í î â Â . Ô . , Â à ñ è ë ü å â Ë . Â . Íåäèôôåðåíöèðóåìàÿ îïòèìèçàöèÿ. — Ì.: Íàóêà, 1981. — 384 ñ. 25. Í ó ð ì è í ñ ê è é Å . À . ×èñëåííûå ìåòîäû âûïóêëîé îïòèìèçàöèè. — Ì.: Íàóêà, 1991. — 168 ñ. 26. Í ó ð ì è í ñ ê è é Å . À . Î ñõîäèìîñòè ìåòîäà ïîäõîäÿùèõ àôôèííûõ ïîäïðîñòðàíñòâ äëÿ ðå- øåíèÿ çàäà÷è î íàèìåíüøåì ðàññòîÿíèè äî ñèìïëåêñà // Æóðíàë âû÷èñëèòåëüíîé ìàòåìàòèêè è ìàòåìàòè÷åñêîé ôèçèêè. — 2005. — 45, âûï. 11. — Ñ. 1996-2004. 27. N u r m i n s k i E . A quadratically convergent line-search algorithm for piecewise smooth convex optimization // Optimization Methods and Software. — 1995. — N 6. — P. 59–80. 28. Â î ð î í ö î â à Å . À . Áûñòðî ñõîäÿùèéñÿ àëãîðèòì ëèíåéíîãî ïîèñêà â íåäèôôåðåíöèðóåìîé îïòèìèçàöèè // Èíôîðìàòèêà è ñèñòåìû óïðàâëåíèÿ. — 2012. — ¹ 2. — C. 39–48. 29. Ñ ò å ö þ ê Ï . È . , Í ó ð ì è í ñ ê è é Å . À . Íåãëàäêèé øòðàô è ñóáãðàäèåíòíûå àëãîðèòìû äëÿ ðåøåíèÿ çàäà÷è ïðîåêöèè íà ïîëèòîï // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 1. — Ñ. 59–63. 30. Ñ ò å ö þ ê Ï . È . , Í ó ð ì è í ñ ê è é Å . À . , Ñ î ë î ì î í Ä . È . Òðàíñïîðòíàÿ çàäà÷à è îðòîãî- íàëüíîå ïðîåêòèðîâàíèå íà ëèíåéíûå ìíîãîîáðàçèÿ // Ìàòåðèàëû V ìåæäóíàðîäíîé íàó÷íîé êîíôåðåíöèè «Òðàíñïîðòíûå ñèñòåìû è ëîãèñòèêà» (Êèøèíåó, Ìîëäîâà, 11–13 äåêàáðÿ 2013 ã.). — Êèøèíåó: Ýâðèêà, 2013. — Ñ. 251–263. 31. Ï ø å í è ÷ í û é Á . Í . Âûïóêëûé àíàëèç è ýêñòðåìàëüíûå çàäà÷è. — Ì.: Íàóêà, Ãëàâíàÿ ðå- äàêöèÿ ôèçèêî-ìàòåìàòè÷åñêîé ëèòåðàòóðû, 1980. — 320 ñ. 32. Ø î ð Í . Ç . Ìåòîäû íåäèôôåðåíöèðóåìîé îïòèìèçàöèè è ñëîæíûå ýêñòðåìàëüíûå çàäà÷è. — Êèøèíýó: Ýâðèêà, 2008. — 270 ñ. 33. Þ ä è í Ä . Á . , Ã î ë ü ø ò å é í Å . Ã . Çàäà÷è è ìåòîäû ëèíåéíîãî ïðîãðàììèðîâàíèÿ: Çàäà÷è òðàíñïîðòíîãî òèïà. — 3-e èçä. — Ì.: Êíèæíûé äîì «Ëèáðîêîì», 2010. — 184 ñ. 34. D o l a n E . , M o r e J . Benchmarking optimization software with performance profiles // Mathematical Programming. — 2002. — N 91. — P. 201–213. 35. O c t a v e P a g e [Ýëåêòðîííûé ðåñóðñ]. — Ðåæèì äîñòóïà: http://www.gnu.org/software/octave/. 36. K e l l e y J . E . The cutting plane method for solving convex programs // Journal of the SIAM. — 1960. — 8 (4). — P. 703–712. 37. Ø î ð Í . Ç . Ïðèìåíåíèå ìåòîäà ãðàäèåíòíîãî ñïóñêà äëÿ ðåøåíèÿ ñåòåâîé òðàíñïîðòíîé çà- äà÷è // Ìàòåðèàëû íàó÷íîãî ñåìèíàðà ïî òåîðåòè÷åñêèì è ïðèêëàäíûì âîïðîñàì êèáåðíåòè- êè è èññëåäîâàíèé îïåðàöèé: Íàó÷íûé ñîâåò ïî êèáåðíåòèêå ÀÍ ÓÑÑÐ. — 1962. — Âûï. 1. — Êèåâ. — Ñ. 9–17. Ïîñòóïèëà 27.10.2014 150 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 4

Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации

Institution

Similar Items