2
$\begingroup$

I have a convex optimization problem as follows:

\begin{align*} maximize_{x\in R^n} &\sum_{i=1}^n a_i \log(x_i)\\ st\quad & \sum_{i=1}^n p_{ij} (x_i-1) = 0 \quad \forall j\\ & x_i > 0 \end{align*} where, $a_i \geq 0$ and $P$ is an $n\times m$ probability matrix with rows sum up to 1.

( I am assuming that $n$ is (much) larger than $m$. Let $P = (p_{ij}) \in \mathbb R^{n \times m}$. Then, the constraint is $P^T (x-1) = 0 $, that is, $x$ is feasible iff $x - 1 \in \text{ker}(P^T)$. We have $\text{ker}(P^T) = \text{Im}(P)^\perp$. The image of $P$ is at most an $m$ dimensional subspace of $\mathbb{R}^n$, hence its orthogonal complement is $(n-m)$-dimensional which is pretty big. There are many feasible solutions besides $x = 1$.)

I tried to optimize the Lagrangian $\sum_{i} \big[a_{i} \log x_{i} - \sum_j \lambda_j p_{ij}(x_{i}-1)\big]$ (keeping the constraint $x_i > 0$), via a dual ascent algorithm:

\begin{align*} x_{i}(\lambda) = \max\Big\{0,\frac{a_i}{\sum_j \lambda_j p_{ij}} \Big\}, \quad \lambda_j^+ = \lambda_j +\alpha \sum_i p_{ij}\big[x_{i}(\lambda)-1\big], \; \forall j \end{align*}

But this doesn't seem right as the dual variable also should be non-negative and the dual problem would be constrained.

How to solve this problem?

$\endgroup$
  • 1
    $\begingroup$ $x_i=1$ is the only feasible point unless you assume the rows of $P$ are linearly dependent. $\endgroup$ – martin cripps Nov 30 '16 at 10:06
  • $\begingroup$ @kipper, please see my update to the question. I am assuming $n > m$, in which case your comment doesn't apply. $\endgroup$ – ie86 Nov 30 '16 at 16:36
  • $\begingroup$ If you want to compute solutions by computer just put the problem into CVX. $\endgroup$ – Dirk Nov 30 '16 at 18:12
  • $\begingroup$ @Dirk I need to compute this many times and it takes forever with CVX. (I've already done that) $\endgroup$ – ie86 Nov 30 '16 at 18:19
  • $\begingroup$ if you want to solve faster than CVX, but without being clever enough to figure out the prox "jazz", use YALMIP with the ECOS solver (which has native exponential cone support) using YALMIP's command "optimizer", rather than "optimize", which saves the modeling time for every instance of the input data (parameters) a and p. You could do this with ECOS under CVX 3.0 beta, which should be faster than using CVX"s successive approximation method, but would incur the modeling time on every new problem instance, unlike YALMIP's optimizer. $\endgroup$ – Mark L. Stone Jun 5 '17 at 2:05
3
$\begingroup$

Your problem is of the form $$ \min F(x)\quad \text{s.t.}\quad Ax=b $$ or $$ \min F(x) + G(Ax) $$ with $G$ being the indicator function of the single point $b$. Hence, you can try basically all methods from the slides "Douglas-Rachford method and ADMM" by Lieven Vandenberghe, i.e. Douglas-Rachford, Spingarn or ADMM. You could also try the primal-dual hybrid gradient method also know as Chambolle-Pock method since this would avoid all projections, see here or here.

Note that the $F$ deals with the constraint $x>0$ implicitly by defining is as extended convex function via $$ F(x) = \begin{cases} -\sum a_i\log(x_i) & \text{all $x_i>0$}\\ \infty & \text{one $x_i\leq 0$}\end{cases} $$ leading to the proximal map $$ \operatorname{prox}_{tF}(x) = \tfrac{x}2 + \sqrt{\tfrac{x^2}4+ta} $$ where all operations are applied componentwise.

$\endgroup$
  • $\begingroup$ This is great! I was trying to do similar things, but failed to massage it into the right form. The trick seems to be on Lieven's slide 13-11. By lifting the problem to a higher dimension. The projectionless approach is really interesting too. Thanks for the nice answer. $\endgroup$ – ie86 Nov 30 '16 at 21:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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