-1 -
ОГЛАВЛЕНИЕ
Введение
Основные обозначения
Глава 1о Метод-матрицы квази-Гессе в исследовании обобщенной . выпуклости дваэды дифференцируемых функций § I. Обобщения понятия выпуклости функции § 2* Локальная обобщенная выпуклость § 3. Характеристики первого и второго порядка различных . типов обобщенной выпуклости § 4. Критерии положительной полуопределенности и полоки-. тельной определенности матрицы квази-Гессе § 5, Достаточные условия локального минимума в нелинейном программировании
Глава II« Обобщенная выпуклость- невыпуклых квадратичных функций
§ I. Квази- и псевдовыпуклость квадратичных срункщш § 2. Критерии обобщенной выпуклости квадратичных функций . на конусах
§ 3. Достаточные условия локального минимума в квадратичном программировании
Глава III. Недифференцируемые квазивкпуклые функции и некоторые вопросы недифсоеренцируемой оптимизации § 1<, Некоторые свойства недхлфферекцируемых псевдовыпук-. лых санкций § 2. Обобщение понятия квазгщисареренцкруемости по . Пшеничному § Зо Направление наискорейшего спуска
Литература
2
9
10
10
17
25
32
48
52
52
60
65
72
75
81
87
31
2
Введение
Математическое программирование имеет дело с задачей оптимизации значений некоторой целевой функции при ограничениях типа равенств и неравенств.
Задача, в которой все фигурирующие при ее описании функции линейны, называется задачей линейного программирования. В противном случае имеет место задача нелинейного программирования. Начало математического программирования можно датировать 1939 годом. В этом году советским математиком Л .В.Канторовичем были созданы методы решения нового типа задач - задач линейного программирования. В дальнейшем теория линейного программирования получила широкое развитие в работах Дж.Данцига и многих других авторов как за рубежом, так и в СССР.
Разработка симплекс-метода и появление быстро-действующих вычислительных машин сделали линейное программирование важным инструментом решения многих проблем, возникающих в самых различных областях. Однако большинство реальных задач не может быть адекватно описано с помощью моделей линейного программирования из-за нелинейности целевой функции или некоторых ограничений. В последние два десятилетия достигли значительного прогресса в исследовании нелинейных задач.
Следующим этапом в развитии теории математического программирования явилась разработка теории выпуклого программирования. Центральным местом в этой теории является теорема Куна-Таккера, дающая необходимые и достаточные условия экстремума.
Потребности выпуклого и также невыпуклого программирования
- 3 -
оказали большое влияние на развитие теории выпуклых функций и выпуклых множеств, т.е. на развитие выпуклого анализа.
Уже в самом начале развития теории выпуклого программирования появились попытки обобщить понятие выпуклости функции, таким образом, чтобы хорошие свойства выпуклых функций сохранялись / Дэ Финетти, Фэнхел, Слейтер, Никайдо и др./. Исследование задач квазивыпуклого программирования стало более интенсивным в начале шестидесятых годов.
Большой вклад в изучение квазивыпуклых задач внесли К.Й. Эрроу, А.Д.Энтховен, Р.В.Котл, Й.А.Фэрланд, О.Л.Мангасарян, Б.Мартош, Ш.Шайбл, М.Авриел и в СССР Я.И.Заботин, А.И.Кораблев, Р.Ф.Хабибуллин, Е.Г.Гольштейн и др. Для недифференцируемых задач квазивыпуклого программирования важные результаты были получены в работах К.-П.Крузейкса и В.Е.Диверта.
Основной целью этих исследований явилось расширение класса выпуклых функций /или функционалов/ до класса таких функций /или функционалов/, для которого основные утверждения выпуклого программирования /напр, теорема Куна-Таккера/ сохраняются.
Одним из самых важных свойств выпуклых функций является то, что любое нижнее множество уровня данных функций является выпуклым множеством. Один класс обобщенных выпуклых функций, так называемых квазивыпуклых функций определен именно по этому свойству.
Хорошо известным свойством дифференцируемых выпуклых функций является достижение в каждой стационарной точке глобального минимума. Этим свойством обладают и псевдовыпуклые функции, класс которых шире класса дифференцируемых выпуклых функций.
С 1949, когда Дэ Финетти впервые ввёл понятие квазивыпуклости
- 4 -
функции, радом математиков были предприняты попытки обобщить в каком-либо смысле понятие выпуклости функции. В результате этих попыток в литературе можно найти более 20 различных классов обобщенных выпуклых функций, но, к сожалению, единых общепринятых наименований пока не возникло. В настоящей диссертации придерживаемся терминологии работы [82].
Общую задачу нелинейного программирования можно сформулировать в следующем виде:
минимизировать #СХ) при условиях С^СХ)>0, I
X е [>.
Здесь £сх;, 91Сх)| . . . ^^Сх) - определенные на Е^ функции, 0 -множество из Е^, X - вектор с компонентами Х^Хг,..., X*. . Задача заключается в нахождении переменных х*,хг,..., удовлетворяющих ограничениям и отвечающих при этом минимальному значению функции
Вектор хеР, удовлетворяющий всем ограничениям <3:(х;£.о ,
± - 4,ил. называют допустимым -решением, или допустимой точкой. Совокупность всех допустимых точек образует допустимую область о Точка х0, Для которой ^СХ) > ^х0) при всех допустимых решениях х, называется оптимальным решением.
В диссертации рассматриваются задачи минимизации квазквыпук-лых и обобщено-квазидифференцируемых функций многих переменных. Задачи квазивыпуклого программирования часто встречаются в различных отраслях техники, экономики и их исследование представляет теоретическое и прикладное значение, /см., например работы [зо, 31, 70, 82}./
- 5 -
Целью настоящей работы является: расширение класса выпуклых функций до класса таких функций, для которого справедливо ут-вервдение теоремы Куна-Таккера в локальном смысле; развитие новой характеристики гладких и негладких квазивыпуклых и псевдо-выпуклых функций; изучение обобщеио-квазидифференцируемых функций; устанавление необходимых и достаточных условий оптимальности решения для общей задачи нелинейного программирования.
В первой главе диссертационной работы исследуется обобщенная выпуклость дифференцируемых и двазды дифференцируемых функций. Свойства двазды дифференцируемых квазивыпуклих и псевдовыиуклых функций изучались многими авторами. Эти исследования группируются в основном вокруг трёх методов. Эти методы базируются пли на исследовании миноров "окаймленной" матрицы Гессе [31,34,53] или на исследовании квадратичной формы (#м(х)2,г) на подпространстве ег) =-оЗ [32,46,47,50,57,72] или на исследовании "расширенной" матрицы Гессе Н(Х;гсх)) =• {\х)+'гСх)$[х)(\х)т [32,35,57,68,80]. Сравнение упомянутых методов осуществляется в работах [47,50,54].
Эти исследования развиты автором в работа:-: [18,61]. Новизной этих исследований являются - с одной стороны - введение и изучение понятия обобщенной выпуклости в точке в локальном смысле и - с другой стороны - устанавление связи глезду локальной квази-зыцуклостью функции £(.х) в точке Хо £ Е*“ и локальной выпуклое-ТЬЮ модифицированной неявкой функции Нс£.1х0(^) в точке Цо&Е функция Не1чХо(.и) определяется формулой Нл%Хо1и):=г-С'?СХо)(с1)-^^) , где (^Чх^сИ) ^ о и неявная функция определена уравнением Т ^СХо) , где и. € Е"’** К 1и*,0чЛи.о)) к Х0 •
Первый параграф главы I носит вспомогательный характер. В нем
- 6 -
приводятся основные определения и известные факты, связанные с обобщенной выпуклостью функций, которые будут использоваться на протяжении всей работы.
В § 1о2 анализ глобальной обобщенной выпуклости функции осуществляется посредством исследования ее локальной обобщенной выпуклости в точках.
В § 1.3 устанавливается связь между локальной квазивыпуклостью, псевдовыпуклостыо и строгой псевдовыпуклостью функции £(Х) в точке х0 £ и локальной выпуклостью и строгой выпуклостью модифицированной неявной функции Н^хДи.) в точке 6 Е‘п'~4‘, где Си.0Ди*))=г Хв • Опираясь на эту связь определяется матрица квази-Гессе дважды дифференцируемой функции и с ее помощью характеризуются КЕазивыпуклостъ, псевдовыпуклость и строгая псевдовыпуклостъ функции, ста характеристика обобщенной выпуклости тлеет тесную аналогию с характеристикой выпуклости функции посредством ее матрицы Гессе. Эта аналогия является причиной того, что матрица Гессе Н^чХ#си.0) модифицированной неявной функции Н^ ^си.) в точке и.с , наигленозака как матрица квази-Гессе функции в точке х0 •
Так как квазквыпуклость, исевдовыпуклость и строгая псевдовк-пуклость тесно связаны с положительной полуопределенностыо и поло-^телыюй определенностью матрицы квазк-Гессе, поэтому в § 1.4 подробно изучаются различные критерии полоотельной полуопреде-лекности и определенности матрицы квази-Гессе.
Метод-матрицы квази-Гессе - кроме новых результатов - дает почти все уже известные результаты, поэтому этот метод можно считать единым подходом в исследовании обобщенной выпуклости дважды дифференцируемых функций.
- 7 -
В конце первой главы, в параграфе 1.5 опираясь на понятие локальной строгой псевдовыпуклости в точке и на его связь с положительной определенностью матрицы квази-Гессе функции, формулируются достаточные условия оптимального решения задачи нелинейного программирования.
Во второй главе применяются результаты, полученные в первой главе для частного случая квадратичных функций. В параграфе 2.1 опираясь на понятие локальной квазивыпуклости в точке, ослабляются некоторые условия уже известных теорем Б.Мартоша [б5,бб] , Й.А.Фэрланда [38,55} и Ш.Шайбла [77,78,79,вф •
В параграфе 2.2 используя элементарные свойства невыпуклых квазквыпуклых квадратичных функций, обобщается теорема Б.Мартоша [б5,6б] и формулируются критерии обобщенной выпуклости невыпуклых квадратичных функций на конусах.
В конце второй главы, в параграфе 2.3 формулируются достаточные условия локального минимума для задачи квадратичного программирования.
В третьей главе изучены некоторые вопросы недифференцируемой оптимизации.
В параграфе 3.1 исследуются недифференцируемые квазивыпуклые функции, причем обобщены некоторые результаты из первой главы. Так как решающую роль в исследованиях этой главы сыграла теорема о неявной функции, поэтому в данном параграфе эта теорема также обобщается. Результаты этого параграфа опубликованы в работе автора [60].
В параграфе 3.2 опираясь на результаты К.-П.Крузейкса [41 ,42, 43,44,45] понятие квазидифференцируемости функции, введено Б.Н.
- Київ+380960830922