In constrained optimization,it is often possible to convert the primal problem (i.e. theoriginal form of the optimization problem) to a dual form, which istermed a dual problem. Usually dual problem refers to theLagrangian dual problem but other dual problems are used,for example, the Wolfe dualproblem and the Fencheldual problem. The Lagrangian dual problem is obtained byforming the Lagrangian,using nonnegative Lagrangemultipliers to add the constraints to the objective function,and then solving for some primal variable values that minimize theLagrangian. This solution gives the primal variables as functionsof the Lagrange multipliers, which are called dual variables, sothat the new problem is to maximize the objective function withrespect to the dual variables under the derived constraints on thedual variables (including at least the nonnegativity).

The solution of the dual problem provides a lower bound to thesolution of the primal problem.^[1]However in general the optimal values of the primal and dualproblems need not be equal. Their difference is called theduality gap. Forconvexoptimization problems, the duality gap is zero under aconstraintqualification condition. Thus, a solution to the dual problemprovides a bound on the value of the solution to the primalproblem; when the problem is convex and satisfies a constraintqualification, then the value of an optimal solution of the primalproblem is given by the dual problem.

[edit]Dualityprinciple

In optimization theory, the duality principle states thatoptimization problems may be viewed from either of twoperspectives, the primal problem or the dual problem.

In general given two dual pairs separatedlocally convexspaces and . Then given the function , we can define the primal problem as finding such that

In other words, is the infimum (greatest lowerbound) of the function .

If there are constraint conditions, these can be built in to thefunction by letting where is the indicator function. Then let be a perturbationfunction such that .^[2]

The duality gap is thedifference of the right and left hand sides of the inequality

where is the convexconjugate in both variables and denotes the supremum (least upperbound).^[2][3][4]

[edit]Duality gap

The duality gap is the difference between the values ofany primal solutions andany 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. The duality gapis zero if and only if strong dualityholds. Otherwise the gap is strictly positive and weak dualityholds.^[5]

In computational optimization, another "duality gap" is oftenreported, which is the difference in value between any dualsolution and the value of a feasible but suboptimal iterate for theprimal problem. This alternative "duality gap" quantifies thediscrepancy between the value of a current feasible but suboptimaliterate 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 convexrelaxation is the problem arising replacing a non-convex feasibleset with its closed convex hull and withreplacing a non-convex function with its convex closure,that is the function that has the epigraphthat is the closed convex hull of the original primal objectivefunction.^{[6][7][8][9][10][11][12][13][14]}

[edit]The linearcase

Linearprogramming problems are optimizationproblems in which the objectivefunction and the constraintsare all linear. In the primalproblem, the objective function is a linear combination of nvariables. There are m constraints, each of which places anupper bound on a linear combination of the n variables. Thegoal is to maximize the value of the objective function subject tothe constraints. A solution is a vector (a list)of n values that achieves the maximum value for theobjective function.

In the dual problem, the objective function is a linearcombination of the m values that are the limits in them constraints from the primal problem. There are ndual constraints, each of which places a lower bound on a linearcombination of m dual variables.

[edit]Relationship between the primal problem and thedual problem

In the linear case, in the primal problem, from each sub-optimalpoint that satisfies all the constraints, there is a direction orsubspace ofdirections to move that increases the objective function. Moving inany such direction is said to remove slack between the candidatesolution and one or more constraints. An infeasible value ofthe candidate solution is one that exceeds one or more of theconstraints.

In the dual problem, the dual vector multiplies the constantsthat determine the positions of the constraints in the primal.Varying the dual vector in the dual problem is equivalent torevising the upper bounds in the primal problem. The lowest upperbound is sought. That is, the dual vector is minimized in order toremove slack between the candidate positions of the constraints andthe actual optimum. An infeasible value of the dual vector is onethat is too low. It sets the candidate positions of one or more ofthe constraints in a position that excludes the actual optimum.

This intuition is made formal by the equations in Linearprogramming: Duality.

