Теория оптимизации

Материальная база курса: вычислительные модули и библиотеки

Учебный курс «Теория оптимизации» построен на работе с численными методами в средах Python 3.12+ и MATLAB R2026a. Используются библиотеки SciPy (оптимизация), CVXOPT (выпуклая оптимизация) и Gurobi (линейное программирование). Каждый метод — от симплекс-алгоритма до градиентного спуска — реализуется в двух вариантах: аналитическом (ручной расчёт на доске) и программном (численная реализация). Для задач с ограничениями применяются библиотеки ortools (Google OR-Tools) и pulp. Конфигурации вычислительных стендов: 8-ядерный процессор Intel Core i7-13700H, 32 ГБ ОЗУ, ОС Ubuntu 24.04 LTS.

Спецификации задач: классы, ограничения, размерность

Курс охватывает три класса оптимизационных задач: линейное программирование (ЛП), нелинейная безусловная оптимизация (НБО) и выпуклая оптимизация с ограничениями. Для ЛП размерность задач варьируется от 10 до 500 переменных, количество ограничений — до 200. Для НБО — до 50 переменных (функции Розенброка, Химмельблау, многомодальные функции). Выпуклая оптимизация: задачи с линейными и квадратичными ограничениями, до 100 переменных. Ключевое отличие от курса «Методы оптимизации» — акцент на выпуклости: 70% задач имеют выпуклую природу, остальные 30% — седловые точки и локальные минимумы. Каждый студент получает индивидуальный набор коэффициентов (seed 42–4200) для предотвращения копирования решений.

Качественные стандарты: точность, сходимость, допустимая погрешность

Критерии оценки решений строго количественны. Для симплекс-метода: точность базисного решения — 1×10⁻⁸ (абсолютная). Для градиентного спуска: условие остановки — норма градиента < 1×10⁻⁶. Для методов Ньютона: число итераций не более 1000, сходимость к стационарной точке. Отличие от формата «просто решить задачу»: требуется не только численный ответ, но и полная аналитическая выкладка первого шага — вычисление градиента, матрицы Гессе, проверка на выпуклость (тест на положительную полуопределённость). Лабораторные работы проходят автоматическую проверку через систему Judge0: код запускается на 10 скрытых тестах, минимальный проходной балл — 80% пройденных тестов. Повторная сдача возможна не более двух раз с частичным понижением оценки (коэффициент 0.85 и 0.7 соответственно).

Отличия от смежных дисциплин: линейное программирование vs выпуклая оптимизация

Курс «Теория оптимизации» принципиально отличается от «Численных методов» и «Исследования операций» по следующим параметрам: 1) В «Численных методах» акцент на аппроксимацию и интерполяцию — здесь же фокус на поиск экстремумов с использованием условий Каруша — Куна — Таккера (ККТ). 2) В «Исследовании операций» преобладают эвристические методы (имитация отжига, генетические алгоритмы) — в нашем курсе только детерминированные алгоритмы с доказанной сходимостью. 3) Техническая реализация: в «Линейном программировании» (отдельный курс) используется только симплекс-метод. В «Теории оптимизации» — 6 методов: симплекс, градиентный спуск, метод Ньютона, квазиньютоновские методы (BFGS), метод внутренней точки и метод сопряжённых градиентов. Каждый метод сравнивается по числу итераций, времени выполнения и количеству вычислений матрицы Гессе.

Производственный процесс освоения: лабораторные стенды и регламенты

Лабораторный практикум включает 8 работ. Первые 4 работы выполняются на бумаге (аналитический расчёт): составление матмодели, нахождение двойственной задачи, проверка условий ККТ. Результаты оформляются в виде отчёта формата LaTeX с обязательными разделами: постановка, метод, исходные данные, промежуточные вычисления (матрицы, векторы), итоговый ответ. Последние 4 работы — программная реализация: код на Python с комментариями, графики (matplotlib) линий уровня и траектории сходимости. Все отчёты сдаются в системе LMS Moodle в формате PDF + ссылка на GitHub-репозиторий. Качество оценивается по чек-листу: (1) корректность выбора метода, (2) обоснование выпуклости/невыпуклости, (3) отсутствие переполнения (NaN/Inf), (4) скорость сходимости (число итераций не более теоретической оценки). Нормы времени: на первую работу — 3 часа, на последнюю — 8 часов.

Требования к аппаратному и программному обеспечению студента

Для выполнения заданий необходим ноутбук с процессором x86-64 (4 ядра, частота >2.0 ГГц), ОЗУ от 16 ГБ (для задач с 500 переменными требуется не менее 12 ГБ выделяемой памяти). Программные спецификации: ОС Windows 11/Ubuntu 22.04, Python 3.10+ с пакетами numpy, scipy, cvxopt, matplotlib, pulp. Для MATLAB-реализаций — версия R2025b+ с установленным пакетом Optimization Toolbox. В случае отсутствия лицензии — альтернатива: GNU Octave 8.4 с пакетом optim. Студенты, использующие виртуальные машины (VirtualBox, WSL), должны гарантировать производительность на уровне нативного выполнения (отсутствие эмуляции с плавающей запятой). Тестовые прогоны на сервере кафедры выполняются под Docker-контейнером с жёстким лимитом CPU (2 ядра, 4 ГБ RAM). Превышение лимита (timeout >30 секунд) автоматически снижает оценку на 20%.

Показатели качества и сертификация результатов

Итоговый экзамен состоит из 2 частей: теоретическое задание (доказательство сходимости одного из методов, 45 минут) и практическая задача (реализация алгоритма на Python / MATLAB, 1 час 30 минут). Порог прохождения — 60 баллов из 100. При наборе 90+ баллов студент получает сертификат «Прикладная оптимизация» с указанием конкретных освоенных библиотек и точности методов. Все оценки валидируются внешним рецензентом (ассистент кафедры вычислительной математики). Повторная сертификация возможна через семестр с обновлённым пулом задач (подстановка новых коэффициентов).

Добавлено: 08.05.2026