{
"cells": [
{
"cell_type": "markdown",
"id": "41d3d0cd",
"metadata": {},
"source": [
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "6ca50021",
"metadata": {},
"source": [
"# Chapter 2\n",
"## Exercise 2.1\n",
"\n",
"For each one of the following sets, determine whether it is a polyhedron.\n",
"\n",
"(a) The set of all $(x, y)\\in \\mathcal{R}^2$ satisfying the constraints:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"x\\cos\\theta+y\\sin\\theta&\\leq 1,\\quad \\forall~\\theta \\in[0, \\pi/2],\\\\\n",
"x&\\geq 0,\\\\\n",
"y&\\geq 0.\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"(b) The set of all $x\\in\\mathcal{R}$ satisfying the constraint $x^2 - 8x + 15 \\leq 0$.\n",
"\n",
"(c) The empty set.\n",
"\n",
"---\n",
"**Solution:**\n",
"\n",
"(a) The set equals $\\{ (x,y) | x \\geq 0, y \\geq 0, x^2 + y^2 \\leq 1 \\}$, which has the following image:"
]
},
{
"cell_type": "markdown",
"id": "cdc1180c",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "markdown",
"id": "3dd6caee",
"metadata": {},
"source": [
"It is a set represented by infinite linear constraints, while a polyhedron is formed by **finite** linear constraints.\n",
"\n",
"(b) The set is $\\{x\\geq 3, x\\leq 5\\}$ and is a polyhedron.\n",
"\n",
"(c) The empty set can be represented as $\\{x\\geq 0, x< 0\\}$ and is a polyhedron."
]
},
{
"cell_type": "markdown",
"id": "11b17e70",
"metadata": {},
"source": [
"```{note}\n",
"A polyhedron is formed by finite **linear** constraints.\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "ca101dc5",
"metadata": {},
"source": [
"## Exercise 2.2\n",
"\n",
"Let $f:\\mathcal{R}^n\\rightarrow\\mathcal{R}$ be a convex function and let $c$ be some constant. Show that the set $S = \\{\\bf{x} \\in \\mathcal{R}^n\\mid f(\\bf{x}) \\leq c\\}$ is convex.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "a8a978f8",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"Assume two random element $x_1$ and $x_2$ in the set $S$, therefore\n",
"\n",
"$$\n",
" \\begin{aligned}\n",
" f(x_1)\\leq c\\\\\n",
" f(x_2)\\leq c\n",
" \\end{aligned}\n",
"$$\n",
"\n",
"For a parameter $\\theta\\in [0, 1]$, \n",
"\n",
"$$\n",
" \\begin{aligned}\n",
" \\theta f(x_1)&\\leq \\theta c\\\\\n",
" (1-\\theta)f(x_2)&\\leq (1-\\theta) c\n",
" \\end{aligned}\n",
"$$\n",
"\n",
" Thus, \n",
" \n",
"$$\n",
" \\theta f(x_1)+ (1-\\theta)f(x_2)\\leq c\n",
"$$\n",
"\n",
"Since $f$ is a convex function, \n",
"\n",
"$$\n",
"f(\\theta x_1+(1-\\theta)x_2)\\leq \\theta f(x_1)+ (1-\\theta)f(x_2)\n",
"$$\n",
"\n",
"And this leads to\n",
"\n",
"$$\n",
"f(\\theta x_1+(1-\\theta)x_2)\\leq c\n",
"$$\n",
"\n",
"Therefore, the set $S$ is convex. $\\Box$\n"
]
},
{
"cell_type": "markdown",
"id": "c1297f61",
"metadata": {},
"source": [
"## Exercise 2.3\n",
"\n",
"**(Basic feasible solutions in standard form polyhedra with upper bounds)** Consider a polyhedron defined by the constraints $\\bf Ax = b$ and $\\bf 0\\leq x\\leq u$, and assume that the matrix $\\bf A$ has linearly independent rows. Provide a procedure analogous to the one in Section 2.3 for constructing basic solutions, and prove an analog of Theorem 2.4.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "072fb011",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
" The only difference of the above statement with Theorem 2.4 is that there are upper bounds for $\\bf x$. An analogous theorem is below:\n",
" \n",
" *Theorem*\n",
"\n",
"For a polyhedron defined by the constraints $\\bf Ax = b$, $\\bf A$ has dimensions $m\\times n$, $\\bf 0\\leq x\\leq u$ and $m$ independent rows. $\\bf x$ is a baisic solutions if and only if there exists indices $B(1), B(2),\\dots, B(m)$ such that:\n",
" \n",
" (a) the columns $\\mathbf{A}_{B(1)},\\dots, \\mathbf{A}_{B(m)}$ are linear independent.\n",
" \n",
" (b) if $i\\neq B(1),\\dots, B(m)$, $x_i=0$ or $x_i=u_i$.\n",
" \n",
" *Proof.*\n",
"\n",
"Assume a solution $x$ satsifying (a) and (b), and $U$ is the set of indecies that $x_i=u_i$, then\n",
"\n",
"$$\n",
"\\mathbf{x}_{B(1)}\\mathbf{A}_{B(1)}+\\dots+\\mathbf{x}_{B(m)}\\mathbf{A}_{B(m)}=b-\\sum_{i\\in U}x_iA_{B(i)}.\n",
"$$\n",
"\n",
"Because the columns $\\mathbf{A}_{B(1)},\\dots, \\mathbf{A}_{B(m)}$ are linear independent and $x$ is a feasible solution, the above equations have a unique solution. And thus $\\bf Ax=b$ has a unique solution. From Theorem 2.2, the $n$ active constraints are independent and thus $\\bf x$ is a basic solution.\n",
"\n",
"For the converse, we assume that $\\bf x$ is a basic solution and we will show that conditions (a) and (b) are true. Since $x$ is a basice solution, it is the solution of $n$ linear independent constraints. Therefore, the $n$ columns of $\\bf A$ and all the components in $\\bf x$ form the equations: \n",
"\n",
"$$\n",
"\\mathbf{x}_{B(1)}\\mathbf{A}_{B(1)}+\\dots+\\mathbf{x}_{B(n)}\\mathbf{A}_{B(n)}=b.\n",
"$$\n",
"\n",
"According to Theorem 2.2, the above equations has $n$ linear independent column vectors and thus has a unique solution. Assume $\\bf x$ has $k$ components that $x_i\\neq 0, x_i\\neq u_i$. Equivalently, $\\sum_{i=1}^k x_i\\mathbf{A}_{B(i)}=b-\\sum_{i\\in U}x_iA_{B(i)}$ has unique solution and therefore its columns $\\mathbf{A}_{B(1)},\\dots, \\mathbf{A}_{B(k)}$ are linear independent.\n",
"\n",
"We have shown that there are $k$ independent columns in $\\bf A$ and this implies $k\\leq m$. Since $\\bf A$ has $m$ independent rows, it also has $m$ independent columns. Now (a) is proved and we prove (b) next. If $i\\neq B(1), \\dots, B(m)$, $i\\neq B(1), \\dots B(k)$ and $x_i=0$ or $x_i=u_i$, (b) is also satisfied. \n",
"\n",
"$\\Box$\n",
" \n",
"```{note}\n",
"Theorem: if equations $Ax=b$ are consistent (has feasible solution), the columns of $\\bf A$ are linearly independent if and only if $\\bf Ax = b$ has a unique solution. (similar to Theorem 1.2)\n",
"\n",
"For $n$ decision variables, $n$ independent row constraints results in a unique solution and also results in $n$ independent column vectors\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "c4934887",
"metadata": {},
"source": [
"## Exercise 2.4\n",
"We know that every linear programming problem can be converted to an equivalent problem in standard form. We also know that nonempty polyhedra in standard form have at least one extreme point. We are then tempted to conclude that every nonempty polyhedron has at least one extreme point. Explain what is wrong with this argument.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "616351e2",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"Assume a nonempty polydron is a hyperplane ${\\bf a'x}=b$, for any point $x_0$ in it, we can find other two points $x_1$, $x_2$ that satisfies $x_0 = \\lambda x_1+(1-\\lambda)x_2$, so there can not be an extreme point in this polyhedron. "
]
},
{
"cell_type": "markdown",
"id": "73c21c59",
"metadata": {},
"source": [
"```{note}\n",
"A hyperplane is a polyhedron, but it does not has extreme points.\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "789579a3",
"metadata": {},
"source": [
"## Exercise 2.5\n",
"**(ExtreIne points of isoInorphic polyhedra)** A mapping $f$ is called affine if it is of the form $f(\\bf x) = Ax + b$, where $\\bf A$ is a matrix and $\\bf b$ is a vector. Let $P$ and $Q$ be polyhedra in $\\mathcal{R}^n$ and $\\mathcal{R}^m$ , respectively. We say that $P$ and $Q$ are isomorphic if there exist affine mappings $f: P\\rightarrow Q$ and $g: Q\\rightarrow P$ such that $g(f(\\bf x) = x$ for all $\\mathbf{x} \\in P$, and $f(g(\\bf y)) = y$ for all $\\mathbf{y} \\in Q.$ (Intuitively, isomorphic polyhedra have the same shape.)\n",
"\n",
"(a) If $P$ and $Q$ are isomorphic, show that there exists a one-to-one correspondence between their extreme points. In particular, if $f$ and $g$ are as above, show that $\\bf x$ is an extreme point of $P$ if and only if $f(\\bf x)$ is an extreme point of $Q$.\n",
"\n",
"(b) **(Introducing slack variables leads to an isoInorphic polyhedron)** Let $P = \\{\\mathbf{x} \\in \\mathcal{R}^n \\mid \\bf Ax \\geq b, x\\geq 0\\}$, where $\\bf A$ is a matrix of dimensions $k\\times n$. Let $Q = \\{\\bf (x, z) \\in \\mathcal{R}^{n+k} \\mid Ax - z = b, x \\geq 0, z \\geq 0\\}$. Show that $P$ and $Q$ are isomorphic.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "cd308241",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"(a) We first prove：if $\\bf x$ is the extreme point of $P$, then it is also the extreme point of $Q$.\n",
"\n",
"According to the definition of extreme point and Theorem 2.3 in the book, $\\bf x$ is also a vertex of $P$, then:\n",
"there exists a vector $\\bf c$ such that $\\bf c'x n$. Is it true that there exist exactly $k\\choose n$ bases that lead to this basic feasible solution? Here ${k\\choose k} = k! / (n! (k - n) !)$ is the number of ways that we can choose $n$ out of $k$ given items.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "e695fd7a",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"No.There may be dependent constrains in the $k$ active constraints. We can find a counter example:\n",
"\n",
"$$\n",
"\\begin{align*}\n",
"x\\geq 1\\\\\n",
"2x\\geq 2\n",
"\\end{align*}\n",
"$$\n",
"\n",
"In this example, $k=2$, $n=1$. However, there is only 1 base that leads to the basic feasible solution."
]
},
{
"cell_type": "markdown",
"id": "547c3f14",
"metadata": {},
"source": [
"## Exercise 2.12\n",
"\n",
"Consider a nonempty polyhedron $P$ and suppose that for each variable $x_i$ we have either the constraint $x_i\\geq 0$ or the constraint $x_i\\leq 0$. Is it true that $P$ has at least one basic feasible solution?\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "0c236bb8",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"Yes. For all the constraints $x_i\\geq 0$ or the constraint $x_i\\leq 0$, there are $n$ of them that are independent. According to Theorem 2.6 (c), there exists a basic feasible solution for this nonempty polyhedron.\n",
"\n",
"```{note}\n",
"According to Theorem 2.6, there must exist a basic fesible solution in a non-empty polyhedron if there are $m$ linear independent row coefficients constraints.\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "657181f9",
"metadata": {},
"source": [
"## Exercise 2.13\n",
"\n",
"Consider the standard form polyhedron $P = \\{\\mathbf x \\mid\\mathbf Ax = \\mathbf b, x \\geq 0\\}$. Suppose that the matrix $\\mathbf{A}$, of dimensions $m \\times n$, has linearly independent rows, and that all basic feasible solutions are nondegenerate. Let x be an element of $P$ that has exactly $m$ positive components.\n",
"\n",
"(a) Show that x is a basic feasible solution.\n",
"\n",
"(b) Show that the result of part (a) is false if the nondegeneracy assumption is removed.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "3a4d61ac",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"(a) *Proof.*\n",
"\n",
"We apply Theorem 2.4 to prove it. Since $\\mathbf x$ has $m$ positive components, let $B(1), \\dots, B(m)$ be its correponding indices. This already satifies Theorem 2.4 (b) that if $i\\neq B(1),\\dots,B(m)$, $x_i=0$. Now we need to prove Theorem 2.4 (a) that the columns $\\mathbf{A}_{B(1)},\\dots,\\mathbf{A}_{B(m)}$ are linear independent. We prove it by contradiction.\n",
"\n",
"If the columns $\\mathbf{A}_{B(1)},\\dots,\\mathbf{A}_{B(m)}$ are linear dependent, there exists one columnn that can be the linear combination of others. We suppose this column be $\\mathbf{A}_{B(m)}$, i.e.,\n",
"\n",
"$$\n",
"\\mathbf{A}_{B(m)}=\\alpha_1\\mathbf{A}_{B(1)}+\\dots+\\alpha_{m-1}\\mathbf{A}_{B(m-1)}.\\tag{1}\n",
"$$\n",
"\n",
"Since\n",
"\n",
"$$\n",
"\\mathbf{Ax}=\\sum_{i=1}^n\\mathbf{A}_ix_i=b,\\tag{2}\n",
"$$\n",
"\n",
"by putting (2) to (1), we have:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"&\\mathbf{A}_{B(1)}x_{B(1)}+\\dots+\\mathbf{A}_{B(m-1)}x_{B(m-1)}+\\mathbf{A}_{B(m-1)}x_{B(m-1)}+(\\alpha_1\\mathbf{A}_{B(1)}+\\dots+\\alpha_{m-1}\\mathbf{A}_{B(m-1)})x_{B(m)}=b\\\\\n",
"\\Rightarrow &\\mathbf{A}_{B(1)}(x_{B(1)}+\\alpha_1x_{B(m)})+\\dots+\\mathbf{A}_{B(m-1)}(x_{B(m-1)}+\\alpha_{m-1}x_{B(m)})=b.\n",
"\\end{align}\n",
"$$\n",
"\n",
"Since the matrix $\\mathbf{A}$ has $m$ independent rows, it must also have $m$ independent columns. We can find another column $\\mathbf{A}_{B(k)}$, $k\\neq B(1),\\dots, B(m)$ that is independent with $\\mathbf{A}_{B(1)},\\dots, \\mathbf{A}_{B(m-1)}$. And because $\\mathbf{Ax=b}$,\n",
"\n",
"$$\n",
"\\mathbf{A}_{B(1)}(x_{B(1)}+\\alpha_1x_{B(m)})+\\dots+\\mathbf{A}_{B(m-1)}(x_{B(m-1)}+\\alpha_{m-1}x_{B(m-1)})+0\\mathbf{A}_k=b.\\tag{3}\n",
"$$\n",
"\n",
"if $\\mathbf{A}_{B(1)},\\dots, \\mathbf{A}_{B(m-1)}$ are independent, this will result in a basic feasible solution $\\left(x_{B(1)}+\\alpha_1 x_{B(m)},\\dots, x_{B(m-1)}+\\alpha_{m-1}x_{B(m-1)}, 0\\right)$, which is degenerate and contradicts with the fact all basic solutions are nondegenerate.\n",
"\n",
"if $\\mathbf{A}_{B(1)},\\dots, \\mathbf{A}_{B(m-1)}$ are dependent, find the independent columns from them, and replenish with some remaining columns from the matrix $\\mathbf{A}$ to get $m$ independent columns. Repeat a similar procedure as above from (1) to (3), this will also lead to a degenerate basic feasible solution, which contradicts the nondegerate fact.\n",
"\n",
"$\\Box$\n",
"\n",
"(b) An counter example.\n",
"\n",
"A standard polyhedron:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"x_2+x_3=4\\\\\n",
"x_2=4\\\\\n",
"x_1,x_2,x_3\\geq 0\n",
"\\end{align}\n",
"$$\n",
"\n",
"One solution (1,4,0) is not a basic feasible solution."
]
},
{
"cell_type": "markdown",
"id": "a72576e5",
"metadata": {},
"source": [
"## Exercise 2.14\n",
"\n",
"\n",
"Let $P$ be a bounded polyhedron in $\\mathcal{R}^n$ , let $\\mathbf a$ be a vector in $\\mathcal{R}^n$ ,and let $b$ be some scalar. We define\n",
"\n",
"$$\n",
"Q = \\{\\mathbf{x}\\in P \\mid \\mathbf{a'x} = b\\} .\n",
"$$\n",
"\n",
"Show that every extreme point of $Q$ is either an extreme point of $P$ or a convex combination of two adjacent extreme points of $P$.\n",
"\n",
"---\n"
]
},
{
"cell_type": "markdown",
"id": "e63097c3",
"metadata": {},
"source": [
"\n",
""
]
},
{
"cell_type": "markdown",
"id": "edabd73b",
"metadata": {},
"source": [
"\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"id": "845ec1b4",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"*Proof.*\n",
"\n",
"\n",
"Assume the polyhedron $P$ is $\\{\\mathbf{x}\\in \\mathcal{R}^n\\mid\\mathbf{A_1x=b_1}, \\mathbf{x}\\geq 0\\}$, then $Q$ can be written as:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"\\mathbf{A_1x}&=\\mathbf{b_1}\\\\\n",
"a'x&=b\\\\\n",
"\\mathbf{x}&\\geq \\mathbf{0}\n",
"\\end{align}\n",
"$$\n",
"\n",
"Assume $\\mathbf{x}^{\\ast}$ is an extreme point of $Q$. Since the extreme point is also a basic feasible solution (Theorem 2.3), from the definition of 2.9, there are $n$ independent active constraints at $\\mathbf{x}^{\\ast}$. Thre are two scenarios:\n",
"\n",
"(1) if the $n$ independent active constraints are all in $\\mathbf{A_1x=b_1}$, then $\\mathbf{x^{\\ast}}$ is the basic feasible solution of $P$ by definition 2.9 and also an extreme point of it. \n",
"\n",
"(2) if $\\mathbf{a'x}=b$ is also an active constraint in them, then there are $n-1$ independent active constraints in $\\mathbf{A_1x=b_1}$. Let $I$ represent the row index in $\\mathbf{A_1x=b_1}$that are active consraints, i.e., $I=\\{i\\mid \\mathbf{a'^i_1x}=b^i_1\\}$. Then all the $\\mathbf{a'}_1^i (i\\in I)$ lie in a proper subspace of $\\mathcal{R}^n$. There exists a non-zero vector $\\mathbf{d}$ that are orthogonal to every $\\mathbf{a'}_1^i (i\\in I)$, i.e., $\\mathbf{a'}_1^i\\mathbf{d}=0$. Let us consider a line:\n",
"\n",
"$$\n",
"y=\\mathbf{x}^\\ast+\\lambda\\mathbf{d},\n",
"$$\n",
"\n",
"where $\\lambda$ is an arbitrary scalar. For all $i\\in I$, $\\mathbf{a'}_i^1(\\mathbf{x}^\\ast+\\lambda\\mathbf{d})=0$, thus the active constraints remain active at all points on this line. If we vary the values of $\\lambda$, some of the original active constraints will eventually be violated. Bus since $P$ is a bounded polyhedron,it does not contain a line. At the point where the orginal active constraints is about to be violated, there will be a new active constraint: $\\mathbf{a'_j}(\\mathbf{x}^\\ast+\\lambda\\mathbf{d})=b_j$. $\\mathbf{a'_2}$ is independent with $\\mathbf{a'}_1^i (i\\in I)$ because if not so, it will be a linear combination of $\\mathbf{a'}_1^i (i\\in I)$ and $\\mathbf{a'}_j\\mathbf{x}^\\ast=b_j$, which contradicts the definiton of $I$ ($j$ should also be in $I$ but it not). Hence, $\\mathbf{a'}_j\\mathbf{x}^\\ast\\neq b_j$ and $\\mathbf{a'_jd}\\neq 0$. By moving from $\\mathbf{x^\\ast}$ to $\\mathbf{x^\\ast}+\\lambda\\mathbf{d}$, we now have $n$ active constraints and the point is an extreme point of $P$.\n",
"\n",
"Since $\\lambda$ can be both positive and negative, we have two directions along the line $y=\\mathbf{x}^\\ast+\\lambda\\mathbf{d}$ and will reach two extreme points of $P$, which have $n-1$ same indepedent active constraints and are adjacent. The point $\\mathbf{x^\\ast}$ lies in the line segment between the two extreme points and it is a convex combination of them.\n",
"\n",
"$\\Box$\n",
"\n",
"The above two figures shows the situation when $P$ is a rectangular and $Q$ is a line.\n"
]
},
{
"cell_type": "markdown",
"id": "9cbc87d9",
"metadata": {},
"source": [
"## Exercise 2.15\n",
"\n",
"**(Edges joining adjacent vertices)** Consider the polyhedron $P = \\{\\mathbf{x} \\in \\mathcal{R}^n \\mid \\mathbf{a'_ix} \\geq b_i, i = 1,\\dots, m\\}$ . Suppose that $\\mathbf u$ and $\\mathbf v$ are distinct basic feasible solutions that satisfy $\\mathbf{a'_iu} = \\mathbf{a'_iv} = b_i , i = 1, \\dots, n - 1$, and that the vectors $\\mathbf{a}_l,\\dots, \\mathbf{a}_{n- 1}$ are linearly independent. (In particular, $\\mathbf u$ and $\\mathbf v$ are adjacent.) Let $L = \\{\\lambda\\mathbf{u} + (1 - \\lambda)\\mathbf{v}\\mid 0\\leq\\lambda\\leq 1\\}$ be the segment that joins $\\mathbf u$ and $\\mathbf v$. Prove that $L = \\{\\mathbf{z}\\in P \\mid \\mathbf{a'}_iz = b_i , i = 1, \\dots, n - 1\\}$ .\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "d1f310d6",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"*Proof.*\n",
"\n",
"In the polyhedron $\\{\\mathbf{z}\\in P \\mid \\mathbf{a'_iz} = b_i, i = 1,\\dots, n-1\\}$, there are $n-1$ independent rows and $n$ columns. From Exercise 2.10 (a), there are at most 2 basic feasible solutions. Since $\\mathbf{u}$ and $\\mathbf{v}$ are two of them, $\\mathbf{u}$ and $\\mathbf{v}$ are exactly the 2 extreme points in it and it is a line segment. And it is bounded for this line segment.. According to Theorem 2.9, a bounded polyhedron is the convex hull of its extreme points. $L = \\{\\lambda\\mathbf{u} + (1 - \\lambda)\\mathbf{v}\\mid 0\\leq\\lambda\\leq 1\\}$ is just the convex hull of extreme points $\\mathbf{u}$ and $\\mathbf{v}$.So it equals to the polyhedron $\\{\\mathbf{z}\\in P \\mid \\mathbf{a'_iz} = b_i, i = 1,\\dots, n-1\\}$.\n",
"\n",
"$\\Box$"
]
},
{
"cell_type": "markdown",
"id": "cccc0d07",
"metadata": {},
"source": [
"## Exercise 2.16\n",
"\n",
"Consider the set $\\{\\mathbf{x} \\in \\mathcal{R}^n \\mid x_l = \\dots = x_{n- l} = 0, 0\\leq x_n\\leq 1\\}$ .Could this be the feasible set of a problem in standard form?.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "661b18bc",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"No, we prove it by contradiction. From the given feasible set, we can see that $x_1=\\dots=x_n=0$ is a feasible solution to the problem. For the polehedron in standard form $\\{\\mathbf{Ax=b, x\\geq 0}\\}$, we get $\\mathbf{A0=0}$, i.e., $\\mathbf{b=0}$.\n",
"\n",
"From the given feasible set, we can also see that $x_1=\\dots,=x_{n-1}=0,x_n=1$ is also a feasbile solution, i.e., \n",
"\n",
"$$\n",
"A\\begin{bmatrix}\n",
"0\\\\\n",
"\\vdots\\\\\n",
"1\n",
"\\end{bmatrix}\n",
"=\\begin{bmatrix}\n",
"0\\\\\n",
"\\vdots\\\\\n",
"0\n",
"\\end{bmatrix}.\n",
"$$\n",
"\n",
"But \n",
"\n",
"$$\n",
"A\\begin{bmatrix}\n",
"0\\\\\n",
"\\vdots\\\\\n",
"2\n",
"\\end{bmatrix}\n",
"=2A\\begin{bmatrix}\n",
"0\\\\\n",
"\\vdots\\\\\n",
"1\n",
"\\end{bmatrix}\n",
"=\\begin{bmatrix}\n",
"0\\\\\n",
"\\vdots\\\\\n",
"0\n",
"\\end{bmatrix}.\n",
"$$\n",
"\n",
"Therefore, $x_1=\\dots=x_{n-1}=0,x_n={2}$ is also a feasible solution, which contradicts with the definiton of the given feasible set. So the set can not be the feasible set of problem in standard form.\n",
"\n",
"$\\Box$"
]
},
{
"cell_type": "markdown",
"id": "d5e23328",
"metadata": {},
"source": [
"## Exercise 2.17 \n",
"Consider the polyhedron $\\{\\mathbf{x} \\in \\mathcal{R}^n \\mid \\mathbf{Ax \\leq b, x \\geq 0}\\}$ and a nondegenerate basic feasible solution $\\mathbf{x}^*$ . We introduce slack variables $\\mathbf{z}$ and construct a corresponding polyhedron $\\{\\mathbf{(x, z)\\mid Ax + z = b, x \\geq 0, z \\geq 0}\\}$ in standard form. Show that $(\\mathbf{x^* , b-Ax^*})$ is a nondegenerate basic feasible solution for the new polyhedron.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "d97a21d3",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"*Proof.*\n",
"\n",
"Assume there are $m$ rows in $\\mathbf{A}$. We represent the original polyhedron as $P_0$ and the new polyhedron as $P_1$.\n",
"\n",
"(1) Apprently, $(\\mathbf{x^* , b-Ax^*})$ is feasible for $P_1$. \n",
"\n",
"(2) Next, we show that it is a baisc solution for $P_1$. To do so, we must show there are $m+n$ independent constraints that are active in $(\\mathbf{x^* , b-Ax^*})$.\n",
"\n",
"\n",
"Since $\\mathbf{x}^\\ast$ is a nondegenerate basic feasible solution, there are $n$ independent active constraints in the polyhedron $\\{\\mathbf{x} \\in \\mathcal{R}^n \\mid \\mathbf{Ax \\leq b, x \\geq 0}\\}$. Without loss of generality, we assume there are $k$ constraints in $\\mathbf{Ax\\leq b}$ and $l$ constraints in $\\mathbf{x}\\geq 0$ that are independent active ($k+l=n, k\\leq m$).\n"
]
},
{
"cell_type": "markdown",
"id": "7bdc4952",
"metadata": {},
"source": [
"\n",
"- Those original $n$ constraints in $P_0 $ are also independent active in $P_1$. For the $k$ active constraints in $\\mathbf{Ax\\leq b}$ of $P_0$, in $P_1$ they becomes $\\mathbf{Ax+0=b}$, i.e., there are $k$ components of $\\mathbf{z}$ that are 0. That is, there are $k$ independent active constraints in $\\mathbf{z}\\geq 0$ of $P_1$. Now we already have $k+n$ independent active constarints in $P_1$.\n",
"\n",
"- For the remnant $m-k$ constraints in $\\mathbf{Ax\\leq b}$ of $P_0$, they may be non active or dependent with the $k$ active constraints. \n",
"\n",
" - For those that are non active in $P_0$, i.e., $\\mathbf{Ax 0$,show that there exists some $\\overline{\\mathbf{b}}$ with the following two properties:\n",
"\n",
"(a) The absolute value of every component of $\\mathbf{b - \\overline{b}}$ is bounded by $\\epsilon$.\n",
"\n",
"(b) Every basic feasible solution in the polyhedron $P = \\{\\mathbf{x \\mid Ax \\leq \\overline{b}}\\}$ is nondegenerate\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "f2babde3",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"*Proof.*\n"
]
},
{
"cell_type": "markdown",
"id": "2679daab",
"metadata": {},
"source": [
"(a) for any element of $\\mathbf{b}$, since $b_i$ is a real number, there exists a $\\epsilon$ neighborhood, i.e., for any $\\epsilon>0$, the $\\epsilon$ neighborhood of $b_i$ is:\n",
"\n",
"$$\n",
"V_i=\\{x\\in\\mathcal{R}\\mid |b_i-x|<\\epsilon\\}.\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "12d9db9f",
"metadata": {},
"source": [
"Hence, we can find $\\overline{b}_i$ in the neighbourhood $V_i$ for any elements in $\\mathbf{b}$ to satisfy the requirement."
]
},
{
"cell_type": "markdown",
"id": "7c914f57",
"metadata": {},
"source": [
"(b) for any feasible solution $\\mathbf{x}^\\ast$, if this solution is degenerate in $P$, it means that there are excessive active constraints at $\\mathbf{x}^\\ast$. For any excessive active constraint $\\mathbf{a'x^\\ast}\\leq b_i$, we an change the value of $b_i$ a little bit by select one value from its $\\epsilon$ neighborhood to make this constraint nonactive at $\\mathbf{x}^\\ast$. Repeat this procedure, we can make all the excessive constraint unactive at $\\mathbf{x}^\\ast$. Hence, we can find the values of $\\mathbf{\\overline{b}}$ to make every basic feasible solution in the polyhedron nondegenerate.\n",
"\n",
"$\\Box$\n"
]
},
{
"cell_type": "markdown",
"id": "4826763d",
"metadata": {},
"source": [
"## Exercise 2.19* \n",
"\n",
"Let $P\\in R^n$ be a polyhedron in standard form whose definition involves $m$ linearly independent equality constraints. Its dimension is defined as the smallest integer $k$ such that $P$ is contained in some k-dimensional affine subspace of $\\mathcal{R}^n$.\n",
"\n",
"(a) Explain why the dimension of $P$ is at most $n - m$.\n",
"\n",
"(b) Suppose that $P$ has a nondegenerate basic feasible solution. Show that the dimension of $P$ is equal to $n - m$.\n",
"\n",
"(c) Suppose that $\\mathbf x$ is a degenerate basic feasible solution. Show that $\\mathbf x$ is degenerate under every standard form representation of the same polyhedron (in the same space $\\mathcal{R}^n$) . Hint: Using parts (a) and (b) , compare the number of\n",
"equality constraints in two representations of $P$ under which $\\mathbf x$ is degenerate and nondegenerate, respectively. Then, count active constraints.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "400b5d82",
"metadata": {},
"source": [
"**Solution:**"
]
},
{
"cell_type": "markdown",
"id": "c66bf1e4",
"metadata": {},
"source": [
"(a) \n",
"\n",
"If there is no feasible solutions in $P$, i.e., $P$ is empty, then the dimension of $P$ is 0.\n",
"\n",
"If there exists a feasible soltion, without loss of generality, we assume $P=\\{\\mathbf{x\\mid Ax=b}\\}$ and the feasible solution is $\\mathbf{x}_0$.\n",
"\n",
"Hence, $\\mathbf{Ax_0=b}$ and $\\mathbf{A(x-x_0)=0}$. The dimension of $P$ is the dimension of the null space of $\\mathbf{A}$ in the set of equations $\\mathbf{A(x-x_0)=0}$.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "64469cd1",
"metadata": {},
"source": [
"By the `Rank Theoreom`, \n",
"\n",
"$$\n",
"\\text{rank}(\\mathbf{A})+\\text{dim}(\\text{Nul}(A))=n \\tag{1}.\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "9f25a254",
"metadata": {},
"source": [
"Since $P$ involves $m$ linear independent equality constraints, $\\text{rank}(\\mathbf{A})\\geq m$ (or else there is no feasible solution for $P$ and its dimension is 0), $\\text{dim}(\\text{Nul}(A))\\leq n-m$.\n",
"\n",
"Therefore, bases on the two above situations, the dimension of $P$ is at most $n-m$."
]
},
{
"cell_type": "markdown",
"id": "9ff13bcd",
"metadata": {},
"source": [
"(b) If $P$ has a nondegerate basic feasible solution, there are exactly $m$ linear independent active constraints at this feasible solution and $\\text{rank}(A)=m$. By the equation (1), the dimension of $P$ is equal to $n-m$."
]
},
{
"cell_type": "markdown",
"id": "e699c09d",
"metadata": {},
"source": [
"(c) For two standard form representations of $P$, $\\mathbf{x}$ is a degenerate basic feasible solution for representation one. Hence, there are more than $m$ independent active constraints at $\\mathbf{x}$ and the dimension of $P$ is at larger than $n-m$. If $\\mathbf{x}$ is nondegerate for representation two, there is a contradiction that the dimension of $P$ is equal to $n-m$ by the conclusion of (b).\n",
"\n",
"Therefore, $\\mathbf{x}$ is degenerate under every stand form representation."
]
},
{
"cell_type": "markdown",
"id": "b6cd9633",
"metadata": {},
"source": [
"## Exercise 2.20 * \n",
"\n",
"Consider the Fourier-Motzkin elimination algorithm.\n",
"\n",
"(a) Suppose that the number $m$ of constraints defining a polyhedron $P$ is even. Show, by means of an example, that the elimination algorithm may produce a description of the polyhedron $\\Pi_{n-1}(P)$ involving as many as $m^2/4$ linear\n",
"constraints, but no more than that.\n",
"\n",
"(b) Show that the elimination algorithm produces a description of the one-dimensional polyhedron $\\Pi_1(P)$ involving no more than $m^{2^{n-1}}/2^{2^n-2}$ constraints.\n",
"\n",
"(c) Let $n = 2^P +p+ 2$, where $p$ is a nonnegative integer. Consider a polyhedron\n",
"in $\\mathcal{R}^n$ defined by the $8 {n \\choose 3}$ constraints\n",
"\n",
"$$\n",
"\\pm x_i\\pm x_j\\pm x_k\\leq 1, \\quad i < j < k \\leq n,\n",
"$$\n",
"\n",
"where all possible combinations are present. Show that after $p$ eliminations, we have at least\n",
"\n",
"$$\n",
"2^{2^P+2}\n",
"$$\n",
"\n",
"constraints. (Note that this number increases exponentially with $n$.)\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "0c1c3db5",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"*Proof.*\n"
]
},
{
"cell_type": "markdown",
"id": "b9ab9560",
"metadata": {},
"source": [
"(a) If the number of constraints is even, in the elimination algorithm to produce the polyhedron $\\Pi_{n-1}(P)$, the biggest number of invovled linear constraints happens when there are $m/2$ constraints that the coefficient $a_{i,n}$ for $x_n$ is positive, while the other $m/2$ constraints that $a_{i,n}$ is negative ($i=1,\\dots,m$). (If there are $k$ constraints that $a_{i,n}$ are positive and $m-k$ other constraints that $a_{i,n}$ are negative, then the total number of involved constraints is $k(m-k)$. By `GM-AM inequality`, $k(m-k)\\leq (\\frac{k+m-k}{2})^2=\\frac{m^2}{4}$)\n",
"\n",
"Hence, there are at most $\\frac{m}{2}\\times\\frac{m}{2}=\\frac{m^2}{4}$ involved constraints."
]
},
{
"cell_type": "markdown",
"id": "bb8b6d21",
"metadata": {},
"source": [
"(b) we prove it by intruduction. \n",
"\n",
"**Base case:** When $n=2$, it is trivial that the production of the one-dimensional polyhedron invoving no more than \n",
"\n",
"$m^{2^{n-1}}/2^{2^n-2}=m^2/4$ constraints. \n",
"\n",
"**Induction step:** Assume that when $n=k$, the production of one-dimensional polyhedron invovles no more than $m^{2^{k-1}}/2^{2^k-2}$ constraints with $m$ constraints in the $k$ dimensional polyhedron. We now prove that the statement holds for $n=k+1$.\n",
"\n",
"When $n=k+1$, if the number of the constraints $m$ is even, the elimination from $k+1$ dimension to $k$-dimensional polyhedron involves $m^2/4$ constraints. By the assumption, the number of involved constraints to eliminate the dimension from $k$ to $1$ involves:"
]
},
{
"cell_type": "markdown",
"id": "8bab1550",
"metadata": {},
"source": [
"$$\n",
"\\frac{(m^2/4)^{2^{k-1}}}{2^{2^k-2}}=\\frac{m^{2^k}}{4^{2^{k-1}}2^{2^k-2}}=\\frac{m^{2^k}}{2^{2^{k+1}-2}}\n",
"$$\n",
"\n",
"constraints, which meets the requirement; if $m$ is old, the number of invovled constraints is no more than the situation when there are $m-1$ constraints, which also meets the requirement. Now the proof is complete."
]
},
{
"cell_type": "markdown",
"id": "48069342",
"metadata": {},
"source": [
"(c) After $p$ eliminations, we eliminate the dimension of the polyhedron $P$ from $2^p+p+2$ to $2^p+2$ and there are still $2^p+2$ variables left in the polyhedron. We first show that since $n=2^p+p+2$, if we eliminate one variable with minimum index in the remnant variables one time (i.e., eliminate $x_1$ in the first elimination, eliminate $x_2$ in the second elimination, and so on), after $p$ elimnations, we have at least some constraints of the following form: "
]
},
{
"cell_type": "markdown",
"id": "0d66b6ac",
"metadata": {},
"source": [
"$$\n",
"\\pm x_{n-2^p-1}\\dots\\pm x_n\\leq 2^p.\\tag{1}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "6faecf8a",
"metadata": {},
"source": [
"**Base case:** If $p=1$, $n=5$. There are constraints $\\pm x_1\\pm x_2 \\pm x_3\\leq 1$, $\\pm x_1\\pm x_4 \\pm x_5\\leq 1$ (they only share one varible $x_1$) in the polyhedron. After eliminating $x_1$ from the two sets of constraints, we can get:"
]
},
{
"cell_type": "markdown",
"id": "10fbf8d9",
"metadata": {},
"source": [
"$$\n",
"\\pm x_2\\pm x_3 \\pm x_4 \\pm x_5\\leq 2,\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "f42eee22",
"metadata": {},
"source": [
"i.e, the base case hold."
]
},
{
"cell_type": "markdown",
"id": "d5cac89a",
"metadata": {},
"source": [
"**Induction step:** Assume after $k$ eliminations, we have at least the following constraints (we replace $n$ with $2^k+k+2$ in the formula (1)):"
]
},
{
"cell_type": "markdown",
"id": "cd2a2468",
"metadata": {},
"source": [
"$$\n",
"\\pm x_{k+1}\\pm x_{k+2}\\dots\\pm x_{2^k+k+2}\\leq 2^k. \\tag{2}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "0af71ac5",
"metadata": {},
"source": [
"Now we prove the situation after $k+1$ eliminations. When $p=k+1$, there are $n=2^{k+1}+k+3$ variables."
]
},
{
"cell_type": "markdown",
"id": "4d93d636",
"metadata": {},
"source": [
"Since we can find another set of constraints below after the $k_{\\text{th}}$ elimination (when we eliminate $k$ times from the constraints with 3 variables in the set $x_1$, $x_2$, $\\dots$, $x_{k+1}$, $x_{2^k+k+3}$, $\\dots$, $x_{2^{k+1}+k+3}$ from the original polyhedron. Recall that there are $2^k+k+2$ variables in the above set),\n",
"\n",
"$$\n",
"\\pm x_{k+1}\\pm x_{2^k+k+3}\\dots\\pm x_{2^{k+1}+k+3}\\leq 2^k,\\tag{3}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "f662c016",
"metadata": {},
"source": [
"which only share one variable with formula (2). By eliminating $x_{k+1}$ from (2) and (3), we can get the following constraints:"
]
},
{
"cell_type": "markdown",
"id": "bc692a35",
"metadata": {},
"source": [
"$$\n",
"\\pm x_{2^k+k+3}\\dots\\pm x_{2^{k+1}+k+3}\\leq 2^k,\n",
"$$\n",
"\n",
"which meets the requirement."
]
},
{
"cell_type": "markdown",
"id": "393b4522",
"metadata": {},
"source": [
"Since formula (1) holds after $p$ eliminations, there are actually $2^{2^p+2}$ constraints in the formula (1).\n",
"\n",
"$\\Box$"
]
},
{
"cell_type": "markdown",
"id": "d539ee3a",
"metadata": {},
"source": [
"```{note}\n",
"the proof for (c) is non-trivial!\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "66597652",
"metadata": {},
"source": [
"## Exercise 2.21 \n",
"\n",
"Suppose that Fourier-Motzkin elimination is used in the manner described at the end of Section 2.8 to find the optimal cost in a linear programming problem. Show how this approach can be augmented to obtain an optimal solution as well.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "90acc51c",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"At page 74 in the text book, we know that by adding a new variabel $x_0$ and making it euqal to the objective function, i.e., $x_0=c'x$, we can get the optimal cost after eliminating the polyhedron $n$ times with only variable $x_0$ in it."
]
},
{
"cell_type": "markdown",
"id": "88b56389",
"metadata": {},
"source": [
"Let us find the solution by backtracking. We use the same notations as at Page 72 in the text book. After eliminating $n$ times, there are only one variable $x_0$ in the constraints in the following form:"
]
},
{
"cell_type": "markdown",
"id": "a4327285",
"metadata": {},
"source": [
"$$\n",
"\\begin{align}\n",
"d_j+f_j'x_0&\\geq d_i + f_i'x_0,\\quad \\text{if } a_{i,1}>0 \\text{ and } a_{j,1}<0,\\tag{1}\\\\\n",
"0&\\geq d_k+f'_kx_0.\\quad \\text{if } a_{k,n}=0.\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "b6fc24ca",
"metadata": {},
"source": [
"From the process of eliminating $x_1$ in the previous elimnation, we know that:\n",
"\n",
"$$\n",
"d_j+f_j'x_0\\geq x_1, \\quad\\forall a_{j,1}<0,\\tag{2}\n",
"$$\n",
"\n",
"and \n",
"\n",
"$$\n",
"d_i+f_i'x_0\\leq x_1, \\quad\\forall a_{i,1}>0.\\tag{3}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "2cfb7188",
"metadata": {},
"source": [
"With the above two sets of constraints in which there is only one unknow variable $x_1$ in them, we can get a value of $x_1$ since two constraints among them will force one exact value for $x_1$ (it is because that the smallest element of $x_0$ happens at one constraint in (1) that the left hand side is equal to the right hand side, while that means the left hand side of one constraint from (2) is equal to the left hand side of another constraint from (3). This will force one value for $x_1$)"
]
},
{
"cell_type": "markdown",
"id": "ee95ef36",
"metadata": {},
"source": [
"Repeat this process, we can get all other values of the solution."
]
},
{
"cell_type": "markdown",
"id": "27b714cc",
"metadata": {},
"source": [
"## Exercise 2.22 \n",
"\n",
"Let $P$ and $Q$ be polyhedra in $\\mathcal{R}^n$. Let $P + Q = \\{\\mathbf{x + y} \\mid x \\in P, \\mathbf{y} \\in Q\\}$.\n",
"\n",
"(a) Show that $P + Q$ is a polyhedron.\n",
"\n",
"(b) Show that every extreme point of $P + Q$ is the sum of an extreme point of $P$ and an extreme point of $Q$.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "8fd1f1f9",
"metadata": {},
"source": [
"**Solution:**\n",
"\n",
"*Proof.*\n"
]
},
{
"cell_type": "markdown",
"id": "5c634646",
"metadata": {},
"source": [
"(a) Let $P=\\{\\mathbf{x\\mid A_1x\\geq b_1}\\}$ and $Q=\\{\\mathbf{y\\mid A_2y\\geq b_2}\\}$. We can make another polyhedron $M$ as follows\n",
"\n",
"$$\n",
"M=\\{\\mathbf{(x,y,z)}\\mid \\ \\mathbf{A_1x\\geq b_1, A_2x\\geq b_2, z=x+y}\n",
"\\}.\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "5e737f96",
"metadata": {},
"source": [
"Then we can use Fourier-Motzkin method to eliminate the variables $\\mathbf{x, y}$ and only keep $\\mathbf{z}$. After the elimination, we get $P+Q$. In other words, $P+Q$ is the projection of $M$ to the $\\mathbf{z}$ coordinates."
]
},
{
"cell_type": "markdown",
"id": "b9ca3644",
"metadata": {},
"source": [
"(b) We prove it by contradiction. If the extreme point $z_0$ of $P+Q$ is the sum of one non-extreme point $x_0$ of $P$ and another point $y_0$ of $Q$, then we can find two other points $\\mathbf{v_1, v_2}$ in $P$ that $\\mathbf{x_0}=\\lambda \\mathbf{v_1}+(1-\\lambda)\\mathbf{v_2}$, in which $0\\leq \\lambda\\leq 1$. Hence,"
]
},
{
"cell_type": "markdown",
"id": "7c671ab4",
"metadata": {},
"source": [
"$$\n",
"\\mathbf{z_0=x_0+y_0}=\\lambda \\mathbf{v_1}+(1-\\lambda)\\mathbf{v_2}+\\mathbf{y_0}=\\lambda (\\mathbf{v_1+y_0})+(1-\\lambda)(\\mathbf{v_2+y_0)}.\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "7f78ce44",
"metadata": {},
"source": [
"Since $\\mathbf{v_1+y_0}$ and $\\mathbf{v_2+y_0}$ are also in $P+Q$, it contradicts with the fact that $\\mathbf{z_0}$ is the extreme point of $P+Q$. Another point is the extreme point of $Q$ follows similarly.\n",
"\n",
"$\\Box$"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "431ed426",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "7675aff3",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "e642243d",
"metadata": {},
"source": [
"## Exercise 2.30\n",
"\n",
"If $f$ is K-convex, $\\xi^x$ follows a Binomial distribution $B(x, p)$ and $|\\mathbb{E}[f(x-\\xi^x)]|<\\infty$, then $g(x)=\\mathbb{E}[f(x-\\xi^x)]$ is also K-convex.\n",
"\n",
"---"
]
},
{
"cell_type": "markdown",
"id": "d27cdd74",
"metadata": {},
"source": [
"\n",
"*Proof.*\n",
"\n",
"We prove it by the induction to the domain of $g(x)$.\n",
"\n",
"We first prove that $g(x)$ is K-convex , we first show that:\n",
"\n",
"$$\n",
"K+g(2)-g(1)\\geq g(1)-g(0),\n",
"$$\n",
"\n",
"i.e., \n",
"\n",
"$$\n",
"K+g(2)+g(0)\\geq 2g(1).\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "ddaa19bb",
"metadata": {},
"source": [
"Since\n",
"\n",
"$$\n",
"\\begin{align}\n",
"g(2)&=\\Pr(\\xi^2=0)f(2)+\\Pr(\\xi^2=1)f(1)+\\Pr(\\xi^2=2)f(0)=\\overline{p}^2f(2)+2\\overline{p}pf(1)+p^2f(0),\\\\\n",
"g(1)&=\\Pr(\\xi^1=0)f(1)+\\Pr(\\xi^1=1)f(0)=\\overline{p}f(1)+pf(0),\\\\\n",
"g(0)&=\\Pr(\\xi^0=0)f(0)=f(0),\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "9bbe64ce",
"metadata": {},
"source": [
"we can get:\n",
"\n",
"$$\n",
"\\begin{align}\n",
"K+g(2)+g(0)-2g(1)&=K+\\overline{p}^2f(2)+2(\\overline{p}p-\\overline{p})f(1)+(p^2-2p+1)f(0)\\\\\n",
"&=K+\\overline{p}^2f(2)+2\\overline{p}(p-1)f(1)+(p-1)^2f(0)\\\\\n",
"&=K+\\overline{p}^2f(2)+\\overline{p}^2f(0)-2\\overline{p}^2f(1)\\geq 0.\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "35f2c369",
"metadata": {},
"source": [
"The above formula holds because of the K-convexity of $f(x)$. We then must also show that:"
]
},
{
"cell_type": "markdown",
"id": "4103a825",
"metadata": {},
"source": [
"$$\n",
"\\frac{K+g(3)-g(1)}{2}\\geq g(1)-g(0),\n",
"$$\n",
"\n",
"for any $a\\in\\mathbb{Z^+}$."
]
},
{
"cell_type": "markdown",
"id": "a96e36bb",
"metadata": {},
"source": [
"Since\n",
"\n",
"$$\n",
"\\begin{align}\n",
"g(3)&=\\Pr(\\xi^{1+a}=0)f(3)+\\Pr(\\xi^{1+a}=1)f(2)+\\Pr(\\xi^{1+a}=1)f(1)+\\Pr(\\xi^{1+a}=1+a)f(0)\\\\\n",
"&=\\overline{p}^{3}f(3)+3\\overline{p}^2pf(2)+3\\overline{p}p^2f(1)+p^{3}f(0),\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "de3d8ac7",
"metadata": {},
"source": [
"then\n",
"\n",
"$$\n",
"\\begin{align}\n",
"&K+g(3)+2g(0)-3g(1)\\\\\n",
"=&K+\\overline{p}^{3}f(3)+3\\overline{p}^2pf(2)+3\\overline{p}p^2f(1)+(p^{3}+2)f(0)-3\\overline{p}f(1)-3pf(0)\\\\\n",
"=&K+\\overline{p}^{3}f(3)+3\\overline{p}^2pf(2)+3\\overline{p}(p^2-1)f(1)+(p^{3}-3p+2)f(0)\\\\\n",
"=&K+\\overline{p}^{3}f(3)+3\\overline{p}^2pf(2)+3\\overline{p}(p^2-1)f(1)+(p+2)(p-1)^2f(0)\\\\\n",
"=&K+\\overline{p}^{3}f(3)+3\\overline{p}^2pf(2)-3\\overline{p}^2(p+1)f(1)+(p+2)\\overline{p}^2f(0)\\\\\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "69aa858c",
"metadata": {},
"source": [
"Let $d(y) = \\mathbb{E}[g(y+1-\\omega^y)]$."
]
},
{
"cell_type": "markdown",
"id": "c6d75946",
"metadata": {},
"source": [
"\n",
"$$\n",
"\\begin{align}\n",
"&K+d(2)+d(0)-2d(1)\\\\\n",
"=& K+p^2f(1)+\\overline{p}^2f(3)+2p\\overline{p}f(2)+f(1)-2\\overline{p}f(2)-2pf(1)\\\\\n",
"=&K+\\overline{p}^2f(3)+\\overline{p}^2f(1)-2\\overline{p}^2f(2)\\geq 0\n",
"\\end{align}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "2251cbf0",
"metadata": {},
"source": [
"According to the law of total expectation,\n",
"\n",
"$$\n",
"g(y) = \\overline{p}d(y-1)+pg(y-1)\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "2b7c9984",
"metadata": {},
"source": [
"So,\n",
"\n",
"$$\n",
"g(3)=\\overline{p}d(2)+pg(2)\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "7b9a2f12",
"metadata": {},
"source": [
"We must show\n",
"\n",
"$$\n",
"\\frac{K+g(3)-g(1)}{2}=\\frac{K+\\overline{p}d(2)+pg(2)-g(1)}{2}\\geq g(1)-g(0)\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "cffe1847",
"metadata": {},
"source": [
"Since $g(1)=\\overline{p}d(0)+pg(0)$ and $g(2)=\\overline{p}d(1)+pg(1)$,"
]
},
{
"cell_type": "markdown",
"id": "6d6c3989",
"metadata": {},
"source": [
"We must show\n",
"\n",
"$$\n",
"K+\\overline{p}d(2)-\\overline{p}g(2)+g(2)-g(1)\\geq 2\\overline{p}\\left[d(0)-g(0)\\right]\n",
"$$\n"
]
},
{
"cell_type": "markdown",
"id": "0f824940",
"metadata": {},
"source": [
"We must show\n",
"\n",
"$$\n",
"K+\\overline{p}\\left[d(2)-g(2)\\right]+\\overline{p}\\left[d(1)-g(1)\\right]\\geq 2\\overline{p}\\left[f(1)-f(0)\\right]\n",
"$$\n"
]
},
{
"cell_type": "markdown",
"id": "99ca4ccc",
"metadata": {},
"source": [
"$$\n",
"f(1)-f(0)\\leq K+f(2)-f(1)\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "a3c03d46",
"metadata": {},
"source": [
"$$\n",
"f(1)-f(0)\\leq \\frac{K+f(3)-f(1)}{2}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "0ca3c0a7",
"metadata": {},
"source": [
"Now assume $g(x)$ is K-convex for the dormain 0, 1,$\\dots$, $n-1$, we now prove it is also K-convex for $x=n$."
]
},
{
"cell_type": "markdown",
"id": "a2d0f2f7",
"metadata": {},
"source": [
""
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.9"
}
},
"nbformat": 4,
"nbformat_minor": 5
}