Методы проектирования точки в нормированных пространствах и их приложения тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат наук Арутюнова, Наталья Константиновна

• Арутюнова, Наталья Константиновна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Арутюнова, Наталья Константиновна

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. МЕТОД ПРОЕКЦИИ ТОЧКИ НА ПОВЕРХНОСТЬ УРОВНЯ ФУНКЦИИ, УДОВЛЕТВОРЯЮЩЕЙ УСЛОВИЯМ ПОДЧИНЕНИЯ,

ОБОБЩАЮЩИМ УСЛОВИЕ ЛИПШИЦА

1.1 .Постановка задачи

1.2.0писание алгоритма 1

1.3.Доказательство сходимости алгоритма 1

1.4.Одна задача проектирования для случая конечномерного евклидова

пространства

1.5.Программная реализация и численный пример

1 .б.Выводы по Главе 1

ГЛАВА 2. МЕТОДЫ ПРОЕКТИРОВАНИЯ НА ПОВЕРХНОСТЬ УРОВНЯ е-ЛИПШИЦЕВОЙ ФУНКЦИИ

2.1.Приближённый алгоритм

2.1.1. Описание алгоритма 2.1

2.1.2. Доказательство сходимости алгоритма 2.1

2.2.Точные алгоритмы

2.2.1. Некоторые вспомогательные утверждения

2.2.2. Описание алгоритма 2.2

2.2.3. Доказательство сходимости алгоритма 2.2

2.2.4. Описание алгоритма 2.3

2.2.5. Доказательство сходимости алгоритма 2.3

2.3.Программная реализация и численный пример

2.4.Выводы по Главе 2

ГЛАВА 3. РЕШЕНИЕ НЕКОТОРЫХ ВСПОМОГАТЕЛЬНЫХ ЗАДАЧ

МИНИМИЗАЦИИ ЛИПШИЦЕВЫХ И 8-ЛИПШИЦЕВЫХ ФУНКЦИЙ, ВОЗНИКАЮЩИХ ПРИ РЕАЛИЗАЦИИ АЛГОРИТМОВ ПРОЕКТИРОВАНИЯ ТОЧКИ

3.1.Модификация метода Евтушенко для непрерывных на отрезке функций

3.1.1. Постановка задачи

3.1.2. Описание алгоритма 3

3.1.3. Обоснование алгоритма 3

3.1.4. Численный пример

3.2.Некоторые способы понижения размерности многомерных задач минимизации липшицевых и е-липшицевых функций

3.2.1. Понижение размерности в задачах минимизации на сфере в пространстве с покоординатной метрикой

3.2.2. Понижение размерности в задачах минимизации на сфере в пространстве с евклидовой метрикой

3.3.Выводы по Главе 3

ГЛАВА 4. НЕКОТОРЫЕ МОДЕЛИ И ПРИЛОЖЕНИЯ МЕТОДОВ

ПРОЕКТИРОВАНИЯ

4.1 .Поиск первого слева нуля непрерывной на отрезке функции

4.1.1. Описание алгоритма 4.1

4.1.2. Численный пример

4.2.Метод штрафных функций с выбором штрафа в виде функции расстояния 62 4.3.Одно обобщение классической модели задачи потребительского выбора

маршаллианского типа

4.3.1. Описание моделей задач потребительского выбора

4.3.2. Анализ и численные методы решения обобщённой задачи потребительского выбора

4.3.2.1.Анализ функции ограничения

4.3.2.2.Алгоритм модифицированного метода штрафных функций

4.3.2.3.Расчёт тестовых примеров

4.4.Выводы по Главе 4

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СПИСОК ЛИТЕРАТУРЫ

СПИСОК ИЛЛЮСТРАТИВНОГО МАТЕРИАЛА

ПРИЛОЖЕНИЕ

Введение диссертации (часть автореферата) на тему «Методы проектирования точки в нормированных пространствах и их приложения»

ВВЕДЕНИЕ

Задачи проектирования точки на множество имеют достаточно давнюю историю, и их решению посвящено большое количество работ.

В общем виде задача проектирования формулируется следующим образом: на заданном множестве С найти точку, ближайшую к заданной точке а <£ С.

Таким образом, задача проектирования является экстремальной задачей следующего вида:

р(х,я)—>• min,

при ограничениях:

хеС,

где р(х, а) - расстояние между точками а их, понимаемое в том или ином смысле.

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

Очевидно, что решение задачи существует и в случае, когда С - компактное множество из конечномерного евклидова пространства, что вытекает из теоремы Вейерштрасса. Однако при этом единственность решения не гарантирована.

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

По-видимому, одним из первых можно назвать алгоритм проектирования нуля пространства на выпуклый многогранник [2]. Впоследствии предлагались и другие алгоритмы проектирования точки на многогранники, на выпуклые множества, порождённые пересечением выпуклых множеств и т.д., например, [3-9].

В [10] рассматривается задача проектирования в некотором смысле точки на пересечение выпуклых замкнутых множеств линейного топологического пространства.

Можно также отметить работу [11], где предлагается конечношаговая процедура отыскания проекции точки на выпуклый многогранник.

