# How can I solve $\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$ in a closed form depending on projection?

I'm trying to solve the minimization problem

$$\inf_{x \in X} x^T(Ax + b) + \sum_{i=1}^n x_i \log(x_i)$$

where $b \in \mathbb{R}^n$, $X \subset \mathbb{R}^n$ is a convex set. And $A$ is a symmetric and positive definite matrix. The optimality conditions give me something like

$$-b \in 2Ax + \vec{1} + L(x) + N_X(x)$$

where $L(x)$ represents the vector in $\mathbb{R}^n$ obtained by taking the elementwise logarithm of $x$; i.e., $[L(x)]_i=\log x_i$.

The problem is how do I take that cone out of the inclusion. If there wasn't that log term it would become a projection on the set $X$. Is there a trick to make this as a projection on $X$ of other vector or something?

I'd appreciate any help or any paper/book reference where there's some information about this kind of problem

• There is no closed form. You have to solve this numerically, even if $X\equiv\mathbb{R}^n$. – Michael Grant Mar 23 '15 at 19:38
• I see. In this case do you know where can I find info on numerically solving this? – karlabos Mar 23 '15 at 22:46
• I would recommend looking into CVX (incidentally, it is partially authored by the previous commenter): cvxr.com/cvx. – bassen Mar 24 '15 at 18:49

Starting from your inclusion $$-b \in 2Ax + \vec{1} + L(x) + N_X(x),$$ we can add $$x$$ on both sides and re-arrange to get:
$$x-2Ax-\vec{1}-L(x)-b \in (I+N_X)(x),$$ where $$I$$ denotes the identity operator $$x\mapsto x$$. We can now invert to get $$x = P_X\big(x-2Ax-\vec{1}-L(x)-b\big).$$ This reformulation takes the normal cone operator out of your problem and converts it to a fixed point problem that you might try to approach with fixed-point theoretic algorithms.