Решение одного класса задач оптимизации с нелинейными ограничениями

Решение одного класса задач оптимизации с нелинейными ограничениями

Optimization problems are discussed which arise when complicated technical objects are modeled. Such problems contain well structured sets of nonlinear equations. Some approach is proposed for decomposition of discussed problems.

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-84936
record_format dspace
spelling irk-123456789-849362015-07-18T03:01:51Z Решение одного класса задач оптимизации с нелинейными ограничениями Лаптин, Ю.П. Optimization problems are discussed which arise when complicated technical objects are modeled. Such problems contain well structured sets of nonlinear equations. Some approach is proposed for decomposition of discussed problems. 2005 Article Решение одного класса задач оптимизации с нелинейными ограничениями / Ю.П. Лаптин// Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 134-139. — Бібліогр.: 6 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84936 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Optimization problems are discussed which arise when complicated technical objects are modeled. Such problems contain well structured sets of nonlinear equations. Some approach is proposed for decomposition of discussed problems.
format Article
author Лаптин, Ю.П.
spellingShingle Лаптин, Ю.П.
Решение одного класса задач оптимизации с нелинейными ограничениями
Теорія оптимальних рішень
author_facet Лаптин, Ю.П.
author_sort Лаптин, Ю.П.
title Решение одного класса задач оптимизации с нелинейными ограничениями
title_short Решение одного класса задач оптимизации с нелинейными ограничениями
title_full Решение одного класса задач оптимизации с нелинейными ограничениями
title_fullStr Решение одного класса задач оптимизации с нелинейными ограничениями
title_full_unstemmed Решение одного класса задач оптимизации с нелинейными ограничениями
title_sort решение одного класса задач оптимизации с нелинейными ограничениями
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2005
url http://dspace.nbuv.gov.ua/handle/123456789/84936
citation_txt Решение одного класса задач оптимизации с нелинейными ограничениями / Ю.П. Лаптин// Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 134-139. — Бібліогр.: 6 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT laptinûp rešenieodnogoklassazadačoptimizaciisnelinejnymiograničeniâmi
first_indexed 2025-07-06T12:03:29Z
last_indexed 2025-07-06T12:03:29Z
_version_ 1836899012433674240
fulltext 134 Теорія оптимальних рішень. 2005, № 4 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматриваются оптимизаци- онные задачи, возникающие в ходе моделирования сложных техниче- ских объектов. Такие задачи вклю- чают в себя хорошо структури- рованные подсистемы нелинейных ограничений-равенств. Предлага- ется подход, позволяющий осуще- ствить декомпозицию рассмат- риваемых задач.  Ю.П. Лаптин, 2005 ÓÄÊ 519.8 Þ.Ï. ËÀÏÒÈÍ ÐÅØÅÍÈÅ ÎÄÍÎÃÎ ÊËÀÑÑÀ ÇÀÄÀ× ÎÏÒÈÌÈÇÀÖÈÈ Ñ ÍÅËÈÍÅÉÍÛÌÈ ÎÃÐÀÍÈ×ÅÍÈßÌÈ Оптимизационные задачи, возникающие в ходе моделирования сложных технических объектов, обычно имеют специальную структуру, которую необходимо учитывать при разработке программных средств их ре- шения. Одной из особенностей таких задач является наличие структурированных нели- нейных ограничений-равенств. Такие огра- ничения часто распадаются на небольшие, слабо связанные, зависящие от параметров подсистемы нелинейных уравнений, которые в отдельных случаях удается эффективно решать на каждой итерации оптимизацион- ных алгоритмов [1, 2]. В результате значи- тельно понижается размерность оптимизаци- онной задачи. В общем случае возникают проблемы, обусловленные тем, что нелиней- ные функции обычно определены на ограни- ченных областях, а подсистемы нелинейных уравнений имеют решения не при всех воз- можных значениях параметров. В работе вводится понятие регуляризован- ного решения системы нелинейных уравне- ний, зависящих от параметров. Рассматри- ваются системы уравнений, состоящие из совокупности взаимосвязанных блоков, слу- чай, когда решение системы может быть по- лучено в результате последовательного ре- шения подсистем уравнений блоков. Для по- строения регуляризованного решения блока необходимо решать гладкую оптимизацион- ную задачу. Формулируется редуцированная задача, эквивалентная исходной, исследуют- ся свойства введенных функций. Редуциро- ванная задача оказывается негладкой невы- пуклой задачей. Обсуждается возможность Ю.П. ЛАПТИН 135 Теорія оптимальних рішень. 2005, № 4 использования некоторых алгоритмов для решения сформулированных задач. 1. Рассмотрим задачу математического программирования: найти ),(min 0 yxf (1) при ограничениях Kkyxfk ,...,1,0),( =≤ . (2) miyxi ,...,1,0),( ==χ , (3) где mn RyRx ∈∈ , , ),(),,( yxyxf ik χ - непрерывно дифференцируемые функции miKk ,...,1,,...,0 == . Предположим, что система (3) разрешима относительно y при любых зна- чениях вектора x . Если система (3) имеет специальную структуру, это может быть использовано для построения эффективных алгоритмов ее решения. В этом случае для текущих значений вектора x целесообразно найти решение )(xy системы (3) и вместо задачи (1) - (3) рассмотреть следующую: найти { }KkRxxx n k ,...,1,,0)(:)(min 0 =∈≤ϕϕ , где Kkxyxfx kk ,...,0)),(,()( ==ϕ . Если система (3) линейная, т.е. имеет вид 0=++ bByAx , (3') то специальная структура может выражаться в том, что матрица B имеет блоч- ный, треугольный или блочно-треугольный вид. Рассмотрим нелинейный случай. Будем называть блоком q B совокупность уравнений вида qqq m Mmyz ∈= ,0),(χ , (3'') если система (3'') при фиксированных значениях q z может быть разрешена от- носительно q y , где qqq i qq j q MIIiyyJjzz =∈=∈= ),,(),,( . Решение системы (3'') обозначим )( qq zy . Вектор q z назовем входом блока q B , )( qqq zyy = - выходом блока q B , q J - множество входных переменных, q I - множество выходных переменных. Обозначим I совокупность индексов переменных y исходной задачи. Бу- дем говорить, что система (3) представима некоторой сетью блоков, если сово- купность уравнений (3) может быть разбита на непересекающиеся подмножест- ва, каждое из которых является блоком. При этом для множества выходных пе- ременных каждого блока q B имеет место II q ⊆ , множества выходных пере- менных разных блоков непересекаются. Компонентами входов каждого блока Ю.П. ЛАПТИН 136 Теорія оптимальних рішень. 2005, № 4 могут быть как компоненты вектора x исходной задачи, так и компоненты вы- ходов других блоков. Блоки pq BB , связаны дугой ),( pq , если некоторые вы- ходы блока q B являются входами блока p B . Пусть система уравнений (3) представима ациклической сетью блоков. Век- тор x будем называть входом, вектор y - выходом сети блоков. Очевидно, что ациклическая сеть определяет некоторое упорядочение блоков (возможно, не- единственное). Нетрудно видеть, что последовательное решение (в соответствии с упорядочением сети) систем уравнений блоков дает решение исходной систе- мы уравнений (3). 2. В общем случае система (3'') имеет решение не при всех значениях q z . Существенной особенностью нелинейных функций является то, что они могут быть определены на ограниченных множествах. Предположим, что при форми- ровании каждого блока явно описываются области, в которых определены функции, входящие в систему уравнений блока, и которым должно принадле- жать решение, т.е. описание блока q B имеет вид qqq m Mmyz ∈= ,0),(χ , (4) qqq s Ssyzl ∈≤ ,0),( . (5) Обозначим { }qqq s qqq SsyzlyzV ∈≤= ,0),(:),( . (6) Предполагается, что функции ),( qq s yzl - линейны, функции ),( qq m yzχ определены на множестве q V , т.е. m q domV χint⊂ , q Mm ∈ , якобиан       ∂ ∂ = i mqq y y yzJ χ det),(det , qq IiMm ∈∈ , отличен от нуля для всех точек qqq Vyz ∈),( . Введем вспомогательные переменные ),( qq j q Jjvv ∈= и рассмотрим вспомогательную задачу: найти qq yv qq vzz −= , min)(δ , (7) qqq m Mmyv ∈= ,0),(χ , (8) qqq s Ssyvl ∈≤ ,0),( . (9) Очевидно, что если при некоторых значениях q z , решение системы (4) - (5) существует, то задача (7) - (9) имеет решения при любых q z , функция )( qq zδ РЕШЕНИЕ ОДНОГО КЛАССА ЗАДАЧ ОПТИМИЗАЦИИ С НЕЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ Теорія оптимальних рішень. 2005, № 4 137 определена для всех q z . Если при заданном q z система (4) - (5) разрешима, то 0)( = qq zδ , иначе 0)( > qq zδ . Пусть ),( ** qq yv – решение задачи (7) - (9) при заданном q z . Положим qqq yz *)( =θ . Вектор-функцию )( qq zθ будем называть регуляризованным решением блока. Пусть задана ациклическая сеть блоков. При последовательном расчете сети для заданного входа x используем регуляризованные решения блоков. Обозначим: )(xθ - «регуляризованное» решение сети блоков (исходной сис- темы уравнений); Kkxxfx kk ,...,0)),(,()( == θϕ ; )(xz q - зависимость входа q z блока q B от входа x сети блоков (полученная в результате последователь- ного расчета сети); Qqxzx qqq ∈= )),(()( δµ . Очевидно, что исходная задача (1) - (3) с учетом дополнительных ограниче- ний (5) эквивалентна следующей: найти )(min 0 * 0 xϕϕ = (10) при ограничениях Kkxk ,...,1,0)( =≤ϕ , (11) Qqxq ∈≤ ,0)(µ . (12) 3. Рассмотрим функцию )(z qδ , которая непрерывна и определена при всех z . Соотношение (8) определяет зависимость )( qqq vyy = . Обозначим ))(,()( qqq s q s vyvlv =υ , и приведем (7) - (9) к виду: найти qq v qq vzz −= min)(δ , (13) qq s Ssv ∈≤ ,0)(υ . (14) Обозначим: )( qq zv - решение задачи (13) - (14) при заданном q z ; { }qq s qq SsvvD ∈≤= ,0)(: υ . Имеет место (см. [6]) следующая Теорема. Пусть при заданном q z выполняется 0)( >qq zδ , задача (13) - (14) имеет единственное решение (проекция точки q z на допустимое множест- во q D ). Тогда функция qδ дифференцируема в точке q z , градиент δ g этой функции лежит на прямой, порожденной отрезком )]([ qqq zvz − , и 1=δ g . Ю.П. ЛАПТИН 138 Теорія оптимальних рішень. 2005, № 4 Следствие. Пусть множество q D выпуклое. Тогда функция qδ - выпуклая и непрерывно дифференцируема в точках q z , таких, что 0)( >qq zδ . Будем говорить, что точка q z регулярна, если для этого q z задача (13) - (14) имеет единственное решение. В общем случае множество q D невыпуклое. Будем говорить, что множество q D обладает свойством ∆ -регулярности, если все точки q z , такие что ∆≤)( qq zδ , являются регулярными. Т.е. функция qδ непрерывно дифферен- цируема в точках q z , таких, что ∆≤< )(0 qq zδ . Приведем без доказательства Утверждение. Пусть функции qq s Ssv ∈),(υ , непрерывно дифференцируе- мы, градиенты )( q vg sυ функций )( q s vυ удовлетворяют условию Липшица с некоторой константой L . Существует 0>ε , такое, что для любой точки q v , в которой 0)( =q s vυ , выполняется ευ >)( q vg s . Тогда существует 0>∆ , та- кое, что множество q D обладает свойством ∆ - регулярности. Замечание. В регулярных точках q z решение )( qq zv задачи (13) - (14) не- прерывно, но может быть негладким. 4. Предложенная схема решения задач оптимизации при наличии структури- рованных нелинейных ограничений-равенств позволяет эффективно решать сис- тему нелинейных уравнений при любых значениях параметров x . Вспомога- тельные задачи (7) - (9) являются гладкими (при условии гладкости исходных функций). Для их решения могут использоваться методы, которые гарантируют выполнение линейных ограничений (9) на каждой итерации (например, некото- рые модификации метода линеаризации [5]). Редуцированная задача (10) - (12) является негладкой, размерность ее относительно исходной задачи существенно понижается. В точках x , таких что значения Qqx q ∈,)(µ , достаточно малы, функции, входящие в задачу, непрерывны. Если значения )(x qµ велики, эти функции могут быть разрывными. Для решения редуцированной задачи могут использоваться алгоритмы с растяжением пространства [3, 4]. Ограничения (11) - (12) при этом должны вводиться в целевой функционал как негладкие штрафы. Эффективность предложенного подхода и круг задач, для которого примене- ние этого подхода целесообразно, могут быть определены в результате вычис- лительных экспериментов. РЕШЕНИЕ ОДНОГО КЛАССА ЗАДАЧ ОПТИМИЗАЦИИ С НЕЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ Теорія оптимальних рішень. 2005, № 4 139 Ю.П. Лаптін РОЗВ’ЯЗАННЯ ОДНОГО КЛАСУ ЗАДАЧ ОПТИМІЗАЦІЇ З НЕЛІНІЙНИМИ ОБМЕЖЕННЯМИ Розглядаються оптимізаційні задачі, які виникають при моделюванні складних технічних об’єктів. Такі задачі включають в себе добре структуровані системи нелінійних обмежень- рівнянь. Пропонується підхід, який дозволяє виконувати декомпозицію задач, що розглядаються. Yu.P. Laptin SOLVING OF ONE CLASS OF OPTIMIZATION PROBLEMS WHICH CONTAIN NONLINEAR CONSTRAINTS Optimization problems are discussed which arise when complicated technical objects are modeled. Such problems contain well structured sets of nonlinear equations. Some approach is proposed for decomposition of discussed problems. 1. Лаптин Ю. П., Журбенко Н. Г. Разработка программных средств оптимизации сложных технических объектов // Теорія оптимальних рішень. – К.: Ін-т кібернетики ім. В.М.Глушкова НАН України, 2002. – С. 3 – 12. 2. Лаптин Ю. П., Журбенко Н. Г., Левин М. М., Волковицкая П.И. Использование средств оптимизации в системе автоматизированного проектирования энергетиче- ских котлоагрегатов КРОКУС // Энергетика и электрификация. – 2003. – № 7. – С. 41 – 51. 3. Shor N. Z. Nondifferentiable Optimization and Polynomial Problems. – London: Kluwer Academic Publishers, 1998. – 381 p. 4. Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяже- ния пространства в направлении разности двух последовательных градиентов // Ки- бернетика. – 1971. – № 3. – C. 51 – 59. 5. Пшеничный Б. Н. Метод линеаризации. – М.: Наука, 1983. – 136 с. 6. Ж. - Б. Ириарт – Уррути. Оптимизация и выпуклый анализ. – Киев: Издательская компания «КИТ», 2004. – 370 с. Получено 27.03.2005

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