A Gentle Introduction to Nonlinear Constrained Optimization with Piecewise Linear Approximations

2026-03-21 · Source: Towards Data Science · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Advanced, long

Summary

This article details a procedure for solving separable nonlinear programming (NLP) problems by transforming them into linear programming (LP) or mixed-integer programming (MIP) models using piecewise linear (PWL) approximations. It begins by defining constrained optimization, linear programming, and nonlinear programming, highlighting that NLPs are generally harder to solve. The core method involves approximating nonlinear objective functions with PWL functions, which can be handled by standard LP/MIP solvers. A portfolio selection example demonstrates how a non-separable problem can be reformulated into a separable one and then approximated. The article explains the role of Special Ordered Sets of Type 2 (SOS type 2) constraints, particularly with Gurobipy, to ensure approximation accuracy by enforcing adjacency conditions for breakpoints. It also discusses the theoretical underpinnings of convex and concave functions, explaining how their properties influence the accuracy and feasibility of PWL approximations for both objective functions and constraints. A Python implementation using Gurobipy is provided, showing how to set up and solve such a problem, with results demonstrating improved accuracy as the number of breakpoints increases from 4 to 16, yielding an optimal objective value of 46.33.

Key takeaway

For Machine Learning Engineers or Data Scientists working with optimization problems, understanding how to linearize separable nonlinear programs is crucial. By applying piecewise linear approximations and Special Ordered Sets of Type 2 constraints, you can leverage efficient LP/MIP solvers like Gurobipy to tackle complex NLPs, potentially avoiding dedicated nonlinear solvers. This approach allows for scalable solutions, though careful consideration of breakpoint density and function convexity/concavity is necessary to manage approximation error and ensure feasible solutions.

Key insights

Linearizing separable nonlinear programs via PWL approximations and SOS type 2 constraints enables efficient solution with LP/MIP solvers.

Principles

• Minimizing $f(x)$ is equivalent to maximizing $-f(x)$.
• Concave objective functions allow omitting SOS type 2 constraints.
• Convex constraints ensure feasible region containment for PWL approximations.

Method

Reformulate non-separable NLPs into separable form, approximate nonlinear terms with piecewise linear functions using breakpoints, and enforce adjacency with SOS type 2 constraints for LP/MIP solvers like Gurobipy.

In practice

• Use Gurobipy for SOS type 2 constraints.
• Increase breakpoints for higher approximation accuracy.
• Evaluate original nonlinear objective at returned solution.

Topics

• Nonlinear Programming
• Piecewise Linear Approximation
• Special Ordered Sets
• Convex Optimization
• Gurobipy

Code references

• caio-biondi/sos

Best for: Machine Learning Engineer, Data Scientist, Research Scientist

Related on AIssential

• A Solver-Free Training Method for Predict-then-Optimize — A measure transformation principle enables solver-free training for predict-then-optimize models, drastically cutting training time while maintaining decision quality.
• [Re-Upload] What is Linear Programming (LP)? (in 2 minutes) ***No Background Music*** — Linear Programming optimizes linear objectives under linear constraints, forming a polyhedral feasible set.
• Efficient Federated RLHF via Zeroth-Order Policy Optimization — Par-S^2ZPO offers efficient federated RLHF for edge devices using zeroth-order optimization and binary perturbation.
• Benders’ Decomposition 101: How to Crack Open a Stochastic Program That’s Too Big to Swallow Whole — Benders' decomposition tackles large stochastic programs by separating first-stage decisions from scenario-specific recourse using iterative cuts.
• Transforming Constraint Programs to Input for Local Search — Automatically generating local search neighborhoods from constraint specifications by linking symmetry properties reduces human intervention in combinatorial optimization.
• Convex hull models — Convex hull computation can be framed as an efficient optimization problem, potentially a linear program.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Towards Data Science.