# MTH9842 HW3
## Group L
## Yang Li, Jimmy Jusuf, Zhirong Zhang, Tiangang Zhang
## December 5, 2018

### Question 1

#### (i) Prove log-concave

#### a. Normal
$$
f(x) = \frac{1}{\sqrt{2 \pi \sigma^2}} e^{-\frac{(x-\mu)^2}{2 \sigma^2}} \\
$$

The distribution density is always equal to or greater than zero.

$$
\log[f(x)] = {-\frac{(x-\mu)^2}{2 \sigma^2}} + \log(\frac{1}{\sqrt{2 \pi \sigma^2}}) \\
$$

Assume two different numbers y1 and y2, we have 
$$
\log[f(\alpha y1 + (1-\alpha) y2)] = {-\frac{(\alpha y1 + (1-\alpha) y2-\mu)^2}{2 \sigma^2}} + \log(\frac{1}{\sqrt{2 \pi \sigma^2}}) \\
\alpha \log[f(y1)] = {-\frac{\alpha(y1-\mu)^2}{2 \sigma^2}} + \alpha \log(\frac{1}{\sqrt{2 \pi \sigma^2}}) \\
(1-\alpha)\log[f(y2)] = {-\frac{(1-\alpha)(y2-\mu)^2}{2 \sigma^2}} + (1-\alpha) \log(\frac{1}{\sqrt{2 \pi \sigma^2}}) \\
$$

