8
$\begingroup$

I am dealing with an optimization problem that has a large number of variables to optimize over - for example let's call these variables $x$, $y$, and $z$ and I wish to minimize the function $f(x,y,z)$. The optimization method that I am using is not able to handle optimizing over all the variables at once. I am instead simplifying the problem by optimizing over a single variable at a time while keeping the other variables fixed.

I.e. I fix $y=y_0$, and $z=z_0$ and then optimize the function only over $x$. This 1D optimization yields some optimal value $x^*$. I then fix $x=x^*$, $z=z_0$, then optimize over $y$. I realize that this doesn't necessarily provide me with a globally optimal solution but it should yield a local minimum.

I am wondering what the name of this method is and where I can find any information about it. Also if there is a more appropriate community to ask, please let me know. Thanks

Edit: the optimization is conducted over $x$, then $y$, then $z$, then $x$, and so on until the solution converges.

|cite|improve this question
$\endgroup$
9
$\begingroup$

This is coordinate descent. I believe it's used on very large-scale problems when other methods like gradient descent might be too slow (e.g., http://epubs.siam.org/doi/abs/10.1137/100802001). It should converge to a local minimum, but it also would require more steps than something like gradient descent or Newton-type methods.

|cite|improve this answer
$\endgroup$
4
$\begingroup$

The approach you described originally (only one iteration optimizing in each of the three variables x,y,z ) is not guaranteed to converge to the optimal solution unless F(x,y.z) is variable separable into univariate functions. Therefore, what you describe is not technically an optimization "method", but an optimization "heuristic", similar to an operator splitting method or alternating direction implicit (ADI) methods.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ You are right it is this method is not guaranteed to reach the optimal solution. The function that I am trying to minimize is non-convex with multiple local minima. Therefore I am satisfied with finding a local minimum and not necessarily the optimal solution. I am still curious to whether this heuristic has been used before in literature $\endgroup$ – user69813 Jan 11 '16 at 16:11
  • $\begingroup$ It is not even guaranteed to find a local minimum, or even anything remotely close to it. $\endgroup$ – Paul♦ Jan 11 '16 at 17:44
  • $\begingroup$ @Paul, I think that the methods converges for smooth functions: "It can be shown that this sequence has similar convergence properties as steepest descent. No improvement after one cycle of line search along coordinate directions implies a stationary point is reached." This reference discuss about it. $\endgroup$ – nicoguaro♦ Jan 11 '16 at 21:20
  • 3
    $\begingroup$ @nicoguaro I think before OP's edit, it sounded like the method did only one iteration of it, then stopped. I was a little confused too. $\endgroup$ – Kirill Jan 12 '16 at 13:23
  • $\begingroup$ @Kirill, I understand. I will erase my comment then. On the other hand, if the question changed so should do the answer, no? $\endgroup$ – nicoguaro♦ Jan 12 '16 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.