0
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ "Strictly convex" is not a property that can apply to such functions $f.$ Nor is "gradient," for that matter. $\endgroup$
    – whuber ♦
    Commented Jan 9, 2019 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
    Commented Jan 9, 2019 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 ♦
    Commented Jan 9, 2019 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
    Commented Jan 9, 2019 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 ♦
    Commented Jan 9, 2019 at 20:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.