«Стохастическое программирование и его приложения Научные редакторы: член-корреспондент НАН Украины П.С. Кнопов доктор технических наук В.И. Зоркальцев г. Иркутск 2012 УДК 519.856 ББК B 183.4 Стохастическое ...»

Институт систем энергетики им. Л.А. Мелентьева СО РАН

Институт кибернетики им. В.М. Глушкова НАН Украины

Иркутская государственная сельскохозяйственная академия

Стохастическое программирование

и его приложения

Научные редакторы:

член-корреспондент НАН Украины П.С. Кнопов

доктор технических наук В.И. Зоркальцев

г. Иркутск

2012

УДК 519.856 ББК B 183.4 Стохастическое программирование и его приложения / П.С. Кнопов, В.И.

Зоркальцев, Я.М. Иваньо и др. [Электронный ресурс]. – Иркутск: Институт систем энергетики им. Л.А. Мелентьева СО РАН, 2012. – 493c.; объем 700 Мб; 1 опт. компакт-диск (CD-ROM).

ISBN 978-5-93908-110-8.

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

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

Табл.: 33. Ил.: 56. Библиогр.: 339 назв.

Рецензенты:

доктор технических наук А.Ю. Горнов доктор физико-математических наук О.В. Хамисов кандидат технических наук О.В. Войтов Утверждено к печати Ученым советом Института систем энергетики им. Л.А. Мелентьева СО РАН © П.С. Кнопов, В.И. Зоркальцев, ISBN 978-5-93908-110- (Электронный ресурс) Я.М. Иваньо и др., © Российская академия наук, Содержание Введение.................................................. Математическое программирование I Модели и методы оптимизации в энергетических 1. исследованиях (Воропай Н.И., Зоркальцев В.И.)......... Субградиентный алгоритм минимизации с преобразованием пространства ( ) алгоритм (Журбенко Н.Г.)... Операторы преобразования пространства в квазиньютоновских методах и методах сопряженных градиентов (Журбенко Н.Г.).......................... Обоснование алгоритмов внутренних точек для задач 1. нелинейного программирования В.И., (Зоркальцев Пержабинский С.М.)................................ Сведение задач двухэтапной вероятностной оптимизации 1. с дискретным распределением случайных данных (Кибзун А.И., Норкин В.И., Наумов А.В.)............... Меры риска в задачах стохастической оптимизации для 1. получения робастных решений (Кирилюк В.С.).......... Метод эмпирических средних в задачах стохастической 1. оптимизации и оценивания (Кнопов П.С.).............. Решение двухэтапных задач стохастического программирования большой размерности PNK-методом (Кузьменко В.Н.)................................... Ускоренные модификации субградиентного метода Поляка для овражных выпуклых функций (Стецюк П.И.)..... Математическое моделирование II Модели несовершенной конкуренции применительно к 2. анализу электроэнергетического рынка Сибири (Айзенберг Н.И., Киселва М.А.)........................... Модели оптимизации размещения посевов сельскохозяйственных культур в условиях неполной информации (Астафьева М.Н., Иваньо Я.М.)...................... Задачи параметрического программирования с вероятностными и интервальными параметрами применительно к задачам оптимизации сельскохозяйственного производства (Барсукова М.Н., Иваньо Я.М.)................... Оценка переменных режима ЭЭС методами вероятностного потокораспределения (Болоев Е.В., Голуб И.И.).... Модели оптимизации взаимодействия участников в агропромышленных кластерах с вероятностными параметрами (Бузина Т.С., Иваньо Я.М.)........................ Макромодель энергетики и экономического роста (Горбачук В.М., Пепеляев В.А.)............................. О создании энергетических плантаций в России и мире 2. 2. надежности при многоуровневом моделирования систем газоснабжения (Дзюбина Т.В., Илькевич Н.И.)........... Информационно-программное обеспечение задач анализа 2. и наджности при многоуровневом моделировании газоснабжающих систем (Дзюбина Т.В., Метлкин А.М.)...... 2. Модели анализа состояний электроэнергетических систем 2. (Зоркальцев В.И., Пержабинский С.М.)................ 2. электроэнергетических систем (Крупенв Д.С.).......... Программно-вычислительный комплекс оценки надежности электроэнергетических систем «Янтарь», алгоритмические особенности (Лебедева Л.М.)................... 2. продукта и добавленной стоимости в продуктивной

ВВЕДЕНИЕ

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

В книге представлены результаты разработки, координации совместных усилий в указанном направлении трех научных коллективов:

Института кибернетики им. В.М. Глушкова НАН Украины, Института систем энергетики им. Л.А. Мелентьева СО РАН, Иркутской государственной сельскохозяйственной академии. Тематика докладов охватывает ряд важных направлений теории оптимизации:

методы решения негладких невыпуклых задач стохастической оптимизации, необходимые условия оптимальности, методы вычисления стохастических градиентов;

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

методы оптимизации и оценивания параметров стохастических систем при наличии априорной информации относительно области их значений;

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

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

модели и методы анализа и синтеза надежности функционирования систем энергетики и энергообеспечения;

модели и методы оптимизации функционирования и развития газоснабжающих систем;

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

В книге представлены материалы, которые обсуждались на РоссийскоУкраинском научном семинаре «Стохастическое программирование и его приложения», прошедшего 23 – 29 июля 2012 года в городе Иркутске.

Семинар осуществлялся при финансовой поддержке НАН Украины (грант № 01-01-12 (У) ) и РФФИ (грант № 12-01-90550-Укр_г).

Книга подготовлена авторским коллективом в следующем составе:

Айзенберг Н.И. (гл. 2.1), Астафьева М.Н. (гл. 2.2), Барсукова М.Н. (гл. 2.3), Болоев Е.В. (гл. 2.4), Бузина Т.С. (гл. 2.5), Воропай Н.И. (гл. 1.1), Голуб И.И.

(гл. 2.4), Горбачук В.М. (гл. 2.6), Губий Е.В. (гл. 2.7), Дзюбина Т.В. (гл. 2.8, гл. 2.9), Журбенко Н.Г. (гл. 1.2, гл. 1.3), Зоркальцев В.И. (гл. 1.1, гл. 1.4, гл.

2.10, гл. 2.11), Иваньо Я.М. (гл. 2.2, гл. 2.3, гл. 2.5), Илькевич Н.И. (гл. 2.8), Кибзун А.И. (гл. 1.5), Кирилюк В.С. (гл. 1.6), Киселва М.А. (гл. 2.1), Кнопов П.С. (гл. 1.7), Ковалв Г.Ф. (гл. 2.13), Крупенв Д.С. (гл. 2.12), Кузьменко В.Н. (гл. 1.8), Лебедева Л.М. (гл. 2.14), Метлкин А.М. (гл. 2.9), Мокрый И.В.

(гл. 2.11), Наумов А.В. (гл. 1.5), Норкин В.И. (гл. 1.5), Пержабинский С.М.

(гл. 1.4, гл. 2.10), Пепеляев В.А. (гл. 2.6), Постников И.В. (гл. 2.15), Стенников В.А. (гл. 2.15), Стецюк П.И. (гл. 1.9, гл. 2.16).

Математическое программирование УДК 330+519.

МОДЕЛИ И МЕТОДЫ ОПТИМИЗАЦИИ

В ЭНЕРГЕТИЧЕСКИХ ИССЛЕДОВАНИЯХ

Институт систем энергетики им. Л.А. Мелентьева СО РАН Институт систем энергетики им. Л.А. Мелентьева СО РАН Аннотация. В статье даётся краткая характеристика некоторых моделей оптимизации функционирования и развития систем энергетики, созданных в Институте систем энергетики Сибирского отделения Российской академии наук. Рассматриваются модели оптимизации развития топливно–энергетического комплекса России, вычислительный комплекс, созданный для анализа надёжности электроэнергетических систем, модель потокораспределения в гидравлических системах. Даётся общее представление о разрабатывавшихся в Институте систем энергетики методах оптимизации, в т.ч. метод приведённого градиента, алгоритмы внутренних точек, метод модифицированной функции Лагранжа, алгоритмов отсечений.

Ключевые слова. Модели оптимизации функционирования и развития систем энергетики. Алгоритмы решения задач математического программирования.

Введение Институт систем энергетики им. Л.А. Мелентьева (ИСЭМ СО РАН) создан в 1960 году. Он расположен в г. Иркутске, в центре Сибири. До года он назывался Сибирский энергетический институт (СЭИ). ИСЭМ является одним из 8 институтов, составляющих Иркутский научный центр Сибирского отделения Российской Академии наук.

Изначально основным направлением научных исследований Института систем энергетики являлся поиск наилучших вариантов формирования, функционирования и развития сложных энергетических объектов и систем [1]. Основным инструментом в этих исследованиях служат математические модели. Для реализации математических моделей функционирования и развития систем энергетики необходимо применение специальных методов вычислительной математики. Среди них особо важную роль играют методы оптимизации – алгоритмы выбора наилучших вариантов по заданным критериям среди возможных. Разработка, развитие, экспериментальные и теоретические исследования методов оптимизации, их применение к моделям энергетики составляют также одно из направлений научных исследований института.

В данной статье постараемся познакомить читателей с некоторыми энергетики, а также с оригинальными методами решения задач оптимизации, признание.

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

Сначала приведём краткую характеристику некоторых математических моделей оптимизации созданных в институте. Затем представим создававшиеся в институте методы оптимизации. Здесь будут рассмотрены четыре класса методов оптимизации. Эти методы мы персонифицируем с авторами исходных их идей. Хотя, конечно, в развитии и реализации этих методов участвовали многие сотрудники института. Необходимо отметить, что создателями рассматриваемых здесь методов оптимизации были как специалисты-энергетики (Л.А. Крумм, Ш.С. Чурквеидзе). Это отражает полезность симбиоза разных наук, который был заложен еще при основании института.

Модель выбора оптимальных долгосрочных вариантов развития топливно-энергетического комплекса страны Одной из крупных комплексных разработок Института систем энергетики, потребовавшей привлечения специалистов разного профиля, является создание модели (в нескольких модификациях) для исследования долгосрочных, на 20 и более лет, вариантов развития топливноэнергетического комплекса страны [2, 3]. Модель предназначена для определения наиболее рациональных путей развития отраслей энергетики с учётом существующих взаимосвязей отдельных видов энергоресурсов при их производстве и их взаимозаменяемости при потреблении. Многие объекты энергетического комплекса (электростанции, нефте- и газодобывающие предприятия, нефтеперерабатывающие заводы, системы теплоснабжения городов) являются очень капиталоёмкими, требуют длительного времени для ввода и реконструкции (на предпроектные и проектные исследования, на создание строительной базы и на само строительство). При этом многие энергетические комплексы функционируют длительное время – от 20 до 50, и более лет. Этим обусловлена необходимость заблаговременной системной проработки вопросов целесообразности сооружения в отдельных районах тех энергоресурсов. Необходимо рассматривать долгосрочные перспективы для оценки эффективности новых мощностей.

