I think that when people say "hard problems" they mean "problems that almost certainly have solutions if you are willing to put in the effort". Poverty on the other hand is a much, much harder problem than that. In fact, no one quite knows how to solve it in a general way (there are things that seem to work in certain contexts but not in others, many special case half-solutions). And on top of that, there probably is…
http://en.wikipedia.org/wiki/Basic_income_guarantee The solution is simple. You simply give every adult citizen enough money every year to insure that they can afford food, shelter, and other basic needs. Give it to everyone, rich or poor, same amount. BAM! No more poverty, except in self-inflicted cases (drug addiction, for example), or things like severe and very expensive illness (which are covered by other means)…
Almost all homeless have mental illness and/or substance abuse issues. That's why they are unable to act on one of the endless options that exist at the moment that can get them even the most basic of accommodations and employment. The people your solution truly helps are the non-homeless poor. To be honest this is a much easier issue to address given some willpower. Then again, as a Canadian, I find basic medical care to be a no brainier as well, which seems to be something the US struggles with quite a bit.
You can't simply suggest that addiction/mental illness is "self inflicted", give them $10K and say "You're on your own, bud." That isn't solving anything. Solving homeless is the same as solving mental illness and/or addiction, and those are massively hard problems to address.