Основы теории оптимизации (стр. 97 )

Для того, чтобы достичь этой цели, мы чередуем итерации Левенберга-Марквардта и предобусловленного L-BFGS алгоритма. В качестве предобуславливателя мы используем квадратичную модель, построенную на предыдущем шаге. В качестве целевой функции - F(x). Градиент F(x), необходимый для работы L-BFGS алгоритма, мы получаем одним из двух способов:

через вычисление произведения 2·f T·J. Этот способ не требует дополнительной информации (кроме вектора функции и Якобиана). через запрос градиента у пользователя. Этот способ имеет смысл использовать, если Якобиан разрежен и произведение 2·f T·J может быть вычислено более эффективно, чем через формирование матрицы J и умножение на вектор f.

Эта стратегия включается вызовом minlmsetacctype(state,2) и может быть использована вместе с любой схемой оптимизации, при которой доступны Якобиан или градиент (VJ, VGJ, FGH).

ALGLIB User Guide - Одномерная и многомерная оптимизация –

Метод активных множеств

ASA-алгоритм

Метод активных множеств (ASA) - это общее название семейства алгоритмов для решения задачи оптимизации с ограничениями вида gi (x)≥0. Название метода происходит от используемой классификации ограничений, в соответствии с которой они делятся на активные и неактивные в текущей точке. Ограничение неактивно, если gi (x) > 0. Если же gi (x)=0, то ограничение может быть как неактивным, так и активным (в зависимости от выбора множества активных ограничений).

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

Основным достоинством метода является простота его реализации для задачи с ограничениями вида ai  ≤ xi  ≤ bi . Активация ограничений состоит в "замораживании" компонент x, что позволяет использовать практически любой алгоритм оптимизации без ограничений. Итерации метода могут быть очень дешевыми, т. к. отсутствует необходимость строить сложные квадратичные модели функции и ограничений.

Реализация в пакете ALGLIB

В пакете ALGLIB реализована незначительная модификация алгоритма, описанного в 'A new active set algorithm for box constrained optimization' (William W. Hager and Hongchao Zhang). Этот алгоритм чередует итерации нелинейного метода сопряженных градиентов и метода проекции градиента. Первый алгоритм позволяет добиться хорошей сходимости после того, как найдено подходящее множество ограничений. Второй алгоритм используется для активации или деактивации ограничений и позволяет активировать за одну итерацию сразу несколько ограничений. Метод обладает глобальной сходимостью при условии, что grad(f) непрерывен по Липшицу на множестве L = { x : f(x) ≤ f(x0 )}. Одним из достоинств является сравнительно низкая стоимость итераций, умеренно отличающаяся от стоимости итераций метода сопряженных градиентов без ограничений.

Быстродействие

ASA против CG на задачах без ограничений

В этом эксперименте мы сравним стоимость итерации ASA со стоимостью итерации классического метода сопряженных градиентов. Стоимость итерации ASA складывается из двух составляющих: стоимости лежащего в основе метода сопряженных градиентов и накладных расходов, связанных с обработкой ограничений. Для того, чтобы выделить составляющую, связанную с собственно обработкой ограничений, мы решим с помощью обоих алгоритмов следующую задачу:

минимизируемая функция: f(x) = x0 4 + 2·x1 4 + ... + (n+1)·xn 4. стартовая точка: xs = [10, ..., 10]. ограничения: -100 ≤ xi  ≤ +100, т. е. в минимуме все ограничения неактивны. размерность задачи n: в диапазоне 10...100 с шагом 10. алгоритмы: CG и ASA

Для тестирования использовался компьютер с процессором Intel Core 2, тактовой частотой 2.4 GHz. По итогам тестирования были получены следующие результаты:

