I’ve been thinking a lot about optimization recently, and the many ways mathematicians and computer scientists alike have devised clever ways to find local and global optima. In data structures and algorithms specifically, two approaches to solving for global optima stand out: (1) greedy approaches, and (2) dynamic programming. I want to make a brief case that the applications of these approaches can give us some (noisy) insight into how we think of optimization in life more broadly.
You’re really better off learning about each of these approaches from someone smarter and more comprehensible than me (the bar is low) but if you insist on not clicking off this page (I love you) then here’s a description that should be sufficient for our purposes.
Greedy algorithms seek to solve for the global optima by repeatedly solving for local optima along the way. In doing so, they never “backtrack” or change a decision that has been made. A problem is simply decomposed into successive subproblems with a solvable suboptimum, and we repeatedly solve for these suboptima which leads us to the global optimum. Hopefully, it should be intuitive to you that this process won’t work on all problems. In fact, it won’t work on the vast majority of problems. After all, something that might be a good idea in the context of a subproblem might lead you astray in the grand scheme of things.
Dynamic programming overcomes this shortcoming by (often recursively) decomposing of a problem into its subproblems, solving each subproblem, then (at the risk of being quite reductive) using knowledge of the solution to each subproblem to guide itself towards the global optimum. Unlike greedy algorithms, dynamic programming guarantees you a global optimum but it does so with the requirement of “seeing” and solving all of the subproblems that comprise your particular problem whereas greedy algorithms need only to know about your current and past subproblems.
Okay. Hopefully all that babbling made some sense to you.
To me, it seems clear that there is some “globally optimum” life \(l^*\) that you can lead in the space of all lives possible for you \(L\) (so obviously \(l^* \in L\)) which you arrive at through some tuple(s) of decisions. It also seems clear that life can be broken down into subproblems in various ways (the most obvious to me is chronologically). Ah! An optimization problem (psychologists would have a field day with me and life coaches are rolling in their graves).
Aside: you get to decide what the variable you’re optimizing for here is. Money? Power? Happiness?
I want to make the case here that while the purely dynamic programming solution here would guarantee you the global optimum here, it sucks as a way of approaching your life! For one reason, it’s impossible! We don’t know all of the sub-problems of our life ex-ante. For another, it’s boring! Sure, we can sit around and optimize every decision all day, but (as my little sister would say) “that lacks whimsy.”
“So Sudhan,” I hear you saying, “the greedy algorithm isn’t much better - you said it yourself! If I just try to optimize for today, I might not end my life anywhere near the optima I’m hoping for!” Fair point, stranger. Two arguments here.
This is why it’s extremely important that we choose our subproblems carefully. Choose a subproblem that’s too short to optimize for, and you’re likely to be led astray by infatuations and short-lived pleasures. Choose a subproblem that’s too long, and it might be near impossible to figure out where the suboptima is, let alone get to it. We can’t just optimize for today, but we can’t just optimize for the next decade either. Choosing the right subproblems makes all the difference in a greedy algorithm.
Global optima often isn’t everything – when your global optima isn’t guaranteed, hitting your local optima has value. Suppose that you’re optimizing for happiness (what naïve fool would optimize for that?). Even if you’re not anywhere near as happy as you could’ve been in \(l^*\), by greedily solving for your local suboptima, you arguably were happier than if you had tried to run the fool’s errand of solving exclusively for the elusive global optima.
My point here isn’t that the greedy algorithm is the best and only one to use here. Far from it. Notions from dynamic programming can also yield wonders – especially the idea that we should recognize, solve, and learn from overlapping subproblems so that we don’t have to solve the same problems twice. I’m sure you could also make a strong case for other optimization techniques like gradient descent giving us some good lessons. But it does make sense to think about things greedily and often optimize for the now (or near future). Computer science says so (actually, computer science says it could go horribly wrong. But what do computer scientists know?)