К теории и методам решения задач квазивыпуклого программирования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

Основные обозначении

Глава I» Метод-матрицы квази-Гессе в исследовании обобщенной .выпуклости дважды дифференцируемых функций

§ I» Обобщения понятия выпуклости функции

§ 2» Локальная обобщенная выпуклость

§ 3. Характеристики первого и второго порядка различных типов обобщенной выпуклости

§ 4. Критерии положительной полуопределенности и полояи тельной определенности матрицы квази-Гессе

§ 5. Достаточные условия локального минимума в нелинейном программировании

Глава II. Обобщенная выпуклость- невыпуклых квадратичных функций

§ I. Квази- и псевдовыпуклость квадратичных функций

§ 2. Критерии обобщенной выпуклости квадратичных функции на конусах

§ 3. Достаточные условия локального минимума в квадратичном программировании

Глава III. Недифференцируемые квазивыпуклые функции и некоторые вопросы недифференцируемой оптимизации

§ 10 некоторые свойства недифференцируемых псевдовыпук лых функций

§ 2. Обобщение понятия квазкдифференцируемости по Пшеничному

§ 30 Направление наискорейшего спуска

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

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

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

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

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

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

Большой вклад в изучение, квазивыпуклых задач внесли К.Й. Эрроу, А.Д.Энтховен, Р.В.Котл, Й.А.Фэрланд, О.Л.Мангасарян, Б.Мартош, Ш.Шайбл, М.Авриел и в СССР Я.И.Заботин, А.И.Кораблев, Р.Ф.Хабибуллин, Е.Г.Голынтейн и др. Для недифференцируемых задач квазивыпуклого программирования важные результаты были получены в работах Ж.-П.Крузейкса и В.Е.Диверта.

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

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

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

Общую задачу нелинейного программирования можно сформулировать в следующем виде: минимизировать £сх) при условиях ^(.Х)>0, ¿=17^.

Хе О.

Здесь ^Сх;, . . . - определенные на Е^ функции, 0 множество из Е*", X - вектор с компонентами х^х^,., Хк. . Задача заключается в нахождении переменных х4,хг »•• ч удовлетворяющих ограничениям и отвечающих при этом минимальному значению функции

Вектор хеР, удовлетворяющий всем ограничениям ^¿Сх;> о , <■ - называют допустимым решением, или допустимой точкой. Совокупность всех допустимых точек образует допустимую область» Точка хв , для которой ^(.х) > при всех допустимых решениях х, называется оптимальным -решением.

В диссертации рассматриваются задачи минимизации квазивыпуклых и обобщено-квазидифференцируемых функций многих переменных. Задачи квазивыпуклого программирования часто встречаются в различных отраслях техники, экономики и их исследование представляет теоретическое и прикладное значение, /см., например работы [ЗО, 31, 70, 82]./

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

В первой главе диссертационной работы исследуется обобщенная выпуклость дифференцируемых и двадцы дифференцируемых функции» Свойства дважды джиоеренцируемых квазивыпуклых и псевдовынуклых фунщий изучались многими авторами. Эти исследования группируются в основном вокруг трёх методов. Эти методы базируются или на исследовании миноров "окаймленной" матрицы Гессе £31,34,53] или на исследовании квадратичной формы (#"(х)н,2:) на подпространстве \г еЕ*"-* (■£'(*),[32,46,47,50,57,72] или на исследовании "расширенной" матрицы Гессе НСХ;гсхЛ =• + ¡32,35,57,68,80]. Сравнение упомянутых методов осуществляется в работах [47,50,54].

Эти исследования развиты автором в работах [18,61]. Новизной этих исследований являются - с одной стороны - введение и изучение понятия обобщенной выпуклости в точке в локальном смысле и - с другой стороны - устанавление связи между локальной квази-выцуклостыо функции £(.х) в точке Х0 £ Е*~ и локальной выпуклостью модифицированной неявной функции КЛ ХоС и.) в точке и.о£ \ дункция И^х*^) определяется формулой Н^^и^г-^'схо) ,<*.)• и.) , где О и неявная функция Али.) определена уравнением ^см^^аио) - £(.х®) , где и. 6 Е*"* и « х<» •

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

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

В § 1.3 устанавливается связь между локальной квазивыпуклостью, псевдовыпуклостью и строгой псевдовыпуклостью функции 4?Сх) в точке х0 £ Е*1" и локальной выпуклостью и строгой выпуклостью модифицированной неявной функции Н^ди.) в точке & ЕГ1г~"1~, где Хв • Опираясь на эту связь определяется матрица квази-Гессе дважды дифференцируемой функции и с ее помощью характеризуются квазивыпуклость, псевдовыпуклость и строгая псевдовыпуклость функции. Зта характеристика обобщенной выпуклости тлеет тесную аналогию с характеристикой выпуклости функции посредством ее матрицы Гессе. Зта аналогия является причиной того, что матрица Гессе модифицированной неявной функции НЛХоол) в точке и0 , наименована как матрица квази-Гессе функции {т в точке х0 .

Так как квазивыпуклость, псевдовыпуклость и строгая псевдовыпуклость тесно связаны с положительной полуопределенностью и положительной определенностью матрицы квази-Гессе, поэтому в § 1.4 подробно изучаются различные критерии положительной полуопределенности и определенности матрицы квази-Гессе.

Метод-матрицы квази-Гессе - кроме новых результатов - дает почти все уже известные результаты, поэтому этот метод можно считать единым подходом в исследовании обобщенной выпуклости дважды дифференцируемых функций.

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

Во второй главе применяются результаты, полученные в первой главе для частного случая квадратичных функций. В параграфе 2.1 опираясь на понятие локальной квазивыпуклости в точке, ослабляются некоторые условия уже известных теорем Б.Мартоша [65,66] , Й.А.Фэрланда [38,55] и Ш.Шайбла [77,78,79,80] 0

В параграфе 2.2 используя элементарные свойства невыпуклых квазивыпуклых квадратичных функций, обобщается теорема Б.Мартоша [б5,бб] и формулируются критерии обобщенной выпуклости невыпуклых квадратичных функций на конусах.

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

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

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

В параграфе 3.2 опираясь на результаты Ж.-П.Крузейкса [41,42, 43,44,45] понятие квазидифференцируемости функции, введено Б.Н.

Пшеничным [24} обобщается и определяется псевдо-субдиййетзенциал квазидифференцируемой функции, при помощи которого описывается необходимое условие локального минимума для квазидифференциру-емых функций.

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

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

В заключении автор считает своим долгом выразить глубокую благодарность своему научному руководителю профессору АСАФУ ДАШДАМИРОВИЧУ ИСКЕНДЕРОВУ, постоянное внимание, непрерывная поддержка и ценные замечания которого способствовали улучшению настоящей работы.

Основные обозначения

Теоремы, леммы и определения нумеруются тремя числами: первое из них - номер главы, второе - номер параграфа, а третье - порядковый номер самой теоремы, леммы, определения в параграфе. Формулы нумеруются двумя числами: первое из них - номер параграфа, второе - номер формулы в параграфе. Если ссылка производится на формулу из другой главы, то к ней слева добавляется еще один индекс, указывающий номер главы.

Е*" - евклидово к.-мерное пространство;

X €• Е1*" - вектор X является элементом пространства Е^ и представляет собой вектор-столбец;

- единичный <--й орт, -с-я координата которого равна единице, остальные координаты - нули;

Хт - транспонированный вектор;

Е>т - транспонированная матрица;

1X11 - евклидова норма вектора х ;

Х,Ч) - скалярное произведение векторов X и ^ ;

X С Е^- подмножество пространства Ек;

X - замыкание множества X ; исЬ X - совокупность внутренних точек множества X ; тг X - относительная внутренность множества X ; функция, определена на некотором подмножестве X пространства Е"4 ; х) - к.-мерный вектор, градиент функции £(х/ ; - квадратная матрица порядкам, матрица Гессе функции ^Х) о

1. БАЗАРА М., ШЕТТИ К. Нелинейное программирование.-М.: Мир, 1982.