Первые, разрабатывавшиеся с конца 60-х годов прошлого века, модели оптимизации топливно-энергетического комплекса относились к классу условно – динамических. Рассматривалось состояние отраслей энергетики в годы t = 1, 2,..., T, соответствующие последним годам пятилетий. Модель имела вид задачи линейного программирования:

Переменные модели составляют векторы (здесь t - рассматриваемый год):

производственных мощностей;

y t – прирост между периодами t 1, t новых мощностей.

Заданными являются:

матрицы At и C t – коэффициентов использования существовавших и новых технологий;

вектор заданных потребностей в различных видах энергоресурсов по разным регионам b t ;

располагаемые к году t мощности, составляющие вектор N t ;

максимально возможные вводы новых мощностей, составляющие вектор Mt.

Динамика изменения располагаемых мощностей представляется в виде следующего соотношения где R t – мощности, выводимые из строя за период между годами t и t + 1.

технологических способов – величина неотрицательная, и она ограничена сверху располагаемыми мощностями. Ограничения (3) означают, что в заданных сверху ограничений на возможности ввода новых мощностей за период [ t 1, t ].

Соотношение (1) задаёт балансовые условия на производство, транспортировку и потребление отдельных видов энергоресурсов. Матрицы коэффициентов [ At, C t ]. Эта матрица имеет двойную блочную структуру – по территориальному и отраслевому принципам.

В модели рассматриваются балансы энергоресурсов применительно к каждому крупному региону. Этих регионов относительно небольшое число:

от 12 до 17 в разных вариантах модели развития ТЭК России. Уместно напомнить, что Россия является самой большой в мире по площади страной.

описывающим поставки отдельных видов энергоресурсов из одного региона в другой.

В отраслевом разрезе выделяются следующие взаимосвязанные блоки.

1. Уголь. В этом блоке описываются процессы добычи, обогащения, перевозок между регионами (транспортом общего пользования) и энергетическое потребление разных видов углей.

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

5. Электро- и теплоэнергетика. В этом блоке описываются разные производства электроэнергии учитывается, что многие электростанции теплоэнергию для производственных нужд, а также для отопления и горячего водоснабжения населения.

Целевая функция (4) означает, что минимизируются затраты на функционирование и развитие топливно-энергетического комплекса.

Компоненты вектора c t соответствуют переменным текущим издержкам.

Компоненты вектора k t имеют вид:

где s t – переменные текущие издержки, d t – инвестиции на создание единицы производственных мощностей, E – коэффициент эффективности капиталовложений (обычно в расчётах принимается равным 0,12).

Модель анализа надёжности электроэнергетических систем В начале 70-х гг. в Сибирском энергетическом институте (ныне ИСЭМ СО РАН) под руководством академика Ю.Н. Руденко была разработана методика анализа надёжности электроэнергетических систем (ЭЭС), основанная на методе статистических испытаний (метод Монте-Карло) [4, 5].

Методика анализа надёжности состоит из трёх основных частей:

1. Вероятностный блок, где формируются случайные состояния режимов функционирования ЭЭС с использованием датчиков случайных чисел. Случайность позволяет «проигрывать» разные возможные ситуации при функционировании ЭЭС (случайнее колебания нагрузки, отказы оборудования и др.).

2. Оценка дефицита мощности для каждого выбранного случайного состояния системы. Это осуществляется на основе специальной модели оценки дефицита мощности, имитирующей функционирование электроэнергетической системы при заданных условиях. В результате определяется для каждого узла электроэнергетической системы дефицит электроэнергии (сам факт его возникновения и его объём).

3. Блок вычисления показателей надёжности (в том числе вероятности бездефицитной работы системы и энергоузлов, математического ожидания дефицита мощности и др.), в котором обрабатывается информация, накопленная в результате многократных оценок случайных состояний ЭЭС.

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

Для реализации модели оценки дефицита мощности используются алгоритмы метода внутренних точек [6, 7].

Другим объектом оптимизации в рассматриваемой методике является задача выбора средств повышения надёжности электроснабжения. Это обеспечивается за счёт создания дополнительных мощностей по производству электроэнергии и развитию линий электропередач между узлами электроэнергетической системы.

Модели потокораспределения Одним из приложений теории и методов оптимизации являются гидравлические цепи. Теория гидравлических цепей была создана Л.Я. Хасильевым и А.П. Меренковым [8] в Институте систем энергетики для осуществляющих водоснабжение, теплоснабжение, газоснабжение, транспортировку нефти и нефтепродуктов. Эти модели можно представить в виде систем нелинейных уравнений, либо в виде эквивалентных задач математического программирования. В качестве исходного аналога при создании теории гидравлических цепей послужила теория электрических цепей, созданная в XIX веке. Приведём для примера модель классической задачи потокораспределения.

ориентированным графом. Пусть m – число узлов, n – число дуг этого графа. Тогда A – матрица инциденции размера m n с элементами: aij = 1, если дуга j выходит из узла i ; aij = 1, если дуга j входит в узел i ; aij = 0, если дуга j не инцидентна узлу i. В каждом столбце матрицы A только два ненулевых элемента: один равен +1, другой равен –1.

Заданными также являются вектор b R n и вектор c R n. Компоненты вектора b характеризуют расходы среды, поставляемые в систему (если bi > 0 ) или из системы (если bi < 0 ) для узла i = 1,..., m.

Компоненты вектора c характеризуют приращение давления на отдельных дугах. Если (вследствие работы насосов). Если c j < 0, то осуществляется дроселирование давления на дуге j = 1,..., n.

Переменные в модели составляют вектора Компоненты векторов x и y характеризуют величины расходов и потерь давления на отдельных дугах. Компоненты вектора u характеризуют давление в отдельных узлах системы.

Классическая задача потокораспределения состоит в отыскании векторов x, y, u, удовлетворяющих условиям:

Здесь условие (5) характеризует баланс расходов транспортируемой среды в каждом узле (аналог первого закона Кирхгофа). Условие (6) характеризует баланс давления для каждой дуги. Условие (7) выражает дугам j = 1,..., n. Здесь f вектор – функция с компонентами f j. Часто применяется квадратичная зависимость где kj – заданный коэффициент. Возможны и другие зависимости. Отметим, что в электрических цепях аналогом (7) является закон Ома.

Потребуем от функций fj выполнения следующих условий:

- являются возрастающими, f j ( ) > f j ( ), если - равны нулю в нуле, f j (0) = 0 ;

- непрерывные.

В силу указанных свойств каждой функции f j соответствует обратная ей функция, удовлетворяющая этим же условиям. Обратную функцию обозначим j. Итак, для любого вещественного Из указанных свойств функций f j и j следует существование для них первообразных:

Отметим, что функции F j и j являются строго выпуклыми, имеющими абсолютный минимум в нуле равный нулю.

Рассмотрим задачу выпуклого программирования В качестве решения этой задачи наряду с вектором x будет рассматривать вектор множителей Лагранжа u ограничений (9) и вектор y, связанный с x условием (7). Здесь f ( x)= F ( x).

Введём двойственную к (8), (9) задачу выпуклого программирования В качестве решения этой задачи наряду с векторами y и u будет рассматривать вектор множителей Лагранжа x ограничений (11).

Справедливо следующее утверждение [9].

Теорема. Если система уравнений (5) совместна, то система (5) – (7), программирования (10), (11) имеют решения. Причём решения любой из этих задач являются решением остальных двух. Среди решений данных задач векторы x, y имеют единственное значение.

Приведённая теорема позволяет сводить исходную систему уравнений к задаче выпуклого программирования, для решения которых могут применяться любые известные методы. Отметим, что для существования решения у системы (5) достаточно, если граф, характеризуемый матрицей инциденций A, является связным и выполняется условие Другие модели Необходимо упомянуть о других моделях оптимизации, создававшихся в ИСЭМ СО РАН: оперативного управления режимами функционирования электроэнергетических систем; оптимизации среднесрочных и долгосрочных программ развития электроэнергетических систем; оптимизации графиков ремонта оборудования электроэнергетики; оптимизации параметров технологических процессов и оборудования по переработке энергоресурсов;

оптимизация резервов и запасов топлива [17].

Метод приведенного градиента Одним из пионеров в разработке специальных методов расчета допустимых и оптимальных режимов электроэнергетических систем был Л.А. Крумм, ныне академик Эстонской Академии наук. Он длительное время работал в ИСЭМ и является одним из основателей электроэнергетического направления исследований института. Особенно большой вклад он внёс в создание моделей и методов оптимизации режимов функционирования электроэнергетических систем.

Л.А. Крумм является одним из создателей класса алгоритмов оптимизации, содержащим методы приведенного градиента в современной терминологии. Его первые работы по обсуждаемым здесь методам оптимизации появились в конце 50-х годов: в 1957 г. – в трудах Таллиннского политехнического института, в 1959 г. – в Известиях СО АН СССР [10, 11].

Л.А. Крумм хорошо понимал, что разработанный им метод может электроэнергетических систем. Поэтому при описании метода он, как правило, использовал общую запись задачи нелинейного программирования.

программирования – с двусторонними ограничениями-неравенствами на (удовлетворяющих ограничениям задачи) заведомо либо ограниченное, либо пустое (ограничения противоречивые).

i = 1,..., m, а также векторы x, x из R n. Причем x j < x j, Рассматривается задача при ограничениях Считается, что функции f i, i = 1,..., m, дифференцируемы. Следует отметить, что для моделей расчета электроэнергетических режимов функции f i существенно нелинейные. Поэтому задача (12) – (14) относится к классу собственно нелинейных и даже невыпуклых задач оптимизации.

Центральная идея метода приведенного градиента состоит в том, чтобы переменных через другие. Пусть вектор переменных x разбит на два вектора:

вектор базисных или зависимых переменных z R m и вектор независимых переменных y R n m. Для определенности будем считать, что первые n m компонент вектора x составляют вектор y, а остальные m компонент – вектор z. Причем вектор z представляется в виде вектор-функции от вектора y, которая равносильна ограничениям (13). То есть ограничения (13) приобретают вид В результате преобразований (15) задача (11) – (14) приобретает вид при ограничениях Эта задача имеет меньшее число переменных, чем задача (12) – (14), и все условия заданы в виде ограничений-неравенств.

Л.А. Крумм особо исследовал случай, когда текущее приближение y k, где k – номер итерации, является допустимым для задачи (16) – (18). Вектор s k определяется как направление уменьшения целевой функции от точки y k в области допустимых решений. Например, вектор s k можно определить как результат решения задачи при условиях Затем вычисляем шаг k с тем, чтобы вектор оставался в области допустимых решений задачи (16) – (18) и при этом минимизировал значение целевой функции.

Такой алгоритм в современной терминологии называется методом условного градиента решения задачи (16) – (18). Для исходной задачи (12) – (14) использование преобразования (15) означает, что изложенный алгоритм будет методом приведенного градиента.

Для решения вспомогательной задачи (19) – (21) и ее модификаций могут использоваться разные методы. Одно время для ее решения применяли разработанном Ш.С. Чурквеидзе, пойдет речь ниже. В дальнейшем стал использоваться метод внутренних точек.

Метод внутренних точек Сотрудник Института систем энергетики И.И. Дикин являлся автором оригинального метода внутренних точек решения задач линейного, и нелинейного программирования. Уже в 70-х годах этот метод нашел применение в реализации нескольких моделей СЭИ, в т.ч. анализа надежности электроэнергетических систем, в задачах выбора оптимальных термодинамики.

Исходной основой И.И. Дикина в разработке его алгоритма внутренних точек послужила очень любопытная и простая идея академика Л.В.

Канторовича по определению рациональной системы цен в случае неоптимального плана (речь конкретно шла о планах использования посевных площадей, хотя предложенный Л.В. Канторовичем подход вполне годится и для других проблем, в т.ч. для планов развития и ценообразования в энергетике).

программирования где – множества допустимых решений исходной (22) и двойственной (23) задач.

Заданными являются векторы c R n, b R m, матрица A размера m n.

Переменные составляют векторы x R n, u R m.

Пусть задача (22) моделирует процесс производства и использования некоторых видов продукции, составляющей вектор b. Вектор x состоит из показателей интенсивности технологии, A – матрица технологических коэффициентов. Задача (11) состоит в определении неотрицательных интенсивностей использования технологий, при которых обеспечивается выпуск заданного набора продукции при заданных ресурсах производства.

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

рациональной системы экономических оценок продукции, составляющих вектор u. Задачи (22), (23) тесно взаимосвязаны. В частности, справедливо следующее утверждение: для того, чтобы вектор x X был оптимальным решением задачи (22) необходимо и достаточно, чтобы существовал вектор u U, при котором выполняется условие дополняющей нежесткости Это условие играет важную роль в экономических приложениях.

оптимуму», а компоненты вектора g (u ) – в качестве экономических оценок эффективности отдельных технологий.

По каким-то причинам, в т.ч., например, из-за несовершенств линейной модели, может быть выбран неоптимальный с позиций задачи (22) план. Для случая, когда принятое решение x X неоптимально, Л.В. Канторович в 1965 г. предложил методику формирования приближенных оценок ресурсов, основанную на минимизации взвешенной суммы квадратов отклонений в условиях дополняющей нежёсткости (26).

Пусть имеется допустимое решение x k X с положительными всеми компонентами x k > 0, j = 1,..., n. По одному из вариантов методики Л.В.

Канторовича для такого решения вектор оценок определяется правилом где Если вектор x k был неоптимальным решением задачи (11), то у вектора g (u k ) будут как положительные, так и отрицательные компоненты.

необходимость увеличения интенсивности использования данной технологии j в целях уменьшения суммарных затрат. Если g j (u k ) < 0, то технология j имеет отрицательную рентабельность в рамках цен u k и интенсивность ее использования должна быть сокращена.

На основе приведенного правила получения экономических оценок ресурсов и технологий И.И. Дикиным в 60-х годах был разработан [12, 13] алгоритм итеративного улучшения решения задачи (22), в котором следующее решение x k +1 X определяется по формуле при Первые программные реализации такого «непривычного» на фоне широко использовавшегося в 60-х годах симплекс-метода показали хорошую работоспособность. И.И. Дикиным были доказаны следующие важные факты (при предположении о невырожденности задачи (22)). Если задача (22) имеет оптимальное решение, то последовательность векторов x k, k = 1, 2,..., будет сходиться к одному из оптимальных решений. Причем получаемое оптимальное решение обладает важной особенностью – оно имеет минимальный набор активных ограничений по сравнению с другими оптимальными решениями. Скорость сходимости значения целевой функции c T x k к ее оптимальному значению – линейная, т.е. по геометрической оптимальному решению двойственной задачи [14].

Данный алгоритм в 70-х годах успешно развивался в России, в том числе в работах Ю.Г. Евтушенко, В.И. Зоркальцева, В.Г. Жадана. Были проведены интересные исследования непрерывных аналогов алгоритмов.

Разработаны новые правила выбора шага область допустимых решений задачи математического программирования [6], двойственные алгоритмы внутренних точек. Уже с 70-х годов данные алгоритмы нашли широкое применение при реализации многих моделей энергетики [6]. С середины 80-х годов это семейство алгоритмов привлекло повышенное внимание во всём мире.

Метод вспомогательной функции и модифицированной функции Лагранжа В конце 60-х годов сотрудник Института систем энергетики Ш.С.

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

Фактически им был создан новый, оригинальный метод решения широкого класса задач оптимизации, в т.ч. линейного и нелинейного программирования, который сразу нашел эффективное применение в ИСЭМ электроэнергетических систем [15, 16, 17]. Этот метод используется и поныне в программно-вычислительном комплексе, предназначенном для электроэнергетических систем.

Идеи Ш.С. Чурквеидзе вылились уже в 70-х годах в особое направление методов оптимизации, получившее название метода модифицированной функции Лагранжа. Теоретическими исследованиями и разработками этого метода сначала занимались только российские математики, в т.ч. Б.Т. Поляк, В.В. Третьяков, А.С. Антипин [18, 19]. Затем к этому методу возник повышенный интерес во всём мире.

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

Рассмотрим задачу оптимизации при ограничениях в форме равенств.

Пусть f 0 – целевая функция, вектора переменных x R n. Обсуждается задача при ограничениях Будем считать, что все функции дифференцируемые.

Наличие ограничений даже только в форме равенств несколько усложняет проблему поиска экстремума по сравнению с задачами безусловной оптимизации. Как известно, Лагранж предложил общую очень плодотворную идею перехода от задачи (29), (30) к задаче без ограничений.

Он предложил добавить к целевой функции f 0 функции ограничений, просуммированные с некоторыми множителями, т.е. перейти к функции где i – коэффициенты, называемые множителями Лагранжа, L – функция Лагранжа, зависящая от вектора исходных переменных x и вектора множителей Лагранжа R m.

В результате приравнивания производных функции Лагранжа нулю, производных L по переменным i дает собственно не что иное, как выполнение условий (30), так как где f – вектор-функция с компонентами f i, i = 1,K, m.

Поскольку то приравнивание частных производных L по x к нулю дает соотношение Итак, равенство частных производных функций Лагранжа нулю удовлетворяющим условиям (30). При этом градиент целевой функции, согласно (32), должен находиться в подпространстве, образованном линейными комбинациями градиентов функций-ограничений.

В некоторых случаях условия (30), (32) являются достаточными для того, чтобы данное значение x было оптимальным решением задачи (29), (30). В частности, это имеет место для задач с выпуклой целевой функцией f 0 и линейными функциями-ограничениями.

Центральная идея Чурквеидзе состояла в использовании квадратичных аппроксимаций вида функциям. В данном случае величина i выполняет роль «маяка», к которому должно стремиться значение функции f i.

вспомогательную функцию Несложно увидеть, что данная функция содержит в качестве составной части функцию Лагранжа (31). Действительно, Появление дополнительных квадратичных составляющих весьма существенно. Они объясняют и использование термина «модифицированная функция Лагранжа».

На рассматриваемом примере хорошо можно пояснить суть метода модифицированной функции Лагранжа. Пусть на итерации k имеется текущее значение вектора переменных x k и приближенное значение k вектора множителей. Решая задачу безусловной оптимизации, находим вектор составляющей ( x j x k ) 2 можно вводить другие квадратичные добавки, как это делал Ш.С.Чурквеидзе, для противодействия «нехорошим свойствам»

целевой функции.

Точного решения этой вспомогательной задачи не требуется. Важно, чтобы точность нарастала по итерациям. Чурквеидзе использовал метод покоординатного спуска для решения подобных вспомогательных задач.

осуществляется корректировка вектора. Значение k должно быть увеличено, если f i k +1 < 0 (что будет стимулировать к увеличению f (x) на следующей итерации) или уменьшено, если f i k +1 > 0. В частности, можно положить Смысл корректировок состоит в том, чтобы достичь допустимого решения вспомогательной задачи, при котором f ( x) = 0. Пусть при некотором корректировке. Тогда, как несложно убедиться, вектор будет состоять из множителей Лагранжа решения x задачи (29), (30), удовлетворяющего необходимым условиям оптимальности.

Существуют различные варианты изложенного метода, применимые к разным типам задач математического программирования.

Хотелось бы отметить, что не только сам новый метод оптимизации, который может обрастать разными модификациями, является открытием Ш.С. Чурквеидзе. Не менее важным открытием является введенный им новый взгляд на множители Лагранжа.

Методы отсечений и погружений Большой вклад в развитие теории и методов оптимизации внёс профессор В.П. Булатов. Он являлся создателем лаборатории «Исследования операции» и отдела «Прикладной математики» в институте, в рамках которого велись широко известные в России и во всём мире работы по вычислительной математике. Он был организатором регулярно проводимой раз в 3 года с 1967 года Международной школы-семинара «Методы оптимизации и их приложения». На этой школе побывали многие известные российские и зарубежные специалисты в области прикладной математики.

Основные научные результаты В.П. Булатова сосредоточены в разработке и теоретическом исследовании класса методов отсечения и погружения. Воспользуемся следующей классификацией разрабатывавшихся В.П. Булатовым алгоритмов [20]. Все алгоритмы назовем методами отсечения. Они состоят из двух классов: «методов погружения» и «методов центрированных отсечений».

Методы погружений В.П. Булатов разделял на два типа. Первый из них – метод последовательного погружения надграфика целевой функции.

Рассматривается задача где x – вектор переменных из R n, (x) – целевая функция, K – множество допустимых решений. В.П. Булатов обычно рассматривал случай, когда K – компакт, т.е. замкнутое и ограниченное множество в R n. Хотя некоторые его алгоритмы могут работать и в случае, если K – неограниченное множество.

В методе последовательного погружения надграфика целевой функции считается, что множество допустимых решений обладает «достаточно хорошими свойствами» и явно задано. Например, это множество решений некой системы линейных неравенств. Считается, что все сложности сосредоточены только в целевой функции (x), которая может быть, например, недифференцируемой, неявно заданной и т.д.

Исходная идея метода последовательного погружения состоит в замене задачи (33) на эквивалентную ей задачу минимизации линейной функции с увеличенным на единицу количеством переменных. Введем функцию где – дополнительная переменная. Тогда задача (33) становится равносильной задаче при условиях где Суть метода состоит в том, что в процессе решения используется некоторая аппроксимация множества K n+1.

Пусть на итерации k определена аппроксимация K n+1. Решается вспомогательная задача при условиях Пусть x k, k – решение этой задачи. Если это не оптимальное решение задачи (35), (36), то переходим путем отсечения точки ( x k, k ) от K n+1 к другому множеству K n+1. Отсечение должно быть таковым, чтобы при этом не отбросить оптимальное решение задачи (27), (28).

