How to find a minimizer with only positive entries?

148 Views Asked by At

Here is my objective function

\begin{equation} \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} \end{equation}

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?
1

There are 1 best solutions below

6
On BEST ANSWER

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