How is it possible to use normals in the definition of a linear programming constraint?

Question

I'm trying to calculate the center of a feasible region in a system of linear inequalities using linear programming techniques.

After a bit of research, it looked like defining the center as a Chebyshev center is a reasonable way to go. For convex polyhedra, the formula to do it seems (relatively) straightforward, described in an article I found here.

The "linear" model they give is:

maximize r subject to:

$a^{T}_{i}x_{c} + r\|a_{i}\|_{2}~\leq ~ b_{i}$

This is using a normal to calculate the length of the radius of the Chebyshev ball.

Doesn't the inclusion of a vector normal mean that the inequality is no longer linear, and therefore, can't be solved using only linear optimization? However, the solution cited very clearly states that the formula given above is a linear optimization problem.

What am I missing?

Answer 1

OK, let me first turn my comment into an answer and then expand on @levand's last comment about constraint generation rules.

"You're missing the fact that the $a_i$ are parameters, not decision variables. As such, they can be manipulated at your leisure. The linear restriction refers only to the decision variables, i.e. $x$ and $r$. Note that in your inequality you have basically $\sum_{c \in C}a_c x_c,\forall i \in I$. It's like asking whether the expression $2^2x \ge 0$ is linear or not. Sure it is, it resolves to $4x\ge0$."

Now, in order to unpack constraints properly and figure out whether you're dealing with a linear or nonlinear problem, you can try the following:

1. Separate your parameters from your decision variables. Look for definition of decision variables either at the end of the program (e.g. $x \ge 0$, $x \in \mathbb{R}^n$, $x \in \{0, 1\}$, etc.) or under the argument of the objective function (e.g. $\max_{x\ge0}{c^Tx}$).
2. Scan the program and check whether there are any nonlinear operations on your decision variables. Examples include polynomials ($x^2 \le My$), absolute values ($|z| \le 0$), multiplication among decision variables ($x_i y_i = 4$) and so on. On the other hand, someone sloppy can write $x/y \le 5$, which is actually linear, since it resolves to $x \le 5y$; but $x/y = z$ with $x,y,z$ as decision variables is not linear!
3. Note that in some disciplines like electrical engineering, using vector notation may make the reading not as straightforward. For example, something like $x^Tx$ is actually $\sum_i x_i^2$. Something like $||x||$ translates into $\sqrt{x^Tx}$, where $x$ is understood to be a vector with coordinates in $n$ dimensions. Pay atention to gradient notation, Jacobian and Hessian matrices, and write, by hand, on a separate sheet of paper your derivation. It takes time, but you'll get better.
4. If you've identified any nonlinearities, see if you can linearize. This can make your life so much easier if you're actually interested in solving the program. I will not get into details, but (as a small example) there are known ways of linearizing absolute values or something like $x_i^2$ if $x_i$ is a binary decision variable. A second linearizing trick may also involve writing out the Talyor expansion for a constraint (or the objective function) and retaining just the first terms.

Answer 2

Full credit for this answer goes to @baudolino's comment; I just thought I'd type it up here for future reference.

The given equation is actually a "template", not something that you would solve directly using linear techniques. In this case, $a_{i}$ represents a particular vector of coefficients. Presumably, if you're using linear techniques, these coefficients are known values, not variables.

Taking the normal of a vector of known values yields a single number as a value, which you can then plug in to the equality without any loss of linearity.