В работе [12] рассматривается некоторое обобщение задачи проектирования точки на выпуклое замкнутое множество конечномерного евклидова пространства и построена конечношаговая процедура его решения.

Вместе с тем, совершенно очевидно, что множество С не всегда удается выразить через выпуклые множества, и даже в тех случаях, когда это возможно, поиск проекций на эти выпуклые множества может вызывать серьезные затруднения. Разумеется, задачу проектирования точки на множество С можно попытаться свести к последовательности задач, в каждой из которых множество С аппроксимировано более простым множеством С к [13]. Однако и здесь нет гарантии, что структура Ск при больших к будет намного проще, чем С.

Как было отмечено выше, задача проектирования является задачей минимизации расстояния, которая в нормированных пространствах сводится к задаче минимизации нормы на заданном множестве, что в более общем случае есть задача минимизации выпуклой функции на множестве С. Мы не будем приводить перечень работ, посвященных этой проблеме и её обобщениям, в силу их многочисленности. Отметим здесь работы [14-16], в которых интерес представляют задачи с целевой функцией, являющейся разностью двух выпуклых (ё.с.-функцией), и ограничениями типа равенства и/или неравенства, также задаваемые с помощью ё.с.-функций.

Задачи проектирования на выпуклое множество находят многочисленные приложения при решении экстремальных задач, например, при использовании хорошо известного метода проекции градиента [17]. Существенное использование проектирования точки можно найти в работах [18-20 и др.], в которых предлагаются численные методы решения задачи математического программирования с ограничениями, являющимися предвыпуклыми множествами [21].

Из невыпуклых множеств, на которые удается спроектировать заданную точку, можно особо выделить множества, определяемые с помощью

функциональных ограничений, и, прежде всего, множества вида С= {х е А\/(х) = 0}, где А<^Е - некоторый выпуклый компакт. Соответствующие методы, как правило, различаются по принадлежности функции / тому или иному классу. Если / является достаточно гладкой, то применимы методы ньютоновского типа [22].

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

В последнее время наблюдается интерес к различным обобщениям условий Липшица-Гёльдера. Так, в работе [25] введено понятие £}-липшицевости, в [26] -обобщённой липшицевости.

Для нас интерес в дальнейшем представит класс, так называемых, в-липшицевых функций, введённых в работах Robert J. Vanderbei [27-29], для которых будут построены алгоритмы проектирования точки на множество их нулей и метод их глобальной оптимизации на отрезке.

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

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

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

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

Данная работа состоит из следующих глав.

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

Глава 2 посвящена методам проектирования на множества уровня 8-липшицевых функций. Предложены и обоснованы три алгоритма -приближённый (алгоритм 2.1) и два точных (алгоритмы 2.2 и 2.3). Алгоритм 2.1 позволяет найти приближённую проекцию точки на множество ^={1е^:0</(х)<£}. Алгоритмы 2.2 и 2.3 сходятся к проекции начальной точки а,/(а)> 0, на множество X* = {х е А:/(х) = 0}, причём, в отличие от приближённого алгоритма, они требуют пересчёта постоянной с-липшицевости функции /. Для обеспечения точности они содержат некоторые дополнительные параметры. Особенность алгоритма 2.2 состоит в том, что на каждом его итерационном шаге производится пересчёт постоянной в-липшицевости функции /, вследствие чего при приближении к решению алгоритм замедляется. В алгоритме 2.3 также производится пересчёт указанной оценки, однако, в отличие от алгоритма 2.2, - лишь в случае выполнения некоторого условия близости к искомому решению.

В Главе 3 приводятся методы и техники, разработанные для решения некоторых вспомогательных задач, возникающих при реализации предлагаемых в Главах 1 и 2 алгоритмов проектирования. Первым описывается и обосновывается модификация метода Евтушенко поиска глобального минимума непрерывной (е-липшицевой) на отрезке функции. Далее показывается возможность использования предлагаемой модификации метода Евтушенко для решения задач глобальной минимизации в-липшицевой функции на сфере, возникающих при реализации рассматриваемых алгоритмов проектирования точки на множество, путём применения различных схем понижения размерности решаемой задачи минимизации.

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

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

Результаты диссертации опубликованы в следующих научных статьях: 1) Заботин, В.И. Два алгоритма отыскания проекции точки на невыпуклое множество в нормированном пространстве / В.И. Заботин, Н.К. Арутюнова // Журнал вычислительной математики и математической физики. - 2013. - Т. 53, №3. - С. 344-349. (ВАК);

2) Арутюнова, H.K. Модификация метода Евтушенко поиска глобального минимума для случая непрерывной на компакте функции / Н.К. Арутюнова // Вестник КГТУ им. А.Н. Туполева. - 2013. - №2, вып. 2.- С. 154-157. (ВАК);

3) Арутюнова, Н.К. Экономико-математическая модель задачи потребительского выбора с ценами благ, зависящими от объёма покупок / Н.К. Арутюнова, В.И. Заботин, Н.П. Заботина // Вестник экономики, права и социологии. - 2014. -№ 2. - С. 7-10. (ВАК);

