Задача коммивояжера (Traveling Salesperson Problem, TSP) — одна из самых известных задач комбинаторной оптимизации. Коммивояжер должен посетить $n$ городов по одному разу и вернуться в исходную точку, пройдя при этом минимальное суммарное расстояние. Несмотря на внешнюю простоту, задача является фундаментальной для теории графов и транспортной логистики.

Задача о рюкзаке (Knapsack Problem) — это классическая задача комбинаторной оптимизации, входящая в список NP-трудных задач. Суть ее заключается в выборе набора предметов с заданным весом и стоимостью, чтобы максимизировать суммарную стоимость при ограничении по общей грузоподъемности рюкзака. Простота постановки контрастирует со сложностью нахождения точного решения при увеличении числа предметов.

Нелинейное программирование охватывает задачи оптимизации, в которых целевая функция или ограничения являются нелинейными. В отличие от линейных задач, здесь локальный экстремум не всегда является глобальным, а сложность алгоритмов зависит от свойств выпуклости функции. Методы градиентного спуска составляют основу итерационных процедур для поиска локального минимума дифференцируемых функций.