Generating Random Polytopes for Nonconvex Optimization

Question

I am working on comparing different approaches for solving the following nonconvex optimization problem:

\begin{align*} \min_{x} \quad & g(x) \\ \text{s.t.} \quad & Ax = b, \\ & x \geq 0. \end{align*}

Specifically, I'm interested in generating random standard bounded polytopes defined by:

\begin{align*} S=\{x:~Ax = b, ~ x \geq 0\}, \end{align*}

where $A$ is an $m \times n$ matrix.

I've observed the following:

-When $m > n$ (more constraints than variables), global solvers tend to find optimal solutions easily and quickly. \

-When $m < n$ (more variables than constraints), global solvers often struggle to find optimal solutions. \end{itemize}

To ensure a fair comparison of different approaches, I'm wondering whether it's better to have $m > n$ or $n > m$ for these polytopes.

Answer 1

TLDR: for problems stated in standard form, it is customary to assume that $m < n$ (more variables than constraints) and that $A$ has full row rank.

The following only applies if your polyhedra are defined in standard form $S = \{ x \in \mathbb{R}^{n} | Ax = b, x \geq 0\}$ where $A \in \mathbb{R}^{m \times n}$.

Assuming $A$ has full row rank, the set defined by $Ax = b$ is an affine subspace of dimension $n - m$: this is because each linear equality constraint eliminates one degree of freedom. If you have more than $n$ constraints, i.e., if $m \geq n$, then $Ax = b$ may have no solution, in which case your problem will be infeasible. If your problem is feasible despite having more constraints than variables, then 1) $A$ does not have full row rank and 2) the feasible space is likely a low-dimensional affine subspace, which may explain why solvers have an easier time.