Penalty Methods

Now, it’s time to deal with bad constraints. Unfortunately, these are the most common kinds of constraints. They’re difficult to get rid of, and it’s also difficult to generate solutions that fulfill them.

For example, let’s see the following problem:

$$\min_{x, y} 2x + 3y\\ s.t.: x < y$$

We don’t know any exact or approximate method to solve this problem in this form. To get rid of the constraint, we’d need to make some analysis of the valid region of solutions in the plane. It’s not too hard to do so, but that’s because this is a simple problem.

If we use a genetic algorithm to solve this problem, we can generate valid initial solutions with a simple method. We first generate a random $y$ and then generate a random $x$, making sure it’s less than $y$. But then we’d need to make sure that mutated solutions and crossover solutions maintain the constraint. With PSO, this can be even harder.

We can see how difficult it is to solve a simple problem involving inequality constraints. What if we further complicate things?

$$\min_{a, b, c, d} 2a + 0.5b + 10c + d \\ s.t.: ab < c + d \\ a + c < \frac{d}{b}$$

Now we’re almost disarmed. We need to change our mindset and approach the problem in a different way. Let’s see how.