Inequality Constraints

Inequality constraints define limitations on the design variables that must be satisfied for a solution to be feasible, but unlike equality constraints, they do not require exact values. They provide boundaries or regions within which the solution must lie, offering more flexibility in the optimization process.

Mathematical Formulation

An optimization problem with inequality constraints can be expressed as:

\begin{align} \min_{\theta} \quad & L(\theta) \ \text{subject to} \quad & I_k(\theta) \geq 0, \quad k = 1,2,\ldots,n \end{align}

where:

• $\theta \in {\mathbb{R}}^D$ is the design vector
• $L(\theta )$ is the objective function to be minimized
• $I_k(\theta )$ are the inequality constraint functions
• $n$ is the number of inequality constraints

Note: Constraints of the form $g(\theta )\le b$ can be rewritten as $b-g(\theta )\ge 0$ to match the standard form.

Types of Inequality Constraints

Linear Inequality Constraints

Constraints that are linear functions of the design variables:

$I_k(\theta )={\mathbf{a}}_k^T\theta -b_k\ge 0$

where ${\mathbf{a}}_k$ is a constant vector and $b_k$ is a constant scalar.

Examples:

• Resource limits: ${\sum }_{i=1}^D{a}_i{\theta }_i\le b$
• Non-negativity: ${\theta }_i\ge 0$
• Capacity constraints: ${\sum }_{i=1}^D{\theta }_i\le C_{\text{max}}$

Nonlinear Inequality Constraints

Constraints that have nonlinear relationships with the design variables:

$I_k(\theta )=g_k(\theta )\ge 0$

where $g_k$ is a nonlinear function.

Examples:

• Stress constraints: ${\sigma }_{\text{max}}(\theta )\le {\sigma }_{\text{allowable}}$
• Volume constraints: $V(\theta )\le V_{\text{max}}$
• Performance requirements: $\text{efficiency}(\theta )\ge 0.85$

Geometric Interpretation

Inequality constraints define half-spaces or curved regions in the design space:

• Each constraint $I_k(\theta )\ge 0$ defines a region bounded by the surface $I_k(\theta )=0$
• The feasible region is the intersection of all these regions
• Unlike equality constraints, inequality constraints don’t necessarily reduce the dimensionality of the feasible region

Active and Inactive Constraints

A key concept for inequality constraints is whether they are active or inactive at a given point:

• Active constraint: An inequality constraint $I_k(\theta )\ge 0$ is active at ${\theta }^{\ast }$ if $I_k({\theta }^{\ast })=0$
• Inactive constraint: An inequality constraint is inactive at ${\theta }^{\ast }$ if $I_k({\theta }^{\ast })>0$

Active constraints behave like equality constraints at the solution point, while inactive constraints have no effect on the local behavior of the solution.

Solution Methods

Karush-Kuhn-Tucker (KKT) Conditions

The KKT conditions extend Lagrange multipliers to handle inequality constraints:

1. Stationarity: $\nabla L({\theta }^{\ast })-{\sum }_{k=1}^n{\lambda }_k\nabla I_k({\theta }^{\ast })=0$
2. Primal Feasibility: $I_k({\theta }^{\ast })\ge 0$ for all $k=1,2,\dots ,n$
3. Dual Feasibility: ${\lambda }_k\ge 0$ for all $k=1,2,\dots ,n$
4. Complementary Slackness: ${\lambda }_k{I}_k({\theta }^{\ast })=0$ for all $k=1,2,\dots ,n$

The complementary slackness condition ensures that either a constraint is active ($I_k({\theta }^{\ast })=0$) or its Lagrange multiplier is zero (${\lambda }_k=0$).

Active Set Methods

Active set methods solve constrained optimization problems by:

1. Guessing which inequality constraints will be active at the solution
2. Treating the active constraints as equality constraints and ignoring inactive constraints
3. Solving this equality-constrained subproblem
4. Checking if any inactive constraints are violated or if any active constraints have negative Lagrange multipliers
5. Updating the active set accordingly and repeating

Interior Point Methods

Interior point methods approach the solution from the interior of the feasible region:

1. Convert inequality constraints to equality constraints using slack variables: $I_k(\theta )-s_k=0,s_k\ge 0$
2. Replace the non-negativity constraints with a barrier function: $-\mu {\sum }_{k=1}^n\ln (s_k)$
3. Solve a sequence of problems with decreasing $\mu$
4. As $\mu \to 0$, the solution approaches the optimal point on the boundary

Penalty and Barrier Methods

• Penalty Method: Add a penalty term for constraint violations ${\min }_{\theta }L(\theta )+\mu {\sum }_{k=1}^n\max (0,-I_k(\theta ){)}^2$ where $\mu >0$ is increased gradually

• Barrier Method: Add a barrier function that prevents leaving the feasible region ${\min }_{\theta }L(\theta )-\mu {\sum }_{k=1}^n\ln (I_k(\theta ))$ where $\mu >0$ is decreased gradually

Constraint Qualification

As with equality constraints, certain regularity conditions (constraint qualifications) must be satisfied for the KKT conditions to be necessary for optimality:

• Linear Independence Constraint Qualification (LICQ): The gradients of all active constraints at ${\theta }^{\ast }$ are linearly independent
• Mangasarian-Fromovitz Constraint Qualification (MFCQ): The gradients of active inequality constraints are positively linearly independent at ${\theta }^{\ast }$
• Slater’s Condition: For convex problems, there exists a strictly feasible point (where all inequality constraints are satisfied strictly)

