Problem 1

Let $C\sube \mathbb{R}^n$ be a non-empty closed convex set and $\mathbb{I}_C$ denote its associated indicator function; i.e.,

$$ \mathbb{I}_C (x) = \left\{ \begin{aligned} &0& \ \ \ \ \ \ \ if \ x\in C,\\ &+\infty& \ \ \ \ \ \ otherwise. \end{aligned} \right. $$

(a) Argue directly using the definition of the subdifferential that for any $x\in C$,

$$ \partial \mathbb{I}_C(x) = \{s\in \mathbb{R}^n: s^T (y-x) \leq 0\ \text{for all} \ y\in C\}. $$

(b)Using the result in (a), show that for any $x\in \mathbb{R}_{+}^n$，

$$ \partial \mathbb{I}_{\mathbb{R}_{+}^n} = \{s\in \mathbb{R}^n:\ s\leq 0,\ x^Ts = 0\} $$

Solution:

(a)

$$ \\ \text{考虑}s\in \mathbb{R}^n，对于任意的x_0\in C，x\in C \\ \mathbb{I}_C(x) \geq f(x_0)+s^T(x-x_0) \\ s^T(x-x_0)+0\leq 0 \\ 故\partial \mathbb{I}_C(x) = \{s\in \mathbb{R}^n: s^T (y-x) \leq 0\ \text{for all} \ y\in C\}. $$

(b)

$$ 根据(a)中的结论，我们有： \\ \partial\mathbb{I}_{\mathbb{R}_{+}^n} = \{s\in \mathbb{R}^n:\ s^T(y-x)\leq 0 \ \text{for all} \ y\in \mathbb{R}_+^n\} \\ 于是s^Ty\leq s^T x \ \text{for all }y\in\mathbb{R}_+^n \\ 于是s^Tx = 0, \ s^T y \leq 0 \\ 由于y\in\mathbb{R}_+^n, s\leq0 \\ 故 \partial \mathbb{I}_{\mathbb{R}_{+}^n} = \{s\in \mathbb{R}^n:\ s\leq 0,\ x^Ts = 0\} $$

Problem 2

Let $f: \mathbb{R}^2 \to \mathbb{R} \cup {+\infty}$ be the function given by

$$ f(x_1, x_2) = \begin{cases} 0, & \text{当 } \| (x_1, x_2) \|_2 < 1, \\ \in [0, +\infty), & \text{当 } \| (x_1, x_2) \|_2 = 1, \\ +\infty, & \text{当 } \| (x_1, x_2) \|_2 > 1. \end{cases} $$

Show that $f$ is convex.

Solution:

$$ 考虑两个点M,N\in\mathbb{R}^2，其中||M||_2\leq ||N||_2 \\ 考虑任意的\alpha,\beta \geq 0 那么有如下几种情况： \\ 1. ||M||_2\leq ||N||_2 \leq 1 \\ 此时||\alpha M + \beta N||_2\leq 1 \\ \alpha f(M)+ \beta f(N) \geq f(\alpha M + \beta N) \\ 2. ||M||_2 \leq 1\leq ||N||_2 \\ 此时f(\alpha M + \beta N) \leq +\infty = \alpha f(M) + \beta f(N) \\ 3. 1\leq ||M||_2 \leq ||N||_2 \\ 此时f(\alpha M + \beta N) \leq (\alpha + \beta )\infty\leq\alpha f(M) + \beta f(N) $$

Problem 3

Let $A \in \mathbb{R}^{m \times n} $ be given. Show that exactly one system in each of the following pairs has a solution.

(a)

$\text{(I)} \quad A x < 0, \quad x \geq 0 $

$ \text{(II)} \quad A^T y \geq 0, \quad y \geq 0, \quad y \neq 0 $

(b)

$ \text{(I)} \quad A x \geq 0, \quad A x \neq 0 $

$ \text{(II)} \quad A^T y = 0, \quad y > 0 $

Solution:

(a)

$$ 假设(I)和(II)都有解\bar{x}和\bar{y} \\ 那么我们可以知道A^T\bar{y}\geq 0 \\ 于是\bar{y}^TA \geq 0 \\ 所以\bar{y}^TA\bar{x}\geq0 \\ 又A\bar{x}< 0 \\ 所以\bar{y}^TA\bar{x}<0 \\矛盾，故(I)和(II)不可能同时成立 \\ 考虑Ax < 0,\ x\geq0 \\ (I')Ax + s = c, 其中x,\ s\geq 0,\ c < 0 \\ 若(I')不成立，根据Farkas引理有： \\ A^Tw\leq 0, \ bw>0,\ 其中b\in \mathbb{R}^n,\ w \leq 0 \\ 那么取b = -e^T,\ y = -w \\ 有A^Ty \geq0, y>0 成立 $$

(b)

$$ 考虑(I'): (-Ax) \leq 0,\ e^TAx >0\\ 假设(I')没有解，根据Farkas引理：\\ (II'):\ -A^Tw = e^TA ,\ w\geq 0有解\\ 于是 (w+e^T)A=0\\ 令y= w+e^T即证明完毕 $$

Problem 4

令 $A \in \mathbb{R}^{m \times n} $且 $b \in \mathbb{R}^m_+$ 已知，考虑以下线性系统：

$$ Ax = b, \quad x \geq 0 \tag{1} $$

以及相关的线性规划问题（LP）：

$$ \text{minimize } e^T y\\ \text{subject to } Ax + Iy = b, \quad x \geq 0, \, y \geq 0 \tag{2} $$

其中，$e = (1, \dots, 1) \in \mathbb{R}^m$ 是一个全为 1 的向量，$I$ 是$m \times m$ 的单位矩阵。这个线性规划问题 (2) 通常称为 Phase One Problem。

(a) 写出问题 (2) 的对偶问题。

(b) 证明问题 (2) 总有最优解。

(c) 证明系统 (1) 有解，当且仅当问题 (2) 的最优值为零。

Solution:

(a)

$$ \text{maxmize } e^Ty\\ \text{subject to }Ax + Iy > b,\ x \geq 0, \ y\geq 0 $$