Constrained Optimization

At this point, we can solve almost any optimization problem either using exact, approximate, or heuristic solutions. But we haven’t learned any method to deal with constraints.

Remember the general form of an optimization algorithm:

$$\min_x f(x) \\ s.t.: x \in C$$

Here, $x$ can be a number, a vector, or a matrix. The second line is a constraint. It tells us that $x$ has to fulfill some properties.

Constraints

Constraints are restrictions over the set of all possible solutions. When we have constraints, we can’t consider all the solutions anymore; we can only consider the solutions that fulfill the constraints. This space of valid solutions is called the feasible region. In contrast, the set of invalid solutions is the unfeasible region.

It’s tempting to think that constraints are good. After all, they cut the solution space and make it smaller so we need to explore fewer solutions. The reality is quite different though. Although sometimes constraints make our lives easier, most of the time they complicate things. For example, it’s very difficult to obtain the feasible region and get rid of the unfeasible one. So we need to check if a solution is valid, which becomes an additional step in the algorithm and can heavily increase runtime.

But we can use other techniques to deal with constraints. We’ll learn how to eliminate them by modifying the target function. When we visit methods to deal with specific problems, we’ll learn another way to deal with constraints in those problems.

Equality and inequality constraints

Although a constraint can have many forms, there are two main types: equality and inequality constraints. These are the most common ones in optimization. For example, consider the following problem:

$$\min_{x, y} -3x + 12y \\ s.t: 3x + 4y \leq 9 \\ 3x + 3y \geq 3 \\ 3x + 6y \geq 8$$

The constraints are all inequality constraints. They have one of the inequality comparison operators ($<$, $>$, $\leq$, and $\geq$). Each of these constraints divides the plane into two regions: feasible and unfeasible. The intersection of the feasible region defined by each of those constraints is the feasible region of the problem. See the following figure:

Here, the feasible region is in light blue. Each of the lines that enclose this region is the division of the original plane by each of the previous constraints. So, the equality constraints create a feasible region that’s a subset of the original solution space. This subset has the same dimensions as the original space, i.e., if the original space is a 2D plane, then the feasible region is also a 2D plane (although this region might be bounded).

What happens with equality constraints?

Let’s add an equality constraint to the previous problem:

$$\min_{x, y} -3x + 12y \\ s.t: 3x + 4y \leq 9 \\ 3x + 3y \geq 3 \\ 3x + 6y \geq 8 \\ 2x + 3y = 5$$

In the following graph, we added the new constraint.

Now there’s a red line crossing our previous feasible region. Instead of defining a new region of the same dimension as the original space, equality constraints create a new region with a smaller dimension. In this case, the 2D region becomes a 1D line segment. The new feasible region is the segment of the red line that lies inside the light blue region. Our solution should be a point on this line segment.

We should keep in mind that the feasible region for the entire problem is the intersection of the feasible regions defined by each constraint. Thus, if this intersection is empty, then the problem is said to be unfeasible and has no solution.

For example, if the line of the equality constraint were entirely outside the light blue region, then the intersection of all feasible regions would be empty and the problem would be unfeasible.

We’ll learn how to deal with different types of constraints and how to use the techniques we already learned to solve constrained problems.