Challenges with Inequality Constraints

Identifying Active Constraints

One of the main challenges is determining which inequality constraints will be active at the optimal solution. This leads to a combinatorial aspect of the problem, as there are $2^n$ possible active sets for $n$ inequality constraints.

Constraint Redundancy

Some inequality constraints may be redundant, meaning they are automatically satisfied when other constraints are satisfied. Identifying and removing redundant constraints can simplify the problem.

Degeneracy

Degeneracy occurs when there are more active constraints than variables, but the constraints are not linearly independent. This can lead to numerical difficulties and non-unique Lagrange multipliers.

Ill-Conditioning

As in equality-constrained problems, ill-conditioning can arise from poorly scaled constraints or nearly dependent constraint gradients.

Interpretations of Lagrange Multipliers

For inequality constraints, Lagrange multipliers have several important interpretations:

1. Sensitivity: ${\lambda }_k$ represents the rate of change of the optimal objective value with respect to the right-hand side of the $k$-th constraint
2. Shadow Price: In economic contexts, ${\lambda }_k$ is the marginal value of relaxing the $k$-th constraint
3. Force: In mechanical systems, ${\lambda }_k$ can represent the reaction force exerted by the $k$-th constraint

Engineering Applications

Structural Design

• Stress constraints: $\sigma (\theta )\le {\sigma }_{\text{allowable}}$
• Displacement constraints: $u(\theta )\le u_{\text{max}}$
• Buckling constraints: $P(\theta )\le P_{\text{critical}}$

Resource Allocation

• Budget constraints: ${\sum }_{i=1}^D{c}_i{\theta }_i\le B$
• Time constraints: ${\sum }_{i=1}^D{t}_i{\theta }_i\le T$
• Capacity constraints: ${\sum }_{i=1}^D{\theta }_i\le C$

Engineering Design

• Size constraints: $L_{\text{min}}\le {\theta }_i\le L_{\text{max}}$
• Performance constraints: $\text{efficiency}(\theta )\ge {\eta }_{\text{min}}$
• Safety constraints: $\text{safety factor}(\theta )\ge S{F}_{\text{min}}$

Example: Optimization with Inequality Constraints

Consider the problem:

\begin{align} \min_{\theta_1, \theta_2} \quad & (\theta_1 - 2)^2 + (\theta_2 - 1)^2 \ \text{subject to} \quad & \theta_1 + \theta_2 \leq 2 \ & \theta_1 \geq 0 \ & \theta_2 \geq 0 \end{align}

This is seeking the point in the non-negative quadrant that is closest to $(2,1)$ while satisfying ${\theta }_1+{\theta }_2\le 2$.

Solution using KKT Conditions

1. Rewrite constraints in standard form:

   • $I_1(\theta )=2-{\theta }_1-{\theta }_2\ge 0$
   • $I_2(\theta )={\theta }_1\ge 0$
   • $I_3(\theta )={\theta }_2\ge 0$

2. Form the Lagrangian: $\mathcal{L}(\theta ,\lambda )=({\theta }_1-2{)}^2+({\theta }_2-1{)}^2-{\lambda }_1(2-{\theta }_1-{\theta }_2)-{\lambda }_2{\theta }_1-{\lambda }_3{\theta }_2$

3. Apply the KKT conditions:

   • Stationarity: $\frac{\partial \mathcal{L}}{\partial {\theta }_1}=2({\theta }_1-2)+{\lambda }_1-{\lambda }_2=0$ $\frac{\partial \mathcal{L}}{\partial {\theta }_2}=2({\theta }_2-1)+{\lambda }_1-{\lambda }_3=0$
   • Primal Feasibility: $2-{\theta }_1-{\theta }_2\ge 0,{\theta }_1\ge 0,{\theta }_2\ge 0$
   • Dual Feasibility: ${\lambda }_1\ge 0,{\lambda }_2\ge 0,{\lambda }_3\ge 0$
   • Complementary Slackness: ${\lambda }_1(2-{\theta }_1-{\theta }_2)=0,{\lambda }_2{\theta }_1=0,{\lambda }_3{\theta }_2=0$

4. Case analysis:

   • The unconstrained optimum is $(2,1)$, which satisfies ${\theta }_1+{\theta }_2\le 2$ (just barely), so the first constraint is active
   • The point $(2,1)$ also satisfies ${\theta }_1\ge 0$ and ${\theta }_2\ge 0$, so these constraints are inactive
   • Thus ${\lambda }_1>0$, ${\lambda }_2={\lambda }_3=0$

5. From the KKT conditions: $2({\theta }_1-2)+{\lambda }_1=0$ $2({\theta }_2-1)+{\lambda }_1=0$ ${\lambda }_1(2-{\theta }_1-{\theta }_2)=0$

   Since ${\lambda }_1>0$, we have ${\theta }_1+{\theta }_2=2$. From the first two equations, we get ${\theta }_1-2={\theta }_2-1$, or ${\theta }_1={\theta }_2+1$.

   Combining with ${\theta }_1+{\theta }_2=2$, we get ${\theta }_2+1+{\theta }_2=2$, which gives ${\theta }_2=0.5$ and ${\theta }_1=1.5$.

6. So the solution is ${\theta }^{\ast }=(1.5,0.5)$, with ${\lambda }_1=1$, ${\lambda }_2={\lambda }_3=0$.

Related Pages

• Equality Constraints
• Lagrange Multipliers
• KKT Conditions
• Penalty Methods
• Augmented Lagrangian Method
• Constrained Optimization