Dissecting the duality gap : the supporting hyperplane interpretation revisited

• We revisit the classic supporting hyperplane illustration of the duality gap for non-convex optimization problems. It is refined by dissecting the duality gap into two terms: the first measures the degree of near-optimality in a Lagrangian relaxation, while the second measures the degree of near-complementarity in the Lagrangian relaxed constraints. We also give an example of how this dissection may be exploited in the design of a solution approach within discrete optimization.

Ämnesord

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

Nyckelord

Non-convex optimization

Duality gap

Lagrangian relaxation

Global optimality conditions

Set covering problem

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)