Опуклий аналіз

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
3-вимірний опуклий многогранник. Опуклий аналіз включає не тільки вивчення опуклих підмножин евклідових просторів, але й вивчення опуклих функцій на абстрактних просторах.

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

Опуклі множини

[ред. | ред. код]

Опукла множина — це множина для деякого векторного простору X, така що для будь-яких і [1]

.

Опукла функція

[ред. | ред. код]

Опукла функція — це будь-яка розширена дійснозначна функція , яка задовольняє нерівності Єнсена, тобто, для будь-яких і будь-якого

[1].

Еквівалентно, опуклою функцією є будь-яка (розширена) дійснозначна функція, така що її надграфік

є опуклою множиною[1].

Опукле спряження

[ред. | ред. код]

Опукле спряження розширеної (не обов'язково опуклої) функції  — це функція , де X* — спряжений простір простору X[2], така що

Подвійне спряження

[ред. | ред. код]

Подвійне спряження функції  — це спряження спряження, що зазвичай записують як . Подвійне спряження корисне, коли потрібно показати, що виконується сильна або слабка двоїстість (за допомогою функції збурень[en]).

Для будь-кого нерівність випливає з нерівності Фенхеля. Для власної функції[en] f = f** тоді й лише тоді, коли f опукла і напівнеперервна знизу за теоремою Фенхеля — Моро[2][3].

Опукла мінімізація

[ред. | ред. код]

(Пряма) задача опуклого програмування, це задача вигляду

така що є опуклою функцією, а є опуклою множиною.

Двоїста задача

[ред. | ред. код]

Принцип двоїстості в оптимізації стверджує, що задачу оптимізації можна розглядати з двох точок зору як пряму задачу або двоїсту задачу.

Загалом, якщо дано двоїсту пару[en][4] відокремлюваних локально опуклих просторів та функцію , можна визначити пряму задачу як знаходження такого , що Іншими словами,  — це інфімум (точна нижня границя) функції .

Якщо є обмеження, їх можна вбудувати у функцію , якщо покласти , де  — індикаторна функція[en]. Нехай тепер (для іншої двоїстої пари ) — функція збурень[en], така що [5].

Двоїста задача для цієї функції збурення відносно вибраної задачі визначається як

де F* — опукле спряження за обома змінними функції F.

Розрив двоїстості — це різниця правої та лівої частин нерівності

де  — опукле спряження від обох змінних, а означає супремум (точна верхня границя)[6][7][5][6] .

Цей принцип збігається зі слабкою двоїстістю. Якщо обидві сторони рівні, кажуть, задача задовольняє умовам сильної двоїстості.

Існує багато умов для сильної двоїстості, такі як:

Двоїстість Лагранжа

[ред. | ред. код]

Для опуклої задачі мінімізації з обмеженнями-нерівностями

за умов для i = 1, …, m .

двоїстою задачею Лагранжа буде

за умов для i = 1, …, m ,

де цільова функція є двоїстою функцією Лагранжа, визначеною так:

Примітки

[ред. | ред. код]
  1. а б в Rockafellar, 1997.
  2. а б Zălinescu, 2002, с. 75–79.
  3. Borwein, Lewis, 2006, с. 76–77.
  4. Двоїста пара — це трійка , де  — векторний простір над полем ,  — множина всіх лінійних відображень , а третій елемент — білінійна форма .
  5. а б Boţ, Wanka, Grad, 2009.
  6. а б Csetnek, 2010.
  7. Zălinescu, 2002, с. 106–113.
  8. Borwein, Lewis, 2006.
  9. Boyd, Vandenberghe, 2004.

Література

[ред. | ред. код]
  • Осипенко К. Ю. Оптимизация. Ч. 1. Выпуклый анализ (консп. лекций). М.: МГУ. 57 с.
  • Осипенко К. Ю. Выпуклый анализ (программа курса и консп. лекций). М.: МГУ. 68 с.
  • Петров Н. Н. Выпуклый анализ (консп. лекций). Ижевск: УдмГУ, 2009. 160 с.
  • Жадан В. Г. Методы оптимизации. Часть I. Введение в выпуклый анализ и теорию оптимизации: учеб. пос. для студ. вузов по направл. … «Прикладные математика и физика». Москва : МФТИ, 2014. ISBN 978-5-7417-0514-8. (Ч. I). 271 с. Выпуск 300 шт.
  • Элементы выпуклого и сильно выпуклого анализа: учебное пособие для студентов высших учебных заведений, обучающихся по направлению «Прикладные математика и физика» и смежным направлениям и специальностям / Е. С. Половинкин, М. В. Балашов. — 2-е изд., испр. и доп. — М. : Физматлит, 2007. — 438 с.; 22 см — (Физтеховский учебник).; ISBN 978-5-9221-0896-6
  • Протасов В. Ю. Выпуклый анализ (консп. лекций. Мехмат МГУ, экономич. поток, 2009 г.). М.: МГУ.
  • Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2. — Springer, 2006. — ISBN 978-0-387-29570-1.
  • Stephen Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge University Press, 2004. — ISBN 978-0-521-83378-3.
  • R. Tyrrell Rockafellar. Convex Analysis = 1970. — Princeton, NJ : Princeton University Press, 1997. — ISBN 978-0-691-01586-6.
  • Radu Ioan Boţ, Gert Wanka, Sorin-Mihai Grad. Duality in Vector Optimization. — Springer, 2009. — ISBN 978-3-642-02885-4.
  • Constantin Zălinescu. Convex analysis in general vector spaces. — River Edge, NJ : World Scientific Publishing Co., Inc, 2002. — С. 106–113. — ISBN 981-238-067-1.
  • Ernö Robert Csetnek. Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. — Logos Verlag Berlin GmbH, 2010. — ISBN 978-3-8325-2503-3.
  • Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — 2. — Springer, 2006. — ISBN 978-0-387-29570-1.
  • Hiriart-Urruty J.-B., Lemaréchal C. Fundamentals of convex analysis. — Berlin : Springer-Verlag, 2001. — ISBN 978-3-540-42205-1.
  • Ivan Singer. Abstract convex analysis. — New York : John Wiley & Sons, Inc, 1997. — С. xxii+491. — (Canadian Mathematical Society series of monographs and advanced texts) — ISBN 0-471-16015-6.
  • Stoer J., Witzgall C. Convexity and optimization in finite dimensions. — Berlin : Springer, 1970. — Т. 1. — ISBN 978-0-387-04835-2.
  • Kusraev A.G., Kutateladze S.S. Subdifferentials: Theory and Applications. — Dordrecht : Kluwer Academic Publishers, 1995. — ISBN 978-94-011-0265-0.
  • Кусраев А. Г., Кутателадзе С. С. Субдифференциалы. Теория и приложения. Ч. 2. — 2-е, перераб. — Новосибирск : Изд-во Ин-та математики, 2003. — ISBN 5–86134–116–8.