What's the link between optimization and classification? I am learning about machine learning and one of the things that still not clear in my mind is how classification is done via optimization? In the couple of papers I read I just don't get how authors manage to model their problems, how does minimizing a function lead to clustering or classification, how do they know they are dealing with the right function?
 A: Optimization in classification tasks
I would suggest to start to check the 0-1 loss, which is the goal of the classification task. In other words, the objective of the classifier is trying to classify objects "correctly" / minimizing the wrong classifications or 0-1 loss.
In real world problems 0-1 loss is hard to optimize directly, therefore there are other loss functions to "approximate" 0-1 loss. (A related discussion can be found here: What are the impacts of choosing different loss functions in classification to approximate 0-1 loss) Logistic loss is one of them. And the classifier based on logistic loss is logistic regression.

Optimization in clustering tasks
The goal of clustering is putting objects into groups/clusters. But what grouping strategy is good? This is the essential question answered by the optimization formulation.
In generally, we want objects in one group are "similar" to each other and between groups are "different". The optimization objective is trying to "maximize" the similarity within groups and "maximize" the difference between groups.
A: There is another, in my mind more intuitive way, of thinking about it: 


*

*Optimization algorithms can be thought of as minimizing or maximizing an objective function. 

*They can also be thought of as search algorithms: They search through a large space of possible values for the the best set of values. 


If you think of optimization as search, then the connection between optimization and classification becomes clear: You are faced with a large space of possible models (as described by their parameters: NNet weights, Regression coefficients, etc....), and your optimization algorithm searches for the best model amongst all possible models. 
A: Once you model your classification problem as assigning probabilities to each class (so regressing to a probability distribution over the classes) you can use cross-entropy as a loss function that when minimizing will try to get the probabilities closer to the actual class and further away from the wrong classes. In that regard, classification becomes an optimization problem. Non-gradient based methods could use other objectives. Tree based methods could look for splits that increase the accuracy most, in that regard you are optimizing accuracy.
