Содержание к диссертации
Введение
ГЛАВА 1. Метод проекции точки на поверхность уровня функции, удовлетворяющей условиям подчинения, обобщающим условие липшица 10
1.3. Доказательство сходимости алгоритма 1 13
1.4. Одна задача проектирования для случая конечномерного евклидова пространства 19
1.5. Программная реализация и численный пример 20
1.6. Выводы по Главе 1 22
ГЛАВА 2. Методы проектирования на поверхность уровня е–липшицевой функции 23
2.1. Приближённый алгоритм 24
2.1.1. Описание алгоритма 2.1 24
2.1.2. Доказательство сходимости алгоритма 2.1 24
2.2. Точные алгоритмы 28
2.2.1. Некоторые вспомогательные утверждения 28
2.2.2. Описание алгоритма 2.2 31
2.2.3. Доказательство сходимости алгоритма 2.2 32
2.2.4. Описание алгоритма 2.3 35
2.2.5. Доказательство сходимости алгоритма 2.3 36
2.3. Программная реализация и численный пример 38
2.4. Выводы по Главе 2 41
ГЛАВА 3. Решение некоторых вспомогательных задач минимизации липшицевых и є-липшицевых функций, возникающих при реализации алгоритмов проектирования точки 42
3.1. Модификация метода Евтушенко для непрерывных на отрезке функций 42
3.1.1. Постановка задачи 43
3.1.2. Описание алгоритма 3 43
3.1.3. Обоснование алгоритма 3 44
3.1.4. Численный пример 45
3.2. Некоторые способы понижения размерности многомерных задач минимизации липшицевых и s-липшицевых функций 47
3.2.1. Понижение размерности в задачах минимизации на сфере в пространстве с покоординатной метрикой 48
3.2.2. Понижение размерности в задачах минимизации на сфере в пространстве с евклидовой метрикой 49
3.3. Выводы по Главе 3 54
ГЛАВА 4. Некоторые модели и приложения методов
4.1. Поиск первого слева нуля непрерывной на отрезке функции 56
4.1.1. Описание алгоритма 4.1 56
4.1.2. Численный пример 57
4.2. Метод штрафных функций с выбором штрафа в виде функции расстояния 58
4.3. Одно обобщение классической модели задачи потребительского выбора
4.3.1. Описание моделей задач потребительского выбора 62
4.3.2. Анализ и численные методы решения обобщённой задачи потребительского выбора 68
4.4. Выводы по Главе 4 74
Список сокращений и условных обозначений 77
Список литературы 78
- Одна задача проектирования для случая конечномерного евклидова пространства
- Некоторые вспомогательные утверждения
- Некоторые способы понижения размерности многомерных задач минимизации липшицевых и s-липшицевых функций
- Метод штрафных функций с выбором штрафа в виде функции расстояния
Одна задача проектирования для случая конечномерного евклидова пространства
Настоящая глава посвящается разработке и обоснованию численных методов проектирования на поверхность уровня функции, определённой на компакте из нормированного пространства и удовлетворяющей на нём условию, так называемой, є-липшицевости, введённому в работах Robert J. Vanderbei [19-21], в которых автор ссылается на более ранний неопубликованный отчёт [28]. Приведём определение є-липшицевости. Пусть на некотором выпуклом компакте А нормированного пространства определена функция/ для которой выполняется следующее условие: для любого є 0 найдется такое L(s) 0, что для всех х,у є А выполняется условие
В работе [20] функция многих переменных, удовлетворяющая условию (2.1), названа г-липшицевой, и мы также будем придерживаться этой терминологии.
Пример є-липшицевой функции Там же [20] доказывается, что всякая непрерывная на выпуклом компакте конечномерного евклидова пространства функция является г-липшицевой. 2.1. Приближённый алгоритм
Пусть на А задана непрерывная функция f и некоторая точка а є А, для которой/!» 0. Ставится задача: Построить и обосновать численный алгоритм решения задачи проектирования точки а на множество X = {х є А: 0 /(х) є} в смысле нормы пространства.
Поскольку по (2.2) для всех х є Ко А справедливо равенство x-a = r0, аналогично доказывается, что при этом имеет место неравенство/(х) 0. Таким образом, на всём G0 =(int 0 n )U(5 0 П ) выполняется х - а\\ г0, и по тем же соображениям, что и в (2.3), получим Д.х) 0. Пусть теперь предложение справедливо для k -l, докажем его справедливость для к. Поскольку f (xk) є, то, очевидно, Кк–і X = 0. Возьмём точку уєш\КкА. Рассмотрим случай, когда
Если существует к, для которого f (xk) є, а f (xk+1) є, то x+1 є Xs. 2. Если для любого к имеет место f (xk) z, то любая предельная точка построенной последовательности хк есть точка изХ. Доказательство. Справедливость первого утверждения следует непосредственно из предложения 2.1, поскольку/ ) 0. Покажем, что справедливо второе утверждение.
Предложение 2.4. [30, 31] Если х є int Кк A, то f{x) 0. Доказательство. Проведем его аналогично доказательству предложения 2.1, по индукции. Положим, что к= 0 и уєМК0 А. Тогда исходя из условия є-липшицевости функции /, записанного для а и у, оценки (2.10) и правила построения радиуса rk (шаг 1 алгоритма 2.2), имеем: /М /(«)-/(Є0Ь-4-Є0=Г0/(Е0)-/(Е0) -« = /(Е0ХА0- -4) 0. Последнее неравенство справедливо в силу построения множеств Кк (шаг 2 алгоритма 2.2) и того, /(є0) 0 (см. лемму 2.1). Пусть теперь на int Кк имеет место/(х) 0. 1. Если найдется уєКкА такое, что f (y) = 0, то у можно будет взять в качестве Хк+\, но тогда гк+\ = 0 и, значит, Кк+\ = Кк, то есть на int +i А имеет место неравенство/ ) 0. 2. Если же для любого уєКкА имеет место f (y) 0, то достаточно показать, что/строго положительна на (int Кк+\ \ Кк) А.
Вначале рассмотрим случай, когда последовательность точек Хк, порождаемая алгоритмом, бесконечна.
Предложение 2.9. [30, 31] Пусть по-прежнему функция fix) непрерывна на выпуклом компакте А и Ґ Ф 0, тогда для любой предельной точки у последовательности ут, построенной по алгоритму 2.3, имеет место у є Ґ.
Доказательство. Из описания алгоритма видно, что уменьшение параметра Zu происходит, когда f (xk) < &k (1 + у). Из предложения 2.2 следует, что указанное неравенство при каждом т = 0, 1, 2, … будет достигаться за конечное число итераций, то есть, если кт - номер итерации такой, что гк < гк _х (по определению полагаем ко = 0), то кт+\ -кт< .
Некоторые вспомогательные утверждения
Скорость произведённых расчётов (время t и количество итераций п\ очевидно, зависят от самого характера функций, а также от полученных для них оценок постоянных є-липшицевости, поскольку их величина обратно пропорциональна радиусу рассматриваемых окружностей Кк. Таким образом, чем больше оценка /(є) (или Дє)), тем меньше шаг основного алгоритма.
Результаты указанной серии экспериментов показали, что число итерационных шагов достаточно точно оценивается как (9(1/є ). 2.4. Выводы по Главе 2 1. Предложен и обоснован приближённый алгоритм 2.1 проектирования на множество JF = {х є А: 0 /( ) є} для s-липшицевых функций. 2. Доказана серия лемм, устанавливающих свойства s-липшицевых функций и необходимых для обоснования алгоритма проектирования 2.2. 3. Предложены и обоснованы алгоритмы 2.2 и 2.3 проектирования точки на множество нулей є-липшицевой функции, названный в работе точным. 4. Построены рабочие алгоритмы для решения двумерных задач указанного типа. 5. Разработано программное обеспечение, реализующее указанные алгоритмы. 6. Просчитан ряд тестовых примеров с помощью разработанного программного обеспечения.
Каждый из предложенных алгоритмов содержит шаг нахождения глобального минимума функции на границе некоторого выпуклого множества, в частности на границе шара. Эти задачи можно решать с помощью известных программных продуктов. Однако особую сложность этот шаг представляет в случае є-липшицевости функции.
Существующим на данный момент методом, позволяющим решать указанную задачу, является модификация алгоритма Пиявского для є-липшицевых функций, предложенная в [20].
Однако, как известно, метод Пиявского при его программной реализации имеет высокие требования к оперативной памяти. Поэтому в данной главе предлагается и обосновывается более простая в реализации и менее требовательная к используемым объёмам памяти модификация метода последовательного перебора, разработанного Ю.Г. Евтушенко [32].
Последнее следует непосредственно из [20], где приводятся формулы для определения оценки постоянной є-липшицевости функций вида f (x) = Xа, где х є [0; b], а є [0; 1].
В Таблице 3.1 приведены результаты расчётов для двух наборов коэффициентов функции (3.8), трёх вариантов отрезка [а;Ь], на котором рассматривается функция, и четырёх различных сочетаний величин (точности) и (параметра алгоритма). Через xmin обозначена абсцисса найденной точки минимума функции, через Fn – значение функции в этой точке, n – количество рассматриваемых точек отрезка [a; b]. Кроме того, для приближённого оценивания временных затрат на расчёты приведено примерное время вычислений t.
Некоторые способы понижения размерности многомерных задач минимизации липшицевых и с-липшицевых функций
Описанная в [20] модификация метода Пиявского и предложенная выше модификация метода последовательного перебора Евтушенко предназначены для непосредственного решения одномерных задач минимизации s-липшицевых функций. Однако нередко, в частности, в описываемых в Главах 1 и 2 алгоритмах проектирования, возникает необходимость минимизации функции многих переменных. В данном подразделе будут описаны некоторые подходы к решению таких задач минимизации путём понижения их размерности в случае, когда в пространстве En выбрана одна из двух достаточно распространённых метрик: - покоординатная:
Схемы понижения размерности будут приводиться на примере реализации итерационных шагов 2 алгоритмов 2.1 - 2.3, поэтому номер итерации к в индексах обозначений для удобства будет опущен. Понижение размерности в задачах минимизации на сфере в пространстве с покоординатной метрикой
В случае покоординатной метрики «-мерного евклидова пространства, в котором решается задача нахождения точки минимума функции на сфере дК с центром в точке а и радиусом г, последняя будет представлять собой границу п-мерного куба с центром в а и длиной ребра 2г, то есть множество, состоящее из 2п кубов размерности (и- 1). Таким образом, размерность указанной задачи минимизации є-липшицевой функции f можно, в первую очередь, понизить на единицу по схеме: , перенумерованные так, что Si и Sn - параллельные друг другу и перпендикулярные оси ХІ грани. Таким образом, вычисление минимума в правой части (3.10) означает нахождение минимума функции f при отдельном фиксировании значения каждой /-й переменной - Понижение размерности в задачах минимизации на сфере в пространстве с евклидовой метрикой
Как и в случае покоординатной метрики, евклидова метрика позволяет в указанной задаче минимизации произвести понижении размерности задачи на единицу. Достигается это путём перехода от декартовой системы координат к обобщенной сферической.
Некоторые способы понижения размерности многомерных задач минимизации липшицевых и s-липшицевых функций
Однако трудоёмкость отыскания на каждом шаге значения р(х,А) или v(x, A) существенно зависит от условий, накладываемых на функцию g(x), поскольку для отыскания этого значения придётся проектировать точку х на множество А в соответствующем смысле. В любом случае, отыскание проекции на каждом шаге метода штрафных функций является дорогостоящей процедурой. Поэтому мы предлагаем использовать в (4.4) вместо р(х, А) значение \g(x]i, а выполнять проверку условия останова (4.5) или (4.6) лишь через определённое число шагов г. Таким образом, алгоритм проектирования будет задействован лишь при проверке условия останова.
Описанный метод штрафных функций реализован программно и использован для анализа предлагаемой ниже модификации модели задачи потребительского выбора.
Одно обобщение классической модели задачи потребительского выбора маршаллианского типа Классические модели маршаллианской (прямой) задачи потребительского выбора с линейными бюджетными ограничениями и гладкими функциями полезности изучены давно и являются предметом изложения в научной литературе по экономико-математическим моделям и методам [37-41].
Известны также двойственные (хиксианские) модели задачи потребительского выбора [40, 41], однако мы будем рассматривать лишь прямые (маршаллианские) задачи и для краткости именования этот факт будем опускать.
Представляет интерес изучение задач потребительского выбора с негладкими бюджетными ограничениями и негладкой функцией полезности. Как будет показано ниже, к таким задачам приводит предположение о зависимости цен, назначаемых продавцом, от количества приобретаемого потребителем блага.
Здесь существенную роль играет стратегия продавца (дилера) понижения цены. Простейшая стратегия понижения цен рассмотрена в [36]. Здесь цена товара p ( x) предполагалась аффинной убывающей на некотором отрезке функцией, аргументом которой является объём приобретаемого блага.
В работе [42] рассматривается задача маршаллианского типа (ошибочно названная двойственной, т.е. хиксианской), в которой стратегия изменения цены p ( x) имеет вид: v c + dx однако ничего не говорится о соотношении между величинами a, b, c и d, что делает постановку задачи некорректной, поскольку функция на интересующем множестве может оказаться разрывной.
Мы будем рассматривать задачу потребительского выбора маршаллианского типа и две из возможных стратегий понижения цен p(x), выбор которых определяется только дилером и в явной форме не учитывает его затраты на приобретение благ у производителя, а также обоснуем возможность использования для численного анализа указанных моделей метода штрафных функций с введённым выше видом функции штрафа.
Через Rn будем обозначать n-мерное евклидово пространство, а норму, если не оговорено противного, будем считать евклидовой.
Аналогично [43] мы введём термин «информированный покупатель», однако придадим ему несколько иной смысл: мы будем предполагать, что покупателю известна стратегия дилера по снижению цен на блага в зависимости от приобретаемого количества последнего, при этом нас не будет интересовать осведомлённость покупателя о затратах дилера на приобретение благ у производителя. В дальнейшем под словом «покупатель» (потребитель) будем понимать «информированный покупатель». Для простоты будем рассматривать случай с одним дилером, стратегии которого по снижению цен в зависимости от количества приобретаемых благ нам известны и являются однотипными. Разумеется, стратегии понижения цен для разных благ могут выбираться различными, однако это усложнит изложение, не приводя к принципиальным трудностям.
Будем опираться на устоявшиеся терминологию и обозначения, несколько изменив их вследствие вносимых предложений: набор благ (продуктов), х, - вектор-столбец х = {хх, х2, …, хп)Т, где Xj О, j = 1,п, - количество у-го блага, приобретаемого покупателем у дилера и измеряемого в «непрерывно изменяющихся» единицах (килограммах, литрах, метрах и т.п.); доход потребителя (капитал потребителя), М, - ограниченное количество денежных средств М 0 потребителя, которые он может использовать для приобретения благ; вектор цен благ, р, - вектор-строка р = {р\,рг, …,Рп) цен, устанавливаемых дилером на приобретаемые потребителем блага, где величина р.=р.(Х]), j = 1,n, (4.7) представляет собой цену единицы приобретаемого у-го продукта в количестве Xj и является невозрастающей по переменной xj функцией на некотором промежутке, смысл которого будет пояснён ниже; стоимость набора благ х, определяемая вектором цен р, S(x), - количество денежных средств потребителя, требуемых к оплате за весь приобретаемый набор благ х: S(x)=S(x,p(x)); (4.8) бюджетное ограничение - условие ограниченности стоимости приобретаемого набора благ капиталом потребителя, т.е. S(x) M; функция полезности, и = и{х), - функция, соответствующая отношению предпочтения потребителя, отражающая уровень (или степень) удовлетворения его потребностей приобретаемым набором благ х. Стандартным предположением относительно свойства функции полезности является её изотонность, то есть в данном случае и(х ) и(х"), если каждая координата вектора х не превосходит соответствующей координаты вектора х" [37-41]; поверхность безразличия - поверхность равноценных (имеющих одинаковую полезность для потребителя) наборов благ, задаваемая уравнением и(х) = с, с = const.
Для каждогоу -го блага, j = 1,п, может быть установлено минимальное хп
и максимальное хах количество, которое может быть приобретено у дилера, и сформировано множество допустимых значений вектора благ: G = \x = (xux2,...,xn)e[0;oof :Vj = u(x Xj хх). Задача потребительского выбора состоит в нахождении такого набора благ, который обеспечивает максимально возможное значение функции полезности при имеющемся доходе потребителя и заданном векторе цен. Поскольку в классической задаче потребительского выбора цены (4.7) считаются постоянными, формула (4.8) вычисления стоимости набора благ имеет вид:
Метод штрафных функций с выбором штрафа в виде функции расстояния
Для того, чтобы расчёты, производимые программой, дали верные результаты, кроме выполнения описанных правил, пользователю необходимо вводить данные (функции и параметры), удовлетворяющие указанным при описании соответствующего алгоритма условиям (см. Главы 1, 2).
Нарушение вышеописанных инструкций может привести к получению неверных результатов или зацикливанию алгоритма.
Некоторые из таких кратких указаний или комментариев выводятся во всплывающей подсказке при наведении курсора мыши на соответствующее поле для ввода значения или пункт (переключатель). В качестве примера на Рисунке 1 показана такая подсказка для пункта (переключателя) 2.3.
Подробное описание работы с программным комплексом пользователь может получить в окне «Справка» (см. Рисунок 2), открывающемся при нажатии соответствующей кнопки главного окна программы. Текст справки при необходимости может быть скопирован пользователем.
Краткая информация о программном комплексе может быть получена по нажатию кнопки «О программе» в соответствующем открывающемся при этом окне (см. Рисунок 3).
Для решения задачи проектирования пользователю необходимо ввести все необходимые для решения задачи данные в соответствующие поля и установить переключатели в области «Исходные данные» и нажать кнопку «Вычислить». Это запустит соответствующую расчётную программу, по завершении работы которой поля области «Результаты расчётов» будут содержать найденное программой решение.
Ход проведённого решения (промежуточные результаты по завершении каждой итерации алгоритма) можно просмотреть в файле output.txt, расположенном в той же папке, что и исполняемый файл программного комплекса Projection2D.exe и отдельных его компонент. В процессе изменения пользователем содержимого полей области «Исходные данные» программа выполняет предварительную проверку введённых в строку данных на корректность. В случае ввода пользователем недопустимого символа (например, пробела) пользователю может быть выведено окно с предупреждением.
При нажатии пользователем кнопки «Вычислить» программа считывает установленные положения переключателей, данные из всех заполненных полей, а в случае, если пользователем какое-либо из активных полей не было заполнено, принимает в качестве необходимого – значение по умолчанию (при этом весьма вероятно несоответствие значений по умолчанию введённым пользователем данных, влекущее за собой ошибку вычислений). Далее выполняется дополнительная проверка всех введённых данных и осуществляется их запись в специальном формате во вспомогательный текстовый файл input.txt, создаваемый в той же папке, что содержит исполняемый файл программного комплекса Projection2D.exe и его компонент.
После этого осуществляется запуск соответствующей расчётной программе-компоненту, выбираемой в соответствии с установленными пользователем пунктами (переключателями) групп «Метод (алгоритм минимизации)» и «Метрика» области «Исходные данные», и интерфейс ожидает завершения её работы.
Работа каждой расчётной программы-компонента начинается с открытия файла input.txt, считывания из него данных для расчётов и выполнения предварительных расчётов вспомогательных величин. После этого следует работа основного алгоритма проектирования, использующего на отдельных этапах алгоритмы решения вспомогательных задач (см. Главу 3), реализованные в виде отдельных модулей.
Основные численные данные, получаемые программой-компонентом в процессе её выполнения (исходные данные для расчётов, важные характеристики модели задачи, промежуточные результаты, получаемые на каждой итерации основного алгоритма, и найденное в итоге решение), выводятся по ходу расчётов в консоль и в текстовый файл output.txt, создаваемый в той же папке, что и исполняемые файлы программного комплекса Projection2D.exe и его компонент. По завершении работы консольной программы-компонента управление передаётся снова интерфейсу. Им осуществляется считывание полученного решения из файла output.txt и заполнение ими соответствующих полей области «Результаты вычислений».
После этого пользователь может продолжить работу в главном окне комплекса «Проектирование точки» и перейти к решению новой задачи, выполняя заново аналогичные описанным действия.
