Solving Complex Problems with Quadratic Optimization

Mathematical optimization allows business leaders to navigate complex decisions and identify the best possible route to meet their goals.  

Different business questions will require different approaches, depending on the nature of the variables and constraints involved. For the basics on different types of optimization models, check out our guide to optimization models. 

What Is Quadratic Optimization? 

Quadratic optimization models are useful in scenarios where the objective function is quadratic and the constraints are linear. If some of the variables are integers, then mixed-integer quadratic programming (MIQP) can be used to find a solution. 

The quadratic relationship between the objective function and its variables means that quadratic optimization is a form of nonlinear programming. If the objective function has a linear relationship with the variables, linear programming is more appropriate for the problem. In addition, the constraints (i.e., conditions or limitations that the solution cannot violate) imposed on basic quadratic programming models are linear. More complex quadratic programming (e.g., mixed-integer quadratically constrained programming) can have nonlinear constraints. 

Formulating Quadratic Optimization Models 

Standard quadratic programming models are those with continuous variables and linear constraints. The basic standard formulation looks like this:  

𝑚𝑖𝑛 𝑥 𝑇𝑄 𝑥 + 𝑝 𝑇𝑥 

𝑠.𝑡. 𝐴𝑥 = 𝑏 

𝑥 ≥ 0 

When Q is positive semi-definite, the model is convex. In this scenario, the local optimum is also the global optimum. This is not the case in non-convex models, which have various local optima in addition to a global optimum. The process of finding the optimal solution must be tailored based on the model’s convexity or lack thereof. 

In convex problems, the objective function is convex (e.g., Q is positive semi-definite), and the feasible region is convex—meaning any two feasible points can be connected by a line segment that remains within the region. 

Solving Quadratic Optimization Problems 

There are a number of approaches that can be used to identify the optimal solution in the feasible region. These methods include: 

• Interior-Point Methods (IPMs): IPMs are used to solve convex optimization problems (both linear and nonlinear). The solver starts by identifying a potentially optimal solution. While the simplex method traces the outline of the feasible region (comparing corners with their neighboring vertices until the algorithm identifies the optimal vertex), IPMs examine the interior of the feasible region. This makes it especially useful for nonlinear programs, as nonlinear solutions can be anywhere in the feasible region. 

• Active Set Methods: With the active set method, the optimization solver uses the various active constraints (selected from a set of inequality constraints) to narrow down the feasible area. Like the simplex method and IPMs, the active set method starts with a potentially feasible solution and iterates until the algorithm identifies a potentially optimal outcome. Then, the team can check to ensure the outcome complies with all of the constraints in the problem. 

• Gradient-Based Methods: Using the gradient-based method, the optimization team can investigate how the slope of the feasible region changes as the algorithm explores solutions. The algorithm starts at a potentially optimal solution and follows the slope in the appropriate direction until it identifies the optimal (i.e., maximum or minimum) outcome. To reduce the risk of arriving at a locally optimal (rather than globally optimal) solution, the algorithm runs many times with many different starting points to converge on the likely solution. 

Common Use Cases & Applications  

Quadratic optimization can be applied to numerous business problems. These include: 

• Portfolio Optimization: Portfolio optimization often involves minimizing risk for clients, represented by the portfolio variance-a quadratic function of the asset weights. Financial firm swissQuant leveraged Gurobi to develop a MIQP that built tailored portfolios based on risk profiles.” Financial firm swissQuant leveraged Gurboi to develop a mixed-integer quadratic program that quickly developed tailored investment models for individual clients based on their risk profiles. 

• Energy Optimization: Since standard quadratic functions are especially adept at minimization, companies pursuing energy efficiency use quadratic programming to minimize energy use while navigating variable energy prices and storage capacity. 

• Logistics: Logistics problems can involve quadratic objectives—for example, when cost functions include squared distances or penalties. Quadratic programming is used in planning routes, allocating warehouse space, and minimizing such nonlinear costs. 

How Can Gurobi Help Solve My Quadratic Optimization Problems? 

With Gurobi, you can access our expert support team, who can support you in developing and finetuning your models. To learn more, request a free evaluation today.