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.

  • $\begingroup$ L-BFGS solvers like IPOPT can solve this problem very efficiently, but convergence is not guaranteed $\endgroup$ – LinAlg Jul 2 '18 at 14:35
  • 1
    $\begingroup$ 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$.) $\endgroup$ – Paul Sinclair Jul 2 '18 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.