11.2 Inequality constrained optimization

Inequality constrained optimization tackles real-world problems with limitations. It maximizes or minimizes a function while staying within set boundaries, like budget constraints or resource limits. This approach is crucial for practical decision-making in fields like economics, engineering, and resource management.

KKT conditions are the backbone of solving these problems. They provide a systematic way to find optimal solutions by balancing the objective function with constraints. Understanding KKT conditions helps us interpret results economically and geometrically, giving insights into resource allocation and problem structure.

Optimization with Inequality Constraints

Formulating Inequality Constrained Problems

Top images from around the web for Formulating Inequality Constrained Problems

• 

  3.1 Graphing Systems Of Linear Inequalites | Finite Math View original

  Is this image relevant?

• 

  3.1 Graphing Systems Of Linear Inequalites | Finite Math View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  3.1 Graphing Systems Of Linear Inequalites | Finite Math View original

  Is this image relevant?

• 

  3.1 Graphing Systems Of Linear Inequalites | Finite Math View original

  Is this image relevant?

1 of 3

Top images from around the web for Formulating Inequality Constrained Problems

• 

  3.1 Graphing Systems Of Linear Inequalites | Finite Math View original

  Is this image relevant?

• 

  3.1 Graphing Systems Of Linear Inequalites | Finite Math View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  3.1 Graphing Systems Of Linear Inequalites | Finite Math View original

  Is this image relevant?

• 

  3.1 Graphing Systems Of Linear Inequalites | Finite Math View original

  Is this image relevant?

1 of 3

• Inequality constrained optimization maximizes or minimizes an objective function subject to one or more inequality constraints
• Standard form minimizes $f(x)$ subject to $g_i(x) \leq 0$ for $i = 1, ..., m$, where $f(x)$ represents the objective function and $g_i(x)$ represent inequality constraints
• Constraints expressed as less than or equal to (≤), greater than or equal to (≥), or strict inequalities (< or >)
• Feasible region encompasses all points simultaneously satisfying all constraints
• Slack variables convert inequality constraints to equality constraints, aiding certain solution methods
• Two-dimensional problems graphically represented by shading the feasible region defined by constraints
  • Example: Maximize profit subject to production capacity constraints (labor hours ≤ 40, material costs ≤ $1000)
• Inequality constraints model real-world limitations (budget constraints, resource availability)
  • Example: Diet optimization problem with minimum nutrient requirements (protein intake ≥ 50g)

Solving Techniques and Considerations

• Graphical method solves two-variable problems by plotting constraints and objective function contours
  • Example: Maximize $z = 3x + 2y$ subject to $x + y \leq 10$, $x \geq 0$, $y \geq 0$
• Interior point methods efficiently solve large-scale problems by moving through the interior of the feasible region
• Active set methods identify binding constraints at the optimal solution
• Convexity of objective function and constraints guarantees global optimality of local solutions
• Sensitivity analysis examines how changes in constraints affect the optimal solution
  • Example: Analyzing impact of increased budget on maximum achievable profit

KKT Conditions for Optimization

Components of KKT Conditions

• Karush-Kuhn-Tucker (KKT) conditions provide necessary optimality criteria for nonlinear programming with inequality constraints
• Four main components comprise KKT conditions:
  1. Stationarity: Gradient of Lagrangian function equals zero at optimal point
  2. Primal feasibility: All inequality constraints satisfied at optimal solution
  3. Dual feasibility: Non-negative Lagrange multipliers for inequality constraints
  4. Complementary slackness: For each constraint, either constraint active or associated Lagrange multiplier zero
• Stationarity condition expressed as $\nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i(x^*) = 0$
• Primal feasibility ensures $g_i(x^*) \leq 0$ for all $i$
• Dual feasibility requires $\lambda_i \geq 0$ for all $i$
• Complementary slackness stated as $\lambda_i g_i(x^*) = 0$ for all $i$

Applying KKT Conditions

• KKT conditions derive system of equations and inequalities yielding candidate optimal solutions
• Steps to apply KKT conditions:
  1. Form the Lagrangian function: $L(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x)$
  2. Write out all KKT conditions
  3. Solve resulting system of equations and inequalities
  4. Verify second-order sufficient conditions for optimality
• Example: Minimize $f(x,y) = x^2 + y^2$ subject to $x + y \geq 1$ and $x,y \geq 0$
• KKT conditions help identify active constraints at the optimal solution
• Solving KKT conditions may require numerical methods for complex problems (Newton's method, interior point methods)

Economic and Geometric Meaning of KKT

Economic Interpretation

• Lagrange multipliers represent shadow prices or marginal values of constraints
• Shadow prices indicate the change in objective function value per unit change in constraint right-hand side
  • Example: In production optimization, Lagrange multiplier for a resource constraint represents the marginal value of that resource
• Complementary slackness reveals whether a constraint impacts the optimal solution
  • Active constraints ($\lambda_i > 0$) influence the solution
  • Inactive constraints ($\lambda_i = 0$) do not affect the solution
• KKT conditions relate to resource allocation and marginal rates of substitution
  • Example: In portfolio optimization, KKT conditions help determine efficient asset allocation

Geometric Interpretation

• Gradient of objective function forms non-negative linear combination of active constraint gradients at optimal point
• Stationarity condition aligns objective function gradient with active constraint gradients
  • Example: In 2D problems, optimal point occurs where objective function contour tangent to constraint boundary
• Complementary slackness geometrically indicates:
  • Active constraints ($g_i(x^*) = 0$) define the boundary of the feasible region
  • Inactive constraints ($g_i(x^*) < 0$) do not influence the optimal solution
• Feasible region shape determined by intersection of constraint boundaries
• Optimal solution occurs at a vertex, edge, or interior point of feasible region depending on objective function and constraints

Optimal Solution and Lagrange Multipliers

Determining Optimal Solutions

• Solve KKT conditions system to find candidate optimal solutions for decision variables and Lagrange multipliers
• Optimal solution satisfies all KKT conditions simultaneously:
  • Primal feasibility: $g_i(x^*) \leq 0$ for all $i$
  • Dual feasibility: $\lambda_i \geq 0$ for all $i$
  • Complementary slackness: $\lambda_i g_i(x^*) = 0$ for all $i$
• Numerical methods solve complex KKT systems in large-scale problems:
  • Interior point methods move through feasible region interior
  • Active set methods identify binding constraints iteratively
• Verify second-order sufficient conditions to confirm local optimality:
  • For minimization: Hessian of Lagrangian positive semidefinite on tangent space of active constraints
  • For maximization: Hessian of Lagrangian negative semidefinite on tangent space of active constraints

Interpreting Lagrange Multipliers

• Non-zero Lagrange multipliers indicate binding constraints and their relative importance
• Sensitivity analysis examines impact of small constraint changes on optimal objective value
  • Example: In production planning, Lagrange multiplier for machine capacity constraint shows impact of additional capacity on profit
• Lagrange multiplier magnitudes reveal most influential constraints
  • Larger multiplier values indicate constraints with greater impact on objective function
• Zero Lagrange multipliers identify non-binding constraints
  • Relaxing these constraints does not improve the optimal solution
• Economic interpretation of Lagrange multipliers as marginal values aids decision-making
  • Example: In resource allocation, Lagrange multipliers guide investment decisions by showing marginal returns of each resource