5.5 Constrained optimization

Constrained optimization is all about finding the best solution while playing by the rules. It's like trying to make the most money possible, but you can't spend more than you have or break any laws.

This topic builds on earlier optimization concepts, adding real-world limitations to the mix. We'll explore how to solve problems with constraints, using methods like penalties and barriers to keep solutions in check.

Constrained Optimization Problems

Defining Constrained Optimization

Top images from around the web for Defining Constrained Optimization

• 

  Nonlinear programming - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Nonlinear programming - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Defining Constrained Optimization

• 

  Nonlinear programming - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

• 

  Nonlinear programming - Wikipedia View original

  Is this image relevant?

• 

  Lagrange multiplier - Wikipedia View original

  Is this image relevant?

1 of 3

• Constrained optimization problems involve finding the optimal solution to an objective function subject to one or more constraints on the decision variables
• Objective function represents the quantity to be maximized or minimized, typically denoted as $f(x)$, where $x$ is a vector of decision variables
• Constraints limit the feasible region of the optimization problem, often represented as equalities or inequalities
• Feasible region encompasses all possible solutions that satisfy all constraints in the optimization problem
• Standard form of a constrained optimization problem includes the objective function, equality constraints, and inequality constraints:
  • Minimize (or Maximize) $f(x)$
  • Subject to:
    • $h_i(x) = 0$ for $i = 1, ..., m$ (equality constraints)
    • $g_j(x) \leq 0$ for $j = 1, ..., n$ (inequality constraints)
    • $x \in X$ (domain constraints)
• Real-world applications include resource allocation (budgeting), portfolio optimization (finance), and engineering design problems (structural optimization)
• Solution to a constrained optimization problem must satisfy both the optimality criteria for the objective function and all specified constraints

Components and Characteristics

• Decision variables ($x$) represent the quantities to be optimized (production levels, investment allocations)
• Objective function ($f(x)$) quantifies the goal to be optimized (maximize profit, minimize cost)
• Constraints define limitations on decision variables:
  • Resource constraints (budget limitations)
  • Physical constraints (capacity restrictions)
  • Logical constraints (binary decisions)
• Feasible region shape depends on constraint types:
  • Linear constraints create a polyhedron
  • Nonlinear constraints may result in a non-convex region
• Global optimum may not be achievable due to constraints, leading to local optima
• Constraint qualification ensures the existence of Lagrange multipliers at the optimal solution
• Sensitivity analysis examines how changes in constraints affect the optimal solution

Constraint Types

Equality and Inequality Constraints

• Equality constraints expressed as $h(x) = 0$, where $h(x)$ is a function of the decision variables that must equal zero at the optimal solution
  • Example: $x_1 + x_2 = 100$ (total production must equal 100 units)
• Inequality constraints expressed as $g(x) \leq 0$ or $g(x) \geq 0$, defining regions where the solution must lie above or below a certain threshold
  • Example: $2x_1 + 3x_2 \leq 50$ (resource usage must not exceed 50 units)
• Active constraints satisfied as equalities at the optimal solution, while inactive constraints satisfied as strict inequalities
  • Active constraint example: $g(x^*) = 0$ at the optimal point $x^*$
  • Inactive constraint example: $g(x^*) < 0$ at the optimal point $x^*$
• Linear constraints expressed as linear functions of the decision variables
  • Example: $a_1x_1 + a_2x_2 + ... + a_nx_n = b$ (linear equality constraint)
• Nonlinear constraints involve nonlinear functions
  • Example: $x_1^2 + x_2^2 \leq 25$ (circular constraint region)

Bound Constraints and Convexity

• Bound constraints directly limit the range of individual decision variables, often expressed as $l \leq x \leq u$
  • Example: $0 \leq x_1 \leq 10$ (production of item 1 between 0 and 10 units)
• Convex constraints define a convex feasible region, crucial for guaranteeing global optimality in convex optimization problems
  • Convex set property: line segment between any two points in the set lies entirely within the set
• Number and type of constraints significantly impact the complexity and solvability of the optimization problem
  • Highly constrained problems may have a very small feasible region
  • Conflicting constraints may result in an infeasible problem
