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
那么有如下几种情况：
\
- ||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)
\ - ||M||_2 \leq 1\leq ||N||_2
\
此时f(\alpha M + \beta N) \leq +\infty = \alpha f(M) + \beta f(N)
\ - 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
$$