Constrained Optimization

Before any method: what is being chosen, what is being made as large or small as possible, and what rules out some of the choices. Most modelling failures happen here.

This matters because every method later in the subject assumes the problem has already been put in this shape. A learner who cannot separate the three parts will read a solution procedure as a ritual rather than as an answer to a question.

Every optimization problem answers one question: of all the choices I am allowed to make, which is best?

Three things must be settled before that question means anything. What may I choose? What counts as best? What am I not allowed to do?

The third is what makes the problem constrained. Without limits, most optimization questions are either trivial or have no answer, produce infinitely much, spend infinitely little. The constraints are not an obstacle bolted onto the problem; they are what makes it a problem worth asking.

A constrained optimization problem consists of three parts:

• Decision variables $x=(x_1,\dots ,x_n)$: the quantities the decision maker sets directly.
• An objective function $f(x)$, together with a direction, minimize or maximize.
• A feasible set $F$, the choices permitted, usually described by constraints.

The problem is written

A point $x\in F$ is a feasible solution. A feasible $x^{\star }$ with $f(x^{\star })\le f(x)$ for every $x\in F$ is an optimal solution, and $f(x^{\star })$ is the optimal value.

Linear programming is the case where $f$ is linear and $F$ is described by linear constraints. Nothing in the three-part structure depends on that.

A factory. We make chairs and tables. Each chair takes 2 hours of labour and 1 unit of timber; each table takes 3 hours and 4 units. We have 120 labour hours and 100 units of timber this week. Chairs earn 40, tables earn 90. What should we make?

• Decision variables: the number of chairs and the number of tables to make.
• Objective: maximize total earnings.
• Constraints: labour used cannot exceed 120 hours; timber used cannot exceed 100 units; neither quantity can be negative.

A diet. Find the cheapest daily menu meeting minimum requirements for protein and iron.

• Decision variables: how much of each food to include.
• Objective: minimize total cost.
• Constraints: protein at least the requirement; iron at least the requirement; amounts nonnegative.

Note what is not a decision variable in the factory problem: total earnings. Earnings are determined once the chairs and tables are fixed. A quantity the decision maker computes rather than sets belongs in the objective, not among the variables.

Consider the factory again: chairs earn 40, tables earn 90, and we want the most money.

Not a formulation. Let $P$ be the total profit. Maximise $P$ subject to the labour and timber limits.

Nothing here can be chosen. $P$ is not something the factory sets; it is what results once the chairs and tables are fixed. Written this way the constraints have nothing to constrain, and no method can act on the problem.

A formulation. Let $x_1$ be the number of chairs and $x_2$ the number of tables. Maximise $40x_1+90x_2$ subject to $2x_1+3x_2\le 120$, $x_1+4x_2\le 100$, $x_1,x_2\ge 0$.

Now the variables are the decisions, and profit is what the objective computes from them. The test is one question: could I write this number down before knowing the others? If not, it is derived, and it belongs in the objective or a constraint, never among the variables.