# Coordinate descent in integer programing: when does it work?

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}$$. For the functions $$f$$ that interest me, 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 along each coordinate a sufficient condition for this procedure to work? Also, if anybody has a reference on the topic that would be highly appreciated.

• "Strictly convex" is not a property that can apply to such functions $f.$ Nor is "gradient," for that matter. – whuber Jan 9 '19 at 19:46
• Right, I guess we can think of convexity of the function on the relaxed set, or convexity along each coordinate. No need for a gradient however. I'm happy to consider any nontrivial condition on $f$ that would make this work. – user_lambda Jan 9 '19 at 20:03
• But when you think of it that way, you are asking whether a method of optimizing a function over a large set $X\subset \mathbb{R}^n$ (such as a convex closed set with nonempty interior) can produce an optimum over a discrete (tiny) subset of points in $X.$ From this abstract point of view it ought to be obvious there is no hope in general that it will succeed. (If this isn't perfectly clear, draw a picture in one dimension.) This indeed is why integer and mixed-integer optimization is so much harder than convex optimization. – whuber Jan 9 '19 at 20:34
• I'm not sure I'm following. I know that integer programing is hard but there are some results out there. In one dimension the algorithm works trivially - I can optimize over any single dimension very easily. I want to know if it can be extended to many dimensions. – user_lambda Jan 9 '19 at 20:37
• You cannot optimize over a single dimension easily at all when the domain of the function is the set of natural numbers! For instance, minimize $\log(1+10^{-12}+\cos x)$ for $x\in\mathbb N.$ – whuber Jan 9 '19 at 20:59