Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 127.06 Kb.
|
Правительство Российской Федерации Федеральное государственное автономное образовательное Учреждение высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики» Факультет «Информационные технологии и вычислительная техника» Программа дисциплины «Методы оптимизации» Для направления 230100 «Информатика и вычислительная техника» специальности 230100.68 «Системы автоматизированного проектирования» подготовки магистра Автор программы : Правдивая Е.А. , kapra64@mail.ru Одобрена на заседании кафедры ИТАС Зав.кафедрой Тумковский С.Р. «______»______________2010 г. Рекомендована профессиональной коллегией УМС Председатель_____________ «_______»________________2010г. Утверждена УС МИЭМ НИУ ВШЭ «______» _______________2010г. Ученый секретарь Симонов В.П. _______________________________ Москва, 2010 г. Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры –разработчика программы.
Целью преподавания дисциплины является ознакомление студентов с формулировками задач параметрической оптимизации, возникающими в процессе проектирования, и методами их решения. Задачами преподавания являются изучение основных формулировок задач оптимизации, критериев существования их решений, методов поиска решений, а также освоение методик решения практических задач оптимального проектирования.
В процессе изучения курса студент должен научиться правильно формулировать задачу оптимизации с учетом особенностей модели оптимизируемого объекта, выбирать соответствующие методы решения задачи и использовать методики их решения.
Лекции.1. Математическая модель проектируемого объекта (процесса), входные, выходные и внутренние параметры и характеристики модели, ее структурные и параметрические изменения и варьируемые параметры, примеры моделей. Неформальное определение наилучшего значения вектора варьируемых параметров модели. Формулировка задач векторной и скалярной параметрической оптимизации. Основные подходы к решению задачи нелинейного программирования, влияние свойств модели проектируемого объекта на процесс ее решения. Первичная классификация задач оптимизации в зависимости от вида целевой функции и наличия и характера ограничений.-2ч 2. Формирование критериев оптимальности, аддитивные, мультипликативные и минимаксные критерии. Основные подходы к решению задачи векторной оптимизации. Область Парето. Построение множества конкурирующих решений. Метод последовательной субоптимизации. Сведение задачи векторной оптимизации к скалярной. Стратегии выбора весовых коэффициентов для частных критериев.-2ч 3. Экстремум ограниченной непрерывной функции. Разложение гладкой функции в ряд Тейлора. Нормы векторов и матриц. Спектральная норма матрицы. Необходимое условие 1-го порядка как теоретическая основа построения градиентных методов оптимизации. Седловая точка. Положительно определенная матрица. Необходимые и достаточные условия 2-го порядка. Количественные значения определенности (положительной, отрицательной и т. д.) матрицы Гессе и тип (минимум, максимум, седло) стационарной точки. Обусловленность матрицы. Количественные значения числа обусловленности матрицы Гессе (с использованием спектральной нормы) и характер экстремума. Квадратичные функции, их использование в последующих темах дисциплины.-4ч 4. Основные подходы к решению задачи условной оптимизации с функциональными ограничениями типа равенств (аналитические преобразования, поисковый процесс). Функция Лагранжа. Теорема (необходимое условие экстремума). Метод множителей Лагранжа, пример решения задачи. Связь в точке минимума множителей Лагранжа с частными производными целевой функции по параметрам ограничений. -2ч 5. Источники возникновения задачи. Общая характеристика методов одномерной минимизации и их классификация. Общие и специфические требования к методам. Методы сокращения длины интервалов неопределенности. Теоретическая основа методов. Методы равномерного поиска, деления интервала пополам, методы Фибоначчи и золотого сечения. Сравнение эффективности методов и оценка их численной устойчивости. Методы, основанные на идее интерполяции (квадратичная и кубическая интерполяция без использования производных, кубическая интерполяция с использованием производных). Методы 0-го, 1-го и 2-го порядков, основанные на построении релаксационных последовательностей. -4ч 6. Общая характеристика методов 0-го порядка. Метод покоординатного спуска с дискретным и оптимальным шагом, его основные недостатки. Метод конфигураций, метод вращающихся координат (метод Розенброка). Теорема о построении ортогональных направлений поиска. Понятие сопряженных направлений. Свойство параллельных подпространств квадратичной функции, квадратичная скорость сходимости процесса поиска ее минимума по сопряженным направлениям. Метод сопряженных направлений 0-го порядка. Линейная независимость направлений поиска. Сравнение эффективности рассмотренных методов. -4ч 7. Общая характеристика методов 1-го порядка. Градиент - направление наиболее быстрого изменения функции (доказательство путем решения соответствующей экстремальной задачи методом множителей Лагранжа). Метод наискорейшего спуска (метод Коши), доказательство его недостатков. Методы параллельных касательных и "тяжелого шарика". Вывод метода сопряженных направлений Флетчера-Ривса. Метод сопряженных направлений Зангвилла. Сравнение эффективности рассмотренных методов.-4ч 8. Общая характеристика методов 2-го порядка. Метод Ньютона, его скорость сходимости для квадратичной функции. Основные недостатки метода Ньютона. Квазиньютоновские методы. Метод Марквардта, его достоинства и недостатки. Метод переменной метрики. Сравнение эффективности рассмотренных методов.-2ч 9. Формулировка задачи линейного программирования, ее распространенность в практике решения оптимизационных задач. Пример формулировки задачи, графические методы ее решения. Переход к формулировке задачи в стандартной форме, симплекс-метод ее решения, пример решения задачи симплекс-методом. Анализ чувствительности в линейном программировании, развитие идей линейного программирования.-2ч 10. Условия Куна-Таккера и задача Куна-Таккера (основные теоремы). Условия существования седловой точки, условия оптимальности второго порядка.-2ч 11. Методы оптимизации, основанные на преобразовании задачи условной оптимизации в безусловную. Штрафные и барьерные функции, примеры функций, пример решения задачи. Методы прямого поиска в задачах условной оптимизации. Метод комплексов. Преобразование задачи в последовательность задач линейного программирования.-4ч 12. Основные сведения о методах случайного поиска, адаптивные эвристические алгоритмы с переменным шагом. Поиск глобального минимума целевой функции путем использования комбинаций различных методов оптимизации, одновременное построение нескольких траекторий поиска. -2ч Практические занятия.
В соответствии с учебным планом (2 часа лекции каждую неделю, 2 часа семинар каждую неделю).
5.1. Рекомендуемая литература а) основная литература. 1). Батищев Д.И. Методы оптимального проектирования.: Учеб. пособие для ВУЗов. - М.: Радио и связь, 1984. - 248 с. 2). Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: Кн. 1. Пер. с англ. - М.: Мир, 1986. - 349 с. 3). Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. Оптимизация в технике: Кн. 2. Пер. с англ. - М.: Мир, 1986. - 320 с. б) дополнительная литература. 1). Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы: Пер. с англ. - М.: Мир, 1982. - 583 с. 5.2. Средства обеспечения дисциплины. Необходимыми для изучения дисциплинами техническими средствами и программным обеспечением являются ОС Windows и разработанные на кафедре пакеты программ. 1). Влияние на характер и тип стационарной точки каких-либо квадратичных функций числовых значений обусловленности и определенности матрицы Гессе. 2). Визуализация процессов работы и сравнение эффективности 9-ти методов одномерной минимизации набора однопараметрических целевых функций. 3). Визуализация процессов работы и автоматического сравнения эффективности и точности 16-ти методов минимизации многопараметрических целевых функций. В библиотеке, открытой для включения новых задач, содержатся описания примерно 20-ти критериев, используемых в отечественных и зарубежных учебниках по методам параметрической оптимизации. 4). Иллюстрация процесса работы симплекс-метода решения задачи линейного программирования. 5). Иллюстрация процесса преобразования многокритериальных задач оптимизации, процессов использования штрафных и барьерных функций. 5). Демонстрация некоторых разделов лекций с помощью ряда фрагментов компьютерного учебника в виде системы видеофильмов с встроенным в них речевым сопровождением. Видеофильмы выполнены в среде Macromedia Director 8.5 и Director MX.
Необходимое оборудование установлено в компьютерных классах №1 и № 2 каф. ИТАС. Рабочая программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности 230104. Настоящая программа рассмотрена на заседании кафедры “20” октября 2010 г. протокол № 10 и рекомендована к применению в учебном процессе. Зав кафедрой ИТАС проф. Тумковский С.Р. “____”_________________2010г. Срок действия программы продлен на 20__/20__ уч. год _____________________________________ (подпись зав. кафедрой) Срок действия программы продлен на 20__/20__ уч. год _____________________________________ (подпись зав. кафедрой) Срок действия программы продлен на 20__/20__ уч. год _____________________________________ (подпись зав. кафедрой) Срок действия программы продлен на 20__/20__ уч. год _____________________________________ (подпись зав. кафедрой) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Добавить документ в свой блог или на сайт