[edit]Economicinterpretation

If we interpret our primal LP problem as a classical "ResourceAllocation" problem, its dual can be interpreted as a "ResourceValuation" problem.

[edit]The non-linearcase

In non-linearprogramming, 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 beidentified easily, the problem formulation often requires that thefunctions be convex and have compact lower level sets.

This is the significance of the Karush–Kuhn–Tucker conditions. They provide necessaryconditions for identifying local optima of non-linear programmingproblems. There are additional conditions (constraintqualifications) that are necessary so that it will be possible todefine the direction to an optimal solution. An optimalsolution is one that is a local optimum, but possibly not a globaloptimum.

[edit]The strong Lagrangian principle: Lagrange duality

Given a nonlinearprogramming 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 multipliervectors associated with the problem. The Lagrange dualfunction is defined as

The dual function g is concave, even when the initialproblem is not convex. The dual function yields lower bounds on theoptimal value of the initial problem; for any and any we have .

If a constraintqualification such as Slater'scondition holds and the original problem is convex, then wehave strong duality,i.e. .

[edit]Convexproblems

For a convex minimization problem with inequalityconstraints,

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 thegradient is equal to zero. The problem

is called the Wolfe dual problem. This problem may be difficultto deal with computationally, because the objective function is notconcave in the joint variables . Also, the equality constraint is nonlinear in general, so the Wolfe dual problem is typically anonconvex optimization problem. In any case, weak dualityholds.^[15]

=======================================================

Duality(mathematics)

In mathematics, aduality, generally speaking, translates concepts, theoremsor mathematical structures into other concepts, theorems orstructures, in a one-to-one fashion, often (but not always) bymeans of an involutionoperation: if the dual of A is B, then the dual ofB is A. As involutions sometimes have fixedpoints, the dual of A is sometimes A itself. Forexample, Desargues'theorem in projectivegeometry is self-dual in this sense.

In mathematical contexts, duality has numerous meanings,and although it is “a very pervasive and important concept in(modern) mathematics”^[1]and “an important general theme that has manifestations in almostevery area of mathematics”,^[2]there is no single universally agreed definition that unifies allconcepts of duality.^[2]

Many mathematical dualities between objects of two typescorrespond to pairings, bilinearfunctions from an object of one type and another object of thesecond type to some family of scalars. For instance, linear algebraduality corresponds in this way to bilinear maps from pairs ofvector spaces to scalars, the duality between distributionsand the associated testfunctions corresponds to the pairing in which one integrates adistribution against a test function, and Poincaréduality corresponds similarly to intersectionnumber, viewed as a pairing between submanifolds of a givenmanifold.^[3]

Duality can also be seen as a functor, at least in therealm of vector spaces. There it is allowed to assign to each spaceits dual space and the pullback construction allows to assign foreach arrow f: V → W, its dual f*:V* → W*.

[edit]Order-reversing dualities

A particularly simple form of duality comes from order theory. Thedual of aposet P =(X, ≤) is the poset P^d = (X, ≥)comprising the same ground set but the converserelation. Familiar examples of dual partial orders include

A concept defined for a partial order P will correspondto a dual concept on the dual poset P^d.For instance, a minimalelement of P will be a maximal elementof P^d: minimality and maximality are dualconcepts in order theory. Other pairs of dual concepts areupper andlower bounds, lower sets andupper sets, andideals andfilters.

A particular order reversal of this type occurs in the family ofall subsets of some set S: if denotes the complement set,then A ⊂ B if and only if . In topology, open sets and closedsets are dual concepts: the complement of an open set isclosed, and vice versa. In matroid theory, thefamily of sets complementary to the independent sets of a givenmatroid themselves form another matroid, called the dual matroid. Inlogic, one may represent atruthassignment to the variables of an unquantified formula as aset, the variables that are true for the assignment. A truthassignment satisfies the formula if and only if the complementarytruth assignment satisfies the De Morgan dual ofits formula. The existential and universal quantifiers in logic aresimilarly dual.

A partial order may be interpreted as a categoryin which there is an arrow from x to y in thecategory if and only ifx≤y in thepartial order. The order-reversing duality of partial orders can beextended to the concept of a dual category, thecategory formed by reversing all the arrows in a given category.Many of the specific dualities described later are dualities ofcategories in this sense.

According to Artstein-Avidan and Milman,^[4][5]a duality transform is just an involutiveantiautomorphism of a partiallyordered set S, that is, an order-reversing involution Surprisingly, in several important cases these simple propertiesdetermine the transform uniquely up to some simple symmetries. If are two duality transforms then their compositionis an orderautomorphism of S; thus, any two duality transformsdiffer only by an order automorphism. For example, all orderautomorphisms of a power setS=2^Rare induced by permutations of R. The papers cited abovetreat only sets S of functions onRⁿ satisfying some condition of convexityand prove that all order automorphisms are induced by linear oraffine transformationsofRⁿ.

[edit]Dimension-reversing dualities

There are many distinct but interrelated dualities in whichgeometric or topological objects correspond to other objects of thesame type, but with a reversal of the dimensions of the features ofthe objects. A classical example of this is the duality of theplatonic solids,in which the cube and the octahedron form a dual pair, thedodecahedron and the icosahedron form a dual pair, and thetetrahedron is self-dual. The dualpolyhedron of any of these polyhedra may be formed as theconvex hull of thecenter points of each face of the primal polyhedron, so thevertices ofthe dual correspond one-for-one with the faces of the primal.Similarly, each edge of the dual corresponds to an edge of theprimal, and each face of the dual corresponds to a vertex of theprimal. These correspondences are incidence-preserving: if twoparts of the primal polyhedron touch each other, so do thecorresponding two parts of the dual polyhedron.More generally, using the concept of polarreciprocation, any convexpolyhedron, or more generally any convexpolytope, corresponds to a dual polyhedronor dual polytope, with an i-dimensional feature of ann-dimensional polytope corresponding to an(n−i−1)-dimensionalfeature of the dual polytope. The incidence-preserving nature ofthe duality is reflected in the fact that the face lattices ofthe primal and dual polyhedra or polytopes are themselves order-theoretic duals. Duality of polytopes and order-theoreticduality are both involutions:the dual polytope of the dual polytope of any polytope is theoriginal polytope, and reversing all order-relations twice returnsto the original order. Choosing a different center of polarityleads to geometrically different dual polytopes, but all have thesame combinatorial structure.

From any three-dimensional polyhedron, one can form a planar graph, thegraph of its vertices and edges. The dual polyhedron has adual graph, a graphwith one vertex for each face of the polyhedron and with one edgefor every two adjacent faces. The same concept of planar graphduality may be generalized to graphs that are drawn in the planebut that do not come from a three-dimensional polyhedron, or moregenerally to graph embeddingson surfaces of higher genus: one may draw a dual graph by placingone vertex within each region bounded by a cycle of edges in theembedding, and drawing an edge connecting any two regions thatshare a boundary edge. An important example of this type comes fromcomputationalgeometry: the duality for any finite set S of points inthe plane between the Delaunaytriangulation of S and the Voronoidiagram of S. As with dual polyhedra and dual polytopes,the duality of graphs on surfaces is a dimension-reversinginvolution: each vertex in the primal embedded graph corresponds toa region of the dual embedding, each edge in the primal is crossedby an edge in the dual, and each region of the primal correspondsto a vertex of the dual. The dual graph depends on how the primalgraph is embedded: different planar embeddings of a single graphmay lead to different dual graphs. Matroid dualityis an algebraic extension of planar graph duality, in the sensethat the dual matroid of the graphic matroid of a planar graph isisomorphic to the graphic matroid of the dual graph.

