Researchers Discover the Optimal Way to Optimize | Hacker News Reader

Researchers Discover the Optimal Way to Optimize

quantamagazine.org

83 pointsjnord14 comments

> While the efforts of Bach and Huiberts are of theoretical interest to colleagues in their field, the work has not yielded any immediate practical applications.

There must be lots of theorems in optimization theory that can be improved w/ more intellectual effort. Unlike video generation if AI is applied to find better algorithms it will have a direct impact on the economy b/c almost every industrial process is using some kind of constraint optimization algorithm including the simplex algorithm & its variations. But it's not flashy & profitable so OpenAI will keep promising AGI by 2030 w/o showing any actual breakthroughs in real world applications.

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

No one thought that theorems in number theory would ever be useful but those theorems are now the foundations of tools like wireguard. Computing the next frame of a snowboarding video is much less valuable than improvements in optimization algorithms that are used daily for optimal transport logistics & energy grid optimization. The promise of AI was solutions to practical problems but what we are getting are frivolous cartoons & 6 second "movie" clips.

Another nice quote,

> The next logical step is to invent a way to scale linearly with the number of constraints. “That is the North Star for all this research,” she said. But it would require a completely new strategy. “We are not at risk of achieving this anytime soon.”

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

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

It is not a mistake, it is just being cheeky.

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...

Neat. Progress on lower bounds. That's been a tough area for decades.

There are a lot of problems like this. Traveling salesman, for example. Exponential in the worst case, but polynomial almost all the time.

Does this indicate progress on P = NP?

Anecdotally it seems like most software engineers have heard of linear programming, but very few have heard of convex programming [1], and fewer still can apply it. The fixation on LPs is kind of odd ...

[1] https://github.com/cvxpy/cvxpy

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.

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’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.

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.

Reply on news.ycombinator.com