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?

  • 1
    $\begingroup$ $x_i=1$ is the only feasible point unless you assume the rows of $P$ are linearly dependent. $\endgroup$ Nov 30, 2016 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, 2016 at 16:36
  • $\begingroup$ If you want to compute solutions by computer just put the problem into CVX. $\endgroup$
    – Dirk
    Nov 30, 2016 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, 2016 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$ Jun 5, 2017 at 2:05

1 Answer 1


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.

  • $\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, 2016 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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