In topology, Poincaréduality also reverses dimensions; it corresponds to the factthat, if a topological manifold isrespresented as a cell complex, thenthe dual of the complex (a higher dimensional generalization of theplanar graph dual) represents the same manifold. In Poincaréduality, this homeomorphism is reflected in an isomorphism of thekth homologygroup and the(n−k)th cohomology group.

Another example of a dimension-reversing duality arises inprojectivegeometry.^[6]In the projectiveplane, it is possible to find geometrictransformations that map each point of the projective plane toa line, and each line of the projective plane to a point, in anincidence-preserving way: in terms of the incidencematrix of the points and lines in the plane, this operation isjust that of forming the transpose.Transformations of this type exist also in any higher dimension;one way to construct them is to use the same polartransformations that generate polyhedron and polytope duality.Due to this ability to replace any configuration of points andlines with a corresponding configuration of lines and points, therearises a general principle of dualityin projective geometry: given any theorem in plane projectivegeometry, exchanging the terms "point" and "line" everywhereresults in a new, equally valid theorem.^[7]A simple example is that the statement “two points determine aunique line, the line passing through these points” has the dualstatement that “two lines determine a unique point, the intersectionpoint of these two lines”. For further examples, see Dual theorems.

The points, lines, and higher dimensional subspacesn-dimensional projective space may be interpreted asdescribing the linear subspaces of an(n+1)-dimensionalvector space; ifthis vector space is supplied with an inner product thetransformation from any linear subspace to its perpendicularsubspace is an example of a projective duality. The Hodgedual extends this duality within an inner product space byproviding a canonical correspondence between the elements of theexterioralgebra.

A kind of geometric duality also occurs in optimizationtheory, but not one that reverses dimensions. A linear programmay be specified by a system of real variables (the coordinates fora point in Euclidean space Rⁿ), a systemof linear constraints (specifying that the point lie in a halfspace;the intersection of these halfspaces is a convex polytope, thefeasible region of the program), and a linear function (what tooptimize). Every linear program has a dual problem withthe same optimal solution, but the variables in the dual problemcorrespond to constraints in the primal problem and viceversa.

[edit]Duality in logic and set theory

In logic, functions or relations A and B areconsidered dual if A(¬x) = ¬B(x), where¬ is logicalnegation. The basic duality of this type is the duality of the∃ and ∀ quantifiers. Theseare dual because ∃x.¬P(x) and¬∀x.P(x) are equivalent for all predicatesP: if there exists an x for which P fails tohold, then it is false that P holds for all x. Fromthis fundamental logical duality follow several others:

Other analogous dualities follow from these:

Topology inherits aduality between open and closedsubsets of some fixed topological space X: a subsetU of X is closed if and only if its complement inX is open. Because of this, many theorems about closed setsare dual to theorems about open sets. For example, any union ofopen sets is open, so dually, any intersection of closed sets isclosed. The interior ofa set is the largest open set contained in it, and the closure ofthe set is the smallest closed set that contains it. Because of theduality, the complement of the interior of any set U isequal to the closure of the complement of U.

The collection of all open subsets of a topological spaceX forms a complete Heyting algebra.There is a duality, known as Stone duality,connecting sober spaces andspatial locales.

[edit]Dualobjects

A group of dualities can be described by endowing, for anymathematical object X, the set of morphisms Hom(X,D) into some fixed object D, with a structure similarto the one of X. This is sometimes called internal Hom. Ingeneral, this yields a true duality only for specific choices ofD, in which case X^∗=Hom(X,D) is referred to as the dual of X. It may ormay not be true that the bidual, that is to say, the dual ofthe dual, X^∗∗ =(X^∗)^∗ is isomorphic to X, asthe following example, which is underlying many other dualities,shows: the dual vectorspace V^∗ of a K-vector spaceV is defined as

V^∗ = Hom (V, K).

The set of morphisms, i.e., linear maps, is avector space in its own right. There is always a natural, injectivemap V → V^∗∗ given by v ↦ (f↦ f(v)), where f is an element of the dualspace. That map is an isomorphism if and only if the dimension ofV is finite.

