For example, "John was asked to solve a complex challenge."
I find this to read very awkwardly, as if someone told me they solved a banana. Is this a case of verb-noun mismatch?
English Language & Usage Stack Exchange is a question and answer site for linguists, etymologists, and serious English language enthusiasts. It only takes a minute to sign up.Sign up to join this community
So long as the noun is something solvable, this would be a valid construction. Thus puzzles, Rubik's cubes and equations are all nouns which can be the object of the verb "to solve". So if the challenge was a puzzle, it could be solved. If the challenge was, however, physical in nature, it would be more natural to say that the challenge was completed. The answer to your question is thus "it depends on the nature of the challenge in question - if the challenge can be said to have a solution, it is acceptable to use the verb 'solve'".
"Solving a challenge" may not be linguistically correct. but it seems to be on the rise in a business or technical context (where "overcome a challenge" would sound slightly esoteric. An example I found is the Solve initiative initiated by the MIT (Massachusetts Institute of Technology) https://solve.mit.edu/challenges.