Четерехкратный прирост длительности итерации показывает, насколько дорого обходится обработка ограничений. Но действительно ли ASA в четыре раза медленнее CG? В худшем случае - да. Однако в нашем примере была выбрана очень простая функция f, стоимость вычисления градиента которой невелика в сравнении со стоимостью итерации любого из используемых методов. В практических задачах время, требуемое для вычисления градиента f, может на порядок превосходить время работы собственно алгоритма. На этом фоне накладные расходы, связанные с обработкой ограничений, могут оказаться незаметны, и быстродействие ASA будет практически равно быстродействию CG в аналогичной задаче, но без ограничений.

Список обозначений

Rп — п-мерное вещественное евклидово пространство.

{х1, ..., хп} — компоненты вектора х Rп.

|| • || — норма в Rп: ||х||2 = х21 + ... + х2п.

(•, •) — скалярное произведение в Rп: (х, у) = х1у1 + ... +хпуп

I — единичная матрица

Ат — матрица, транспонированная к А.

A+ — псевдообратная матрица к А.

А ≥ В — матрицы А и В симметричны и А — В неотрицательно опреде­лена

А > В — матрицы А и В симметричны и А—В положительно определена.

||A|| — норма матрицы А: ||А||=

ρ(А) — спектральный радиус матрицы А .

х ≥ у — все компоненты вектора х Rп не меньше соответствующих компонент вектора у Rп : хі ≥ уі, i = 1, ..., п.

Rп+ — неотрицательный ортант в Rп: Rп+ = { х Rп: х≥0}.

х+ — положительная часть вектора х Rп: (х+)і = max {0, хі}, i = 1, ... п.

—любая точка глобального минимума f (x) на Q: х Q,

— множество точек глобального минимума f (х) на Q: .

f(x), f'(x) — градиент скалярной функции f(x).

g(х), g'(x) — производная векторной функции g(x), матрица Якоби.

2f(x), f"(x)—матрица вторых производных, гессиан.

L'x(x, у), L''xx(x, у) — градиент и матрица вторых производных L(x, у) пo переменной х.

df(x) — субградиент выпуклой функции.

∂ε f(x) — ε-субградиенг выпуклой функции.

f ' (х; у) — производная функции f (x) в точке х по направлению у.

D(f) — область определения функции f(x).

Conv Q — выпуклая оболочка множества Q.

Q — внутренность множества Q.

— пустое множество.

PQ(x) — проекция точки х на множество Q .

ρ(х, Q) — расстояние от точки х до множества Q: ρ(х,Q )=

o(h(x)) — если g: Rп→Rm, h: Rп→Rs и ||g (x) ||/||h (x)|| →0 при ||х||→0.

O(h(x*)) — если g: Rп→Rm, h: Rп→RS и найдутся ε > 0, α такие, что ||g (x) ||≤ α || h (x)|| при || (x)||≤ε, то g (x) =О (h(x)).

o(uk) — если последовательности uk Rп, vk Rm, k = 1, 2,…, таковы, что || vk ||/|| uk || → 0 при k→∞, то vk = о(uk).

О(uk) — если для последовательностей uk Rn, vk Rm, k = 1, 2,…, найдутся α > 0, k0 такие, что || vk ||≤α|| uk || при k≥ k0 ,то vk = О(uk).

Мξ — математическое ожидание случайной величины ξ

М (ξ| х) — условное математическое ожидание случайной величины ξ, за­висящей от х, при фиксированном значении х.

— квантор общности: x Q — «для всех x Q».

Литература

1.Основная

1. Введение в методы оптимизации. — М.: Паука, 1977.

2. Бахвалов методы.—М.: Наука, 1973.

3. В а й н б е р г метод и метод монотонных опе­раторов в теории нелинейных уравнений —М.: Наука, 1972.

4. Кириллова оптимизации. — Минск: Б ГУ, 1975.

5. , Рубинов А М. Приближенные методы реше­ния экстремальных задач —Л.: ЛГУ, 1968.

6. Нелинейное программирование. Единый подход --М.: Сов. Радио, 1973.

