Constrained optimization
Constrained Optimization
Constrained optimization means optimizing an objective function when only some decisions are allowed.
The general form is:
\[\min f(x)\]subject to:
\[x \in S\]or:
\[\max f(x)\]subject to:
\[x \in S\]where:
- $x$ is the decision vector
- $f(x)$ is the objective function
- $S$ is the feasible set
Unconstrained vs Constrained Optimization
An unconstrained problem has no restrictions on $x$.
Example:
\[\min f(x)\]with:
\[x\in\mathbb{R}^n\]A constrained problem restricts the allowed values of $x$.
Example:
\[\min f(x)\]subject to:
\[x_1+x_2\le 10\] \[x_1,x_2\ge 0\]Why Constraints Are Needed
Without constraints, many OR problems are meaningless.
Example:
\[\max x_1+x_2\]If $x_1$ and $x_2$ have no upper limits, the value can grow forever.
So the problem is unbounded.
Constraints represent real-world limits.
Typical Constraints
Constraints can represent:
- limited budget
- limited labor
- limited machines
- minimum demand
- maximum capacity
- legal requirements
- nonnegative quantities
- integer decisions
Feasible Set
The feasible set is the set of all points satisfying the constraints.
If:
\[S=\{x\in\mathbb{R}^n \mid x \text{ satisfies all constraints}\}\]then constrained optimization means choosing the best point inside $S$.
Feasible and Infeasible Points
A point $x$ is feasible if:
\[x\in S\]A point is infeasible if:
\[x\notin S\]Only feasible points can be optimal.
Constrained Minimum
For:
\[\min f(x)\]subject to:
\[x\in S\]a point $x^*\in S$ is a constrained minimum point if:
\[f(x^*)\le f(x)\]for every:
\[x\in S\]Constrained Maximum
For:
\[\max f(x)\]subject to:
\[x\in S\]a point $x^*\in S$ is a constrained maximum point if:
\[f(x^*)\ge f(x)\]for every:
\[x\in S\]Optimal Value
If $x^*$ is optimal, then:
\[z^*=f(x^*)\]is the optimal value.
The point $x^*$ is the optimal solution.
The number $z^*$ is the optimal value.
Example
Suppose:
\[\max 5x_1+12x_2\]subject to:
\[20x_1+10x_2\le 200\] \[10x_1+20x_2\le 120\] \[10x_1+30x_2\le 150\] \[x_1,x_2\ge 0\]Here:
- $x_1,x_2$ are decision variables
- $5x_1+12x_2$ is the objective function
- the inequalities are constraints
- the feasible set is the set of all allowed production plans
Linear Programming as Constrained Optimization
Linear programming is a special case of constrained optimization.
A linear programming problem has:
- linear objective function
- linear equality or inequality constraints
General form:
\[\min \text{ or } \max \quad c^Tx\]subject to linear constraints.
Standard form:
\[\min c^Tx\]subject to:
\[Ax=b\] \[x\ge 0\]Geometry
In two-variable linear programming:
- constraints define half-planes
- the feasible set is their intersection
- objective contour lines move across the feasible region
- the optimum occurs at the last feasible point touched
In higher dimensions:
- constraints define half-spaces
- the feasible set is a polyhedron
- algorithms replace drawing
Possible Outcomes
A constrained optimization problem may have:
- a unique optimal solution
- multiple optimal solutions
- no feasible solution
- an unbounded objective
Infeasible Problem
If:
\[S=\emptyset\]then the problem is infeasible.
There is no feasible point and no optimal solution.
Unbounded Problem
A maximization problem is unbounded if:
\[f(x)\]can grow without limit while $x$ remains feasible.
A minimization problem is unbounded below if:
\[f(x)\]can decrease without limit while $x$ remains feasible.
Local and Global Optimality
A local optimum is best near a point.
A global optimum is best over the entire feasible set.
In linear programming, because the objective is linear and the feasible set is convex, local optimality implies global optimality.
OR Interpretation
Constrained optimization is the mathematical form of:
choose the best decision among the decisions that are actually allowed.
Examples:
| Problem | Objective | Constraints |
|---|---|---|
| production | maximize profit | limited resources |
| transportation | minimize cost | supply and demand |
| diet | minimize expense | nutrient requirements |
| investment | maximize return | budget and allocation rules |
Checklist
You understand constrained optimization if you can:
- identify the objective function
- identify the feasible set
- distinguish feasible from infeasible points
- define constrained minimum and maximum
- distinguish optimal solution from optimal value
- recognize infeasible problems
- recognize unbounded problems
- explain why LP is constrained optimization
See Also
- Optimization Foundations
- Decision Variables
- Objective Functions
- Constraints
- Feasible Sets
- Optimal Solutions and Optimal Values
- Linear Programming
Exam checkpoint
In exam problems, translate the story into variables, objective, constraints, feasible set, and optimal value. Always state whether the problem is a maximization or minimization and what the units are.