Одним из способов «отсечений» является введение дополнительных линейных неравенств. Такой подход применялся ранее для решения задач целочисленного линейного программирования (алгоритмы отсечений Гомори) и для решения задач выпуклого программирования (алгоритм Келли). В указанных алгоритмах происходит постепенное «сужение»

аппроксимирующего множества В.П. Булатов разрабатывал алгоритмы с линейными отсечениями, в которых указанное включение не выполняется, в т.ч. из-за исключения некоторых введенных на предыдущих итерациях «отсечения» линейных неравенств.

Главное, что В.П. Булатовым была предпринята во многом успешная попытка создания общей теории отсечений, ведущих к оптимальному решению. В практическом плане кроме линейных отсечений интерес представляет рассматривавшийся им случай отсечений с помощью вогнутых функций. Если целевая функция (x) невыпуклая, то для общего случая оптимального решения задачи (33). В тех случаях, когда функция (x) допускает представление в виде суммы выпуклой функции и невыпуклой функции, хорошо аппроксимируемой снизу вогнутой функцией, имеются конструктивные пути нахождения глобального минимума (x) на компакте Второе, более общее направление в методах «погружения» названо последовательным погружением допустимого множества. Это обобщение рассчитано и на случай, когда в ограничениях задачи присутствуют «плохие»

ограничения. Собственно, этот случай можно свести к предыдущему. Пусть у задачи (33) имеются дополнительные ограничения где g i – некоторые «нехорошие» функции, в т.ч., например, невыпуклые или недифференцируемые. Введем функцию Затем рассмотрим задачу (35), (36), у которой множество K n +1 определено условием В итоге приходим к рассмотренному первому случаю.

В 1979 году в Докладах академии наук (ДАН) СССР вышла статья математика из Вычислительного центра Российской Академии наук Хачияна Л.Т. «Полиномиальные алгоритмы в линейном программировании». В этой статье рассматривалась модификация предложенного ранее известными математиками А.С. Немировским, Д.Б. Юдиным и Н.З. Шором метода эллипсоидов. Суть метода состояла в том, что допустимая область, содержащая оптимальное решение, погружалась в некий n -мерный эллипсоид. От этого эллипсоида на каждой итерации по специальным правилам отсекалась какая-то часть, не содержащая искомую точку оптимума. Оставшаяся часть погружалась в следующий эллипсоид меньшего объема. В результате сокращений на каждой итерации объемов эллипсоидов, содержащих искомую точку оптимума, за конечно число итераций можно было получить приближение к точке оптимума с любой точностью.

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

В.П. Булатову в самом начале истории результата о возможности решения задач линейного программирования за полиномиальное время пришла в голову простая мысль – не только эллипсоидами можно аппроксимировать множество решений. В итоге его обсуждения с еще двумя ведущими математиками СЭИ (это были И.А. Александров и Е.Г.

Анциферов) родился метод «центрированных отсечений», основанный на аппроксимации области, содержащей точку оптимума, n -мерным симплексом. Симплексом называется телесный линейный многогранник в n мерном пространстве, содержащий ровно n + 1 вершину. Разделение на каждой итерации многогранника на две части (содержащую и не содержащую точу оптимума) осуществлялось гиперплоскостью, проходящей через «центр тяжести» многогранника. Отсюда и название алгоритма – метод центрированных отсечений.

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

направлений СЭИ – ИСЭМ. Отв. ред. Н.И. Воропай. – Новосибирск:

Наука, 2010.

[2] Кузнецов Ю.А., Макаров А.А., Мелентьев Л.А. Система математических моделей для оптимизации перспективных энергетических балансов.

Теплоэнергетика, 1966. – № 2.

[3] Модели развития энергетики и согласования решений // Сб. научных трудов под ред. А.А. Макарова. – Иркутск: СЭИ СО АН СССР, 1984.

надежности электроэнергетических систем методом статистического исследования надежности больших систем энергетики. – Иркутск: СЭИ, 1975. – Вып. 4. – С.4 – 35.

вероятностного моделирования при анализе надежности сложных ЭЭС // электроэнергетических систем». – Рига, 1987. – С.344 – 345.

математического программирования (алгоритмы метода внутренних точек). – Новосибирск: Наука, 1988. – 144 с.

[7] Zorkaltsev, V., Perzhabinsky S. Model for power shortage estimation in electric power systems. Interior point algorithms. International Journal of Energy Optimization and Engineering. (appear) [8] Хасильев Л.Я., Меренков А.П. Теория гидравлических цепей. – М.:

Наука, 1985.

[9] Епифанов С.П., Зоркальцев В.И. Симметрическая двойственность в оптимизации и гидравлические цепи. // Вычислительные технологии, [10] Крумм Л.А. Методы решения общих уравнений стационарного режима электрической системы с учетом статистических характеристик нагрузок и генераторов при автоматическом регулировании частоты, напряжения и мощности // Труды Таллиннского политехнического института, 1957. – [11] Крумм Л.А. Две формы более общих уравнений экономичного режима объединенных энергосистем // Известия СО АН СССР, 1959.

[12] Дикин И.И. Итеративное решение задач линейного и квадратичного программирования // Доклады Академии наук, 1967. – Т. 141. – №4. – С.

[13] Дикин И.И. Итеративные алгоритмы решения задач линейного, квадратичного и выпуклого программирования // Опыт решения экономических задач математическими моделями. – Новосибирск:

Наука, 1967. – С. 31 – 38.

[14] Дикин И.И. О сходимости одного итерационного процесса // Управляемые системы. – Новосибирск, 1974. – Вып. 12. – С. 54 – 60.

[15] Сыров Ю.П., Чурквеидзе Ш.С. Некоторые методологические вопросы решения задачи оптимизации управления длительными режимами электроэнергетических систем // Методы управления большими системами. – Иркутск, 1970. – Т.2.

[16] Сыров Ю.П., Чурквеидзе Ш.С., Посекалин В.В. Метод вспомогательных характеристик для решения задачи оптимизации суточных режимов вспомогательной функции // Труды Иркутского политехнического института. Иркутск, 1971. – Вып. 2.

[17] Чурквеидзе Ш.С., Посекалин В.В. Метод и алгоритм оптимизации перспективных суточных режимов электроэнергетических систем // Математические модели для анализа и экономической оценки вариантов электроэнергетических систем. – Иркутск, 1971.

[18] Поляк Б.Т., Третьяков Н.В. Об одном итерационном методе линейного программирования, его экономической интерпретации // Экономика и математические методы. – Т. VIII. – Вып. 5. – 1972.

[19] Антипин А.С. Методы линейного программирования, основанные на прямой и двойственной модификации функции Лагранжа. – М.: ВЦ АН СССР, 1979. – 74 с.

[20] Булатов В.П. Методы погружения в задачах оптимизации. – Новосибирск: Наука, 1977. – 161 с.

УДК 519.

СУБГРАДИЕНТНЫЙ АЛГОРИТМ МИНИМИЗАЦИИ

С ПРЕОБРАЗОВАНИЕМ ПРОСТРАНСТВА ( ) – АЛГОРИТМ

Институт кибернетики им. В.М. Глушкова НАН Украины Аннотация. Приводится субградиентный алгоритм минимизации выпуклой функции в конечномерном евклидовом пространстве с преобразованием пространства. Алгоритм основан на процедуре одномерного спуска и является в некотором смысле монотонным. Алгоритм обеспечивает решение задачи с заданной точностью за конечное число итераций. Приводится оценка трудоемкости алгоритма при решении задачи оптимизации.

Ключевые слова. Оптимизация, субградиент, преобразование пространства, отсекающая плоскость, эллипсоид локализации, трудоемкость алгоритма.

Введение Более 40 лет назад был разработан субградиентный алгоритм минимизации с растяжением пространства в направлении разности двух последовательных градиентов – r алгоритм [1]. Практика использования r алгоритма показывает, что до сих пор он является одним из наиболее эффективных алгоритмов негладкой оптимизации. Однако теоретическое исследование эффективности r алгоритма далеко не закончено (даже для класса выпуклых функций).

В данной статье приводится описание ( ) алгоритма – результаты автора по разработке субградиентного алгоритма сравнимой с r алгоритмом эффективностью и с его основными характеристиками:

использование процедуры одномерной минимизации и растяжение пространства с большими коэффициентами.

Задача –минимизации Рассматривается задача минимизации ограниченной снизу выпуклой f * = min{ f(x)|x R n }, X * – множество точек минимума функции f (x).

Для заданного числа 0 введем –оптимальное множество X * ( ), Произвольную точку ~ X * ( ) и значение функции f = f ( ~ ) будем называть решением задачи –оптимизации ( –решением).

Пусть задан шар начальной локализации –решения D( z, R ) :

z R n центр шара, R > 0 его радиус. Будем предполагать, что шар D( z, R ) содержит хотя бы одну точку минимума x* X *. Поэтому D( z, R) X * ( ). Далее характеристика множества начальной локализации будет уточнена (см. замечание к утверждению 10).

–субградиент Мы будем использовать несколько отличное от классического определение –субградиента [2 – 4]. Вектор g R n называется (, f ) cубградиентом функции f (x ) в точке z, если для x выполняется неравенство:

где f f * ; R1. Значение f на k ой итерации алгоритма решения задачи – оптимизации обычно равно полученному рекордному значению функции f (x). Если значение f * известно априори, то f = f *. Обычное классическое определение – субградиента соответствует определению (, f ) субградиента (1) при f = f ( z ), 0. Обобщенный градиент (субградиент) функции f (x), в т. z в классическом смысле [5] является (0, f ( z )) –субградиентом: f ( z ) = G (0, f ( z ), z ).

Через G (, f, z ), f ( z ) будем обозначать множество (, f ) субградиентов и множество обобщенных градиентов функции f (x) в т. z соответственно. В дальнейшем предполагается, что имеются алгоритмы выg ( x) f ( x) Таким образом, (, f ) – субградиент в некоторой точке z1 является (, f ) – субградиентом в любой другой точке z2. Формула (2) определяет правило пересчета параметров (, f ) – субградиента. G (, f, z ) по своим свойствам аналогично множеству f (z ) (выпуклость, замкнутость и т.д., Отметим два простых (но важных для дальнейшего) утверждения.

Утверждение 1. Если X (, f ) =, то f является – решением.

Утверждение 2. Если f f * + 2, то X * ( ) X (, f ).

Агрегированный – субградиент точку z с нормалью R n, | |> 0. P + ( z, ) = {x R n | ( x z, ) 0} – полупространство, определяемое (секущей) плоскостью P( z, ). Следующее утверждение соответствует обычному построению отсекающих плоскостей Замечание. Если f = f * (задача с известным значением минимума), то субградиент g f (z ) является (, f * ) – субградиент с = ( f ( z ) f * ).

Для случая обычной задачи минимизации ( = 0 ) величина "сдвига" h = ( ) / | g |= ( f ( z ) f * ) / | g | в точности соответствует шаговому множителю метода Поляка [6].

( x z, g ) ( ), а вектор «сдвига» ~ z отсекающей плоскости можно min{1 / 2 | y |2 : ( y, g ) ), где =. Обобщим этот результат для множества субградиентов. Пусть gi G ( i, f, z ), i = 1,K, m, i = i. Тогда X (, f ) содержится в пересечении подпространств: ( x z, gi ) i, (не исключается, что это пересечение пусто). Вектор «сдвига» y для множества –субградиентов G ( i, f, z ) из точки z определим решением следующей задачи:

Если система (4) несовместна, то вектор y не определен.

Утверждение 3. Пусть система ограничений (4) – несовместна. Тогда f является решением задачи –оптимизации и выпуклая оболочка множества –субградиентов G ( i, f, z ) содержит 0.

Утверждение 4. Пусть:

b) система (4) совместна;

