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

На правах рукописи

АРУТЮНОВА НАТАЛЬЯ КОНСТАНТИНОВНА

МЕТОДЫ ПРОЕКТИРОВАНИЯ ТОЧКИ В НОРМИРОВАННЫХ ПРОСТРАНСТВАХ И ИХ ПРИЛОЖЕНИЯ

Специальность: 01.01.07 - Вычислительная математика

? о №1

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

005569988

Казань 2015

005569988

Диссертационная работа выполнена на кафедре Прикладной математики и информатики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Казанский национальный исслсдоватсльский технический университет имени А.Н. Туполева - КАИ» (КНИТУ-КАИ)

Научный Заботин Владислав Иванович

руководитель доктор технических наук, профессор, профессор каф.

прикладной математики и информатики КНИТУ-КАИ

Официальные Хайруллин Мухамед Хильмиевич

оппоненты: доктор технических наук, профессор, действительный

член РАЕН, заведующий лабораторией подземной гидродинамики института механики и машиностроения Казанского научного центра РАН

Стрекаловский Александр Сергеевич

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

Ведущая Федеральное государственное бюджетное учреждение

организация науки Вычислительный центр им. A.A. Дородницына

Российской академии наук

Защита состоится 25 июня 2015 года в 14 часов 30 минут на заседании диссертационного совета Д 212.081.21 при ФГАОУ ОНО «Казанский (Приволжский) федеральный университет» в 218 аудитории 2 корпуса но адресу: 420008, г. Казань, ул. Кремлевская, 35.

С диссертацией можно ознакомиться в Научной библиотеке имени Н.И. Лобачевского Казанского (Приволжского) федерального университета по адресу: 420008, г. Казань, ул. Кремлёвская, 35.

Электронная версия автореферата размещена на официальном сайте Казанского (Приволжского) федерального университета: www.kpfu.ru.

Автореферат разослан «Л? »

2015 г.

Ученый секретарь диссертационного совета доктор физико-математических наук, профессор

у Ф1.

Задворнов O.A.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В общем виде математическая модель указанной задачи может быть записана в следующем виде:

Пусть множество СсЕ, где Е — нормированное пространство, пусть также задана точка а е Е, а г С. Требуется

р(.г,а)-» min,

при ограничениях .ve С, где p(.v, а) — расстояние между точками а и .v.

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

B.Н. Малозёмова алгоритм поиска проекции нуля пространства на выпуклый многогранник. Позднее в работах Л.Г. Турина, Б.Т. Поляка и Э.В. Райка, Ph. Wolfe, A.A. Dax, H.H. Bauschke и J.M. Bonvein, E.A. Нурмннского,

C.H.J. Pang были предложены различные алгоритмы проектирования точки на многогранники, выпуклые множества, задаваемые в виде пересечения выпуклых множеств и др.. Л.М. Брсгман рассматривает задачу проектирования в некотором смысле точки на пересечение выпуклых замкнутых множеств линейного топологического пространства. Можно отметить также разработанную З.Р. Габидуллпной конечношаговую процедуру поиска проекции точки па выпуклый многогранник.

В работе А.Н. Куликова и В.Р. Фазылова рассматривается некоторое обобщение задачи проектирования точки на выпуклое замкнутое множество конечномерного евклидова пространства и построена конечношаговая процедура cí o решения.

Поскольку не всякое множество может быть выражено через выпуклые, полезным таком случае может оказаться подход, предложенный Н. Тиу, F. Al-Khayyal н Р.Т. Thach. При 'этом подходе с каждым шагом повышается точность аппроксимации множества С, однако при этом усложняется п структура нового аппроксимирующего множества, и вспомогательная задача может оказаться также весьма трудоёмкой.

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

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

В случае достаточной гладкости функции, задающей множество С, применимы методы ньютоновского типа. Для случая, когда С задано как множество нулей функции, удовлетворяющей на некотором выпуклом компакте условию Липшица-Гсльдсра, В.Н. Заботипым и A.M. Дуллпсвым был предложен итерационный алгоритм проектирования.

Задачи проектирования нередко возникают при решении оптимизационных задач, в частности, они являются вспомогательными при реализации методов типа проекции градиента. Механизм проектирования оказывается существенным также в решении задач математического программирования с предвыпуклым множеством ограничений методами, разработанными в ряде работ Ю.А. Черняева и В.И. Заботина.

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

