# How to find a minimizer with only positive entries?

Here is my objective function

$$\begin{array}{c} \text{min} \hspace{4mm} \mathbf{x}^T A\mathbf{x} \\ s.t \hspace{4mm}x_1 = 1 \\ \hspace{35mm}x_i > 0 \hspace{10mm} 2\leq i \leq n, \end{array}$$

where $\mathbf{x} \in \mathbb{R}^{n}$ and $\mathbf{A} \in \mathbb{R}^{n\times n}$ and is a positive semidefinite matrix.

In this case, the feasible set belongs to non-negative orthand of $\mathbb{R}^n$

My question are:

1. How can I write these constraints in a better/compact way?
2. Is it possible to find a closed form solution to this problem? If yes, then how?
• If you want the non-negative orthant, then it should be $x_i \geq 0$. – Rodrigo de Azevedo Nov 15 '16 at 20:20
• If I change it to $x_i>0 \forall i$, will it disturb the convexity of the feasible set? – NAASI Nov 15 '16 at 21:08
• It is not a matter of convexity, but of whether there is an infimum instead of a minimum. – Rodrigo de Azevedo Nov 16 '16 at 0:24

We have the quadratic program (QP) in $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{minimize} & \mathrm x^{\top} \mathrm A \, \mathrm x\\ \text{subject to} & x_1 = 1\\ & x_2, \dots, x_n \geq 0\end{array}$$

which can be written as the following QP in $\mathrm y \in \mathbb R^{n-1}$

$$\boxed{\begin{array}{ll} \text{minimize} & \mathrm y^{\top} \mathrm Q \, \mathrm y - 2 \, \mathrm r^{\top} \mathrm y + s\\ \text{subject to} & \mathrm y \geq 0_{n-1}\end{array}}$$

where

$$\mathrm x = \begin{bmatrix} 1\\ \mathrm y\end{bmatrix}$$

and

$$\mathrm A = \begin{bmatrix} s & -\mathrm r^{\top}\\ -\mathrm r & \mathrm Q\end{bmatrix}$$

• Thank you for posting your answer. Just one comment. Since objective function is quadratic, it seems that minimum would be achieved by making $x_2,\cdots,x_n$ all $=0$. In this case we might not even need to do anything. What do you think? – NAASI Nov 16 '16 at 19:25
• Taking the gradient of the objective function and finding where it vanishes, we obtain the linear system $$\mathrm Q \mathrm y = \mathrm r$$ If $\mathrm Q$ is positive definite, then the unique solution is $\bar{\mathrm y} := \mathrm Q^{-1} \mathrm r$. If this solution is in the nonnegative orthant, we are done. – Rodrigo de Azevedo Nov 16 '16 at 19:48
• If $\mathrm A \succ \mathrm O$ is diagonal, then the minimizer should be $\bar{\mathrm x} := (1,0,\dots,0)$. – Rodrigo de Azevedo Nov 16 '16 at 19:54
• In fact, there is no need for $\mathrm A$ to be diagonal. Having $\mathrm r = 0_{n-1}$ is enough. $\mathrm Q$ does not have to be diagonal. – Rodrigo de Azevedo Nov 16 '16 at 20:15
• @ Rodrigo. You commented that the unique solution is $\bar{y}:=\mathrm{Q^{-1}r}$. and if its in positive orthant, then we are done. What if that is not the case and there are negative entries in $\bar{\mathrm{y}}$ – NAASI Dec 12 '16 at 20:05