y, – оптимальные значения прямых и двойственных переменных задачи (3), (4);

Тогда:

Если условие b) не выполнено, то положим g = 0.

Вектор g, определяемый в утверждении 4, будем называть агрегированным –субградиентом множества субградиентов G ( i, f, z ).

Геометрический смысл агрегированного –субградиента: агрегированный –субградиент принадлежит выпуклой оболочке множества субградиентов G ( i, f, z ) и обеспечивает максимальный сдвиг отсекающей плоскости.

Утверждение 5. Пусть для всех субградиентов i = <, i = 1,K, m. Тогда агрегированный субградиент является вектором наименьшей длины выпуклой оболочки множества субградиентов ( g = Nr{g1,K, g m } ).

Таким образом, для множества –субградиентов G ( i, f, z ) с одинаковыми значениями i агрегированный –субградиент совпадает с кратчайшим вектором выпуклой оболочки G ( i, f, z ). Именно этот вектор обычно используется при построении –субградиентных методов оптимизации. Введенное выше определение агрегированного –субградиента полезно в следующих смыслах. Во-первых, при решении задачи (3 – 4) может оказаться, что некоторое значение i > 0 даже если соответствующее значение i >. Обычно такие –субградиенты при решении задачи – оптимизации не используются. Во-вторых, при использовании g = Nr{g1,K, g m } все –субградиенты при выборе направления сдвига из точки z оказываются «равноправными» по отношению к значениям i :

вектор g = Nr{g1,K, g m } не зависит от –параметров. Однако значения – параметров существенны для локализации – решения.

Использование введенного агрегированного –субградиента позволяет получать модификации –субградиентных методов минимизации по обычной схеме их построения.

На основе утверждения 5 разработан оригинальный алгоритм решения задачи проектирования на политоп (определения вектора g = Nr{g1,K, g m } ) [8].

Утверждение 6. Для заданной точки z, направления (спуска) (| |= 1) и Алгоритм генерации –субградиента утверждения 6 имеет много субградиентов [3], [9].

Локализаторы –решения Следующие два утверждения касаются построения специальных эллипсоидов минимального объема, содержащих подмножества шара простой структуры (сегмент и сектор).

определяемая секущей плоскостью P( ~,1 ), где ~ = z + h ; 0 h < R, | |= 1.

W * – эллипсоид минимального объема с центром в точке ~, содержащий сегмент W, D* ( z, R ) – шар минимального объема, содержащий эллипсоид W *, V (K ) – объем тела K. R ( ) = ( 1) T + I оператор растяжения пространства [5] по направлению с коэффициентом.

W * эллипсоид минимального объема с центром в т. z, содержащий сектор W, D* ( z, R ) шар минимального объема, содержащий W * ;

* = (2 1 ) / | 2 1 |, * = (2 + 1 ) / | 2 + 1 |, {i, i = 1,K, n 2} – ортонормированный базис подпространства ортогонального векторам *, *.

Утверждение 8.

где Заметим, что построение эллипсоида W * приведено в работе [7].

Приведенный оператор преобразования эллипсоида W * в шар отличен от используемого в [7] «однорангового эллипсоидального оператора».

Существенное отличие состоит в том, что все собственные числа самосопряженного оператора не меньше 1.

Оператор преобразования формулы (9) можно представить в слеR * / (* ) R1 / ( * ), Из утверждения 8 следует, что объем эллипсоида W * меньше объема шара D* ( z, R ) только для < / 2 ( > / 2). Поэтому для использования такого эллипсоида в качестве локализации –решения необходим алгоритм генерации двух –субградиентов, угол между которыми тупой. Описание одного из таких алгоритмов приведено ниже.

Генерация сектора (алгоритм AlgSectorLocation) Приведем итеративный алгоритм (AlgSectorLocation) генерации (по Обозначим E = {e1, e2,K, em } – множество векторов ei R n, i = 1, K m, Nr{E} – вектор выпуклой оболочки множества E минимальной длины.

Описание алгоритма AlgSectorLocation 1 – ая итерация.

Вычисляем g1 f ( z ). Если g1 = 0, то останов (задача минимизации f (x) решена), иначе e1 = g1 / | g1 |.

Используя процедуру одномерной минимизации по направлению e1, вычисляем –субградиент g 2 G (, f, z ), для которого, ( g 2, e1 ) (см. утверждение 6). Если g 2 = 0, то останов (задача –минимизации f (x) решена).

Если p1 = 0, то останов (задача – минимизации f (x) решена). Если cos(1 ) 1 +, то останов, иначе переход на следующую итерацию.

Итерация (k + 1) (k = 1,2 K).

Используя процедуру одномерной минимизации по направлению, ( g m +1, pk ) 0 (см. утверждение 6). Если g m +1 = 0, то останов (задача –минимизации f (x) решена). Заметим, что в результате одномерной минимизации значение f может уменьшиться. В этом случае производится пересчет (, f ) параметров векторов множества Gk согласно (2).

где I – множество индексов i, для которых i > 0.

множество «активных» векторов из Ek +1 относительно операции Nr{.}, n | Ek +1 | 2 ). Перенумеруем вектора множества Ek +1, таким образом, чтобы Ek +1 = {ei, i = 1,2 K m; }, 1 2 K m > 0 (вектора Gk +1 перенумеровываются соответственно Ek +1 ).

Если cos( k +1 ) 1 +, то останов, иначе переход на следующую итерацию.

Утверждение 9. Алгоритм AlgSectorLocation конечен. При останове алгоритма выполняется одно из следующих условий: a) задача – минимизации f (x) решена; b) получены такие отсекающие плоскости P( z,1 ), P( z, 2 ), что (1, 2 ) = cos( k +1 ) 1 +. Справедливы следующие оценки значений | pk +1 | и sin( k +1 ) ( k +1 = k +1 ) (Здесь и далее pk +1 =| pk +1 |2 ).

Приведем некоторые свойства формулы (13). Нетрудно видеть, что то отсюда следует оценка:

P( z,1 ), P( z, 2 ) ). Тогда из (15) следует Можно показать, что функция ( pk +1 ) правой части (14) монотонно возрастает для pk +1 [0,1 / n], причем (0) = 0, (1 / n) = 1. Поэтому оценка (14) содержательна лишь для pk +1 < 1 / n. Например, (1 / n 2 ) = (1 + 1 / n).

Поэтому, если pk +1 1 / n 2, то sin( k +1 ) Отметим, что при этом, в соответствии с (10), (11), q = sin( k +1 ) 0. (любобытно заметить, что коэффициент уменьшения объма локлизации в Из приведенных оценок (12), (14), следует, что алгоритм AlgSectorLocation гарантирует коэффициент q 0.7 не более чем за n 2 итераций.

Автор, конечно, понимает, что эта оценка удручающе плоха. Однако это оценка трудоемкости и можно надеятся, что при реработе алгоритма она практически не будет реализовываться (пример такого алгоритма всем известен – симплекс алгоритм).

( ) –алгоритм В основе предлагаемого –субградиентного алгоритма минимизации лежит следующая простая идея. Задано число (параметр алгоритма) q, Пусть на итерации k получены: точка xk, Ak – невырожденное линейное преобразование ( Bk = Ak 1 ), f k – рекордное значение функции f (x), Rk – параметр эллипсоида локализации Ek множества X (, f k ) :

Итерация k + 1 алгоритма производится в преобразованном пространстве Yk = Ak X, где X – исходное пространство переменных. Образом эллипсоида Ek в пространстве Yk является шар D( yk, Rk ), где yk = Ak xk. На итерации k + 1 устанавливается факт решения задачи 2 – V ( Ek +1 ) qV ( D( yk, Rk )). Построение этого эллипсоида и параметра f k + производится на основании использования процедур одномерной минимизации в соответствии с алгоритмом AlgSectorLocation. При этом на каждой итерации этого алгоритма вычисляются значения коэффициентов уменьшения объемов эллипсоидов локализации множества X (, f k ) q1 и q2 согласно утверждениям 7 и 8 соответственно. Пусть qk +1 = min{q1, q2 }. Если qk +1 q, то алгоритм AlgSectorLocation прекращает работу.

Возможны два случая.

Если qk +1 = q1, то оператор k +1 определяется оператором утверждения (7). Параметры утверждения (7) определяются следующим образом: = g / | g |, h = ( ) / | g ) |, где g – агрегированный субградиент текущего множества субградиентов алгоритма AlgSectorLocation. Если h > Rk, то останов – задача решена. Иначе переход в новую точку (соответствует сдвигу отсекающей плоскости агрегированного субградиента в преобразованном пространстве): x = x hB g / | g |.

Если qk +1 = q2 > q1, то оператор k +1 определяется оператором утверждения (8). Параметры утверждения (8) определяются следующим образом: 1 = e1, 2 = / | |, где e1, – текущие вектора алгоритма AlgSectorLocation. Перехода в новую точку не происходит: xk +1 = xk.

Преобразование пространства на итерации k + 1 определяется оператором k +1 : Ak +1 = k +1 Ak.

На основании [11] можно доказать следующее утверждение об эффективности приведенного алгоритма.

Утверждение 10. Для числа итераций k алгоритма, за которые он обеспечивает решение 2 –оптимизации, справедлива следующая оценка:

где – относительная точность решения задачи ( = /(RC ), где C оценка сверху норм субградиентов в исходном шаре локализации D( z, R ) ).

Замечания 1. При доказательстве утверждения 10 предполагается, что для шара начальной локализации –решения D( z, R ) выполняется следующие условия. Пусть C –оценка сверху норм субградиентов в точках шара ограничена: g ( x) C ( g ( x) f ( x); x D( z, R)). Шар D( z, R ) содержит такой шар x* X * ), что все его точки являются –решениями: d ( x*, r ) X * ( ).

Учитывая ограниченность норм субградиентов, можно считать, что Поясним смысл используемой относительной точности. Из ограниченности норм субградиентов, имеем следующую начальную оценку:

чальная оценка улучшена в раз.

Численная эффективность ()–алгоритма.

Тестовые задачи:

где n = 106 /( n 1). Степень вытянутости линий уровня («овражности») функций не зависит от размерности и равна 106. Начальная точка xi = 1.0, i = 1,K n. Параметр точности решения по функционалу = 106.

Обозначения колонок таблиц: nVarbl – число переменных; qVolum – значение параметра уменьшения объема локализации решения на итерации (параметр алгоритма); nIter – число итераций; nLStep – среднее число применения алгоритма одномерной минимизации на одной итерации;

Alpha – среднее значение коэффициента растяжения пространства; r – алгоритм – число итераций r –алгоритма.

Приведенные численные эксперименты демонстрируют достаточно высокую эффективность ( ) алгоритма, сравнимую с эффективностью r алгоритма [5] (по числу итераций). Результаты выявляют следующие интересные его особенности.

Среднее число применения алгоритма одномерной минимизации на одной итерации оказывается малым в сравнении с гарантированной его оценкой ( n 2 ).

Даже если параметр гарантируемого уменьшения объема локализации решения на каждой итерации задается малым (0.99), тем не менее, среднее значение коэффициента растяжения пространства оказывается существенно больше единицы.

Заключение Качественная интерпретация ( ) –алгоритма состоит в следующем.

Алгоритм относится к классу методов с преобразованием пространства [5].

На каждой итерации алгоритма преобразование состоит в применении операторов растяжения пространства по ортогональным направлениям.

Параметры преобразования определяются построением эллипсоидов локализации –решения. Эллипсоиды локализации строятся на основе информации, получаемой в результате применения процедуры одномерной минимизации. На каждой итерации обеспечивается уменьшение объема локализации –решения в не менее чем заданное число q раз (параметр агоритма). Если в результате процедур одномерной минимизации происходит существенное улучшение рекордного значения функции, то преобразование пространства определяется оператором растяжения по направлению агрегированного субградиента. В противном случае, за конечное число одномерных процедур минимизации гарантируется генерации (по крайней мере) двух субградиентов с настолько тупым углом между ними, что он обеспечивает построение эллипсоида локализации решения с требуемым уменьшением объема локализации. При этом преобразование пространства определяется операторами растяжения по n 1 ортогональным направлениям. Причем с максимальным коэффициентом производится растяжение по направлению разности двух ортонормированных субградиентов из выпуклой оболочки построенных субградиентов. Таким образом, образно выражаясь, ( ) –алгоритм объединяет алгоритмы Н.З. Шора с растяжением пространства по субградиенту и по разности двух последовательных субградиентов.

Получена оценка трудоемкости ( ) –алгоритма для решения задачи –оптимизации. Численные эксперименты показывают, что (по числу итераций) эффективность ( ) –алгоритма сравнима с эффективностью r –алгоритма Н.З. Шора. Однако трудоемкость одной итерации ( ) – алгоритма существенно больше.

[1] Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов // Кибернетика. – Киев: Наук. думка, 1971. – [2] Brondsted A. and Rockafellar R.T. On the subdifferentiability of convex functions // Proc. Amer. Math. Soc. 16, 1965. – Pp. 605 – 611.

[3] Lemarechal C., Mifflin K. Nonsmooth Optimization. – Oxford: Pergamon Press, 1978. – 180 p.

[4] Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. – М.: Наука, 1981. – 384 с.

[5] Шор Н.З. Методы минимизации недифференцируемых функций и их применение. – Киев: Наук.думка, 1979. – 200 с.

[6] Поляк Б.Т. Минимизация негладких функционалов // Журн. вычислит.

математики и матем. физики, 1969. – Т.9, № 3. – С. 507 – 521.

[7] Стецюк П.И. Ортогонализующие линейные операторы в выпуклом программировании (Часть I) // Кибернетика и системный анализ, 1997.

[8] Журбенко Н.Г. Алгоритм проектирования на политоп // Теорія оптимальних рішень, 2008. – № 7. – C. 125 – 132.

[9] Ржевский С.В. Монотонные методы выпуклого программирования. – Киев: Наук. думка, 1993. – 319 с.

[10] Журбенко Н.Г. Об одном классе методов минимизации с преобразованием пространства // Методы решения экстремальных задач, 1996. – [11] Журбенко Н.Г. Оценка эффективности одного класса –субградиентных методов минимизации с преобразованием пространства // Оптимизация и ее приложения, 1997. – C. 49 – 54.

УДК 519.

ОПЕРАТОРЫ ПРЕОБРАЗОВАНИЯ ПРОСТРАНСТВА В КВАЗИНЬЮТОНОВСКИХ МЕТОДАХ И МЕТОДАХ СОПРЯЖЕННЫХ ГРАДИЕНТОВ

Институт кибернетики им. В.М. Глушкова НАН Украины Аннотация. Приводится интерпретация квазиньютоновского условия и условия сопряженности направлений при построении квазиньютоновских методов и методов сопряженных направлений на основе использования операторов преобразования пространства.

Ключевые слова. Kвазиньютоновский метод, сопряженные направления, оператор преобразования, минимизация.

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

Имеются различные интерпретации и схемы построения этих методов [1 – 3].

Общая схема квазиньютоновских методов и методов сопряженных направлений безусловной минимизации функции f (x) в R n определяется следующим итеративным процессом генерации приближений xk R n :

где hk – шаговый множитель, g k 1 – градиент функции f (x) в точке xk 1; H k 1 – симметричная положительно определенная матрица.

После шага k матрица H k определяется в форме аддитивной поправки матрицы H k 1 : H k = H k 1 + H k, где H k – матрица ранга 1 или 2. Выбранная корректировка H k матрицы H k 1 определяет конкретный алгоритм (1).

Известны следующие «градиентные» интерпретации метода (1). Первая из них обычно приводится для квазиньютоновских методов и состоит в следующем. Шаг метода (1) соответствует шагу градиентного метода в пространстве с определяемой матрицей H k 1 метрикой, т.е. в пространстве со скалярным произведением (,) H : ( x, z ) H = ( H k 1x, z ). Поэтому квазиньтоновские методы часто называют методами переменной метрики.

Другая интерпретация метода (1) связана с операцией преобразованием пространства переменных линейным оператором. Представим матрицу H k в виде H k = Bk Bk, где Bk – невырожденная матрица n n.. Такое представление корректно поскольку матрица H k невырождена и положительно определена. Положим Ak = Bk 1. Пусть Y – «преобразованное» соответствующим матрице Ak линейным оператором пространство: Y = Ak X. Градиент g ( y ) функции f ( y ) = f ( Bk x), соответствующей функции f (x) в пространстве Y, равен Bk g (x). Поэтому шаг метода (1) соответствует (в исходном пространстве X ) шагу градиентного алгоритма в «преобразованном» пространстве Y.

Построение методов рассматриваемого класса обычно основано на основе анализа задачи минимизации квадратичной функции где C положительно определенная симметричная матрица (для методов сопряженных направлений можно рассматривать случай C 0, однако, для краткости, мы будем считать, что C > 0 ).

Квазиньтоновские методы и методы сопряженных направлений обеспечивают (и должны обеспечивать по определению) решение задачи (3) не более чем за n шагов. В дальнейшем, для краткости, будем считать, что решение обеспечивается за n шагов.

Для квазиньютоновских методов (по определению) должно выполняться условие: H n = C 1. Отсюда следует так называемое квазиньютоновское условие рекуррентного пересчета матрицы H k :

H n +1 = C 1 не обязательно (если это условие выполняется, то такой метод относится к классу квазиньютоновских). Так в численных схемах простейших алгоритмов сопряженных направлений матрица H k вообще отсутствует (например, алгоритмы Флетчера-Ривса [4], Полака-Рибьера [4], Поляка Б.Т.

[5]). Варианты таких алгоритмов и алгоритмов с несимметричными матрицами мы рассматривать не будем.

Основой построения методов сопряженных направлений является требование C ортогональности (сопряженности) направлений pk = H k g k :

Наиболее известная методика построения методов сопряженных направлений разработана Х. Хуангом (H. Y. Huang) [1]. Согласно приведенной в работе [3] описанию этой методики, условие C ортогональности (5) будет выполнено (с учетом (2)), если выполнены соотношения:

где – произвольная неотрицательная константа.

Также как и для квазиньютоновских методов, после шага k матрица H k определяется в форме аддитивной поправки.

После описания приведенных выше хорошо и давно известных фактов, нашей задачей является интерпретация квазиньютоновского условия (4) и условия C ортогональности (6) с позиции использования операторов преобT разования пространства: матрица H k представляется в виде H k = Bk Bk.

Квадратичной функции f (x) задачи (3) в преобразованном оператором Ak = Bk 1 пространстве Y = Ak X имеет вид f ( y ) = (Ck y, y ) + ( Bk b, x) + c, где Ck = Bk CBk – матрица квадратичной части функции в преобразованном проA p ( ~ – направление в преобстранстве. Положим: pk = H k 1 g k 1, pk pk разованном пространстве, соответствующее направлению «движения» pk алгоритма (1) в исходном пространстве).

Пусть матрица преобразования Bk удовлетворяет следующему условию (вектор ~k является собственным вектором матрицы квадратичной функции в преобразованном пространстве; собственное значение вектора равно k ) Утверждение 1. Квазиньютоновское условие (4) и условие (7), в котором k = 1, эквивалентны.

Естественная форма корректировки матрицы преобразования пространства Ak имеет вид Такая форма соответствует последовательному преобразованию пространства: Yk = Rk Yk 1 ( Y0 = X ).

Отметим, что представление известных вариантов квазиньютоновских методов (Давидона-Флетчера-Пауэлла, Бройдена-Флетчера-Шенно) в такой форме методов с преобразованием пространства приведено в работе [6].

Шаг (1) соответствует шагу обычного градиентного метода в пространстве Yk 1 :

yk 1 = Bk 1 xk 1.

yk = Bk 1 xk пространства Yk 1, {g k 1, g k } – двумерное подпространство пространства Yk 1 определяемое векторами g k 1, g k Выделим подкласс методов с преобразованием пространства следующим ограничением на выбор операторов R : R оператор изменяет только подпространство {g, g } ). Для k выделенного подкласса методов с преобразованием пространства справедливо следующее утверждение.

Утверждение 2. Условия C -ортогональности (6) и условие (7), в котором k =, эквивалентны.

Заключение В заключение сделаем несколько замечаний.

1. Отметим содержательный смысл рассматриваемого класса квазиньютоновских методов и методов сопряженных направлений, генерируемых на основе преобразования пространства. В преобразованном пространстве Yk выполняется шаг градиентного алгоритма (9). После этого производится преобразование пространства (изменяющее лишь подпространство {g k 1, g k } ) с выполнением условия (7). Содержательный смысл этого условия: образ (в пространстве Yk ) вектора смещения в пространстве Yk должен являться собственным вектором матрицы квадратичной функции в пространстве Yk. Оказывается, что такой принцип выбора операторов преобразования соответствует квазиньютоновскому условию (4) и известному условию C -ортогональности (6) методов сопряженных направлений. Для квадратичной функции образ траектория метода (1) в пространстве Yn соответствует движению по (взаимно ортогональным) собственным векторам матрицы Cn.

2. Приведенная интерпретация квазиньютоновского условия и условия C -ортогональности не только интересна своей наглядностью (удивительно, но автор не обнаружил публикацию такой интерпретации). Она позволяет строить новые модификации методов рассматриваемого класса. Так в работах [7, 8] разработано семейство алгоритмов на основе использования условия (7) и операторов растяжения пространства R ( ) [9]. Как частный случай в это семейство входит предельный вариант r-алгоритма [10] (одного из наиболее эффективных алгоритмов негладкой оптимизации) с бесконечным коэффициентом растяжения.

[1] H. Y. Huang Unified approach to quadratically convergent algorithms for function minimization // J. Optim. Theory and Appl., 1970. – Vol. 5. – Pp.

[2] Полак Э.Численные методы оптимизации. – М.: Мир, 1974. – 376с.

[3] Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. – М.: Наука, 1975. – 376 с.

[4] Fletcher R., Reeves C.M. Function minimization by conjugate gradients // Comput. J., 1964. –Vol. 7. – №2. – Pp. 149 – 154.

[5] Поляк Б.Т. Метод сопряженных градиентов в задачах на экстремум // ЖВМ и МФ, 1969. – Вып.9. – №4. – C. 807 – 821.

[6] Стецюк П.И. Линейные операторы в квазиньютоновских методах // Теория и приложения методов оптимизации. – К.: Ин-т кибернетики им.

В.М.Глушкова НАН Украины, 1998. – C. 3 – 8.

[7] Журбенко Н.Г. Построение семейства методов сопряженных направлений на основе использования оператора растяжения пространства // Теория и приложения методов оптимизации. – К.: Ин-т кибернетики им.

В.М.Глушкова НАН Украины, 1998. – C. 12 – 18.

[8] Журбенко Н.Г. Квазиньтоновские алгоритмы минимизации на основе использования оператора растяжения пространства // Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1999. – C. 45 – 50.

[9] Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. – Киев: Наук. думка, 1979. – 199 с.

[10] Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов // Кибернетика. – Киев: Наук. Думка, 1971. – №3. – С. УДК 519.6:519.

ОБОСНОВАНИЕ АЛГОРИТМОВ ВНУТРЕННИХ ТОЧЕК

ДЛЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Институт систем энергетики им. Л.А. Мелентьева СО РАН Институт систем энергетики им. Л.А. Мелентьева СО РАН Аннотация. Рассматривается семейство алгоритмов внутренних точек. Алгоритмы предназначены для решения задач математического программирования с нелинейными ограничениями-неравенствами. При поиске направления улучшения решения используются изменяющиеся по итерациям взвешенные евклидовы нормы. Представлены результаты теоретического обоснования алгоритмов при некоторых предположениях (в т.ч. о невырожденности задачи).

Ключевые слова. Метод внутренних точек, взвешенная евклидова норма, линеаризация.

Введение высокоэффективными процедурами решения задач математического программирования. Из множества алгоритмов внутренних точек в особый класс выделяются алгоритмы, в которых поиск направления улучшения решения основывается на идее стимулирования движения вдоль границ области допустимых по ограничениям-неравенствам решений. Это обуславливает оригинальность и эффективность этих методов, но в то же время затрудняет их теоретическое обоснование. Пионерные разработки таких алгоритмов были осуществлены в СССР в 60 – 70-х гг. прошлого века С.М. Анцызом, И.И. Дикиным [1, 2], Ю.Г. Евтушенко и В.Г. Жаданом [3, 4], В.И. Зоркальцевым [2, 5, 6]. Алгоритмы внутренних точек обсуждаемого типа успешно используются с 70-х гг. прошлого века при реализации ряда моделей энергетики в Институте систем энергетики им. Л.А. Мелентьева СО РАН. При этом для моделей с нелинейными ограничениями применяются процедуры итеративной линеаризации.

Постановка задачи Рассмотрим задачу нелинейного программирования где Заданы векторы x, x из R n (причем x j < x j, j = 1,..., n ) и выпуклые дважды дифференцируемые функции f i (x), i = 0,..., m.

Следовательно, задача (1), (2) удовлетворяет условию Слейтера. Согласно условиям оптимальности Куна-Таккера, для того, чтобы вектор x* X был существования векторов u * R m, * R n, * R n, при которых:

Допустимое решение x X назовем стационарным, если для него выполняются соотношения (3) – (6) при некоторых векторах u,,. Если такие векторы единственные, то решение x будем называть невырожденным.

Задачу (1), (2) назовем невырожденной, если у нее любое стационарное решение невырождено. Заметим, что оптимальное решение является всегда стационарным, но не любое стационарное решение является оптимальным.

Описание семейства алгоритмов внутренних точек В рассматриваемом вычислительном процессе последовательность векторов x k из int X вырабатывается по правилу Здесь k = 0, 1, 2,..., – номер итерации, x k вектор спуска, k шаг корректировки.

Основной проблемой в излагаемом вычислительном процессе является определение направления улучшения решения. Для ее разрешения сначала в точке x k вычисляется градиент целевой функции Если c k = 0, то дальнейшие вычисления прекращаются, т.к. x k точка минимума функции f 0 ( x). Далее будем считать, что c k 0.

После этого находится матрица Ak размера m n, строками которой являются градиенты функции диагональная матрица Bk размера n n с положительными элементами на главной диагонали.

В работе [8] в качестве Bk использовалась взвешенная сумма матриц вторых производных функции f i (x), i = 0,..., m, Здесь vik 1 приближения на итерации k 1 к множителям Лагранжа нелинейных ограничений задачи (1), (2). На начальной итерации vi0 = 1, внутренних точек показали его вычислительную эффективность.

является диагональной. В этой связи возможна модификация правила (8), в которой для всех i, i = 0,..., m, вместо матрицы 2 f i ( x k ) используется диагональная матрица того же размера с элементами размещенными на главной диагонали.

Затем определяем векторы весовых коэффициентов d k R n, h k R m.

Их компоненты должны удовлетворять неравенствам Здесь, – некоторые непрерывные неубывающие функции положительного аргумента, удовлетворяющие двум условиям:

при некоторых > 0, M > 0 для всех t (0, ].

алгоритмов, поскольку могут использоваться различные правила вычисления весовых коэффициентов. В частности, можно пользоваться правилом экспериментальных и теоретических исследований [6], вариантами правил нахождения весовых коэффициентов могут служить следующие при заданном > 0. Здесь uik 1, k 1, k 1 приближения на итерации k к множителям Лагранжа ограничений, f i ( x) 0, i = 1,..., m, x x, x x.

диагональные матрицы размера n n и m m с компонентами векторов d k и h k на главной диагонали.

Интервальный и аксиоматический подходы к определению весовых коэффициентов были введены в [5] применительно к алгоритмам внутренних точек для решения задач линейного программирования. Такой подход обобщает имеющиеся способы нахождения весовых коэффициентов и позволяет создавать новые. При этом не обязательно иметь конкретные выражения для функций,. Достаточно доказать существование таких функций и указанных их свойств.

Вспомогательная задача поиска направления улучшения решения Вектор x k определим как результат решения вспомогательной задачи минимизации квадратичной выпуклой функции от векторов x R n и z R m при линейных ограничениях-равенствах В целевой функции задачи (14), (15) составляющие x T Dk x, z T H k 1 z стимулируют при выборе x k к движению «вдоль» границ множества векторов, удовлетворяющих неравенствам x x x, f i ( x) 0, i = 1,..., m.

Составляющая x T Bk x является квадратом взвешенной евклидовой нормы.

Если матрица Bk вычисляется по правилу (8), то это слагаемое представляет вторые производные в аппроксимации функций f i (x), i = 0,..., m.

Обозначим u k вектор множителей Лагранжа этих ограничений.

Определим вектор приближений к множителям Лагранжа нелинейных ограничений исходной задачи Множество номеров i, при которых uik < 0, обозначим I k.

Два варианта вычисления направления корректировки Вспомогательная задача (14), (15) сводится к решению системы матрицей. Возможны два варианта вычислений векторов x k, z k, u k.

Один из них основывается на решении системы линейных уравнений с матрицей размера n n Найдя в результате решения системы (17) вектор x k, определяем векторы Система (17) следует из задачи безусловной минимизации к которой приходим в результате подстановки вектора z (из условия (15)) в целевую функцию (14).

Второй вариант вычислений основан на решении системы размера Вычислив u k, находим вектор и по формуле (15) – вектор z k. Система (19) – результат решения задачи (14), (15) методом неопределенных множителей Лагранжа. Второй из двух вариантов вычислений предпочтительней в том случае, когда m < n.

Векторы k R n, k R n, являющиеся приближениями на итерации k к множителям Лагранжа ограничений x x, x x, определим следующим образом Вектор q k вычисляется по правилу что, согласно (20), равносильно следующей формуле Нахождение шага корректировки Шаг корректировки вычисляется следующим образом:

интервала (0, 1) ;

Правила нахождения шага k гарантируют, что вектор x k +1 будет находиться в int X.

Критерий останова Вычисления заканчиваются при выполнении с заданной точностью Лагранжа и условий дополняющей нежесткости (4) – (6) Здесь векторы v k, k, k находятся по правилам (16), (21).

Свойства вырабатываемых приближений Bk + Dk 1 + Ak H k 1 Ak, для всех k, k = 0, 1, 2,..., имеет место неравенство Из выполнения неравенства (22) и правил определения шага k следует, что Поскольку целевая функция задачи (1), (2) ограничена снизу на множестве X, то, в силу (23), значения целевой функции сходятся к некоторой величине Евклидовы проекции начала координат на линейное многообразие установленный в [5] факт ограниченности множества евклидовых проекций начала координат на линейное многообразие. Сначала поясним этот факт.

Пусть L линейное многообразие в R n. Вектор s L назовем опорным вектором многообразия L, если не существует вектора y L такого, что ненулевых компонент вектора y. Обозначим Q(L) выпуклую оболочку опорных векторов линейного многообразия L. Поскольку число опорных векторов у линейного многообразия L конечно, то их выпуклая оболочка Q(L) будет ограниченным множеством.

– евклидову проекцию начала координат на линейное многообразие L при использовании евклидовой нормы с заданными весовыми коэффициентами p j > 0 , j = 1,..., n. В [5] доказано следующее утверждение Лемма 1. Любая евклидова проекция начала координат R n на линейное многообразие L R n находится в выпуклой оболочке опорных векторов этого многообразия, r ( p ) Q( L) при любых p j > 0, j = 1,..., n.