2. ВАСИЛЬЕВ Ф.П. Численные методы решения экстремальных задач.- М.: Наука, 1980.

3. ВЕРТГЕЙМ Б.А., РУБИНШТЕЙН Г.Ш. К определению квазивыпуклых функций.- Сб.: Матем.Программирование, М.: Наука, 1966, с. 121-134.

4. ВЛАДИМИРОВ A.A., НЕСТЕРОВ Ю.Е., ЧЕКАНОВ Ю.Н. О равномерно квазивыпуклых функционалах.- Вестник Московск, ун.-та. Сер. вычислит, матем. и кибернетика, 1978, № 4,с. 65-70.

5. ВОЕВОДИН В.В. Линейная алгебра.- М.: Наука, 1980.

6. ГОЛЬШТЕЙН Е.Г. Теория двойственности в математическом программировании и ее приложения.- М.: Наука, 1971.

7. ДЕМЬЯНОВ В.Ф., ВАСИЛЬЕВ Л.В. Недифференцируемая оптимизация.- М.: Наука, 1981.

8. ДЕМЬЯНОВ В.Ф., ПОЛЯКОВА Л.Н. Условия минимума квази-дифференцируемой функции, на квазидифференцируемом множестве.- IBM и МФ, 1980, т. 20, № 4, с. 894-856.

9. ДЕМЬЯНОВ В.Ф., РУБИНОВ A.M. О квазидифференцируемых функционалах.- ДАН СССР, 1980, т. 250, № I, с. 21-25.

10. ЕВТУШЕНКО Ю.Г. Методы экстремальных задач и их применение в системах оптимизации.- М.: Наука, 1982.

11. ЗАБОТИН Я.И., САВИЦКАЯ Т.И. О свойствах квазивогнутых функций.- Сб.: Применение методов вычислительной математики и ЭВМ в технико-экономических расчетах, Казань, Изд-во КГУ, 1970, с. 137-143.

12. ЗАБОТИН Я.И., КОРАБЛЕВ А.И., ХАБИБУЛЛИН Р.Ф. О минимизации квазивыпуклых функционалов.- Изв.вузов.Математика, 1972,10, с. 27-33.

13. ЗАБОТИН Я.И., КОРАБЛЕВ А.И. Псевдовыпуклые функционалы и их экстремальные свойства.- Изв.вузов.Математика, 1974, № 4, с. 27-31.

14. ЗАБОТИН Я.И. Эквивалентные определения квазивыпуклости.-Исследования по прикладной математике, Вып.2., Изд-во КГУ, 1974, с. 43-56.

15. ЗАНИЗИМ У. Нелинейное программирование. Единый подход.-М.: Сов. радио, 1973.

16. КАРМАНОВ В.Г. Математическое программирование.- М.: Наука, 1980.

17. КОМЛОШИ Ш. Исследование обобщенной выпуклости квадратичных функций.- Труды ун-та им. Януса Паннониуса, Вып. 6., 1983, с. 1-49./на венгерском языке/.

18. КОМЛОШИ Ш. Некоторые дополнения к теории квазивыпуклых функций.- Журнал прикладной математики /Венгрия/, 1984, т.10, № 1-2, под редакцией. /На венгерском языке./

19. КОМЛОШИ Ш. Обобщенная выпуклость невыпуклых квадратичных функций.- Изв.вузов.Математика, принята к печати.

20. КОМЛОШИ Ш. Об одном возможном обобщении квазидифференци-руемости функции.- Деп. в АзНИИНТИ, №

21. КОРАБЛЕВ А.И. Некоторые классы псевдовыпуклых функционалов.- Исследования по прикладной математике, Вып. 2.,Казань,Изд-во КРУ, 1974, с. 63-71.

22. ЛЮСТЕРНИК Л.А., СОБОЛЕВ В.И. Элементы функционального анализа,- М.: Наука, 1965.

23. НИКАЙДО X. Выпуклые структуры и математическая экономика.-М.: Мир, 1972.

24. ПШЕНИЧНЫЙ Б.Н. Необходимые условия экстремума.- М.: Наука, Т969.

