Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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 \ge 0$. –  baudolino Aug 22 '13 at 1:36
    
Based on what you have written, the problem is of the form $\max_{r} r \,\, \textrm{s.t.} \,\, r \leq \alpha_i$ for $i=1,2,\dots$. The norm in this case is just a number in the constraints. (And $r=\min_i(\alpha_i)$.) –  AnonSubmitter85 Aug 22 '13 at 1:40
    
@baudolino Ok, that makes sense at a high level; essentially the equation I gave is at a higher level of abstraction than the actual linear constraints. That said, I still feel a bit lost when it comes to actually understanding how to "unpack" that statement into actual linear inequalities. Any tips there? –  levand Aug 22 '13 at 2:32
add comment

2 Answers 2

up vote 1 down vote accepted

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.
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.