In
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
theory, duality or the duality principle is the principle that
optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem (and vice versa). Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem. Therefore, the solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal.
This fact is called weak duality.
In general, the optimal values of the primal and dual problems need not be equal. Their difference is called the
duality gap In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If d^* is the optimal dual value and p^* is the optimal primal value then the duality gap is equal to p^* - d^*. This value ...
. For
convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization probl ...
problems, the duality gap is zero under a
constraint qualification condition. This fact is called strong duality.
Dual problem
Usually the term "dual problem" refers to the ''Lagrangian dual problem'' but other dual problems are used – for example, the
Wolfe dual problem
In mathematical optimization, Wolfe duality, named after Philip Wolfe, is type of dual problem in which the objective function and constraints are all differentiable functions. Using this concept a lower bound for a minimization problem can be f ...
and the
Fenchel dual problem. The Lagrangian dual problem is obtained by forming the
Lagrangian
Lagrangian may refer to:
Mathematics
* Lagrangian function, used to solve constrained minimization problems in optimization theory; see Lagrange multiplier
** Lagrangian relaxation, the method of approximating a difficult constrained problem with ...
of a minimization problem by using nonnegative
Lagrange multipliers to add the constraints to the objective function, and then solving for the primal variable values that minimize the original objective function. This solution gives the primal variables as functions of the Lagrange multipliers, which are called dual variables, so that the new problem is to maximize the objective function with respect to the dual variables under the derived constraints on the dual variables (including at least the nonnegativity constraints).
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 of
separated locally convex spaces
and
and the function
, we can define the primal problem as finding
such that
In other words, if
exists,
is the
minimum
In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given ran ...
of the function
and the
infimum (greatest lower bound) of the function is attained.
If there are constraint conditions, these can be built into the function
by letting
where
is a suitable function on
that has a minimum 0 on the constraints, and for which one can prove that
. The latter condition is trivially, but not always conveniently, satisfied for the
characteristic function (i.e.
for
satisfying the constraints and
otherwise). Then extend
to 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 In optimization problems in applied mathematics, the duality gap is the difference between the primal and dual solutions. If d^* is the optimal dual value and p^* is the optimal primal value then the duality gap is equal to p^* - d^*. This value ...
is the difference of the right and left hand sides of the inequality
:
where
is the
convex conjugate in both variables and
denotes the
supremum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
(least upper bound).
Duality gap
The duality gap is the difference between the values of any primal solutions and any 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 holds.
In computational optimization, another "duality gap" is often reported, which is the difference in value between any dual solution and the value of a feasible but suboptimal iterate for the primal problem. This alternative "duality gap" quantifies the discrepancy between the value of a current feasible but suboptimal iterate for the primal problem and the value of the dual problem; the value of the dual problem is, under regularity conditions, equal to the value of the ''convex relaxation'' of the primal problem: The convex relaxation is the problem arising replacing a non-convex feasible set with its closed
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
and with replacing a non-convex function with its convex
closure, that is the function that has the
epigraph that is the closed convex hull of the original primal objective function.
Linear case
Linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
problems are
optimization problems in which the
objective function and the
constraints are all
linear
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
. In the primal problem, the objective function is a linear combination of ''n'' variables. There are ''m'' constraints, each of which places an upper bound on a linear combination of the ''n'' variables. The goal is to maximize the value of the objective function subject to the constraints. A ''solution'' is a
vector (a list) of ''n'' values that achieves the maximum value for the objective function.
In the dual problem, the objective function is a linear combination of the ''m'' values that are the limits in the ''m'' constraints from the primal problem. There are ''n'' dual constraints, each of which places a lower bound on a linear combination of ''m'' dual variables.
Relationship between the primal problem and the dual problem
In the linear case, in the primal problem, from each sub-optimal point that satisfies all the constraints, there is a direction or
subspace of directions to move that increases the objective function. Moving in any such direction is said to remove slack between the
candidate solution and one or more constraints. An ''infeasible'' value of the candidate solution is one that exceeds one or more of the constraints.
In the dual problem, the dual vector multiplies the constraints that determine the positions of the constraints in the primal. Varying the dual vector in the dual problem is equivalent to revising the upper bounds in the primal problem. The lowest upper bound is sought. That is, the dual vector is minimized in order to remove slack between the candidate positions of the constraints and the actual optimum. An infeasible value of the dual vector is one that is too low. It sets the candidate positions of one or more of the constraints in a position that excludes the actual optimum.
This intuition is made formal by the equations in
Linear programming: Duality.
Nonlinear case
In
nonlinear programming
In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or sta ...
, the constraints are not necessarily linear. Nonetheless, many of the same principles apply.
To ensure that the global maximum of a non-linear problem can be identified easily, the problem formulation often requires that the functions be convex and have compact lower level sets.
This is the significance of the
Karush–Kuhn–Tucker conditions
In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be o ...
. They provide necessary conditions for identifying local optima of non-linear programming problems. There are additional conditions (constraint qualifications) that are necessary so that it will be possible to define the direction to an ''optimal'' solution. An optimal solution is one that is a local optimum, but possibly not a global optimum.
The strong Lagrangian principle: Lagrange duality
Given a
nonlinear programming
In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or sta ...
problem in standard form
:
with the domain
having non-empty interior, the ''Lagrangian function''
is defined as
:
The vectors
and
are called the ''dual variables'' or ''Lagrange multiplier vectors'' associated with the problem. The ''Lagrange dual function''
is defined as
:
The dual function ''g'' is concave, even when the initial problem is not convex, because it is a point-wise infimum of affine functions. The dual function yields lower bounds on the optimal value
of the initial problem; for any
and any
we have
.
If a
constraint qualification such as
Slater's condition
In mathematics, Slater's condition (or Slater condition) is a sufficient condition for strong duality to hold for a convex optimization problem, named after Morton L. Slater. Informally, Slater's condition states that the feasible region must h ...
holds and the original problem is convex, then we have
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 ...
, i.e.
.
Convex problems
For a convex minimization problem with inequality constraints,
:
the Lagrangian dual problem is
:
where the objective function is the Lagrange dual function. Provided that the functions
and
are continuously differentiable, the infimum occurs where the gradient is equal to zero. The problem
:
is called the Wolfe dual problem. This problem may be difficult to deal with computationally, because the objective function is not concave in the joint variables
. Also, the equality constraint
is nonlinear in general, so the Wolfe dual problem is typically a nonconvex optimization problem. In any case,
weak duality holds.
History
According to
George Dantzig, the duality theorem for linear optimization was conjectured by
John von Neumann
John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest cove ...
immediately after Dantzig presented the linear programming problem. Von Neumann noted that he was using information from his
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, and conjectured that two person zero sum matrix game was equivalent to linear programming. Rigorous proofs were first published in 1948 by
Albert W. Tucker
Albert William Tucker (28 November 1905 – 25 January 1995) was a Canadian mathematician who made important contributions in topology, game theory, and non-linear programming.
Biography
Albert Tucker was born in Oshawa, Ontario, Canada, and ea ...
and his group. (Dantzig's foreword to Nering and Tucker, 1993)
See also
*
Convex duality
In mathematics and mathematical optimization, the convex conjugate of a function is a generalization of the Legendre transformation which applies to non-convex functions. It is also known as Legendre–Fenchel transformation, Fenchel transformati ...
*
Duality
Duality may refer to:
Mathematics
* Duality (mathematics), a mathematical concept
** Dual (category theory), a formalization of mathematical duality
** Duality (optimization)
** Duality (order theory), a concept regarding binary relations
** Dual ...
*
Relaxation (approximation) In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an approximation of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about t ...
Notes
References
Books
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Articles
*
*
Duality in Linear ProgrammingGary D. Knott
{{Convex analysis and variational analysis
Convex optimization
Linear programming