0
$\begingroup$

I'm reading through my first textbook on linear optimization. The book states a theorem without proof and I'd like to understand why it's true.

Glossary of Terms:

Definition 1

The problem

Maximize $f(x_1,x_2,\cdots,x_n)=c_1x_1+c_2x_2+\cdots+c_nx_n$

Subject to $a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n\leq b_1$

$a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n \leq b_2$

$\cdots$

$a_{m1}x_1+a_{m2}x_2+ \cdots + a_{mn}x_n \leq b_n$

$x_1,x_2, \dots, x_n \geq 0$

is said to be a canonical maximization linear programming problem. The definition for minimization is analogous.

Definition 2

Let $x= (x_1,x_2,\cdots ,x_n), y=(y_1,y_2,\cdots ,y_n)\in$ R$^n$. Then $tx+(1-t)y$ for $0\leq t\leq 1$ is said to be the line segment between $x$ and $y$ inclusive.

Definition 3

The set of all points $(x_1,x_2, \cdots, x_n)$ satisfying the constraints of the canonical maximization problem is said to be the constraint set

Definition 4

Let $S$ be a subset of R$^n$. $S$ is said to be convex if, whenever $x$=$(x_1,x_2,\cdots,x_n)$,$y$$=(y_1,y_2,\cdots,y_n)\in S$, then

$tx+(1-t)y \in S$ for $0\leq t \leq 1$

The Theorem:

The constraint set of a canonical maximization or canonical minimization linear programming problem is convex.

My Work

I know I must show that $(x_1,x_2,\cdots ,x_n)$ i.e. the constraint set satisfies the requirements for convexity, I have no idea how to do this though. The question isn't homework, we were told to accept it, but I want to understand.

$\endgroup$
0
$\begingroup$

The constraint set of the above LP is $$ S = \{ x \mid A x \le b \} $$ where $A x \le b$ is short for: all components satisfy $(Ax)_i \le b_i$.

Let $x, y \in S$ then $$ A x \le b \\ A y \le b $$ Thus for $$ z = tx + (1-t) y \quad (t \in [0, 1]) $$ we have $$ A z = A(tx + (1-t) y) = t Ax + (1-t) Ay \le t b + (1-t) b = b $$ because $A$ is linear. So $z \in S$ as well. This means $S$ is convex.

The other condition $x \ge 0$ is not needed, as far as I can tell. It is just one of the conditions which makes this form canonical. (Arbitrary $x$ can be split in two parts $x^ \pm$ with $x^\pm \ge 0$).

$\endgroup$
  • $\begingroup$ thanks, this is very clear and concise. I appreciate the help. $\endgroup$ – Darcy Olson Jan 15 '16 at 3:05
  • $\begingroup$ The vector-wise $\le$ operator makes it more compact and readable. $\endgroup$ – mvw Jan 15 '16 at 3:21
0
$\begingroup$

Here is another way of looking at it.

If $C_1,..., C_n$ are convex sets, then it is easy to check that $C = \cap_k C_k$ is convex as well.

Any set of the form $\{x | a^T x \le b \}$ is convex. This is easy to check since the function $x \mapsto a^T x$ is linear and hence the level sets are convex.

The constraint set can be written as $F = \{x | a_1^T x \le b_1 \} \cap \cdots \cap \{x | a_m^T x \le b_m \} \cap \{ x | - x_1 \le 0 \} \cap \cdots \cap \{ x | - x_n \le 0 \}$, hence it is convex.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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