Denote $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to minimize a function $f:N\rightarrow \mathbb{R}$. It is very easy to minimize $f$ coordinate by coordinate so one natural algorithm is to iterate on a mapping $T$ for which the $i$th element is defined as $$(Tn)_i=\arg\min_{\tilde{n}_i\in N_i} f\left( \left\{ n_1,\dots,\tilde{n}_i,\dots,n_I\right\}\right)$$ until we have convergence. This is essentially a coordinate descent algorithm but in a discrete space.

My question is: under what conditions does this approach yield the true global minimum of $f$? For instance, is $f$ strictly convex a sufficient condition for this procedure to work? Also, if anybody has a reference on the topic that would be highly appreciated.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.