Separability of Constrained Optimization

435 Views Asked by At

Suppose I have a constrained optimization problem of the following form : $$\underset{g_1(x_1) \leq c_1 ,\\ g_2(x_2) \leq c_2,\\.\\.\\g_n(x_n) \leq c_n}{\operatorname{min} \big[f_1(x_1)+f_2(x_2) +.....+f_n(x_n)\big]}$$ where $c_1 ,c_2,....c_n$ are some constants, $f_1,...,f_n$ and $g_1,...,g_n$ are some functions and $x_1,x_2....x_n$ are $n$ blocks of variables which when appended together as $[x_1^\top,x_2^\top,....,x_n^\top]^\top$ belongs to some vector space $\mathcal{X}$.

For example , if $\mathcal{X} = \mathbb{R}^{10}$ , then $x_1$ could comprise of the first $4$ entries of the vector in $\mathbb{R}^{10}$, $x_2$ could comprise of the next $3$ entries of the vector in $\mathbb{R}^{10}$ and $x_3$ could comprise of the last $3$ entries of the vector in $\mathbb{R}^{10}$. Are problems of the above form separable in the sense that : Can I solve separate optimization problems of the form

$${x}_i^* = \underset{g_i(x_i) \leq c_i }{\operatorname{argmin} \big[f(x_i)\big] }\;\;\;\;\;\;\;\;\;\;i = 1 \;\text{ to } \;\;n $$

and then append the individual solutions to get $x^* =[(x_1^{*})^\top,(x_2^{*})^\top,....,(x_n^{*})^\top]^\top $, the solution of the original problem. If yes, how can I prove that the solution obtained by appending $x_1^*,x_2^*,...x_n^*$ is a solution of the original problem.