Optimization: Standard Form

The standard form of linear optimization problems is:

$$ \begin{align*} \underset{x\in \mathbb{R}^n}{\text{maximize}}\qquad& c^{T} x\\ \text{subject to:}\qquad& Ax \le b\\ & x \ge 0 \end{align*} $$

Transformation tricks #

• Conversion between min and max: $min f(x) = - max(-f(x))$
• $Ax >= b$ <=> $-Ax <= -b$
• $f(x) = 0$ <=> $f(x) >= 0$ and $f(x) <= 0$
• $x \in \mathbb{R} <=> u \ge 0, v \ge 0, x = u - v$

An example #

$$ \begin{align*} \underset{p, q}{\text{minimize}}\qquad& p + q\\ \text{subject to:}\qquad& 5p - 3q = 7\\ & 2p + q \ge 2 \\ & 1 \le q \le 4 \end{align*} $$

Let us transform the above.

First, $p$ is unbounded, so we have $p = u - v, u \ge 0, v \ge 0$.

The standard form is $x \ge 0$, but $q$ here does not conform to this format. We split $1 \le q \le 4$ into two parts: $q \ge 1$ and $q \le 4$. We can use the former one as something like $x \ge 0$. We can have $w = q + 1$. Because $q \ge 1$, so we have $w \ge 0$; because $q \le 4$, we have $w \le 3$.

Because the constraints of the standard form are like $Ax \le b$, so we need to change the constraints as well. According to the conversion tricks, we can have:

$$ 5p - 3q \le 7 \\ 5p - 3q \ge 7 \\ -2p - q \le -2 $$

Because

$$ p = u - v \\ q = w + 1 $$

we have

$$ 5u - 5v - 3w \le 10 \\ -5u + 5v + 3w \le -10 \\ -2u + 2v - w \le -1 $$

Do not forget that we have another constraint:

$$ w \le 3 $$

Solution #

Therefore, the standard form of the example linear problem is:

$$ \begin{align*} \underset{u, v, w}{\text{maximize}}\qquad& -u + v - w - 1\\ \text{subject to:}\qquad& 5u - 5v - 3w \le 10 \\& -5u + 5v + 3w \le -10 \\& -2u + 2v - w \le -1 \\& w \le 3 \\& u \ge 0 \\& v \ge 0 \\& w \ge 0 \end{align*} $$

It should be noted that the objective value of the standard form is the negative of that of the example problem.

Last modified on 2023-03-22