Proving ceil(ceil(x)/a) = ceil(x/a) using Optimization

While flipping through the recursion section of some algorithms text, I got curious as to whether Indeed, it is true. Below is a proof I came up with that interestingly enough exploits the fact that any ceiling function can be written as an optimization problem. Proof. Using simple algebra, we may rewrite the nested ceiling …

Advertisements

Why Convexity?

Etymologically, the term convex originates from the latin word convexus—which translates to arched. It is not uncommon for one to wonder why convexity seems to accompany the word "optimization" in almost every context? Why are convex functions, sets, and formulations so important? Why is there a convex relaxation (such as LASSO) craze sweeping the machine learning community, both in academia and industry? T. Rockafellar’s Convex …