9
$\begingroup$

I was wondering what differences and relations are between "search methods" and "optimization methods"?

Especially when solving an optimization problem? I emphasize the context of solving optimization problems, because I guess search methods are not just for solving optimization problems, but also non-optimization problems?

My confusion comes from the following facts:

  1. There are some optimization methods, named "xxx search", such as local search, stochastic search, .... What does "search" mean actually? I wonder if there are optimization methods that are not "search"?
  2. Also in this book Introduction to Stochastic Search and Optimization by Spall, I don't quite understand the difference between "Search" and "Optimization" in its title as well as in its content. Why needs to distinguish between "Search" and "Optimization", if they mean the same? Or does "Optimization" mean stochastic optimization tasks/problems instead of optimization methods, as opposed to "search" means the methods to solve the optimization tasks/problems?
  3. Also No free lunch in search and optimization distinguishes search and optimization again.

Thanks and regards!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

search = attempt to find a feasible point that satisfies all constraints (and for optimization a better point than found so far), generally using function values only.

local search: improving a feasible point (or a distance to feasibility measure) by searching among neighboring points.

stochastic search: searching using a nondeterministic criterion for choosing trial points.

This is independent of whether an optimization criterion is given. In particular, in ''No free lunch in search and optimization'' search refers to search for feasibility, while optimization refers to search for optimality.

In a general sense, for optimization problem, search and optimization are equivalent. However, they have connotations that make a difference in the usage of the term.

optimization method = a method for solving an optimization problem, often (but not necessarily) using gradient (or subgradient or even Hessian) information.

Being able to use gradients drastically increases the efficiency of optimization methods. One uses in this context (i.e., with gradients known) to the term search only in the combination ''line search'' which means searching for a better point along a chosen direction.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! So for optimization problems, (1) In its broader sense, search is equialent to optimization methods. (2) In its narrower sense, does search "generally using function values only" mean "{search methods} = {optimization methods using function values only} $\cup$ {line search methods}" ? Is "line search" the only "search method" that uses things beyond function values? If I add some perturbation to gradient in a gradient based-method, does the method become a "stochastic search" method? Do local search and stochastic search both only use function values? $\endgroup$
    – Tim
    Commented May 4, 2012 at 14:13
  • $\begingroup$ (3) Are search methods in its narrow sense all metaheuristic? $\endgroup$
    – Tim
    Commented May 4, 2012 at 14:13
  • $\begingroup$ @Tim: A line search may or may not use gradients in its search (e.g., a Wolfe line search needs them). You shouldn't attach to these words a too precise meaning; they are suggestive of something, not mathematical concepts with a precise meaning. - Newton's method uses gradients and Hessians. - A method is stochastic once the search involves a random number generator. - local search may be used in a general sense of a method that doesn't guarantee convergence to a global optimum, or mean a direct search based on inspecting local neighborhoods of the current best point only. $\endgroup$
    – Arnold Neumaier
    Commented May 4, 2012 at 14:47
  • $\begingroup$ A metaheuristic must contain principles more specific than just ''local search'' to deserve its naame; I never heard it apply this generally. But the terminology isn't very precise $\endgroup$
    – Arnold Neumaier
    Commented May 4, 2012 at 14:48
4
$\begingroup$

The difference in terminology between "search" and "optimize" comes from the fact that searching refers to the process of finding an $x^\ast$ so that for a given $g(x)$ we have $g(x^\ast)=0$, i.e. we search for a root. In optimization, we want to find an $x^\ast$ so that $f(x) \rightarrow \textrm{min!}$. At least if $f$ is smooth, then finding this minimum is typically converted to the problem of finding a root for $g(x)=\nabla f(x)$. In other words, the term "searching" comes from a more general problem, but for optimization problems things that deal with optimization are often reduced to things that deal with searching.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Search is more generally applied to systems of equations and inequalities. In particular, in case of optimization, one searches for a solution of $g(x)=0, f(x)\le f_{best}$. But direct search methods in optimization don't have access to $g(x)$ hence cannot simply apply a search algorithm to this set of constraints. $\endgroup$
    – Arnold Neumaier
    Commented May 9, 2012 at 10:30

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.