In
optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
s in
applied mathematics
Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathematical s ...
, the duality gap is the difference between the
primal and dual solutions. If
is the optimal dual value and
is the optimal primal value then the duality gap is equal to
. This value is always greater than or equal to 0 (for minimization problems). The duality gap is zero if and only if
strong duality Strong duality is a condition in mathematical optimization in which the primal optimal objective and the dual optimal objective are equal. This is as opposed to weak duality (the primal problem has optimal value smaller than or equal to the dual ...
holds. Otherwise the gap is strictly positive and
weak duality In applied mathematics, weak duality is a concept in optimization which states that the duality gap is always greater than or equal to 0. That means the solution to the dual (minimization) problem is ''always'' greater than or equal to the solution ...
holds.
In general given two
dual pair
In mathematics, a dual system, dual pair, or duality over a field \mathbb is a triple (X, Y, b) consisting of two vector spaces X and Y over \mathbb and a non-degenerate bilinear map b : X \times Y \to \mathbb.
Duality theory, the study of dual ...
s
separated locally convex space
In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vec ...
s
and
. Then given the function
, we can define the primal problem by
:
If there are constraint conditions, these can be built into the function
by letting
where
is the
indicator function
In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
. Then let
be a
perturbation function In mathematical optimization, the perturbation function is any function which relates to primal and dual problems. The name comes from the fact that any such function defines a perturbation of the initial problem. In many cases this takes the form ...
such that
. The ''duality gap'' is the difference given by
: