Revisiting a crazy global NLP problem

2026-03-17 · Source: Yet Another Math Programming Consultant · Field: Science & Research — Mathematics & Computational Sciences, Engineering & Applied Sciences · Depth: Intermediate, extended

Summary

This analysis investigates the problem of finding the smallest encompassing triangle for a given set of $n$ 2D points, focusing on the computational challenges of non-convex quadratic optimization models. The problem is formulated using the determinant formula for triangle area and barycentric coordinates to enforce point inclusion. Initial attempts to minimize area, using both variable splitting and bounding methods, failed to prove optimality for even a small $n=3$ case within 1,000 seconds, with solvers like SCIP, Baron, Gurobi, and Antigone struggling to move the lower bound from 0. The article then explores alternative definitions for "smallest," demonstrating that minimizing circumference or the sum of squares of edge lengths significantly improves solver performance, achieving optimal or near-optimal solutions for 50 random points within 117-133 seconds, compared to the 1,000-second time limit hit by area-minimizing models.

Key takeaway

For a Research Scientist or Data Scientist working with geometric optimization problems, if your non-convex model struggles with optimality proofs or time limits, you should experiment with alternative objective functions. Redefining "smallest" from area to circumference or sum of squares can transform an intractable problem into one solvable within practical timeframes, even if the resulting triangles are nearly identical.

Key insights

Non-convex quadratic optimization problems can be intractable even for small instances.

Principles

• Problem redefinition can dramatically alter solver performance.
• Non-convexity often leads to poor lower bound progression in solvers.

Method

The smallest encompassing triangle problem can be modeled by minimizing area, circumference, or sum of squared edge lengths, with point inclusion enforced via barycentric coordinates.

In practice

• Consider alternative objective functions for intractable optimization problems.
• Pre-process data to include only convex hull points.

Topics

• Smallest Encompassing Triangle
• Non-convex Optimization
• Global Solvers
• Barycentric Coordinates
• Optimization Objective Functions

Best for: Research Scientist, Software Engineer, Data Scientist

Related on AIssential

• Largest empty shapes — Finding largest empty shapes in point sets requires diverse optimization models depending on the shape.
• Subject to: Aharon Ben-Tal — Ronnie Ben-Tal's career exemplifies the profound impact of theoretical optimization on real-world engineering and medical challenges.
• NVIDIA and OpenAI Are Scaling an AI That Cannot Subtract — Current AI's mathematical foundations are flawed, leading to basic arithmetic failures despite massive investment.
• Separating Geometry from Probability in the Analysis of Generalization — Generalization can be analyzed deterministically via sensitivity of optimization solutions to data perturbations.
• Minimum enclosing circle/ellipse 2 — The smallest enclosing circle for a set of circles can be found using NLP or SOCP models.
• The New Geometry of Intelligence #ai — Neural networks under capacity pressure form a "crystalline latent structure" using "tight frames" for efficient feature representation.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Yet Another Math Programming Consultant.