Researchers Discover the Optimal Way to Optimize

> “We are not at risk of achieving this anytime soon.”

Here "risk" seems odd (or it's a translation/language-nuance mistake).

My bet on this would be to abandon moving to vertices like simplex does and move on facets instead.

However, this requires to solve a quadratic 'best direction' problem each time which if IIRC reduces to 'Linear complementarity problem (LCP)' (https://en.wikipedia.org/wiki/Linear_complementarity_problem). The LCP problem scales with the number of active constraints which is always smaller than the dimensionality (N) of the problem. So if you have number of constraints P >> N you are golden.

Note that Dantzig has also contributed to LCP.

Obviously any breakthrough in these basic methods is directly translatable to more efficient learning algorithms for training single layer neural nets (perceptrons). Extending to multi layer NNs is not far off from there...

CP sits in a weird place between LP and general global optimization solvers. You need to study the solution space to make sure it is not higher order than CP can handle. And if your analysis fails, you may end up with local optimization. It is much easier to figure out if the problem is linear. So might as well switch to GA instead of risking it with CP.

I’m a software engineer who has been trained on convex programming. I have read the Boyd book, did some hobby projects in the area. But it is just not comming up during the day to day work. Even when i have a task well suited for continous value optimisation it does never seem to be a good fit for convex programming. The application areas were sensor calibration, slam, model predictive control, trajectory prediction and the like. Usually when this happens we just throw the problem at ceres solver and deal with it when it is not converging. Would be nice to have the strong guarantees a convex optimiser could give us but I’m not finding a way in practice.

It is probably just a “git gud” situation. I even re-read Lars Blackmore’s “Lossless Convexification of Nonconvex Control Bound and Pointing Constraints of the Soft Landing Optimal Control Problem” from time to time hoping that i find a way to apply a similar convexification idea to my problems. With all of that I’m not that surprised that convex optimisation is not more widely known.

I’ve always thought it was weird too, and have spent far too much time thinking why - my best guess is that it’s used in Economics while other methods aren’t used outside programming curiosities (unless you need to apply it at work)

I feel software/CS people largely avoid (or don’t need) certain areas of math.

To me, convex optimization is more the domain of engineering when there are continuous functions and/or stochastic processes involved.

Much of signal processing and digital communication systems are founded around convex optimization because it’s actually a sensible way to concretely answer “was this designed right?”.

One can use basic logic to prove a geometry proof, or the behavior of a distributed algorithm.

But if one wants to prove that a digital filter was designed properly for random/variable inputs, it leads to finding solutions of convex optimization problems (minimization of mean squared error or such).

Of course, whether the right problem is being solved is a different issue. MMSE is just mathematically extremely convenient but not necessarily the most meaningful characterization of behavior.

One of OpenAI's founding team members developed Adam [0] well before it was flashy and profitable. It's not like nobody is out there trying to develop new algorithms.

The reality is that there are some great, mature solvers out there that work well enough for most cases. And while it might be possible to eke out more performance in specific problems, it would be very hard to beat existing solvers in general.

Theoretical developments like this, while interesting on their own, don't really contribute much to day-to-day users of linear programming. A lot of smart people have worked very hard to "optimize the optimizers" from a practical standpoint.

[0] https://arxiv.org/abs/1412.6980