4) Арутюнова, Н.К. Алгоритмы проектирования точки на поверхность уровня непрерывной на компакте функции / Н.К. Арутюнова, A.M. Дуллиев, В.И. Заботин // Журнал вычислительной математики и математической физики. — 2014.-Т. 54, №9.-С. 1448-1454. (ВАК);

5) англоязычная версия статьи 4:

Arutyunova, N.K. Algorithms for Projecting a Point onto a Level Surface of a Continuous Function on a Compact Set / N.K. Arutyunova, A.M. Dulliev, V.l. Zabotin // Computational Mathematics and Mathematical Physics. - 2014. - Vol. 54, №9. -P. 1395-1401. (SCOPUS);

а также следующих докладах:

1) Арутюнова, Н.К. Обобщенный метод проекции точки на невыпуклое многообразие / Н.К. Арутюнова, А.Ф. Загидуллин // XVIII Туполевские чтения: сборник трудов Международной молодежной научной конференции. - Казань, 2010. - С. 131-132;

2) Заботин, В.И. Итерационные алгоритмы проектирования точки на невыпуклое множество / В.И. Заботин, Н.П. Заботина, Н.К. Арутюнова // Математические методы и информационные технологии в экономике, социологии и образовании: сборник статей XXV Международной научно-технической конференции. - Пенза: Приволжский Дом знаний, 2010. - С. 121-124;

3) Арутюнова, Н.К. Модифицированный метод штрафных функций для решения задачи потребительского выбора с дисконтированием цен / Н.К. Арутюнова, В.И. Заботин, К.С. Исхакова // Математические методы и информационные технологии в экономике, социологии и образовании: сборник

статей XXXI Международной научно-технической конференции. - Пенза: Приволжский Дом знаний, 2013. - С. 34-37;

4) Арутюнова, Н.К. Метод Евтушенко поиска глобального минимума

8-липшицевой функции и его приложения / Н.К. Арутюнова // Математические методы и информационные технологии в экономике, социологии и образовании: сборник статей XXXIII Международной научно-технической конференции. -Пенза: Приволжский Дом знаний, 2014. - С. 22-25.

ГЛАВА 1. МЕТОД ПРОЕКЦИИ ТОЧКИ НА ПОВЕРХНОСТЬ УРОВНЯ ФУНКЦИИ, УДОВЛЕТВОРЯЮЩЕЙ УСЛОВИЯМ ПОДЧИНЕНИЯ, ОБОБЩАЮЩИМ УСЛОВИЕ ЛИПШИЦА

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

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

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

Как было показано в работе [23], таким ослаблением условий на функцию ограничения является, например, условие Липшица-Гёльдера. Напомним это условие.

Функция определённая на выпуклом компактном множестве А нормированного пространства, удовлетворяет условию Липшица-Гёлъдера, если существуют такие Ь, а > 0, что для всех х,у е А имеет место

В случае, когда а = 1 условие (1.1), называется условием Липшица.

В упомянутой работе [23] предложен численный алгоритм проектирования точки линейного нормированного пространства на поверхность уровня функции, удовлетворяющей условию (1.1).

Однако, как показывает приведённый в конце главы пример, представляет интерес случай, когда функция ограничения удовлетворяет некоторым более общим условиям, нежели условие Липшица-Гёльдера.

Поэтому в данной главе мы рассмотрим метод проектирования точки на множество (поверхность уровня функции/)

где функция / подчиняется некоторому условию, обобщающему (1.1), а проекция точки на множество X* будет пониматься в смысле, описанном ниже.

Всюду ниже в данной работе через А обозначается выпуклое компактное множество нормированного пространства Е.

В связи с различием в определении компактности уточним то, как она понимается:

Множество А нормированного пространства будем называть компактным (по [30; 31] - компактным в себе), если из любой последовательности в А можно выделить сходящуюся подпоследовательность, предел которой принадлежит Л.

Пусть на Е определена выпуклая непрерывная функция д(х) такая, что д(х) = 0 тогда и только тогда, когда х = 0. Ясно, что в этом случае имеет место:

(1.1)

X* ={х&А:/(х) = 0},

1.1. Постановка задачи

\/х,у е Е V/ е [0;1]: + (1 - ¿)у) < ^(х) + (1 - ^(у).

Если зафиксировать^ = 0 и принять во внимание, что д(у) = 0, получим:

д^х)<1д(х), УхеЕ, У/е[0;1]. (1.2)

Предположим также, что на Е (или хотя бы на выпуклом компакте А<^Е) определена функцияудовлетворяющая следующему условию:

Ух,уе А: | /(*) - /(у) | <д(х-у). (1.3)

Рисунок 1.1 иллюстрирует данное условие.

Будем предполагать, что введённое выше множество X* нулей функции f не пусто.

Заметим, что (1.3) вместе с непрерывностью д(х) означает непрерывность на А и функции/(х).

Пусть также задана точка а <е А, такая, что/(а) > 0. Введём обозначение

\ni qix - а). (1.4)

хвХ"

Если г е X* таков, что

то точку г назовем ближайшей в смысле (1.4) к точке а среди точек из X*, или проекцией в смысле (1.4) точки а на множество X*.

В данной главе проекцию точки а будем понимать в указанном смысле, поэтому ради краткости будем употреблять термин «проекция». Поставим задачу:

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

1.2. Описание алгоритма 1

Шаг 0. Задаются к := 0, хо := а. Шаг 1. Строится множество

к

/=о

Шаг 2. Находится следующая итерационная точка:

хк+х =argmin{f(x):x&dKk f| À). ШагЗ. Если/Ххш) = 0,

то Хк+1 принимается в качестве искомой проекции, иначе полагается к := к+1 и осуществляется переход к шагу 1. Отметим, что вследствие непрерывности функции / построение точки Хк возможно для любого к.

1.3. Доказательство сходимости алгоритма 1

Предложение 1.1. [32; 33] Любая из предельных (в смысле нормы пространства Е) точек последовательности х^ построенной с помощью алгоритма 1, принадлежит множеству X*.

Доказательство. Заметим, что в силу предположения fia) > 0 множество int Ко Ф 0, и покажем сначала, что на int Ко П А имеет место неравенство/(х) > 0. Действительно, из шагов 0 и 1 алгоритма видно, что

К0 = {х е Е : q{x-a)< f{a)}. Принимая^ = а и учитывая левую часть неравенства (1.3), получаем:

-(f(x)-f{a))<q{x-a).

Легко видеть, что тогда

f(x)>f(a)-q{x-a)>0 для всех х g int Ко. Это следует из вида Ко и из того, что равенство q(x - a) -f {а) имеет место в силу выпуклости q лишь для х е ôKq.

Допустим теперь, что х\ тогда если перейти к построению К\,

окажется, что К\ = Ко, а это значит, что Х2 и все последующие точки последовательности Xk совпадают с х\.

Покажем, что если х\ е X*, то для любого х* е X* имеет место неравенство

q(x* -а)> q(x] - а),

которое в силу выпуклости функции q означает, что х\ является проекцией точки а на множество X*.

Действительно, х* £ int Ко, иначе, как было показано, f (х*) > 0, что противоречит тому, что х* е X*. А тогда с учётом/(xi) = 0 получаем

q(x* -a)>f(a)=f(a)+f(xx)>q(x] -а). Последнее неравенство следует из построения К\.

Аналогичные рассуждения можно провести и в случае, если существует такой к, что xi,x2, 1 € X*, Xk £ X*. Для этого всюду вместо xi необходимо рассматривать Хк, а вместо К\ - множество Кь. Поэтому далее будем полагать, что процесс построения точек х^ бесконечен.

Покажем теперь, что для любого к = 0, 1, 2, ... из условия у е int Кк П А следует, что f(y)> 0. Доказательство проведем по индукции.

Для к -0 справедливость утверждения показана выше. Предположим его справедливость для к— 1.

Рассмотрим множества

А{ =int^A_, f]A; А2=дКк_1ПА;

А,

к-1 к

;=0

1=0

ПА.

Из шага 1 алгоритма и выпуклости функции q следует, что

int Кк_х =

дКк_х =

xe£:g(x-ß)<^/(x,)

i=0 к-1

xeE:q(x-a)=^f(x,)

i=0

а это значит, что

Г к-1 к

int Кк= int и и X е Е: £ /(*, )<Ч(х-а)<^ /(*,)

[ 1=0 1=0

и, следовательно, е int П А тогда и только тогда, когда у е А} U А2 U А3.

1)Если^ е А\, утверждение доказано.

2) Если у е Аг, то из построения точки Хк и того, что Хк € -X* следует

/О) >/(**) > о.

3)Если у е Лз, то возьмём любую точку X/ = iy + (1 -1) а, t е [0; 1], отрезка [а; у] и рассмотрим уравнение

к-\

q(xt-a)=Yuf{xl).

(=0

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

х: - a = ty + { 1 - {)а - а = + а — Га — а = /(у - а)

и получим:

¿-1

*)) = £/(*,)• (1-5)

;=0

а-1

Заметим, что ^ /(х,) > 0, а <7(0) = 0.

;=0

Тогда

к-1 /=0

и, следовательно, в силу непрерывности функции д найдется ? е (0; 1), являющееся решением уравнения (1.5).

Пусть ? - решение уравнения (1.5). Тогда вследствие (1.2) имеем:

к-1

X )="*)) - ^ ~

1=0

Учитывая это неравенство, построение точки Хк, свойство (1.2) функции д и условие (1.3) для точек х, и у, получим следующую оценку:

к-1

= /(*,)+^(у - а)-- а) > /(хк)+ ]Г /(х;)-<?(у - а) > 0.

/=0

Индукция завершена. Покажем теперь, что

00 ( )

£/(х, )<Ы^{х-а\хеХ*\. (1.6)

;=0

Доказательство проведём от противного.

Пусть существуют такие у е X* и к е Ы, что

к

(=0

но тогда, как следует из предыдущей оценки,/(у) > 0, что противоречит тому, что уеГ.

Из неравенства (1.6) следует, что

Нт/(х,) = 0. (1.7)

к

Если х* - предельная точка последовательности х^, то, учитывая компактность множества^, замечаем, чтох* е А.

Выделяя теперь из х* подпоследовательность хк , сходящуюся к х*, и

учитывая непрерывность/ получаем

К

то есть х

Предложение доказано. ■

Предложение 1.2. [32; 33] Если х* е X* - предельная точка последовательности Хк, построенной по алгоритму 1, то она является проекцией в смысле (1.4) точки а на X*.

Доказательство. Из (1.6) и (1.4) имеем:

сс

£/(*,) <у(я; .Г ).

7=0

Выберем произвольную подпоследовательность хк последовательности Хк, построенной по алгоритму 1, и пусть хк сходится кх* е X*.

Из шага 2 алгоритма следует, что хк е д Кк , а тогда по построению Кк имеем:

Переходя в этом равенстве к пределу по кп ->оо, и учитывая (1.6) и (1.4), получим

Замечание. Предложения 1.1 и 1.2 доказаны в предположении о существовании предельной точки х* итерационной последовательности х^ То, как мы условились понимать компактность множества А, гарантирует существование предельных точек у построенной последовательности х^ принадлежащих А.

Если ослабить требование на компакнтность А, при которых не будет гарантировано существование х* е А, то в силу (1.7) сходимость итерационной последовательности будет существовать «по функционалу».

В случае конечномерности нормированного пространства Е компактность А эквивалентна его ограниченности и замкнутости, и в этом случае у любой последовательности Хк со значениями в А будет существовать сильно сходящаяся к точке из А подпоследовательность.

Предложение 1.3. [32; 33] Если х* е X* - единственная ближайшая в смысле (1.4) к а точка из X* то хк —•

Доказательство. Действительно, в противном случае из Хк можно выделить подпоследовательность хк ->х'еА, хг Ф х*. В силу предложения 1.2 х'

1=0

1=0

что и требовалось доказать.

является проекцией точки а на X*, что противоречит предположению о единственности х*. я

Если X* = 0, то в силу связности множества А и непрерывности на нём функции/

УхеЛ:/(х)>0. (1.8)

Кроме того, в силу компактности А по теореме Вейерштрасса нижняя грань

5 = М/(х)>0 (1.9)

хеЛ

достижима.

Введём в рассмотрение величину

<3 = шах д(х - а),

хеЛ

которую назовём диаметром множества А. Вследствие компактности А и непрерывности функции д, очевидно, с1< оо. Введём также множество

й = {х е Е: д(х — а) < ¿/}. Предложение 1.4. Если множество X* нулей функции / на компакте А пусто, то алгоритм 1 обнаружит это за конечное число шагов.

Доказательство. Покажем вначале, что если X* = 0, то на некоторой к-й итерации алгоритма 1 окажется, что £> а Кк.

По построению множеств Кк (шаг 1 алгоритма 1) и определениям величины

и множества И это эквивалентно условию:

к

з^^ХДхД

7=0

Действительно:

1=0 У

о (хе£>=>хе ЛГА) о д(х-а)<<1 д(х - <з)< ^/(х.)

к /=0

Предположим теперь противное:

Л

Г к \

V /=о

V* :</>£/(*,).

/=0

Отсюда очевидно, что

чего в силу построения Хк (шаг 2 алгоритма 1) и соотношения (1.9) быть не может. Таким образом, £> с Кк.

Заметим также, что из построения величины с1 следует, что для любого х е А имеет место

д(х -а)<с/.

Тогда с учётом построения множества Э получаем включение

Ас О с: Кк.

Если хотя бы одно из данных включений окажется строгим, то, очевидно, получим, что дКк П А = 0, и, следовательно, на шаге 2 к-й итерации алгоритма 1 построение следующей точки Хк+\ будет невозможно.

Если же окажется, что А = Кк, то по шагу 2 алгоритма 1 будет найдена на дКк П А Ф 0 следующая итерационная точка Хк+\. Однако, вследствие (1.9) выполнится /{хк+ 0>0, и, следовательно, А= КкС Кк+\, причём Кк является собственным

подмножеством Кк+\. В этом случае, аналогично случаю, описанному выше, будет невозможно отыскание точки Хк+2.

Предложение доказано. ■

Замечание.

Как нетрудно заметить, алгоритм, предложенный в статье [23], является частным случаем предложенного здесь алгоритма при условии, что функция является липшицевой.

На наш взгляд, представляет интерес разработка алгоритма для случая, когда функция ц{х) из условия (1.3) является строго квазивыпуклой [34], что полностью обобщило бы алгоритм [23].

1.4. Одна задача проектирования для случая конечномерного евклидова

пространства

Пусть Е - я-мерное евклидово пространство и на нём или выпуклом компакте АсЕ определена функция /{х\,хг, ...,хп), удовлетворяющая условию Липшица-Гельдера покоординатно, то есть для каждого / = 1, 2, ..., п существуют такие Ь, > 0 и а/> 0, что для любых х\ и х", /=1,2, ...,п, на множестве А выполняется условие

|/(х,,...,х;_,,х1,х/+1,...,хп) — У(х]хг_,,х(,х;+1,...,хп)(<Ь1 |х; — Х^ . (1-Ю)

Предложение 1.5. [30; 33] Условие (1.10) эквивалентно тому, что найдутся Ь,> 0 и а, > 0, /=1,2, ...,/7, при которых для всех х,уеА имеет место неравенство

I(1.11)

г=1

Доказательство. Произведём с использованием неравенства треугольника и (1.10) следующую оценку: \/(х],х2,...,хп)-/(у],у2,...,уп}<

<\/(х1,х2,...,хп)-/(у1,х2,...,х„) + \/(у],х2,...,хп)-/(у],у2,х3,...,х„) +

