1

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.

Darcy Olson
  • 65

2 Answers2

1

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$).

mvw
  • 34,562
0

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.

copper.hat
  • 172,524