7. Методы возможных направлений —М.: ИЛ, 1963.

8. Карманов программирование. — М.: Наука, 1975.

9. Кононюк математика. К.1. — К.: КМТ, 2009.

10.Кононюк математика. К.2. — К.: КМТ, 2009.

11.Кононюк математика. К.1, ч.1 — К.: Освіта України, 2010.

12.Кононюк математика. К.1, ч.2 — К.: Освіта України, 2010.

13.Кононюк математика. К.2, ч.1 — К.: Освіта України, 2011.

14.Кононюк математика. К.2, ч.2 — К.: Освіта України, 2011.

15.Кононюк математика. К.2, ч.3 — К.: Освіта

України, 2011.

16.Кононюк математика. К.3, ч.1 — К.: Освіта України, 2011.

17.Кононюк математика. К.3, ч.2 — К.: Освіта України, 2011.

18. М о и с е е в Н. Н., И в а н и л о в Ю. П., Meтоды оптимизации.—М.: Наука, 1978.

19. Ортега Дж., Итерационные методы решения нелинейных систем уравнений со многими неизвестными — М.: Мир, 1975.

20. Численные методы оптимизации. Единый подход — М: Мир, 1974.

21. Поляк в оптимизацию. —М.: Наука, 1983.

22. , Данилин методы в экс­тремальных задачах.— М.: Наука, 1975.

23. Растригин экстремального управления —М.: Наука, 1974.

24. С е а Ж. Оптимизация. Теория и алгоритмы.— М.: Мир, 1973

25. Дж. Методы поиска оптимума.—М.: Науки 1967.

26. Федоренко решение задач оптимального управления. — М.: Наука, 1978.

27. Мак-Кормик Дж. Нелинейное программиро­вание: методы последовательной безусловной минимизации.—М: Мир 1972.

28. Хи м м е л ь б л а у Д. Прикладное нелинейное программирование М.: Мир, 1975.

29. Численные методы условной оптимизации /Под ред. Ф. Гилла, У Мюр рея. — М.: Мир, 1977.

30. Э р р о у К. Дж., ГурвицЛ. УдзаваХ. Исследования по лпигП ному и нелинейному программированию. — М.: ИЛ, 1962.

2. Дополнительная

, Статистическое исследование одного алгоритма глобальной оптимизации. — Труды ФОРА, 2004. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. — М.: Высшая школа, 1986. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985. , Методы поиска глобального экстремума. — М.: Наука, Физматлит, 1991. Математическое программирование = Математическое программирование. — Изд-во физ.-мат. литературы, 2004. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576. , Математические основы кибернетики. — М.: Энергоатомиздат, 1972. , Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980. Расчет и оптимизация термоупругого состояния тел с учетом геометрической и физической нелинейности : Автореф. дис. на соиск. учен. степ. д-ра физ.-мат. наук : (01.02.04) / Казан. гос. ун-т им.— Казань, 1989. Математическое программирование = экспресс-курс. — 2006. — С. 171. — ISBN 985-475-186-4 Статистические методы поиска. — М.: 1968. Таха Введение в исследование операций = Operations Research: An Introduction. — 8 изд.. — М.: «Вильямс», 2007. — С. 912. — ISBN 0-13-032374-8 Никайдо Х. Выпуклые структуры и математическая экономика. —  М.: Мир, 1972 Кини Р. Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения.- М.: Радио и связь, 1981 Соболь И. М., Статников Р. Б. Выбор оптимальных параметров в задачах со многими критериями. —  М.: Наука, 1981 Подиновский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. —  М.: Наука, 1982 Морозов В. В., Сухарев А. Г., Федоров В. В. Исследование операций в задачах и упражнениях. —  М.: Высшая школа, 1986 Юдин Д. Б. Вычислительные методы теории принятия решений. —  М.: Наука, 1989 Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. —  М.: Наука, 1990 Штойер Р. Многокритериальная оптимизация. —  М.: Радио и связь, 1992 Батищев Д. И., Коган Д. И. Вычислительная сложность экстремальных задач переборного типа. — Изд. ННГУ, Н. Новгород, 1994 Коротченко А. Г., Тихонов В. А. Методические указания (сборник задач) по курсу «Модели и методы принятия решений» — Изд. ННГУ, Н. Новгород, 2000 Коротченко А. Г., Бобков А. Н. Принципы оптимальности в задачах принятия решений (методическая разработка) — Изд. ННГУ, Н. Новгород, 2002 Батищев Д. И. Задачи и методы векторной оптимизации. — Изд. ГГУ, Горький, 1979 Розен В. В. Цель - оптимальность - решение: Математические модели принятия оптимальных решений. —  М.: Радио и связь, 1982 Батищев Д. И. Методы оптимального проектирования. —  М.: Радио и связь, 1984

28. и др. Методы разработки интегрированных АСУ промышленными предприятиями. М.: Энергоатомиздат – 1983.
29. , , . Методы определения коэффициентов важности критериев “Автоматика и телемеханика”, №8, 1997, с3-35.
30. Таха, Введение в исследование операций – М.:Мир,2001, с354-370.
31. Р. Штойер. Многокритериальная оптимизация: теория, вычисления, приложения. М.:Наука, 1982, с14-29, 146-258.
32. Многокритериальная оптимизация. Математические аспекты. М.:Наука, 1989, с116-123.
33. , . Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982, с9-64.
34. . Элементы теории многокритериальной оптимизации. М.: Наука, 1983, с8-25.
35. , , . Эволюционно-генетический подход к решению задач невыпуклой оптимизации. /Межвузовский сборник научных трудов «Оптимизация и моделирование в автоматизированных системах», Воронеж, ВГТУ, 1998г, стр.20-28.
36. , . Оптимизация многоэкстремальных функций с помощью генетических алгоритмов. /Межвузовский сборник научных трудов «Высокие технологии в технике, медицине и образовании», Воронеж, ВГТУ, 1997г, стр.4-17.
37. . Популярно о генетических алгоритмах. Интернет-ресурс http://bspu. ab. ru./Docs/~saisa/ga/ga-pop. html.
38. . Обоснованно о генетических алгоритмах. Интернет-ресурс http://bspu. ab. ru/Docs/~saisa/ga/text/part1.html.
39. . Решение многокритериальных задач. Интернет-ресурс http://bspu. ab. ru/Docs/~saisa/ga/idea1.html.
40. Раздел «Математика\Optimization Toolbox». Интернет-ресурс http://www. matlab. ru/optimiz/index. asp.
41. Система СИМОП для автоматизации выбора рациональных решений в комплексах САПР и АСНИ. Интернет-ресурс. http://www. software. unn. ac. ru/mo_evm/research/symop. html
42. Интегрированный пакет многокритериальной оптимизации «МАЛТИ». Интернет-ресурс http://ksu. /emf/kafkiber. htm
43. Комплексный инженерный анализ - прочность, динамика, акустика. Интернет-ресурс http://osp. admin. tomsk. ru/ap/1998/02/31.htm
44. Программы семейства COSMOS – универсальный инструмент конечно-элементного анализа. Интернет-ресурс http://. ru/7/Info/cosmos_3.html

Научно-практическое издание

Основы теории оптимизации

Книга 2

Безусловная оптимизация

Авторская редакция

Подписано в печать 21.03.2011 г.

Формат 60x84/16.

Усл. печ. л. 16,5. Тираж 300 экз.

Издатель и изготовитель:

Издательство «Освита Украины»

04214, 3, к. 40

Свидетельство о внесении в Государственный реестр

издателей ДК № 000 от 01.01.2001 г.

Тел./; 237-5992

E-mail: *****@***net, www. rambook. ru

⨪