п

^ т I |0С, т I |си т I |«„ V-1 г I 1«.

+ Ь2\х2~ у 2\ - +... + Ьп\хп - уп\ =2^Ц\х1-у,\ .

Проводя аналогичное оценивание и для других координат, и суммируя получаемые неравенства, получим (1.11).

Предложение доказано. ■

Сравнивая правые части условий (1.3) и (1.10), можно заметить, что при а, > 1, / = 1, 2, ..., п, функция

п

я(х)=^1>\х'\а'

;=1

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

Следует, однако, заметить, что случай, когда а;> 1, /=1,2, ...,п, не представляет интереса, поскольку в этом случае функция будет постоянной. Для функции одного переменного это показано в [35, с. 87]. Этот факт легко переносится и на случай, если функция определена на нормированном пространстве. Для этого достаточно показать, что её производная по любому направлению Н равна нулю:

/(х + й)-/(х)

В силу сказанного, интерес для нас представит функция q{x) вида:

п

q(x)=YLi\4- (1-12)

/=1

Этот вид функции, по-видимому, представляет наибольший интерес и для практического применения алгоритма 1.

1.5. Программная реализация и численный пример

По представленному принципиальному алгоритму 1 для случая, когда функция ограничения /(х) удовлетворяет условию (1.3) с функцией q{x) вида (1.12), составлены рабочие алгоритмы и их программная реализация.

Одна из разработанных программ была включена как компонент в программный комплекс «Проектирование точки», описание которого приведено в Приложении.

Рассмотрен случай, когда E = R3 и на нём определена покоординатная норма, то есть для х е Е

Список литературы диссертационного исследования кандидат наук Арутюнова, Наталья Константиновна, 2015 год

СПИСОК ЛИТЕРАТУРЫ

1. Колмогоров, А.Н. Элементы теории функций и функционального анализа / А.Н. Колмогоров, С.В. Фомин. - М.: Наука: Гл. ред. физ.-мат. лит., 1976. -543 с.

2. Демьянов, В.Ф. Введение в минимакс / В.Ф. Демьянов, В.Н. Малоземов. - М.: Наука: Гл. ред. физ.-мат. лит., 1972. - 368 с.

3. Гурин, Л.Г. Методы проекций для отыскания общей точки выпуклых множеств / Л.Г. Гурин, Б.Т. Поляк, Э.В. Райк // Журнал вычислительной математики и математической физики. - 1967. - Т. 7, № 6. - С. 1211-1228.

4. Wolfe, Ph. Finding the nearest point in a polytope / Ph. Wolfe // Mathematical Programming. - 1976. - Vol. 11, № 1. - P. 128-149.

5. Dax, A. The smallest point of a polytope / A. Dax // Journal of Optimization Theory and Applications. - 1990. - Vol. 64, № 2. - P. 429^432.

6. Bauschke, H.H. On projection algorithms for solving convex feasibility problems / H.H. Bauschke, J.M. Borwein // S1AM Review. - 1996. - Vol. 38, №3. -P. 367-426.

7. Нурминский, E.A. О сходимости метода подходящих аффинных подпространств для решения задачи проекции на симплекс / Е.А. Нурминский // Журнал вычислительной математики и математической физики. - 2005. -Т. 45, № 11.-С. 1991-1999.

8. Нурминский, Е.А. Проекция на внешне заданные полиэдры / Е.А. Нурминский // Журнал вычислительной математики и математической физики. - 2008. -Т. 48, №3.-С. 387-396.

9. Pang, C.H.J. Set intersection problems: Supporting hyperplanes and quadratic programming / C.H.J. Pang // Mathematical Programming. - 2015. Vol. 149. -Issue 1-2.-P. 329-359.

10. Брэгман, Л.М. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для решения задач выпуклого программирования /

JI.M. Брэгман // Журнал вычислительной математики и математической физики. - 1967.-Т. 7, № 3. - С. 620-631.

11. Габидуллина, З.Р. Теорема отделимости выпуклого многогранника от нуля пространства и её приложения в оптимизации / З.Р. Габидуллина // Известия высших учебных заведений. Математика. - 2006. - № 12. - С. 21-26.

12. Куликов, А.Н. Выпуклая оптимизация с заданной точностью / А.Н. Куликов,

B.Р. Фазылов // Журнал вычислительной математики и математической физики. - 1990. -Т. 30, № 5. - С. 663-671.

13. Tuy, H. Monotonie Optimization: Branch and Cut Methods / H. Tuy, F. Al-Khayyal, P.T. Thach // in Essays and Surveys in Global Optimization, eds

C. Audet, P. Hansen, G. Savard. - Springer. - 2005. - P. 39-78.

14. Стрекаловский, A.C. Элементы невыпуклой оптимизации / A.C. Стрекаловский. - Новосибирск: Наука, 2003. - 356 с.

