Show that the following optimization problem is convex

Question

I have the following optimization problem

\begin{equation} \label{logdual} \begin{array}{ll@{}ll} \text{minimize}_{\pmb\alpha \in \mathbb{R}^n} & \theta(\pmb\alpha) &\\ \text{subject to} & \pmb\alpha > 0 &\\ \end{array} \end{equation}

where $\theta(\pmb{\alpha}) = \frac{1}{2\lambda} \sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x_i}^T\mathbf{x_j} + \sum_i \alpha_i \log{\alpha_i} + (1-\alpha_i)\log(1 - \alpha_i)$

$\mathbf{x_1}, \mathbf{x_2}, \dots, \mathbf{x_n}$ are $n$ data points where $\mathbf{x_i} \in \mathbb{R}^d$ and $y_1, y_2, \dots, y_n$ are binary labels for each data point such that $y_i \in \{1, -1\}$

This is also happens to be the Lagrangian dual of the $\ell_2$-Logistic regression problem.

My attempt to show that this is convex was to show that the Hessian $\mathbf{H}$ of $\theta(\pmb\alpha)$ is positive definite but I am unable to do so. I tried following the approach given in Section 9 of this paper. Here they show that the following

$$ \frac{\partial^2\theta(\pmb\alpha)}{\partial \alpha_i^2} = \frac{1}{\lambda}y_i^2\mathbf{x_i}^T\mathbf{x_i} + \frac{1}{\alpha_i(1 - \alpha_i)} $$ $$ \frac{\partial^2\theta(\pmb\alpha)}{\partial \alpha_i \partial \alpha_j} = \frac{1}{\lambda}y_iy_j\mathbf{x_j}^T\mathbf{x_i} $$

and then proceed to state that the Hessian $$\mathbf{H} = \frac{1}{\lambda}\text{diag}(\mathbf{y})\mathbf{X}^T\mathbf{X} \text{diag}(\mathbf{y}) + \text{diag}\left(\frac{1}{\alpha_i(1-\alpha_i)}\right)$$

and if so then because $\mathbf{x}\mathbf{x}^T$ is positive definite then so is $\mathbf{H}$ but I am unable to follow how the author came up with the term $\mathbf{X}^T\mathbf{X}$ in $\mathbf{H}$

I have been at this for hours now and any explanation would be really helpful!

Answer 1

Note that $\log (1-\alpha_i)$ imposes the inequality constraint $\alpha_i \leq 1$. Thus, $0 \leq \alpha_i \leq 1$.

Note also that, if $p \in [0,1]$, then

$$p \log (p) + (1-p) \log (1-p) \propto - \mathcal{H} (p)$$

where $\mathcal{H} (p)$ is the famous binary entropy function, which is concave. Hence,

$$\alpha_i \log (\alpha_i) + (1-\alpha_i) \log (1-\alpha_i)$$

is convex and, thus, the sum

$$\sum_{i=1}^n \left( \alpha_i \log (\alpha_i) + (1-\alpha_i) \log (1-\alpha_i) \right) = - \sum_{i=1}^n \mathcal{H} (\alpha_i)$$

is also convex. Let

$$c_{ij} := y_i y_j \mathrm x_i^{\top} \mathrm x_j$$

and let $\mathrm C$ be the $n \times n$ matrix whose $(i,j)$-th entry is $c_{ij}$. Let $\mathrm X$ be the $d \times n$ matrix whose $i$-th column is $\mathrm x_i$, and let $\mathrm y := (y_1, y_2, \dots, y_n)$. Hence,

$$\mathrm C = (\mathrm X \, \mbox{diag} (\mathrm y))^{\top} (\mathrm X \, \mbox{diag} (\mathrm y)) = \mbox{diag} (\mathrm y) \, \mathrm X^{\top} \mathrm X \, \mbox{diag} (\mathrm y) \succeq \mathrm O$$

and, thus,

$$\sum_{i=1}^n \sum_{j=1}^n c_{ij} \alpha_i \alpha_j = \langle \mathrm C, \alpha \alpha^{\top} \rangle = \alpha^{\top} \mathrm C \, \alpha$$

is also convex. We conclude that if $\lambda > 0$, then the cost function $\theta$ is convex.