Linear programming, simplex и greedy
Что сказать про линейное программирование, simplex-метод и жадные алгоритмы, если спрашивают на техническом ML-интервью?
Короткий ответ
LP оптимизирует линейную цель при линейных ограничениях; simplex ходит по вершинам допустимого многогранника; greedy делает локально лучший выбор и требует доказательства корректности.
Полный разбор
Линейное программирование формулируется как оптимизация линейной функции при линейных ограничениях. Геометрически допустимая область - многогранник, а оптимум, если он существует, достигается в одной из его вершин. Simplex-метод использует эту структуру и переходит между вершинами, улучшая целевую функцию.
Жадный алгоритм проще по идее: на каждом шаге выбирает локально лучший вариант. Но он корректен не всегда; нужно доказывать greedy choice property или exchange argument. Примеры, где greedy работает: Dijkstra с неотрицательными весами, activity selection, Huffman coding. Пример, где наивный greedy ломается: 0/1 knapsack.
Для ML-интервью достаточно показать понимание постановки, ограничений и того, что optimization algorithms требуют условий применимости.
Теория
И simplex, и greedy используют структуру задачи; без этой структуры локальный выбор может не дать глобальный оптимум.
Типичные ошибки
- Говорить, что greedy всегда дает оптимум.
- Не отличать LP от произвольной нелинейной оптимизации.
- Не уметь привести пример, где greedy ломается.
Как отвечать на собеседовании
- Для simplex скажи "vertices of feasible polytope".
- Для greedy сразу добавь, что нужна доказуемая применимость.