2.2 Single-Objective Optimization Problem

A typical single-objective optimization problem consists of a domain set \(\mathcal{D}\), an objective function \(f:\mathcal{D} \rightarrow \mathbb{R}\), and predicates \(\mathcal{C}_i\) on \(\mathcal{D}\), where \(i = 1,\ldots,m\) for some non-negative integer \(m\), called constraints.

We want to find, if possible, an element \(\mathbf{x} \in \mathcal{D}\) such that \(\mathcal{C}_i(\mathbf{x})\) holds for \(i = 1,\ldots,m\) and the value of \(f(\mathbf{x})\) is either as high (in the case of maximization) or as low (in the case of minimization) as possible. Compactly, single-objective optimization problems are written down as: \[\begin{array}{|rl} \min & f(\mathbf{x}) \\ \mbox{s.t.} & \mathcal{C}_i(\mathbf{x}) \quad i = 1,\ldots,m \\ & \mathbf{x} \in \mathcal{D}. \end{array}\] in the case of minimizing \(f(\mathbf{x})\), or \[\begin{array}{|rl} \max & f(\mathbf{x}) \\ \mbox{s.t.} & \mathcal{C}_i(\mathbf{x}) \quad i = 1,\ldots,m \\ & \mathbf{x} \in \mathcal{D}. \end{array}\] in the case of maximizing \(f(\mathbf{x})\).

Here, “s.t.” is an abbreviation for “subject to.” To be technically correct, \(\min\) should be replaced with \(\inf\) (and \(\max\) with \(\sup\)) since the minimum value is not necessarily attained. However, we will abuse notation and ignore this subtle distinction.

Some common domain sets include

  • \(\mathbb{R}^n_+\) (the set of \(n\)-tuples of non-negative real numbers)

  • \(\mathbb{Z}^n_+\) (the set of \(n\)-tuples of non-negative integers)

  • \(\{0,1\}^n\) (the set of binary \(n\)-tuples)

The Binary Knapsack Problem (BKP) can be formulated using the notation we have just introduced. Suppose that there are \(n\) items, with item \(i\) having weight \(w_i\) and value \(v_i > 0\) for \(i = 1,\ldots, n\). Let \(K\) denote the capacity of the knapsack.

Then the BKP can be formulated as: \[\begin{array}{|rl} \max & \sum\limits_{i = 1}^n v_i x_i \\ \mbox{s.t.} & \sum\limits_{i = 1}^n w_i x_i \leq K \\ & x_i \in \{0,1\} \quad i = 1,\ldots, n. \end{array}\]

In the above problem, there is only one constraint given by the inequality modeling the capacity of the knapsack. For the pirate example discussed previously, the BKP is: \[\begin{array}{|rl} \max & 2800 x_1 + 4400 x_2 + 1200 x_3 \\ \mbox{s.t.} & 20 x_1 + 40 x_2 + 30 x_3 \leq 50\\ & x_1, x_2, x_3 \in \{0,1\} \end{array}\]

2.2.1 Feasible and Optimal Solutions

An element \(\mathbf{x} \in \mathcal{D}\) satisfying all the constraints (that is, \(\mathcal{C}_i(\mathbf{x})\) holds for each \(i = 1,\ldots,m\)) is called a feasible solution and its objective function value is \(f(\mathbf{x})\). For a minimization (resp. maximization) problem, a feasible solution \(\mathbf{x}^*\) such that \(f(\mathbf{x}^*) \leq f(\mathbf{x})\) (resp. \(f(\mathbf{x}^*) \geq f(\mathbf{x})\)) for every feasible solution \(\mathbf{x}\) is called an optimal solution.

The objective function value of an optimal solution, if it exists, is the optimal value of the optimization problem. If an optimal value exists, it is by necessity unique, but the problem can have multiple optimal solutions. Consider, for instance, the following example: \[\begin{array}{|rl} \min & x+y \\ \mbox{s.t.} & x+y \geq 1 \\ & \begin{bmatrix} x \\ y \end{bmatrix} \in \mathbb{R}^2 \end{array}\] This problem has an optimal solution \[\begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1-t \\ t \end{bmatrix}\] for every \(t \in \mathbb{R}\), but a unique optimal value of 1.

2.2.2 Infeasible and Unbounded Problems

It is possible that there exists no element \(\mathbf{x} \in \mathcal{D}\) such that \(\mathcal{C}_i(\mathbf{x})\) holds for all \(i = 1,\ldots,m\). In such a case, the optimization problem is said to be infeasible. The following problem, for instance, is infeasible: \[\begin{array}{|rl} \min & x \\ \mbox{s.t.} & x \leq -1 \\ & x \geq 0 \\ & x \in \mathbb{R} \end{array}\] Indeed, any solution \(x\) must be simultaneously non-negative and smaller than \(-1\), which is patently impossible. An optimization problem that is not infeasible can still fail to have an optimal solution, however.

For instance, the problem \[\begin{array}{|rl} \max & x \\ \mbox{s.t.} & x \in \mathbb{R} \end{array}\] is not infeasible, but the \(\max/\sup\) does not exist since the objective function can take on values larger than any candidate maximum. Such a problem is said to be unbounded.

On the other hand, the problem \[\begin{array}{|rl} \min & e^{-x} \\ \mbox{s.t.} & x \in \mathbb{R}, \end{array}\] has a positive objective function value for every feasible solution. Even though the objective function value approaches \(0\) as \(x\to \infty\), there is no feasible solution with an objective function value of 0. Note that this problem is not unbounded as the objective function value is bounded below by 0.

2.2.3 Possible Tasks Involving Optimization Problems

Given an optimization problem, the most natural task is to find an optimal solution (provided that one exists) and to demonstrate that it is optimal. However, depending on the context of the problem, one might be tasked to find:

  • a feasible solution (or show that none exists);

  • a local optimum;

  • a good bound on the optimal value;

  • all global solutions;

  • a “good” (but not necessarily optimal) solution, quickly;

  • a “good” solution that is robust to small changes in problem data, and/or

  • the \(N\) best solutions.

In many contexts, the last three tasks are often more important than finding optimal solutions.

For example, if the problem data comes from measurements or forecasts, one needs to have a solution that is still feasible when deviations are taken into account.

Additionally, producing multiple “good” solutions could allow decision makers to choose a solution that has desirable properties (such as political or traditional requirements) but that is not represented by, or difficult to represent with, problem constraints.