25. ПШЕНИЧНЫЙ Б.Н. Выпуклый анализ и экстремальные задачи.-М.: Наука, 1980.

26. РОКАФЕЛЛАР Р. Выпуклый анализ.- М.: Мир, 1973.

27. РАШЕВСКИЙ П.К. Риманова геометрия и тензорный анализ.-М.: Наука, 1967.

28. РУДИН У. Основы математического анализа.- М.: Мир, 1966.

29. ШОР Н.З. О классе почти-дифференцируемых функций и одном методе минимизации функций этого класса,- Кибернетика, 1972, № 4, с 65-70.

30. ЛЭСДОН Л.С. Оптимизация больших систем.- М.: Наука,1975.

31. ARROW K.J., ENTHOVEIî A.D. Quasi-concave programming.-Econometrica 29 /1961/ 778-800.

32. AVRIEL M. r-convex functions.- Mathematical Programming2 /1972/ 309-323.

33. AVRIEL M. Nonlinear programming: analysis and methods.-Prentice Hall, Englewood Cliffs, NJ, 1976.

34. AVRIEL M., SCHAIBLE S. Second order characterization of pseudoconvex functions.- Mathematical Programming 14 /1978/ 170-185.

35. AVRIEL M., ZANG I. Generalized convex functions with applications to nonlinear programming.- in: Mathematical programs for activity analysis, Ed.: P.van Moeseke /North Holland,Amsterdam, 1974/ 23-33.

36. CLARKE P.M. A new approach to Lagrange multipliers.-Mathematics of Operations Research 2 /1976/ 165-174.

37. CLARKE P.M. Generalized gradients and applications.-Transactions of the American Mathematical Society 205 /1975/ 247-262.

38. COTTLE R.W., FERLA1TD J.A. Matrix-Theoretic Criteria for the Quasi-Convexity and Pseudo-Convexity of Quadratic Functions.- Linear Algebra and its Applications 5 /1972/ 123-136.

39. COTTLE R.W., FERLAIiD J.A. On pseudo-convex functions of non-negative variables.- Mathematical Programming 1 /1971/ 95-101.

40. COTTLE R.W., On the convexity of quadratic forms over convex sets.- Operations Research 15/1967/ 170-172.

41. CROUZEIX J.-P. Aboute Differentiability of Order One of Quasiconvex Functions on Journal of Opt.Theory and Appl. 36 /1982/ 367-385.

42. CROUZEIX J.-P. Conditions for convexity df quasiconvex functions.- Mathematics of Operations Research 5 /1980/ 120-125.

43. CROUZEIX J.-P. Continuity and differentiability propertieséof quasiconvex functions on Rn.- in: ^82^ 109-131.

44. CROUZEIX J.-P. Sur l'existence de la derivee des fonctions quasiconvexes.- Seminare analyse numerique et optimisation, Université de Clermont II /Novembre 1979/.

45. CROUZEIX J.-P. On second order conditions for quasiconvexi-ty.-Mathematical Programming 18 /1980/ 349-352.

46. CROUZEIX J.-P., PERLAND J.A. Criteria for quasiconvexity and pseudoconvexity: relationships and comparisons.-Mathematical Programming 23 /1982/ 193-205.

47. DIEWERT W.E.,AVRIEL M.,ZAÎTG I. Nine kinds of quasiconcavity and concavity.- Discussion Paper 77-91, Department of Economics University of British Columbia, 1977.

48. FENCHEL W. Convex Cones,Sets and Functions.- Mimeo, Princeton University, Princeton, N.J. /1953/.

49. FERLAND J.A. On the maximum of a quasi-convex quadraticfuncti on on a polyhedral convex set.-SIAM J. Appl. Math. 29 /1975/ 409-415.

50. FERLAND J.A. Maximal domains of quasi-convexity and pseudo-convexity for quadratic functions.- Mathematical Programming 3 /1972/ 178-192.4 • / . /

51. De FINETTI B. Sulle Stratificazioni Convesse.- Ann.Math. Pura Appl. 30 /1949/ 173-183.

52. GEREEIOSER L. On a close relation between quasi-convex and convex functions and related investigations.- Math. Operationsforschung und Statistik 4 /1973/ 201-211.

