Точные штрафные функции в схемах декомпозиции по переменным

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

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-111508
record_format	dspace
spelling	irk-123456789-1115082017-01-11T03:03:18Z Точные штрафные функции в схемах декомпозиции по переменным Лаптин, Ю.П. Использование точных штрафных функций в схемах декомпозиции по переменным нелинейных задач оптимизации позволяет преодолеть ряд проблем, связанных с неявным описанием допустимой области координирующей задачи. В работе рассматриваются вопросы определения значений штрафных коэффициентов при таком подходе. Використання точних штрафних функцій у схемах декомпозиції за змінними нелінійних задач оптимізації дозволяє подолати ряд проблем, пов’язаних з неявним описом допустимої області координуючої задачі. В роботі розглядаються питання визначення штрафних коефіцієнтів при такому підході. The use of exact penalty functions in schemes of decomposition of variables for nonlinear optimization problems can overcome a number of difficulties associated with the implicit description of the feasible region for master problems. In the paper the determination of values of penalty coefficients according this approach is considered. 2014 Article Точные штрафные функции в схемах декомпозиции по переменным / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 39-48. — Бібліогр.: 9 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/111508 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Использование точных штрафных функций в схемах декомпозиции по переменным нелинейных задач оптимизации позволяет преодолеть ряд проблем, связанных с неявным описанием допустимой области координирующей задачи. В работе рассматриваются вопросы определения значений штрафных коэффициентов при таком подходе.
format	Article
author	Лаптин, Ю.П.
spellingShingle	Лаптин, Ю.П. Точные штрафные функции в схемах декомпозиции по переменным Теорія оптимальних рішень
author_facet	Лаптин, Ю.П.
author_sort	Лаптин, Ю.П.
title	Точные штрафные функции в схемах декомпозиции по переменным
title_short	Точные штрафные функции в схемах декомпозиции по переменным
title_full	Точные штрафные функции в схемах декомпозиции по переменным
title_fullStr	Точные штрафные функции в схемах декомпозиции по переменным
title_full_unstemmed	Точные штрафные функции в схемах декомпозиции по переменным
title_sort	точные штрафные функции в схемах декомпозиции по переменным
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2014
url	http://dspace.nbuv.gov.ua/handle/123456789/111508
citation_txt	Точные штрафные функции в схемах декомпозиции по переменным / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 39-48. — Бібліогр.: 9 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT laptinûp točnyeštrafnyefunkciivshemahdekompoziciipoperemennym
first_indexed	2025-07-08T02:15:53Z
last_indexed	2025-07-08T02:15:53Z
_version_	1837043237949276160
fulltext	Теорія оптимальних рішень. 2014 39 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Использование точных штрафных функций в схемах декомпозиции по переменным нелинейных задач оптимизации позволяет преодолеть ряд проблем, связанных с неявным описанием допустимой области координирующей задачи. В работе рассматриваются вопросы определения значений штрафных коэффициентов при таком подходе.   Ю.П. Лаптин, 2014 УДК 519.8 Ю.П. ЛАПТИН ТОЧНЫЕ ШТРАФНЫЕ ФУНКЦИИ В СХЕМАХ ДЕКОМПОЗИЦИИ ПО ПЕРЕМЕННЫМ Введение. Схемы декомпозиции по перемен- ным широко используются при решении оптимизационных задач, обладающих специальной структурой [1 – 4]. При фиксированных значениях связывающих переменных исходная задача большой размерности распадается на совокупность небольших подзадач, каждая из которых решается независимо. Оптимальные значения подзадач зависят от параметров – связывающих переменных. Значения связывающих переменных определяются при решении координирующей задачи. В случае, когда отдельные подзадачи являются задачами линейного программирования или имеют специальную структуру, их точные решения могут быть получены достаточно эффективно. На основе этих решений вычисляются субградиенты функций координирующей задачи. Если при некоторых значениях связывающих переменных подзадачи не имеют решений (множество допустимых точек пусто), определяются дополнительные ограничения в пространстве связывающих переменных. Трудоемкость построения таких дополнительных ограничений соизмерима с затратами на получение точных решений подзадач. Для нелинейных подзадач ситуация существенно отличается. Во-первых, точное решение получить невозможно, только приближенное. Учитывая это приходится использовать  -субградиенты функций координирующей задачи [5, 6]. С увеличением точности растет трудоемкость решения подзадач. Но намного более критическими являются Ю.П. ЛАПТИН 40 Теорія оптимальних рішень. 2014 проблемы, возникающие в случае, когда множество допустимых точек подзадач становится пустым. Поскольку для вычисления оценок используются кусочно- линейные аппроксимации функций подзадач, установить пустоту допустимого множества подзадачи при некоторых значениях связывающих переменных и построить дополнительные ограничения становится чрезвычайно сложно. Эффективным подходом для преодоления этих проблем является использование точных штрафных функций. При практическом решении часто удается подобрать корректные значения штрафных коэффициентов и успешно решать задачи. Но в общем случае разработка методик определения значений штрафов наталкивается на существенные трудности, связанные с большой размерностью исходных задач. В предлагаемой работе предлагаются некоторые из возможных подходов к решению таких проблем. Постановка задачи. Рассматривается квазиблочная задача математического программирования со связывающими переменными: найти   Q q q q yx yxf 1 0 , ),(min (1) при ограничениях ( , ) 0, 1,..., , 1,..., ,i q q qf x y i I q Q   (2) где ),( qi q yxf – выпуклые дифференцируемые функции, принимающие ко- нечные значения при любых значениях аргументов, ,Lx R , Nq qy R 0, , , 1 .qi I q , , Q     Пусть связывающие переменные x фиксированы. Обозначим  0( ) min ( , ) : ( )q q q q qx f x y y D x   , (3) где  ( ) : ( , ) 0, 1,...,q q i q q qD x y f x y i I   . Положим qW   : ( )qx D x   , ( )q x   , если qx W . В схемах декомпозиции решается следующая задача, которая эквивалентна исходной (1) – (2): найти 1 min ( ) : , 1,..., . Q q q q x x W q Q             (4) Известно (см., например, [2]), что )(xq – выпуклые собственные функции. Для вычисления субградиентов функций )(xq используются точные ТОЧНЫЕ ШТРАФНЫЕ ФУНКЦИИ В СХЕМАХ ДЕКОМПОЗИЦИИ … Теорія оптимальних рішень. 2014 41 решения подзадач (3). Вопросы построения -субградиентов этих функций на основании приближенных решений рассматривались в [5, 6]. Рассмотрим задачу (3). Индекс ,q если это не вызывает неоднозначность, будем опускать. Пусть заданы точка Lx R и совокупность 1 2, ,..., my y y точек из ,NE в каждой точке ( , )kx y вычислены значения ( , )ik i kf f x y и субградиенты ( , )ik ik ik x yg g g функций , 0,..., ,if i I 1,..., .k m Рассмотрим нижнюю линейную аппроксимацию задачи (3) при фиксированном x x , min y   , (5) при ограничениях ( , ) , 1,..., , 0,ik ik y kf g y y k m i      (6) ( , ) 0, 1,..., , 1,..., .ik ik y kf g y y k m i I     (7) Теорема 1 [5]. Пусть задана точка ( )y D x , , y  – оптимальное решение, iku – оптимальные значения двойственных переменных, 1,..., ,k m 0,..., ,i I задачи (5) – (7). Тогда 0( ) ( , )x f x y    , ( )g x   1 0 , m I ik ik x k i u g    где 0( , ) .f x y     Обычно, точки 1 2, ,..., my y y генерируются в ходе решения задачи (3), точка ( )y D x одна из них (наилучшая допустимая). Проблема получения допустимых точек в ходе решения задачи (3) может быть достаточно сложной. Ситуация существенно ухудшается, в случае, когда ( )D x  . Обозначим  ( ) : ( , ) 0, 1,..., , 1,..., .ik ik m y kD x y f g y y k m i I      Множество ( )mD x – это аппроксимация множества ( )D x . Если ( )mD x  , то можно построить [4] дополнительное ограничение вида , 0,a x b  которому должны удовлетворять связывающие переменные (точки множества W ). Совокупность таких ограничений при разных значениях вектора x формирует аппроксимацию множеств .W Однако, в случае, когда ( ) ,D x   построение совокупности точек  1 2, ,..., my y y , для которой выполняется условие ( ) ,mD x  может быть очень трудоемким. Ю.П. ЛАПТИН 42 Теорія оптимальних рішень. 2014 Одним из подходов к преодолению этих проблем является использование точных штрафных функций при решении задачи (1) – (2). Такой прием предлагался еще в [1]. Исходная задача при этом становится задачей безусловной оптимизации: найти 0 , 1 1 min ( , ) ( , ) , qIQ q i i q q q q x y q i f x y f x y            (8) и ключевым оказывается вопрос определения значений коэффициентов i q . Здесь  ( ) max 0, ( ) .f x f x  Необходимо отметить, что значения i q должны быть не меньше оптимальных значений двойственных переменных задачи (1) – (2) и не могут быть получены при решении отдельных подзадач вида (3). Основные результаты. Для описания предлагаемого подхода к определению значений штрафных коэффициентов будем рассматривать задачи в стандартной формулировке: найти  * 0 0min ( ) : ,f f x x  (9) где  : ( ) 0, 1,..., , ,n ix f x i m x R     : n if R R , 0,1,...,i m – выпуклые непрерывные дифференцируемые функции. Положим 0 1 ( ) ( ) ( ) m i i i x f x f x       ,  ( ) max ( ), 1,...,ih x f x i m  , 0( ) ( ) ( ),F x f x h x    min ( ) : nx x R      , (10)  min ( ) : nF F x x R    . (11) ( )x ( ( )F x ) называется точной штрафной функцией, если решения задач (9) и (10) (соответственно (11)) совпадают. Известно (см., например, [2]), что если , 1,...,iu i m  – оптимальные значения множителей Лагранжа задачи (9), то ( )x – точная штрафная функция при , 1,..., ,i iu i m   ( )F x – точная штрафная функция при 1 . m i i u    Точные штрафные функции широко используются при реализации различных алгоритмов оптимизации [1, 2, 7]. При этом для определения ТОЧНЫЕ ШТРАФНЫЕ ФУНКЦИИ В СХЕМАХ ДЕКОМПОЗИЦИИ … Теорія оптимальних рішень. 2014 43 множителей Лагранжа на каждой итерации решаются некоторые вспомогательные задачи (например, линеаризации исходной задачи). В схемах декомпозиции такой подход неприменим учитывая большую размерность исходной задачи. Рассмотрим другие подходы. Для выпуклой функции ( )x обозначим ' ( , )x p одностороннюю производную в точке nx R по направлению p . Положим: ( , )p x y вектор, определяющий направление из точки x в точку ,y ( , ) ( ) , ,p x y y x y x y x       ( , ) , ( , ) , ,T x y x x p x y x y    где 0  . Множество ( , )T x y – это  -окрестность точки x на отрезке  ,x y . Очевидно, что  ( , ) ,T x y x y  , если y x   . Теорема 2 [9]. Пусть : nR R  – непрерывная, дифференцируемая по направлениям функция (существуют односторонние производные), x – локальный минимум функции  на ,nR B – ограниченное замкнутое множество, ,n B R  int ,B  0 int ,By   , 1,2,...,k nx R k  – последовательность, сходящаяся к x , для некоторых чисел 0,  0  выполняются условия ' 0( , ( , )) ,kx p x y   0( , ) \ .k Bx T x y   (12) Тогда для предельной точки x имеет место .Bx Из приведенной теоремы непосредственно следует следующая Теорема 3. Пусть заданы числа 0,  0,  допустимая точка 0 int ,y   задачи (9) и (10) (или (11)) имеют решения, последовательность точек , 0,1,...kx k  , сходится к решению x задачи (10) (соответственно (11)) и выполняются условия: 0( , ( , ))kx p x y   , 0( , ) \kx T x y  , 0,1,...k  , (13) где ( ) ( )x x   (соответственно ( ) ( )x F x  ). Тогда x – это решение задачи (9). Пусть для решения задачи (10) используется некоторый сходящийся алгоритм безусловной оптимизации, и заданы начальные значения коэффициентов 0, 1,..., .i i m   Условие (13) позволяет определять простые Ю.П. ЛАПТИН 44 Теорія оптимальних рішень. 2014 процедуры уточнения штрафных коэффициентов по ходу работы алгоритма, например, если на некоторой итерации это условие не выполняется, положить ,i i    1,..., ,i m где 1    выбирается так, чтобы условие (13) выполнилось. Здесь  – некоторый фиксированный параметр. Таким же образом увеличивается коэффициент  , если используется функция ( )F x . Аналогично тому, как это делалось в [8], можно показать, что при условии 0 inty   число уточнений штрафных коэффициентов будет конечно. При практическом использовании рассматриваемого подхода необходимо конкретизировать процедуру проверки условия (13). Нетрудно видеть, что множество, на котором это условие проверяется, имеет вид  0: ( , ),0k kХ x x x tp x y t t     либо  0: ( , ),0 .k kX x x x tp x y t t     Во втором случае предельная точка 0( , )k kx x t p x y   не принадлежит множеству .X Проверка заключается в анализе поведения функции 0( ) ( ( , ))k kt x t p x y    в интервале 0 .t t  Обозначим ' ( )t производную функции ( )t в точке t в направлении увеличения переменной ,t ' ( )t – производная в направлении уменьшения переменной .t В силу выпуклости функции ( )t имеем ' ' ' 1 2( ) ( ) ( )t t t       для любых  1 2 1 2, 0, ,t t t t t  . Откуда следует, что проверку условия (13) достаточно проводить только в точке .t При неудачном выборе точки 0 inty   значения штрафных коэффициентов могут устанавливаться достаточно большими. Для уменьшения этих значений точка 0y может варьироваться в процессе решения задачи (10) или (11). В работе [8] показано, что минимальное значение  коэффициента  , которое может быть достигнуто за счет варьирования точки 0 ,y равно 1 m i i u     для задач линейного программирования при определенных условиях. В схемах декомпозиции, учитывая большую размерность исходной задачи, значение  может оказаться неприемлемо большим. При использовании функции  существенным является такая организация вычислительного процесса, чтобы коэффициенты i не принимали слишком ТОЧНЫЕ ШТРАФНЫЕ ФУНКЦИИ В СХЕМАХ ДЕКОМПОЗИЦИИ … Теорія оптимальних рішень. 2014 45 больших значений. Обозначим   ( ) : ( ) 0, 1,..., ,iI x i f x i m   и представим условия (13) для функций F и  в следующем виде ' ' 0 ( , ) ( , ) ,jf x p f x p     argmax ( ), 1,..., ,ij f x i m  ' ' 0 ( ) ( , ) ( , ) ,i i i I x f x p f x p      где 0( , ),p p x y 0( , ) \kx T x y  . То есть для штрафной функции F возрастание функции 0f в точке x в направлении p уравновешивается убыванием одной функции ,jf а для функции  – убыванием совокупности функций , ( ).if i I x Естественно ожидать, что при большом числе ограничений m коэффициенты точной штрафной функции ( )x будут существенно меньше коэффициента  функции ( )F x . Однако, это не так для точек x , в которых нарушается только одно ограничение. Одним из путей обеспечения того, чтобы коэффициенты , 1,...,i i m  оставались сравнительно небольшими, является формирование последовательности точек , 0,1,...,kx k  (или подпоследовательности точек, в которых проверяются условия (13)) таким образом, чтобы для точек 0( , ) \kx T x y  число ( )I x нарушенных ограничений в точках 0( , ) \kx T x y  было не меньше некоторого заданного параметра  , n  . Здесь ( )I x    : ( ) 0, 1,..., .ii f x i m   Построение таких точек связано с дополнительными вычислительными затратами. Другой подход связан с тем, чтобы в случае ( )I x   использовалось иное правило регулировки коэффициентов i . Пусть точка x зафиксирована, ( )J I x . Рассмотрим задачу: найти ' 0( ) min ( ), , p x f x p  (14) '( ), 0, ,if x p i J  (15) 1p  (16) Ю.П. ЛАПТИН 46 Теорія оптимальних рішень. 2014 и штрафную функцию 0 ' '( , ) ( ), ( ), ( 1) .p i i i J x p f x p f x p p           Пусть p – решение задачи (14) – (16) ( , ), ,iu x J i J ( , )v x J оптимальные значения двойственных переменных, соответствующих ограничениям (15), (16). При условиях ( , ),i iu x J i J   , (17) и ( , )p v x J  имеет место  ( , ) min ( , ) : .nx p x p p R      Положим ( )J I x . Пусть 0p  , т. е. 1p  . Нетрудно видеть, что для производной по направлению ' ( , )x p   справедливо ' ( , ) ( , )x p x p       , ( , ) 0x p  , и вектор p определяет направление убывания функции ( )x . Пусть 0p  . Тогда ' ' 0 ( ) ( , ) ( ) 0i i i J f x u x J f x    , ' ( , )x p    '( ( , )) ( ),i i i i J u x J f x p     и, выбирая любой вектор 0,p  удовлетворяющий условиям (15), получаем направление убывания функции ( )x . Таким образом, справедлива Лемма 1. Пусть задано 0,  if , 0,1,...,i m – выпуклые непрерывно дифференцируемые функции, задачи (9) и (10) имеют решения, , 0,1,...kx k  , – последовательность, сходящаяся к решению x задачи (10), и выполняются условия ( , ( )) , ( ),k k k i iu x I x i I x     , 0,1,...k  . (18) Тогда x – это решение задачи (9). Для доказательства достаточно отметить, что если x  , то в точке x выполняются условия (18) и существует направление убывания функции ( )x , что противоречит предположению об оптимальности точки x . Рассмотрим возможные подходы к решению задачи (14) – (16). Обозначим I  множество активных ограничений вида (15) в оптимальной точке ,p 0 ' ( , , ) ( ),L p u v f x p  2'( ), ( 1)i i i J u f x p v p    – функция Лагранжа (используется квадрат ограничения (16), что эквивалентно). Если ограничение (16) активно в точке ,p то условия оптимальности (Каруша – Куна – Таккера) имеют вид ТОЧНЫЕ ШТРАФНЫЕ ФУНКЦИИ В СХЕМАХ ДЕКОМПОЗИЦИИ … Теорія оптимальних рішень. 2014 47 0 ' ' ( , , ) ( ) ( ) 2 0, ii i I L p u v f x u f x vp p         (19) '( ), 0, ,if x p i I  (20) 2 1 0.p   (21) Умножая (19) скалярно на вектор ' ( )jf x и учитывая (20), получаем систему уравнений 0 ' ' ' '( ), ( ) ( ), ( ) 0, ,j i i j i I f x f x u f x f x j I       (22) из которой при невырожденности однозначно определяются оптимальные значения двойственных переменных ( , ),iu x J i J . Вектор p после этого находится из соотношений (19) и (21). Для наших целей достаточно ограничиться приближенным решением задачи (14) – (16), т. е. вместо I  использовать множество ,I J для которого решение u системы уравнений (22) удовлетворяет условию 0,u  а направление убывания целевой функции (14) из точки 0,p  определяемое по соотношению (19), удовлетворяет всем ограничениям (15). Для построения такого множества I J могут быть предложены достаточно эффективные алгоритмы. В случае, когда число ( )kI x нарушенных ограничений в текущей токе kx достаточно большое, трудоемкость решения задачи (14) – (16) становится слишком высокой. Для построения правил, позволяющих при сравнительно невысоких вычи- слительных затратах определять не слишком большие значения штрафных коэффициентов, следует объединить рассмотренные подходы, т. е. при ( )I x   использовать условие (13), в противном случае – условие (18). Заключение. Заметим, что допустимая точка 0 inty   может варьироваться по ходу решения задачи (10), также возможны и другие правила уточнения коэффициентов. Полученные результаты могут быть полезны при разработке алгоритмов декомпозиции выпуклых квазиблочных задач. Ю.П. Лаптін Ю.П. ЛАПТИН 48 Теорія оптимальних рішень. 2014 ТОЧНІ ШТРАФНІ ФУНКЦІЇ У СХЕМАХ ДЕКОМПОЗИЦІЇ ЗА ЗМІННИМИ Використання точних штрафних функцій у схемах декомпозиції за змінними нелінійних задач оптимізації дозволяє подолати ряд проблем, пов’язаних з неявним описом допустимої області координуючої задачі. В роботі розглядаються питання визначення штрафних коефіцієнтів при такому підході. Yu.P. Laptin EXACT PENALTY FUNCTIONS IN SCHEMES OF DECOMPOSITION OF VARIABLES The use of exact penalty functions in schemes of decomposition of variables for nonlinear optimiza- tion problems can overcome a number of difficulties associated with the implicit description of the feasible region for master problems. In the paper the determination of values of penalty coefficients according this approach is considered. 1. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. – Киев: Наук. думка, 1979. – 199 c. 2. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – London: Kluwer Academic Publishers, 1998. – 381 p. 3. Zverovich V., Fábián C., Ellison E., Mitra G. A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition // Mathematical Programming Computation, September 2012. – Vol. 4, Issue 3. – Р. 211 – 238. 4. Ruszczynski A. A regularized decomposition method for minimizing a sum of polyhedral functions // Mathematical Programming. – 1986. – 35: Р. 309 – 333. 5. Лаптин Ю.П. -субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации // Теорія оптимальних рішень. – К.: Ін-т кібернетики імені В.М. Глушкова НАН України. – 2003. – № 2. – С. 75 – 82. 6. Лаптин Ю.П., Журбенко Н.Г., Кузьменко В.Н. Решение блочных нелинейных задач оптимизации со связывающими переменными // Теорія оптимальних рішень. – К.: Ін-т кібернетики імені В.М. Глушкова НАН України. – 2004. – № 3. – С. 142 – 149. 7. Byrd R.H., Lopez-Calva G., Nocedal J. A line search exact penalty method using steering rules // Math. Program., Series A and B. – 2012. – Vol. 133. – Р. 39 – 73. 8. Лаптин Ю.П. Вопросы построения точных штрафных функций // Вестник С.-Петербургского ун-та. Сер. 10: Прикладная математика. – 2013. – Вып. 4. – C. 21 – 31. 9. Лаптин Ю.П. Решение невыпуклых задач оптимизации с использованием точных штрафных функций // Компьютерная математика. – 2014. – № 1. – С. 119 – 130. Получено 02.04.2014

Точные штрафные функции в схемах декомпозиции по переменным

Репозитарії

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