# How to solve a large-scale convex problem under some linear constraints.

Consider the following convex problem, where $M,N$ are integers and $a_n\ge0$ is a constant.$$(P_0)\min_{\{x_n\},\{y_m\}}\sum_{n=1}^Nf(x_n)\\ s.t. a_nx_n\le0\\ x_n+\sum_{m=1}^My_m\le0\\ x_n\in[0,1],n=1,2,\cdots,N\\ y_m\in[0,1], m=1,2,\cdots,M$$

In Problem $P_0$, $f(\cdot)$ is smooth and convex, and the constraints are linear (notes: $f(\cdot)$ depends only on $\{x_n\}$). I know $P_0$ can be solved by CVX efficiently when $N,M$ are relatively small. But I still have some questions about solving this problem.

(1) Can $P_0$ be solved by block coordinate descent method with guaranteeing convergence? (I noticed that the block $\{y_m\}$ is coupled with block $\{x_n\}$)

(2) When $N$ or $M$ is very large, this large-scale convex optimization problem $P_0$ may not be solved efficiently by CVX and other solvers. So, is there some method to handle this type of problem?

Any help is appreciated.

• L-BFGS solvers like IPOPT can solve this problem very efficiently, but convergence is not guaranteed – LinAlg Jul 2 '18 at 14:35
• As stated, your problem is trivial. The only way the constraints can be satisfied is if $x_n = 0$ for all $n$. Therefore, the answer is $Nf(0)$. Did you not copy it correctly? (The $x_n, y_m, a_n$ are all $\ge 0$, but the constraints require sums and products of them to be $\le 0$.) – Paul Sinclair Jul 2 '18 at 23:26