12.2 Wolfe's method for quadratic programming

Wolfe's method is a powerful approach for solving quadratic programming problems with inequality constraints. It transforms the problem into a system of linear equations by applying Karush-Kuhn-Tucker conditions, allowing for simultaneous solution of primal and dual variables.

This technique offers advantages in handling inequality constraints and providing sensitivity analysis. However, it can be computationally complex for large-scale problems and requires a positive definite Q matrix, making it important to consider alternative methods for certain problem types.

Understanding Wolfe's Method for Quadratic Programming

Principles of Wolfe's method

• Wolfe's method tackles quadratic programming problems with inequality constraints efficiently
• Objective function expressed as quadratic form $f(x) = \frac{1}{2}x^TQx + c^Tx$ subject to linear constraints $Ax \leq b$
• Converts inequality constraints to equality constraints by introducing slack variables $s$ (Ax + s = b)
• Applies Karush-Kuhn-Tucker (KKT) conditions ensuring optimal solution
  • Stationarity: gradient of Lagrangian equals zero
  • Primal feasibility: satisfies original constraints
  • Dual feasibility: non-negative Lagrange multipliers
  • Complementary slackness: product of slack variables and multipliers equals zero
• Formulates system of linear equations from KKT conditions
• Simultaneously solves for primal variables $x$ and dual variables $\lambda$ (Lagrange multipliers)

Step-by-step application of Wolfe's method

1. Express objective function $f(x) = \frac{1}{2}x^TQx + c^Tx$ and constraints $Ax \leq b$

2. Introduce slack variables $s$ to convert inequalities to equalities: $Ax + s = b$

3. Construct Lagrangian function: $L(x, s, \lambda, \mu) = \frac{1}{2}x^TQx + c^Tx + \lambda^T(Ax + s - b) - \mu^Ts$

4. Apply KKT conditions:

   • $\nabla_x L = Qx + c + A^T\lambda = 0$
   • $\nabla_s L = \lambda - \mu = 0$
   • $Ax + s = b$
   • $\mu^Ts = 0$

5. Form system of linear equations by combining KKT conditions

6. Eliminate $\mu$ using $\lambda - \mu = 0$

7. Solve resulting linear system using matrix methods (Gaussian elimination)

8. Extract optimal values for $x$, $s$, and $\lambda$

Optimal solutions using Wolfe's method

• Verify all KKT conditions satisfied
• Identify primal solution by extracting optimal $x$ values
• Examine dual solution through $\lambda$ (Lagrange multipliers)
• Interpret slack variables $s$:
  • Active constraints: $s = 0$
  • Inactive constraints: $s > 0$
• Calculate objective function value using optimal $x$
• Confirm solution feasibility by checking all original constraints

Wolfe's method vs other techniques

• Advantages:
  • Directly handles inequality constraints
  • Solves primal and dual problems simultaneously
  • Provides sensitivity analysis via Lagrange multipliers
  • Applicable to convex quadratic programming problems
• Limitations:
  • Computationally complex for large-scale problems
  • Sensitive to numerical errors in matrix operations
  • Requires positive definite Q matrix
  • May struggle with degenerate problem instances
• Comparison:
  • Interior point methods better suited for very large problems
  • Active set methods more efficient with few active constraints
  • Gradient projection methods simpler but less robust for complex constraints