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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автори:	Лаптин, Ю.П., Бардадым, Т.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Назва видання:	Проблемы управления и информатики
Теми:	Оптимальное управление и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/207310
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Некоторые подходы к регуляризации нелинейных задач оптимизации / Ю.П. Лаптин, Т.А. Бардадым // Проблемы управления и информатики. — 2011. — № 3. — С. 57–68. — Бібліогр.: 15 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207310
record_format	dspace
spelling	irk-123456789-2073102025-10-06T00:09:16Z Некоторые подходы к регуляризации нелинейных задач оптимизации Деякі підходи до регуляризації нелінійних задач оптимізації Some Approaches to Regularization of Nonlinear Optimization Problems Лаптин, Ю.П. Бардадым, Т.А. Оптимальное управление и методы оптимизации Розглянуто способи перетворення опуклих задач оптимізації з обмеженнями на еквівалентні задачі з кращими обчислювальними властивостями. Достатньо уваги приділено питанням використання конічних апроксимацій та конічних подовжень цільових функцій із допустимої області оптимізаційної задачі на весь простір змінних. Результатом застосування запропонованого підходу є задача опуклого програмування без обмежень (регуляризована задача), розв’язок якої збігається з розв’язком початкової задачі. Особливе значення розглянуті підходи мають тоді, коли цільова функція не визначена за межами допустимої області. Запропоновано ефективні процедури обчислення допоміжних функцій, розглянуто особливості програмної реалізації алгоритмів, результати обчислювальних експериментів. Methods for transforming convex optimization problems with constraints into equivalent problems with better computational properties are considered. Special attention is paid to conical approximations and conical extensions of objective functions from the feasible set to the entire space of variables. The result of the proposed approach is an unconstrained convex programming problem (regularized problem) whose solution coincides with the solution of the original one. These approaches are particularly important when the objective function is undefined outside the feasible set. Effective procedures for computing auxiliary functions are proposed, software implementation peculiarities are considered, and computational experiment results are reported. 2011 Article Некоторые подходы к регуляризации нелинейных задач оптимизации / Ю.П. Лаптин, Т.А. Бардадым // Проблемы управления и информатики. — 2011. — № 3. — С. 57–68. — Бібліогр.: 15 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207310 519.8 10.1615/JAutomatInfScien.v43.i5.40 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	2011
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207310
citation_txt	Некоторые подходы к регуляризации нелинейных задач оптимизации / Ю.П. Лаптин, Т.А. Бардадым // Проблемы управления и информатики. — 2011. — № 3. — С. 57–68. — Бібліогр.: 15 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT laptinûp nekotoryepodhodykregulârizaciinelinejnyhzadačoptimizacii AT bardadymta nekotoryepodhodykregulârizaciinelinejnyhzadačoptimizacii AT laptinûp deâkípídhodidoregulârizacíínelíníjnihzadačoptimízacíí AT bardadymta deâkípídhodidoregulârizacíínelíníjnihzadačoptimízacíí AT laptinûp someapproachestoregularizationofnonlinearoptimizationproblems AT bardadymta someapproachestoregularizationofnonlinearoptimizationproblems
first_indexed	2025-10-07T01:08:14Z
last_indexed	2025-10-07T01:08:14Z
_version_	1845283304580841472
fulltext	© Ю.П. ЛАПТИН, Т.А. БАРДАДЫМ, 2011 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 57 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 519.8 Ю.П. Лаптин, Т.А. Бардадым НЕКОТОРЫЕ ПОДХОДЫ К РЕГУЛЯРИЗАЦИИ НЕЛИНЕЙНЫХ ЗАДАЧ ОПТИМИЗАЦИИ Рассматриваются способы преобразования выпуклых задач оптимизации с ограничениями в эквивалентные задачи, обладающие лучшими вычислительными свойствами. К таким подходам относятся, например, методы негладких штрафных функций для построения эквивалентной задачи безусловной оптимизации [1–4], метод регуляризации Моро–Иосиды [5–8]. Для функций, определенных на огра- ниченных множествах, полезным оказывается их продолжение на все простран- ство, и именно построению таких продолжений в статье уделяется наибольшее внимание. В разд. 1 перечислены несколько известных способов выпуклого продолжения функций с выпуклого компакта на все пространство и обсуждаются возникающие при этом вычислительные трудности. В частности, приводится конструкция из [1], а также описывается операция инфимальной свертки (infimal convolution), позво- ляющая построить липшицево продолжение [7]. При этом безусловный оптимум построенного продолжения (регуляризованной задачи) совпадает с минимумом исходной функции на рассматриваемом компакте (решением исходной задачи). Предлагается также возможность учесть свойства допустимого множества, рас- смотрев инфимальную свертку исходной функции с функцией Минковского (или, как ее иногда называют, калибровочной функцией, см. [3, 7]). Достаточно эффективным для реализации оптимизационных алгоритмов ока- залось использование специальных конических продолжений целевой функции с допустимой области на все пространство [9, 10]. Поведение такого продолжения вне допустимой области определяется поведением целевой функции на ее грани- це, что иногда затрудняет разработку алгоритмов решения оптимизационных задач. Разумной альтернативой является применение конических аппроксима- ций вместо конических продолжений функций. Эти вопросы рассматриваются в разд. 2. Вопросам разработки алгоритмов оптимизации на основе использования рас- сматриваемых подходов к регуляризации задач посвящен разд. 3. Обсуждаются результаты вычислительных экспериментов. 1. Выпуклые продолжения и операция инфимальной свертки Рассматривается задача выпуклого программирования: найти )(min xff  (1) при ограничениях ,0)( xh (2) 58 ISSN 0572-2691 где ,nRx }{:,  RRhf n — выпуклые функции. Обозначим :{ nRxC  }.0)( xh Предполагается, что C — непустой выпуклый компакт. Удобно пола- гать, что функция f задана на всем пространстве ,nR но . dom fC  При использовании методов штрафных функций обычно предполагается, что целевая функция задана и за пределами множества C, и этот факт используется при построении вычислительных процедур. Если же целевая функция вне допу- стимой области не определена, естественно построить ее выпуклое продолжение на все пространство .nR В [1] для этого предлагается использовать функцию },:)),(()({sup)(ˆ Czzxzvzfxf  (3) где ,domint fC  )(zv — произвольный (но фиксированный для каждого z) вектор из )(zfC — условного субдифференциала функции f в точке z по множеству C. Лемма 1 [1, с. 118]. Функция )(ˆ xf выпукла и конечна на nR и совпадает на С с функцией ),(xf т.е. )()(ˆ xfxf  .Cx Несмотря на то, что выпуклое продолжение задается в явном виде, с вычис- лительной точки зрения использование функции (3) достаточно трудоемко. В работе [7] приведен способ построения выпуклого продолжения, основан- ный на операции инфимальной свертки (сложения надграфиков). При этом оказы- вается возможным построение продолжения даже с сохранением липшицевости исходной минимизируемой функции (если она обладала таким свойством). Утверждение 1 [7, т. І, с. 175] (о липшицевом продолжении). Пусть C — не- пустое выпуклое множество, а RRf n : — выпуклая функция, удовлетворяю- щая на C условию Липшица с постоянной L. Тогда существует выпуклая функ- ция f̂ },)({infˆ uxLuff Cu   (4) которая совпадает с f при всех Cx и удовлетворяет условию Липшица с посто- янной L во всем пространстве. Операция, указанная в правой части (4), — это инфимальная свертка функ- ций )()(1  ff и .)(2  Lf Она имеет следующий геометрический смысл: надграфик функции 21 ˆ fff  — это сумма надграфиков функций 1f и ,2f т.е. множество, заданное как }.2,1),(:),{(epiepiˆepi 212121  jxfrrrxxfff jjj Операция инфимальной свертки функций позволяет построить вспомога- тельную дифференцируемую выпуклую функцию, определенную на всем про- странстве, сохранив точку минимума. Для любых 0r рассмотрим функ- цию ,rf определенную в nR согласно .\|\|\|\| 2 )(inf)( 2         ux r ufxf nRur (5) Функция rf называется регуляризацией Моро–Иосиды функции f (см. [5–8]). Можно показать, что точная нижняя грань в (5) достигается в некоторой точке ,rx а построенные таким образом функции rf будут дифференцируемыми, причем ).()( rr xxrxf  Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 59 В рамках этого подхода можно учесть и свойства допустимого множества, воспользовавшись инфимальной сверткой исходной функции с функцией Мин- ковского (или, как ее иногда называют, калибровочной функцией, см. [3, 7]), ко- торая определяется для замкнутого выпуклого множества C, содержащего ноль, как }.,0:{inf)( CxxRC  Напомним ее свойства: CR выпукла в ;nR )()( xtRtxR CC  для ;0t если ,Cx то ,1CR если ,Cx то ;1CR 1CR для точек границы множества С; );()()( yRxRyxR CCC  множество C является компактом тогда и только то- гда, когда 0CR для всех .0x Далее в разд. 1 будем полагать, что .0 C Рас- смотрим для любых 0r аналогичную (5) функцию )}.()({inf)(}{ uxrRufxf CRur n   (6) Утверждение 2. Функция }{rf является выпуклой и для любых nRx вы- полняется ).()()( }1{}{ xfxfxf rr   Если , domint fx  то ).()(lim }{ xfxf r r   Доказательство. Функция }{rf является выпуклой, так как ее надграфик получен сложением надграфиков выпуклых функций f и ,CrR т.е. также явля- ется выпуклым. Поскольку в силу определения )},({epi)}()1{(epi  CC rRRr то }{}1{ epiepiepi rr fff   . Поэтому для nRx выполняется )(}{ xf r ).()(}1{ xfxf r   Поскольку функция f выпукла по u на компакте C, а при каждом nRx функция  )( uxRC при ,u то точная нижняя грань в (6) достигается. Обозначим эту точку :rx ).()()(}{ rCrr xxrRxfxf  Пусть . domint fx  Как было показано, ),()( }{ xfxf r т.е. ).()()()( }{ rCrr xxrRxfxfxf  Посколь- ку , domint fx  то .)( xf Так как функция f выпукла, она имеет аффинную миноранту, т.е. существуют nRs , такие, что ).(,)()( }{ rCrr xxrRxsxfxf  Здесь все ,domint fxr  иначе правая часть была бы равна . При r после- довательность )( rC xxrR  также всегда будет стремиться в бесконечность за исключением случая, когда ,lim xxr r   а это в силу полунепрерывности f снизу означает, что ).()(lim }{ xfxf r r   ■ Приведем формулы, необходимые для вычисления субдифференциалов и -субдифференциалов функции, получающейся в результате инфимальной свертки. Утверждение 3 [7, т. ІІ, с. 119]. Пусть 0 и  )(dom 21 ffx .domdom 21 ff  Предположим, что существуют такие ,1y ,2y что точная нижняя грань в операции инфимальной свертки в точке 21 yyx  достига- ется (это имеет место, например, когда пересечение относительных внутренно- стей эффективных областей для функций, сопряженных ,1f ,2f непусто). Тогда }.,0,:)()({))(( 2121221121 21   yfyfxff  Утверждение 4 [7, т. ІІ, с. 120]. Пусть .21 fff  Рассмотрим ,dom ii fy  2,1i и ).dom(21 fyyx  Тогда ).()()( 2211 xfyfyf   (7) 60 ISSN 0572-2691 Если множество )()( 2211 yfyf   непусто, то точная нижняя грань в опе- рации инфимальной свертки в точке 21 yyx  достигается, а в (7) имеет место равенство. В случае использования инфимальной свертки с функцией Минковского при 0y имеем },,1),(:{)0()0( 0 2 CsxsxCRf C  а при 0y соответ- ственно }.0),,(sup)(),(:{)()()( 0 00 0 2   ddsddsCsyFyRyf Cs CCC Все перечисленные в разд. 1 подходы позволяют продолжить целевую функ- цию задачи (1), (2) с множества C на все пространство переменных, при этом ис- ходная задача сводится к задаче безусловной минимизации. Однако для вычисле- ния значений функций f̂ необходимо решать вспомогательные задачи типа (3)–(6), трудоемкость решения которых в общем случае соизмерима с трудоемкостью ре- шения исходной задачи. Наиболее используемой при построении алгоритмов решения выпуклых (не- гладких) задач оптимизации оказалась регуляризация Моро-Иосиды, послужив- шая толчком для развития целого направления так называемых прокси-методов. В алгоритмах, использующих подобную регуляризацию, обычно вместо задачи (5) на каждой итерации k решается вспомогательная задача , 2 )(inf)( 2         ux r ufxf kRu k r n (8) где kf — кусочно-линейная аппроксимация исходной функции f, полученная на итерации k. Задача (8) является задачей квадратичного программирования, и для ее решения существуют эффективные алгоритмы. Для примера приведем лишь несколько ссылок из большого количества работ, посвященных смежным вопро- сам. Так, работа [11] является развитием методов линеаризации, предложенных ранее для минимизации гладких функций при наличии ограничений, в [12, 13] рассматриваются алгоритмы, построенные на основе квазиньютоновских методов. В настоящее время работы ведутся по применению такого рода подходов для ре- шения негладких невыпуклых задач оптимизации (см., например, [14]). 2. Конические аппроксимации функций Рассматривается задача выпуклого программирования (1), (2). Как и ранее, считается, что }0)(:{  xhRxC n — выпуклый компакт, .dom fC  Предпо- лагается заданной допустимая точка Cx 0 такая, что .0)( 0 xh В [9, 10] для решения задачи (1), (2) предлагалось использовать специальную процедуру конического продолжения целевой функции с допустимой области на все пространство. При определенном подборе параметра этой процедуры кониче- ское продолжение оказывается выпуклым и исходная задача с ограничениями сводится к безусловной выпуклой задаче оптимизации. Это позволяет для реше- ния исходной задачи использовать эффективные алгоритмы негладкой оптимиза- ции [2]. Предложенный подход оказался достаточно эффективным, разработан- ные программы нечувствительны к плохому масштабированию задач и показали определенные преимущества по сравнению с известными программными сред- ствами при решении плохо обусловленных классов задач [10]. В данном разделе рассматриваются обобщения этого подхода. Пусть задано некоторое число )( 0xfE  . Обозначим F надграфик функции f на множестве C }.)(:),({ xfCRxF  Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 61 Положим ),,( xz  .nRRz  Рассмотрим коническую оболочку )(E надграфика F с вершиной в точке :),( 00 xEzE  }.,0),(,:{)( 00 FzzzzvRRvvE EE n  (9) Множество )(E выпукло (посколь- ку выпукло множество F) и может рас- сматриваться как надграфик некоторой выпуклой функции, обозначим ее )(xE и будем называть конической аппроксима- цией функции f на множестве C. Функция )(xE определена на всем пространстве nR и принимает конечные значения при любых x. Пример конической аппроксима- ции функции приведен на рисунке, где сплошной линией показана функция ),(xf штрих-пунктирной — функция ),(xE в точках 1, xa значения этих функций сов- падают, множество C — отрезок ],[ ba . Рассмотрим условный -субдифференциал функции )(xf в точке 0x при Exf  )( 0 }.),()()({)( 000 CzxzvxfzfRvxf nC  Можно показать, что )}.(),()({max)( 000 xfvxxvxfx C E  Нетрудно видеть, что для произвольной точки ,nRx ,0xx  на луче, выхо- дящем из точки 0x и проходящем через x, найдется точка ,x Cx (возможно, не одна) такая, что ).()( xxf E Обозначим )(xE такую точку, ближайшую к .0x Положим        .)( если),( ,)( если),( )( 00 00 xxxxx xxxxxf x EE E E (10) Лемма 2. Функция )(xE представима в виде . )( )))((()( 0 0 xx xx ExfEx E EE    (11) Доказательство следует из того, что графиком функции ),()(~ 0 ptxt EE  0 0 xx xx p    является линейная функция, принимающая значения E в точке 0t и ))(( xf E в точке .)( 0xxt E  ■ Рассмотрим задачу: найти }.:)({inf n EE Rxx  (12) Теорема 1. Пусть , fE тогда .  fE E a b 0x 1x 62 ISSN 0572-2691 Доказательство. По построению )()( xxf E и )()( xxf E .Cx Та- ким образом, .  Ef Заметим также, что .})(:{ 00 Cxxxxx E  Рассмотрим точку x такую, что 00 )( xxxx E  (т.е. )).()( xx EE  По- скольку 0))((   EfExf E и  00 )()( xxxxxx EE ,)( 0xxE  то из (11) следует, что ).(()( xfx EE  Отсюда получаем  })(:)({inf}:)({inf 00 xxxxxRxx EE n EE ,}:)({inf})(:)({inf 00  fCxxfxxxxxf E т.е. .  fE ■ Теорема 2. Пусть C — выпуклый компакт, ,dom fC  ,int0 Cx  ).( 0xfE  Тогда RRn E  : — выпуклая функция. Доказательство. Рассмотрим надграфик )(E функции ).(xE Нетрудно видеть, что },,1),(,:{)( 00 FzzzzvRRvvE EE n  (13) где, как и ранее, F — надграфик функции f на множестве C, ).,( 00 xEzE  Пусть ),(, Ewu  покажем, что )()1( Ewuv  для любых .10  В силу (13) существуют Fwu , и коэффициенты ,1,  wu для которых имеет место ),( 00 EuE zuzu  ).( 00 EwE zwzw  Отсюда  wuv )1( . )1( )1( ))1(( 00           E wu wu wuE z wu z Полагая , )1( wu u    ,)1( wu  ,)1( wuv  получаем ).( 00 EE zvzv  Очевидно, что ,10  ,1 отсюда ,Fv  ).(Ev  Таким образом, )(xE — выпуклая функция, принимающая конечные значения при любых x, поскольку таким свой- ством обладает функция ).(xE ■ Построение функции )(xE можно интерпретировать в терминах, близких к понятию инфимальной свертки. Обозначим ),(:{)( 00 xxxyyxLC  }0, Cy отрезок луча, проходящего через точки 0x и x, где Cx int0  — за- данная точка. Пусть определена некоторая функция .: RRn  Условной инфи- мальной сверткой функций ,f назовем функцию )}.(:)()({inf)( xLuuxufxf C  (14) Введенное понятие отличается от стандартного определения инфимальной свертки тем, что точная нижняя грань в (14) берется по отрезку )(xLC вместо всего компакта С, что позволяет использовать эффективные процедуры одномер- ного поиска. Можно показать, что для условной инфимальной свертки )(xf функций )(xf и )()( xx E имеет место .)()( Exxf E  Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 63 Для использования рассматриваемого подхода в алгоритмах решения опти- мизационных задач должны быть определены эффективные процедуры вычисле- ния значений функции )(xE и ее субградиентов (-субградиентов). Обозначим ),( pxf  производную функции f в точке Cx по направлению p. Пусть зафиксирована некоторая точка ,x положим , 0 0 xx xx p    .)( 0xxt E  Лемма 3. Пусть ,0t .0 Cptx  Тогда ,если),,( )( 0 0   ttptpxf t Etpxf (15) .если),,( )( 0 0   ttptpxf t Etpxf (16) Доказательство. Обозначим ),()( 0 ptxftf  )(tf — производная функ- ции )(tf в точке t при сдвиге в направлении увеличения аргумента, )(tf — производная при сдвиге в направлении уменьшения аргумента, ,0t .0 Cptx  Пусть зафиксировано некоторое ,0t .0 Ctpx  Рассмотрим линейную функцию )(~ t такую, что ,)0(~ E ).()(~ tft  Нетрудно видеть, что если , tt то )(~ t является касательной к функции )(tf в этой точке (если точка касания не одна, то величина t соответствует точке касания, ближайшей к ),0x если , tt то ),()(~   tft если , tt то ).()(~   tft Пусть , tt тогда ).( ))(( )()(~)()()()( tt t Etf tfttftttftf      Отсюда следует (15). Для случая  tt аналогично ).()()()()( ))(( )()(~       tttftftftt t Etf tft ■ Следствие. .,0),,( )( :sup 00 0            Ctpxtptpxf t Etpxf tt (17) Из выпуклости )(xf имеем ),,(),( 00 ptpxfptpxf  откуда с учетом (15), (16) получаем (17). Теорема 3. Пусть точка x такая, что )(xx E — внутренняя точка множе- ства С. Тогда в точке x существует субградиент g функции f, для которого вы- полняется ),,()( 0xxgExf  (18) и вектор g — субградиент функции E в точке x. Доказательство. Из соотношений ,)( 0 ptxxx E   ),( 0 ptpxf ),,( 0 ptpxf  (15), (16) получаем ).,( )( ),( pxf t Exf pxf     (19) 64 ISSN 0572-2691 Очевидно, в точке x существуют субградиенты 21, gg (возможно )21 gg  функции f, для которых ).,(),(),,(),( 21 pxfpgpxfpg  Нетрудно ви- деть, что из (19) следует существование такого ,10,  что для вектора 21 )1( ggg  будет выполняться ).,( )( pg t Exf    Вектор g — субгради- ент функции f в точке .x Учитывая, что ,0xxpt  получаем (18). Докажем, что вектор g — субградиент функции E в точке .x Для этого достаточно показать, что надграфик )(E функции E принадлежит надграфику L функции ).,()( 0xxgExL  Надграфик L — полупространство в .1nR Пусть точка 11  nRz лежит на границе множества ,L а .2 Lz  Тог- да, очевидно, луч, исходящий из 1z и порожденный вектором ,12 zz  содержит- ся в .L Нетрудно видеть, что надграфик F функции f принадлежит ,LK точка ),( 00 xEzE  лежит на границе множества .L Отсюда следует, что любая точка ,,0),( 00 Fzzzzv EE  также принадлежит ,LK т.е. надграфик )(E функции E принадлежит надграфику .L ■ Заметим, что субградиент g функции f в точке , domint)( Cxx E  удо- влетворяющий соотношению (18), может быть определен в ходе решения задачи одномерного поиска (17). Теорема 4 [10]. Пусть точка x такая, что )(xx E принадлежит границе множества C, hfx domntidomint  , ),(xg f )(xgh — субградиенты функций f и h в точке .x Тогда 0)),((  xxxgh и вектор )( )),(( )),(()( )( 0 0 xg xxxg xxxgxfE xgg h h f f    (20) — субградиент функции )(xE в точке x. Доказательство. Предположим, что ,0)),((  xxxgh тогда и ),(( xgh ,0)0  xx отcюда ,0)),(()()( 00  xxxgxhxh h что противоречит условию .0)( 0 xh Рассмотрим линейные функции ),),(()()( xxxgxfxf fL   )()( xhxhL ).),(()),(( xxxgxxxg hh  Положим }0)(:{  xhRxC L n L и рассмотрим )}(:),({ xfCRxF LLL  — надграфик функции Lf на множестве LC и выпуклую коническую оболочку L надграфика LF относительно точки :),( 0xEzE  }.,0)({ LEEL Fzzzzv  (21) Множество L является надграфиком некоторой выпуклой функции, ко- торую обозначим ).(xL По построению )()( xfxL  в области }{ LCx функция )(xL линейна, т.е. ),,()()( xxgxfxL  где вектор g однозначно определяется по векторам ),(xg f ).(xgh Более того,  ))(( 00 xxxL )).(( 00 xxxE  Поскольку надграфик функции )(xE принадлежит надграфику функции ),(xL то функция ),()()( xxgxfxL  является каса- тельной для ),(xE а вектор g — субградиент функции )(xE во всех точках ).( 00 xxxx  Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 65 Нетрудно проверить, что для вектора g должны выполняться соотношения ,),()( 0 Exxgxf  (22) )),((),( xyxgxxg f  (23) для всех x таких, что .0)),((  xxxgh (24) Представим векторы g, fg в виде ,  ggg где ,0)),(( gxgh ),(xgg h ,    fff ggg где ,0)),((  fh gxg ),(xgg hf    . )( ))(),(( 2 xg xgxg h hf  Из (23), (24) следует ,  fgg т.е. ).( )( ))(),(( )( 2 xg xg xgxg xgg h h hf f  Подставляя полученные выражения в (22), получаем  2 )( ))(),(( xg xgxg h hf , )),(( )),(()( 0 0 xxxg xxxgxfE h f    отсюда следует (20). ■ При условии  fE задачу (12) будем называть конической регуляризацией задачи (1), (2). При этом условии для решения задач (12) может использоваться любой метод безусловной минимизации выпуклых функций. Заметим, что если точка 0x близка к решению x задачи (1)–(2), а разность Ef  невелика, то по- ведение функции )(xE определяется поведением функции )(xf в окрестности решения .x Приведенные утверждения позволяют эффективно вычислять значе- ния функции )(xE (требуется решить задачу одномерного поиска (17)) и ее субградиенты (см. теоремы 3, 4). 3. Обсуждение алгоритмических и вычислительных аспектов Для использования конической регуляризации задачи (1), (2) необходимо за- давать величину E, такую что . fE После этого для решения задачи (12) может использоваться любой метод безусловной минимизации выпуклых функций. Если значение f заранее не известно, то величина E должна уточняться по ходу оп- тимизации. Пусть задано некоторое значение величины E, для решения задачи (12) ис- пользуется сходящийся алгоритм A безусловной минимизации выпуклых функ- ций, на каждой итерации которого определяется текущая точка ,kx вычисляются значение минимизируемой функции )(xE и ее субградиент в этой точке. Для вычисления значения функции E в точке kx необходимо решить задачу одно- мерного поиска (17). При определенных условиях эта задача может быть упроще- на. Пусть в соотношении (17) ,)( 0 0 xx xx xpp k k k    t — значение параметра t такое, что точка txpxxx kk C k  )()( 0 лежит на границе множества C. 66 ISSN 0572-2691 Лемма 4. Пусть ,))(,()( 0xxxpxfxfE kkkk  (25) тогда точная верхняя грань в соотношении (17) для точки kx достигается на гра- нице множества C. Доказательство. В силу выпуклости функции f имеет место  ))(( 0 kxtpxf ,))(,()())(),(( 0 txpxfxftxpxtpxf kkkkk  где ,0 tt   0xx k .)( frCxpt k  Отсюда следует утверждение леммы. ■ Таким образом, при выполнении условия леммы 4 для вычисления значения функции E в текущей точке kx необходимо решать задачу одномерного поис- ка точки )( k C x пересечения отрезка ],[ 0 kxx с границей множества C (если ).Cxk  В настоящее время предлагаемый подход реализован при дополнительном предположении, что функция f удовлетворяет условию Липшица на компакте C. При использовании алгоритма A на каждой итерации k выполняются проверки условия (25) и условия ).( kxfE  (26) Если эти условия не выполняются на каком-то шаге алгоритма A, то значение E уменьшается: ,BE  где },))(,()(),({min 0xxxpxfxfxf kkkkk  0B — задаваемый параметр. В силу липшицевости функции f существует такое ,E что при  EE усло- вия (25), (26) выполняются при любых x. Нетрудно видеть, что уточнение значе- ния величины E будет проводиться конечное число раз, после чего алгоритм схо- дится [10] к оптимальному решению задачи (12). Заметим, что если условие (25) выполняется при любых x, то функция E совпадает с функцией f при Cx E( — выпуклое продолжение функции f с множества C на все пространство ).nR В связи с этим описанный подход назван методом выпуклых продолжений целевой функции. В программной реализации [10] предлагаемого подхода в качестве алгоритма безусловной минимизации использовался r-алгоритм [2], для определения точки )(xx C (пересечения отрезка ],[ 0 xx с границей множества C) использовался дихотомический поиск. Точность определения точки x была фиксирована и яв- лялась параметром алгоритма. Разработанные программные средства совместимы со стандартной программной средой AMPL [15]. Это позволило в ходе вычисли- тельного эксперимента провести сравнение с некоторыми современными оптими- зационными программами (SNOPT, MINOS, LOQO). Вычислительный эксперимент проводился на специально разработанных плохо обусловленных тестовых задачах, сформированных на основе базовых за- дач стандартного вида: найти )(min 0 xff  (27) при ограничениях ,0)( xfk ,...,,1 mk  (28) Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 3 67 где .nRx Тестовые задачи формировались путем замены ограничений вида (28) на ,0)()()( 10  xfxx kkk ,...,,1 mk  (29) где ,0)(0  x k ,0)(1  xk mk ...,,1 (допустимое множество задачи при этом не изменяется),         ,...,,1,1 ,...,,1,)( )( 1 1 2 0 mmk mkxx xk )),)(/((sin)( 21  kkk xxx ,...,,1 mk  ,1 .0 Здесь ],2/[1 mm  x — оптимальное решение базовой задачи,  kk xx , — k-е компоненты векторов ,, xx .nm  Целевая функция заменялась на следующую:        случае, противном в}...,,1:)(max{ ,...,,1:)(если),( )( ~ 0 0 mkxf mkxfxf xf k k (30) где .0 В допустимой области )(0 xf и )( ~ 0 xf совпадают, вне допустимой обла- сти при 0 функция )( ~ 0 xf не определена. Заметим, что при ,1 ,0 ,0  тестовая задача совпадает с базо- вой задачей (27), (28). В ходе вычислительного эксперимента параметры функций ),(0 xk )(1 xk подбирались таким образом, чтобы в одних ситуациях тестовые за- дачи имели вырожденное масштабирование в окрестности оптимального реше- ния, в других — функции ограничений содержали осцилирующий множитель. В ходе вычислительного эксперимента программная реализация предложен- ного метода выпуклого продолжения продемонстрировала устойчивость к плохой обусловленности и плохому масштабированию задач [10]. Некоторые задачи уда- лось решить только методом выпуклого продолжения. Использованные тестовые задачи и предварительная версия программных средств размещены для свободно- го доступа на сайте http://elis.dvo.ru/sites/default/files/OptimiZone/software/ndo-icyb/ index.html. Ю.П. Лаптін, Т.О. Бардадим ДЕЯКІ ПІДХОДИ ДО РЕГУЛЯРИЗАЦІЇ НЕЛІНІЙНИХ ЗАДАЧ ОПТИМІЗАЦІЇ Розглянуто способи перетворення опуклих задач оптимізації з обмеженнями на еквівалентні задачі з кращими обчислювальними властивостями. Достатньо уваги приділено питанням використання конічних апроксимацій та конічних подовжень цільових функцій із допустимої області оптимізаційної задачі на весь простір змінних. Результатом застосування запропонованого підходу є за- дача опуклого програмування без обмежень (регуляризована задача), розв’язок якої збігається з розв’язком початкової задачі. Особливе значення розглянуті підходи мають тоді, коли цільова функція не визначена за межами допустимої області. Запропоновано ефективні процедури обчислення допоміжних функцій, розглянуто особливості програмної реалізації алгоритмів, результати обчислю- вальних експериментів. http://elis.dvo.ru/sites/default/files/OptimiZone/software/ndo-icyb/%0bindex.html http://elis.dvo.ru/sites/default/files/OptimiZone/software/ndo-icyb/%0bindex.html 68 ISSN 0572-2691 Yu.P. Laptin, T.A. Bardadym SOME APPROACHES TO REGULARIZATION OF NONLINEAR OPTIMIZATION PROBLEMS Methods for transformation of convex optimization problems with constraints into equivalent problems with better computational properties are considered. Main attention is paid to conical approximations and conical extensions of the objective functions from the feasible set to the full space of variables. As a result we get an unconstrainerd (regularized) convex programming problem, whose solution co- incides with the solution of the initial one. Special importance these approaches have in the case when the objective function is not defined outside of the feasible set. Effective procedures for computation of auxiliary functions are proposed, peculiarities of software realizations are considered, results of computational ex- periments are reported. 1. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. — М. : Наука, 1981. — 384 с. 2. Shor N.Z. Nondifferentiable optimization and polynomial problems. — Amsterdam; Dordrecht; London : Kluwer Academ. Publ., 1998. — 381 p. 3. Пшеничный Б.Н. Метод линеаризации. — М. : Наука. — 1983. — 136 с. 4. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирова- ния. — М. : Наука, 1976. — 191 с. 5. Moreau J. Proximité et dualité dans un espace hilbertien // Bull. Soc. Math. France. — 1965. — 93. — P. 273–299. 6. Rockafellar R.T. Monotone operators and the proximal point algorithm // SIAM Journ. on Contr. and Optimiz. — 1976. — 14. — P. 877–898. 7. Hiriart-Urruty J.-B., Lemaréchal C. Convex analysis and minimization algorithms. Vol. I and II. — Berlin : Springer Verlag, 1991. — I. — 417 p; II. — 347 p. 8. Ириарт-Уррути Ж.-Б. Оптимизация и выпуклый анализ. — К. : Издательская компания «КИТ», 2004. — 370 с. 9. Лаптин Ю.П. Один подход к решению нелинейных задач оптимизации с ограничениями // Кибернетика и системный анализ. — 2009. — № 3. — С. 182–187. 10. Лаптин Ю.П., Лиховид А.П. Использование выпуклых продолжений функций для решения нелинейных задач оптимизации // Управляющие системы и машины. — 2010. — № 6. — C. 25–31. 11. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Комбинированный метод решения общей задачи выпуклого программирования // Кибернетика и системный анализ. — 1998. — № 4. — С. 121–134. 12. Lemaréchal C., Sagastizábal C. Variable metric bundle methods: from conceptual to imple- mentable forms // Math. Program. — 1997. — 76. — P. 393–410. 13. Mifflin R., Sagastizábal C. A VU-algorithm for convex minimization // Ibid. — 2005. — 104(2-3). — P. 583–608. 14. Hare W., Sagastizábal C. Computing proximal points of nonconvex functions // Ibid. — 2009. — 116(1-2). — P. 221–258. 15. Fourer R., Gay D.M., Kernighan B.W. AMPL — a modeling language for mathematical pro- gramming, second edition. — Brooks/Cole — Thomson Learning, 2003. — 517 p. Получено 23.02 2011

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

Репозитарії

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