Then based on the definition of the concave function, we calculate the below inequality, 
$$
2\sigma^2 \left[\alpha \log[f(y1)]+(1-\alpha)\log[f(y2)]-\log[f(\alpha y1 + (1-\alpha) y2)]\right] \\
= -\alpha y1^2 - (1-\alpha)y2^2 + [(\alpha y1 + (1-\alpha) y2]^2 \\
= -(1-\alpha)\alpha (y1^2+y2^2-y1y2) \\
= -(1-\alpha)\alpha [(y1-\frac{y2}{2})^2 + \frac34 {y2}^2] \\
<= 0 \\
$$

Therefore the normal density is log-concave from the above result. 

#### b. multinormal
$$
f(x) = \frac{1}{(2\pi)^{p/2}|\Sigma|^{1/2}} e^{-\frac12 (x-\mu)^T \Sigma^{-1} (x-\mu)}
$$

The distribution density is always equal to or greater than zero.

Following the same method for normal distribution. we have, 
$$
\log[f(x)] = {-\frac12 (x-\mu)^T \Sigma^{-1} (x-\mu)} + \log(\frac{1}{(2\pi)^{p/2}|\Sigma|^{1/2}}) \\
$$

Also assume two different multi-dimensional vectors y1 and y2, where $\alpha$ is a scalar, we have 
$$
\log[f(\alpha y1 + (1-\alpha) y2)] = {-\frac12 (\alpha y1 + (1-\alpha) y2-\mu)^T \Sigma^{-1} (\alpha y1 + (1-\alpha) y2-\mu)} + \log(\frac{1}{(2\pi)^{p/2}|\Sigma|^{1/2}}) \\
\alpha \log[f(y1)] = {-\frac{\alpha}{2} (y1-\mu)^T \Sigma^{-1} (y1-\mu)} + \alpha \log(\frac{1}{(2\pi)^{p/2}|\Sigma|^{1/2}}) \\
(1-\alpha) \log[f(y2)] = {-\frac{(1-\alpha)}{2} (y2-\mu)^T \Sigma^{-1} (y2-\mu)} + (1-\alpha) \log(\frac{1}{(2\pi)^{p/2}|\Sigma|^{1/2}}) \\
$$

Then based on the definition of the concave function, we calculate the below inequality, 
$$
\log[f(\alpha y1 + (1-\alpha) y2)] - \alpha \log[f(y1)]- (1-\alpha) \log[f(y2)] \\
= -\frac12(\alpha y1^T)\Sigma^{-1}(\alpha y1) + \frac12(\alpha y1^T)\Sigma^{-1}(y1) -\frac12((1-\alpha) y2^T)\Sigma^{-1}[(1-\alpha) y2] + \frac12[(1-\alpha) y2^T]\Sigma^{-1}(y2) - (\alpha y1^T)\Sigma^{-1}[(1-\alpha) y2] \\
= \frac{\alpha-\alpha^2}{2}(y1^T)\Sigma^{-1}(y1) + \frac{(1-\alpha) - (1-\alpha)^2}{2}(y2^T)\Sigma^{-1}(y2) - \alpha(1-\alpha)(y1^T)\Sigma^{-1}(y2) \\
= \frac{\alpha(1-\alpha)}{2}(y2^T)\Sigma^{-1}(y2) + \frac{\alpha(1-\alpha)}{2}(y1^T)\Sigma^{-1}(y1) - \alpha(1-\alpha)(y1^T)\Sigma^{-1}(y2) \\
= \frac{\alpha(1-\alpha)}{2}[(y2^T)\Sigma^{-1}(y2) - 2(y1^T)\Sigma^{-1}(y2) + (y1^T)\Sigma^{-1}(y1)] \\ >= 0
$$

Therefore the multinormal density is also log-concave from the above result.

#### c. exponential

When x>= 0 
$$
f(x) = \lambda e^{-\lambda x} \\
$$
The distribution density is always equal to or greater than zero.

$$
\log [f(x)] = -\lambda x + \log(\lambda) \\
$$

Assume two different numbers y1 and y2, we have 
$$
\log[f(\alpha y1 + (1-\alpha) y2)] = -\lambda (\alpha y1 + (1-\alpha) y2) + \log(\lambda) \\
\alpha \log[f(y1)] = -\alpha \lambda (y1) + \alpha \log(\lambda) \\
(1-\alpha) \log[f(y2)] = -(1-\alpha) \lambda (y2) + (1-\alpha) \log(\lambda) \\
$$

Then based on the definition of concave function, we calculate as below

$$
\log[f(\alpha y1 + (1-\alpha) y2)] - \alpha \log[f(y1)] - (1-\alpha)\log[f(y2)] \\
= -\lambda (\alpha y1 + (1-\alpha) y2) + \alpha \lambda (y1) + (1-\alpha) \lambda (y2) \\
= 0 \\
>= 0 \\
$$

Therefore the exponential density is log-concave from the above result. 

#### d. logistic
$$
f(x) = \frac{e^{-(x-\mu)/s}}{s(1+e^{-(x-\mu)/s})^2} \\
$$
The distribution density is always equal to or greater than zero.

$$
\log [f(x)] = -(x-\mu)/s - \log(s) - 2\log(1+e^{-(x-\mu)/s}) \\
$$

Take the second derivative to this log function, we have
$$
\log [f(x)]'' = \frac{2}{s^2} \frac{e^{-(x-\mu)/s}}{(1+e^{-(x-\mu)/s})^2} - \frac{2}{s^2} \frac{e^{-(x-\mu)/s}}{(1+e^{-(x-\mu)/s})} <= 0
$$

Therefore the logistic density is log-concave from the above result. 

#### (2) Kullback-Leibler distance

By definition, we have
$$
KL = \sum{p_i \log{\frac{p_i}{q_i(\theta)}}} \\
$$
and $q_i(\theta)$ is a log-concave function.

For each component i, we have
$$
KL_i = p_i \log{p_i} - p_i \log{q_i(\theta)} \\ 
$$

Assume two different parameters $\theta_1$ and $\theta_2$, we have
$$
KL_i|_{\alpha \theta_1 + (1-\alpha) \theta2} = p_i \log{p_i} - p_i \log{q_i[\alpha \theta_1 + (1-\alpha) \theta2]} \\ 
\alpha KL_i|_{\theta_1} = \alpha p_i \log{p_i} - \alpha p_i \log{q_i(\theta_1)} \\ 
(1-\alpha) KL_i|_{\theta2} = (1-\alpha) p_i \log{p_i} - (1-\alpha) p_i \log{q_i(\theta2)} \\ 
$$

Then
$$
\alpha KL_i|_{\theta_1} + (1-\alpha) KL_i|_{\theta2} - KL_i|_{\alpha \theta_1 + (1-\alpha) \theta2} \\
= - \alpha p_i \log{q_i(\theta_1)} - (1-\alpha) p_i \log{q_i(\theta_2)} + p_i \log{q_i[\alpha \theta_1 + (1-\alpha) \theta_2]} \\
= p_i [ \log{q_i(\alpha \theta_1 + (1-\alpha) \theta_2)} - \alpha \log{q_i(\theta_1)} - (1-\alpha) \log{q_i(\theta_2)}] \\
$$
Given $q_i(\theta)$ is a log-concave function, we have 
$$
\log{q_i(\alpha \theta_1 + (1-\alpha) \theta_2)} - \alpha \log{q_i(\theta_1)} - (1-\alpha) \log{q_i(\theta_2)} >= 0
$$
Therefore, 
$$
\alpha KL_i|_{\theta_1} + (1-\alpha) KL_i|_{\theta2} - KL_i|_{\alpha \theta_1 + (1-\alpha) \theta2} >= 0
$$
which means each KL term/component is convex. Consequently, the sum of the convex fucntions is also convex. 


### Question 2 

Let <br>
(1)
\begin{equation}
A = \begin{pmatrix}
  13 & 12 & -2 \\
  12 & 17 & 6 \\
  -2 & 6 & 12 \\
  \end{pmatrix} = A^T,\quad 
a = \begin{pmatrix} -22 \\ -14.5 \\ 13 \\ \end{pmatrix},\quad
b = 1. 
\end{equation}

<br> 
(2) 
\begin{equation}
\text{The objective function to be minimized }f:R^3\rightarrow R,
f(x)=\frac12 x^T A x + a^T x + b,
\end{equation}

<br>
(3)
\begin{equation}
\text{subject to} {-1}\leq x_i\leq 1, i=1,2,3
\text{ or } \begin{pmatrix} {-1\\-1\\-1} \end{pmatrix}
  \leq x\leq \begin{pmatrix} {1\\1\\1} \end{pmatrix},
  x\in R^3.
\end{equation}

Rewrite inequality constraints as 
$h_1(x)=-x+\begin{pmatrix} -1\\-1\\-1 \end{pmatrix}\leq 0$
and
$h_2(x)=x+\begin{pmatrix} -1\\-1\\-1 \end{pmatrix}\leq 0$, <br>
Or
$$
x1 - 1 <= 0 \\
-x1 - 1 <= 0 \\
x2 - 1 <= 0 \\
-x2 - 1 <= 0 \\
x3 - 1 <= 0 \\
-x3 - 1 <= 0 \\
$$

Note that
$\nabla_x f(x)=A x + a=
\begin{pmatrix}{21\\14.5\\-11}\end{pmatrix} + \begin{pmatrix}{-22\\14.5\\13}\end{pmatrix} = \begin{pmatrix}{-1\\0\\2}\end{pmatrix}, \\$
$\nabla_x h_1(x)=\begin{pmatrix}{-1\\-1\\-1}\end{pmatrix}$, 
$\nabla_x h_2(x)=\begin{pmatrix}{1\\1\\1}\end{pmatrix}$.

Let $
\Lambda_1=\begin{pmatrix}\lambda_1\\ \lambda_2\\ \lambda_3\end{pmatrix},
\Lambda_2=\begin{pmatrix}\lambda_4\\ \lambda_5\\ \lambda_6\end{pmatrix} $ be the Lagrange multipliers
for constraints $h_1(x)$ and $h_2(x)$ respectively.

Define Lagrangian <br>
(4)
\begin{gather}
L(x, \Lambda)=f(x)+ \Lambda_1^T h_1(x) + \Lambda_2^T h_2(x)
\end{gather}

For $x^*$ to be a local minimum, we want to show the following KKT Necessary Conditions are met. <br>
(5)
$$
\nabla_x L(x^*, \Lambda^*) = 
\nabla_x f(x) + (\Lambda_1^*)^T \nabla_x h_1(x) + (\Lambda_2^*)^T \nabla_x h_2(x) \\
= (A x + a) + (\Lambda_1^*)^T \begin{pmatrix}{-1\\-1\\-1}\end{pmatrix} + (\Lambda_2^*)^T\begin{pmatrix}{1\\1\\1}\end{pmatrix} = 0
$$
(6)
$$
(\Lambda_1^*)^T h_1(x^*) = 0 \\
$$
(7)
$$
(\Lambda_2^*)^T h_2(x^*) = 0 \\
$$
(8)
$$
\Lambda_1^* \geq 0 \\
$$
(9)
$$
\Lambda_2^* \geq 0 \\
$$
$$
d^T \nabla_{xx}^2 L(x^*, \lambda^*) d > 0 \\
$$

Plugging in $x^* = \begin{pmatrix}{1 \\ 0.5 \\ -1}\end{pmatrix}$, we checked the KKT necessary conditions.<br>
(5a)
$$
\nabla_{x} L(x^*, \Lambda^*) = 
\begin{pmatrix}{-1\\0\\2}\end{pmatrix}
  +\begin{pmatrix}{-\lambda_1\\-\lambda_2\\-\lambda_3}\end{pmatrix}
  +\begin{pmatrix}{\lambda_4\\ \lambda_5\\ \lambda_6}\end{pmatrix} =0 \\
$$
(6a)
$$
\begin{pmatrix}{\lambda_1, \lambda_2, \lambda_3}\end{pmatrix} \begin{pmatrix}{-2\\-1.5\\0}\end{pmatrix} = 0
\implies \lambda_1=\lambda_2=0 \\
$$
(7a)
$$
\begin{pmatrix}{\lambda_4, \lambda_5, \lambda_6}\end{pmatrix} \begin{pmatrix}{0\\-0.5\\-2}\end{pmatrix} = 0
\implies \lambda_5=\lambda_6=0 \\
\Lambda_1^* h_1(x^*) = 0 \\
\Lambda_2^* h_2(x^*) = 0 \\
\Lambda_1^* \geq 0 \\
\Lambda_2^* \geq 0 \\
$$
The complementary slackness condition forces
$\lambda_1,\lambda_2,\lambda_5,\lambda_6$ to be zero as
$h_1(x_1), h_1(x_2), h_2(x_2), h_2(x_3) \leq 0$ are not active under the optimum solution. 

Back-substitution into the first order equation (5a) yields $\lambda_4=1$ and 
$\lambda_3=-2$. All the $\lambda$'s satisfy conditions (8)
and (9)

As all the leading principal minor of $A$ is positive, the second order condition is met. 


```python

```

00b96e99a18ef00491b4c8589d78e96fb4b50c8c
ipynb
Jupyter Notebook
HW3/9842HW3_Group L.ipynb
jjusuf/MTH-9842
476a089b7d49089c6edad2a0f2c9257c283aa6d3
MIT
HW3/9842HW3_Group L.ipynb
jjusuf/MTH-9842
476a089b7d49089c6edad2a0f2c9257c283aa6d3
MIT
HW3/9842HW3_Group L.ipynb
jjusuf/MTH-9842
476a089b7d49089c6edad2a0f2c9257c283aa6d3
MIT
Qwen/Qwen-72B
1. YES
2. YES