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:

1
2
3

double weakBound(Tour tour) {
  return tour.cost(); // Any tour cost upper bounds optimal
}

C++ - Lower bounding knapsack solution:

1
2
3

int weakBound(vector<Item> selection) {
  return value(selection); // Any selection lower bounds optimal
}

Python - Upper bounding assignment problem:

1
2

def weak_bound(assignment):
  return cost(assignment) # Any assignment cost upper bounds optimal

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).

  1. f(x) is the objective function for the primal problem, aiming to maximize the output.
  2. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import org.apache.commons.math3.optimization.linear.*;

// Assume a pre-existing Java library for LP solving; Apache Commons Math is an example.

public class WeakDuality {
    public static void main(String[] args) {
        // Define the primal problem
        // For simplicity, assume it's to maximize z = 3x + 4y, x >= 0, y >= 0
        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] {3, 4}, 0);

        // Define constraints
        Collection<LinearConstraint> constraints = new ArrayList<>();
        constraints.add(new LinearConstraint(new double[] {1, 1}, Relationship.LEQ, 4));
        
        // Solve the primal problem
        SimplexSolver solver = new SimplexSolver();
        RealPointValuePair solution = solver.optimize(f, constraints, GoalType.MAXIMIZE, new NonNegativeConstraint(true));
        
        double primalValue = solution.getValue();

        // The dual problem is to minimize w = 4s, s >= 0
        // Its solution will be w = 4s = 4 * primalValue / (3 + 4)

        double dualValue = 4 * primalValue / (3 + 4);
        
        // Weak duality
        System.out.println("Primal value: " + primalValue);
        System.out.println("Dual value (lower bound): " + dualValue);
    }
}

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <iostream>

// Assume we've solved primal and dual problems using an LP library
// This is just for demonstration
double primalValue = 28;  // For example
double dualValue = 4 * primalValue / (3 + 4);

int main() {
    std::cout << "Primal value: " << primalValue << std::endl;
    std::cout << "Dual value (lower bound): " << dualValue << std::endl;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from scipy.optimize import linprog

# Define the primal problem coefficients
c = [-3, -4]  # Coefficients for the objective function (maximize 3x + 4y)
A = [[1, 1]]  # Coefficients for the inequalities
b = [4]  # Constants for the inequalities

# Solve the primal problem
res = linprog(c, A_ub=A, b_ub=b, method='highs')
primal_value = -res.fun

# Dual value
dual_value = 4 * primal_value / (3 + 4)

# Weak duality
print("Primal value:", primal_value)
print("Dual value (lower bound):", dual_value)

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.