Formulating Optimization Problems
Objective function, constraints, and feasible region
Introductory Undergraduate Level
What is optimization?
Optimization means making some quantity as large or as small as possible under given conditions. We perform optimization in everyday life.
- Choosing a route that minimizes commuting time
- Shopping for the highest satisfaction within a budget
- Getting the most study benefit in a fixed amount of time
To handle these mathematically, we need to formulate the problem.
Objective function
Definition: Objective function
An objective function is a function representing the quantity you want to maximize or minimize. It takes a variable $x$ (or several variables $x_1, x_2, \ldots, x_n$) as input and outputs a real value.
$$f: \mathbb{R}^n \to \mathbb{R}$$Example 1: Maximizing area
Suppose we want to maximize the area of a rectangle with perimeter $20$.
Letting the two side lengths be $x$ and $y$:
- Perimeter condition: $2x + 2y = 20$, i.e. $y = 10 - x$
- Area (objective function): $f(x) = x \cdot y = x(10 - x) = 10x - x^2$
The goal is to maximize $f(x) = 10x - x^2$.
Example 2: Minimizing cost
When a factory produces $x$ units of product A and $y$ units of product B, suppose the total cost is
$$C(x, y) = 100x + 150y + 2000$$The goal is to minimize this cost function $C(x, y)$.
Constraints
Definition: Constraint
A constraint is a condition that the variables must satisfy. There are two main kinds of constraints.
- Equality constraint: of the form $g(x) = 0$
- Inequality constraint: of the form $h(x) \leq 0$ or $h(x) \geq 0$
Example 3: Constraints in a production plan
Suppose a factory's production plan has the following constraints.
- Raw-material limit: $2x + 3y \leq 100$ (inequality constraint)
- Labor-time limit: $x + 2y \leq 50$ (inequality constraint)
- Production is non-negative: $x \geq 0$, $y \geq 0$ (non-negativity constraint)
Unconstrained and constrained optimization
The case without constraints is called unconstrained optimization, and the case with constraints is called constrained optimization.
We first study the unconstrained case, and later chapters cover the constrained case (the method of Lagrange multipliers, etc.).
Feasible region
Definition: Feasible region
The feasible region (or feasible set) is the set of points that satisfy all the constraints.
$$\mathcal{F} = \{x \in \mathbb{R}^n : \text{all constraints are satisfied}\}$$A point in the feasible region is called a feasible solution.
Example 4: A two-variable feasible region
When the constraints are
$$x + y \leq 4, \quad x \geq 0, \quad y \geq 0$$the feasible region is the interior and boundary of the triangle shown below.
Maximization and minimization
Optimization problems come in two kinds: maximization problems and minimization problems.
Standard form
The standard form of a minimization problem:
$$\begin{aligned} \min_{x} \quad & f(x) \\ \text{subject to} \quad & g_i(x) = 0, \quad i = 1, \ldots, m \\ & h_j(x) \leq 0, \quad j = 1, \ldots, p \end{aligned}$$Here "subject to" means "subject to the conditions," and is sometimes abbreviated s.t.
Converting between maximization and minimization
Maximization and minimization problems can be converted into each other by changing the sign of the objective function.
$$\max_x f(x) = -\min_x (-f(x))$$Therefore it suffices to consider minimization problems. Still, we use both maximization and minimization depending on the context.
Worked examples
Example 5: Maximizing the volume of a box
From a square sheet of side $a$, cut squares of side $x$ from each corner and fold up the sides to make an open-top box. How should $x$ be chosen to maximize the volume?
Formulation:
- Base of the box: $(a - 2x) \times (a - 2x)$
- Height of the box: $x$
- Volume (objective function): $V(x) = x(a - 2x)^2$
Constraint:
$$0 < x < \dfrac{a}{2}$$($x$ must be positive and $a - 2x > 0$)
We solve this problem in the next chapter using differentiation.
Example 6: Shortest-distance problem
Find the shortest distance from the point $(3, 0)$ to a point on the parabola $y = x^2$.
Formulation:
Letting a point on the parabola be $(x, x^2)$, the squared distance from $(3, 0)$ is
$$D(x) = (x - 3)^2 + (x^2)^2 = (x - 3)^2 + x^4$$Since minimizing the distance is the same as minimizing the squared distance, we minimize $D(x)$.
Constraint:
$x$ is any real number (unconstrained optimization)
Example 7: A loss function in machine learning
In machine learning, we minimize the error between a model's predictions and the actual values. For example, in linear regression we minimize the loss function
$$L(w) = \displaystyle\sum_{i=1}^{n} (y_i - w^T x_i)^2$$Here $w$ are the model parameters and $(x_i, y_i)$ are the data.
Local and global optima
Definition: Local minimum and global minimum
A point $x^*$ is a local minimum if $f(x^*) \leq f(x)$ holds within some neighborhood of $x^*$.
A point $x^*$ is a global minimum if $f(x^*) \leq f(x)$ holds over the entire feasible region.
Note
In a general optimization problem, a local minimum is not necessarily a global minimum. There can be several local minima.
However, if the objective function is convex (covered in Convex Sets and Convex Functions), every local minimum is necessarily a global minimum. This is one reason convex optimization is so important.
Summary
- Objective function: the function to maximize or minimize
- Constraints: conditions the variables must satisfy (equality and inequality constraints)
- Feasible region: the set of points satisfying all constraints
- Maximization and minimization problems are interconvertible by changing signs
- Local optima and global optima generally differ
Frequently asked questions
What is an optimization problem?
It is the problem of minimizing (or maximizing) an objective function $f(x)$ subject to constraints $g_i(x) \leq 0$ and $h_j(x) = 0$. Many problems in engineering, economics, and machine learning—minimizing production cost, maximizing profit, finding the shortest route—can be formulated as optimization problems.
What is the difference between a local optimum and a global optimum?
A local optimum is a solution better than its neighbors, while a global optimum is the best solution over the entire region. In convex optimization the local optimum equals the global optimum, but non-convex problems can have several local optima. In practice the global optimum is often hard to find, so approximations and heuristics are used.
What is the difference between unconstrained and constrained optimization?
Unconstrained optimization $\min f(x)$ has no restriction on the search space, and candidate solutions are found from the derivative condition $\nabla f = 0$. Constrained optimization $\min f(x)$ s.t. $g(x) \leq 0$ uses the method of Lagrange multipliers for equality constraints and the KKT conditions for inequality constraints. Constraints narrow the solution space and make the optimality conditions more complex.