Этот факт служит основой для теоретического обоснования алгоритмов внутренних точек задач линейного программирования [5, 6]. Усложняющим обстоятельством для нелинейных задач является изменение линейных многообразий, рассматриваемых при доказательстве, в зависимости от итеративно меняющейся точки, в которой осуществляется линеаризация. При этом меняются также опорные векторы.

Выделим два линейных многообразия, соответствующих вектору x такому, что x x x. Линейное многообразие L1 ( x) состоит из векторов x R n, z R m, удовлетворяющих условиям Здесь A(x) матрица размера m n, строками которой являются градиенты функций f i (x), i = 1,..., m.

Линейное многообразие L2 ( x) состоит из векторов q R n, u R m, удовлетворяющих условию Теоретическое обоснование алгоритмов внутренних точек Для доказательства сходимости последовательности приближений, вырабатываемых вычислительным процессом (7), к оптимальному решению задачи (1), (2) введем некоторые предположения.

1. Будем считать, что целевая функция линейна: при заданном c R n, Отметим, что это предположение вводится для удобства доказательства и не является существенным.

2. С изменением вектора x могут меняться значения опорных векторов линейных многообразий L1 ( x), L2 ( x). Предположим, что объединения по x, многообразий L1 ( x) и объединения по x, удовлетворяющим x x x, множеств опорных векторов многообразий L2 ( x) будут ограниченными множествами.

3. Будем считать, что величина шага k на всех итерациях ограничена снизу некоторым положительным числом, т.е. существует > 0 такое, что В случае линейных ограничений это условие обязательно выполняется, поэтому нет необходимости вводить его особо. При наличии нелинейных ограничений выполнение этого условия – открытый вопрос. Поэтому оно, к сожалению авторов, вводится в условия теоремы.

Для доказательства сходимости векторов x k к оптимальному решению задачи (1), (2) потребуется следующее вспомогательное утверждение, доказываемое стандартным образом.

Лемма 2. Если положительный ряд k сходится, последовательность чисел k, k = 0, 1, 2,..., ограниченная, то ряд k k сходится.

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

Теорема 1. Пусть а) задача (1), (2) невырождена;

б) целевая функция линейна;

в) объединения по всем x, удовлетворяющим условию x x x, множеств опорных векторов линейных многообразий L1 ( x), L2 ( x) ограничены;

г) существует > 0 такое, что k, k = 1, 2,....

Тогда существуют векторы ~ X, u R m, R n, R n такие, что Вектор ~ является оптимальным решением, а векторы u,, множителями Лагранжа ограничений задачи (1), (2).

Доказательство. Будем нумеровать отдельные фрагменты рассуждений.

1. Вычислительный процесс (7) равносилен следующему где Положим Из вспомогательной задачи (14), (15) вытекает, что векторы ~ k, ~ k являются решением задачи:

при ограничениях Т.е. векторы ~ k, ~ k являются евклидовыми проекциями начала координат на линейное многообразие L1 ( x k ).

Векторы q k, u k определяются как результат решения следующей задачи нахождения евклидовой проекции начала координат на линейное многообразие L2 ( x k ) Из леммы 1 и условия ограниченности объединений по k = 0, 1, 2,..., множеств опорных векторов линейных многообразий L1 ( x), ограниченные последовательности: при некоторых M 1 > 0, M 2 > 0, для всех Из (24) следует, что положительный ряд k является сходящимся Из (29), (31), (33) и леммы 2, примененной к процессу (29), получаем, что при некотором ~ R n При этом ~ X, так как на всех итерациях x k X и множество X замкнуто.

Отметим, что в полученном обосновании сходимости векторов x k условия на выбор весовых коэффициентов не использовались в полной мере.

В силу (7) Поэтому Из (28) получаем, что Производная в точке оптимума минимизируемой в (14) функции должна быть равна нулю по любому направлению из R n, в том числе и по направлению x k, Из (15) и (35) следует, что Согласно (18), (20), (27), (36) при k последовательностей векторов u k, q k образуют ограниченные множества, которые обозначим Lim u k, Lim q k.

В силу (9) – (12) последовательности векторов d k, h k являются предельных при k значений, которые обозначим Lim d k, Lim h k.

Для любого u Lim u k существует, согласно (38), вектор h Lim h k такой, что d Lim d k такой, что Учитывая условия на выбор весовых коэффициентов (9) – (12), получаем, что для вектора ~ X при любых векторах u Lim u k, q Lim q k выполняются условия стационарности.

Поскольку задача (1), (2) невырожденная, то для стационарного решения ~ X векторы q и u, удовлетворяющие условиям (37) и (38) соответственно, единственны. Поэтому последовательность векторов u k последовательность векторов q k будет сходиться к единственному вектору q = lim q k.

3. Предположим, что у вектора u есть отрицательные компоненты.

Если ui < 0 для некоторого i, то начиная с некоторой итерации k 0, на всех последующих итерациях zik < 0. Из (15) следует, что В силу (39) и условий на выбор шага k, для всех k k 0 имеет место Получаем, что значение f i ( x k ) для данного i будет убывать по итерациям. Поэтому hi > 0. Неравенства hi > 0 и ui < 0 противоречат условию (38). Тем самым доказано, что u 0.

Если для некоторого i ui > 0, то, начиная с некоторой итерации k 0, для всех k k 0 значение f i ( x k ) для данного i будет возрастать. Следовательно, значение f i (x ) либо меньше нуля, либо равно нулю. В силу (38), hi = 0.

Отсюда, согласно (10), следует, что ( f i ( ~ )) = 0. Это означает, что дополняющей нежесткости (3) для векторов ~, u.

Неотрицательность компонент векторов, следует из правила (21).

Покажем, что для векторов ~,, выполняются условия дополняющей нежесткости (4), (5).

Множества номеров положительных, отрицательных и нулевых компонент q обозначим Q+, Q, Q0, соответственно.

начиная с некоторой итерации k, на всех последующих q k > 0. Согласно (20), (7) и неравенства k > 0 получаем, что величина x k для данного j будет убывать по итерациям. Поэтому Из (37) и положительности q k следует, что для данного номера j последовательность величин d k сходится к нулю при k. Это означает, в силу определения весовых коэффициентов d k и (41), что ( x k x j ) 0 при k. Отсюда следует, что условия (4), (5) выполняются для j Q+.

некоторой итерации k, на всех последующих q k < 0. Поскольку q k < 0, d k > 0, b k 0, то, согласно (40), x k > 0 для всех k k. Из (7) и неравенства k > 0 получаем, что величина x k для данного j будет возрастать по итерациям. Поэтому Из (37) и отрицательности q k следует, что для данного номера j последовательность величин d k сходится к нулю при k. Это означает, в силу определения весовых коэффициентов d k и (42), что ( x j x k ) 0 при k. Отсюда следует, что для j Q выполняются условия (4), (5).

означает, что для j Q0 имеют место (4), (5).

Итак, доказано, что для векторов ~, u,, выполняются условия дополняющей нежесткости (3) – (5). Теорема доказана.

Заключение Представлено описание нового семейства алгоритмов внутренних точек для решения задач оптимизации с нелинейными ограничениями.

Основной вычислительной проблемой в алгоритмах является нахождение на каждой итерации направления корректировки решения. Эта задача представляется в виде задачи безусловной минимизации квадратичной выпуклой функции от n или m переменных. Такая альтернатива может быть полезна в вычислительном отношении.

последовательности приближений, вырабатываемых алгоритмами внутренних точек из описанного класса, к стационарному и оптимальному решению задачи (1), (2). Весовые коэффициенты в этих алгоритмах удовлетворяют условиям (9) – (12). Отметим, что для доказательства сходимости последовательности приближений, вырабатываемых вычислительным процессом (7), имеющиеся стандартные техники доказательства, описанные, например, у У.И. Зангвилла [7], не годятся. Это связано с тем, что при поиске направления улучшения решения используются изменяющиеся по итерациям нормы. Доказательство теоремы 1 является некоторым переложением техники доказательства сходимости, предложенной в [5] для теоретического обоснования алгоритмов внутренних точек в линейном программировании.

[1] Дикин И.И. Итеративное решение задач линейного и квадратичного программирования // Доклады АН СССР, 1967, том 174. – С.747–748.

[2] Дикин И.И., Зоркальцев В.И. Итеративное решение задач математического программирования (алгоритмы метода внутренних точек). – Новосибирск: Наука, 1980. – 144с.

[3] Евтушенко Ю.Г., Жадан В.Г. Численные методы решения некоторых задач исследования операций. // Журнал вычислительной математики и математической физики.– 1973. – Т. 13. – № 3. – С. 583–597.

[4] Евтушенко Ю.Г., Жадан В.Г. Барьерно-проективные методы решения задач нелинейного программирования // Журнал вычислительной математики и математической физики.– 1994. –Т. 34. –№ 5. – С. 669–684.

[5] Зоркальцев В.И. Относительно внутренняя точка оптимальных решений.

Сыктывкар: Коми фил. АН СССР, 1984. – 48с.

[6] Зоркальцев В.И. Метод относительно внутренних точек. – Сыктывкар:

Коми филиал АН СССР, 1986. – 18с.

[7] Зангвилл У.И. Нелинейное программирование. – М.: Советское радио, 1973. – 312с.

[8] Пержабинский С.М. Алгоритм внутренних точек, использующий квадратичные аппроксимации. // Современные технологии. Системный анализ. Моделирование. – Иркутск: ИрГУПС. – 2008. – №3(19). – С.97– УДК 519.

СВЕДЕНИЕ ЗАДАЧ ДВУХЭТАПНОЙ ВЕРОЯТНОСТНОЙ ОПТИМИЗАЦИИ

С ДИСКРЕТНЫМ РАСПРЕДЕЛЕНИЕМ СЛУЧАЙНЫХ ДАННЫХ

К ЗАДАЧАМ ЧАСТИЧНО ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

Институт кибернетики В.М. Глушкова НАН Украины Аннотация. В работе рассматриваются модели двухэтапного стохастического программирования с квантильным критерием, а также модели с вероятностным ограничением на случайные значения целевой функции второго этапа. Такие модели позволяют формализовать требования к надежности и безопасности оптимизируемой системы, а также оптимизировать функционирование системы в экстремальных условиях. Предлагается способ эквивалентного преобразования таких моделей при дискретном распределении случайных параметров к задачам частично целочисленного программирования большой размерности. Число дополнительных целочисленных (булевых) переменных в этой задаче равно числу возможных значений вектора случайных параметров. Полученные смешанные задачи предполагается решать мощными стандартными компьютерными программами дискретной оптимизации. В качестве иллюстрации подхода приводятся результаты численных экспериментов на задаче небольшой размерности.

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

                                                              Работа выполнена при частичной поддержке Государственного фонда фундаментальных исследований Украины в рамках совместного российско-украинского проекта Ф40.1/016 (2011-2012) и Российского фонда фундаментальных исследований (проекты 11-07-90407-Укр-ф-а, 11-07-00315-а).