0
$\begingroup$

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

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

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.

$\endgroup$

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.