In the realm of topologicalvector spaces, a similar construction exists, replacing thedual by the topological dual vector space. A topological vector space thatis canonically isomorphic to its bidual is called reflexivespace.

The dual lattice of alattice Lis given by

Hom(L, Z),

which is used in the construction of toricvarieties.^[8]The Pontryagin dualof locally compacttopologicalgroups G is given by

Hom(G, S¹),

continuous grouphomomorphisms with values in the circle (with multiplication ofcomplex numbers as group operation).

[edit]Dualcategories

[edit]Opposite category and adjoint functors

In another group of dualities, the objects of one theory aretranslated into objects of another theory and the maps betweenobjects in the first theory are translated into morphisms in thesecond theory, but with direction reversed. Using the parlance ofcategory theory,this amounts to a contravariantfunctor between two categoriesC and D:

F: C → D

which for any two objects X and Y of Cgives a map

Hom_C(X, Y) →Hom_D(F(Y), F(X))

That functor may or may not be an equivalenceof categories. There are various situations, where such afunctor is an equivalence between the oppositecategory C^op of C, and D. Usinga duality of this type, every statement in the first theory can betranslated into a "dual" statement in the second theory, where thedirection of all arrows has to be reversed.^[9]Therefore, any duality between categories C and D isformally the same as an equivalence between C andD^op (C^op and D).However, in many circumstances the opposite categories have noinherent meaning, which makes duality an additional, separateconcept.^[10]

Many category-theoreticnotions come in pairs in the sense that they correspond to eachother while considering the opposite category. For example,Cartesianproducts Y₁ × Y₂ anddisjoint unionsY₁ ⊔ Y₂ of sets are dual toeach other in the sense that

Hom(X, Y₁ × Y₂) =Hom(X, Y₁) × Hom(X,Y₂)

and

Hom(Y₁ ⊔ Y₂, X) =Hom(Y₁, X) × Hom(Y₂,X)

for any set X. This is a particular case of a moregeneral duality phenomenon, under which limitsin a category C correspond to colimitsin the opposite category C^op; further concreteexamples of this are epimorphisms vs.monomorphism, inparticular factor modules (orgroups etc.) vs. submodules, direct productsvs. direct sums(also called coproducts toemphasize the duality aspect). Therefore, in some cases, proofs ofcertain statements can be halved, using such a duality phenomenon.Further notions displaying related by such a categorical dualityare projective andinjectivemodules in homologicalalgebra,^[11]fibrations andcofibrations intopology and more generally modelcategories.^[12]

Two functors F:C → D and G: D → C are adjoint if forall objects c in C and d in D

Hom_D(F(c), d) ≅Hom_C(c, G(d)),

in a natural way. Actually, the correspondence of limits andcolimits is an example of adjoints, since there is anadjunction

between the colimit functor that assigns to any diagram inC indexed by some category I its colimit and thediagonal functor that maps any object c of C to theconstant diagramm which has c at all places. Dually,

[edit]Examples

For example, there is a duality between commutativerings and affine schemes: toevery commutative ring A there is an affine spectrum,SpecA, conversely, given an affine scheme S, one getsback a ring by taking global sections of the structure sheafO_S. In addition, ringhomomorphisms are in one-to-one correspondence with morphismsof affine schemes, thereby there is an equivalence

(Commutative rings)^op ≅ (affine schemes)^[13]

Compare with noncommutativegeometry and Gelfandduality.

In a number of situations, the objects of two categories linkedby a duality are partiallyordered, i.e., there is some notion of an object "beingsmaller" than another one. In such a situation, a duality thatrespects the orderings in question is known as a Galoisconnection. An example is the standard duality in Galois theory(fundamentaltheorem of Galois theory) between fieldextensions and subgroups of theGalois group: abigger field extension corresponds—under the mapping that assignsto any extension L ⊃ K (inside some fixed biggerfield Ω) the Galois group Gal(Ω / L)—to a smallergroup.^[14]

