Алгоритмы внутренних точек с приближенным решением вспомогательной задачи

Содержание

1. Алгоритмы внутренних точек с приближенным решением вспомогательной задачи
2. 1939 – линейное программирование (Канторович).1947 – симплекс-метод
3. Основные классы алгоритмоввнутренних точек(1)(2)Пара взаимно-двойственных задачлинейного программирования
4. Аффинно-масштабирующиеалгоритмы внутренних точекСтартовое приближение:Итеративный переход:Задача поиска направления корректировки:Шаг корректировки:(3)Способы выбора весовых коэффициентов:(4)(5)(6)(7)
5. Алгоритмы центрального пути(имеют полиномиальные оценки)Логарифмическая барьерная функция:(8)Задача поиска направления корректировки:Комбинированные алгоритмы(используют параметризацию)(10)(9)Задача поиска направления корректировки:
6. Решение вспомогательной задачиАффинно-масштабирующие алгоритмы:Алгоритмы центрального пути:Комбинированные алгоритмы:(11)(12)(13)(14)(17)(18)(15)(16)
7. Методы решениявспомогательной задачи Метод Гаусса. Метод Халецкого
8. Метод сопряженных направленийНаправление корректировки:Шаг, определяющий вариант метода:Итеративный переход:Шаг корректировки:
9. Экспериментальное исследованиеЧисло итераций, необходимое для решения задач при n=1,2mЧисло итераций, необходимое для решения задач при n=1,5m
10. Параметры управления алгоритмом Вариант приближенного метода. ε
11. Спасибоза внимание!
12. Скачать презентанцию

