A penalty-interior point method combined with MADS for equality and inequality constrained optimization

Charles Audet, Andrea Brilli, Youssef Diouane, Sébastien Le Digabel, Everton J. Silva, Christophe Tribes · 2026

Read A penalty-interior point method combined with MADS for equality and inequality constrained optimization by Charles Audet, Andrea Brilli, Youssef Diouane, Sébastien Le Digabel, Everton J. Silva, Christophe Tribes (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-20811.txt.

Introduction

Charles Audet and five co-authors build a solver for hard optimization problems with constraints. Their 2026 paper presents MADS-PIP. The base method, MADS, is mesh adaptive direct search, a tool for nonsmooth blackbox problems. A blackbox problem gives answers only through trials, with no formula to inspect. Constraints can demand equality or set bounds that must hold.

The new framework folds a penalty-interior point strategy into MADS. The constraints are split into two subsets. One subset is handled with a logarithmic barrier on the total violation. The other is handled with an exterior quadratic penalty. Blending the two styles aims for speed and reliability at once. The solver serves engineers who must optimize systems they can only test, not solve on paper.

Catalog record

CREATORCharles Audet, Andrea Brilli, Youssef Diouane, Sébastien Le Digabel, Everton J. Silva, Christophe Tribes
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-20811

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A penalty-interior point method combined with MADS for equality and inequality constrained optimization Charles Audet, Andrea Brilli, Youssef Diouane, Sébastien Le Digabel, Everton J. Silva, Christophe Tribes Abstract This work introduces MADS-PIP, an efficient framework that integrates a penalty-interior point strategy into the mesh adaptive direct search (MADS) algorithm for solving nonsmooth blackbox optimization problems with general inequality and equality constraints. Inequality constraints are partitioned into two subsets: one treated via a logarithmic barrier applied to an aggregated interior constraint violation, and the other handled through an exterior quadratic penalty. All equality constraints are treated by the exterior penalty. A merit function defines a sequence of unconstrained subproblems, which are solved approximately using MADS, while a carefully designed update rule drives the penalty-barrier parameter to zero. In the nonsmooth setting, we establish convergence results ensuring feasibility for general constraints as well as Clarke stationarity for inequality-constrained problems. Computational experiments on both analytical test sets and challenging blackbox problems demonstrate that the proposed MADS-PIP algorithm is competitive with, and often outperforms, MADS with the progressive barrier strategy, particularly in the presence of equality constraints. Keywords: Blackbox constrained optimization; Mesh adaptive direct search; Penalty-interior point method. AMS Classification: 68Q25, 68R10, 68U05 1 Introduction The presence of general constraints in optimization introduces challenges. For nonlinear or nonconvex constraints, classical optimization methods, such as gradient-based ones, may be inefficient [ 17 ] . The task is even harder when derivatives are unavailable. Algorithms that do not rely on derivative information are particularly relevant for problems where the objective and/or the constraint functions are defined by complex simulations, for which derivatives are not computable, unreliable, or simply nonexistent. Such nonsmooth problems are addressed by Derivative-Free Optimization (DFO) algorithms [ 11 , 25 ] . This work targets constrained optimization problems of the form \displaystyle\displaystyle\min_{{\bf{x}}\in\mathbb{R}^{n}}\quad \displaystyle f({\bf{x}}) s.t. \displaystyle g_{\ell}({\bf{x}})\leq 0, \displaystyle\ell=1,2,\dots,m ( P_{0} ) \displaystyle h_{j}({\bf{x}})=0, \displaystyle j=1,2,\dots,p where f:\mathbb{R}^{n}\to\overline{\mathbb{R}} , g_{\ell}:\mathbb{R}^{n}\to\overline{\mathbb{R}} for all \ell=1,2,\ldots,m , h_{j}:\mathbb{R}^{n}\to\overline{\mathbb{R}} for all j=1,2,\ldots,p , and \overline{\mathbb{R}}=\mathbb{R}\cup\{+\infty\} . 1.1 Constraint handling in DFO Over the years, several methods have been proposed to handle constraints, most of them employing penalty, filter, or barrier approaches [ 45 ] . In the context of direct search methods, early contributions to smooth constrained problems were proposed by Lewis and Torczon for bound-constrained [ 34 ] and linearly constrained [ 35 ] problems. They proposed an augmented Lagrangian approach [ 36 ] for general constraints, using a sequence of bound-constrained minimizations. Audet and Dennis [ 5 ] propose a filter approach [ 31 ] that accepts a trial point which improves either the objective function value or the constraint violation measure. Mesh Adaptive Direct Search (MADS) [ 6 ] is a generalization of pattern search methods that handles nonsmooth constraints using an extreme barrier approach that only evaluates feasible points. To address the limitations of the extreme barrier, a progressive barrier approach was proposed in [ 8 ] . Similar to a filter approach, the progressive barrier method sets a threshold on the constraint violation accepted, progressively decreasing its value as the iterations progress. The approach was later extended to handle linear equality constraints [ 12 ] , by reformulating the optimization problem, potentially reducing the number of original variables. Merit-function techniques have been investigated within the derivative-free literature; for instance, [ 32 ] proposes a merit-based strategy for DFO methods, while [ 29 ] extends a class of evolution strategies to handle quantifiable relaxable constraints [ 37 ] through a merit function combined with a restoration procedure, and addresses unrelaxable constraints using either an extreme-barrier or projection approach. Linesearch approaches are directional direct search methods. In this framework, a contribution to smooth bound-constrained problems was proposed by Lucidi and Sciandrione [ 40 ] . Slight modifications of the same approach have been recently proposed in [ 19 ] , inspired by [ 21 ] , proving worst-case complexity bounds and a finite active-set identification property. In [ 39 ] the authors consider inequality constrained problems using a transformation into unconstrained or linearly constrained minimization of a smooth approximation of a nonsmooth exact penalty function. In [ 30 ] an exact penalty approach addressing nonsmooth inequalities is proposed. A sequential penalty approach was proposed in [ 38 ] . It solves the original problem through a sequence of approximate minimizations of a merit function, progressively increasing the penalization of constraint violations. In [ 22 ] , using the same algorithmic framework, a merit function handles inequality constraints with a logarithmic barrier approach and equality constraints by including a penalization term. The latter approach has been recently integrated into direct search (LOG-DS) to address general nonlinear constrained optimization problems [ 20 ] , assuming the continuous differentiability of the functions. The convergence to KKT-stationary points was established for LOG-DS under smooth assumptions. 1.2 Contributions and structure of the paper DFO algorithms, particularly direct search methods, are well known for their ability to handle nonsmooth problems. This work extends the MADS algorithm to equality constrained optimization problems. The constraints are partitioned into two sets. One set is treated by a logarithmic barrier, and the other is handled by an exterior penalty. In the nonsmooth setting, we derive convergence guarantees that lead to feasibility under general constraints and to Clarke stationarity in the case of inequality constraints. Computational results obtained on both analytical benchmarks and realistic blackbox problems show that the proposed method is competitive with, and often outperforms, the MADS progressive barrier approach [ 8 ] , especially in the presence of equality constraints. Section 2 describes the proposed algorithm, with emphasis on the partition of inequality constraints. Section 3 develops the convergence analysis, addressing both feasibility for general constraints and stationarity for inequality constraints. Section 4 describes practical implementation aspects, and Section 5 reports computational experiments on analytical test problems and difficult blackbox problems. Section 6 concludes with final remarks. 2 A penalty-interior point method for MADS This work proposes to solve ( P 0 ) by means of a merit function approach that transforms the constrained problem into a sequence of unconstrained ones. 2.1 Partitioning the constraints The approach partitions the inequality constraints indices into two sets, namely \mathcal{G}^{\tt int} and \mathcal{G}^{\tt ext} , so that \mathcal{G}^{\tt int}\cap\mathcal{G}^{\tt ext}=\emptyset and \mathcal{G}^{\tt int}\cup\mathcal{G}^{\tt ext}=\{1,2,\dots,m\} . This partition depends on the starting point, and further details are provided in Section 4 . The set of feasible points for ( P 0 ) is the intersection of \displaystyle\Omega^{\tt int} \displaystyle= \displaystyle\{{\bf{x}}\in\mathbb{R}^{n}\mid\ g_{\ell}({\bf{x}})\leq 0,\ \forall\ell\in\mathcal{G}^{\tt int}\} \displaystyle\mbox{and }\quad\Omega^{\tt ext} \displaystyle= \displaystyle\left\{{\bf{x}}\in\mathbb{R}^{n}\mid\ g_{\ell}({\bf{x}})\leq 0,\ \forall\ell\in\mathcal{G}^{\tt ext};\ h_{j}({\bf{x}})=0,\ \forall j=1,2,\dots,p\right\}. Therefore, a point {\bf{x}}\in\mathbb{R}^{n} is feasible for ( P 0 ) if and only if {\bf{x}}\in\Omega\equiv\Omega^{\tt int}\cap\Omega^{\tt ext} . We briefly recall the logarithmic-barrier/exterior-penalty strategy used in [ 20 ] . The approach analyzed in [ 22 ] employs a merit function that treats the inequality constraints via a logarithmic barrier and the equality constraints via an exterior penalty term. A well-known drawback of a pure barrier strategy is the requirement of a strictly feasible starting point; this is addressed in [ 20 ] by combining the logarithmic term with an exterior penalty that handles the constraints violated by the initial point. Another practical issue is that the use of

Read the complete text