Pontryaginduality gives a duality on the category of locally compactabelian groups:given any such group G, the charactergroup

χ(G) = Hom(G, S¹)

given by continuous group homomorphisms from G to thecircle groupS¹ can be endowed with the compact-opentopology. Pontryagin duality states that the character group isagain locally compact abelian and that

G ≅ χ(χ(G)).^[15]

Moreover, discrete groupscorrespond to compact abeliangroups; finite groups correspond to finite groups. Pontryaginis the background to Fourieranalysis, see below.

Both Gelfand and Pontryagin duality can be deduced in a largelyformal, category-theoretic way.^[17]

[edit]Analyticdualities

In analysis,problems are frequently solved by passing to the dual descriptionof functions and operators.

Fouriertransform switches between functions on a vector space and itsdual:

and conversely

If f is an L²-functionon R or R^N, say, then so is and . Moreover, the transform interchanges operations of multiplicationand convolution on thecorresponding function spaces.A conceptual explanation of the Fourier transform is obtained bythe aforementioned Pontryagin duality, applied to the locallycompact groups R (or R^N etc.): anycharacter of R is given by ξ↦ e^−2πixξ. Thedualizing character of Fourier transform has many othermanifestations, for example, in alternative descriptions ofquantummechanical systems in terms of coordinate and momentumrepresentations.

[edit]Poincaré-style dualities

Theorems showing that certain objects of interest are thedual spaces (in thesense of linear algebra) of other objects of interest are oftencalled dualities. Many of these dualities are given by abilinearpairing of two K-vector spaces

A ⊗ B → K.

For perfectpairings, there is, therefore, an isomorphism of A tothe dual ofB.

For example, Poincaréduality of a smooth compact complexmanifold X is given by a pairing of singular cohomologywith C-coefficients (equivalently, sheafcohomology of the constant sheafC)

Hⁱ(X) ⊗ H²ⁿ⁻ⁱ(X) →C,

where n is the (complex) dimension of X.^[18]Poincaré duality can also be expressed as a relation of singularhomology and de Rhamcohomology, by asserting that the map

(integrating a differential k-form over an2n−k-(real)-dimensional cycle) is a perfectpairing.

The same duality pattern holds for a smooth projectivevariety over a separablyclosed field, using l-adiccohomology with Q_ℓ-coefficientsinstead.^[19]This is further generalized to possibly singularvarieties, using intersectioncohomology instead, a duality called Verdierduality.^[20]With increasing level of generality, it turns out, an increasingamount of technical background is helpful or necessary tounderstand these theorems: the modern formulation of both thesedualities can be done using derivedcategories and certain directand inverse image functors of sheaves, applied to locallyconstant sheaves (with respect to the classical analytical topologyin the first case, and with respect to the étaletopology in the second case).

Yet another group of similar duality statements is encounteredin arithmetics: étalecohomology of finite, local and global fields (alsoknown as Galoiscohomology, since étale cohomology over a field is equivalentto groupcohomology of the (absolute) Galois group of thefield) admit similar pairings. The absolute Galois groupG(F_q) of a finite field, forexample, is isomorphic to , the profinitecompletion of Z, the integers. Therefore, the perfectpair ing (for any G-moduleM)

Hⁿ(G, M) ×H¹⁻ⁿ (G, Hom (M,Q/Z)) → Q/Z^[21]

is a direct consequence of Pontryaginduality of finite groups. For local and global fields, similarstatements exist (local dualityand global or Poitou–Tateduality).^[22]

Serre duality orcoherentduality are similar to the statements above, but applies tocohomology of coherentsheaves instead.^[23]

来源：

http://en.wikipedia.org/wiki/Duality_(optimization)；

http://en.wikipedia.org/wiki/Duality_(mathematics)；

爱华网本文地址 » http://www.413yy.cn/a/25101015/272812.html