I have been confronted with two meanings of the term "optimization" or "optimization algorithm":

  1. to find the absolute maximum in a set $X$ according to some criterion $f:X\to \mathbb R$

  2. to find a "relatively high" or "increasingly high" or "locally maximum" element in a set $X$ according to some criterion $f:X\to \mathbb R$

A friend of mine claimed that nr $1$. is the only "official" meaning of the term, and that only laymen or people who speak informally use the meaning of $2$. Is my friend correct?

  • 2
    $\begingroup$ There’s no official dictionary of computer science. $\endgroup$ Dec 29 '18 at 8:24
  • $\begingroup$ Approximation algorithms are definitely part of optimization. $\endgroup$ Dec 29 '18 at 8:25
  • $\begingroup$ @YuvalFilmus, I put "official" between quotes for a reason. $\endgroup$
    – user626625
    Dec 29 '18 at 19:24
  • $\begingroup$ Finding a local minimum or maximum definitely counts as optimization. For example, we use optimization algorithms to train neural networks, and these algorithms find local minimums, not global minimums. $\endgroup$
    – littleO
    Dec 29 '18 at 23:17

There is no governing body mandating the meaning of terms in computer science. Instead, just like all human language, the meaning of a term is defined implicitly by its use, and could depend on the language community.

In theoretical computer science, optimization is a wide topic that covers many different problems. The most common problem is to find the maximum or minimum of a function subject to constraints. Often one is interested in finding an approximate optimum, or an approximate optimum which only approximately satisfies the constraints (this is known as a bicriteria approximation).

When finding even an approximate optimum turns out to be difficult, it is reasonable to consider finding a local optimum or an approximate local optimum. This happens, for example, in machine learning, and is actively pursued by the optimization community.

Summarizing, there is no official meaning of the term optimization in computer science, any more than there is an official meaning of this term in English. In practice, in the theoretical computer science community, the term is widely used in the more relaxed sense corresponding to your second definition, and beyond.


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.