A convex optimization problem

Question

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?

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.