Photo: DTU

A mathematician on a mission

Tuesday 27 Nov 18
|
by Morten Andersen

HC Ørsted lectures

Twice a year, DTU invites prominent foreign researchers to lecture on their work, research findings, and the prospects within their field of research at the so-called Ørsted Lectures. The lectures are open to all.

Watch or revisit some of the previous lectures and find out about upcoming lectures.

Stanford University Professor Stephen Boyd applies convex optimization to a wide range of engineering problems. With astounding results.

"DTU should teach a course on convex optimization. And all students should be obliged to take it!"

Americans have a reputation for being forward, and Stephen P. Boyd, Samsung Professor of Engineering at the Electrical Engineering Department, Stanford University, is no exception to that rule.
Before diving into what convex optimization actually is a quick illustration of the momentum of the cause for which Stephen Boyd is the unofficial leader.

During the last decade or so, convex optimization has been applied to areas such as circuit design, control systems, signal processing, finance, data analysis, and model fitting.

The results are astounding, as optimizations can be performed either much faster or with several orders of magnitude higher accuracy, ultimately leading to higher yields, better predictions and improved business performances.

The jewel among the results is the contribution to the world's first vertical landing of a space launch rocket, the Falcon 9 operated by Space Exploration Technologies (or SpaceX) in 2017.
This achievement has opened a new era in space flight, as rockets can be reused rather than immediately becoming debris.

Half a year ago, SpaceX reported the use of software from Stephen Boyd's group.

"I knew for some time, they were using our software but I could disclose it only after they chose to report it."

Optimization often involves improving yields with, say, 10 or 20 per cent, which may impress colleagues–and will certainly make the management of any business very happy–yet fails to impress outsiders.

"In the case of the Falcon 9, we have contributed to making something possible, which was previously impossible. So that's an improvement of an infinite magnitude!"

What is convex optimization?

To understand what convex optimization is, it is necessary to know how optimization is normally done in engineering.

Take a problem from everyday life. How will weather influence ice cream sales? We all know that sales will be higher on a sunny day compared to a rainy one, but an engineer will want a more accurate description. To that end, data points are necessary. For instance, these data points could be ice cream sales across a chain of supermarkets plotted against hours of sunshine per day.

As expected, the data points will tend to form an upward curve. Still, you will always have the odd data point far off the curve, and many points deviating slightly. The art here is to establish the curve that best represents the total contingency of data points.

This curve gives a model for the relationship - ready to assist, for instance, a logistics operator in a chain of supermarkets.

An exact solution method to complex problems

Known as "the least squares method", the mathematics to solve this problem was developed more than 200 years ago for applications in astronomy.

The curve with the lowest sum of the squares of all the residuals – residual meaning the deviance of a data point from this curve – is the optimal fit for the data.

"The great thing about convex optimization is its ability to transform an apparently very complex problem into something which can be solved exactly—just as if it had been a least squares problem."
Professor Stephen Boyd, Standford University

"The least squares problem is an example of a simple optimization problem, which can be solved exactly. However, many optimization problems are far more complex than the relationship between sunshine and ice cream sales. The great thing about convex optimization is its ability to transform an apparently very complex problem into something which can be solved exactly—just as if it had been a least squares problem," Stephen Boyd explains.

A convex function curves upwards; mathematically it has positive curvature. Examples are the quadratic function and the exponential function.

"The positive curvature is very practical in optimization. It allows us to know with certainty that the point we've found is actually the very best choice. When the functions aren't convex, you may have what looks like a nice solution, but you are not certain whether an even better solution might exist. With convex optimization, you will always know that you have found the optimal solution and don't need to look any further."

Contribution to Danish wind power

The basic mathematics involved was developed more than 50 years ago.

"Many have contributed, with some of the most important contributions coming from Soviet mathematicians in the 1960'ies. Since then, many researchers have worked on convex optimization, especially new algorithms that can handle very large problems such as those arising in machine learning. My group has made some contributions to new methods, but mainly what we have done is to take all these basic tools and making them accessible to engineering and other fields," says Professor Boyd.

To illustrate, he gives an example with high Danish relevance:

"A few years ago, I was approached by an engineer from a Danish wind energy company. The challenge was how to optimize production from an offshore windmill farm."

It is well known that windmills situated in the wake of others will produce less. In addition, the situation will be different depending on wind speed and direction.

