1. Introduction
Whenever I try to visualise a linear programming problem, I notice that the shape of the feasible region is always very neat. It never has dents, holes, or bends. This neat shape is something special — it is called a convex set. Understanding this idea makes it easier to see why optimum values in linear programming problems appear at corner points and why the whole method works smoothly.
These notes collect the basic ideas about convex sets, non-convex sets, and the connection between convexity and feasible regions.
2. What Is a Convex Set?
A set of points is called convex if, whenever I pick any two points inside it, the entire line segment joining those two points also lies inside the set. This simple idea gives the set a smooth, bulging-out shape with no inward dents.
2.1. Definition
The definition using math symbols is:
\( S \text{ is convex if for any } A, B \in S, \text{ the whole segment } AB \subseteq S. \)
Another way to express a point on the line segment between \(A\) and \(B\) is:
\( P = \lambda A + (1 - \lambda) B, \quad 0 \le \lambda \le 1. \)
If every such \(P\) stays in the set, then the set is convex.
2.2. Simple Visual Idea
To check if a region is convex, imagine drawing a straight line between any two points in the region. If the line stays completely inside, the region is convex. If it sticks out or passes through an empty area, the region is not convex.
3. Non-Convex Sets
A set that is not convex is called non-convex. These sets usually have holes, inward curves, or disconnected parts. When I draw a line between two points inside a non-convex region, part of the line may step outside the region.
3.1. Definition
A set is non-convex if there exist two points \(A\) and \(B\) in the set such that the line segment between them contains at least one point that is not in the set.
3.2. Examples of Non-Convex Shapes
Non-convex sets often look like:
- A C-shape or a U-shape region
- A region with a hole inside
- Two separate regions that do not touch
These shapes break the rule that the full line between two points must lie inside the region.
4. Convexity of Feasible Regions
One of the nicest facts about linear programming is this: Every feasible region formed by linear inequalities is convex. This property is what makes solving linear programming problems possible using simple graphical or corner-point methods.
4.1. Why Feasible Regions Are Convex
Each individual inequality like \(ax + by \le c\) represents a half-plane. A half-plane is always convex, because any two points in a half-plane can be joined by a segment that never leaves the half-plane.
The feasible region is created by intersecting several half-planes. The intersection of convex sets is always convex. Therefore, the feasible region automatically becomes convex.
4.2. Graphical Interpretation
When all the constraints are drawn and the overlapping shaded part is marked, the shape that appears is always a nice polygon-like region with straight boundaries. It never has dents or holes because every constraint is linear.
This makes the feasible region resemble a triangle, quadrilateral, or another convex polygon — or it may be unbounded but still convex.
4.3. Feasible Regions Are Always "Nice and Simple"
No matter how many linear constraints we add, the feasible region will always look like a clean convex region without strange curves or shapes. This makes the problem easier to understand and solve.
5. Why Convexity Matters in Linear Programming
Convexity is not just a geometric detail — it plays a key role in finding optimal solutions. Because the region is convex, linear objective functions behave in a predictable way, and the optimum always occurs at specific boundary points.
5.1. Linear Objective Functions on Convex Sets
A linear objective function looks like:
\( Z = ax + by \)
When this function is drawn as a line and moved parallel to itself, it will touch the feasible region at a corner point. This is because the highest (or lowest) value of a linear function over a convex region always occurs at an extreme point.
5.2. Corner Points and Extreme Points
The corners of a convex feasible region are called extreme points. These are intersection points of the boundary lines of constraints.
For linear programming, checking the objective function at just these corner points is enough to find the maximum or minimum value. This is a huge advantage and comes directly from the convexity of the region.
6. Examples to Connect Convexity and Feasibility
Looking at small examples helps in firmly understanding why feasible regions are convex and why this matters in solving problems.
6.1. Example: Feasible Region as a Triangle
Consider the system:
- \(x + y \le 8\)
- \(x \ge 0\)
- \(y \ge 0\)
The feasible region is the triangular area between the axes and the line \(x + y = 8\). Pick any two points inside this triangle — the line joining them will always stay within the triangle, making it convex.
6.2. Example: Unbounded but Still Convex Region
Consider the constraints:
- \(x - y \ge 2\)
- \(x \ge 0\)
The region opens infinitely in the northeast direction. Even though it stretches out, any two points inside it still have their connecting line lying completely in the region. So the region is unbounded but convex.
7. Convex vs Non-Convex Sets: Quick Comparison
| Feature | Convex Set | Non-Convex Set |
|---|---|---|
| Line Segment Between Points | Stays completely inside | May go outside |
| Shape | Smooth, no dents or holes | Holes, inward curves, irregular shapes |
| Feasible Regions in LP | Always convex | Never occurs in standard LP |
| Effect on Optimization | Optimum lies at corner points | Optimum may lie anywhere; harder to solve |