Методы гладкого штрафа на основе комбинированной штрафной функции

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

Full description

Saved in:

Bibliographic Details
Date:	2014
Main Authors:	Соболенко, Л.А., Ненахова, С.Г., Шубенкова, И.А.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Series:	Теорія оптимальних рішень
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/111509
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Методы гладкого штрафа на основе комбинированной штрафной функции / Л.А. Соболенко, С.Г. Ненахова, И.А. Шубенкова // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 49-54. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-111509
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1115092025-02-23T17:00:40Z Методы гладкого штрафа на основе комбинированной штрафной функции Методи гладкого штрафу на основі комбінованої штрафної функції Smooth penalty methods on the basis of combined penalty function Соболенко, Л.А. Ненахова, С.Г. Шубенкова, И.А. С помощью разработанной общей схемы аппроксимирующих методов последовательного квадратичного программирования, в основе которой лежит релаксация штрафной функции, содержащей гладкие и негладкие штрафы, описаны методы гладких штрафов для решения задач условной оптимизации с нелинейными ограничениями в форме неравенств. За допомогою розробленої загальної схеми апроксимуючих методів послідовного квадратичного програмування, в основі якої лежить релаксація штрафної функції, що містить гладкі та негладкі штрафи, описано методи гладких штрафів для розв’язування задач умовної оптимізації з нелінійними обмеженнями у вигляді нерівностей. By means of the developed general scheme of approximating methods of sequential square programming which is based on the relaxation of the penal function containing smooth and unsmooth penalties, smooth penalty methods for the solution of problems of the conditional optimization with nonlinear restrictions in the form of inequalities are described. 2014 Article Методы гладкого штрафа на основе комбинированной штрафной функции / Л.А. Соболенко, С.Г. Ненахова, И.А. Шубенкова // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 49-54. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/111509 519.8 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
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	https://nasplib.isofts.kiev.ua/handle/123456789/111509
citation_txt	Методы гладкого штрафа на основе комбинированной штрафной функции / Л.А. Соболенко, С.Г. Ненахова, И.А. Шубенкова // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 49-54. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT sobolenkola metodygladkogoštrafanaosnovekombinirovannojštrafnojfunkcii AT nenahovasg metodygladkogoštrafanaosnovekombinirovannojštrafnojfunkcii AT šubenkovaia metodygladkogoštrafanaosnovekombinirovannojštrafnojfunkcii AT sobolenkola metodigladkogoštrafunaosnovíkombínovanoíštrafnoífunkcíí AT nenahovasg metodigladkogoštrafunaosnovíkombínovanoíštrafnoífunkcíí AT šubenkovaia metodigladkogoštrafunaosnovíkombínovanoíštrafnoífunkcíí AT sobolenkola smoothpenaltymethodsonthebasisofcombinedpenaltyfunction AT nenahovasg smoothpenaltymethodsonthebasisofcombinedpenaltyfunction AT šubenkovaia smoothpenaltymethodsonthebasisofcombinedpenaltyfunction
first_indexed	2025-11-24T02:19:06Z
last_indexed	2025-11-24T02:19:06Z
_version_	1849636418331082752
fulltext	Теорія оптимальних рішень. 2014 49 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ С помощью разработанной общей схемы аппроксимирующих мето- дов последовательного квадра- тичного программирования, в ос- нове которой лежит релаксация штрафной функции, содержащей гладкие и негладкие штрафы, описаны методы гладких штра- фов для решения задач условной оптимизации с нелинейными огра- ничениями в форме неравенств. © Л.А. Соболенко, С.Г. Ненахова, И.А. Шубенкова, 2014 УДК 519.8 Л.А. СОБОЛЕНКО, С.Г. НЕНАХОВА, И.А. ШУБЕНКОВА МЕТОДЫ ГЛАДКОГО ШТРАФА НА ОСНОВЕ КОМБИНИРОВАННОЙ ШТРАФНОЙ ФУНКЦИИ Введение. Настоящая работа является про- должением работы * , в которой для решения гладких задач оптимизации с нелинейными ограничениями в форме неравенств была предложена общая схема аппроксимирую- щих методов последовательного квадратич- ного программирования на основе штрафной функции, объединяющей гладкие и неглад- кие штрафы, а также описаны алгоритмы негладкого штрафа. В данной работе предлагается алгоритм гладкого штрафа на основе той же комби- нированной штрафной функции. Постановка задачи. По-прежнему рассма- тривается задача нелинейной оптимизации: найти * min ( ), x f f x    ( ) 0, 1,..., ,n ix R g x i m     (1) где ( )f x , ( )ig x , 1,...,i m – дифференци- руемые функции, градиенты ( )f x , ( )ig x , 1,..., ,i m удовлетворяющие условию Лип- шица. Под решением этой задачи понимается отыскание стационарных точек ,x , удовлетворяющих необходимым условиям экстремума: * * * 1 ( ) ( ) 0, m i i i f x g x      * * ( ) 0, 0, 1,..., .i i ig x i m     (2) Соболенко Л.А., Ненахова С.Г., Шубенкова И.А. Комбинированная штрафная функция для постро- ения различных методов решения нелинейных задач условной оптимизации // Теорія оптимальних рі- шень. – 2013. – С. 42–49. Л.А. СОБОЛЕНКО, С.Г. НЕНАХОВА, И.А. ШУБЕНКОВА 50 Теорія оптимальних рішень. 2014 Далее ,X  – множества соответствующих точек ,x , ( ) { 1,...,I x i  ,..., ( ) 0},im g x  * * * ( ), .I I x x X  Векторы рассматриваются как вектор-столбцы, – евклидова норма вектора и согласованная с ней норма матриц: если ,ry R то 1 1 r i i y y   , ( , )z x  – вектор с компонентами x и ,  ,L x  – функция Лагранжа задачи (1). Предлагаемая схема аппроксимирующих методов базируется на решении в каждой точке kx итерационного процесса вспомогательной задачи квадратич- ного программирования 1 min ( ), ( ), , 2 k k k k k x f x x x A x x x x           ( ) ( ), 0, 1,..., ,i k i k kg x g x x x i m    (3) где T k kA A – сильно положительно определенная матрица 2 2 , , 0, n ka x A x x a x a x R     . (4) А. Относительно задачи (3) предполагается, что она разрешима (ее ограни- чения совместны) в любой точке итерационной последовательности  ,kx которая предполагается ограниченной, и существует такая константа N и такие множители Лагранжа ,k что 1 , 0,1,...k N k   . (5) Пара Куна – Таккера  ,k kx  задачи (3) используется для поиска направле- ния спуска, а величину спуска характеризует шаговый множитель ,k опреде- ляемый из условия релаксации (убывания) некоторой штрафной функции. Штрафная функция. В качестве таковой в [] предложена смешанная (комбинированная) штрафная функция ( ).F z     2 1 1 ( ) ( ) ( ) ( ) , , 2 m m i i i i i F z f x g x g x               (6) где  0, 1,..., ,m iR i m      0,  0  – коэффициенты штрафа:  – негладкий (недифференцируемый) штраф,  – гладкий штраф, штраф ( )g x – вектор из mR с компонентами  ( ) max 0, ( ) .i ig x g x  Будем называть алгоритм, основанный на стратегии увеличения коэффи- циента штрафа  (при постоянном 0  ),  -алгоритмом, а на увеличении коэффициента штрафа  (при постоянном 0  ) –  -алгоритмом. МЕТОДЫ ГЛАДКОГО ШТРАФА НА ОСНОВЕ КОМБИНИРОВАННОЙ ШТРАФНОЙ ФУНКЦИИ Теорія оптимальних рішень. 2014 51 В работе [] описан  -алгоритм, а также свойства функции ( ).F z В частности, показано (лемма 2), что для  -алгоритма при постоянном 0  существует «пороговое» 0  такое, что для любых    во всех точках ограниченной последовательности   n kz R   выполняется неравенство     1 1 1 1 , ,k k k k kb A p p g x      (7) где ,k k kp x x   1 0;1  – любая константа. Это неравенство гарантирует релаксацию функции ( )F z в точке kz вдоль направления  , :k k k kz p    1 1 ( ) , ( ) , ( ) ,k k k k k k k k F z A p p g x g x z            (8) где ( )kg x – вектор из mR с компонентами  ( ) min 0, ( )i ig x g x  . Поскольку правая часть неравенства (8) в точке kx x отрицательна, производная функции ( )F z по направлению kz убывает. Заметим, что в отличие от  (лемма 2 в [] ) коэффициент , при котором начинает выполняться неравенство (7) и, следовательно, (8) может расти неограниченно в точках n kz R   , k  , т. е. «порогового» 0,  вообще говоря, не существует. Напомним, что  , n k k kz x R     – точки, которые будут генерироваться  -алгоритмом при решении задачи (1),  ,k kx  – пара Куна – Таккера за- дачи (3), € € k k k    – направление спуска по , зависящее от выбора € .k Если  € € ,i k k    € min , ,i i i k k k    1,..., ,i m то  € ;k k k      если € ,k k   то € 0.k  При замене ,k  ,k k kz x  на € ,k  €€ ,k k kz x  выражение (7) (см. (13) из []) принимает вид:   2 1 1 €2 , ( ) 1 , ( ) ( ) .k k k k k k kg x A p p g x g x           (9) Приведем основное свойство  -алгоритмов, вытекающее из неограничен- ного роста  в точках .kx Лемма 1. Пусть неравенство (9) нарушено в точке ˆ n kz R   при ( )kx   и выполняется при любых ( );kx   последовательности  ,kx  k ограни- чены, 0  фиксировано. Л.А. СОБОЛЕНКО, С.Г. НЕНАХОВА, И.А. ШУБЕНКОВА 52 Теорія оптимальних рішень. 2014 Если учесть ( )kx  при ,k  то 0,kp  ,kx X ,k  1( ) 0.k kg x C    Доказательство. Нарушение (9) при ( )kx   вследствие (4) приводит к неравенству   2 1 1 €1 , ( ) ( ) 2 , ( ) ,k k k k k k k kA p p g x g x g x            (10) которое возможно только при € , ( ) 0.k kg x  Из ограниченности  k и опре- деления € k вытекает ограниченность последовательности  € ,k  € .k С учетом ограниченности  ,kx  € k из (10) и (4) получим, что 1( ) ,k kg x C   где C – константа. Поэтому ( ) 0kg x  . Тогда на основании (10) и (4) выполняется 0kp  – необходимое и достаточное условие того, что kx X , k   и 1( ) 0.k kg x C    Лемма доказана. Формулировка метода. Примем  и 1 любыми константами из (0;1); 0 1,  0 nx R произвольно, 0  – любое фиксированное число, его не будем указывать в обозначениях и вместо ( )F z будем писать ( , ).kF z  Каждая k -ая итерация в точке kz ( kx x , 0kp  ), 0,1,...k  состоит в следующем. Шаг 1 (определение kp и k ). Задать матрицу T k kA A , удовлетворяющую (4) и, решая задачу (3), найти ,kx ,k .kp Шаг 2 (спуск по  и сохранение штрафа 1k k   ). Вычислить  € min ; ,i i i k k k    1,...,i m и найти  €€ ; ,k k kz x   € € ,k k k      полагая 0 € k   при 0.k  В случае € 0k  принять 1k k   и перейти к шагу 4; при нарушении к шагу 3. Шаг 3 (вычисление нового k и переопределение ˆ kz , € kz ). Найти ,k как наименьшее из значений 1 2 , s k     1,2,...s  , для которого впервые выполняется (9). Взять в качестве нового € k вектор k и, соответ- ственно, новые  € , ,k k kz x  € 0.k  Шаг 4 (определение k ). Найти k как наименьшее из значений 2 ,s  0,1,...s  , для которого впервые выполнится неравенство €€ € €( , , ) ( , ) ,k k k k k k kF z z F z       0 1,   (11) МЕТОДЫ ГЛАДКОГО ШТРАФА НА ОСНОВЕ КОМБИНИРОВАННОЙ ШТРАФНОЙ ФУНКЦИИ Теорія оптимальних рішень. 2014 53 где 1 1 €€ , ( ) , ( ) , 2 k k k k k k kA p p g x g x           10 1.   (12) Шаг 5. Вычислить 1 € € ,k k k kz z z    : 1.k k  Конец итерации. Отметим, что при поиске k в неравенстве (9) используются вычисленные на шаге 2 значения € ,k € ,kz € ,k € .kz При этом в (11) в качестве € k выступает вектор с компонентами ( 1,...,i m )   1 1 min ; , если , € , если . i i k k k ki k i k k k                (13) Соответсвенно (13) определяется и € € k k k    в (11):  € k k k      при 1k k   и € 0k  при 1.k k   Вследствие ограниченности объема публикации, сформулируем свойства  -алгоритма в виде двух теорем без доказательств. Теорема 1. Пусть градиенты ( )f x , ( )ig x , 1,...,i m удовлетворяют усло- вию Липшица, для вспомогательной задачи (3) выполняется предположение А, 0 nx R – произвольно, tkx – точки увеличения . Тогда. 1. Если k  , то при k  , ,tkx X kx  , ( , ) ,k kF z F  (14) где ( )F f x – значение функции ( )f x в одной из стационарных точек .x X При дополнительном условии выпуклости задачи (1) будет ,kx X * F f , ( ) .kf x f (15) 2. Если 0k    – константа при 0k k , то справедливы утверждения из [] для  -алгоритма о нелокальной сходимости kx X (теорема 1) и локальных оценках скорости сходимости (теорема 2). Оценки локальной скорости сходимости устанавливались в зависимости от выполнения условий: А1. Функции ( )f x , ( )ig x , ( )i I x выпуклы в окрестности множества  , содержащего внутреннюю точку. А2. Функции ( )f x , ( )ig x , ( )i I x дважды непрерывно дифференцируемы в окрестности ,x градиенты ( ),ig x ( )i I x линейно-независимы и для всех x таких, что ( ), 0ig x x  ,  * * ( ) ( ) 0ii I x i I x      имеет место ( ) , 0.xxL z x x  Л.А. СОБОЛЕНКО, С.Г. НЕНАХОВА, И.А. ШУБЕНКОВА 54 Теорія оптимальних рішень. 2014 А3. Градиенты ( ),ig x  ( ) 1,...,i I x i m   – линейно независимы и * 0i  для всех ( ).i I x Ограниченность генерируемых алгоритмом значений k исследуется в теореме 2. Теорема 2. Пусть выполнены условия теоремы 1 и А1, kx x при k  . Тогда при дополнительном условии А2 или А3 будет 0k    – константа для 0 ,k k при этом ,k  € ,k  € 0k  и справедливы оценки локальной скорости сходимости * 1 ,k kx x C q  2 1 * 2 * ,k kx x C x x    где (0;1)q , 1C , 2C . – константы. Заключение. В отличие от  -алгоритма [], нелокальная сходимость (14) в  -алгоритме гарантируется, вообще говоря, при .   Однако при их комбинации в предложенной схеме присутствие постоянного 0  положи- тельно влияет на характер генерируемых .k Так, если ,k k      0 ,k k то неравенство (9) выполнится, гарантируя ограниченность k   как для выпук- лой, так и невыпуклой задачи (1). Если же ( ),ig x ( )i I x линейно-независимы в предельной точке *,x то при любом постоянном 0  генерируется .k   Таким образом, сам факт присутствия коэффициента 0  обуславливает ограниченность генерируемых .k Л.О. Соболенко, С.Г. Ненахова, І.А. Шубенкова МЕТОДИ ГЛАДКОГО ШТРАФУ НА ОСНОВІ КОМБІНОВАНОЇ ШТРАФНОЇ ФУНКЦІЇ За допомогою розробленої загальної схеми апроксимуючих методів послідовного квадра- тичного програмування, в основі якої лежить релаксація штрафної функції, що містить гладкі та негладкі штрафи, описано методи гладких штрафів для розв’язування задач умовної оптимізації з нелінійними обмеженнями у вигляді нерівностей. L.A. Sobolenko, S.G. Nenakhova, I.A. Shubenkova SMOOTH PENALTY METHODS ON THE BASIS OF COMBINED PENALTY FUNCTION By means of the developed general scheme of approximating methods of sequential square programming which is based on the relaxation of the penal function containing smooth and unsmooth penalties, smooth penalty methods for the solution of problems of the conditional optimization with nonlinear restrictions in the form of inequalities are described. Получено 20.03.2014

Методы гладкого штрафа на основе комбинированной штрафной функции

Institution

Similar Items