07. Problem Formulation — Variables, Objectives, Constraints, and the Feasible Region

// CORE 1/7 — decision variables, objective function, constraints, feasible region

An optimization problem does not begin with an algorithm. The problem must first be written precisely. If the formulation is wrong, a fast algorithm merely reaches the wrong answer faster.

Standard form

The most basic optimization problem is written as

$$\begin{aligned} \min_x\quad & f(x)\\ \text{subject to}\quad & g_i(x)\le 0,\quad i=1,\dots,m,\\ & h_j(x)=0,\quad j=1,\dots,p. \end{aligned}$$

This one expression contains four components.

Decision variables

Decision variables are the values we can choose directly. They are usually written as $x$.

Examples:

• Model parameters
• Design dimensions
• Production volume
• Route waypoints
• Experimental conditions

A good variable must be "something that can be changed." Values that cannot be chosen directly, such as weather or material properties, are more naturally treated as parameters or uncertainty rather than variables.

Objective function

The objective function defines what to minimize or maximize:

$$f(x):\mathbb{R}^n\to\mathbb{R}.$$

Because an optimization algorithm must compare scalar objectives, several performance measures must be combined into one number.

Example:

$$f(x)=\text{cost}(x)+\lambda\,\text{error}(x).$$

Here $\lambda$ adjusts the trade-off between cost and error.

Constraints

Constraints are conditions that must be satisfied.

Inequality constraint:

$$g_i(x)\le 0.$$

Equality constraint:

$$h_j(x)=0.$$

The ranges of variables can also be restricted directly with box constraints:

$$l\le x\le u.$$

A constraint is not "something that is better when improved," but "something that must not be violated." Mixing the objective and constraints changes the meaning of the problem.

Feasible region

The feasible region is the set of candidates satisfying every constraint:

$$\mathcal{F}=\{x\mid g_i(x)\le 0,\ h_j(x)=0\}.$$

Optimization ultimately finds the point inside $\mathcal{F}$ with the best $f(x)$:

$$x^\ast\in\arg\min_{x\in\mathcal{F}}f(x).$$

Example: least-squares regression

Given data $(a_i,y_i)$, fitting the linear model $a_i^\top x$ gives the problem

$$\min_x \frac{1}{2}\sum_{i=1}^{n}(a_i^\top x-y_i)^2.$$

• Decision variable: parameter vector $x$
• Objective function: sum of squared errors
• Constraints: none
• Feasible region: all of $\mathbb{R}^d$

Adding regularization changes the objective:

$$\min_x \frac{1}{2}\|Ax-y\|_2^2+\lambda\|x\|_2^2.$$

Formulation checklist

1. What can I actually adjust?
2. Can good and bad outcomes be compared as a scalar?
3. Which conditions must never be violated?
4. Is the feasible region nonempty?
5. Do the objective and constraints have consistent units or appropriate scales?

Next: Mathematical Foundations