Основные цели работы:

1) постановка и анализ задач проектирования на множество нулей (или некоторой его аппроксимации) функции, определённой на некотором выпуклом компакте и удовлетворяющей на нём условию подчинения более общего вида, нежели условие Липшица, в частности, являющейся е-липшицевой;

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

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

4) создание комплекса программ, реализующих предложенные алгоритмы.

Диссертационная работа состоит в решении следующих задач:

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

• разработка и обоснование приближённых и точных алгоритмов проектирования на множество нулей функции, удовлетворяющей на некотором выпуклом компакте условию с-липшицевости (непрерывности);

• разработка и обоснование алгоритмов и способов решешш вспомогательных задач, возникающих при реализации предлагаемых методов проектирования, в частности:

- алгоритма глобальной минимизации непрерывной на отрезке функции, основанного на идее метода, разработанного Ю.Г. Евтушенко;

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

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

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

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

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

• проведение численных испытаний разработанного нрофаммиого обеспечение и подтверждение таким образом работоспособности предложенных алгоритмов.

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

Научная новизна:

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

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

• Предложен и обоснован простой в реализации, основанный па идее Ю.Г. Евтушенко метод поиска глобального минимума непрерывной па отрезке функции, представляющий также и отдельный интерес.

• Построена одна экономико-математическая модель задачи потребительского выбора, показана возможность её решения предложенными алгоритмами, проведены численные эксперименты.

Практическая ценность:

• Получены численные алгоритмы проектирования на классы множеств, не рассматривавшихся ранее;

• Предложенная модель задачи потребительского выбора более адекватно описывает стратегию поставщика благ по ценообразования, нежели классическая модель;

• Разработаны программные приложения для решения задач, сформулированных в работе:

- задач проектирования размерности до 4;

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

- задачи поиска первого слева пуля непрерывной на отрезке функции;

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

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

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

Апробация работы. Основные результаты работы были представлены в виде докладов на следующих конференциях: XXV Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2010 г.), XVIII Международной молодежной научной конференции «Туполевские чтения» (г.Казань, 2010г.), XXXI и XXXIII Международных научно-технических конференциях «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2013 и 2014 гг.), а также на научном семинаре академика РАН Ю.Г. Евтушенко в ВЦ РАН (2015 г.).

Публикации. По тематике работы опубликовано 9 печатных работ, из которых 4 научные статьи - в рецензируемых журналах, рекомендованных ВАК (Журнал вычислительной математики и математической физики, Вестник КГТУ и Вестник экономики, права и социологии), англоязычная версия одной из которых - в журнале, входящем в международную систему цитирования SCOPUS (Computational Mathematics and Mathematical Physics).

Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка сокращений и условных обозначений, списка использованной литературы, включающего 54 наименования, списка иллюстративного материала и приложения. Работа изложена на 97 страницах машинописного текста, содержит 7 таблиц, 10 рисунков.

Личный вклад автора.

Глава 1. Постановка задачи 1 и доказательство предложения 1.1 выполнены совместно с В.И. Заботиным. Остальные результаты главы получены автором диссертации.

Глава 2. Постановка задачи 2.2 н доказательства лемм 2.2, 2.3 выполнены совместно с В.И. Заботиным, формулировка алгоритма 2.3 и доказательство предложения 2.10 — совместно с A.M. Дуллиевым. Остальные результаты главы принадлежат автору.

Глава 3. Все результаты принадлежат автору.

Глава 4. Предложение 4.1 доказано совместно с В.И. Заботиным. Постановка задачи потребительского выбора с ступенчатой функцией цены (тип 1) предложена автором, В.И. Заботиным и Н.П. Заботиной. Построение математических моделей типа 1 и типа 2 и их анализ, а также разработка алгоритмов выполнены автором. Остальные результаты главы принадлежат автору.

Разработка всех рабочих алгоритмов, программного обеспечения и расчёты тестовых задач выполнены автором.

СОДЕРЖАНИЕ РАБОТЫ

Всюду в работе, если не оговорено иного, приняты следующие обозначения: Е - нормированное пространство; А с Е - выпуклый компакт (в смысле компактности в себе); int ß, cl В, dB - внутренность, замыкание и граница множества В а Е соответственно; X" с А множество нулей функции /, определённой на/1. Все функции предполагаются действительнозначными.

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