1939 – линейное программирование (Канторович).1947 – симплекс-метод (Данциг).1967 – метод внутренних точек (Дикин).1984 – полиномиальный МВТ (Кармаркар).1990-е - 2007 – эффективные программные реализации. CPlex (http (http:// (http://maximal (http://maximal- (http://maximal-usa (http://maximal-usa. (http://maximal-usa.com),

Главная
Математика
Алгоритмы внутренних точек с приближенным решением вспомогательной задачи

Слайды и текст этой презентации

Слайд 1Алгоритмы внутренних точек
с приближенным решением
вспомогательной задачи
Филатов А.Ю.
к.ф.-м.н., ИСЭМ СО РАН,

ИГУ (Иркутск)

Пержабинский С.М.
ИСЭМ СО РАН (Иркутск)
Работа выполнена при финансовой поддержке

РФФИ
(проект 05-01-00587а)

http://polnolunie.baikal.ru/me/mat_http://polnolunie.baikal.ru/me/mat_proghttp://polnolunie.baikal.ru/me/mat_prog.htm,
http://matec.isu.ru

Алгоритмы внутренних точекс приближенным решениемвспомогательной задачиФилатов А.Ю.к.ф.-м.н., ИСЭМ СО РАН, ИГУ (Иркутск)Пержабинский С.М.ИСЭМ СО РАН (Иркутск)Работа выполнена

Слайд 21939 – линейное программирование (Канторович).
1947 – симплекс-метод (Данциг).
1967 – метод

внутренних точек (Дикин).
1984 – полиномиальный МВТ (Кармаркар).
1990-е - 2007 –

эффективные программные реализации.

CPlex (http (http:// (http://maximal (http://maximal- (http://maximal-usa (http://maximal-usa. (http://maximal-usa.com), BPMPD (http (http:// (http://sztaki (http://sztaki. (http://sztaki.hu), MOSEK (http (http:// (http://mosek (http://mosek. (http://mosek.com),
HOPDM (http (http:// (http://www (http://www. (http://www.maths (http://www.maths. (http://www.maths.ed (http://www.maths.ed. (http://www.maths.ed.ac (http://www.maths.ed.ac. (http://www.maths.ed.ac.uk (http://www.maths.ed.ac.uk/~ (http://www.maths.ed.ac.uk/~gondzio (http://www.maths.ed.ac.uk/~gondzio/ (http://www.maths.ed.ac.uk/~gondzio/software (http://www.maths.ed.ac.uk/~gondzio/software/ (http://www.maths.ed.ac.uk/~gondzio/software/hopdm (http://www.maths.ed.ac.uk/~gondzio/software/hopdm. (http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html)

Исторический экскурс

1939 – линейное программирование (Канторович).1947 – симплекс-метод (Данциг).1967 – метод внутренних точек (Дикин).1984 – полиномиальный МВТ (Кармаркар).1990-е

Слайд 3Основные классы алгоритмов
внутренних точек
(1)

(2)
Пара взаимно-двойственных задач
линейного программирования
Аффинно-масштабирующие алгоритмы.
Алгоритмы

центрального пути.
Алгоритмы скошенного пути.
Комбинированные алгоритмы.

Прямые алгоритмы.
Двойственные

алгоритмы.
Прямо-двойственные алгоритмы.

Основные классы алгоритмоввнутренних точек(1)(2)Пара взаимно-двойственных задачлинейного программирования Аффинно-масштабирующие алгоритмы. Алгоритмы центрального пути. Алгоритмы скошенного пути. Комбинированные алгоритмы.

Слайд 4Аффинно-масштабирующие
алгоритмы внутренних точек
Стартовое приближение:
Итеративный переход:
Задача поиска направления корректировки:
Шаг корректировки:
(3)
Способы выбора

весовых коэффициентов:
(4)
(5)
(6)
(7)

Аффинно-масштабирующиеалгоритмы внутренних точекСтартовое приближение:Итеративный переход:Задача поиска направления корректировки:Шаг корректировки:(3)Способы выбора весовых коэффициентов:(4)(5)(6)(7)

Слайд 5Алгоритмы центрального пути
(имеют полиномиальные оценки)
Логарифмическая барьерная функция:
(8)
Задача поиска направления корректировки:
Комбинированные

алгоритмы
(используют параметризацию)
(10)
(9)
Задача поиска направления корректировки:

Алгоритмы центрального пути(имеют полиномиальные оценки)Логарифмическая барьерная функция:(8)Задача поиска направления корректировки:Комбинированные алгоритмы(используют параметризацию)(10)(9)Задача поиска направления корректировки:

Слайд 6Решение вспомогательной задачи
Аффинно-масштабирующие алгоритмы:
Алгоритмы центрального пути:
Комбинированные алгоритмы:
(11)
(12)
(13)
(14)
(17)
(18)
(15)
(16)

Решение вспомогательной задачиАффинно-масштабирующие алгоритмы:Алгоритмы центрального пути:Комбинированные алгоритмы:(11)(12)(13)(14)(17)(18)(15)(16)

Слайд 7Методы решения
вспомогательной задачи
Метод Гаусса.
Метод Халецкого (метод квадратного корня).

Метод сопряженных направлений.
Метод Зейделя.
Другие приближенные итеративные методы.
Предпосылки использования
приближенных

итеративных методов

На первых итерациях достаточно искать приближенное
направление корректировки , используя вектор ,
для которого .

В финале вычислительного процесса, диагональная мат-
рица изменяется по итерациям очень незначительно,
имеется хорошее стартовое приближение .

Методы решениявспомогательной задачи Метод Гаусса. Метод Халецкого (метод квадратного корня). Метод сопряженных направлений. Метод Зейделя. Другие приближенные

Слайд 8Метод сопряженных направлений

Направление корректировки:
Шаг, определяющий вариант метода:
Итеративный переход:
Шаг корректировки:

Слайд 9Экспериментальное исследование
Число итераций, необходимое для решения задач при n=1,2m
Число итераций,

необходимое для решения задач при n=1,5m

Экспериментальное исследованиеЧисло итераций, необходимое для решения задач при n=1,2mЧисло итераций, необходимое для решения задач при n=1,5m

Слайд 10Параметры управления алгоритмом
Вариант приближенного метода.
ε – параметр в

условии останова
δ – параметр в условие перехода с точного

на
приближенный метод
K – максимальное число выполняемых подряд
итераций приближенного метода.
t – число внутренних итераций приближенного
метода.
Процедуры корректировки формул (3), (10) и
формул вычисления максимального шага на
фазе 1.

– прогноз шага корректировки.

Параметры управления алгоритмом Вариант приближенного метода. ε – параметр в условии останова δ – параметр в условие

Слайд 11Спасибо
за внимание!

Скачать презентацию

Теги

Разделы презентаций

Алгоритмы внутренних точек с приближенным решением вспомогательной задачи

Содержание

Слайды и текст этой презентации

Слайд 1Алгоритмы внутренних точек
с приближенным решением
вспомогательной задачи
Филатов А.Ю.
к.ф.-м.н., ИСЭМ СО РАН,

ИГУ (Иркутск)

Пержабинский С.М.
ИСЭМ СО РАН (Иркутск)
Работа выполнена при финансовой поддержке

Слайд 21939 – линейное программирование (Канторович).
1947 – симплекс-метод (Данциг).
1967 – метод

внутренних точек (Дикин).
1984 – полиномиальный МВТ (Кармаркар).
1990-е - 2007 –

Слайд 3Основные классы алгоритмов
внутренних точек
(1)

(2)
Пара взаимно-двойственных задач
линейного программирования
Аффинно-масштабирующие алгоритмы.
Алгоритмы

центрального пути.
Алгоритмы скошенного пути.
Комбинированные алгоритмы.

Прямые алгоритмы.
Двойственные

весовых коэффициентов:
(4)
(5)
(6)
(7)

Слайд 5Алгоритмы центрального пути
(имеют полиномиальные оценки)
Логарифмическая барьерная функция:
(8)
Задача поиска направления корректировки:
Комбинированные

алгоритмы
(используют параметризацию)
(10)
(9)
Задача поиска направления корректировки:

Слайд 6Решение вспомогательной задачи
Аффинно-масштабирующие алгоритмы:
Алгоритмы центрального пути:
Комбинированные алгоритмы:
(11)
(12)
(13)
(14)
(17)
(18)
(15)
(16)

Слайд 7Методы решения
вспомогательной задачи
Метод Гаусса.
Метод Халецкого (метод квадратного корня).

Метод сопряженных направлений.
Метод Зейделя.
Другие приближенные итеративные методы.
Предпосылки использования
приближенных

Слайд 8Метод сопряженных направлений

Направление корректировки:
Шаг, определяющий вариант метода:
Итеративный переход:
Шаг корректировки:

Слайд 9Экспериментальное исследование
Число итераций, необходимое для решения задач при n=1,2m
Число итераций,

необходимое для решения задач при n=1,5m

Слайд 10Параметры управления алгоритмом
Вариант приближенного метода.
ε – параметр в

условии останова
δ – параметр в условие перехода с точного

Слайд 11Спасибо
за внимание!

Обратная связь

Что такое TheSlide.ru?

Разделы презентаций

Алгоритмы внутренних точек с приближенным решением вспомогательной задачи

Содержание

Слайды и текст этой презентации

Слайд 1Алгоритмы внутренних точекс приближенным решениемвспомогательной задачиФилатов А.Ю.к.ф.-м.н., ИСЭМ СО РАН,

ИГУ (Иркутск)Пержабинский С.М.ИСЭМ СО РАН (Иркутск)Работа выполнена при финансовой поддержке

Слайд 21939 – линейное программирование (Канторович).1947 – симплекс-метод (Данциг).1967 – метод

внутренних точек (Дикин).1984 – полиномиальный МВТ (Кармаркар).1990-е - 2007 –

Слайд 3Основные классы алгоритмоввнутренних точек(1)(2)Пара взаимно-двойственных задачлинейного программирования Аффинно-масштабирующие алгоритмы. Алгоритмы

центрального пути. Алгоритмы скошенного пути. Комбинированные алгоритмы. Прямые алгоритмы. Двойственные

весовых коэффициентов:(4)(5)(6)(7)

Слайд 5Алгоритмы центрального пути(имеют полиномиальные оценки)Логарифмическая барьерная функция:(8)Задача поиска направления корректировки:Комбинированные

алгоритмы(используют параметризацию)(10)(9)Задача поиска направления корректировки:

Слайд 6Решение вспомогательной задачиАффинно-масштабирующие алгоритмы:Алгоритмы центрального пути:Комбинированные алгоритмы:(11)(12)(13)(14)(17)(18)(15)(16)

Слайд 7Методы решениявспомогательной задачи Метод Гаусса. Метод Халецкого (метод квадратного корня).

Метод сопряженных направлений. Метод Зейделя. Другие приближенные итеративные методы.Предпосылки использованияприближенных

Слайд 8Метод сопряженных направленийНаправление корректировки:Шаг, определяющий вариант метода:Итеративный переход:Шаг корректировки:

Слайд 9Экспериментальное исследованиеЧисло итераций, необходимое для решения задач при n=1,2mЧисло итераций,

необходимое для решения задач при n=1,5m

Слайд 10Параметры управления алгоритмом Вариант приближенного метода. ε – параметр в

условии останова δ – параметр в условие перехода с точного

Слайд 11Спасибоза внимание!

Похожие презентации

Обратная связь

Что такое TheSlide.ru?

Слайд 1Алгоритмы внутренних точек
с приближенным решением
вспомогательной задачи
Филатов А.Ю.
к.ф.-м.н., ИСЭМ СО РАН,

ИГУ (Иркутск)

Пержабинский С.М.
ИСЭМ СО РАН (Иркутск)
Работа выполнена при финансовой поддержке

Слайд 21939 – линейное программирование (Канторович).
1947 – симплекс-метод (Данциг).
1967 – метод

внутренних точек (Дикин).
1984 – полиномиальный МВТ (Кармаркар).
1990-е - 2007 –

Слайд 3Основные классы алгоритмов
внутренних точек
(1)

(2)
Пара взаимно-двойственных задач
линейного программирования
Аффинно-масштабирующие алгоритмы.
Алгоритмы

центрального пути.
Алгоритмы скошенного пути.
Комбинированные алгоритмы.

Прямые алгоритмы.
Двойственные

весовых коэффициентов:
(4)
(5)
(6)
(7)

Слайд 5Алгоритмы центрального пути
(имеют полиномиальные оценки)
Логарифмическая барьерная функция:
(8)
Задача поиска направления корректировки:
Комбинированные

алгоритмы
(используют параметризацию)
(10)
(9)
Задача поиска направления корректировки:

Слайд 6Решение вспомогательной задачи
Аффинно-масштабирующие алгоритмы:
Алгоритмы центрального пути:
Комбинированные алгоритмы:
(11)
(12)
(13)
(14)
(17)
(18)
(15)
(16)

Слайд 7Методы решения
вспомогательной задачи
Метод Гаусса.
Метод Халецкого (метод квадратного корня).

Метод сопряженных направлений.
Метод Зейделя.
Другие приближенные итеративные методы.
Предпосылки использования
приближенных

Слайд 8Метод сопряженных направлений

Направление корректировки:
Шаг, определяющий вариант метода:
Итеративный переход:
Шаг корректировки:

Слайд 9Экспериментальное исследование
Число итераций, необходимое для решения задач при n=1,2m
Число итераций,

Слайд 10Параметры управления алгоритмом
Вариант приближенного метода.
ε – параметр в

условии останова
δ – параметр в условие перехода с точного

Слайд 11Спасибо
за внимание!