How literally is "optimization" or "optimization algorithm" used in CS?
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.