Хk - значение вектора управляемых параметров на k-м шаге,
h -
шаг,g(Xk) - направление поиска.
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Лекция 4
Содержание
- 1. Лекция 4
- 2. Классификация методов математического программирования
- 3. В САПР основными методами оптимизации являются поисковые методы.
- 4. Поисковые методы основаны на пошаговом изменении управляемых параметров
- 5. В большинстве методов приращение вектора управляемых параметров
- 6. Следовательно, если выполняются условия сходимости, то реализуется пошаговое (итерационное) приближение к экстремуму.
- 7. Методы оптимизации классифицируют по ряду признаков:
- 8. В зависимости от числа управляемых параметров различают
- 9. Различают методы условной и безусловной оптимизации по
- 10. В зависимости от числа экстремумов различают задачи
- 11. Методы нескольких порядков различают по использованию при
- 12. Методы первого порядка называют также градиентными, поскольку
- 13. Конкретные методы определяются следующими факторами:1) способом вычисления
- 14. Шаг может быть постоянным или выбираться исходя
- 15. Правило окончания поиска: если на протяжении r
- 16. Необходимые условия экстремума
- 17. В задачах безусловной оптимизации необходимые условия представляют собой равенство нулю градиента целевой функции
- 18. Базовая (общая) задача оптимизации ставится как задача
- 19. В общей задаче математического программирования необходимые условия
- 20. Абстрактная формулировка условий имеет простой геометрический смысл
- 21. Рассмотрим случай с ограничениями только типа неравенств.Если
- 22. Наоборот, если точка не является экстремальной, то
- 23. Методы поиска условных экстремумов
- 24. Широко известен метод множителей Лагранжа, ориентированный на
- 25. Суть метода заключается в преобразовании задачи условной
- 26. Необходимые условия экстремума функции
- 27. Основная идея методов штрафных функций — преобразование
- 28. Среди методов штрафных функций различают методы внутренней
- 29. Ситуация появления барьера у целевой функции Ф(х)
- 30. Примеры штрафных функций:для метода внутренней точки при
- 31. Чем больше коэффициент r, тем точнее решение
- 32. Основной вариант метода проекции градиента ориентирован на задачи математического программирования c ограничениями типа равенств.
- 33. Поиск при выполнении ограничений осуществляется в подпространстве
- 34. Поиск минимума начинают со спуска из исходной
- 35. Идею метода поясним для случая поиска в двумерном пространстве при одном ограничении ψ(X) = 0.
- 36. На рисунке это ограничение представлено жирной линией,
- 37. Рассмотрим получение аналитических выражений для направлений спуска и движения вдоль гиперповерхности ограничений.
- 38. Спуск Необходимо из текущей точки поиска В
- 39. Используем метод множителей Лагранжа, обозначая А-В=U и
- 40. Движение вдоль гиперповерхности ограничений Шаг в гиперплоскости
- 41. Уменьшение целевой функции при переходе из точки
- 42. где вариация S осуществляется в пределах гиперплоскости
- 43. Для решенияиспользуем метод множителей Лагранжа.где λ и
- 44. Таким образом, матрица представляет собой проектирующую матрицу,
- 45. Частным случаем применения метода проекции градиента являются
- 46. В качестве ограничений задачи в исходной постановке
- 47. Спасибо за внимание!
- 48. Скачать презентанцию
Классификация методов математического программирования
Слайды и текст этой презентации
Слайд 5В большинстве методов приращение
вектора управляемых параметров вычисляется по формуле
g(Xk) - направление поиска.
Слайд 6Следовательно, если выполняются условия сходимости, то реализуется пошаговое (итерационное) приближение
к экстремуму.
Слайд 8В зависимости от числа управляемых параметров различают методы одномерной (управляемый
параметр единственный) и многомерной (размер вектора X не менее двух)
оптимизации.Реальные задачи в САПР многомерны,
методы одномерной оптимизации играют вспомогательную роль на отдельных этапах многомерного поиска.
Слайд 9Различают методы условной и безусловной оптимизации по наличию или отсутствию
ограничений.
Для реальных задач характерно наличие ограничений.
Однако задачи условной оптимизации
с помощью специальных методов могут быть сведены к задачам без ограничений (к безусловной оптимизации).
Слайд 10В зависимости от числа экстремумов различают задачи одно- и многоэкстремальные.
Локальный метод ориентирован на определение какого-либо локального экстремума.
Метод глобального
поиска – метод, результатом которого является глобальный экстремум. Удовлетворительные по вычислительной эффективности методы глобального поиска для общего случая отсутствуют и потому на практике в САПР используют методы поиска локальных экстремумов.
Слайд 11Методы нескольких порядков различают по использованию при поиске производных целевой
функции по управляемым параметрам.
Если производные не используются, то имеет
место метод нулевого порядка, если используются первые или вторые производные, то соответственно метод первого или второго порядка. 
Слайд 12Методы первого порядка называют также градиентными,
поскольку вектор первых производных
F(X) по N есть градиент целевой функции
Слайд 13Конкретные методы определяются следующими факторами:
1) способом вычисления направления поиска g(Xk)
в формуле
;2) способом выбора шага h;
3) способом определения окончания поиска.
Определяющим фактором является первый.
Слайд 14Шаг может быть постоянным или выбираться исходя из одномерной оптимизации
— поиска минимума целевой функции в выбранном направлении g(Xk).
В последнем
случае шаг будем называть оптимальным. 
Слайд 15Правило окончания поиска:
если на протяжении r подряд идущих шагов
траектория поиска остается в малой
ε-окрестности текущей точки поиска Xk,
то поиск следует прекратить.Условие окончания поиска :
Слайд 17В задачах безусловной оптимизации необходимые условия представляют собой равенство нулю
градиента целевой функции
Слайд 18Базовая (общая) задача оптимизации ставится как задача математического программирования:
где
F(X) — целевая функция, X — вектор управляемых (проектных) параметров,
φ(X) и ψ(X) — функции-ограничения,Dx —допустимая область в пространстве управляемых параметров.
Слайд 19В общей задаче математического программирования необходимые условия экстремума (условия Куна-Таккера)
формулируются:
для того, чтобы точка Q была экстремальной точкой выпуклой
задачи математического программирования (ЗМП), необходимо наличие неотрицательных коэффициентов ui, таких, чтои при этом соблюдались ограничения задачи, а также выполнялось условие
где m — число ограничений типа неравенств, L— то же равенств, коэффициенты aj>0.
Слайд 21Рассмотрим случай с ограничениями только типа неравенств.
Если максимум находится внутри
допустимой области R, то, выбирая все ui=0, добиваемся выполнения
если же точка максимума Q лежит на границе области R, то, как видно из левой части рисунка, эту точку всегда соответствующим подбором неотрицательных ui можно поместить внутрь оболочки, натянутой на градиенты целевой функции F(X) и
функций-ограничений φi(X).
Слайд 22Наоборот, если точка не является экстремальной, то условие
нельзя выполнить при любом выборе
положительных коэффициентов ui (см. правую часть рисунка, где рассматриваемая точка N лежит вне выпуклой оболочки, натянутой на градиенты).
Учет ограничений типа равенств очевиден, если добавляется сумма
Слайд 24Широко известен метод множителей Лагранжа, ориентированный на поиск экстремума при
наличии ограничений типа равенств
ψ(X) = 0,
т.е. на решение
задачи где
Слайд 25Суть метода заключается в преобразовании
задачи условной оптимизации в задачу
безусловной оптимизации
с помощью образования новой целевой функции
где
- вектор множителей Лагранжа, L - число ограничений.
Слайд 26Необходимые условия экстремума функции :
Система содержит n+L
алгебраических уравнений, где
n - размерность пространства управляемых параметров. Её
решение - искомые координаты экстремальной точки и значения множителей Лагранжа. При численном решении системы (алгоритмические модели) возникают трудности. Поэтому в САПР основными методами решения ЗМП являются методы штрафных функций и проекции градиента.
Слайд 27Основная идея методов штрафных функций — преобразование задачи условной оптимизации
в задачу безусловной оптимизации путем формирования новой целевой функции Ф(N)
введением в исходную целевую функцию F(X) специальным образом выбранной функции штрафа S(X):где r - множитель, значения которого можно изменять в процессе оптимизации.
Слайд 28Среди методов штрафных функций различают методы внутренней и внешней точки.
Согласно методам внутренней точки (методам барьерных функций) исходную для поиска
точку можно выбирать только внутри допустимой области, а для методов внешней точки как внутри, так и вне допустимой области (в ней функции целевая и ограничений должны быть определены). 
Слайд 29Ситуация появления барьера у целевой функции Ф(х) и соотношение между
условным в точке х2 и безусловным в точке х1 минимумами
F(x) в простейшем одномерном случае иллюстрируется рисунком
Слайд 30Примеры штрафных функций:
для метода внутренней точки при ограничениях
где m
- число ограничений типа неравенств;
для метода внешней точки при таких
же ограничениях здесь штраф сводится к включению в Ф(N) суммы квадратов активных (т.е. нарушенных) ограничений;
3) в случае ограничений типа равенств
Слайд 31Чем больше коэффициент r, тем точнее решение задачи, однако при
больших r может ухудшаться ее обусловленность.
Поэтому в начале поиска
обычно выбирают умеренные значения r, увеличивая их в окрестностях экстремума. 
Слайд 32Основной вариант
метода проекции градиента ориентирован на задачи математического программирования
c ограничениями типа равенств.
Слайд 33Поиск при выполнении ограничений осуществляется в подпространстве
(n-m) измерений,
где
n - число управляемых параметров, m - число ограничений.
При
этом движение осуществляется в направлении проекции градиента целевой функции F(X) на гиперплоскость, касательную к гиперповерхности ограничений (точнее к гиперповерхности пересечения гиперповерхностей ограничений). 
Слайд 34Поиск минимума начинают со спуска из исходной точки на гиперповерхность
ограничений. Далее выполняют шаг в указанном выше направлении (шаг вдоль
гиперповерхности ограничений).Поскольку этот шаг может привести к заметному нарушению ограничений, вновь повторяют спуск на гиперповерхность ограничений и т.д.
Слайд 35
Идею метода поясним для случая поиска в двумерном пространстве при
одном ограничении ψ(X) = 0.
Слайд 36На рисунке это ограничение представлено жирной линией, а целевая функция
— совокупностью более тонких линий равного уровня.
Спуск обычно осуществляют
по нормали к гиперповерхности ограничений (в данном случае к линии ограничения).Условие окончания поиска основано на сопоставлении значений целевой функции в двух последовательных точках, получаемых после спуска на гиперповерхность ограничений.
Слайд 37Рассмотрим получение аналитических выражений для направлений спуска и движения вдоль
гиперповерхности ограничений.
Слайд 38Спуск
Необходимо из текущей точки поиска В попасть в точку
А, являющуюся ближайшей к В точкой на гиперповерхности ограничений,
т.е.
решить задачу:min |B-A|
при условии ψ(X)=0, которое после линеаризации в окрестностях точки В имеет вид
Слайд 39Используем метод множителей Лагранжа, обозначая А-В=U и учитывая, что минимизация
расстояния равнозначна минимизации скалярного произведения U на U, получаем
тогда
из второго выражения получаемподставляя его в третье выражение, имеем
откуда
Подставляя λ во второе выражение, находим
Слайд 40Движение вдоль гиперповерхности ограничений
Шаг в гиперплоскости D, касательной к
гиперповерхности ограничений, следует сделать в направлении вектора S, на котором
целевая функция уменьшается в наибольшей мере при заданном шаге h.
Слайд 41Уменьшение целевой функции при переходе из точки А в новую
точку С подсчитывают, используя формулу линеаризации F(X) в окрестностях точки
А:где - приращение F(X),
которое нужно минимизировать, варьируя направления S.
Слайд 42
где вариация S осуществляется в пределах гиперплоскости D; grad ψ(A)
и S — ортогональные векторы.
Следовательно, минимизацию этого выражения необходимо
выполнять при ограничениях Последнее ограничение говорит о том, что при поиске направления движения, вектор S должен лишь указывать это направление, т.е. его длина несущественна (пусть S — единичный вектор).
Слайд 43Для решения
используем метод множителей Лагранжа.
где λ и q — множители
Лагранжа;
Из второго выражения следует, что
подставляя S в третье выражение,
получаем откуда
Слайд 44
Таким образом, матрица
представляет собой проектирующую матрицу, а вектор S,
рассчитанный по верхнему выражению, — проекцию градиента grad F(A) на
гиперповерхность ограничений.
Слайд 45Частным случаем применения метода проекции градиента являются задачи оптимизации с
максиминным критерием. Для поиска экстремума функции минимума
где Zj — нормированная
величина j-го выходного параметра yj,
удобно применять метод проекции градиента.
Слайд 46В качестве ограничений задачи в исходной постановке фигурируют только прямые
ограничения
Здесь хmaxi и xmini — граничные значения допустимого диапазона варьирования
параметра хi. В процессе поиска, если минимальной является функция Zq(X) и траектория поиска пересекает гребень
то поиск продолжается в направлении проекции градиента функции Zq(X) на гиперповерхность этого гребня.
