# Show that the following optimization problem is convex

I have the following optimization problem

$$\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}$$

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!

• Hint: Avoid computing the Hessian, if you can, and use the calculus of convex functions instead! Define $\mathbf z_i = y_i \mathbf x_i$ and the corresponding matrix $\mathbf Z = (\mathbf z_i)$. Can you rewrite the first term as a quadratic function of the vector $\alpha$ and utilizing $\mathbf Z$ appropriately? Is the corresponding quadratic convex? If so, what, then what do you know about the sum of convex functions? Dec 15, 2016 at 20:05
• One also needs the constraint $\alpha_i \leq 1$, otherwise $\log (1 - \alpha_i)$ goes imaginary. Dec 15, 2016 at 20:09
• @cardinal I rewrote the first term as $\frac{1}{2\lambda}(\mathbf{\alpha} \mathbf{Z})^T(\mathbf{\alpha Z})$ This gives me $\frac{1}{2\lambda}\mathbf{Z}^T\mathbf{\alpha}^T\mathbf{\alpha} \mathbf{Z}$ but I am unable to draw any further conclusions from here. Dec 15, 2016 at 20:16
• @cardinal I see that $\pmb{\alpha}^T \pmb{\alpha}$ is convex but how does this become a sum of convex functions? Dec 15, 2016 at 20:23
• Banach: It's always good to double-check the basic properties of an expression you derive. If you are treating $\alpha$ as a column vector, then your resulting expression is a matrix, not a scalar (whoops!), and if you were treating it as a row vector, then the expression makes no sense at all since the dimensions do not conform (unless $n = d$, and even then the result is incorrect). Dec 15, 2016 at 20:23

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.