Unleashing the Power of Non-Linear Programming: A Real-World Example

6 min readJul 20, 2023

A step by step introduction to formulating and solving a non-linear optimization problem in Python.

Introduction

In the realm of optimization, linear programming often takes the spotlight. However, there is a powerful counterpart that tackles more complex problems: non-linear programming. In this article, we’ll dive into the world of non-linear programming and its practical applications. Through a captivating real-world example, we’ll explore how non-linear programming techniques can unlock optimal solutions in the face of non-linear constraints.

The main objective of this article is to introduce the reader to optimization problems that are non-linear in nature and the introduce tools to solve them both conceptually and through code.

Prerequisites

The given prerequisites are good to have and not necessary.

Basic coding knowledge in Python.
Basic understanding on how to formulate a linear programming programming, objective function, constraints and decision variables.

Understanding Non-Linear Programming

Non-linear programming encompasses the optimization of non-linear functions, allowing us to tackle problems with intricate relationships and dependencies. While linear programming assumes linearity, non-linear programming embraces the complexities of reality. From finance to engineering, non-linear programming finds its footing in various domains where decision-making requires a nuanced approach.

Example : Fuel Efficiency Optimization

Imagine a car manufacturer aiming to optimize fuel efficiency in their vehicle design. The objective is clear: maximize fuel economy while accounting for non-linear factors such as aerodynamics, tire friction, and engine performance. This scenario exemplifies the need for non-linear programming, as the relationship between variables and the objective function is not simple or linear.

Non-Linear Programming Techniques

To solve such complex optimization problems, non-linear programming offers a range of techniques. Let’s explore three commonly used techniques:

1. Gradient Descent:

Gradient descent is an iterative optimization method that adjusts the design variables based on the gradient (partial derivatives) of the objective function. It seeks to minimize the objective function by moving in the direction of steepest descent. In our fuel efficiency optimization example, gradient descent allows us to fine-tune the design variables such as engine power, vehicle weight, and aerodynamic coefficient.

Gradient Descent climbing down the function until it reaches the absolute minimum.

2. Newton’s Method:

Newton’s method is another iterative technique used in non-linear optimization. It utilizes second-order derivatives (Hessian matrix) in addition to the gradient to guide the optimization process. This method often converges faster than gradient descent but requires additional computation. Newton’s method can provide more accurate results, although it might encounter challenges with complex non-linear functions or ill-conditioned problems.

Relationship between Gradient descent and Newton’s method

3. Genetic Algorithms:

Genetic algorithms draw inspiration from the principles of natural selection and evolution. They involve maintaining a population of potential solutions (individuals) and evolving them over generations through operations such as selection, crossover, and mutation. Genetic algorithms are particularly useful when dealing with optimization problems that have multiple optimal solutions or lack clear mathematical formulations. They provide a stochastic and exploratory approach to finding near-optimal solutions.

Python Explanation and Code for the Example

To illustrate the fuel efficiency optimization example using Python, we’ll leverage the SciPy library, which offers powerful optimization tools. Specifically, we’ll use the minimize function from the scipy.optimize module for gradient descent and Newton’s method, and the differential_evolution function for genetic algorithms. Each of these libraries have a ton of documentation and details around the function parameters available here.

We’ll be using the same example around fuel efficiency optimization shared above.

Here’s the step-by-step code walkthrough:

Import necessary libraries

Numpy is used to work with matrices and matrix operations for data handling and preparation.

Scipy is needed for the non-linear solvers for the techniques that we will be deploying.

# Import necessary libraries
import numpy as np
from scipy.optimize import minimize, differential_evolution

Define objective function

Our objective function is to minimize the fuel usage.

# Define the objective function
def objective(x):
    power, weight, coefficient = x
    # Calculate fuel efficiency (objective function)
    mpg = 1000 / (power * weight * coefficient)  # Simplified example calculation
    return -mpg  # Negative sign for maximization

Define non-linear constraints

The key constraints are the following and are defined in the code below:-

