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.

  • 1
    $\begingroup$ "Strictly convex" is not a property that can apply to such functions $f.$ Nor is "gradient," for that matter. $\endgroup$ – whuber Jan 9 '19 at 19:46
  • $\begingroup$ 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. $\endgroup$ – user_lambda Jan 9 '19 at 20:03
  • $\begingroup$ 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. $\endgroup$ – whuber Jan 9 '19 at 20:34
  • $\begingroup$ 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. $\endgroup$ – user_lambda Jan 9 '19 at 20:37
  • $\begingroup$ 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.$ $\endgroup$ – whuber Jan 9 '19 at 20:59

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.