15. Груздева, Т.В. Негладкие задачи минимизации разности двух выпуклых функций / Т.В. Груздева, A.C. Стрекаловский, A.B. Орлов, О.В. Дружинина // Вычислительные методы и программирование. - 2011. - Т. 12. - С. 384-396.

16. Strekalovsky, A.S. On Solving Optimization Problems with Hidden Nonconvex Structures / A.S. Strekalovsky // Optimization in Science and Engineering. In Honor of the 60th Birthday of Panos M. Pardalos. - Springer. - 2014. - P. 465-502.

17. Поляк, Б.Т. Введение в оптимизацию / Б.Т. Поляк. - М.: Наука: Гл. ред. физ,-мат. лит., 1983.-384 с.

18. Заботин, В.И. Сходимость итерационного метода решения задачи математического программирования с ограничением в виде выпуклой гладкой поверхности / В.И. Заботин, Ю.А. Черняев // Журнал вычислительной математики и математической физики. - 2004. - Т. 44, № 4. - С. 609-612.

19. Черняев, Ю.А. Два алгоритма решения задачи математического программирования с предвыпуклыми ограничениями / Ю.А. Черняев // Журнал вычислительной математики и математической физики. - 2004. -Т. 44, №7.-С. 1229-1233.

20. Черняев, Ю.А. Два метода минимизации выпуклых функций на классе невыпуклых множеств / Ю.А. Черняев // Журнал вычислительной математики и математической физики. - 2008. - Т. 48, № 10. - С. 1802-1811. 21.3аботин, В.И. Предвыпуклые множества, отображения и их приложения к экстремальным задачам / В.И. Заботин, Ю.А. Полонский // Кибернетика. -1981. -№ 1.-С. 71-74.

22. Ортега, Дж. Итерационные методы решения нелинейных систем уравнений со многими неизвестными / Дж. Ортега, В. Рейнболдт. - М.: Мир, 1975. - 560 с.

23. Заботин, В.И. Итерационный алгоритм проектирования точки на невыпуклое многообразие в линейном нормированном пространстве / В.И. Заботин,

A.M. Дуллиев // Журнал вычислительной математики и математической физики. - 2004. - Т. 44, № 5. - С. 834-837.

24. Булатов, В.П. Метод отсечения в Еп+Х для решения задач глобальной оптимизации на одном классе функций / В.П. Булатов, О.В. Хамисов // Журнал вычислительной математики и математической физики. - 2007. -Т. 47, № 11.-С. 1830-1842.

25. Jouini, Elyes. Generalized Lipschitz functions / Elyes Jouini // Nonlinear Analysis.

- 2000. - Vol. 41. - P. 371-382.

26. Chidume, Charles. Geometric Properties of Banach Spaces and Nonlinear Iterations. Lecture Notes in Mathematics / Charles Chidume. - Springer, 2009. - 326 pp.

27. Vanderbei, R.J. Extension of Piyavskii's Algorithm to Continuous Global Optimization. DIMACS Technical Report 97-23 / R.J. Vanderbei. - Princeton University: Statisticsand Operations Research, 1997.

28. Vanderbei, R.J. Extension of Piyavskii's Algorithm to Continuous Global Optimization / R.J. Vanderbei // Journal of Global Optimization. - 1999. - Vol. 14. -P. 205-216.

29. £inlar, Erhan. Undergraduate Texts in Mathematics / Erhan £inlar, R.J. Vanderbei.

- Springer, 2013. - 170 pp.

30. Люстерник, Л.А. Элементы функционального анализа / Л.А. Люстерник,

B.И. Соболев. - 2-е изд. перераб. - М.: Наука, 1965. - 520 с.

31. Соболев, В.И. Лекции по дополнительным главам математического анализа / В.И. Соболев. -М.: Наука: Гл. ред. физ.-мат. лит., 1968. -288 с.

32. Заботин, В.И. Два алгоритма отыскания проекции точки на невыпуклое множество в нормированном пространстве / В.И. Заботин, Н.К. Арутюнова // Журнал вычислительной математики и математической физики. — 2013. -Т. 53, №3.-С. 344-349.

33. Заботин, В.И. Итерационные алгоритмы проектирования точки на невыпуклое множество / В.И. Заботин, Н.П. Заботина, Н.К. Арутюнова // Математические методы и информационные технологии в экономике, социологии и образовании: сборник статей XXV Международной научно-технической конференции. - Пенза: Приволжский Дом знаний, 2010. - С. 121-124.

34. Карманов, В.Г. Математическое программирование: Учеб. пособие / В.Г. Карманов. - 5-е изд., стереотип. - М.: ФИЗМАТЛИТ, 2004. - 264 с.

35. Шварц, Лоран. Анализ: в 2 т. Т. 1 / Лоран Шварц. - М.: Мир, 1972. - 824 с.

36. Васильев, Ф.П. Численные методы решения экстремальных задач: Учеб. пособие для вузов / Ф.П. Васильев. - 2-е изд. перераб. и доп. - М.: Наука: Гл. ред. физ.-мат. лит., 1988. - 552 с.

