5
$\begingroup$

From Wikipedia:

In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution. If the change produces a better solution, an incremental change is made to the new solution, repeating until no further improvements can be found.

I wonder if there are differences between hill climbing method and coordinate descent/ascent method? They seem the same to me.

Thanks and regards!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

Hill climbing = optimization.

Coordinate descent is ''search in turn along each coordinate'', changing one variable at a time, and is a very specific optimization technique. (Very slow, too, except for separable problems.)

But please read more substantial stuff than wikipedia to see how optimization is done and how the terminology is actually used, rather than asking here about everything that wikipedia leaves open. This site is not a language course in optimization!

Online references to some excellent books/surveys/papers/websites on optimization:

A. Non-heuristic (Usually requiring gradients or subgradients):

J. Nocedal and S.J. Wright,Numerical Optimization, 2006.
http://home.agh.edu.pl/~pba/pdfdoc/Numerical_Optimization.pdf

S. Boyd and L. Vandenberghe, Convex Optimization, 2004.
http://www.stanford.edu/~boyd/cvxbook

Yu. Nesterov, Introductory lectures on convex optimization, 2003.
http://www.core.ucl.ac.be/~nesterov/Courses/INMA2460/Intro-nl.pdf

A. Neumaier, Complete Search in Continuous Global Optimization and Constraint Satisfaction, 2004
http://www.mat.univie.ac.at/~neum/papers.html#glopt03 (this is by me)

B. Derivative-free optimization (mostly heuristic)

L.M. Rios and N.V. Sahinidis, Derivative-free optimization: A review of algorithms and comparison of software implementations.
http://thales.cheme.cmu.edu/dfo/dfo.pdf

N. Hansen et al. Comparing Results of 31 Algorithms from the Black-Box Optimization Benchmarking BBOB-2009.
http://www.lri.fr/~hansen/gecco09-results-2010.pdf

M. Lozano, D. Molina, C. García-Martínez, F. Herrera Evolutionary Algorithms and other Metaheuristics for Continuous Optimization Problems.
http://sci2s.ugr.es/eamhco/

C: Repository of papers on optimization

A repository of eprints about optimisation and related topics. http://www.optimization-online.org/

D: Online access to mostly excellent solvers

NEOS Solvers - NEOS Server for Optimization http://www.neos-server.org/neos/solvers/index.html

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! May I ask what are some substantial stuff? And standard references saying hill climbing is not what Wiki says? $\endgroup$
    – Tim
    Commented May 4, 2012 at 19:55
  • $\begingroup$ Are you making a language study (your questions suggest that), or do you want to learn optimization (in which case what you read in wikipedia or anywhere else is sufficient to go on to the substance, even though the words are imperfectly explained)? Read good books and surveys on optimization. I'll indicate some online stuff in my answer, in a few minutes. $\endgroup$
    – Arnold Neumaier
    Commented May 4, 2012 at 20:19
  • $\begingroup$ I am learning optimization, its language (glossary, terms) included. I am not learning English. Thanks! $\endgroup$
    – Tim
    Commented May 4, 2012 at 20:34
  • $\begingroup$ The language will come with experience. The substance is in the algorithms. $\endgroup$
    – Arnold Neumaier
    Commented May 4, 2012 at 20:36
1
$\begingroup$

Going by the definitions of hill climbing and coordinate descent in wikipedia, they're both very similar: each operates on every input variable of the function of interest separately. The main difference between the two methods appears to be in how they adjust those input variables.

In basic hill climbing, each variable is first adjusted by a predefined quantity, and then the function value is tested for improvement, like a very simple Monte Carlo algorithm. On the other hand, in coordinate descent a line search is performed along each variable in order to directly find the local minima/maxima of the function value with respect to that variable.

In practice, this means that in a single iteration of hill climbing each variable will be incremented by either 0 or a fixed quantity, whereas in coordinate descent each variable will be incremented by some value between 0 and the endpoint of the line search. In their vanilla forms, it seems like coordinate descent is best applied to functions on continuous variables, while hill climbing can be applied to both continuous and discrete variables.

In the literature, the two methods seem to get conflated somewhat, although it appears that coordinate descent is most often used to descrive this kind of search when it is performed along the axes of a Euclidean space.

Improve this answer
$\endgroup$

Your Answer

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

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