Перечень вопросов
- Из каких частей состоит задача оптимизации?
- Что такое выпуклое множество?
- Чем выпуклая оболочка отличается от конуса?
- Что такое базисное допустимое решение?
- Как привести линейную задачу к стандартной форме?
- Когда можно гарантировать достижение оптимума?
- Как решить линейную задачу графически?
- Как выбирают симплекс-переход?
- Что такое вырожденность и почему возможно зацикливание?
- Как найти альтернативные оптимальные решения?
- Как различить несовместность и неограниченность?
- Как записать двойственную линейную задачу?
- Что означают слабая и сильная двойственность?
- Как применять дополняющую нежёсткость?
- Как понимать теневые цены и анализ чувствительности?
- Как устроена транспортная задача?
- Почему задача о рюкзаке требует целочисленности?
- Как определить состояние в динамическом программировании?
- Как записать уравнение Беллмана?
- Что такое выпуклая функция и чем полезна выпуклость?
- Что дают градиент и матрица Гессе?
- Как применять множители Лагранжа?
- Как записать условия Каруша — Куна — Таккера?
- Как выбирать шаг градиентного спуска?
- Чем метод Ньютона отличается от градиентного спуска?
- Как доказать результат вычислительного алгоритма?
- Когда применим алгоритм Дейкстры?
- Как связаны максимальный поток и минимальный разрез?
Ответы к экзамену
1. Из каких частей состоит задача оптимизации?
Нужно задать переменные, допустимое множество S и целевую функцию f. Решение x* должно принадлежать S и давать значение не хуже любой допустимой точки. Инфимум или супремум может существовать без достижения: inf eˣ=0 на ℝ, но минимальной точки нет. Поэтому ответы «значение» и «все оптимальные точки» — разные части решения. Необходимо также различать локальный и глобальный оптимум.
2. Что такое выпуклое множество?
Множество S выпукло, если вместе с любыми x,y содержит весь отрезок tx+(1−t)y, 0≤t≤1. Пересечение выпуклых множеств выпукло, в частности область линейных равенств и неравенств. Объединение выпуклых множеств может быть невыпуклым. Для проверки невыпуклости достаточно найти две допустимые точки, чья промежуточная выпуклая комбинация недопустима.
3. Чем выпуклая оболочка отличается от конуса?
Выпуклая оболочка точек состоит из комбинаций Σαᵢxᵢ, где αᵢ≥0 и Σαᵢ=1. Порожденный векторами конус — комбинации Σβᵢuᵢ с βᵢ≥0 без нормировки суммы. Отрезок описывает ограниченное смешение вершин, конус — неограниченные направления. Для многогранной области с вершинами часто нужен ответ «выпуклая оболочка вершин плюс конус направлений», а не только перечень вершин.
4. Что такое базисное допустимое решение?
В стандартной форме Ax=b,x≥0 при ранге A=m выбирают m линейно независимых столбцов, остальные переменные обнуляют и решают систему по базису. Если полученные координаты неотрицательны, базис допустим. Некоторые базисные переменные могут быть нулевыми — это вырожденность. Геометрически базисные допустимые решения соответствуют вершинам области; разные базисы могут задавать одну вырожденную вершину.
5. Как привести линейную задачу к стандартной форме?
Ограничение aᵀx≤b превращают в aᵀx+s=b с запасом s≥0. Для aᵀx≥b вводят избыточную переменную: aᵀx−s=b. Свободную по знаку переменную заменяют разностью двух неотрицательных. Максимизацию можно свести к минимизации отрицательной цели. Эти преобразования должны сохранять связь исходных и новых переменных; искусственная переменная первой фазы не является реальным запасом ресурса.
6. Когда можно гарантировать достижение оптимума?
Непрерывная функция достигает минимума и максимума на непустом компактном множестве. В стандартной линейной задаче при непустой области и конечном оптимальном значении существует оптимальное базисное допустимое решение. Для произвольной нелинейной задачи одной ограниченности значения недостаточно: например, минимум может не достигаться на открытой области. Сначала проверяют существование допустимых точек и свойства области.
7. Как решить линейную задачу графически?
На плоскости пересекают полуплоскости ограничений, находят вершины и исследуют линии уровня цели. Для ограниченного многоугольника достаточно сравнить значения в вершинах; при равных лучших значениях на концах ребра всё ребро оптимально. Для неограниченной области дополнительно исследуют допустимые направления. Пустую область и уход цели в бесконечность нельзя обнаружить одним сравнением найденных точек.
8. Как выбирают симплекс-переход?
Сначала явно фиксируют соглашение о строке цели. Например, при max z словарь z=z₀+Σrⱼxⱼ улучшается вводом переменной с rⱼ>0. В выражениях базисных переменных ищут максимальное допустимое увеличение: правило отношений учитывает только строки, где рост входящей переменной уменьшает базисную. Минимальное отношение определяет выходящую переменную. После поворота снова проверяют допустимость и коэффициенты цели.
9. Что такое вырожденность и почему возможно зацикливание?
Базис вырожден, если хотя бы одна базисная переменная равна нулю. Симплекс-переход тогда может изменить базис без движения точки и без изменения цели. При неудачном выборе переходов возможен цикл. Правило Бланда выбирает входящую и выходящую переменные по установленному порядку индексов и предотвращает циклы. Вырожденность не означает несовместность задачи или множественность оптимальных точек.
10. Как найти альтернативные оптимальные решения?
В оптимальном словаре нулевая приведённая стоимость небазисной переменной указывает на направление, которое не меняет цель. Надо проверить, возможно ли положительное допустимое движение. Если оно приводит в другую точку, получаем альтернативный оптимум; если длина шага нулевая, меняется лишь вырожденный базис. Полный ответ может быть отрезком, гранью или лучом, а не только двумя выбранными вершинами.
11. Как различить несовместность и неограниченность?
Несовместность означает отсутствие допустимых точек. В первой фазе стандартного двухфазного симплекс-метода положительный минимум суммы искусственных переменных подтверждает несовместность. Неограниченность цели требует допустимой точки и направления, вдоль которого цель улучшается без границы. Для max cᵀx в стандартной форме достаточно x≥0, Ax=b и d≥0, Ad=0, cᵀd>0: тогда x+td допустим и улучшается при t≥0.
12. Как записать двойственную линейную задачу?
Для прямой max cᵀx при Ax≤b,x≥0 двойственная равна min bᵀy при Aᵀy≥c,y≥0. Знаки следуют из типа ограничений и знаковых ограничений переменных. Равенство в прямой задаче даёт свободную двойственную переменную; свободная прямая переменная — равенство двойственного ограничения. Надёжнее выводить пару через оценку цели, чем запоминать правила без соглашения о max/min.
13. Что означают слабая и сильная двойственность?
Для любой допустимой пары в указанной max/min паре cᵀx≤bᵀy — слабая двойственность. Если прямая линейная задача допустима и имеет конечный оптимум, двойственная тоже имеет оптимальное решение, и значения равны — сильная двойственность. Равенство целей двух допустимых кандидатов сразу доказывает их оптимальность. Наличие красивой двойственной формулы без проверки допустимости кандидатов такого сертификата не даёт.
14. Как применять дополняющую нежёсткость?
Для max cᵀx, Ax≤b,x≥0 и её двойственной пары в оптимуме yᵢ(bᵢ−aᵢᵀx)=0, xⱼ((Aᵀy)ⱼ−cⱼ)=0. Положительный множитель требует активного ограничения, положительная переменная — нулевого двойственного зазора. Эти условия вместе с допустимостью обеих сторон эквивалентны оптимальности линейной пары. Нулевой множитель не запрещает ограничению быть активным.
15. Как понимать теневые цены и анализ чувствительности?
Двойственные множители интерпретируют как локальную ценность изменения правых частей там, где соответствующая чувствительность корректна. Формула изменения значения по множителям действует в пределах сохранения нужного оптимального режима; при смене базиса возможен излом. Двойственный оптимум может быть неединственным. Поэтому нельзя умножить любую большую прибавку ресурса на найденную теневую цену и объявить это точным глобальным прогнозом.
16. Как устроена транспортная задача?
Переменные xᵢⱼ — перевозки от поставщика i потребителю j. Суммы строк равны запасам, столбцов — потребностям; цель Σcᵢⱼxᵢⱼ→min. В сбалансированной задаче общий запас равен спросу. Ранг системы равен m+n−1, поэтому столько клеток входит в базис. Методы северо-западного угла и минимального элемента строят начальный план; оптимальность проверяют потенциалами или другим точным методом.
17. Почему задача о рюкзаке требует целочисленности?
Количество неделимых предметов задают целыми переменными. Дробная линейная релаксация может выбрать часть предмета и дать лишь верхнюю оценку для максимизации. Жадный выбор по прибыли на единицу веса решает классическую дробную задачу, но в целочисленной может проиграть из-за остатка вместимости. Различайте неограниченное число экземпляров каждого типа и вариант, где каждый предмет разрешён не более одного раза.
18. Как определить состояние в динамическом программировании?
Состояние должно сохранять всю информацию прошлого, которая влияет на доступные будущие действия и их последствия. Принцип оптимальности позволяет заменить хвост оптимальной стратегии оптимальным хвостом из достигнутого состояния. Для рюкзака состоянием может быть остаток вместимости; для игр — число камней и игрок, чей ход. Если два разных прошлого с одинаковым «состоянием» имеют разные будущие возможности, состояние выбрано недостаточно подробно.
19. Как записать уравнение Беллмана?
Для конечного горизонта Vₜ(s)=maxₐ{rₜ(s,a)+E[Vₜ₊₁(S′)|s,a]} с заданным терминальным Vₜₑᵣₘ. Решают обратной индукцией. Для конечной модели с ограниченными наградами и дисконтированием 0≤β<1 уравнение V(s)=maxₐ{r(s,a)+βEV(S′)} имеет единственную ограниченную неподвижную точку. Без дисконтирования нельзя автоматически считать бесконечную сумму наград конечной; нужен другой критерий или дополнительные условия.
20. Что такое выпуклая функция и чем полезна выпуклость?
Функция f выпукла на выпуклой области, если f(tx+(1−t)y)≤tf(x)+(1−t)f(y). Для дифференцируемой выпуклой функции график лежит выше любой касательной: f(y)≥f(x)+∇f(x)ᵀ(y−x). Поэтому ∇f(x*)=0 даёт глобальный минимум в безусловной задаче. Каждый локальный минимум выпуклой задачи глобален. Строгая выпуклость обеспечивает не более одной минимальной точки, но не сама по себе её существование.
21. Что дают градиент и матрица Гессе?
Градиент содержит первые производные и задаёт направление наибольшего локального роста в евклидовой норме. Гессе — матрица вторых производных. Для дважды дифференцируемой функции на открытой выпуклой области положительная полуопределённость Гессе в каждой точке характеризует выпуклость. В стационарной точке положительно определённый Гессе достаточен для строгого локального минимума. Полуопределённость только в одной точке не решает вопрос: нужны дальнейшие условия.
22. Как применять множители Лагранжа?
Для min f(x) при h(x)=0 строят L=f+νᵀh. Если градиенты равенств линейно независимы в локальном оптимуме, существуют ν с ∇ₓL=0 и h=0. Эти уравнения дают кандидатов, которые нужно проверить по допустимости, локальному типу и сравнению значений. Они не являются универсальным доказательством глобального минимума. При нарушении регулярности оптимальная точка может не удовлетворять обычной системе множителей.
23. Как записать условия Каруша — Куна — Таккера?
Для min f при gᵢ≤0,hⱼ=0 условия ККТ: допустимость, λᵢ≥0, λᵢgᵢ=0 и ∇f+Σλᵢ∇gᵢ+Σνⱼ∇hⱼ=0. Необходимость в локальном оптимуме требует квалификации ограничений. В дифференцируемой выпуклой задаче с выпуклыми gᵢ и аффинными hⱼ выполненные ККТ достаточны для глобальной оптимальности. Условие Слейтера — типичный способ обеспечить существование множителей в подходящей выпуклой постановке.
24. Как выбирать шаг градиентного спуска?
Итерация xₖ₊₁=xₖ−α∇f(xₖ). Для функции с L-липшицевым градиентом шаг 0<α≤1/L обеспечивает оценку убывания цели; при выпуклости и существовании минимума действуют стандартные гарантии сходимости значений. Слишком большой шаг может вызвать расходимость даже на квадратной функции. В невыпуклой задаче уменьшение нормы градиента не является доказательством глобального оптимума. Для ограничений нужны допустимые переходы, например проекция.
25. Чем метод Ньютона отличается от градиентного спуска?
Ньютоновское направление решает ∇²f(xₖ)dₖ=−∇f(xₖ) и учитывает локальную кривизну. При регулярном положительно определённом Гессе и хорошей близости к решению возможна быстрая локальная сходимость. Из далёкого старта полный шаг может быть неудачным; используют поиск шага, регуляризацию или доверительную область. Необратимый или неопределённый Гессе требует отдельного обращения. Один малый шаг алгоритма не служит сертификатом оптимальности.
26. Как доказать результат вычислительного алгоритма?
Проверяют допустимость, значение цели и отдельный сертификат: двойственный зазор, условия оптимальности или строгую верхнюю/нижнюю оценку. Для точной линейной задачи равенство прямой и двойственной целей даёт доказательство. Для целочисленной полезны полный перебор малой задачи и доказанная граница. Сообщение программы «успех» или совпадение нескольких запусков сами по себе не исключают неверной постановки, ошибки округления или локального решения.
27. Когда применим алгоритм Дейкстры?
Дейкстра находит кратчайшие пути от одной вершины в графе с неотрицательными весами рёбер. Он фиксирует вершину с минимальной текущей меткой и релаксирует исходящие рёбра. С отрицательными весами это правило в общем случае неверно: нужен другой алгоритм и проверка отрицательных циклов. Для ориентированного графа направление рёбер существенно. Нулевая длина пути вершины к самой себе отличается от отсутствия петли в исходной матрице.
28. Как связаны максимальный поток и минимальный разрез?
Допустимый поток не превышает пропускные способности и сохраняется во внутренних вершинах. Его значение не больше ёмкости любого разреза, отделяющего источник от стока. Теорема о максимальном потоке и минимальном разрезе говорит, что эти оптимальные значения равны. Поток и разрез одинаковой величины — проверяемый сертификат оптимальности. В остаточной сети учитывают и прямые возможности увеличения, и обратные возможности отменить уже проведённый поток.
Разобранный пример и проверка
Рассмотрим f(x,y)=(x−2)²+2(y+1)². Градиент (2x−4,4y+4), Гессе diag(2,4). Функция строго выпукла, и единственный глобальный минимум (2,−1) имеет значение 0. Константа липшицевости градиента L=4.
| Итерация k | xₖ | yₖ | f(xₖ,yₖ) |
|---|---|---|---|
| 0 | 0 | 0 | 6 |
| 1 | 1 | −1 | 1 |
| 2 | 3/2 | −1 | 1/4 |
| 3 | 7/4 | −1 | 1/16 |
Из (0,0) с шагом α=1/4 градиентный спуск сразу приводит y к −1, а ошибку x−2 каждый раз уменьшает вдвое. Для k≥1 имеем xₖ=2−2·2⁻ᵏ, yₖ=−1, fₖ=4·4⁻ᵏ. Таблица проверена точными дробями. Ньютон для этой квадратичной функции с обратимым Гессе достигает (2,−1) за один полный шаг из любого старта.
Сертификат глобальности здесь не сам ход итераций, а представление f как суммы неотрицательных квадратов. В точке (2,−1) оба квадрата равны нулю. Для другой, невыпуклой функции такое заключение по одной траектории алгоритма было бы необоснованным.
Как готовить устный ответ
Сначала сформулируйте определение и условия результата. Затем объясните, зачем он нужен, приведите короткий пример и назовите типичную ошибку. Формулу проверяйте на простом или граничном случае. У преподавателя может быть другой перечень тем; сопоставьте его с оглавлением этой страницы.
Источники тематического охвата
Перечень вопросов и все ответы составлены редакцией damirock.com. Официальные программы ниже использованы для сверки тем, а не как источник готовых ответов. Проверка источников: 8 октября 2026 года. НИУ ВШЭ: «Методы оптимизации в машинном обучении», программа 2025/2026; Борис Демешев: открытый задачник по методам оптимальных решений, закреплённая редакция (CC0).
Проверить понимание на задачах
Выберите разбор по теме: условие, ход решения, проверка и типичная ошибка приведены отдельно.