37. Васильев, Ф.П. Методы оптимизации / Ф.П. Васильев. - М.: Факториал Пресс, 2002. - 824 с.

38. Vanderbei, R.J. Uniform continuity is almost lipschitz continuity. Technical Report SOR-91-11 / R.J. Vanderbei. - Princeton University: Statistics and Opérations Research Sériés, 1991.

39. Арутюнова, Н.К. Обобщенный метод проекции точки на невыпуклое многообразие / Н.К. Арутюнова, А.Ф. Загидуллин // XVIII Туполевские чтения: сборник трудов Международной молодежной научной конференции. -Казань, 2010.-С. 131-132.

40. Арутюнова, Н.К. Алгоритмы проектирования точки на поверхность уровня непрерывной на компакте функции / Н.К. Арутюнова, А.М. Дуллиев, В.И. Заботин // Журнал вычислительной математики и математической физики. - 2014. - Т. 54, № 9. - С. 1448-1454.

41. Arutyunova, N.K. Algorithms for Projecting a Point onto a Level Surface of a Continuous Function on a Compact Set / N.K. Arutyunova, A.M. Dulliev, V.I. Zabotin // Computational Mathematics and Mathematical Physics. - 2014. -Vol. 54, №9.-P. 1395-1401.

42. Евтушенко, Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) / Ю.Г. Евтушенко // Ж. вычисл. матем. и матем. физ.- 1971.-Т. 11, №6.-С. 1390-1403.

43. Арутюнова, Н.К. Модификация метода Евтушенко поиска глобального минимума для случая непрерывной на компакте функции / Н.К. Арутюнова // Вестник КГТУ им. А.Н. Туполева. - 2013. - №2, вып. 2.- С. 154-157.

44. Арутюнова, Н.К. Метод Евтушенко поиска глобального минимума

S-липшицевой функции и его приложения / Н.К. Арутюнова // Математические методы и информационные технологии в экономике, социологии и образовании: сборник статей XXXIII Международной научно-технической конференции. - Пенза: Приволжский Дом знаний, 2014. -С.22-25.

45. Zabotin, V.I. Sufficient conditions for the existence of multichannel global communication satellite systems / V.I. Zabotin // Cosmic Research. - 2000. -Vol. 38, №1.-P. 91-95.

46. Арутюнова, Н.К. Модифицированный метод штрафных функций для решения задачи потребительского выбора с дисконтированием цен / Н.К. Арутюнова,

B.И. Заботин, К.С. Исхакова // Математические методы и информационные технологии в экономике, социологии и образовании: сборник статей XXXI Международной научно-технической конференции. - Пенза: Приволжский Дом знаний, 2013. - С. 34-37.

47. Замков, О.О. Математические методы в экономике: Учебник / О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемных. - 2-е изд. - М.: МГУ им. М.В. Ломоносова: Дело и Сервис, 1999. - 368 с.

48. Минюк, С.А. Математические методы и модели в экономике: Учеб. пособие /

C.А. Минюк, Е.А. Ровба, К.К. Кузьмич. - Мн.: ТетраСистемс, 2002. - 432 с.

49. Шелобаев, С.И. Математические методы и модели в экономике, финансах, бизнесе: Учеб. пособие для вузов / С.И. Шелобаев. - М.: ЮНИТИ-ДАНА, 2001.-367 с.

50. Черемных, Ю.Н. Микроэкономика. Продвинутый уровень / Ю.Н. Черемных. -М.: ИНФРА-М, 2008. - 844 с.

51. Фридман, A.A. Лекции по курсу микроэкономики продвинутого уровня /

A.A. Фридман. -М.: Изд. дом ГУ ВШЭ, 2007. - 375 с.

52. Ян, Икума Иссомбо. Численное решение задачи потребительского выбора с нелинейными бюджетными ограничениями / Икума Иссомбо Ян // Международный журнал «Программные продукты и системы». - 2011. - № 2. - С. 76-79.

53. Заложнев, А.Ю. Модели принятия решений об объемах закупок фирмой -оптовым покупателем в зависимости от изменения отпускных цен производителя и спроса конечных покупателей / А.Ю. Заложнев // Сборник трудов «Управление большими системами». - 2003. - № 3. - С. 35-42.

54. Арутюнова, Н.К. Экономико-математическая модель задачи потребительского выбора с ценами благ, зависящими от объёма покупок / Н.К. Арутюнова,

B.И. Заботин, Н.П. Заботина // Вестник экономики, права и социологии. -2014.-№2. -С. 7-10.

СПИСОК ИЛЛЮСТРАТИВНОГО МАТЕРИАЛА

Рис. 1.1. Пояснение условия (1.3)................................................................................14

Рис. 2.1. Пример е-липшицевой функции...................................................................26

Рис. 3.1. График функции (3.8) для набора коэффициентов 1..................................51

Рис. 3.2. График функции (3.8) для набора коэффициентов 2..................................51

Рис. 4.1. График функции/(х)......................................................................................61

Рис. 4.2. Тип 1 («ступенчатый») функций цены и стоимости блага........................70

Рис. 4.3. Тип 2 («кусочно-линейный») функций цены и стоимости блага..............72