Парето-фронт (его ещё называют границей Парето или кривой Парето) — это множество всех Парето-эффективных решений в многокритериальной оптимизации. Проще говоря, когда в задаче несколько целей, Парето-фронт собирает такие решения, среди которых ни одно не лучше другого сразу по всем критериям, но при этом любое решение вне этого множества хуже хотя бы одного из них по всем критериям. Концепцию широко используют в инженерии: она позволяет проектировщику не перебирать все возможные комбинации параметров, а сосредоточиться на наборе эффективных вариантов и уже внутри него выбирать компромиссы.
Классический пример: на графике точка C не лежит на фронте, потому что её доминируют точки A и B — обе лучше по всем показателям. А вот A и B не доминируются никем, поэтому они на фронте. В экономике производства красная линия на графике производственных возможностей — это Парето-эффективная граница; точки вне её, например N и K, не эффективны, так как существуют точки на границе, которые их доминируют.
Формально пусть f: X → R^m, где X — компактное множество допустимых решений в метрическом пространстве, а Y — множество всех возможных векторов критериев. Точка y'' строго доминирует y', если она лучше по всем критериям. Тогда Парето-фронт P(Y) — это множество точек из Y, для которых не существует другой точки из Y, которая их строго доминирует.
В экономике важное свойство: в Парето-оптимальном распределении предельная норма замещения одинакова для всех потребителей. Если есть m потребителей и n благ, у каждого своя функция полезности, а суммарное потребление каждого блага ограничено, то из максимизации лагранжиана и условий первого порядка следует, что отношения предельных полезностей двух благ у всех потребителей равны.
Построить полный Парето-фронт часто вычислительно трудно, поэтому используют приближённые алгоритмы. Legriel с коллегами называют множество S ε-аппроксимацией фронта P, если направленное расстояние Хаусдорфа между S и P не больше ε. Они выяснили, что ε-аппроксимацию любого Парето-фронта в d измерениях можно получить за (1/ε)^d запросов. Zitzler, Knowles и Thiele сравнили разные алгоритмы приближения по таким критериям, как инвариантность к масштабированию, монотонность и вычислительная сложность.