Коническая регуляризация в задачах квадратичной оптимизации

Рассматриваются вопросы вычисления оценок оптимальных значений невыпуклых задач квадратичной оптимизации на основе лагранжевых релаксаций исходной задачи. На границе допустимой области оценочной задачи функции задачи могут быть разрывны, плохо обусловлены, что усложняет разработку вычислительных алг...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2016
Автор:	Лаптин, Ю.П.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Назва видання:	Компьютерная математика
Теми:	Теория и методы оптимизации
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/168426
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Коническая регуляризация в задачах квадратичной оптимизации / Ю.П. Лаптин // Компьютерная математика. — 2016. — № 2. — С. 129-141. — Бібліогр.: 7 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-168426
record_format	dspace
spelling	irk-123456789-1684262020-05-02T01:28:56Z Коническая регуляризация в задачах квадратичной оптимизации Лаптин, Ю.П. Теория и методы оптимизации Рассматриваются вопросы вычисления оценок оптимальных значений невыпуклых задач квадратичной оптимизации на основе лагранжевых релаксаций исходной задачи. На границе допустимой области оценочной задачи функции задачи могут быть разрывны, плохо обусловлены, что усложняет разработку вычислительных алгоритмов. В работе приводятся новые подходы преодоления указанных проблем, основанные на использовании конических регуляризаций выпуклых задач оптимизации. Розглядаються питання обчислення оцінок оптимальних значень неопуклих задач квадратичної оптимізації на основі лагранжевих релаксацій вихідної задачі. На границі допустимої області оціночної задачі функції задачі можуть бути розривні, погано обумовлені, що ускладнює розробку обчислювальних алгоритмів. У роботі наводяться нові підходи подолання зазначених проблем, засновані на використанні конічних регуляризації опуклих задач оптимізації. Calculation of estimates for optimal values for non-convex quadratic optimization problems on the base of Lagrange relaxation of the original problem is considered. At the boundary of the feasible set of the estimation problem the used functions can be discontinuous or poorly conditioned that complicates the development of numerical algorithms. The paper presents a new approach to overcome these problems, based on the use of conic regularizations of convex optimization problems. 2016 Article Коническая регуляризация в задачах квадратичной оптимизации / Ю.П. Лаптин // Компьютерная математика. — 2016. — № 2. — С. 129-141. — Бібліогр.: 7 назв. — рос. 2616-938Х http://dspace.nbuv.gov.ua/handle/123456789/168426 519.8 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	2016
topic_facet	Теория и методы оптимизации
url	http://dspace.nbuv.gov.ua/handle/123456789/168426
citation_txt	Коническая регуляризация в задачах квадратичной оптимизации / Ю.П. Лаптин // Компьютерная математика. — 2016. — № 2. — С. 129-141. — Бібліогр.: 7 назв. — рос.
series	Компьютерная математика
work_keys_str_mv	AT laptinûp koničeskaâregulârizaciâvzadačahkvadratičnojoptimizacii
first_indexed	2025-07-15T03:12:43Z
last_indexed	2025-07-15T03:12:43Z
_version_	1837680991671418880
fulltext	Компьютерная математика. 2016, № 2 129 Теория и методы оптимизации Рассматриваются вопросы вычи- сления оценок оптимальных зна- чений невыпуклых задач квадра- тичной оптимизации на основе лагранжевых релаксаций исход- ной задачи. На границе допусти- мой области оценочной задачи функции задачи могут быть раз- рывны, плохо обусловлены, что усложняет разработку вычисли- тельных алгоритмов. В работе приводятся новые подходы пре- одоления указанных проблем, ос- нованные на использовании кони- ческих регуляризаций выпуклых задач оптимизации. Ю.П. Лаптин, 2016 УДК 519.8 Ю.П. ЛАПТИН КОНИЧЕСКАЯ РЕГУЛЯРИЗАЦИЯ В ЗАДАЧАХ КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ Введение. К невыпуклым задачам квадра- тичной оптимизации (максимизации квадра- тичной формы при квадратичных ограниче- ниях) могут быть сведены самые разные многоэкстремальные задачи. Для вычисления оценок оптимальных значений таких задач применяются лагранжевы релаксации (см., например, [1, 2]) и SDP-релаксации (релакса- ции к задачам полуопределенного програм- мирования) [3], которые в определенном смысле эквивалентны. При использовании лагранжевых релаксаций формируются оце- ночные параметрические матричные задачи в пространстве двойственных переменных. Функции оценочных задач непрерывно диф- ференцируемы и принимают конечные зна- чения в областях отрицательной определен- ности матриц функций Лагранжа исходных квадратичных задач. На границе области от- рицательной определенности эти функции разрывны (в области положительной опреде- ленности принимают значения  ), а вбли- зи границы матрицы плохо обусловлены (причем количество близких к нулю собст- венных чисел может приближаться к размер- ности пространства), что приводят к необхо- димости учета этих особенностей при разра- ботке вычислительных алгоритмов решения оценочных задач. В работе приводятся новые подходы пре- одоления указанных проблем, основанные на использовании конических регуляризаций выпуклых задач оптимизации. В пункте 1 в соответствии с [1, 2] приво- дятся постановки квадратичных оптимизаци- онных задач и формулируются оценочные задачи. В пункте 2 формулируются новые Ю.П. ЛАПТИН Компьютерная математика. 2016, № 2130 результаты, касающиеся поиска по направлению в оценочных задачах. Эти результаты идейно близки алгоритму «граничного оракула», введенному в [4]. В пунктах 3, 4 приводится обобщение понятий конической регуляризации для рассматриваемого класса задач, изложенных ранее в [5]. Рассматриваются эффективные алгоритмы вычисления функций и субградиентов регуляризованой задачи. 1. Квадратичные оптимизационные задачи и оценки их оптимальных значений Постановка задачи 0sup ( ), nK K R  x x (1) при ограничениях 1( ) 0, 1,...,iK i m x ; 1( ) 0, 1,...,jK j m N  x , 1 ,m N (2) где ( ) , ,i i i iK c  x A x x l x , iA – симметричные матрицы, il – векторы соответствующих размерностей, ic R ,  0,1,..., .i N Задача (1) – (2) – многоэкстремальная в общем случае, для вычисления оцен- ки оптимального значения в [1] предложено использовать лагранжеву релакса- цию этой задачи. Обозначим  1 1( ,..., ) : 0, 1,..., .N iU u u u i m    u ( ) sup ( , ) nR L    x u x u , (3) где 0 1 ( , ) ( ) ( ) ( ) , ( ), ( ) N i i i L K u K c      x u x x A u x x l u x u , 0 1 ( ) N i i i u   A u A A , 0 1 ( ) N i i i u   l u l l , 0 1 ( ) N i i i c c u c   u . (4) Пусть T – множество допустимых решений задачи (1) – (2), ,U u тогда 0( ) sup ( , ) sup ( , ) sup ( ) n T TR L L K K        x xx u x u x u x . Положим D ( )D – подмножества NR , состоящие из таких U u , что ( )A u является отрицательно определенной (соответственно – неположительно определенной) матрицей. Если ,u D то ( ) .  u Справедливо соотношение [2] inf ( ) inf ( ). U D         u u u u (5) Пусть Du , ( )x u – решение задачи (3). Вектор ( )x u – решение системы уравнений [1] 2 ( ) ( ) 0 A u x l u . (6) КОНИЧЕСКАЯ РЕГУЛЯРИЗАЦИЯ В ЗАДАЧАХ КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ Компьютерная математика. 2016, № 2 131 Откуда, 11( ) ( ) ( ) 2  x u A u l u , 11 1( ) ( ) ( ), ( ) ( ) ( ), ( ) ( ) 4 2 c c     u A u l u l u u x u l u u . (7) Обозначим max ( ( ))u A максимальное собственное число матрицы ( ).uA Множество D может быть представлено в виде  max 1: ( ( )) 0, 0, 1,...,N iD R u i m     u A u . Во внутренних точках ( max ( ( )) 0 A u ) множества D функция ( ) u непрерывно дифференцируема и принимает конечные значения, на границе ( max ( ( )) 0 A u ) множества D функция ( ) u может принимать как конечные значения, так и значения  . Особенности поведения функции ( ) u вблизи границы множества D приводит к существенным проблемам при практическом решении задачи (5). 2. Процедуры одномерного поиска для функции ( ) u Пусть заданы точка 0 int ,Du такая, что 0 max ( ( )) 0 A u и произвольная точка 1 .NRu Рассмотрим точки  0 1 0( )t t  u u u u , расположенные на прямой, проходящей через точки 0u и 1.u Введем обозначения: 0 0( )A A u , 1 1( )A A u , 0 0( )l l u , 1 0( ) ( )  l l u l u 0 0( )c c u , 1 0( ) ( )c c c  u u ,    0 1 0( )t t  A u A A A ,    0 1 0 0( ) ( ) ( )t t t     l u l l u l u l l ,    0 1 0 0( ) ( ) ( )c t c t c c c t c     u u u . Для  0 1 0( )t t  u u u u , ( )t Du соотношение (6) принимает вид    0 1 0 01( ) 2 t x t     A A A l l . (8) Известно (см., например, [6]), что для вещественных симметричных матриц 0 1,A A при условии, что матрица 0A положительно определена, существует невырожденная матрица ,T такая, что  0  T A T I ,  1T A T = B , (9) где I – единичная, B – диагональная матрицы. Ю.П. ЛАПТИН Компьютерная математика. 2016, № 2132 Пусть матрица T удовлетворяет условию (9). Полагая ,x = Ty уравнение (8) приведем к виду    t t  01I + (B + I) y = T l + Δl 2 , или     011 1 , 1,..., 2ii i i iB t y t i n         , (10) где   0 0η = T l , η = T l , 0 , , 1,...,i i i n   – компоненты векторов 0η , η . Положим   max min 1 1 : 1, 1,..., ,ii iit B B i n     если  : 1, 1,...,iii B i n     , то maxt   ,   min max 1 1 : 1, 1,...,ii iit B B i n     , если  : 1, 1,...,iii B i n     , то min .t   Утверждение 1. Пусть min maxt t t  , тогда ( )t Du , ( )) ( )t tx(u Ty , где      0 ( ) , 1,..., 2 1 1 i i i ii t y t i n B t          . Если maxt   , то max max( ( ))) 0t A(u . Аналогично для mint . Положим ( ) ( ( ))t t   u . Для min maxt t t  функция ( )t может быть представлена в виде      20 0 1 1( ) ( ( )) 4 1 1 n i i iii t t t c t c B t              u . (11) Утверждение 2. Пусть   arg min 1 1 : 1, 1,...,ii iii B B i n     , тогда     max max 20 0 max , 0, если 0, lim 1 1 , в противном случае. i i i i t t t t i i t t B t                      Аналогичное утверждение может быть сформулировано для   arg max 1 1 : 1, 1,...,ii iii B B i n     . Обозначим   arg min 1 1 : 1, 1,...,ii iiI B B i n      . Теорема 1. Пусть max ,t   max max, lim ( ) , t t t t t      т. е. 0 max 0,i it    .i I  КОНИЧЕСКАЯ РЕГУЛЯРИЗАЦИЯ В ЗАДАЧАХ КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ Компьютерная математика. 2016, № 2 133 Положим    0 max max max ( ) , 2 1 1 i i i ii ty t i I B t          , (12) для i I значения max( )iy t определим произвольным образом. Тогда вектор max max( )) ( )t tx(u Ty – решение задачи (3) при max( )tu u . Доказательство. Учитывая введенные обозначения, приведем функцию Ла- гранжа max( , ( ))L tx u к виду     0 1 0 0 0 max max max max( , ( )) , ,L t t t c t c         x u A A A x x l l x     0 0 max max max, ,t t c t c        I B + I y y η η y . Учитывая, что   max1 1 0,iit B    0 max 0,i it    ,i I  т. е. от переменных ,iy i I функция max( , ( ))L tx u не зависит, и записывая условия оптимальности относительно остальных переменных, получаем утвер- ждение теоремы. ■ Таким образом, теорема 1 определяет решения задачи (3) в точках на грани- це ( max ( ( )) 0 A u ) множества D , в которых функция ( ) u принимает конеч- ные значения. Покажем, повторяя доказательство леммы 1.1 из [7], что это в свою очередь определяет субградиенты max( ( ))tg u функция ( ) u в таких точках max max( ( )) ( ( ( )))t t g u K x u . (13) Здесь max( ( ( )))tK x u – вектор, компонентами которого являются величины max( ( ( ))), 1,..., .iK t i Nx u Нетрудно видеть, что для произвольной точки Nu R имеет место max( ) ( ( ))t u u max max max( ( ( )), ) ( ( ( )), ( ))L t L t t x u u x u u . В самом деле, если ( ) u принимает конечное значение, то max max max( ) ( ( )) ( ( ), ) ( ( ( )), ( ))t L L t t    u u x u u x u u max( ( ( )), )L t x u u max max( ( ( )), ( )).L t t x u u Здесь x(u) – решение задачи (3) при заданном значе- нии вектора u . Если ( ) ,  u то неравенство очевидно. Далее max max max max max 1 ( ( ( )), ) ( ( ( )), ( )) ( ( )) ( ( ( ))) N i i i i L t L t t u u t K t     x u u x u u x u Ю.П. ЛАПТИН Компьютерная математика. 2016, № 2134 max max max max 1 ( ( )) ( ( ( ))) ( )), ( ( ( ))) N i i i i u u t K t t t     x u u - u K x u , откуда следует (13). Рассмотрим задачу поиска минимума функции ( )t (минимума по направ- лению функции ( ) u ), которая имеет вид  min max 1inf ( ) : , ( ) 0, 1,...,it t t t u t i m     . (14) Задача (14) – простая и может быть эффективно решена. Наиболее трудоем- ким является построение матрицы ,T удовлетворяющей условию (9). Использование на каждом шаге оптимизационного алгоритма решений за- дачи (14) для определения величины шага обеспечивает выполнение всех ограни- чений задачи (5). В качестве точки 0u должна использоваться точка, сгенериро- ванная на предыдущем шаге. Принципиальные проблемы, возникающие при таком использовании, связаны с тем, что матрица 0A может быть плохо обусловленной вблизи границы множества D или вырожденной на границе множества D . 3. Коническая регуляризация задач оптимизации В данном пункте рассматривается подход, в котором для задачи выпуклого программирования с ограничениями формируется эквивалентная задача без- условной оптимизации, целевая функция которой принимает конечные значения при любых значениях переменных. Целевая функция исходной задачи может быть не определена на границе и вне допустимой области. Предлагаемый подход обобщает результаты, изложенные в [5], и позволяет преодолевать проблемы, возникающие при решении задачи (5). Рассмотрим задачу выпуклого программирования: найти inf ( )   u (15) при ограничениях ( ) 0,h u (16) где nRu , , : { }nh R R    – выпуклые замкнутые функции. Обозначим  : ( ) 0nC R h  u u . Если множество C описывается сово- купностью ограничений –  : ( ) 0, 1,...,n iC R h i m   u u , полагаем  ( ) max ( ) : 1,..., .ih h i m u u Предположение 1. int domC   , если u принадлежит границе множества C , то ( ) 0h u . Предположение 2. Задана допустимая точка 0 ,Cu такая, что 0( ) 0.h u На границе множества C функция  может быть не определена (значение функции  может быть равно  ). КОНИЧЕСКАЯ РЕГУЛЯРИЗАЦИЯ В ЗАДАЧАХ КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ Компьютерная математика. 2016, № 2 135 Из замкнутости функции  следует, что если u принадлежит границе мно- жества C и для любой последовательности int , 1,...k C k u , такой, что k u u при ,k  выполняется lim ( )k k   u , тогда dom . u В работе [5] предполагалось, что C – компактное множество, domC   . Для оценочных задач квадратичной оптимизации множество C может быть неограни- ченным, на границе множества C значение функции  может быть равно  . Полученные в [5] результаты непосредственно обобщаются на рассматри- ваемый случай. Пусть задано некоторое число 0( )E   u . Обозначим F надграфик функ- ции  на множестве C  ( , ) : ( )F R C      u u . Положим ( , ), nR R   z u z . Рассмотрим коническую оболочку ( )E надграфика F с вершиной в точке 0 0( , )E Ez u :  0 0( ) : , ( ), 0,n E EE R R F         v v v z z z z . (17) Множество ( )E выпукло (поскольку выпуклым является множество F ), однако может быть незамкнутым (например, если множество C не ограничено, а  – линейная функция). Обозначим ( )E замыкание множества ( )E . Множество ( )E может рассматриваться как надграфик некоторой выпуклой функции. Эту функцию обозначим ( )E u и будем называть конической аппроксимацией функции  на множестве .C Функция ( )E u определена на всем пространстве nR и принима- ет конечные значения при любых .u Пример конической аппроксимации функ- ции показан на рисунке. Утверждение 3. Пусть множество C ограничено. Тогда для произвольной точки ,nRu 0,u u на луче, выходящем из точки 0u и проходящем через ,u найдется точка ,u Cu (возможно не одна), такая, что ( ) ( )E  u u . Если множество C не ограничено, такая точка может не существовать. Обозначим ( )Eμ u такую точку, ближайшую к 0.u Положим 0( ) , если точка ( ) существует, ( ) + , в противном случае, E E E       μ u u μ u u Ю.П. ЛАПТИН Компьютерная математика. 2016, № 2136 0 0 ( ), если ( ), ( ) ( ), если ( ). E E E E             u u u u u u u u u (18) Лемма 1. Пусть для точки ,nRu 0,u u существует точка ( ),Eμ u тогда 0 0 ( ) ( ( ( )) ) ( ) E E E E E      u - u u μ u μ u u . (19) РИСУНОК. Сплошной линией показана функция ( ), u штрих-пунктирной – ( ),E u в точках 1,a u значения этих функций совпадают, множество C – отрезок  a, b Рассмотрим задачу: найти  inf ( ) : n E E R   u u . (20) Теорема 2. Пусть ,E   тогда .E     Теорема 3. Пусть выполняются предположения 1, 2 и 0( ).E x  Тогда : n E R R  – выпуклая функция. Задачу (20) будем называть конической регуляризацией исходной задачи (15) – (16). КОНИЧЕСКАЯ РЕГУЛЯРИЗАЦИЯ В ЗАДАЧАХ КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ Компьютерная математика. 2016, № 2 137 Для использования рассматриваемого подхода в алгоритмах решения опти- мизационных задач должны быть определены эффективные процедуры вычисле- ния значений функции ( )E u и ее субградиентов (  -субградиентов). Обозначим '( , ) u p производную функции  в точке Cu по направле- нию .p Пусть зафиксирована некоторая точка 1u , положим 1 0 1 0    u up u u , 1 0( )Et  μ u u , если точка 1( )Eμ u не существует, полагаем t   . Лемма 2. Пусть 0t  , 0 intt C u p . Тогда 0 0( ) '( , ), если ,t E t t t t        u p u p p (21) 0 0( ) '( , ), если .t E t t t t         u p u p p (22) Следствие. 0 0 0( )sup : '( , ), 0, int .t Et t t t t C t                  u p u p p u p (23) Теорема 4. Пусть точка 1u , такая, что 1( )Eu μ u – внутренняя точка мно- жества .C Тогда в точке u существует субградиент g функции , для которого выполняется 0( ) E   u g,u u (24) и вектор g – субградиент функции E в точке 1u (в точке u ). Теорема 5. Пусть выполняются предположения 1, 2, точка 1,u такая, что 1( )Eu μ u принадлежит границе множества ,C тогда 1) dom u , 2) 0( ), 0h  g u u u и вектор 0 0 ( ) ( ), ( ) ( ) ( ), h h E          u g u u u g g u g u g u u u (25) есть субградиент функции ( )E u в точке 1u (в точке u ), где ( )g u , ( )hg u – субградиенты функций  и h в точке .u Ю.П. ЛАПТИН Компьютерная математика. 2016, № 2138 При использовании предлагаемого подхода значение  обычно неизвест- но. Поэтому величина E уточняется по ходу решения задачи (20). При получении допустимого решения u задачи (15) – (16) такого, что ( ) E u , полагаем ( ) ,E B  u где 0.B  При фиксированном значении параметра B число таких уточнений будет конечно. Необходимо отметить, что для вычисления значения функции E в произ- вольной точке u должна решаться задача одномерного поиска (23), что в случае общей задачи выпуклого программирования существенно увеличивает трудоем- кость по сравнению с вычислением значения функции  . 4. Коническая регуляризация оценочной квадратичной задачи Подходы, приведенные в пункте 3, будем использовать для решения задачи (5), которую представим в виде  max 1inf ( ) : ( ) 0, 0, 1,..., .iu i m      u A(u) (26) Функция ( ) u вычисляется в соответствии с соотношением (7), матрица ,A(u) вектор ( )l u и величина ( )c u – в соответствии с (4). Будем считать заданной точку 0 int ,Du такую, что 0 max ( )) 0 A(u , и число 0( ).E   u При использования конической регуляризации для задачи (26) необходимо для произвольной точки 1 NRu находить точку 1( )Eμ u на луче, выходящем из точки 0u и проходящем через 1,u в которой выполняется равенство 1 1( ( )) ( ( ))E E E  μ u μ u . Здесь ( )E u – коническая аппроксимация функции  на множестве .D Для поиска такой точки должна решаться задача одномерного поиска (23), которая с учетом обозначений, введенных в пункте 2, может быть представлена в виде: max 1 ( )sup : '( ), 0 , ( ) 0, 1,...,i t Et t t t t u t i m t              . (27) Функция ( )t – простая, задача (27) может быть решена достаточно эффек- тивно. В случае t   функция ( )E u не используется при регуляризации исходной задачи (26) вдоль прямой, проходящей через точки 0u и 1.u Как и для задачи (14) наиболее трудоемким при решении задачи (27) являет- ся построение матрицы ,T удовлетворяющей условию (9). Таким образом, трудоемкости вычисления значений функций ( ) u и ( )E u оказываются со- измеримыми. Если maxt t    , 1( ) 0, 1,...,iu t i m   , то субградиент функции ( )E u в точке ( )tu определяется решением ( ( ))tx u , которое вычисляется в соответ- ствии с утверждением 1. КОНИЧЕСКАЯ РЕГУЛЯРИЗАЦИЯ В ЗАДАЧАХ КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ Компьютерная математика. 2016, № 2 139 Если maxt t    ,  1( ) 0, 1,...,iu t i m   (точка ( )tu лежит на границе множества  1: 0, 1,...,iu i m u ), то субградиент функции ( )E u в точке ( )tu определяется в соответствии с теоремой 5. В случае maxt t    возможные решения ( ( ))tx u задачи (3) описывают- ся теоремой 1. При формулировке следующей теоремы используются обозначе- ния пункта 2. Теорема 6. Пусть maxt t    . Тогда существует вектор ( , 1,..., ),iy i n  y удовлетворяющий квадратичному уравнению 0c E  ' 0y,y + T l ,y (28) и соотношениям (12) теоремы 1 ( max( ),i iy y t i I   ). При этом вектор  x Ty – решение задачи (3) при ( )tu u , а вектор   1 ( ) N i i K   x – субградиент функции ( )E u в точке ( )tu . Здесь матрица T удовлетворяет условию (9). Доказательство. Из теоремы 5 следует, что если для субградиента g функции  в точке ( )tu выполняется 0( ( )) ( , ( ) )t E t     u g u u , (29) то вектор g – субградиент функции E в этой точке. Субградиенты g в точке ( )tu определяются решениями x задачи (3) при ( )tu u , т. е.   1 ( ) ( ) . N i i K K     g x x Решения x в соответствии с теоремой 1 могут быть представлены в виде , x Ty где матрица T и вектор y удовлетворяют условиям теоремы 1. Пусть x – решение задачи (3) при ( )tu u , для которого выполняется условие (29). Нетрудно видеть, что 0 0, ( ) ( ), ( )t t       g u u K x u u = 0( , ( )) ( , )L t L   x u x u 0( ( )) ( , ).t L  u x u Откуда следует 0( , )L E x u . Используя обозначения пункта 2, имеем 0 0( , ) ( ) ,L x u   A u x x 0 0( ), ( )c l u x u 0 0 0, , .c    A x x l x Делая замену  x Ty и учи- тывая, что матрица T удовлетворяет условию (9), получаем 0( , )L  x u 0c    ' 0y , y + T l , y . Отсюда получаем, что если условие (28) выполня- ется, то вектор g – субградиент функции E в точке ( )tu u . Ю.П. ЛАПТИН Компьютерная математика. 2016, № 2140 Уравнение (28) при дополнительных соотношениях (12) теоремы 1 разре- шимо не при любых значениях параметра E . В частности, если 0( )E   u , то уравнение (28) решений не имеет. По построению конической аппроксимации ( )E x величина E выбирается так, что 0( )E   u . Можно показать, что если уравнение (28) решений не имеет, то найдется точка maxt t  , в которой будет выполняться условие (24). Последнее противоречит предположению о том, что maxt t  . Теорема доказана. ■ Выводы. В работе для вычисления оценки оптимального значения за-дачи квадратичной оптимизации предложено использовать коническую регуляриза- цию оценочной задачи. Такой подход позволяет построить эквивалентную задачу безусловной оптимизации, целевая функция которой определена на всем про- странстве переменных задачи и удовлетворяет условию Липшица. Показано, что особенностью рассмотренного класса задач является возможность построения эффективных алгоритмов поиска по направлению. Такие алгоритмы являются существенными для использования конической регуляризации. Трудоемкость вычисления функций и субградиентов регуляризованой задачи оказывается соизмеримой с трудоемкостью вычисления функций исходной оценочной задачи. Полученные результаты будут полезны при разработке эффективных мето- дов решения оценочных задач квадратичной оптимизации. Автор выражает глубокую благодарность Березовскому О.А. за ценные замечания и советы по данной работе. Ю.П. Лаптін КОНІЧНА РЕГУЛЯРІЗАЦІЯ У ЗАДАЧАХ КВАДРАТИЧНОЇ ОПТИМІЗАЦІЇ Розглядаються питання обчислення оцінок оптимальних значень неопуклих задач квадратич- ної оптимізації на основі лагранжевих релаксацій вихідної задачі. На границі допустимої об- ласті оціночної задачі функції задачі можуть бути розривні, погано обумовлені, що ускладнює розробку обчислювальних алгоритмів. У роботі наводяться нові підходи подолання зазначе- них проблем, засновані на використанні конічних регуляризації опуклих задач оптимізації. Yu.P. Laptin CONIC REGULARIZATION IN QUADRATIC OPTIMIZATION PROBLEMS Calculation of estimates for optimal values for non-convex quadratic optimization problems on the base of Lagrange relaxation of the original problem is considered. At the boundary of the feasible set of the estimation problem the used functions can be discontinuous or poorly conditioned that com- plicates the development of numerical algorithms. The paper presents a new approach to overcome these problems, based on the use of conic regularizations of convex optimization problems. КОНИЧЕСКАЯ РЕГУЛЯРИЗАЦИЯ В ЗАДАЧАХ КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ Компьютерная математика. 2016, № 2 141 1. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая оптимизация. Киев: Наукова думка, 1989. 204 с. 2. Березовский О.А., Стецюк П.И. Об одном способе нахождения двойственных квадратичных оценок Шора. Кибернетика и системный анализ. 2008. № 2. С. 89 – 99. 3. Boyd S., Vandenberghe L. Semidefinite programming relaxations of non-convex problems in control and combinatorial optimization. Communications, Computation, Control, and Signal Pro- cessing. – Springer US, 1997. Р. 279 – 287. 4. Поляк Б.Т., Щербаков П.С. Рандомизированный метод решения задач полуопределенного программирования. Стохастическая оптимизация в информатике. – Издательство Санкт- Петербургского государственного университета (Санкт-Петербург), 2006. Том 2. № 1-1. С. 38 – 70. 5. Лаптин Ю.П., Бардадым Т.А. Некоторые подходы к регуляризации нелинейных задач оптимизации. Проблемы управления и информатики. 2011. № 3. C. 57 – 68. 6. Беллман Р. Введение в теорию матриц. М.: Наука, 1976. С. 352. 7. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-тран- спортного планирования. М.: Наука, 1986. С. 260. Получено 23.09.2016 Об авторе: Лаптин Юрий Петрович, доктор физико математических наук, старший научный сотрудник Института кибернетики имени В.М. Глушкова НАН Украины.

Коническая регуляризация в задачах квадратичной оптимизации

Репозитарії

Схожі ресурси