An Almost Feasible Sequential Linear Programming Algorithm

2024/01/24 by David Kiessling, Charlie Vanaret, Kiessling, David +7 · 1 citation
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Formal Methods in Verification #Optimization and Control (math.OC) #Robotic Path Planning Algorithms

paper · pdf · doi:10.48550/arxiv.2401.13840

openalex publication_date 2024/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper proposes an almost feasible Sequential Linear Programming (afSLP) algorithm. In the first part, the practical limitations of previously proposed Feasible Sequential Linear Programming (FSLP) methods are discussed along with illustrative examples. Then, we present a generalization of FSLP based on a tolerance-tube method that addresses the shortcomings of FSLP. The proposed algorithm afSLP consists of two phases. Phase I starts from random infeasible points and iterates towards a relaxation of the feasible set. Once the tolerance-tube around the feasible set is reached, phase II is started and all future iterates are kept within the tolerance-tube. The novel method includes enhancements to the originally proposed tolerance-tube method that are necessary for global convergence. afSLP is shown to outperform FSLP and the state-of-the-art solver IPOPT on a SCARA robot optimization problem.

Cited by

• Learn to Relax with Large Language Models: Solving Nonlinear Combinatorial Optimization Problems via Bidirectional Coevolution

Related

• The Colourful Feasibility Problem
• Continuation Method with the Trusty Time-stepping Scheme for Linearly Constrained Optimization with Noisy Data
• A Novel Algorithm for Linear Programming
• Continuous-Time Systems for Solving 0-1 Integer Linear Programming Feasibility Problems
• Integer Programming as a General Solution Methodology for Path-Based Optimization in Robotics: Principles, Best Practices, and Applications