Численные методы оптимизации

Численные методы оптимизации М.Р.Давидсон МГУ им Ломоносова, ф-т ВМиК Кафедра Исследования Операций Лекция 1 Введение Постановка задачи оптимизации min f ( x) x∈ X целевая функция (функция цели) X - допустимое множество Вид допустимого множества: Пример 1 X = {x ∈ R n | g i ( x) ≤ 0, i = 1,..., m} Пример 2 X = {x ∈ R n | g ( x, y ) ≤ 0, y ∈ Y } f ( x) : R n → R • Математические исследования отдельных экономических проблем (20e гг. ХХ века) – Развитие экономики потребовало количественных показателей, и в 1920 годы был создан межотраслевой баланс (МОБ). Он-то и послужил толчком в деле создания и исследования математических моделей. Разработка МОБ в 1924—1925 годах в СССР повлияла на работы экономиста и статистика Василия Васильевича Леонтьева. Он разработал межотраслевую модель производства и распределения продукции: Модель продуктивна, если для всякого неотрицательного у разрешима система x = Ax + y, x ≥ 0, y ≥ 0 • Начало линейного программирования В 1938 году Леонид Витальевич Канторович в порядке научной консультации приступил к изучению практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась обычным методам. В 1939 году Л.В. Канторович написал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования. В ней был предложен расчетный метод, позволяющий находить решение технико-экономических вопросов такого рода, как наиболее рациональное распределение работ по механизмам, раскрои материала с минимальными отходами, распределение грузов по нескольким видам транспорта и т. п. Однако эта работа настолько опережала время и настолько не соответствовала догматам тогдашней политической экономии, что ее публикация оказалась возможной только в 1959 г. Изучение подобных задач привело к созданию новой научной дисциплины линейного программирования и открыло новый этап в развитии экономико-математических методов. • Применение в исследовании операций Источник: Ф.Морз, Дж.Кимбелл, Методы исследования операций, 1956 • Критерий соотношения потерь (число потопленных ПЛ/число потопленных торговых судов): • Задача оптимизации: максимизировать соотношение потерь Другие примеры задач оптимизации: Задача об оптимальном рационе Транспортная задача • Симплекс - метод Исторически общая задача линейного программирования была впервые поставлена в 1947 году Джорджем Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических методов для военных задач и проблем планирования. В 1949 году Данциг разработал эффективный метод решения задач линейного программирования (ЛП)— симплекс-метод. Первое успешное решение задачи ЛП на ЭВМ SEAC было проведено в январе 1952 года • Что значит «эффективность»? – Понятие сложности задачи (битовая длина записи исходных данных задачи) – Понятие сложности алгоритма решения (количество машинных операций, как функция от размерности задачи) – Эффективный/неэффективный – полиномиальный/экспоненциальный – Пример 1: метод Гаусса решения системы линейных равенств (О(n^3)) – Пример 2: эффективный алгоритм определения простоты числа ??? • Эффективен ли симплекс-метод? – Сколько вершин у многогранника, заданного n линейными ограничениями? Пример: X = {x ∈ R n | 0 ≤ xi ≤ 1, i = 1,..., n} – Может ли симплекс-метод обойти все вершины? Klee, Victor Minty, George J. How good is the simplex algorithm? // Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, • Полиномиальный алгоритм для задачи ЛП – метод эллипсоидов (Хачиян Л.Г., 1979) – O(n^3(n + m)L) – метод внутренней точки (Кармаркар Н., 1984, O(m^{3/2}n^2L) – J. Renegar (1986) O(n^3L) – A.Немировский, Ю.Нестеров (1988), обобщение на выпуклый случай • Классификация задач оптимизации – Безусловная оптимизация • глобальный/локальный экстремум – Условная оптимизация • Линейное программирование (ЛП) • Выпуклое программирование • Общая задача нелинейного программирования (НЛП) • Полубесконечная оптимизация – Негладкая оптимизация – Дискретное программирование Лекция 2 Основные понятия • Вектор  x1     x2  n x ∈ R , x =  ,    x   n xT = ( x1 , x2 ,  , xn ) • Векторное пространство: линейное пространство, в котором, есть 0, определены сложение векторов, умножение векторов на число Свойства так определенного скалярного произведения • Неравенство Коши-Буняковского (следует непосредственно из свойств скалярного произведения) ( x, y ) ≤| x | | y |, где | u |= (u , u )1/ 2 • Неравенство треугольника | x + y |2 = ( x, x) + ( y, y ) + 2( x, y ) ≤ ( x, x) + ( y, y ) + 2 | x || y | =| x |2 + | y |2 +2 | x || y |= (| x | + | y |) 2 , откуда | x + y |≤| x | + | y | • Метрическое пространство – это пространство, в котором определена метрика: • Нормированное пространство – пространство, где для каждого вектора определена норма • Пользуясь свойствами скалярного произведения и неравенством треугольника, можем определить Евклидову метрику: d ( x, y ) =| x − y | • Евклидова длина вектора | u |= (u , u )1/ 2 является нормой • Матрицы • Умножение матрицы на вектор и на матрицу • Частный случай: произведение векторов x ∈ R n , y ∈ R n , x T y ≡ ( x, y ) • Неотрицательно/положительно определенные матрицы A ≥ 0 ⇔ ( Ax, x) = xT Ax ≥ 0 ∀x ∈ R n • Симметричная матрица имеет n вещественных собственных чисел и ортонормированный базис из собственных векторов Ah = λi h , i = 1,..., n i i i j (h , h ) = 0, i, j = 1,..., n, i ≠ j • Симметричная матрица неотрицательно определена тогда и только когда, ее собственные числа неотрицательны. λi ≥ 0, i = 1,..., n • Операторная норма матрицы • 88 x ∈ R n , || Ax ||≤|| A || || x || • По определению для всех • В Евклидовом пространстве для любого х /2 || Ax ||= ( Ax, Ax)1/ 2 = ( AT Ax, x)1/ 2 ≤ λ1max ( AT A) || x || /2 ( AT A) • Таким образом || A ||= λ1max • Если А симметрична, || A ||= max | λ ( A) | • Аналогично, || A−1 ||= max | 1 / λ ( A) |= 1 / min | λ ( A) |