Is solving a convex optimisation for variables in $\mathbb{Q}$ just as hard as $\mathbb{Z}$?

54 Views Asked by At

If $\mathcal{F}^\mathcal{D}$ is taken to be the feasible set in domain $\mathcal{D}$, a convex optimisation problem of the form:

\begin{align*} \text{minimise} \quad & f(\textbf{x})\\ \text{subject to} \quad &\textbf{x} \in \mathcal{F}^\mathbb{R} \subseteq \mathbb{R}^{|\mathbb{x}|}, \end{align*}

is a linear programming problem and therefore very easy to solve (can be done in polynomial time). However, problems of the form:

\begin{align*} \text{minimise} \quad & f(\textbf{x})\\ \text{subject to} \quad &\textbf{x} \in \mathcal{F}^\mathbb{Z} \subseteq \mathbb{Z}^{|\mathbb{x}|}, \end{align*}

are much harder to solve, as the feasible region is not continuous.

Does the same thing hold for problems of the form:

\begin{align*} \text{minimise} \quad & f(\textbf{x})\\ \text{subject to} \quad &\textbf{x} \in \mathcal{F}^\mathbb{Q} \subseteq \mathbb{Q}^{|\mathbb{x}|}? \end{align*}

As far as I understand, there are uncountably many more numbers in the set $\mathbb{R} \setminus \mathbb{Q}$ than there are in $\mathbb{Q}$.

I know that, without any bounds, $|\mathbb{Q}| = |\mathbb{Z}|$; but if the region is finite then $\mathcal{F}^\mathbb{Z}$ would be finite, and $\mathcal{F}^\mathbb{Q}$ would be infinite - so I imagine solving a problem on $\mathbb{Q}$ would be easier than $\mathbb{Z}$.

But still, $|\mathcal{F}^\mathbb{Q}| < |\mathcal{F}^\mathbb{R}|$ by uncountably many elements. Does this mean that solving a convex optimisation problem on $\mathbb{R}$ is easier than solving one on $\mathbb{Q}$ which is easier than solving one on $\mathbb{Z}$?

I imagine that, practically, it makes no difference, as the numerical precision used by computer solvers mean that problems in $\mathbb{R}$ are treated like problems in $\mathbb{Q}$ anyway. But what about theoretically? is there any difference? have I made a wrong assumption by saying problems in $\mathbb{Z}$ "are much harder to solve, as the region is not continuous"?

1

There are 1 best solutions below

1
On BEST ANSWER

If a linear program is specified entirely using rational numbers, then every basic optimal solution will be rational (since it's the intersection of some of the constraints). In that case, there's nothing to worry about. In fact, the simplex method can be done using only rational numbers and get the exact optimal answer.

That's the most reasonable case to think about, so for the rest of this answer, I'll think about the unreasonable case.


If a linear program is specified using arbitrary real numbers, we can get in trouble. For example, $$\{(x,y) \in \mathbb R^2 : x+y \ge 1, y = \sqrt 2x\}$$ contains infinitely many points, but $$\{(x,y) \in \mathbb Q^2 : x+y \ge 1, y = \sqrt 2x\}$$ contains none.

Given a system of equations, we should be able to deduce a few more equations that always hold if the variables are rational, as long as we can tell when coefficients are linearly independent over the rationals. For example, if we know that $\pi$ is irrational, then over $\mathbb Q$, we have $$x + (\pi+1)y + 2\pi z = 1 \implies \begin{cases}x + y = 1 \\ y + 2z = 0\end{cases}$$ by writing both sides in the $\{1,\pi\}$ basis and concluding that the coefficients of $1$ and $\pi$ must be equal. Once we've done that, we have a rational system to solve, and this reduces a linear program in equational form (including $A\mathbf x = \mathbf b$ with $\mathbf x \ge \mathbf 0$, or anything else where all the inequalities are already rational) to one with rational coefficients.

Things are slightly trickier if you have a system of inequalities: say, $\{\mathbf x \in \mathbb Q^n : A\mathbf x \le \mathbf b, \mathbf x \ge \mathbf 0\}$. The weird thing is that the slack variables are real: we can transform this linear program into $$\{(\mathbf x, \mathbf s) \in \mathbb Q^n \times \mathbb R^m : A\mathbf x + I\mathbf s = \mathbf b, \mathbf x \ge \mathbf 0, \mathbf s \ge \mathbf 0\}$$ I can't think of a good way to deal with these.

It's possible that the optimal real solution can be approximated arbitrarily well by rational solutions. This happens when the feasible region is full-dimensional, for instance. In general, however, we can only say that the optimal real solution is approximated arbitrarily well by rational points that are arbitrarily close to feasible.