Math professor’s research could help military better solve optimization problems

As the global battlefield becomes increasingly complex, there’s a need for better tools to optimize resources.

Hao Hu, an assistant professor in the Clemson University School of Mathematical and Statistical Sciences, has received a three-year grant for nearly $600,000 to develop a new algorithm that will allow the Department of Defense to solve large-scale problems more quickly and accurately in areas such as military transportation and logistics, resource allocation, radio frequency assignment, and satellite network design.

The new algorithm Hu develops could be used to solve non-military problems as well.

Wide application

“It has a very wide application,” he said.

One way to tackle challenging problems is to formulate them as mathematical optimization models. Mathematical modelling is the process of describing a real-world problem in mathematical terms, usually in the form of inequalities, and then using the inequalities to help understand the original problem and find the best solution out of all feasible solutions.

Hu studies a specific category of modeling tools known as semidefinite programming (SDP). SDP models offer highly precise descriptions for a wide array of complex real-life problems, potentially enhancing the ability to make more informed decisions, Hu said.

SDP relaxation is an important tool for solving challenging combinatorial problems. They generally provide tight bounds, which help accelerate the problem-solving procedure. But their applicability to large-scale problems still needs to be improved. 

Two issues

There are two major issues, Hu said. First, the size of SDP models is often inherently bigger than the size of classical models, and there are no fast algorithms for solving SDP models. Second, SDP models are more likely to suffer from numerical instability issues than classical models, and obtaining an accurate solution from SDP models is thus more challenging.

Hu will develop a novel facial reduction algorithm to overcome the above two issues for SDP relaxations of combinatorial problems.

“By doing so, we aim to obtain an optimal solution from the models quickly and accurately,” he said.

Harnessing SDP’s potential will provide more satisfactory solutions to critical problems, Hu said. For instance, SDP models could allow the semiconductor industry to produce more powerful chips by laying them out more effectively. Similarly, it could help the healthcare sector deliver more effective radiation therapy for cancer patients. In that instance, each radiation beam can be adjusted to varying intensities to allow the desired dose to be delivered to the target while minimizing exposure to normal tissues.

“Here, SDP excels in capturing the optimal adjustments accurately, promising better treatment plans if we can extract its solutions,” he said. “Furthermore, SDP models find applications in diverse fields such as logistics, scheduling and machine learning. The advancements in understanding SDP models hold immense benefits to the public, impacting various aspects of our lives.”

Hu will collaborate with Boshi Yang, an assistant professor in the School of Mathematical and Statistical Sciences, on the research.