Power*Weight*Coefficient ≤100
Power + Weight ≤ 2000
Coefficient ≤ 0.5

# Define the non-linear constraints
def constraints(x):
    power, weight, coefficient = x
    # Define the non-linear constraints and return the constraint values as an array
    constraint1 = power * weight * coefficient - 100  # Example constraint 1
    constraint2 = power + weight - 2000  # Example constraint 2
    constraint3 = coefficient - 0.5  # Example constraint 3
    return [constraint1, constraint2, constraint3]

Define the initial values

For a non-linear problem, we usually assign initial values which are taken as the starting point and from where the key decision variables are adjusted towards the optimal solution.

# Define the initial design variables
x0 = [200, 1500, 0.3]  # Initial values for engine power, vehicle weight, and aerodynamic coefficient

Non-linear optimization algorithms

Below we use gradient descent, newton’s method and genetic algorithms and define the non-linear optimization problem using the minimize function by adding the objective function, initial design values, constraints and other key parameters:


# Gradient Descent Optimization
gd_result = minimize(objective, x0, constraints=({'type': 'ineq', 'fun': constraints}))

# Newton's Method Optimization
newton_result = minimize(objective, x0, method='Newton-CG', constraints=({'type': 'ineq', 'fun': constraints}))

# Genetic Algorithms Optimization
bounds = [(100, 500), (1000, 2000), (0.1, 0.9)]  # Bounds for design variables
ga_result = differential_evolution(objective, bounds, constraints=[{'type': 'ineq', 'fun': constraints}])

Output the optimal solution

Below we output the optimal value for the fuel efficiency and the values of each of the decision variable values that determine the ideal fuel efficiency:

# Extract the optimized design variables and fuel efficiency for each technique
gd_optimized_variables = gd_result.x
gd_mpg = 1000 / (gd_optimized_variables[0] * gd_optimized_variables[1] * gd_optimized_variables[2])

newton_optimized_variables = newton_result.x
newton_mpg = 1000 / (newton_optimized_variables[0] * newton_optimized_variables[1] * newton_optimized_variables[2])

ga_optimized_variables = ga_result.x
ga_mpg = 1000 / (ga_optimized_variables[0] * ga_optimized_variables[1] * ga_optimized_variables[2])

# Print the optimized results and fuel efficiency for each technique
print("Gradient Descent Optimization Results:")
print(f"Engine Power: {gd_optimized_variables[0]} horsepower")
print(f"Vehicle Weight: {gd_optimized_variables[1]} kilograms")
print(f"Aerodynamic Coefficient: {gd_optimized_variables[2]}")
print(f"Final Fuel Efficiency (MPG): {gd_mpg}\n")

print("Newton's Method Optimization Results:")
print(f"Engine Power: {newton_optimized_variables[0]} horsepower")
print(f"Vehicle Weight: {newton_optimized_variables[1]} kilograms")
print(f"Aerodynamic Coefficient: {newton_optimized_variables[2]}")
print(f"Final Fuel Efficiency (MPG): {newton_mpg}\n")

print("Genetic Algorithms Optimization Results:")
print(f"Engine Power: {ga_optimized_variables[0]} horsepower")
print(f"Vehicle Weight: {ga_optimized_variables[1]} kilograms")
print(f"Aerodynamic Coefficient: {ga_optimized_variables[2]}")
print(f"Final Fuel Efficiency (MPG): {ga_mpg}")

By running the entire code above, we can obtain the optimized design variables and the final fuel efficiency for each optimization technique. The results will demonstrate how different techniques can yield slightly different optimal solutions.

Summary

Through the application of non-linear programming techniques, we successfully optimized the fuel efficiency of our car design. Gradient descent, Newton’s method, and genetic algorithms each offer unique approaches to tackling non-linear optimization problems. By embracing these techniques, we can navigate the complexities of real-world scenarios and unlock optimal solutions. The fuel efficiency optimization example serves as a testament to the power and practicality of non-linear programming in diverse fields.

With this, we come to the end of this article. I hope you find this useful!