Lektsia-1-pometki (1)

1. Методы оптимизации Лекция 1: Введение

ГОЛОВКИНА АННА ГЕННАДЬЕВНА
GOLOVKINA.A@GMAIL.COM

2. Геометрические задачи

Пример: Найти стороны прямоугольника, вписанного в
окружность радиуса R и имеющего наибольшую площадь S.

3. Идентификация математических моделей как задача оптимизации

•В начале 19 века Джузеппе Пьяцци опубликовал наблюдения за
недавно открытой карликовой планетой Церера
• К.Ф. Гаусс смог рассчитать орбиту Цереры по наблюдениям (между
орбитами Марса и Юпитера). Планета была обнаружен в
предсказанном местоположение через много недель после того, как
ее видимое положение изменилось.
• Чтобы подобрать параметры модели из (зашумленных)
наблюдений, Гаусс изобрел метод наименьших квадратов
•Подгонка параметров модели для уменьшения ошибки прогноза
также известна как минимизация эмпирического риска.

4. Идентификация математических моделей как задача оптимизации

5. Диета Стиглера

•В 1930-х годах армия США была заинтересована в создании
питательного рациона для солдат с минимальной
стоимостью
- Должны быть учтены рекомендуемые суточные дозы
потребления питательных веществ
- Рассмотрен питательный состав 77 типов продуктов и их цена
- Какая самая дешевая комбинация продуктов будет
удовлетворять ограничениям?
•Предыдущие попытки расчета давали рацион стоимостью
100 $ в год
•Джордж Стиглер использовал оптимизацию
- 9 служащих занимались расчетами в течение 120 человеко-дней
- Было найдено решение стоимостью $39.93
•Диета Стиглера относится к классу оптимизационных задач,
которые называются Линейное программирование
•Сейчас такие задачи решаются стандартными солверами за
миллисекунды.

6. Задача о рационе

7. Оптимизация в инженерных задачах

Оптимизация затрат при ограничениях
Оптимизация производительности при ограничениях
Компромисс производительность-затраты

8. Оптимизация в задачах управления

• Управление в замкнутом цикле или управление с обратной связью
• Изначально называлось кибернетикой, сегодня - теория управления
• Управление с прогнозирующими моделями: управления это
результат решения задачи оптимизации, которая решается множество
раз в секунду
Пример: автоматическое управление гоночной машинкой
Пример: перевернутый маятник

9. Оптимизация и компьютерное зрение

Сопоставление
стереоизображений
Удаление шума на
изображении
Удаление размытия
изображения
• Функция энергии описывает качество решения (по аналогии с функцией потерь в машинном
обучении)
• Задачи оптимизации в компьютерном зрении сильно многомерные!
• Невыпуклые функции энергии аппроксимируются выпуклыми

10. Оптимизация в природе

Свет распространяется по кратчайшему пути (принцип Ферма)
Оптимизация как закон природы
• Состояние минимальной энергии
• Принцип наименьшего действия
• Свет распространяется по кратчайшей траектории
• Классическая механика
• Целенаправленное активное поведение
Мыльная пленка стремится к минимальной поверхности
Минимизация энергии при фолдинге белка