53. HIRIART-URRUTY J.B. Hew concepts in nondifferentiable programming.- Journees d*analyse non convexe, Universite de Pau /France/, 1977.

54. KERI G. An examination of non-negativity and quasiconvexi-ty conditions of quadratic forms on the nonnegative or-thant.- Studia Sci.Math.Hungarica 7 /1972/ 11-20.

55. KOMLOSI S. Some properties of nondifferentiable pseudo-convex functions.- Mathematical Programming 26 /1983/ 232-237.

56. MANGASARIAN O.L. Pseudo-convex functions.- SIAM Journal on Control 3 /1965/ 281-290.

57. MANGASARIAN O.L. Nonlinear programming.- New York: McGraw-Hill, 1969.

58. MARTOS B. Quadratic programming with a quasiconvex objective functions.- Operations Research 19 /1971/ 87-97.

59. MARTOS B. Subdefinite Matrices and Quadratic Forms.-SIAM J.Appl.Math. 17 /1969/ 1215-1223.

60. MARTOS B. Nonlinear programming: theory and methods.-Budapest: Akademiai Kiado, 1975.

61. MER3AU P.,PAQUET J.G. Second order conditions for pseudo-convex functions.- SIAM J. Appl. Math. 27 /1974/131-137.

62. MIFFLIN R. Semismooth and semiconvex functions in optimization.- SIAM Journal on Control and Optimization 15 /1977/ 959-972.

63. NEWMAN R. Some Properties of Concave Functions.- Journal of Economic Theory 1 /1969/ 291-314.

64. PONSTEIN J. Seven kinds of convexity.- SIAM Review 9 /1967/ 115-119.

65. RAPCSAK T. A SUMT-modszer alkalmazasa nem konvex programo-zasi feladatok eseten.- Alk.Mat .Lapok /Budapest/ 2 /1976/ 427-437.

66. RAPCSÀK T. Az optimalitâs masodrendü feltételeirol.- Alk. Mat.Lapok /Budapest/ 4 /1978/ 109-116.4 4

67. ROCKAPELLAR R.T. Generalized directional derivatives and subgradients of nonconvex functions.- Canadien Journal of Mathematics 32 /1980/ 257-280.

68. ROCKAPELLAR R.T. Clarke's tangent cone and the boundaries4 »of closed sets in R11.- Nonlinear Analysis 3/1979/ 145-154.

69. ROCKAPELLAR R.T. Directionally Lipschitzian functions and subdifferential calculus.- Proceedings of the London Mathematical Society 39 /1979/ 331-355.

70. SCHAIBLE S. Generalized convexity of quadratic functions.-in: 82. 183-199.

71. SCHAIBLE S. Quasi-convex optimization in general real linear spaces.- Zeitschrift für Operations Research 161972/ 205-213.*

72. SCHAIBLE S. Beitrüge zur Quasiconvexen Programmierung.-Ph.D.Dissertation, Universität Köln, 1971.

73. SCHAIBLE S. Second order characterization of pseudoconvex quadratic functions.- Journal of Optimization Theory and Applications 21 /1977/ 15-26.

74. SCHAIBLE S. Quasi-concave,strictly quasi-concave functions.- in: Operations Research Verfahren, eds.: R.Henn, H.P.Künzi, H.Schubert /1972/ 308-316.4 4 4 »

75. SCHAIBLE S., ZIEBIBA W.T. /Eds./ Generalized concavity in optimization and economics.- New York: Academic Press, 1981.

76. TAMMER K. Notwendige und hinreichende Bedingungen für /strenge/ Konvexität»Pseudukonvexität und /strenge/Quasikonvexität einer Quadratischen Punktion bezüglicheiner konvexen Menge.- Aplikace Mathematiky 21 /1976/ 97-110.* *

77. TUY H. Sur les inequalites lineaires.- Colloquium Mathematicum 13 /1964/ 107-123.

78. KARAMARDIAN S. Duality in Mathematical Programming.0 é 4 4J.Math. Anal. Appl. 20 /1967/ 344-358.