• Constraint classification affects algorithm choice:
  • Linear constraints allow for efficient linear programming methods
  • Nonlinear constraints may require more complex nonlinear programming techniques

Optimality Conditions

Karush-Kuhn-Tucker (KKT) Conditions

• Karush-Kuhn-Tucker (KKT) conditions represent first-order necessary conditions for a solution to be optimal in nonlinear programming
• KKT conditions include:
  • Stationarity
  • Complementary slackness
  • Dual feasibility
  • Primal feasibility
• Lagrange multipliers ($\lambda$ and $\mu$) introduced in KKT conditions to account for the impact of constraints on the objective function
• Stationarity condition relates the gradient of the objective function to the gradients of the active constraints at the optimal point:
  • $\nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla h_i(x^*) + \sum_{j=1}^n \mu_j \nabla g_j(x^*) = 0$
• Complementary slackness ensures either an inequality constraint is active or its corresponding Lagrange multiplier is zero:
  • $\mu_j g_j(x^*) = 0$ for all $j = 1, ..., n$

Additional Optimality Criteria

• Dual feasibility requires non-negative Lagrange multipliers for inequality constraints:
  • $\mu_j \geq 0$ for all $j = 1, ..., n$
• Primal feasibility ensures all constraints are satisfied:
  • $h_i(x^*) = 0$ for all $i = 1, ..., m$
  • $g_j(x^*) \leq 0$ for all $j = 1, ..., n$
• Second-order sufficient conditions, involving the Hessian of the Lagrangian, can be used to verify that a KKT point is indeed a local minimum
  • Lagrangian function: $L(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i h_i(x) + \sum_{j=1}^n \mu_j g_j(x)$
  • Second-order condition: Hessian of Lagrangian is positive definite on the tangent space of active constraints
• Fritz John conditions provide an alternative set of necessary conditions when constraint qualification fails
• Slater's condition ensures strong duality in convex optimization problems, guaranteeing zero duality gap

Handling Constraints in Optimization

Penalty and Barrier Methods

• Penalty methods transform constrained optimization problems into unconstrained problems by adding a penalty term to the objective function for constraint violations
• Quadratic penalty method uses a quadratic function of constraint violations, with the penalty parameter increasing iteratively to enforce feasibility:
  • Penalized objective: $\phi(x, \rho) = f(x) + \frac{\rho}{2} (\sum_{i=1}^m h_i(x)^2 + \sum_{j=1}^n \max(0, g_j(x))^2)$
• Augmented Lagrangian methods combine penalty terms with Lagrange multiplier estimates to improve convergence properties:
  • Augmented Lagrangian: $L_A(x, \lambda, \mu, \rho) = f(x) + \sum_{i=1}^m \lambda_i h_i(x) + \frac{\rho}{2} \sum_{i=1}^m h_i(x)^2 + \sum_{j=1}^n \mu_j \max(0, g_j(x))$
• Barrier methods, such as the logarithmic barrier method, add terms to the objective function that prevent solutions from violating inequality constraints:
  • Barrier function: $B(x) = -\sum_{j=1}^n \log(-g_j(x))$
• Interior point method uses barrier functions to solve linear and nonlinear programming problems efficiently
  • Primal-dual interior point methods simultaneously optimize primal and dual variables

Projection and Active Set Methods

• Projection methods handle constraints by projecting infeasible points onto the feasible region after each iteration of an unconstrained optimization algorithm
  • Example: Projected gradient method for bound-constrained problems
• Active set methods identify the set of active constraints at each iteration and solve a sequence of equality-constrained subproblems
  • Working set: estimate of the active set at each iteration
  • Equality-constrained subproblem solved using Lagrange multipliers
• Choice of constraint-handling strategy depends on:
  • Problem structure (linear vs. nonlinear)
  • Constraint types (equality, inequality, bounds)
  • Desired trade-offs between solution accuracy and computational efficiency
• Hybrid methods combine multiple techniques to leverage their strengths:
  • Sequential Quadratic Programming (SQP) uses active set approach with quadratic programming subproblems
  • Augmented Lagrangian methods with bound constraints handled separately