Двойственная квадратичная оценка для линейной задачи дополнительности

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2017
Hauptverfasser:	Березовский, О.А., Бардадым, Т.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2017
Schriftenreihe:	Компьютерная математика
Schlagworte:	Теория и методы оптимизации
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/168444
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:	Двойственная квадратичная оценка для линейной задачи дополнительности / О.А. Березовский, Т.А. Бардадым // Компьютерная математика. — 2017. — № 1. — С. 134-139. — Бібліогр.: 12 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-168444
record_format	dspace
spelling	irk-123456789-1684442020-05-03T01:26:27Z Двойственная квадратичная оценка для линейной задачи дополнительности Березовский, О.А. Бардадым, Т.А. Теория и методы оптимизации Для линейной задачи дополнительности рассмотрена эквивалентная постановка в виде квадратичной экстремальной задачи, которая имеет точную двойственную оценку, если решение исходной задачи существует. Предложен путь нахождения приближения к одному из решений квадратичной экстремальной задачи общего вида двойственным подходом в случае точной двойственной оценки. Для лінійної задачі комплементарності розглянута еквівалентна постановка у вигляді квадратичної екстремальної задачі, яка має точну двоїсту оцінку, якщо розв’язок початкової задачі існує. Запропоновано шлях знаходження наближення до одного з розв’язків квадратичної екстремальної задачі загального вигляду двоїстим підходом у разі точної двоїстої оцінки. For the linear complementarity problem, the equivalent formulation in the form of a quadratic extremal problem is considered. If the solution of the original problem exists, then this quadratic extremal problem has an exact dual estimate. We propose a way of finding an approximation to one of the solutions of a quadratic extremal problem of general form by a dual approach in the case of an exact dual estimate. 2017 Article Двойственная квадратичная оценка для линейной задачи дополнительности / О.А. Березовский, Т.А. Бардадым // Компьютерная математика. — 2017. — № 1. — С. 134-139. — Бібліогр.: 12 назв. — рос. 2616-938Х http://dspace.nbuv.gov.ua/handle/123456789/168444 519.85 ru Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України
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	2017
topic_facet	Теория и методы оптимизации
url	http://dspace.nbuv.gov.ua/handle/123456789/168444
citation_txt	Двойственная квадратичная оценка для линейной задачи дополнительности / О.А. Березовский, Т.А. Бардадым // Компьютерная математика. — 2017. — № 1. — С. 134-139. — Бібліогр.: 12 назв. — рос.
series	Компьютерная математика
work_keys_str_mv	AT berezovskijoa dvojstvennaâkvadratičnaâocenkadlâlinejnojzadačidopolnitelʹnosti AT bardadymta dvojstvennaâkvadratičnaâocenkadlâlinejnojzadačidopolnitelʹnosti
first_indexed	2025-07-15T03:13:37Z
last_indexed	2025-07-15T03:13:37Z
_version_	1837681048606998528
fulltext	134 Компьютерная математика. 2017, № 1 Теория и методы оптимизации Для линейной задачи дополнитель- ности рассмотрена эквивалент- ная постановка в виде квадратич- ной экстремальной задачи, кото- рая имеет точную двойственную оценку, если решение исходной задачи существует. Предложен путь нахождения приближения к одному из решений квадратичной экстремальной задачи общего ви- да двойственным подходом в слу- чае точной двойственной оценки.  О.А. Березовский, T.А. Бардадым, 2017 УДК 519.85 О.А. БЕРЕЗОВСКИЙ, Т.А. БАРДАДЫМ ДВОЙСТВЕННАЯ КВАДРАТИЧНАЯ ОЦЕНКА ДЛЯ ЛИНЕЙНОЙ ЗАДАЧИ ДОПОЛНИТЕЛЬНОСТИ Введение. Линейная задача дополнительно- сти (ЛЗД), состоит в нахождении вектора ,nx R такого что 0Mx q  , (1) 0x  , (2) ( ) 0Tx Mx q  , (3) для заданных матрицы M размера nn и вектора nq R . Если все элементы вектора q неотрица- тельны, то задача (1) – (3) имеет очевидное решение 0.x  В общем случае ЛЗД – это NP-трудная задача. Как показано в [1] (со ссылкой на [2]), ЛЗД с нижне- треугольной отрицательно определенной матрицей M специального вида эквивалент- на задаче о рюкзаке. Выделение задач дополнительности в са- мостоятельный класс часто связывают с ра- ботами [3, 4], хотя условие дополнитель- ности появилось значительно раньше при решении вариационных неравенств (см., например, ссылки в [5, 6]) . В работе [3] показано, что если матрица M положитель- но определена (не обязательно симметрич- на), то в задаче квадратичного программиро- вания, которая эквивалентна ЛЗД, * min ) 2 T T TM Mf x x x q           , (4) 0Mx q  , (5) 0x  , (6) оптимальное значение целевой функции ДВОЙСТВЕННАЯ КВАДРАТИЧНАЯ ОЦЕНКА ДЛЯ ЛИНЕЙНОЙ ЗАДАЧИ ДОПОЛНИТЕЛЬНОСТИ Компьютерная математика. 2017, № 1 135 f равно нулю. В работе [4] этот результат обобщен для случая, когда все главные миноры матрицы M положительны. Для решения ЛЗД применяются алгоритм Лемке или его модификации [5, 6], модификации метода внутренних точек [7], алгоритмы на основе теории глобального поиска для минимизации разности выпуклых функций (d.c. functions) [8], алгоритм с использованием определенной очередности перехода односторонних связей механических систем в альтернативное состояние [9] и др. В данной работе будет рассмотрена возможность применения для решения ЛЗД двойственных квадратичных оценок [10]. Напомним, что двойственная оценка  оптимального значения целевой функции f квадратичной экстремальной задачи 0inf ( ) nz T R f f z    , (7) где { : ( ) 0, , ( ) 0, }i iT z f z i I f z j J     , ( ) T T i i i if z z A z b z c   , {0}i I J   – квадратичные функции в n -мерном пространстве, определяется следующим образом [10]: * * ( ) 0, sup ( ) , A u u U u f         (8) где ( ) inf ( , ), nz R u L z u    ( , ) ( ) ( ) ( )T TL z u z A u z b u z c u   – функция Лагранжа для задачи (7), { : 0, }iU u u i I    , ( ) 0A u  ( ( ) 0A u  ) определяет множество двойственных переменных, при которых матрица ( )A u неотрицательно (поло- жительно) определена. Принимая во внимание неоднозначность постановки квадратичных оптими- зационных задач, соответствующих задаче (1) – (3), можно получать различные результаты. Например, для задачи (4) – (6), если матрица 2 TM M      положительно определена, то в результате применения двойственного подхода (нахождения двойственной оценки (8)) получаем как точную оценку * * 0,f   так и точку минимума, которая удовлетворяет условиям (1) – (3). Если же 2 TM M      является отрицательно определенной матрицей, множество { : 0, }mu u A u R   пусто и двойственная оценка  (8) не определена. Это соответствует тому, что значение оценки, полученной лагранжевой релаксацией этой задачи, равно . Рассмотрим другую квадратичную постановку , min ( ) ( ), n n T x R y R f y Mx q y Mx q        (9) 0,x  (10) 0,y  (11) ( , ) 0.x y  (12) О.А. БЕРЕЗОВСКИЙ, Т.А. БАРДАДЫМ Компьютерная математика. 2017, № 1136 Эта задача всегда имеет не пустую область определения (10) – (12) и конечное значение глобального минимума. Если минимальное значение f целевой функции задачи (9) – (12) равно нулю, множество ее решений совпадает с мно- жеством решений ЛЗД (1) – (3); если же 0,f  то ЛЗД не имеет решений. Функция Лагранжа для задачи (9) – (12) равна 1 2 3( , , ) ( ) ( )T T T TL x y u y Mx q y Mx q u x u y u x y         ( ) ( ) ( ),T Tz A u z b u z c u   где x z y        , 1 2 3 u u u u           – вектор двойственных переменных, 1 ,nu R 2 ,nu R 1 3 ,u R 3 3 ( ) T TM M M u I A u M u I I         , 1 2 2 ( ) 2 TM q u b u q u        , ( ) Tc u q q . При * 0u  имеем ( , ) ( ) ( )TL z u y Mx q y Mx q     . Тогда, если ЛЗД имеет решение, то 0f  и функция * ( , )L z u f представима в виде суммы квадратов линейных форм, что является необ- ходимым и достаточным условием получения точной двойственной оценки (т. е. f  ) [11, теорема 4]. Однако при данном значении u мы не получим искомые x и ,y так как оптимальное значение двойственной оценки * 0  достигается для произвольного x при y Mx q   . Рассмотрим один из возмож- ных приемов, который в ряде случаев дает возможность все же получить решение исходной ЛЗД. Для произвольной квадратичной экстремальной задачи (7) с оптимальным значением f в точке z справедливо Утверждение 1. Если * * ( ) ,u f    то * ( ) arg min ( , ). z z Z u L z u  Доказательство. Допустим противное: пусть * ( ) arg min ( , ), z z Z u L z u  т. е. * * * * ( , ) ( ) ( ( ), )L z u u L z u u f    . Но для функции Лагранжа для u U   и z T  справедливо 0( , ) ( )L z u f z . Поскольку ,u U  * ,z T то * ( , )L z u  ( ) .f z f  Получили противоречие, которое доказывает справедливость утверждения. ДВОЙСТВЕННАЯ КВАДРАТИЧНАЯ ОЦЕНКА ДЛЯ ЛИНЕЙНОЙ ЗАДАЧИ ДОПОЛНИТЕЛЬНОСТИ Компьютерная математика. 2017, № 1 137 Если двойственная оценка точная и достигается при некотором векторе двойственных переменных ,u то согласно утверждению 1 множество Z точек глобального минимума задачи (7) принадлежит множеству ( )Z u решений внутренней задачи inf ( , ) nz R L z u  в (8). Таким образом, задача нахождения точки глобального минимума при условии точной двойственной оценки сводится к вопросу ее выделения из множества ( ).Z u Утверждение 2. Если * ,f  то существует такое  -возмущение элементов матрицы 0A и вектора 0b целевой функции задачи (7), что для возмущенной задачи решение u задачи (8) удовлетворяет условию ( ) 0A u  и, следовательно, z определяется точно. Доказательство. Поскольку оценка точная ( * f  ), то функция ( , )L z u f представима в виде суммы квадратов линейных форм [11, теорема 4], причем из доказательства этой теоремы следует, что * * * 2 * 1 ( , ) ( )( ( ), ( )) , n i i i L z u u u z z u f       где ( )i u – собственные числа, а ( )i u – собственные вектора матрицы ( )A u , ( )z u – точка, к которой стремится последовательность решений внутренней задачи 1( ) ( ) ( ) / 2z u A u b u  при u u (подчеркнем, что ( )z u не обязательно удовлетворяет ограничениям исходной задачи и, соответственно, не обязательно является ее решением). Определим множество ( )J u : ( )j J u , если ( ) 0j u  . Выбрав некоторое решение z задачи (7), построим возмущенную задачу * * * * 2 0 ( ) inf ( ) ( , ) ) n j j z T R j J u f f z z z                , которая имеет то же оптимальное значение и ту же точку глобального минимума, что и исходная задача. Для нее двойственная оценка (8) достигается при том же векторе двойственных переменных ,u что для исходной задачи, и *    (т. е. является точной). Но матрица ( )A u не вырождена (положи- тельно определена), и, следовательно, ( ) .z u z  Доказательство завершено. Из приведенных рассуждений при доказательстве последнего утверждения следует и способ построения возмущения исходной задачи (7), который может позволить получить приближение к ее определенному решению. Если ( )z u достигается в недопустимой точке, т. е. когда ( )A u вырожденная матрица, вводится возмущение матрицы в целевой функции 0 0A A A   так, чтобы О.А. БЕРЕЗОВСКИЙ, Т.А. БАРДАДЫМ Компьютерная математика. 2017, № 1138 ( )A u A была не вырожденной (для этого достаточно * * 2 ( ) ( , )j j j J u A x     ). Например, если использовать ,A I   где I – единичная матрица, то в резуль- тате решения возмущенной задачи получим приближение к точке глобального экстремума исходной задачи, которая наименее удалена от центра координат. В случае, если такое решение не единственно, следует возмутить и линейную часть целевой функции 0 0b b b   , т. е. добавить сдвиг, который убирает эту неоднозначность. Часто достаточно одного сдвига, чтобы получить необходимый результат [12]. Выше рассмотрена ситуация, когда решение ЛЗД существует. К сожалению, применяя двойственный подход к решению задачи не всегда можно выяснить, существует ли это решение. Объясняется это тем, что двойственная оценка  (8) в случае несовместности системы (1) – (3) может принимать как положи- тельное значение, так и нулевое. Если 0  говорит о том, что решение ЛЗД не существует, то при * 0  ситуация неопределенная. В последнем случае ( * 0  ) нередко все же удается путем введением избыточных ограничений уточнить оценку * . Например, можно заменить ограничение (12) на эквивалентную систему равенств ( , ) 0i ix y  , 1, ,i n добавить ограничения, которые являются следствием неравенств (10), (11), 0i jx x  , 0i jy y  , 0i jx y  , i j , 1,i n , 1,j n и другие ограничения. Эти ограничения не меняют допустимую область задачи (9) – (12), но изме- няют функцию Лагранжа, что может привести к уточнению двойственной оценки. В результате введения таких ограничений двойственная оценка может принять положительное значение, и неоднозначность будет исключена. Работа выполнена при поддержке НАН Украины, проект 0117U000327. О.А. Березовський, Т.О. Бардадим ДВОЇСТА КВАДРАТИЧНА ОЦІНКА ДЛЯ ЛІНІЙНОЇ ЗАДАЧІ КОМПЛЕМЕНТАРНОСТІ Для лінійної задачі комплементарності розглянута еквівалентна постановка у вигляді квадра- тичної екстремальної задачі, яка має точну двоїсту оцінку, якщо розв’язок початкової задачі існує. Запропоновано шлях знаходження наближення до одного з розв’язків квадратичної екстремальної задачі загального вигляду двоїстим підходом у разі точної двоїстої оцінки. O.A. Berezovskyi, T.A. Bardadym DUAL QUADRATIC ESTIMATE FOR LINEAR COMPLEMENTARITY PROBLEM For the linear complementarity problem, the equivalent formulation in the form of a quadratic extremal problem is considered. If the solution of the original problem exists, then this quadratic extremal problem has an exact dual estimate. We propose a way of finding an approximation to one of the solutions of a quadratic extremal problem of general form by a dual approach in the case of an exact dual estimate. ДВОЙСТВЕННАЯ КВАДРАТИЧНАЯ ОЦЕНКА ДЛЯ ЛИНЕЙНОЙ ЗАДАЧИ ДОПОЛНИТЕЛЬНОСТИ Компьютерная математика. 2017, № 1 139 1. Pardalos P.M., Rosen J.B. Global optimization approach to the linear complementarity problem. SIAM Journal on Scientific and Statistical Computing. 1988. 9(2). P. 341 – 353. 2. Chung S.J., Murty R.G. Polynomially bounded ellipsoid algorithm for convex quadratic programming. In O.L. Mangassarian, R.R. Meyer, S.M. Robinson (editors): Nonlinear programming 4. Academic Press, 1981. P. 439 – 485. 3. Dorn W.S. Self-dual quadratic program. SIAM J. Appl. Math. 1963. 9(1). P. 51 – 54. 4. Dantzig G.B., Cottle R.W. Positive (semi-) definite programming. In: Nonlinear Programming. A Course. Ed. J. Abadie. Amsterdam: Noth-Holland, 1967. P. 55 – 73. 5. Реклейтис Г., Рейвиндран А., Рэгдел К. Оптимизация в технике. Т. 2. М.: Мир, 1986. 134 с. 6. Попов Л.Д. Введение в теорию, методы и экономические приложения задач о допол- нительности. Изд-во Урал. ун-та, 2001. 124 с. 7. Simantiraki E.M., Shanno D.F. An Infeasible-Interior-Point method for linear complementarity problems. Rutcor Research Report. 1996. 8. Mazurkevich E.O., Petrova E.G., Strekalovsky A.S. On the numerical solution of the linear complementarity problem. Computational Mathematics and Mathematical Physics. 2009. Т. 49, № 8. С. 1318 – 1331. 9. Колесников Г.Н., Раковская М.И. Алгоритмы решения линейной задачи о дополни- тельности и дискретные модели механических систем. Электронный журнал «Исследовано в России» http://zhurnal.ape.relarn.ru/articles/2004/164.pdf . 10. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая оптимизация. К.: Наук. думка, 1989. 208 с. 11. Березовский О.А. О точности двойственных оценок для квадратичных экстремальных задач. Кибернетика и системный анализ. 2012. № 1. С. 33 – 39. 12. Березовский О.А. О решении одной специальной оптимизационной задачи, связанной с определением инвариантных множеств динамических систем. Проблемы управления и информатики. 2015. № 3. С. 33 – 40. Получено 30.03.2017 Об авторах: Березовский Олег Анатольевич, кандидат физико-математических наук, старший научный сотрудник Института кибернетики имени В.М. Глушкова НАН Украины, E-mail: berezovskyi@mail.ru Бардадым Тамара Алексеевна, кандидат физико-математических наук, старший научный сотрудник Института кибернетики имени В.М. Глушкова НАН Украины. E-mail: tbardadym@gmail.com

Двойственная квадратичная оценка для линейной задачи дополнительности

Institution

Ähnliche Einträge