В Первой главе предложен и обоснован алгоритм проектирования точки на множество нулей функции, удовлетворяющей условиям более общего вида, нежели условие Липшица.

Пусть на Е определена выпуклая функция q(x) такая, что q(x) = 0 тогда и только тогда, когда х = 0. Пусть/'удовлетворяет условию:

V.y, v е А:: /(*)- /0')| < ч{х ~ у)- (1)

Если для а е А, /(Vi) > 0, и некоторого х* е А" имеет место v(a, X' )= q(x' — а), где

\'(я,А")= inf q(x-a), (2)

точку .г будем называть проекцией в смысле (2) точки а на множество А".

Ставится задача 1: Построить и обосновать алгоритм отыскания проекции в смысле (2) заданной точка а на множество АЛ

Для решения данной задачи предлагается алгоритм Г.

Шаг 0. Задаются к := 0, х0 := а.

Шаг 1. Строится множество Кк = j.v е Е: q(x - а) < У /(.у,- )|.

Шаг 2. Находится следующая итерационная точка: .rt+l = arg m in {/(.г): x e 8 Kk П А}.

Шаг3. Если/(.v/tu) = О,

то xt 11 принимается в качестве искомой проекции,

иначе полагается к :- к I 1 и осуществляется переход к шагу 1.

Предложение 1.1. Любая из предельных (в смысле нормы пространства Е) точек последовательности хь построенной с помощью алгоритма I, принадлежит множеству )С.

Предложение 1.2. Если х' с X' - предельная точка последовательности Xi, построенной по алгоритму /, то она является проекцией в смысле (2) точки а на X".

Предложение 1.3. Если х' е X" - единственная ближайшая в смысле (2) к а точка из X*. то х, —■—>х*.

Предложение 1.4. Если множество X" нулей функции f на компакте А пусто, то алгоритм 1 обнаружит это за конечное число шагов.

Пусть Е - и-мерное евклидово пространство и функция f(x\,Х2, ...,х„), удовлетворяет условию Липшица-Гельдера покоординатно: V/ = П" 31;,а, > 0 Vx;,x? е А:

!/(.v, v,_,, х;, хш ,...,х„)-/(.г,,..., .т,_,, х", хм ,...,xj< /,, |х; - .r,f.

Предложение 1.5. Условие (3) эквивалентно тому, что найдутся L, > 0 и а, > 0, i = 1,2,..., п, при которых для всехх,у е А имеет место неравенство

i=i

Можно заметить, что при а; > 1, i = 1, 2,..., п, функция

q(x)=±L,\x,r (4)

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

Однако случай, когда а,>1, г = 1, 2,н, не представляет интереса, поскольку в этом случае функция будет постоянной. Таким образом, условие (1) с функцией q(x) вида (4) при а, = 1 эквивалентно условию (3).

Для случаев, когда Е = R2 и Е - R\ а функция / удовлетворяет условию (3), алгоритм 1 решения задачи 1 реализован программно и в проведённых тестовых расчётах показал свою работоспособность и ожидаемые результаты.

Во Второй главе ставятся и решаются задачи проектирования точки на множество, определяемое функцией/, которая удовлетворяет условию:

Ve > 0 3 ¿(с) > 0 V.v, у е A: |/(.r) - f(y) < ¿(е)[дг - j|| + с, названному предложившим его Robert J. Vanderbei условием с-липшицевости.

В той же работе Robert J. Vanderbei показывает, что всякая непрерывная на выпуклом компакте конечномерного евтидова пространства функция является г-липшицевой, и предлагает подходы к определению оценки Z(e).

Задача 2.1: Построить и обосновать численный алгоритм решения задачи проектирования точки а е A (J (а) > 0) на множество А' = {.г е А: 0 <f(x) < е}, в смысле нормы пространства;

Задача 2.2: Построить и обосновать численный алгоритм решения задачи проектирования точки а е A (f (а) > 0) на множество X" = {х е A: f(x) = 0} & 0 в смысле нормы пространства.

Для решения задачи 2.1 предлагается следующий алгоритм, названный в работе приближенным.

Алгоритм 2.1.

Шаг 0. Полагается к = 0, д-0 = а.

Шаг 1. Если/(л*) < с,то л* принимается за искомую точку, иначе производится переход к шагу 2.

Шаг 2. Определяются

/Ы-s

¿(с)

Kk=<xeE:\x-ai< , хк+] =argmin{/(.r):.vecA'A. ГЫ}.

Шаг 3. Полагается к к + 1 и осуществляется переход к шагу 1. Для доказательство сходимости алгоритма получен ряд предложении. Предложение 2.1. Если f(xt) > с, шо/(х) > 0 на int Кк П А. Предложение 2.2. 1 °.Если существует к, для которого / (х*) > е, af (хц i) < е, то х* (i е Л1:. 2°.Если для любого к имеет место f{xk) > £, то любая предельная точка построенной последовательности х* есть точка изА\

Предложение 2.3. Если ЛЛ; = 0, то алгоритм 2.1 обнаружит это за конечное число шагов.

Для каждого фиксированного s е (0,/(а)) обозначим /(c) = inf{l(c)}. Константа L(c) для функции/названа s-достижимой, если

Эх0, Л е Л, х0 * у0 : |/(хп ) - /(.yn ) = l(c)||x0 - у01 + с. Лемма 2.1. Для любого е е (0, f(a)) имеет место 1(с.)> 0, /(е) е {¿(е)}, или, иными словами, нижняя грань множества {¿(с)} достижима.

Лемма 2.2. Оценка /(с) с-достижи.ма при любом фиксированном с е (0,/(«)). Если L(c) с-достижима, то ¿(с) = /(с). Лемма 2.3.

1°./(е) строго возрастает при е. монотонно стремящемся к нулю. 2°.Если /(с) ограничена на (0,/(я)) сверху, то/- липшицева. Алгоритм 2.2.

В силу свойства 2° будем полагать неограниченность /(s) сверху. Шаг 0. Задаются начальная точка хл = а е А, значение параметра алгоритма А е (0; 1), номер шага к := 0.

Шаг 1. Вычисляются величины: параметр ¡д = ^/(хд), соответствующая fix )

оценка Кг.Л пяти^ г. = — f 1 — ^ )

Шаг 3. Eani/'(xui) = 0,

то Xi. 1 берётся в качестве решения поставленной задачи, иначе - принимается к := к + 1 и выполняется переход к шагу 1.

Предложение 2.4. Если х е int Кк П А. то/(х) > 0.

Предложение 2.5. Если хц - итерационная последовательность, формируемая алгоритмом 2.2, то f(xL)—>0.

Предложение 2.6. Если у* е А* и у* - предельная точка последовательности хк, то р(а,А")=|'а-у* |, то есть у - ближайшая к а точка из Л'*.

Предложение 2.7. Если Л* состоит из единственной точки или ближайшая к а точка из )С единственна, то хк сходится к этой точке.

Предложение 2.8. Если Л" = 0, то алгоритм 2.2 обнаружит это за конечное число шагов.

Алгоритм 2.3.

Шаг 0. Задаются начальное значение параметра е0 > 0, начальная точка .го = а е А, параметры алгоритма у, л, е (0; 1). Полагаются у0 := к ■= 0, т := 0.

Шаг 1. Если/{хк) < >:к (1 + у),

то последовательно устанавливаются лг*+1 := У™-1 хк,

т := т + 1, и производится переход к шагу 2; иначе - переход к шагу 3.

Шаг 2. Если/О*) < е*, то принимается £ы ™ а/(**),

иначе устанавливается едг-1 := Ул\к\ и производится переход к шагу 4.

ШагЗ. Определяется хы но схеме:

