1
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ If you want the non-negative orthant, then it should be $x_i \geq 0$. $\endgroup$ – Rodrigo de Azevedo Nov 15 '16 at 20:20
  • $\begingroup$ If I change it to $x_i>0 \forall i$, will it disturb the convexity of the feasible set? $\endgroup$ – NAASI Nov 15 '16 at 21:08
  • $\begingroup$ It is not a matter of convexity, but of whether there is an infimum instead of a minimum. $\endgroup$ – Rodrigo de Azevedo Nov 16 '16 at 0:24
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – NAASI Nov 16 '16 at 19:25
  • $\begingroup$ 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. $\endgroup$ – Rodrigo de Azevedo Nov 16 '16 at 19:48
  • 1
    $\begingroup$ If $\mathrm A \succ \mathrm O$ is diagonal, then the minimizer should be $\bar{\mathrm x} := (1,0,\dots,0)$. $\endgroup$ – Rodrigo de Azevedo Nov 16 '16 at 19:54
  • $\begingroup$ 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. $\endgroup$ – Rodrigo de Azevedo Nov 16 '16 at 20:15
  • $\begingroup$ @ 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}}$ $\endgroup$ – NAASI Dec 12 '16 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.