Minimization problem convex set

Question

I'm trying to minimize the function: $$f(w)=w^T\mu+k\sqrt{w^T\Sigma w}$$ where $w$ is a vector in $W=\{x \in \mathbb{R}^n|x_1+...+x_n=1 , x_i \geq 0 \forall i\}$.

The vector $\mu \in \mathbb{R}^n$, the constant $k\in \mathbb{R}$ and the symmetric positive-semidefinite matrix $\Sigma\in \mathbb{R}^{n*n}$ are given.

Does this problem have an unique solution? I am able to see that $W$ is convex but I don't think $f(w)$ is convex. How can I numerically solve the problem? I know some theory of linear and quadratic programming but I' not able to use them in this case.

Answer 1

To put your problem in a form that CVX can accept, we can factor $\Sigma$ as $\Sigma = L^T L$. Then \begin{align} \sqrt{w^T \Sigma w} &= \sqrt{w^T L^T L w} \\ &= \sqrt{y^T y} \\ &= \|y\|_2 \end{align} where $y = Lw$. The optimization problem can be reformulated as \begin{align} \text{minimize}_{w,y} &\quad w^T \mu + k \|y\|_2 \\ \text{subject to} & \quad y = L w\\ & \quad w \in \Delta \end{align} where $\Delta$ is the probability simplex.

Here's some Matlab code that solves this problem using CVX:

% randomly generate a problem
k = 1;
N = 100;
mu = randn(N,1);

m = 50;
A = randn(m,N);
Sigma = A'*A;

% solve the problem
L = sqrtm(Sigma);
L = real(L);
check = Sigma - L'*L;
max(abs(check(:)))

cvx_begin

    variables w(N) y(N)
    minimize( w'*mu + k*norm(y))
    subject to          
        y == L*w;
        w == simplex(N)

cvx_end