The Central Idea
Optimization does not ask for the best value among every imaginable choice. It asks for the best value among the choices that are allowed.
A general optimization problem can be written
\[ \boxed{ \begin{aligned} \text{maximize or minimize}\quad &f(\mathbf{x})\\ \text{subject to}\quad &\mathbf{x}\in\mathcal{F}, \end{aligned} } \]where \(f(\mathbf{x})\) is the objective function and \(\mathcal{F}\) is the feasible set.
The constraints determine \(\mathcal{F}\).
What Is a Constraint?
A constraint is a mathematical condition that a decision must satisfy in order to be permitted.
Examples include
\[ x\ge0, \] \[ x+y\le100, \] \[ 2x+3y=60, \]or
\[ x\in\mathbb{Z}. \]Each condition removes some possible decisions and preserves others.
Feasible and Infeasible Decisions
A decision is feasible if it satisfies every constraint.
A decision is infeasible if it violates even one constraint.
Suppose
\[ x+y\le10, \qquad x\ge0, \qquad y\ge0. \]The point
\[ (4,5) \]is feasible because
\[ 4+5=9\le10. \]The point
\[ (7,6) \]is infeasible because
\[ 7+6=13>10. \]The Feasible Set
The collection of all feasible decisions is called the feasible set.
In one variable, a feasible set might be an interval such as
\[ 0\le x\le20. \]In two variables, the feasible set is often a region in the coordinate plane.
In higher dimensions, it becomes a region in \(\mathbb{R}^n\).
Feasible Region
The phrase feasible region is commonly used when the feasible set has a geometric interpretation.
Suppose
\[ x\ge0, \qquad y\ge0, \qquad x+y\le6. \]The feasible region consists of all points in the first quadrant lying on or below the line
\[ x+y=6. \]Geometrically, this forms a triangle with vertices
\[ (0,0),\qquad(6,0),\qquad(0,6). \]Equality Constraints
An equality constraint requires a mathematical relationship to hold exactly.
For example,
\[ x+y=20 \]restricts the decision to points lying exactly on a line.
In three variables,
\[ x+y+z=100 \]restricts the decision to a plane.
Inequality Constraints
An inequality constraint permits an entire side of a boundary.
For example,
\[ x+y\le20 \]includes the line
\[ x+y=20 \]together with one side of that line.
Similarly,
\[ x+y\ge20 \]selects the opposite side.
Strict and Non-Strict Inequalities
The distinction between
\[ x<5 \]and
\[ x\le5 \]matters in optimization.
The second condition includes the boundary point \(x=5\), while the first excludes it.
This can determine whether a maximum or minimum is actually attained.
Example: Why Boundary Inclusion Matters
Consider
\[ \text{maximize }f(x)=x. \]If
\[ 0\le x\le5, \]then the maximum exists at
\[ \boxed{x=5}. \]But if
\[ 0\le x<5, \]values of \(x\) can approach \(5\) without ever reaching it.
The supremum is \(5\), but no maximum is attained.
Nonnegativity Constraints
Many practical decision variables cannot be negative.
If \(x\) and \(y\) represent production quantities, then we often require
\[ x\ge0, \qquad y\ge0. \]These are called nonnegativity constraints.
Upper and Lower Bounds
A variable may be restricted to an interval:
\[ a\le x\le b. \]This is equivalent to the pair of constraints
\[ x\ge a \]and
\[ x\le b. \]Bounds commonly arise from capacity limits, safety requirements, contractual limits, or physical dimensions.
Resource Constraints
Suppose two products require limited labor hours.
If product \(x\) uses \(2\) hours per unit and product \(y\) uses \(3\) hours per unit, and only \(120\) hours are available, then
\[ \boxed{2x+3y\le120}. \]The left side represents labor used.
The right side represents labor available.
Budget Constraints
Suppose one activity costs \(50\) dollars per unit and another costs \(80\) dollars per unit.
If the total budget is \(4000\) dollars, then
\[ \boxed{50x+80y\le4000}. \]This converts a verbal financial limit into a mathematical constraint.
Capacity Constraints
A system may have a maximum operating capacity.
If total production cannot exceed \(500\) units, then
\[ \boxed{x+y\le500}. \]Capacity constraints are common in manufacturing, transportation, storage, computing, energy systems, and logistics.
Minimum-Requirement Constraints
Not all constraints are upper limits.
Suppose a system must provide at least \(100\) units of output:
\[ \boxed{x+y\ge100}. \]This creates a lower requirement rather than an upper capacity.
Multiple Constraints
Real optimization models usually contain several constraints simultaneously.
For example,
\[ 2x+y\le100, \] \[ x+3y\le120, \] \[ x\ge0, \] \[ y\ge0. \]A point is feasible only if it satisfies all four conditions.
The Feasible Region Is an Intersection
Each constraint defines a set of permitted points.
The feasible region is the intersection of all those sets.
If the individual constraint sets are
\[ F_1,F_2,\ldots,F_m, \]then the complete feasible set is
\[ \boxed{ \mathcal{F} = F_1\cap F_2\cap\cdots\cap F_m }. \]Testing a Candidate Point
Suppose the constraints are
\[ x+2y\le12, \] \[ 3x+y\le15, \] \[ x\ge0, \qquad y\ge0. \]Test the point
\[ (3,4). \]First constraint:
\[ 3+2(4)=11\le12. \]Second constraint:
\[ 3(3)+4=13\le15. \]The coordinates are nonnegative, so
\[ \boxed{(3,4)\text{ is feasible}.} \]Example of an Infeasible Point
Using the same constraints, test
\[ (4,5). \]The first constraint gives
\[ 4+2(5)=14. \]Since
\[ 14>12, \]the point violates the first constraint.
Therefore,
\[ \boxed{(4,5)\text{ is infeasible}.} \]Constraint Boundaries
The boundary associated with
\[ ax+by\le c \]is the line
\[ \boxed{ax+by=c}. \]Graphing the boundary first helps determine which half-plane satisfies the inequality.
Using a Test Point
To determine which side of a boundary satisfies an inequality, choose a point not lying on the boundary.
For
\[ 2x+y\le8, \]test
\[ (0,0). \]Since
\[ 2(0)+0=0\le8, \]the side containing the origin is feasible for this constraint.
Graphing a Linear Constraint
Consider
\[ 2x+y\le8. \]First graph the boundary
\[ 2x+y=8. \]Solving for \(y\),
\[ y=8-2x. \]The intercepts are
\[ (0,8) \]and
\[ (4,0). \]The feasible half-plane is the side satisfying the original inequality.
Constructing a Feasible Region Graphically
To graph a system of linear constraints:
- graph the boundary of each inequality;
- determine the permitted side of each boundary;
- include or exclude boundaries according to the inequality symbols;
- identify the overlap satisfying every condition;
- mark important intersection points or vertices.
The overlap is the feasible region.
Example: Building a Feasible Region
Consider
\[ x+y\le6, \] \[ x\le4, \] \[ x\ge0, \] \[ y\ge0. \]The first constraint lies below
\[ y=6-x. \]The second restricts us to the left of
\[ x=4. \]The nonnegativity constraints keep us in the first quadrant.
The resulting feasible region has vertices
\[ (0,0), \qquad (4,0), \qquad (4,2), \qquad (0,6). \]Vertices of a Feasible Region
A vertex is a corner point where boundary lines meet.
Vertices are especially important in linear programming because a linear objective, when it attains an optimum over a polygonal feasible region, has an optimal solution at a vertex, though multiple points may share the same optimal value.
Finding a Vertex Algebraically
Suppose two boundaries are
\[ x+y=10 \]and
\[ 2x+y=14. \]Subtract the first equation from the second:
\[ x=4. \]Then
\[ y=6. \]Therefore, the lines intersect at
\[ \boxed{(4,6)}. \]Active Constraints
A constraint is active or binding at a feasible point when it holds with equality.
If
\[ x+y\le10 \]and a feasible point satisfies
\[ x+y=10, \]then that constraint is active at the point.
Inactive Constraints
A constraint is inactive or nonbinding when there is slack.
If
\[ x+y\le10 \]and
\[ x+y=7, \]then the constraint has
\[ 10-7=3 \]units of slack.
Slack
For a constraint
\[ g(\mathbf{x})\le b, \]the quantity
\[ \boxed{b-g(\mathbf{x})} \]measures the unused capacity or slack.
Slack is zero when the constraint is active.
Surplus
For a lower-bound constraint
\[ g(\mathbf{x})\ge b, \]the amount
\[ \boxed{g(\mathbf{x})-b} \]measures how far the decision exceeds the minimum requirement.
Redundant Constraints
A redundant constraint does not further reduce the feasible region because it is already implied by other constraints.
For example, if
\[ x\le5 \]is already required, then an additional condition
\[ x\le10 \]adds no new restriction.
Conflicting Constraints
Constraints can contradict one another.
Consider
\[ x\ge8 \]and
\[ x\le5. \]No real number satisfies both.
Therefore, the feasible set is
\[ \boxed{\mathcal{F}=\varnothing}. \]Empty Feasible Regions
An optimization problem with no feasible solutions cannot be solved by searching for a best feasible point because no feasible point exists.
This situation is called infeasibility.
Detecting infeasibility is itself an important modeling task.
Unbounded Feasible Regions
A feasible region may extend indefinitely.
For example,
\[ x\ge0, \qquad y\ge0 \]defines the entire first quadrant.
Such a region is unbounded.
An unbounded feasible region does not automatically imply that the objective is unbounded, but it makes that possibility important to check.
Bounded Feasible Regions
A feasible region is bounded if it fits inside some sufficiently large finite region.
For example,
\[ x\ge0, \qquad y\ge0, \qquad x+y\le10 \]produces a bounded triangular region.
Closed Feasible Regions
A feasible region is closed when it contains all of its boundary points.
Non-strict inequalities such as
\[ g(\mathbf{x})\le b \]naturally include their boundaries.
Closedness becomes important when asking whether an optimum is attained.
Why Closed and Bounded Sets Matter
A central existence principle from analysis says that a continuous function on a nonempty compact set attains both a maximum and a minimum.
In Euclidean space, a set that is closed and bounded is compact.
Therefore, if \(f\) is continuous and \(\mathcal{F}\) is nonempty, closed, and bounded, then \(f\) attains global extrema on \(\mathcal{F}\).
This gives a powerful theoretical reason to study the geometry of the feasible set before optimizing.
Nonlinear Constraints
Constraints do not have to be linear.
For example,
\[ x^2+y^2\le25 \]restricts points to the disk of radius \(5\) centered at the origin.
Another example is
\[ xy\ge12. \]Nonlinear constraints can produce curved feasible boundaries.
Equality Constraints as Curves and Surfaces
The equality
\[ x^2+y^2=25 \]restricts feasible points to a circle rather than the entire disk.
In three dimensions,
\[ x^2+y^2+z^2=25 \]defines a sphere.
Equality-constrained optimization therefore often takes place on a lower- dimensional curve or surface.
General Constraint Notation
A constrained optimization problem may be written
\[ \boxed{ \begin{aligned} \text{minimize}\quad &f(\mathbf{x})\\ \text{subject to}\quad &g_i(\mathbf{x})\le0, \qquad i=1,\ldots,m,\\ &h_j(\mathbf{x})=0, \qquad j=1,\ldots,p. \end{aligned} } \]The functions \(g_i\) represent inequality constraints and the functions \(h_j\) represent equality constraints.
Why Constraints Are Often Written as \(g(x)\le0\)
A condition such as
\[ 2x+3y\le120 \]can be rewritten
\[ 2x+3y-120\le0. \]This standardized form is convenient in general optimization theory and algorithm design.
Domain Restrictions Can Function as Constraints
Sometimes a formula itself imposes restrictions.
If
\[ f(x)=\sqrt{x-2}, \]then real-valued evaluation requires
\[ x\ge2. \]Such domain conditions must be incorporated into the feasible set.
Discrete Constraints
A decision may be required to be integral:
\[ x\in\mathbb{Z}. \]A yes-or-no decision may be represented by
\[ x\in\{0,1\}. \]These restrictions create discrete feasible sets and lead to integer and combinatorial optimization.
Continuous Versus Discrete Feasible Sets
Under
\[ 0\le x\le10, \]a continuous decision variable can take any real value in the interval.
If instead
\[ x\in\mathbb{Z}, \]then the feasible choices are only
\[ 0,1,2,\ldots,10. \]The same numerical bounds can therefore produce very different feasible sets.
Mixed Constraints
A model may combine continuous, integer, and binary variables.
For example,
\[ x\ge0, \qquad x\in\mathbb{R}, \] \[ y\in\mathbb{Z}_{\ge0}, \] \[ z\in\{0,1\}. \]Such models arise in scheduling, facility planning, logistics, capital allocation, and network design.
Feasibility Before Optimality
A solution cannot be optimal unless it is feasible.
This gives a useful logical sequence:
\[ \boxed{ \text{first feasibility, then optimality} }. \]A candidate that gives an excellent objective value but violates a constraint is not an admissible solution.
Example: Production Planning
Suppose a company produces products \(x\) and \(y\).
Profit is
\[ P(x,y)=40x+60y. \]Labor imposes
\[ 2x+3y\le120. \]Machine time imposes
\[ x+y\le50. \]Production quantities must satisfy
\[ x\ge0, \qquad y\ge0. \]The complete model is
\[ \boxed{ \begin{aligned} \text{maximize}\quad &40x+60y\\ \text{subject to}\quad &2x+3y\le120,\\ &x+y\le50,\\ &x\ge0,\\ &y\ge0. \end{aligned} } \]Objective Contours and the Feasible Region
Once the feasible region is known, objective level sets can be compared against it.
For a linear objective
\[ f(x,y)=40x+60y, \]the contours satisfy
\[ 40x+60y=c. \]Moving these parallel lines through the feasible region provides a geometric way to see how objective values change.
Constraints Shape the Optimization Landscape
The same objective can produce different optimal decisions under different constraints.
For example, maximizing
\[ f(x,y)=x+y \]over a triangle, a disk, a rectangle, or an unbounded region can produce different solutions or even different questions about existence.
The geometry of the feasible set is therefore part of the optimization problem itself.
Constraints Can Force an Optimum onto a Boundary
An unconstrained optimum may lie outside the feasible region.
In that case, the constrained optimum often occurs on a boundary where one or more constraints become active.
This observation leads directly to constrained calculus methods and Lagrange multipliers.
Interior and Boundary Points
A feasible point is an interior point if a small neighborhood around it remains inside the feasible region.
A boundary point lies at the edge of the feasible region.
These distinctions matter because unconstrained derivative conditions generally apply directly to interior points, while boundary points require additional analysis.
Common Error: Checking Only One Constraint
A point must satisfy every constraint.
Passing three conditions and failing the fourth still makes the point infeasible.
Common Error: Reversing the Feasible Side
When graphing
\[ 2x+y\le8, \]the boundary line alone is not enough.
A test point should be used when necessary to determine which side satisfies the inequality.
Common Error: Forgetting Nonnegativity
If \(x\) and \(y\) represent quantities that cannot be negative, then
\[ x\ge0, \qquad y\ge0 \]must be included even when they are not visually emphasized in the verbal description.
Common Error: Treating an Equality Like an Inequality
The constraint
\[ x+y=10 \]permits only points on the line.
It does not permit the entire region below or above the line.
Common Error: Ignoring Units
In a resource constraint such as
\[ 2x+3y\le120, \]the terms must represent the same kind of quantity.
If the left side measures labor hours, the right side must also represent labor hours.
Common Error: Assuming the Feasible Region Is Nonempty
Before optimizing, verify that at least one point satisfies all the constraints.
Contradictory requirements can make the model infeasible.
A Reliable Constraint Workflow
- Define the decision variables and their units.
- Identify every practical restriction.
- Translate each restriction into an equation or inequality.
- Include sign, domain, integer, or binary restrictions.
- Check dimensional consistency.
- Standardize the constraints when useful.
- Test candidate points for feasibility.
- Graph the constraints when the problem has two variables.
- Identify the intersection forming the feasible region.
- Locate boundaries, vertices, and active constraints.
- Check whether the feasible set is empty, bounded, or unbounded.
- Only then proceed to optimization.
Practice 1: Feasible or Infeasible?
Determine whether
\[ (2,3) \]satisfies
\[ x+y\le6, \qquad x\ge0, \qquad y\ge0. \]Practice 2: Test a Point
Determine whether
\[ (4,3) \]satisfies
\[ 2x+y\le10, \qquad x+2y\le12. \]Practice 3: Write a Resource Constraint
Product \(x\) requires \(4\) machine hours per unit and product \(y\) requires \(6\) machine hours per unit.
No more than \(240\) machine hours are available.
Write the constraint.
Practice 4: Write a Minimum Requirement
A system must produce at least \(500\) total units from two activities \(x\) and \(y\).
Write the constraint.
Practice 5: Find a Boundary Intersection
Find the intersection of
\[ x+y=12 \]and
\[ 2x+y=16. \]Practice 6: Identify an Active Constraint
At the point
\[ (3,4), \]determine whether
\[ x+y\le7 \]is active or inactive.
Practice 7: Compute Slack
For
\[ 2x+y\le20 \]evaluate the slack at
\[ (4,5). \]Practice 8: Empty Feasible Set
Determine whether the following system has any feasible solution:
\[ x\ge6, \qquad x\le4. \]Practice 9: Discrete Feasibility
Suppose
\[ 0\le x\le5 \]and
\[ x\in\mathbb{Z}. \]List all feasible values of \(x\).
Practice 10: Build the Model
A company earns \(30\) dollars per unit of product \(x\) and \(50\) dollars per unit of product \(y\).
Each unit of \(x\) uses \(2\) labor hours and each unit of \(y\) uses \(4\) labor hours. At most \(160\) labor hours are available.
Total production cannot exceed \(60\) units.
Write the objective and constraints.
Practice Answers
Practice 1
Since
\[ 2+3=5\le6 \]and both coordinates are nonnegative,
\[ \boxed{(2,3)\text{ is feasible}.} \]Practice 2
First,
\[ 2(4)+3=11>10. \]Therefore,
\[ \boxed{(4,3)\text{ is infeasible}.} \]Practice 3
\[ \boxed{4x+6y\le240}. \]Practice 4
\[ \boxed{x+y\ge500}. \]Practice 5
Subtract
\[ x+y=12 \]from
\[ 2x+y=16. \]Then
\[ x=4. \]Therefore,
\[ y=8. \]The intersection is
\[ \boxed{(4,8)}. \]Practice 6
At \((3,4)\),
\[ 3+4=7. \]Equality holds, so
\[ \boxed{\text{the constraint is active}.} \]Practice 7
Resource use is
\[ 2(4)+5=13. \]Therefore, slack is
\[ 20-13=\boxed{7}. \]Practice 8
No real number satisfies both conditions, so
\[ \boxed{\mathcal{F}=\varnothing}. \]Practice 9
\[ \boxed{\{0,1,2,3,4,5\}}. \]Practice 10
The objective is
\[ \boxed{\text{maximize }P(x,y)=30x+50y}. \]The labor constraint is
\[ 2x+4y\le160. \]The production constraint is
\[ x+y\le60. \]Include
\[ x\ge0, \qquad y\ge0. \]What to Remember
Constraints determine which decisions are admissible.
The feasible set is the intersection of all constraint sets:
\[ \boxed{ \mathcal{F} = F_1\cap F_2\cap\cdots\cap F_m }. \]- equality constraints must hold exactly;
- inequality constraints define permitted regions;
- nonnegativity and domain restrictions are part of feasibility;
- a feasible point satisfies every constraint;
- an active constraint holds with equality;
- slack measures unused capacity;
- the feasible region may be bounded, unbounded, or empty;
- an optimal solution must always be feasible.
The governing principle is
\[ \boxed{ \text{first determine what is allowed, then determine what is best} }. \]Where We Go Next
Once the objective function and feasible region are established, the next question is how to recognize and classify the best values that occur within that region.
Some points are better only than nearby alternatives, while others are best across the entire feasible set.
The next lesson, Local and Global Extrema, develops this distinction and provides the conceptual foundation for the optimization methods that follow.