Despite this complexity, Stephen Boyd was able to formulate the optimization as a convex function. Or, strictly speaking, as a concave function since the task was not to find a minimum value but rather a maximum value for the possible energy output. A concave function curves downwards and is thus the reverse of a convex function. Yet, to a mathematician, it comes down to the same thing.

"The point is that the real challenge is in the formulation of a given optimization problem. Most often, when a company or an engineer describes a problem you will have the feeling things are very complicated. I have to admit not always will it be possible to formulate the problem as a convex function, but surprisingly often it is," says Stephen Boyd while disclosing one of his favourite tricks:

Photo: DTU

Mathematics in practice

"After listening to such problem description, I will invite the person to lunch. Meanwhile, a student in my group will work on the problem. As we return from the meal, my student will provide a solution which may not be perfect, but often significantly better compared to the state-of-the-art solution normally used in the given context."

A trick that never fails to impress.

"Obviously, when you see your best current method improved so fast by a student, you will be keen to see how much further optimization will yield. As we take things a bit further, we will often arrive at a result 10-12 times more powerful compared to their current method. As a mathematician, you would normally leave it there, but we will often take things a bit further. For somebody to actually apply the solution it will take more work," says Stephen Boyd, adding:

"Many fields of engineering have a lot of implicit limitations. Things you can't do or should do. Sometimes our initial solution will violate such rules. The engineer will then complain, but how should we – as mathematicians – know that you can't raise pressure that fast in a given chemical engineering facility? So, the point is that expressing the true limitations of the required solution is actually highly important."

This observation should not offend engineers too much. In fact, Stephen Boyd is partly an engineer himself:

"Throughout my undergraduate studies and for the first few years of my PhD, I did rock & roll sound engineering, travelling as a sound engineer for rock bands on tour. Yes, this was fun, but it also gave me an appreciation of how practical engineers approach problems – and, often, crises!"

Other members of his group have degrees in electrical engineering, mechanical engineering, bioengineering, applied mathematics, pure mathematics, medicine, business, computational mathematics, and data science. The diversity is reflected in a class on convex optimization taught by Stephen Boyd at Stanford, with about 350 students from 30 different departments attending.

"For any given subject I may talk about, I will always have at least ten people in the auditorium knowing more about it than myself. So, what we are creating here is really a multi-cultural phenomenon. A lot of our effort is getting people to communicate with each other, despite speaking different academic "dialects" which can be mutually unintelligible."

Everything is available as Open Source

All of Boyd's academic writings, lectures, software, course materials, and data are available as Open Source, and very widely viewed and downloaded:

"Things have really taken off during the last five years. It is hard to verify the exact number of users. However, based on the number of downloads and citations of our work, a good guess is at least 100,000 active participants in our community. Most of these people we have never met. Yet, they not only use our software but also contribute. I can be applying software, which is actually created by a 16-year old in Estonia. That's part of the fun."

Another ambition is making the software accessible to a wider audience.

"Given the merits of convex optimization, I feel the potential should be higher, but in the current situation, we shouldn't expect more than a four or five-fold increase in the number of users. We are limited by the fact that you still need some skills in mathematics to use our software. For a typical business operator, it is probably hard."

But not for a candidate from DTU?

"Certainly, anybody with a degree from DTU will be able to use our software. Still, I will recommend DTU to create a course in convex optimization. Not just because this is a useful tool in practically all areas of engineering, but just as much due to the very clear way of thinking introduced. Working with convex optimization encourages interdisciplinary collaboration, and – even more importantly – it promotes a highly organized way to collect your thoughts. Once you formulate your problem right, you are already a lot closer to the solution."

CV

Stephen P. Boyd is Samsung Professor of Engineering at the Electrical Engineering Department at Stanford University. He graduated from Harvard University with a degree in mathematics in 1980 and got a PhD from U.C. Berkeley in 1985.

Stephen Boyd’s research group has produced a number of open source software packages such as CVX, CVXPY, and Convex, which are used worldwide for convex optimization. He is a member of a number of scientific societies, one of which is the National Academy of Engineering.

With convex optimization, optimization can be much faster or far more precise.

Professor Stephen Boyd’s research group at Stanford University has combined all the basic tools for convex optimization and made them available to a number of engineering disciplines.