Can a nonconvex primal have a convex dual optimization problem?

Yes. Maximizing its concave dual function over convex multiplier constraints is a convex optimization problem.

Must primal and dual optimal values agree?

No; a positive duality gap can remain.

AI Glossary / Mathematics and optimization / Advanced

Dual problem

Definition

A dual problem is an optimization problem constructed from another problem, called the primal, to obtain bounds on its best objective value. In the Lagrange-dual setting considered here, a minimization problem gives rise to a maximization problem over constraint multipliers. Each admissible multiplier choice produces a lower bound on the primal minimum; the dual seeks the strongest bound obtainable from that construction.

What it means

The primal asks which feasible decision achieves the lowest cost. Its dual asks how high a lower bound on that cost can be raised. A feasible decision supplies an upper bound on the minimum, while a dual-feasible choice supplies a lower bound.
When those bounds agree, they certify the optimal value. They need not agree for every problem. Understanding the dual therefore requires distinguishing a valid bound from an exact reformulation. A useful dual can provide evidence about solution quality even when it does not reproduce the primal optimum.

How it works

Write inequalities in the form fᵢ(x) ≤ 0 and equalities as hⱼ(x) = 0. The Lagrangian adds λᵢfᵢ(x) and νⱼhⱼ(x) to the objective. Inequality multipliers λᵢ are nonnegative; equality multipliers νⱼ are unrestricted.
The dual function takes the infimum of this Lagrangian over the original variable domain, without imposing the constraints already moved into it. For feasible x, the added inequality terms are nonpositive and equality terms vanish. Thus the infimum is a lower bound on every feasible objective value.
The dual maximizes this function over admissible multipliers. The dual function is concave, even when the primal is nonconvex. Some multiplier choices yield minus infinity and provide no useful finite bound. Strong duality means equality of the optimal values, and requires suitable conditions rather than following automatically from the construction.

Three practical examples

An optimization team compares the cost of a feasible plan with a dual lower bound. A small difference can certify that little further cost reduction is possible within the model, even before the exact optimum is located.
A resource-allocation model associates multipliers with capacity constraints. Under appropriate sensitivity conditions, optimal multipliers help interpret the effect of changing a constraint. Their meaning depends on the formulation and sign convention.
A decomposition method uses constraint multipliers to coordinate subproblems. The dual structure can separate some calculations, but recovering a feasible primal decision remains a distinct requirement when intermediate solutions violate coupling constraints.

Think of it this way

Think of comparing a price you can actually achieve with a floor below which no valid offer can fall. The price is evidence from a feasible solution. The floor is evidence from a bound. If they meet, the search is settled. A floor below the best offer can still be useful without proving that the offer itself is optimal.

Worked example

Consider minimizing f(x) = (x − 3)² subject to x ≥ 5, with x a real number. The unconstrained preferred value three is disallowed. Over x ≥ 5, the smallest cost is attained at x = 5 and equals four.
Rewrite the constraint as 5 − x ≤ 0. The Lagrangian is L(x, λ) = (x − 3)² + λ(5 − x), with λ ≥ 0. For a fixed λ, minimize over all real x. The derivative 2(x − 3) − λ is zero at x = 3 + λ/2, and the positive quadratic coefficient confirms this is the minimum.
Substitution gives g(λ) = 2λ − λ²/4. Equivalently, g(λ) = 4 − (λ − 4)²/4. The dual problem is therefore to maximize this expression over λ ≥ 0. Its maximum is four at λ = 4.
The feasible primal point x = 5 has cost four, and the dual choice λ = 4 supplies a lower bound of four. Together they certify optimality. At λ = 2, the lower bound is only three. The corresponding Lagrangian minimizer is x = 4, which violates the primal constraint; this is permitted in the inner dual calculation and does not make it a feasible recommendation.

Illustrative case study

In a fictional planning exercise using the worked model, a solver proposes x = 6, with cost nine. An analyst also computes the dual bound g(2) = 3. These results establish that the unknown optimal cost lies between three and nine; they do not certify the proposed decision as optimal.
A better feasible proposal x = 5 lowers the upper bound to four. Improving the multiplier to λ = 4 raises the lower bound to four. The team can now explain why further improvement is impossible under the stated model, instead of relying only on the solver's recent progress.
A numerically attractive objective from an infeasible point is not a valid primal upper bound, and an invalid multiplier or incorrectly evaluated infimum is not a valid dual lower bound.

Common misconceptions and mistakes

A dual problem is not formed by simply changing minimize to maximize or negating the objective. The multiplier signs, Lagrangian and inner infimum are essential. Its variables are generally different from the primal decision variables.
Weak duality guarantees the lower-bound relationship, while strong duality states equality of optimal values. Convexity supports strong-duality results but must be accompanied by the applicable regularity conditions. A solution of the dual also does not automatically provide a usable primal solution without recovery and feasibility checks.

Business use

Dual problems help explain bounds, assess optimization progress and, under stated conditions, interpret constraint sensitivity. Report the best feasible objective and the justified dual bound in the same units and sign convention. State whether equality has been established or a gap remains. Keep conclusions tied to the model: a mathematical certificate establishes optimality for its objective and constraints, not the completeness of the underlying business assumptions.

Check your understanding

Why must λ be nonnegative here?

Answer: The constraint is written as 5 − x ≤ 0, making its multiplier term nonpositive at feasible points.

What is the best dual multiplier?

Answer: Four.

What certifies the optimum?

Answer: A feasible cost and a dual lower bound that both equal four.

Related terms

Lagrangian
Duality gap
Primal problem
Lagrange multiplier
dual function
weak duality
strong duality
feasibility

Learn next

Derive dual functions for small constrained problems. Then study the conditions for strong duality and how primal - dual bounds provide stopping certificates.

Sources

Aalto Dictionary of Machine Learning, dual problem: maximizing Lagrangian lower bounds. https://aaltodictionaryofml.github.io/ADictML_Main.pdf Stephen Boyd and Lieven Vandenberghe, Convex Optimization slides, chapter 5: Lagrangian, dual function, weak duality and constraint qualifications. https://web.stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf The quadratic derivation and fictional bound-refinement case are original teaching illustrations.

Previous: Dual norm Next: Dual total correlation