Advantages of approaching a problem by formulating a cost function that is globally optimizable This is a rather general question (i.e. not necessarily specific to statistics), but I have noticed a trend in the machine learning and statistical literature where authors prefer to follow the following approach: 
Approach 1: Obtain a solution to a practical problem by formulating a cost function for which it is possible (e.g. from a computational standpoint) to find a globally optimal solution (e.g. by formulating a convex cost function).
rather than:
Approach 2: Obtain a solution to the same problem by formulating a cost function for which we may not be able to obtain a globally optimal solution (e.g. we can only get a locally optimal solution for it).
Note that rigorously speaking the two problems are different; the assumption is that we can find the globally optimal solution for the first one, but not for the second one.
Other considerations aside (i.e. speed, ease of implementation, etc.), I am looking for:


*

*An explanation of this trend (e.g. mathematical or historical arguments)

*Benefits (practical and/or theoretical) for following Approach 1 instead of 2 when solving a practical problem.

 A: My believe is that the goal should be to optimize the function you are interested in. If that happens to be the number of misclassifications - and not a binomial likelihood, say - then you should try minimizing the number of misclassifications. However, for the number of practical reasons mentioned (speed, implementation, instability etc), this may not be so easy and it may even be impossible. In that case, we choose to approximate the solution. 
I know of basically two approximation strategies; either we come up with algorithms that attempt to directly approximate the solution of the original problem, or we reformulate the original problem as a more directly solvable problem (e.g. convex relaxations). 
A mathematical argument for preferring one approach over the other is whether we can understand a) the properties of the solution actually computed and b) how well the solution approximates the solution of the problem we are actually interested in. 
I know of many results in statistics where we can prove properties of a solution to a  optimization problem. To me it seems more difficult to analyze the solution of an
algorithm, where you don't have a mathematical formulation of what it computes (e.g. that it solves a given optimization problem). I certainly won't claim that you can't, but it seems to be a theoretical benefit, if you can give a clear mathematical formulation of what you compute. 
It is unclear to me, if such mathematical arguments give any practical benefits to Approach 1 over Approach 2. There are certainly somebody out there, who are not afraid of a non-convex loss function.
A: @NRH provided an answer to this question (over 5 years ago), so I'll just offer an Approach 3, which combines Approaches 1 and 2.
Approach 3: 


*

*Formulate and solve to global optimality a convex, or in any event, globally optimizable (not necessarily convex), problem which is "close" to the problem you really want to solve.

*Use the globally optimal solution from step 1 as the starting (initial) solution to a non-convex optimization problem you really want to solve (or more want to solve than the problem solved in step 1). Hope that your starting solution is in the "region of attraction" to the global optimum relative to the solution method employed to solve the non-convex optimization problem you really want to solve.

