Weak Duality
Weak duality is a principle in optimization stating that for a minimization problem, any feasible solution provides an upper bound on the optimal solution.
For a maximization problem, any feasible solution provides a lower bound.
This provides a simple way to test solution quality.
Examples:
Minimization:
 Let x be a feasible solution with cost C(x)
 Then C(x) ≥ C(x*) for optimal solution x*
Maximization:
 Let x be a feasible solution with value V(x)
 Then V(x) ≤ V(x*) for optimal x*
Java  Upper bounding TSP solution:


C++  Lower bounding knapsack solution:


Python  Upper bounding assignment problem:


Weak duality provides a simple bounding principle for optimization. Tighter bounds can further prune search spaces.
In optimization theory, weak duality refers to the property that the objective value of the dual problem provides a bound to the objective value of the primal problem. Specifically, for a maximization primal problem, the dual problem will provide a lower bound. Conversely, for a minimization primal problem, the dual problem will offer an upper bound. Weak duality holds for all types of optimization problems.
In optimization problems, weak duality refers to the relationship between a primal problem and its dual problem. Specifically, the optimal value of the objective function in the dual problem provides a lower bound for the optimal value of the primal problem.
Visual Representation:
Let’s consider a graphical example using a linear programming problem. Imagine two objective functions, one for the primal problem (f) and another for its dual problem (g).
f(x)
is the objective function for the primal problem, aiming to maximize the output.g(y)
is the objective function for the dual problem, aiming to minimize the output.
Graphically, you could plot f(x)
and g(y)
against x
and y
respectively.
f(x) \
\
\\ g(y)
/
/
/
x y
In this hypothetical graph:
f(x)
is decreasing as x increases.g(y)
is increasing as y increases.
Weak Duality states that the value of g(y)
will always be less than or equal to f(x)
. This can be visually seen in how g(y)
is always below f(x)
for the feasible set of solutions.
Key Takeaway:
Weak Duality provides a useful way to approximate the solution to the primal problem by solving the dual problem, giving a lower bound that helps in understanding how good an existing solution is. This can be a powerful tool for simplifying complex optimization problems.
Solution
Note that the concept of weak duality is more theoretical and usually does not involve direct coding. However, it’s commonly applied implicitly in optimization algorithms like the Simplex method for Linear Programming (LP) or Quadratic Programming (QP).
Here’s a simple example illustrating weak duality using a linear programming problem.
Java


C++
In C++, you might use an LP library like GLPK to solve the primal and dual problems. However, let’s focus on the values you would check to assert weak duality:


Python


Key Takeaways
 Weak duality offers a relationship between the primal and dual optimization problems.
 The dual objective provides a bound on the primal objective.
 While direct coding of weak duality is rare, the concept is embedded within optimization algorithms.