г, ={.геЕ:|!.х-а|<У/;.1.г4+| =аг8т1п{/(.г):.ге5А:1[ П^};

А5*) [ ыа \

полагается Еж := ск и осуществляется переход к шагу 4.

Шаг 4. Если/(лч+1) = 0 или/(у,„) = 0,

то принимается л^ц илиут, соответственно, в качестве решения задачи;

иначе устанавливается к := к + 1 и выполняется переход шагу 1.

Предложение 2.9. Пусть по-прежнему функция /(л*) непрерывна на выпуклом компакте А и А7" * 0, тогда для любой предельной точки у' последовательности ут, построенной по алгоритму 2.3, имеет место у е А".

В случае конечности числа значений последовательности дг<, очевидно, в качестве решения принимается последнее найденное значение х'к или у^, по условию шага 4 алгоритма 2.3 принадлежащее множеству Л".

Предложение 2.10. Точки у", х*к или у* в зависимости от конечности числа значений последовательности хк являются проекциями начальной точки а б А на множество )С.

Предложение 2.11. Если )С = 0, то (игоритм 2.3 обнаружит это за конечное число шагов.

По предложенным принципиальным алгоритмам 2.1 - 2.3 были составлены рабочие алгоритмы для случаев, когда пространство Е имеет размерность до п = 4, а метрика, заданная в нём является евклидовой или

покоординатной, разработано программное обеспечение и рассчитан ряд тестовых задач.

В качестве примера рассмотрены следующие функции с соответствующими оценками постоянных е-липшицевости:

/ (Л'>}') - v'ki + \l\y\ > /2(л-,у)=л/|л-| + Ы,

Причём указанные оценки L(e) вследствие удовлетворения описанным в Леммах 2.1 - 2.3 условиям могут быть приняты в качестве /(с).

Проведённый анализ результатов показал, что наибольшее быстродействие имеет алгоритм 2.1, наименьшее - 2.2,

Результаты экспериментов также показали, что число итерационных шагов достаточно точно оценивается как 0( 1/е").

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

Задача 3: Для функции /=/(*), удовлетворяющей на отрезке [а; b] условию с-липшицевости. найти величину /' = min f(x).

л=[я;б]

Суть предлагаемой модификации метода Евтушенко для непрерывных на отрезке функций состоит в построении такой последовательности точек .Г1,.Г2, ...,х„ (а <л", <.v2 < ... <х„ < Ь), что значение функции в одной из них может быть принято в качестве некоторого приближения к /* с некоторой точностью е , т.е.

/(.ij = min/(.v,)<.r +с*. (5)

I <1П

Для работы алгоритма вводится дополнительный параметр е е (0; е*), для которого оценка ¿(е) считается известной.

Обозначим: h = 2(е* -е)/л(с); Е: = min Д\-Д Vi = TJi.

Алгоритм 3.

1) Задаётся начальная точка: л*, = а + hl2.

2)Для каждого / = 1,«-2 определяется .r;il = х,- + h + (f(xi)-F^/L{f).

3) Полагается x„ = min{.v„ , +h + (/(.v„_,)-F„_t)/L(c),b}.

4) Число n определяется из условия: лг„_, < b - h/2 < ,v„4 +h + (/(.т„_,)- )/L(c).

5) Величина F„ принимается в качестве искомого минимального значения/*.

Предложение 3.1. Описанный метод последовательного перебора решает задачу (5).

Алгоритм 3 реализован в виде отдельного ирофаммного приложения и использован как вспомогательное средство решения задачи глобальной минимизации Е-липшицевой функции на сфере, возникающей па одном из шагов алгоритмов 2.1 —2.3.

Следует отметать, что предложенная модификация представляет и самостоятельный интерес, поскольку даёт возможность численной минимизации непрерывной на отрезке функции.

Предложенная модификация имеет преимущества перед обобщением метода Пиявского, предложенного R.J. Vandcrbci, аналогичные преимуществам метода Евтушенко перед методом ломаных.

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

Для покоординатной нормы естественным является отыскание минимума на каждой из ipaiicii гиперкуба.

Для евклидовой нормы понизить порядок позволяет обобщённая сферическая замена с соответствующим пересчётом оценки постоянной Е-липшнцевости. Пусть:

х{ = а1 + р • cos фл_г • cos ф„_2 •... • cos Ф2 • cos Ф,,

х2 = а2 + p-cosv„_, -со5ф„_2 - ...-cosqb -sincp,, 0<ф, <2n,

х} = a¡ + P-COS4V,-со5фл„2 ■...'Sin((i2, _

: --<ф,.<-, i=2,n -1,

■Vi = a„-\ + P • eos <pn4 • sin ф„_2, 2 2

,v„ =an + p-simp„_,,

где a¡, x¡, i = l,n, - декартовы координаты точек а и дг, соответственно, а (р,ф[,ф,,...,ф„^) - сфсричсскис координаты точки х, причем р = const для всех точек сферы дК, что и понижает размерность задачи.

Через ^„фг.-.ф^,) обозначены значения функции / на сфере дК,

после указанной замены.

Лемма 3.1. Если функция f к-лшииицева по переменным хь ..., х„ с постоянной Lf, то функция F г-липишцева по каждой из переменных (f>¡, i = 1,н -1, при фиксированных остальных с постоянной L% = v'2 pLf.

Введем в рассмотрение функции: _

Ф,.(ф|,ф2,...,ф„_;_1) = штпцп...пнп/;'(ф1,ф2,...,ф„_1), i = 1,п-2.

Лемма 3.2. Каждая функция Ф,(ф1,ф2,---,ф„-,-1). i = hn-2, г-липшицева

по переменной Ф„_,_; при любых фиксированных ф, е [О;2тх], ■ j = 2,n — 2-i, с постоянной £ф =л/2р

1Z _ л "2'2

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

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

Частным случаем задачи 2.2 проектирования точки является задача поиска первого слева нуля непрерывной на отрезке функции.

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

Алгоритм 4.1 также реализован в виде программного приложения и произведены экспериментальные расчёты.

Предложение 4.1. Если А - компактное множество в Я", то функция расстояния р(х, А)лшииицева по х с константой Липшица, равной 1.

Теперь (как, например, предложил Ф.П. Васильев) п качестве функции штрафа можно брать р(х,А) и использовать метод штрафных функций по схеме, предложенной В.Г. Кармановым, строя штрафную функцию в виде: =/(*)/Р* +р(*,Л), где р^—-—>=о. В предположении липшицсвости / функция Ф* становится липшицевой с постоянной 1к = ¿у/Р; +1.

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

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

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

В диссертации рассматривается, так называемая, прямая задача (маршаллианского типа), классическая постановка которой имеет вид: и[х) = и(х,, .г-,,..., хп ) -> шах, хев,

1>,.т,-М = 0.

j=^

Здесь:

• ...,л„)г, л>>0, у' = 1,п, - набор благ, приобретаемых покупателем,

где.гу, у = 1,я, измеряются в «непрерывно изменяющихся» единицах;

max

допустимое

множество наборов благ (.r™in и .t™x - фиксированные минимальное и максимальное количсства./'-го блага, доступные для приобретешь);

• Р = (Риpi, ■ • ■,Р»), Pi = const, pj > О, j вектор цеп благ, установленных па приобретаемые потребителем блага;

• М > О - доход (капитал) потребителя, т.е. ограниченное количество денежных средств потребителя, которые он может использовать для приобретения благ;

• и = и(х) - функция полезности, отражающая уровень (или степень) удовлетворения его потребностей приобретаемым набором благ .v, предполагаемая изотопной.

Линейность ограничений задачи обеспечивается предположением о

постоянстве значений цен pj, j = \,п.

Задача с простейшими зависимостями Pj=Pj(xj), j = 1,", рассмотрена в работе Икума Иссомбо Ян. Однако эта работа имеет ряд существенных неточностей. _

В данной диссертационной работе предлагается считать pj =pj(xj), j = нсвозрастающей по переменной xj функцией на отрезке [л-'™'; х"'" ]. Стратегия продавца по понижению цены р/л>) считается известной покупателю для каждого j = 1,п.

Теперь задача примет вид:

и(х) = u(xt,x2,...,x„)->ma\,

S{x)-M= 0, (6)

.X е G,

где S(x) = 5(д:, р(х))- функция стоимости всего приобретаемого набора благ х.

Функцию будем вычислять как сумму площадей фигур под

графиками pj = p/xj), на отрезке [0; .г,], j = \,п, т.е.:

В работе предложены два типа функций р, --р/л>) и соответствующих зависимостей = у' = 1 ,п. Ниже для удобства индекс у опущен и

использована верхняя индексацию цен и количеств блага.

Тип 1 («ступенчатый»). Пусть заданы величины рт >р"^ >...>/;' > >р° > 0 и 0 < я'"< а1 < ... <ат. Примем я° = 0, и введем величину ат+1 наибольшего количества блага, доступного для приобретения (ят+1 > я"'). Закон изменения цены в зависимости от количества приобретаемого блага примет

где

о

вид:

(я'; я1+1 ], 1=0, т.

р(х) = р"'', если .г б

При этом стоимость 5 всего количества х, х е (0;«'""]. приобретаемого блага будет вычисляться по формуле:

о

Графически вид таких зависимостей поясняет рис. 1. Можно показать, что

S(.r)= min /}Л,.(л-),

P,={pf), j'Jj; U = о,

I aJ^-aJ, J<i,

<x~aJ 0,

j=i, /', j = 0, m. j>i,

P»

P"

p«-1

P' P"

ii° = 0

а' а- a'

am а"

а)

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

Тип 2 («кусочно-лнненный»), Принимается 0 = и < а < а~ < ... <

<ат< а™'1 и/?",+1 = рт > ртЛ > ... >р1 >ра > 0.

Функции цены и стоимости при этом задаются следующим образом:

_ + 1 Г 1 _

7ТГ1—#—,- = 0,1И,

Графическое представление данных функций приведено на рис. 2. В работе показано, что функции стоимости покупки одного блага для двух типов стратегий являются липшицевымн с постоянной, равной р'". Функция стоимости всей покупки, состоящей из нескольких п > 1 благ, тогда

И

будет удовлетворять условию Липшица с постоянной ^ = и условию

покоординатной лнпшнцевости с постоянными [>'■ по соответствующему ху. Таким образом, функция стоимости всей покупки 5(х) будет удовлетворять условию подчинения (1) с функцией q{x) вида:

п

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

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

Будем считать целевую функцию и(х) и функцию ограничения &(х) = 5(х)-Л/ липшицевыми с известными постоянными Липшица ¿„ и соответственно.

Будем минимизировать функцию Фк =-аки(х) + \^(х}, где сц>0,

а,->0. Её постоянная Липшица вычисляется но формуле: Ьк =акЬи + Ь .

К к

Алгоритм 4.2.

Шаг 0. Задаются точность е > 0; целое число г > 0; номер шага к := 0. Шаг I. Вычисляется (Ц и определяется точка Xм, как любая из точек множества а^тт{ф,(х):хеС} одним из методов минимизации липшицевых

функций.

Шаг 2. Если к кратно г,

то производится переход к шагу 3, иначе — к шагу 4.

ШагЗ. Если выполняется выбранное условие останова р(г*+1,л)5£ или у(х*+1,л)<е, то х*" принимается в качестве решения исходной задачи, иначе - осуществляется переход к шагу 4. Шаг 4. Устанавливается к := к + 1 и осуществляется переход к шагу 1.

В качестве примера рассмотрена задача потребительского выбора (6) для « = 2 благ, цены на которые снижаются по одной из описанных стратегии, с функцией полезности типа функции Леонтьева:

"(-т|-л2)= 111111 {'/[-т|.72}, .V, ,.г2,у,,у2 >0.

Её постоянная Липшица может быть вычислена по формуле Ьи = тах{у, ,у2 }, а функция полезности г/(.гь /с,) не будет гладкой.

Для решения такого типа задач потребительского выбора на основе описанного принципиального алгоритма 4.2 был построен рабочий алгоритм, реализованный затем программно. Были проведены расчёты тестовых примеров с различными стратегиями обоих типов понижения цен наборов из двух благ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В диссертационной работе поставлены н решены следующие задачи:

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

2) разработка и доказательство сходимости приближённого метода проектирования точки на поверхность уровня Е-липшнцевой функции;

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

4) разработка и обоснование метода глобальной оптимизации олипгшщевых функций на отрезке;

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

6) разработка рабочего алгоритма поиска первого слева нуля е-липшицевой на отрезке функции;

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Арутюнова, Н.К. Обобщенный метод проекции точки на невынуклое

многообразие / Н.К. Арутюнова, А.Ф. Загидуллин // XVIII Туполсвскис

чтения: сборник трудов Международной молодежной научной конференции. - Казань, 2010. - С. 131-132.

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

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

4. Арутюнова, Н.К. Модифицированный метод штрафных функций для решения задачи потребительского выбора с дисконтированием цен / Н.К. Арутюнова, В.И. Заботин, К.С. Исхакова // Математические методы и информационные технологии в экономике, социологии и образовании: сборник статей XXXI Международной научно-технической конференции. -Пенза: Приволжский Дом знаний, 2013. - С. 34—37.

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

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

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

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

9. Англоязычная версия статьи 8:

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).

Формат 60x84 1/16. Бумага офсетная. Печать цифровая. Усл. печ. л. 0,93. Тираж 100. Заказ Д 25.

Полиграфический участок Издательства КНИТУ-КАИ 420111, Казань, К. Маркса, 10.