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.
S. Boyd and L. Vandenberghe, Convex Optimization, 2004.
Yu. Nesterov, Introductory lectures on convex optimization, 2003.
A. Neumaier, Complete Search in Continuous Global Optimization and Constraint
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.
N. Hansen et al. Comparing Results of 31 Algorithms from the Black-Box
Optimization Benchmarking BBOB-2009.
M. Lozano, D. Molina, C. García-Martínez, F. Herrera
Evolutionary Algorithms and other Metaheuristics for Continuous Optimization Problems.
C: Repository of papers on optimization
A repository of eprints about optimisation and related topics.
D: Online access to mostly excellent solvers
NEOS Solvers - NEOS Server for Optimization