# Cutting planes for signomial programming

Liding Xu LIX CNRS, École Polytechnique, Institut Polytechnique de Paris,
Palaiseau, 91128, France. E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Claudia D’Ambrosio11footnotemark: 1 Leo
Liberti11footnotemark: 1 Sonia Haddad-Vanier11footnotemark: 1 Université Paris
1 Panthéon-Sorbonne, Paris, 75005, France.

###### Abstract

Cutting planes are of crucial importance when solving nonconvex nonlinear
programs to global optimality, for example using the spatial branch-and-bound
algorithms. In this paper, we discuss the generation of cutting planes for
signomial programming. Many global optimization algorithms lift signomial
programs into an extended formulation such that these algorithms can construct
relaxations of the signomial program by outer approximations of the lifted set
encoding nonconvex signomial term sets, i.e., hypographs, or epigraphs of
signomial terms. We show that any signomial term set can be transformed into
the subset of the difference of two concave power functions, from which we
derive two kinds of valid linear inequalities. Intersection cuts are
constructed using signomial term-free sets which do not contain any point of
the signomial term set in their interior. We show that these signomial term-
free sets are maximal in the nonnegative orthant, and use them to derive
intersection sets. We then convexify a concave power function in the
reformulation of the signomial term set, resulting in a convex set containing
the signomial term set. This convex outer approximation is constructed in an
extended space, and we separate a class of valid linear inequalities by
projection from this approximation. We implement the valid inequalities in a
global optimization solver and test them on MINLPLib instances. Our results
show that both types of valid inequalities provide comparable reductions in
running time, number of search nodes, and duality gap.

_Key words:_ global optimization, signomial programming, extended formulation,
cutting plane, intersection cut, convex relaxation

##  1 Introduction

General nonconvex nonlinear programming (NLP) problems typically admit the
following formulation:

$\min_{x\in\mathbb{R}^{n}}\;c\cdot x\quad\operatorname{s.t.}\quad Ax+Bg(x)\leq
d,$ (1)

where $c\in\mathbb{R}^{n},A\in\mathbb{R}^{m\times n},B\in\mathbb{R}^{m\times
k},g:\mathbb{R}^{n}\to\mathbb{R}^{k},d\in\mathbb{R}^{m}$.

The mapping $g(x)$ represents a vector $(g_{1}(x),\dots,g_{k}(x))$ of
nonconvex functions on $x$, and we denote $g_{i}$ as their _terms_. Note that
the objective function is supposed to be linear, w.l.o.g., since we can always
reformulate a problem with a nonlinear objective function as the problem (1)
above (epigraphic reformulation).

General-purpose global optimization solvers, such as BARON [65], Couenne [10],
and SCIP [11], are capable of solving the problem (1) within an
$\epsilon$-global optimality. They achieve this by employing the spatial
branch-and-bound (sBB) algorithm, which explores the feasible region of (1)
implicitly, but systematically. The sBB algorithm effectively prunes out
unpromising search regions by comparing the cost of the best feasible solution
found with the cost bounds associated with those regions. These cost bounds
can be computed by solving convex relaxations of (1).

The backend convex relaxation algorithms implemented in many general-purpose
solvers, including BARON, Couenne, and SCIP, are linear programming
relaxations. These solvers take advantage of the separability introduced in
the rows of $Ax+Bg(x)$, allowing them to relax and linearize nonlinear terms
$g_{i}$ individually. In the solvers’ data structures, the problem (1) is
transformed into an extended formulation:

$\min_{(x,y)\in\mathbb{R}^{n+k}}\;c\cdot x\quad\operatorname{s.t.}\quad
Ax+By\leq d\;\land\;y=g(x).$ (2)

All the nonlinear terms are grouped within the nonconvex constraints $y=g(x)$.
These constraints give rise to a nonconvex _lifted set_ defined as:

${\mathcal{S}}_{\mathrm{lift}}\coloneqq\\{(x,y)\in\mathbb{R}^{n+k}:y=g(x)\\}.$
(3)

The relaxation algorithms used by these solvers are based on factorable
programming [35, 47]: This approach treats the multivariate nonlinear terms
$g_{i}$ as composite functions. These algorithms typically factorize each
$g_{i}$ into sums and products of a collection of univariate functions. If
convex and concave relaxations of those univariate functions are available,
these algorithms can linearize these relaxations, and yield a linear
relaxation for Eq. (1). Common lists of such univariate functions, that are
usually available to all sBB solvers, include $t^{a}$ (for $a\in\mathbb{N}$),
$\frac{1}{t}$, $\log{t}$, $\exp{t}$. Some solvers also offer a choice of
trigonometric functions, e.g. Couenne.

Most sBB solvers can handle _signomial term_ $\psi_{\alpha}(x)\coloneqq
x^{\alpha}=\prod_{j\in[n]}x_{j}^{\alpha_{j}}$, where the exponent vector
$\alpha$ is in $\mathbb{R}^{n}$, but in a way that yields poor relaxations
(more about this below). In this paper, we provide a deeper treatment of the
signomial term w.r.t. convexification and linearization within an sBB
algorithm. The SCIP solver can handle signomial terms, but, as of version 8.0,
the treatment was limited to recognizing convexity and concavity. The
technical report [11] explicitly states that the techniques proposed in this
paper are going to be integrated into SCIP.

When all the terms in $g$ are signomial terms, the problem (1) falls under the
category of signomial programming (SP). In this scenario, we refer to (1) as
the _natural formulation_ of SP. The left-hand sides of the constraints in
this formulation are referred to as _signomial functions_. The lifted set
${\mathcal{S}}_{\mathrm{lift}}$ in the extended formulation (2) is called a
_signomial lift_.

Since negative entries may present in the exponent vector $\alpha$, in
general, variables of SP are assumed to be positive. The point of restriction
on SP over positive variables is simply to make the theoretical treatment more
readable and streamlined. We remark that the techniques in this paper can also
treat signomial terms in general mixed-integer NLP problems.

In the case of SP, LP relaxations can be derived from polyhedral outer
approximations of the signomial lift in its extended formulation. A typical
relaxation algorithm for SP involves factorizing the signomial term
$\psi_{\alpha}(x)$ into the product of $n$ univariate signomial terms
$x_{i}^{\alpha_{i}}$. After the factorization, the algorithm proceeds to
convexify and linearize the intermediate multilinear term and univariate
functions. However, this factorial programming approach can lead to weak LP
relaxation and introduce additional auxiliary variables that represent
intermediate functions. These problems have already been discussed in the
context of pure multilinear terms [14, 21, 63].

We propose two cutting plane-based relaxation algorithms for SP. In contrast
to the conventional factorable programming approach, our method uses a novel
reformulation of the signomial lift. We transform each nonlinear equality
constraint $y_{i}=g_{i}(x)$ in (3) to an equivalent constraint
$\psi_{\beta}(u)-\psi_{\gamma}(v)=0$, where $\beta>0,\gamma>0$,
$\max({\lVert\beta\rVert}_{1},{\lVert\gamma\rVert}_{1})=1$, $u,v$ are sub-
vectors partitioned from $(x,y)$, and $\psi_{\beta},\psi_{\gamma}$ are concave
functions. We consider approximating the following set

${\mathcal{S}}_{\mathrm{st}}\coloneqq\\{(u,v)\in\mathbb{R}_{+}^{h+\ell}:\,\psi_{\beta}(u)-\psi_{\gamma}(v)\leq
0\\}.$ (4)

Our first cutting plane algorithm is based on the intersection cut paradigm
[19]. As shown in Sec. 2, one can approximate a nonconvex set ${\mathcal{S}}$
using its polyhedral outer approximation. This requires the construction of
${\mathcal{S}}$-free sets, i.e., closed convex sets containing none of the
interiors of ${\mathcal{S}}$. The main insight about ${\mathcal{S}}$-free sets
for a nonconvex set ${\mathcal{S}}$ is that they provide an explicit and
useful description of the convex parts of the complement of ${\mathcal{S}}$.
In Sec. 3 we extend several general results from the literature on maximal
${\mathcal{S}}$-free sets. In Sec. 4 we give the transformation procedure
leading to ${\mathcal{S}}_{\mathrm{st}}$ and construct
${\mathcal{S}}_{\mathrm{st}}$-free sets from the transformation. We show that
these sets are also signomial-lift-free and maximal in the nonnegative
orthant. We also discuss the separation of intersection cuts.

To ensure convergence of the sBB algorithm, a common assumption for SP is that
all variables are bounded. Our second cutting plane algorithm aims to
approximate ${\mathcal{S}}_{\mathrm{st}}$ within a hypercube. In Sec. 5, we
provide an extended formulation for the convex envelope of the concave
function $\psi_{\beta}$ over the hypercube. This formulation yields a convex
set including ${\mathcal{S}}_{\mathrm{st}}$ (which is a convex outer
approximation of ${\mathcal{S}}_{\mathrm{st}}$), so that we can generate outer
approximation cuts by projection. We prove that $\psi_{\beta}$ is a
supermodular function. For $h=2$ we provide a closed expression for its convex
envelope by exploiting supermodularity, which allows us to remove the
projection step.

For the computational part of this study, we note that signomials are one of
the four main types of nonlinearities found in the mixed-integer NLP library
(MINLPLib) [9, 13]. Our relaxation approach does not require factorization or
the introduction of intermediate functions, so implementing the proposed
cutting planes in the general-purpose solver SCIP is straightforward. In Sec.
6, we perform computational tests with instances from MINLPLib and observe
improvements to SCIP default settings due to the proposed valid inequalities.

###  1.1 Related works

The majority of relaxations for SP are derived from its generalized geometric
programming (GPP) formulation, which is an exponential transformation [25] of
its natural formulation. The exponential transformation replaces positive
variables $x$ by exponentials $\exp(z)$, where $z$ are real variables. The
authors of [46] show that signomial functions in GGP are difference-of-convex
(DC) functions. For the signomial function in each constraint of GGP, they
construct linear underestimators of its concave part; the author of [61]
constructs linear underestimators of the whole function via the mean value
theorem. The author of [68] proposes inner approximations of GGP via the
inequality of arithmetic and geometric means (AM-GM inequality). The authors
of [15, 24, 54] construct non-negativity certificates for signomial functions
via the AM-GM inequality, and propose a hierarchy of convex relaxations for
GGP. Exponential transformations can be combined with other variable
transformations, such as power transformations, and the inverse
transformations can be approximated by piece-wise linear functions, see [38,
43, 44].

The solvers SCIP [11], BARON [65], ANTIGONE [50], and MISO [51] are able to
solve the natural formulation of SP or its extended formulation within a
global $\epsilon$-optimality using the sBB algorithm. More precisely, MISO is
a specialized solver for SP, which uses exponential transformations of some
signomial terms only when necessary. For the following reasons, exponential
transformations can complicate general-purpose solvers. First, in certain NLP
problems, signomial terms may appear only as a subset of the nonlinear terms
of $g(x)$. In such cases, solvers may need to force the inverse transformation
$x_{j}=\ln(z_{j})$, which requires additional processing for convexification
algorithms. Second, when dealing with mixed-integer SP and some variables of
$x$ are integer, exponential transformations cause certain components of $z$
to become discrete but not necessarily integer. As a result, the sBB algorithm
must adjust its branching rules.

While much attention has been paid to the construction of relaxations for GGP,
the literature on relaxations for the extended natural formulation of SP is
relatively limited. The convex relaxations used in the aforementioned solvers
rely mainly on factorial programming [36, 47]. Since exponential
transformations are nonlinear variable transformations, it is impossible to
apply the relaxations developed for the GGP formulation directly to the
natural formulation.

Numerous research efforts have been devoted to improving relaxation techniques
for multilinear terms and univariate/bivariate functions commonly used in
factorizable programming [6]. Multilinear terms over the unit hypercube are
vertex polyhedral and their envelopes over the unit hypercube admits simple
extended formulations [58]. In particular, there are closed forms for the
convex envelopes of bilinear functions [1, 47] and trilinear functions [48,
49] over hypercubes. In [62], the author presents convex envelopes for
multilinear functions (sum of multilinear terms) over the unit hypercube and
specific discrete sets. For a comprehensive analysis of multilinear term
factorization via bilinear terms, we refer to [42, 63]. Additionally, [14]
offers an in-depth examination of quadrilinear function factorization through
bilinear and trilinear terms, while [21] presents a computational study on
extended formulations.

Convexifying univariate/bivariate functions plays an important role in the
field of global optimization. In [37], convex envelopes for monomials with odd
degrees are derived. An approach presented in [41] enables the evaluation of
the convex envelope of a bivariate function over a polytope and separating its
supporting hyperplane by solving low-dimensional convex optimization problems.
The convex optimization problems are further reduced by solving a Karush-Kuhn-
Tucker system [40]. In [39], convex envelopes for bilinear, fractional, and
other bivariate functions over a polytope are constructed using a polyhedral
subdivision technique. Additionally, [55, 64] employ polyhedral subdivision
and lift-project methods to derive explicit forms of convex envelopes for
various nonconvex functions, including a specific subclass of bivariate
signomial terms.

Convexifying high-order multivariate functions is a major challenge, and the
available literature on convex underestimators for trivariate functions is
relatively few. In [31, 32], the authors propose a novel framework for
relaxing composite functions in nonlinear programs. Another approach is to use
the intersection cut paradigm [19] to approximate nonconvex functions. This
paradigm can generate cutting planes to strengthen LP relaxations of NLP
problems. Constructing intersection cuts involves finding an
${\mathcal{S}}$-free set, where ${\mathcal{S}}$ represents a nonconvex set
defined by nonconvex functions. The study of intersection cuts originated in
the context of NLP [67]. Gomory later introduced the concept of corner
polyhedron [30], and intersection cuts were explored in the field of integer
programming [5]. The modern definition of intersection cuts for arbitrary sets
${\mathcal{S}}$ is from [23, 29]. For more comprehensive details, we refer to
[2, 7, 20, 22, 23, 57]. Recent research has revealed ${\mathcal{S}}$-free sets
for various nonconvex sets encountered in structured NLP problems. Examples
include outer product sets [12], sublevel sets of DC functions [59], quadratic
sets [53], and graphs of bilinear terms [28]. Intersection cuts have also been
developed for convex mixed-integer NLP problems [3, 8, 34, 52] and for bilevel
programming [27].

###  1.2 Notation

We follow standard notation in most cases. Let $[n_{1}:n_{2}]$ stand for
$\\{n_{1},\ldots,n_{2}\\}$, and let $[n]$ stand for $[1:n]$. For a vector
$x\in\mathbb{R}^{n}$, $x_{j}$ denotes the $j$-th entry of $x$; given
$J\subseteq[n]$, $x_{J}=(x_{j})_{j\in J}$ denotes the sub-vector formed by
entries indexed by $J$. $\lVert\cdot\rVert_{p}$ denotes the $L_{p}$-norm
($1\leq p\leq+\infty$). For a set $X\subseteq\mathbb{R}^{n}$,
$\operatorname{conv}(X)$, $\operatorname{cl}(X)$, $\operatorname{int}(X)$,
$\operatorname{bd}(X)$, $|X|$, $X^{c}$ denote the convex hull, closure,
interior, boundary, cardinality, and complement of $X$, respectively. For a
function $f$, $\operatorname{dom}(f)$ and $\operatorname{range}(f)$ denote the
domain and range of $f$, respectively; $\operatorname{graph}(f)$ denotes its
graph $\\{(x,t)\in\mathbb{R}^{n+1}:f(x)=t\\}$, $\operatorname{epi}(f)$ denotes
its epigraph $\\{(x,t)\in\mathbb{R}^{n+1}:f(x)\leq t\\}$, and
$\operatorname{hypo}(f)$ denotes its hypograph
$\\{(x,t)\in\mathbb{R}^{n+1}:f(x)\geq t\\}$; if $f$ is differentiable, for a
$\tilde{x}\in\operatorname{dom}(f)$, $\nabla{f}(\tilde{x})$ denotes the
gradient of $f$ at $\tilde{x}$ and

${\Xi^{f}_{\tilde{x}}}(x):=f(\tilde{x})+\nabla
f(\tilde{x})\cdot(x-\tilde{x}).$ (5)

The word linearization involves the replacement of a nonlinear function by its
affine underestimators or overestimators. For example, the affine
underestimators of convex functions $f$ are given as
${\Xi^{f}_{\tilde{x}}}(x)$ for some $\tilde{x}$.

##  2 Preliminaries

In this section we present an overview of ${\mathcal{S}}$-free sets and
intersection cut theory. The process of constructing intersection cuts
involves two fundamental steps [18]: constructing ${\mathcal{S}}$-free sets
and deriving cutting planes from these sets. Since maximal
${\mathcal{S}}$-free sets yield tightest cutting planes, one can include an
optional step to check the maximality of ${\mathcal{S}}$-free sets.

######  Definition 1.

Given a set ${\mathcal{S}}\subsetneq\mathbb{R}^{p}$, a closed set
${\mathcal{C}}$ is (convex) ${\mathcal{S}}$-free if ${\mathcal{C}}$ is convex
and $\operatorname{int}({\mathcal{C}})\cap{\mathcal{S}}=\varnothing$.

Fig. 1 shows an example of an ${\mathcal{S}}$-free set, where we find that
${\mathcal{C}}$ is a convex inner approximation of
$\operatorname{cl}({\mathcal{S}}^{c})$. Thereby, we show how to construct
${\mathcal{S}}$-free sets from a “reverse” representation of some nonconvex
sets. We look at sets involving a particular type of nonconvex function.

######  Definition 2.

A function $f$ is said to be difference-of-concave (DCC), if there exist two
concave functions $f_{1},f_{2}$ such that $f=f_{1}-f_{2}$.

It is easy to show that the negative of a DCC function is also a DCC function,
and any DC function can be converted into a DCC function. We call a nonconvex
set a _DCC set_ , if it admits a _DCC formulation_ , meaning that it can be
represented as the sublevel set of a DCC function. The superlevel set of a DCC
function is a sublevel set of another DDC function (the negative of that
function), so the superlevel set is also a DCC set. By using the _reverse-
linearization technique_ , the following lemma provides a collection of
${\mathcal{S}}$-free sets for DCC sets.

######  Lemma 1.

[59, Prop. 6] Let
${\mathcal{S}}\coloneqq\\{z\in\mathbb{R}^{p}:f_{1}(z)-f_{2}(z)\leq 0\\}$,
where $f_{1},f_{2}$ are concave functions over $\mathbb{R}^{p}$. Then, for any
$\tilde{z}\in\mathbb{R}^{p}$,
${\mathcal{C}}\coloneqq\\{z\in\mathbb{R}^{p}:f_{1}(z)-{\Xi^{f_{2}}_{\tilde{z}}}(z)\geq
0\\}$ is ${\mathcal{S}}$-free. Moreover, if
$\tilde{z}\in\mathbb{R}^{p}\smallsetminus{\mathcal{S}}$,
$\tilde{z}\in\operatorname{int}({\mathcal{C}})$.

The reverse-linearization technique involves reversing the inequality that
defines ${\mathcal{S}}$ and linearizing its convex component $-f_{2}$. The
point $\tilde{z}$ is referred to as the _linearization point_. It is important
to note that, when the shared domain ${\mathcal{G}}$ of $f_{1}$ and $f_{2}$ is
not the entire space $\mathbb{R}^{p}$, the set ${\mathcal{S}}$ needs to be
constrained to the _ground set_ ${\mathcal{G}}$. This restriction ensures the
applicability of the lemma.

(a)

(b)

(c)

Figure 1: An ${\mathcal{S}}$-free set ${\mathcal{C}}$, simplicial cone
${\mathcal{R}}$, and intersection cut.

To construct an intersection cut, an essential requirement is the availability
of a translated simplicial cone ${\mathcal{R}}$ that satisfies two conditions:
(i) ${\mathcal{R}}$ is generated by linearly independent vectors, (ii)
${\mathcal{R}}$ contains ${\mathcal{S}}$, and (iii) the vertex $\tilde{z}$ of
${\mathcal{R}}$ does not belong to ${\mathcal{S}}$. We assume that
${\mathcal{R}}$ admits a hyper-plane representation
$\\{z\in\mathbb{R}^{p}:B(z-\tilde{z})\leq 0\\},$ where
$B\in\mathbb{R}^{p\times p}$ is an invertible matrix. For every $j\in[p]$, let
$r^{j}$ denote the $j$-th column of $-B^{-1}$, then $r^{j}$ turns out to be an
extreme ray of ${\mathcal{R}}$. Thereby, ${\mathcal{R}}$ also admits a ray
representation $\\{z\in\mathbb{R}^{p}:\exists\eta\in\mathbb{R}^{p}_{+}\textup{
}z=\tilde{z}+\sum_{j=1}^{p}\eta_{j}r^{j}\\}.$ For every $j\in[p]$, we define
the step length from $\tilde{z}$ along ray $r_{j}$ to the boundary
$\operatorname{bd}({\mathcal{C}})$ as

$\eta_{j}^{\ast}\coloneqq\sup_{\eta_{j}\in[0,+\infty]}\\{\eta_{j}:\tilde{z}+\eta_{j}r^{j}\in{\mathcal{C}}\\}.$
(6)

Then, an intersection cut admits the form

$\sum_{j=1}^{p}B_{j}(z-\tilde{z})/\eta_{j}^{\ast}\leq-1,$ (7)

where $B_{j}$ is the $j$-th row of $B$. When all step lengths are positive,
the above linear inequality cuts off $\tilde{z}$ from ${\mathcal{S}}$. See for
an example of an intersection cut in Fig. 1.

We can obtain the sets ${\mathcal{C}}$, ${\mathcal{R}}$ and the vertex
$\tilde{z}$ by the following procedure. Suppose that we have an LP relaxation
$\min_{z\in{\mathcal{P}}}c\cdot z$ of an SP problem, where ${\mathcal{P}}$ is
a polyhedral outer approximation of the feasible set of the SP problem. If the
solution to the LP problem turns out to be infeasible for the SP problem, it
means that the solution does not belong to the signomial lift. In such cases,
we can fix $\tilde{z}$ as the solution obtained from LP and let
${\mathcal{C}}$ be the signomial-lift-free
(${\mathcal{S}}_{\mathrm{lift}}$-free) set. Moreover, we can extract the cone
${\mathcal{R}}$ from the optimal LP basis defining $\tilde{z}$, see [18].

One focus of our study is the construction of (maximal) ${\mathcal{S}}$-free
sets. The importance of finding _maximal_ sets follows from the fact that if
we have two ${\mathcal{S}}$-free sets called ${\mathcal{C}}$ and
${\mathcal{C}}^{\ast}$, where ${\mathcal{C}}$ is a subset of
${\mathcal{C}}^{\ast}$, then the intersection cut derived from
${\mathcal{C}}^{\ast}$ dominates the cut derived from ${\mathcal{C}}$ (see
[19, Remark 3.2]). To give a precise characterization, we present a formal
definition of maximal ${\mathcal{S}}$-free sets.

######  Definition 3.

Given a closed convex set ${\mathcal{G}}\subseteq\mathbb{R}^{p}$ such that
${\mathcal{S}}\subsetneq{\mathcal{G}}$, an ${\mathcal{S}}$-free set
${\mathcal{C}}$ is (inclusion-wise) maximal in ${\mathcal{G}}$, if there is no
other ${\mathcal{S}}$-free set ${\mathcal{C}}^{\prime}$ such that
${\mathcal{C}}\cap{\mathcal{G}}\subsetneq{\mathcal{C}}^{\prime}\cap{\mathcal{G}}$.

The above definition provides a generalization of the conventional concept of
maximal ${\mathcal{S}}$-free sets, which is a special case when
${\mathcal{G}}=\mathbb{R}^{p}$. Studying maximality for ${\mathcal{S}}$-free
sets in $\mathbb{R}^{p}$ can be challenging in certain scenarios. However,
Defn. 3 allows us to examine the intersections of ${\mathcal{S}}$-free sets
within the ground set ${\mathcal{G}}$. This constraint is essential for our
analysis, especially considering that all variables in SP are non-negative.

##  3 General results on maximality

In this section, we present two results on the maximality of
${\mathcal{S}}$-free sets arising in general nonconvex NLP problems. The
results are used to construct maximal signomial-lift-free sets in non-negative
orthants.

###  3.1 Lifted sets

We consider the extended formulation (2) of a general NLP problem and focus on
the associated lifted set ${\mathcal{S}}_{\mathrm{lift}}$ in (3). We show a
lifting result on constructing maximal ${\mathcal{S}}_{\mathrm{lift}}$-free
sets.

Let $z\coloneqq(x,y)$ denote the vector variable in the extended formulation
(2), with its index set being $[n+k]$. Consequently, we have $z_{[n]}=x$ and
$z_{[n+1:n+k]}=y$. Consider a closed subset ${\mathcal{X}}$ of the domain
$\bigcap_{i\in[k]}\operatorname{dom}(g_{i})$ for $x$, and let ${\mathcal{Y}}$
be a closed subset of the domain
$\bigtimes_{i\in[k]}\operatorname{range}(g_{i})$ for $y$. The ground set
${\mathcal{G}}$ can, thus, be set as ${\mathcal{X}}\times{\mathcal{Y}}$.
Consequently, the lifted set ${\mathcal{S}}_{\mathrm{lift}}$ in (3) admits the
form $\\{(x,y)\in{\mathcal{G}}:y=g(x)\\}$.

Given that each $g_{i}(x)$ (for $i\in[k]$) may only depend on a subset of
variables indexed by $J_{i}\subseteq[n]$, we can express $g_{i}(x)$ as a lower
order function $g^{\prime}_{i}(x_{J_{i}})$ defined over $\mathbb{R}^{J_{i}}$.
Let $I_{i}\coloneqq J_{i}\cup\\{i+n\\}$. As above, we consider a closed subset
${\mathcal{X}}^{i}$ of $\operatorname{dom}(g^{\prime}_{i})$ and
${\mathcal{Y}}^{i}$ of $\operatorname{range}(g^{\prime}_{i})$. Consequently,
the graph, epigraph, and hypograph of $g^{\prime}_{i}$ reside within sets
${\mathcal{G}}^{i}\coloneqq{\mathcal{X}}^{i}\times{\mathcal{Y}}^{i}$, e.g.,
$\operatorname{epi}(g^{\prime}_{i})=\\{(x_{J_{i}},y_{i})\in{\mathcal{G}}^{i}:g^{\prime}_{i}(x_{J_{i}})\leq
y_{i}\\}$.

We refer to
${\mathcal{X}},{\mathcal{Y}},\\{{\mathcal{X}}^{i},{\mathcal{Y}}^{i}\\}_{i\in[k]}$
as the _underlying sets_ of the lifted set ${\mathcal{S}}_{\mathrm{lift}}$.
The sets are said to be _1d-convex decomposable_ by a collection
$\\{{\mathcal{D}}_{j}\\}_{j\in[n+k]}$ of closed convex sets in $\mathbb{R}$,
if
${\mathcal{X}}=\bigtimes_{j\in[n]}{\mathcal{D}}_{j},{\mathcal{Y}}=\bigtimes_{j\in[n+1:n+k]}{\mathcal{D}}_{j}$,
and, for all $i\in[k]$, ${\mathcal{X}}^{i}=\bigtimes_{j\in
J_{i}}{\mathcal{D}}_{j},{\mathcal{Y}}^{i}={\mathcal{D}}_{n+i}$. This
decomposability condition restricts the domains to Cartesian products of real
lines, intervals, or half rays, thereby excluding complicated domain
structures.

The decomposability condition allows the analysis of sets with fewer
variables. The construction of $\operatorname{epi}(g^{\prime}_{i})$-free sets
and $\operatorname{hypo}(g^{\prime}_{i})$-free sets is in general simpler than
the construction of ${\mathcal{S}}_{\mathrm{lift}}$-free sets. We show that
any maximal $\operatorname{epi}(g^{\prime}_{i})$-free or
$\operatorname{hypo}(g^{\prime}_{i})$-free set can be transformed into a
maximal ${\mathcal{S}}_{\mathrm{lift}}$-free set.

######  Theorem 1.

Suppose the underlying sets of ${\mathcal{S}}_{\mathrm{lift}}$ are 1d-convex
decomposable and $g$ is continuous. For some $i\in[k]$, let ${\mathcal{C}}$ be
a maximal $\operatorname{epi}(g^{\prime}_{i})$-free set or a maximal
$\operatorname{hypo}(g^{\prime}_{i})$-free set in ${\mathcal{G}}^{i}$. Then,
$\bar{{\mathcal{C}}}\coloneqq{\mathcal{C}}\times\mathbb{R}^{I^{c}_{i}}$ is a
maximal ${\mathcal{S}}_{\mathrm{lift}}$-free set in ${\mathcal{G}}$.

See the proof in the appendix. For any $i\in[k]$, we call the operation
${\mathcal{C}}\times\mathbb{R}^{I^{c}_{i}}$ the _orthogonal lifting_ of
${\mathcal{C}}$ with respect to $g_{i}$. A similar lifting result for integer
programming is given by [19, Lemma 4.1]: given
${\mathcal{S}}\coloneqq\mathbb{Z}^{n}\times\mathbb{R}^{h}$, any maximal
lattice-free set (i.e., $\mathbb{Z}^{n}$-free set) can be transformed into a
maximal ${\mathcal{S}}$-free set by orthogonal lifting. Therefore, Thm. 1
serves as the NLP counterpart to this lemma (whose proof is also similar).
This theorem allows us to focus on low-dimensional projections of the lifted
set. We will show in Cor. 1 that the signomial lift satisfies the
prerequisites of Thm. 1. The following example illustrates the application of
Thm. 1.

######  Example 1.

Consider a lifted set ${\mathcal{S}}_{\mathrm{lift}}$ defined as

$\\{(x_{1},x_{2},x_{3},x_{4},y_{1},y_{2},y_{3}):y_{1}=\exp(x_{1}-x_{2}/x_{3})\land
y_{2}=\log(x_{1})\land y_{3}=\sin(x_{1}/x_{4})\\}.$

One can verify that the 1d-convex decomposable condition holds for
${\mathcal{D}}_{1}=\mathbb{R}_{+}$, ${\mathcal{D}}_{j}=\mathbb{R}$ (for
$j\in[2:7]$). Then
${\mathcal{G}}\coloneqq\mathbb{R}^{1}_{+}\times\mathbb{R}^{6}$. We use
$\log(x_{1})$ to construct a ${\mathcal{S}}_{\mathrm{lift}}$-free set. A
maximal ${\mathcal{S}}_{\mathrm{lift}}$-free set can be
$\\{(x_{1},x_{2},x_{3},x_{4},y_{1},y_{2},y_{3})\in{\mathcal{G}}:y_{2}\leq\log(x_{1})\\}$.
Since $\log(x_{1})$ is defined over positive reals, this example gives a
reason to restrict maximality over ${\mathcal{G}}$.

###  3.2 Sufficient conditions on maximality

We provide sufficient conditions for the maximality of ${\mathcal{S}}$-free
sets for two general classes of nonconvex sets ${\mathcal{S}}$. At the
beginning, we give an overview of some basic results of convex analysis. Our
subsequent exposition relies on the use of support functions of convex sets.
The properties of support functions can be summarized as follows.

######  Lemma 2.

[33, Chap. C] For a full-dimensional closed convex set
${\mathcal{C}}\subsetneq\mathbb{R}^{p}$, let
$\sigma_{{\mathcal{C}}}:\mathbb{R}^{p}\to\mathbb{R},\lambda\mapsto\sup_{z\in{\mathcal{C}}}{\lambda}\cdot
z$ be the support function of ${\mathcal{C}}$. Then: (i)
${\mathcal{C}}=\\{z\in\mathbb{R}^{p}:\forall{\lambda}\in\operatorname{dom}(\sigma_{{\mathcal{C}}})\textup{
}{\lambda}\cdot z\leq\sigma_{{\mathcal{C}}}({\lambda})\\}$, (ii)
$\operatorname{int}({\mathcal{C}})=\\{z\in\mathbb{R}^{p}:\forall{\lambda}\in\operatorname{dom}(\sigma_{{\mathcal{C}}})\smallsetminus\\{0\\}\textup{
}{\lambda}\cdot z<\sigma_{{\mathcal{C}}}({\lambda})\\}$, (iii)
$\sigma_{{\mathcal{C}}}(\rho\lambda)=\rho\sigma_{{\mathcal{C}}}(\lambda)$ for
any $\rho>0$. Moreover, for any closed convex set ${\mathcal{C}}^{\prime}$
including ${\mathcal{C}}$,
$\sigma_{{\mathcal{C}}}\leq\sigma_{{\mathcal{C}}^{\prime}}$.

A valid inequality $a\cdot z\leq b$ of ${\mathcal{C}}$ is called a _supported
valid inequality_ , if there exists a _supporting point_
$z^{\prime}\in\operatorname{bd}(C)$ such that $a\cdot z^{\prime}=b$.
Geometrically, a closed convex set is the intersection of half-spaces
associated with supported valid inequalities.

######  Observation 1.

It follows from Lemma 2 that every supported valid inequality of
${\mathcal{C}}$ must admit the form $\lambda\cdot
z\leq\sigma_{{\mathcal{C}}}(\lambda)$ for some
$\lambda\in\operatorname{dom}(\sigma_{{\mathcal{C}}})$, where the supremum
$\sigma_{{\mathcal{C}}}(\lambda)$ is attained at its supporting points.

An inequality of the form $\lambda\cdot z\leq\sigma_{{\mathcal{C}}}(\lambda)$,
for $\lambda\in\operatorname{dom}(\sigma_{{\mathcal{C}}})$, is referred to as
an _exposed valid inequality_ , if there exists an _exposing point_
$z^{\prime}\in\operatorname{bd}(C)$ such that $\lambda\cdot
z=\sigma_{{\mathcal{C}}}(\lambda)$ and, for all
${\lambda^{\prime}}\in\operatorname{dom}(\sigma_{\mathcal{C}})\smallsetminus\\{{\rho\lambda}\\}_{\rho>0}$,
${\lambda^{\prime}}\cdot z^{\prime}<\sigma_{{\mathcal{C}}}(\lambda^{\prime})$.

######  Observation 2.

An exposed valid inequality must be a supported valid inequality. Conversely,
a supported valid inequality is an exposed valid inequality if the manifold
$\operatorname{bd}({\mathcal{C}})$ is smooth at its supporting point. For
example, ${\mathcal{C}}_{1}\coloneqq\\{(x,y)\in\mathbb{R}^{2}:y=x^{2}\\}$ is a
smooth manifold, so any supported valid inequality of ${\mathcal{C}}_{1}$ is
exposed; ${\mathcal{C}}_{2}\coloneqq\\{(x,y)\in\mathbb{R}^{2}:y=|x|\\}$ is
smooth at $x\in[1,2]$, so any supported valid inequality of
${\mathcal{C}}_{2}$ with support point $(x,y)$ ($x\in[1,2]$) is also exposed
by the same point; however, a supported valid inequality of
${\mathcal{C}}_{2}$ with supporting point $(x,y)$ ($x=0$) cannot be exposed,
since there are infinitely many supported valid inequalities at the same
point.

The first theorem we present holds for full-dimensional nonconvex sets
${\mathcal{S}}$. As shown in Fig. 1, we have observed the geometric
equivalence between the closed convex inner approximation of
$\operatorname{cl}({\mathcal{S}}^{c})$ and ${\mathcal{S}}$-free sets. The
theorem provides a sufficient condition for the maximality of closed convex
inner approximations.

######  Theorem 2.

Let ${\mathcal{F}}$ be a full-dimensional closed set in $\mathbb{R}^{p}$, and
let ${\mathcal{C}}\subseteq{\mathcal{F}}$ be a full-dimensional closed convex
set. If, for any
$z^{\ast}\in\operatorname{int}({\mathcal{F}}\smallsetminus{\mathcal{C}})$ and
any $\lambda\in\operatorname{dom}(\sigma_{{\mathcal{C}}})$ such that
$\lambda\cdot z^{\ast}>\sigma_{{\mathcal{C}}}(\lambda)$, there exists a point
$z^{\prime}\in\operatorname{bd}({\mathcal{F}})\cap\operatorname{bd}({\mathcal{C}})$
exposing $\lambda\cdot z\leq\sigma_{{\mathcal{C}}}(\lambda)$, then
${\mathcal{C}}$ is a maximal convex inner approximation of ${\mathcal{F}}$.

We call $z^{\ast}$ in Thm. 2 an _outlier point_ , by which we try to enlarge
an ${\mathcal{S}}$-free set, and let
$L(z^{\ast}):=\\{\lambda\in\operatorname{dom}(\sigma_{{\mathcal{C}}}):\lambda\cdot
z^{\ast}>\sigma_{{\mathcal{C}}}(\lambda)\\}$. The proof of Thm. 2 (in the
appendix) was adapted from [53, Thm. 2], which excludes the presence of the
outlier point and requires a stronger assumption, namely that for any
$\lambda\in\operatorname{dom}(\sigma_{{\mathcal{C}}})$ there exists a point
$z^{\prime}\in\operatorname{bd}({\mathcal{F}})\cap\operatorname{bd}({\mathcal{C}})$
exposing $\lambda\cdot z\leq\sigma_{{\mathcal{C}}}(\lambda)$. As we will see
in the proof of Thm. 3,
$\bigcup_{z^{\ast}\in\operatorname{int}({\mathcal{F}}\smallsetminus{\mathcal{C}})}L(z^{\ast})$
can be a proper subset of $\operatorname{dom}(\sigma_{{\mathcal{C}}})$, so we
do not need to check that all
$\lambda\in\operatorname{dom}(\sigma_{{\mathcal{C}}})$ are exposed.

We next focus on a specific type of function, namely _positive homogeneous
functions_. We summarize their properties as follows.

######  Lemma 3.

Let $f$ be a positive homogeneous function of degree $d\in\mathbb{R}$, such
that, for any $z\in\operatorname{dom}(f)\subseteq\mathbb{R}^{p}$ and any
$\rho\in\mathbb{R}_{++}$, $f(\rho z)=\rho^{d}f(z)$. Then: (i)
$\operatorname{int}(\operatorname{dom}(f))$ is a cone, and (ii) if $d=1$, then
for any $\breve{z}\in\operatorname{dom}(f)$,
${\Xi^{f}_{\breve{z}}}(z)=\nabla{f}(\breve{z})\cdot z$ for
$z\in\operatorname{dom}(f)$ and ${\Xi^{f}_{\breve{z}}}(z)=f(z)$ for
$z=\rho\breve{z}$ with $\rho\in\mathbb{R}_{++}$.

The proof is in the appendix. We recall that ${\Xi^{f}_{\breve{z}}}$ in the
above lemma is defined in Eq. (5). Moreover, $\operatorname{dom}(f)$ is
embedded in $\mathbb{R}^{p}$, so we call $\mathbb{R}^{p}$ the _ambient space_
of $f$.

The second theorem we present offers a more structured result, specifically
related to nonconvex DCC sets ${\mathcal{S}}$. [60, Thm. 5.48] provides a
sufficient condition for the maximality of the ${\mathcal{S}}$-free set
described in Lemma 1. However, to clearly distinguish it from our result
below, we translate the condition into our setting as follows: (i) the
functions $f_{1}$ and $f_{2}$ are superlinear, i.e. they are positive
homogeneous of degree 1 and superadditive (note that superlinear functions are
concave), (ii) they are separable and act independently on different variables
$u$ and $v$, (iii) $f_{1}$ is negative everywhere except at 0, (iv) the
linearization point $\tilde{v}$ of $f_{2}$ is nonzero, and (v) the domains
$\operatorname{dom}(f_{1})$ and $\operatorname{dom}(f_{2})$ are Euclidean
spaces.

Our second theorem provides an alternative condition for maximality that
relaxes condition (i) by requiring only that one of $f_{1}$ or $f_{2}$ be
positive homogeneous of degree 1, while imposing mild regularity conditions.
Moreover, the domains can be full-dimensional convex cones.

######  Theorem 3.

For every $i\in\\{1,2\\}$, let $f_{i}$ be concave. Let
${\mathcal{S}}\coloneqq\\{(u,v)\in\operatorname{dom}(f_{1})\times\operatorname{dom}(f_{2}):f_{1}(u)-f_{2}(v)\leq
0\\}$. Suppose that: (i) at least one of $f_{1},f_{2}$ is positive homogeneous
of degree 1, (ii) $f_{1},f_{2}$ are both positive/negative over the interiors
of their domains, (iii) $f_{1}$ is continuously differentiable over
$\operatorname{int}(\operatorname{dom}(f_{1}))$, and (iv)
$\operatorname{dom}(f_{1}),\operatorname{dom}(f_{2})$ are full-dimensional in
the ambient spaces of $f_{1},f_{2}$, respectively. Then, for any
$\tilde{v}\in\operatorname{int}(\operatorname{dom}(f_{2}))$,
${\mathcal{C}}\coloneqq\\{(u,v)\in\operatorname{dom}(f_{1})\times\operatorname{dom}(f_{2}):f_{1}(u)-{\Xi^{f_{2}}_{\tilde{v}}}(v)\geq
0\\}$ is maximally ${\mathcal{S}}$-free in
$\operatorname{dom}(f_{1})\times\operatorname{dom}(f_{2})$.

###### Proof.

We first adapt Lemma 1 by restricting the domain of $z$ to the convex ground
set
${\mathcal{G}}\coloneqq\operatorname{dom}(f_{1})\times\operatorname{dom}(f_{2})$.
It follows from Lemma 1 that ${\mathcal{C}}$ is an ${\mathcal{S}}$-free set in
${\mathcal{G}}$. Since
$\operatorname{dom}(f_{1})\times\operatorname{dom}(f_{2})$ are full-
dimensional, ${\mathcal{S}},{\mathcal{C}},{\mathcal{G}}$ are full-dimensional.
As ${\mathcal{S}},{\mathcal{C}}\subseteq{\mathcal{G}}$, the maximality of
${\mathcal{C}}$ in ${\mathcal{G}}$ is equivalent to that ${\mathcal{C}}$ is a
maximal convex inner approximation of
${\mathcal{F}}\coloneqq\operatorname{cl}({\mathcal{S}}^{c})\cap{\mathcal{G}}=\\{(u,v)\in{\mathcal{G}}:f_{1}(u)-f_{2}(v)\geq
0\\}$. Note that ${\mathcal{F}}$ is full-dimensional. We then apply Thm. 2 to
prove that ${\mathcal{C}}$ is a maximal convex inner approximation of
${\mathcal{F}}$. Let
$z^{\ast}\in\operatorname{int}({\mathcal{F}}\smallsetminus{\mathcal{C}})$ be
any outlier point. It follows from the separating hyperplane theorem that
there exists a supported valid inequality $\lambda\cdot
z\leq\sigma_{{\mathcal{C}}}(\lambda)$ of ${\mathcal{C}}$ such that
$\lambda\cdot z^{\ast}>\sigma_{{\mathcal{C}}}(\lambda)$. Since
${\mathcal{F}}\smallsetminus{\mathcal{C}}\subseteq{\mathcal{G}}$,
$\operatorname{int}({\mathcal{F}}\smallsetminus{\mathcal{C}})\subseteq{\mathcal{G}}$.
Since ${\mathcal{C}}\subseteq{\mathcal{G}}$, the inequality cannot be
supported by a valid inequality at $\operatorname{bd}({\mathcal{G}})$, so the
inequality must be a valid inequality supported at
${\mathcal{C}}\smallsetminus\operatorname{bd}({\mathcal{G}})$. It follows from
the concavity of $f_{1}$ that the inequality must admit the form
${\Xi^{f_{1}}_{\breve{u}}}(u)-{\Xi^{f_{2}}_{\tilde{v}}}(v)\geq 0$ for some
$\breve{u}\in\operatorname{dom}(f_{1})$ (identical up to a positive
multiplier). By the smoothness of $f_{1}$, w.l.o.g, we can perturb $\breve{u}$
such that it is in $\operatorname{int}(\operatorname{dom}(f_{1}))$. Let
$\breve{v}:=\tilde{v}$. We now have that
$\breve{u}\in\operatorname{int}(\operatorname{dom}(f_{1})),\breve{v}\in\operatorname{int}(\operatorname{dom}(f_{2}))$.
We will prove that
${\Xi^{f_{1}}_{\breve{u}}}(u)-{\Xi^{f_{2}}_{\breve{v}}}(v)\geq 0$ is exposed
by a point
$(u^{\prime},v^{\prime})\in(\operatorname{bd}({\mathcal{F}})\cap\operatorname{bd}({\mathcal{C}}))\cap\operatorname{int}({\mathcal{G}})$.
It suffices to show that the following three equations hold:

$\displaystyle{\Xi^{f_{1}}_{\breve{u}}}(u^{\prime})-{\Xi^{f_{2}}_{\breve{v}}}(v^{\prime})$
$\displaystyle=0\quad\textup{({i.e.,} supported at
$(u^{\prime},v^{\prime})$)},$ (8) $\displaystyle
f_{1}(u^{\prime})-{\Xi^{f_{2}}_{\breve{v}}}(v^{\prime})$
$\displaystyle=0\quad\textup{({i.e.,}
$(u^{\prime},v^{\prime})\in{\mathcal{C}}$)},$ $\displaystyle
f_{1}(u^{\prime})-f_{2}(v^{\prime})$ $\displaystyle=0\quad\textup{({i.e.,}
$(u^{\prime},v^{\prime})\in{\mathcal{F}}$)}.$

Since ${\mathcal{C}}\subseteq{\mathcal{F}}$ and they are both full-
dimensional, the last two equations imply that
$(u^{\prime},v^{\prime})\in\operatorname{bd}({\mathcal{C}})\cap\operatorname{bd}({\mathcal{F}})$.
As $f_{1}$ is continuously differentiable and concave in the interior of its
domain, the graph of $f_{1}(u)-{\Xi^{f_{2}}_{\breve{v}}}(v)$ over
$\operatorname{int}({\mathcal{G}})$ is a smooth manifold embedded in
$\operatorname{int}({\mathcal{G}})\times\mathbb{R}$. The intersection of a
smooth manifold with a hyperplane yields another lower-dimensional smooth
manifold. This implies that the level set ${\mathcal{C}}$ of
$f_{1}(u)-{\Xi^{f_{2}}_{\breve{v}}}(v)$ is also smooth at any point
$(u,v)\in\operatorname{int}({\mathcal{G}})\cap{\mathcal{C}}$. By Obs 2,
$(u,v)$ is an exposing point. Since
$(u^{\prime},v^{\prime})\in{\mathcal{C}}\cap\operatorname{int}({\mathcal{G}})$,
$(u^{\prime},v^{\prime})$ is an exposing point, and the maximality of
${\mathcal{C}}$ is verified. We now proceed to construct
$(u^{\prime},v^{\prime})$ from $(\breve{u},\breve{v})$ and prove (8). Let
$\rho\coloneqq f_{2}(\breve{v})/f_{1}(\breve{u})$. Since
$\breve{u}\in\operatorname{int}(\operatorname{dom}(f_{1})),\breve{v}\in\operatorname{int}(\operatorname{dom}(f_{2}))$,
by the assumption, $\rho>0$. We consider the following two cases separately.

Case i. We first suppose that $f_{1}$ is positive homogeneous of degree 1. Let
$(u^{\prime},v^{\prime})\coloneqq(\rho\breve{u},\breve{v})$, which, by Lemma
3, is in $\operatorname{int}({\mathcal{G}})$. We have that:

$f_{1}(u^{\prime})\stackrel{{\scriptstyle(i.1)}}{{=}}{\Xi^{f_{1}}_{\breve{u}}}(u^{\prime})\stackrel{{\scriptstyle(i.2)}}{{=}}\rho
f_{1}(\breve{u})\stackrel{{\scriptstyle(i.3)}}{{=}}f_{2}(\breve{v})\stackrel{{\scriptstyle(i.4)}}{{=}}f_{2}(v^{\prime})\stackrel{{\scriptstyle(i.5)}}{{=}}{\Xi^{f_{2}}_{\breve{v}}}(v^{\prime}),$

where equations $(i.1),(i.2)$ follow from Lemma 3, $(i.3)$ follows from the
definition of $\rho$, and $(i.4),(i.5)$ follow from $v^{\prime}=\breve{v}$.

Case ii. We then suppose that $f_{2}$ is positive homogeneous of degree 1. Let
$(u^{\prime},v^{\prime})\coloneqq(\breve{u},\breve{v}/\rho)\in\operatorname{int}({\mathcal{G}})$.
We have that:

${\Xi^{f_{1}}_{\breve{u}}}(u^{\prime})\stackrel{{\scriptstyle(ii.1)}}{{=}}f_{1}(u^{\prime})\stackrel{{\scriptstyle(ii.2)}}{{=}}f_{1}(\breve{u})\stackrel{{\scriptstyle(ii.3)}}{{=}}f_{2}(\breve{v})/\rho\stackrel{{\scriptstyle(ii.4)}}{{=}}f_{2}(v^{\prime})\stackrel{{\scriptstyle(ii.5)}}{{=}}{\Xi^{f_{2}}_{\breve{v}}}(v^{\prime}),$

where equations $(ii.1),(ii.2)$ follow from $\breve{u}=u^{\prime}$, $(ii.3)$
follows from the definition of $\rho$, and $(ii.4),(ii.5)$ follow from Lemma
3. Therefore, (8) are satisfied in both cases. ∎

We present the motivation for restricting the maximality of the set
${\mathcal{C}}$ within the ground set
$\operatorname{dom}(f_{1})\times\operatorname{dom}(f_{2})$. The main reason
for this restriction arises from the difficulty of finding a nontrivial
concave extension of $f_{1}$ over its ambient space such that for all
$u\notin\operatorname{dom}(f_{1})$, $f_{1}(u)>-\infty$. While such an
extension can exist geometrically, the construction of a closed expression
remains unclear. In the next section, we will examine a specific example to
illustrate this point.

Moreover, we will apply the above theorem to develop DCC formulations for a
nonconvex set. In particular, the functions $f_{1}$ and $f_{2}$ must not
simultaneously have positive homogeneity of degree 1, and their domains are
non-negative orthants. Consequently, the relaxed condition for homogeneous
degrees and domains in Thm. 3 becomes necessary. We give two examples for
verification Thm. 3.

######  Example 2.

Let $f_{1}(u)\coloneqq u$ with $\operatorname{dom}(f_{1})\in\mathbb{R}$, and
let $f_{2}(v)\coloneqq\sum_{i\in[n]}\sqrt{v_{i}}$ with
$\operatorname{dom}(f_{2})=\mathbb{R}^{n}_{+}$. Note that $f_{1},f_{2}$ are
concave, $\operatorname{dom}(f_{2})$ is a non-negative orthant, and $f_{1}$ is
positive homogeneous of degree 1. Let
${\mathcal{G}}\coloneqq\mathbb{R}\times\mathbb{R}^{n}_{+}$. One can verify
that the presupposition of Thm. 3 is satisfied. Then,
${\mathcal{S}}\coloneqq\\{(u,v)\in{\mathcal{G}}:u-\sum_{i\in[n]}\sqrt{v_{i}}\leq
0\\}$ is a convex set. It is easy to see that
${\mathcal{C}}\coloneqq\\{(u,v)\in{\mathcal{G}}:u-\sum_{i\in[n]}(\sqrt{\tilde{v}_{i}}+(v_{i}-\tilde{v}_{i})/\sqrt{\tilde{v}_{i}})\geq
0\\}$ is maximally ${\mathcal{S}}$-free in ${\mathcal{G}}$ with $\tilde{v}>0$.

######  Example 3.

Exchange the functions $f_{1},f_{2}$ in the previous examples. Then,
${\mathcal{S}}\coloneqq\\{(u,v)\in{\mathcal{G}}:\sum_{i\in[n]}\sqrt{v_{i}}-u\leq
0\\}$ is a reverse-convex set. It is easy to see that
${\mathcal{C}}\coloneqq\\{(u,v)\in{\mathcal{G}}:\sum_{i\in[n]}\sqrt{v_{i}}-u\geq
0\\}$ is the unique maximal ${\mathcal{S}}$-free set in ${\mathcal{G}}$.

##  4 Signomial-lift-free sets and intersection cuts

In this section, we construct (maximal) signomial-lift-free sets and generate
intersection cuts for SP.

###  4.1 Signomial-lift-free and signomial-term-free sets

We introduce and study new formulations of signomial term sets. We transform
signomial term sets into DCC sets. We also construct signomial term-free sets
and lift them to signomial term-lift-free sets. The maximality of these sets
is studied, and a comparison is made between signomial term-free sets derived
from different DCC formulations.

We consider an $n$-variate signomial term $\psi_{\alpha}(x)$ arising in the
extended formulation (2) of SP. The exponent vector $\alpha$ may contain
negative/zero/positive entries. We extract two sub-vectors $\alpha^{-}$ and
$\alpha^{+}$ from $\alpha$ such that
$\alpha^{-}\in\mathbb{R}^{h^{\prime}}_{--}$ and
$\alpha^{+}\in\mathbb{R}^{\ell^{\prime}}_{++}$, and let
$x_{-}\in\mathbb{R}^{h^{\prime}}$ and $x_{+}\in\mathbb{R}^{\ell^{\prime}}$ be
the corresponding sub-vectors of $x$. Entries $x_{j}$ with $\alpha_{j}=0$ are
excluded from consideration, and so $h^{\prime}+\ell^{\prime}$ may be smaller
than $n$. Since $\psi_{\alpha}(x)$ only depends on $x_{-}$ and $x_{+}$, it can
be represented in the form of $x_{-}^{\alpha^{-}}x_{+}^{\alpha^{+}}$ of lower
order. We consider the _signomial term set_ as epigraph or hypograph of
$x_{-}^{\alpha^{-}}x_{+}^{\alpha^{+}}$:

${\mathcal{S}}_{\mathrm{st}}=\\{(x_{-},x_{+},t)\in\mathbb{R}_{++}^{h^{\prime}+\ell^{\prime}+1}:t\lesseqgtr
x_{-}^{\alpha^{-}}x_{+}^{\alpha^{+}}\\}.$ (9)

We first give DCC reformulations of signomial term sets. Let $\lessgtr$ denote
$<$ or $>$. The interior of ${\mathcal{S}}_{\mathrm{st}}$ in (9) is

$\operatorname{int}({\mathcal{S}}_{\mathrm{st}})=\\{(x_{-},x_{+},t)\in\mathbb{R}_{++}^{h^{\prime}+\ell^{\prime}+1}:t\lessgtr
x_{-}^{\alpha^{-}}x_{+}^{\alpha^{+}}\\}.$

Reorganizing the signomial terms and taking the closure of the set, we recover

${\mathcal{S}}_{\mathrm{st}}=\\{(x_{-},x_{+},t)\in\mathbb{R}_{+}^{h^{\prime}+\ell^{\prime}+1}:tx_{-}^{-\alpha^{-}}\lesseqgtr
x_{+}^{\alpha^{+}}\\}.$

Notably, the exponents associated with signomial terms on both sides are now
strictly positive. Let $u\coloneqq(t,x_{-}),v\coloneqq x_{+}$, let $h\coloneqq
h^{\prime}+1$, and let $\ell\coloneqq\ell^{\prime}$. Then,
$\psi_{\beta^{\prime}}(u)=tx_{-}^{-\alpha^{-}}$ and
$\psi_{\gamma^{\prime}}(v)=x_{+}^{\alpha^{+}}$, where
$\beta^{\prime}\coloneqq(1,-\alpha^{-})\in\mathbb{R}_{++}^{h}$ and
$\gamma^{\prime}\coloneqq\alpha^{+}\in\mathbb{R}_{++}^{\ell}$. After the
change of variables, the set admits the following form:

${\mathcal{S}}_{\mathrm{st}}=\\{(u,v)\in\mathbb{R}_{+}^{h+\ell}:\,\psi_{\beta^{\prime}}(u)\lesseqgtr\psi_{\gamma^{\prime}}(v)\\}.$
(10)

The formulation (10) exhibits symmetry between $u$ and $v$. We can therefore
consider w.l.o.g. the inequality “$\leq$” throughout the subsequent analysis.
Since the signomial terms $\psi_{\beta^{\prime}}(u),\psi_{\gamma^{\prime}}(v)$
are non-negative over $\mathbb{R}_{+}^{h},\mathbb{R}_{+}^{\ell}$, we can take
any positive power $\eta\in\mathbb{R}_{++}$ on both sides of (10). Finally,
the signomial term set in (9) admits the following form:

${\mathcal{S}}_{\mathrm{st}}=\\{(u,v)\in\mathbb{R}_{+}^{h+\ell}:\,\psi_{\beta}(u)-\psi_{\gamma}(v)\leq
0\\},$ (11)

where $\beta\coloneqq\eta\beta^{\prime}$, and
$\gamma\coloneqq\eta\gamma^{\prime}$.

A signomial term $\psi_{\alpha}(x)$ is said to be a _power function_ if
$\alpha\geq 0$, and $\lVert\alpha\rVert_{1}\leq 1$. According to [4, 16],
power functions are concave over the non-negative orthant; if additionally
$\lVert\alpha\rVert_{1}=1$, $\psi_{\alpha}(x)$ is positive homogeneous of
degree 1. Through an appropriate scaling of the parameter $\eta$, we obtain a
family of DCC reformulations (11) of signomial term sets. We let
${\mathcal{G}}\coloneqq\mathbb{R}_{+}^{h+\ell}$, and use the reverse-
linearization technique to construct signomial-term-free sets. We recall that
the definition of the operator $\Xi$ is given in Eq. (5).

######  Proposition 1.

Let $\max(\lVert\beta\rVert_{1},\lVert\gamma\rVert_{1})\leq 1$. For any
$\tilde{v}\in\mathbb{R}^{\ell}_{++}$,

${\mathcal{C}}\coloneqq\\{(u,v)\in\mathbb{R}_{+}^{h}\times\mathbb{R}^{\ell}:\,\psi_{\beta}(u)-{\Xi^{\psi_{\gamma}}_{\tilde{v}}}(v)\geq
0\\}$ (12)

is a signomial-term-free (${\mathcal{S}}_{\mathrm{st}}$-free) set. If
$\max(\lVert\beta\rVert_{1},\lVert\gamma\rVert_{1})=1$, then ${\mathcal{C}}$
is a maximal signomial-term-free set in ${\mathcal{G}}$.

###### Proof.

Since $\max(\lVert\beta\rVert_{1},\lVert\gamma\rVert_{1})\leq 1$,
$\psi_{\beta}(u),\psi_{\gamma}(v)$ are concave. By Lemma 1, ${\mathcal{C}}$ is
signomial-term-free. If
$\max(\lVert\beta\rVert_{1},\lVert\gamma\rVert_{1})=1$, then at least one of
$\lVert\beta\rVert_{1},\lVert\gamma\rVert_{1}$ is 1. Therefore, one of
$\psi_{\beta}(u),\psi_{\gamma}(v)$ is positive homogeneous of degree 1.
Moreover, $\psi_{\beta}(u),\psi_{\gamma}(v)$ are both continuously
differentiable and positive over positive orthants
$\mathbb{R}^{h}_{++},\mathbb{R}^{\ell}_{++}$ (the interiors of their domains).
Since
${\mathcal{G}}=\operatorname{dom}(\psi_{\beta})\times\operatorname{dom}(\psi_{\gamma})$,
by Thm. 3,
${\mathcal{C}}\cap{\mathcal{G}}=\\{(u,v)\in{\mathcal{G}}:\,\psi_{\beta}(u)-{\Xi^{\psi_{\gamma}}_{\tilde{v}}}(v)\geq
0\\}$ is a maximal signomial-term-free set in ${\mathcal{G}}$. Therefore,
${\mathcal{C}}$ is also a maximal signomial-term-free set in ${\mathcal{G}}$.
∎

Given that $\max(\lVert\beta\rVert_{1},\lVert\gamma\rVert_{1})=1$ results in a
desirable DDC formulation for the signomial term set, we refer to this
formulation as its _normalized DCC formulation_. Comparing Prop. 1 to Thm. 3,
we extend the domain of ${\Xi^{\psi_{\gamma}}_{\tilde{v}}}(v)$ from
$\mathbb{R}^{\ell}_{+}$ to $\mathbb{R}^{\ell}$, since it is an affine
function. However, the further extension requires a non-trivial concave
extension of the power function $\psi_{\beta}$, which we are unaware of.

We have reduced the $n$-variate signomial term $\psi_{\alpha}(x)$ to a
signomial term $x_{-}^{\alpha^{-}}x_{+}^{\alpha^{+}}$ of lower order and
constructed the corresponding signomial-term-free sets. A similar reduction is
observed for $g_{i}$ to $g^{\prime}_{i}$ in Subsec. 3.1, where we demonstrate
the relationship between ${\mathcal{S}}_{\mathrm{lift}}$-free sets and
$\operatorname{epi}(g^{\prime}_{i})$-free/$\operatorname{hypo}(g^{\prime}_{i})$-free
sets.

Next, we let the lifted set ${\mathcal{S}}_{\mathrm{lift}}$ be the signomial
lift, where all $g_{i}$ are signomial terms. Each equality constraint
$y_{i}=g_{i}(x)$ defining the signomial lift is equivalent to two inequality
constraints $y_{i}\lesseqgtr g_{i}(x)$. Applying the normalized DDC
reformulation to these inequality constraints, we thus obtain a reformulation
of the signomial lift, which we call its _normalized DCC reformulation_.

######  Corollary 1.

Let ${\mathcal{C}}$ be as in (12), where $\psi_{\alpha}=g_{i}$ for some
$i\in[k]$ and $\max(\lVert\beta\rVert_{1},\lVert\gamma\rVert_{1})=1$. Then the
orthogonal lifting of ${\mathcal{C}}$ w.r.t. $g_{i}$ is a maximal signomial-
lift-free (${\mathcal{S}}_{\mathrm{lift}}$-free) set in the non-negative
orthant.

###### Proof.

We verify that the conditions of Thm. 2 are satisfied by the signomial lift.
For any $i\in[k]$, the signomial term $g_{i}$ is continuous, and its domain
and range are $\mathbb{R}_{++}$. Let $J_{i}$ be the index set of variables of
its reduced signomial term $g^{\prime}_{i}$. Let
${\mathcal{X}}\coloneqq\bigtimes_{j\in[n]}\mathbb{R}_{++},{\mathcal{Y}}\coloneqq\bigtimes_{j\in[k]}\mathbb{R}_{++}$.
For all $j\in[n+k]$, let ${\mathcal{D}}_{j}\coloneqq\mathbb{R}_{++}$. For all
$i\in[k]$, let ${\mathcal{X}}^{i}\coloneqq\bigtimes_{j\in
J_{i}}\mathbb{R}_{++},{\mathcal{Y}}^{i}\coloneqq\mathbb{R}_{++}$. The
underlying sets of the signomial lift are
${\mathcal{X}},{\mathcal{Y}},\\{{\mathcal{X}}^{i},{\mathcal{Y}}^{i}\\}_{i\in[k]}$
that are 1d-convex decomposable by $\\{{\mathcal{D}}_{j}\\}_{j\in[n+k]}$. By
Prop. 1, ${\mathcal{C}}$ is a maximal
$\operatorname{hypo}(g^{\prime}_{i})$-free set in
${\mathcal{X}}^{i}\times{\mathcal{Y}}^{i}$. By Thm. 2, its orthogonal lifting
w.r.t. $g_{i}$ is a maximal signomial-lift-free set in positive orthant. By
continuity of $\psi_{\beta},\psi_{\gamma}$, we change the ground set (the
positive orthant) to its closure, i.e., non-negative orthant. ∎

The following examples show signomial term-free sets from different DDC
formulations.

######  Example 4 (Comparison of DCC formulations).

Consider ${\mathcal{S}}_{\mathrm{st}}=\\{(u,v)\in\mathbb{R}^{2}_{+}:u\leq
v\\}$, which is already in normalized DCC formulation. It is easy to see that
${\mathcal{C}}_{1}\coloneqq\\{(u,v)\in\mathbb{R}_{+}\times\mathbb{R}:u\geq
v\\}$ is a maximal ${\mathcal{S}}_{\mathrm{st}}$-free set in
$\mathbb{R}^{2}_{+}$ given by Prop. 1. Let $\tilde{v}\in\mathbb{R}_{++}$ be a
linearization point. As
$\operatorname{int}({\mathcal{S}}_{\mathrm{st}})=\\{(u,v)\in\mathbb{R}^{2}_{+}:\log(u)\leq\log(v)\\}$
admits a DCC formulation, applying the reverse-linearization technique at
$\tilde{v}$ yields
${\mathcal{C}}_{2}\coloneqq\\{(u,v)\in\mathbb{R}^{2}_{+}:\log(u)-(\log(\tilde{v})+(v-\tilde{v})/\tilde{v})\geq
0\\}$, which is also an ${\mathcal{S}}_{\mathrm{st}}$-free set. For any
$0<\eta<1$,
${\mathcal{S}}_{\mathrm{st}}=\\{(u,v)\in\mathbb{R}^{2}_{+}:u^{\eta}\leq
v^{\eta}\\}$ is a DDC set, applying the reverse-linearization technique at
$\tilde{v}$ yields
${\mathcal{C}}_{3}\coloneqq\\{(u,v)\in\mathbb{R}^{2}_{+}:u^{\eta}-((1-\eta)\tilde{v}^{\eta}+\eta\tilde{v}^{\eta-1}v)\geq
0\\}$, which is also an ${\mathcal{S}}_{\mathrm{st}}$-free set. However,
${\mathcal{C}}_{2},{\mathcal{C}}_{3}$ cannot be maximal in
$\mathbb{R}^{2}_{+}$, because their intersections with $\mathbb{R}^{2}_{+}$
are not polyhedral. These sets are visualized in Fig. 2 with a linearization
point $\tilde{v}=0.5$ and scaling parameter $\eta=0.7$.

(a)

(b)

(c)

Figure 2: ${\mathcal{S}}_{\mathrm{st}}$-free sets from Example 4.

######  Example 5.

Consider the hypograph of signomial term $x_{1}^{-2}x_{2}^{2}$ and
${\mathcal{S}}_{\mathrm{st}}=\\{(x,y)\in\mathbb{R}_{+}^{3}:y\leq
x_{1}^{-2}x_{2}^{2}\\}.$ For $(x,y)\in\mathbb{R}_{++}^{3}$, $y\leq
x_{1}^{-2}x_{2}^{2}$ if and only if $y^{1/3}x_{1}^{2/3}\leq x_{2}^{2/3}$. The
following set is maximal ${\mathcal{S}}_{\mathrm{st}}$-free in
${\mathcal{G}}=\mathbb{R}_{+}^{3}$:
${\mathcal{C}}_{4}\coloneqq\\{(x,y)\in\mathbb{R}_{+}^{3}:y^{1/3}x_{1}^{2/3}\geq\tilde{x}_{2}^{2/3}+\frac{2}{3}\tilde{x}_{2}^{-1/3}(x_{2}-\tilde{x}_{2})\\},$
where $\tilde{x}_{2}\in\mathbb{R}_{++}$. See Fig. 3(a) for
$\tilde{x}_{2}=0.2$.

######  Example 6.

Consider the epigraph of signomial term $x_{1}^{3}x_{2}$ and
${\mathcal{S}}_{\mathrm{st}}=\\{(x,y)\in\mathbb{R}_{+}^{3}:y\geq
x_{1}^{3}x_{2}\\}.$ For $(x,y)\in\mathbb{R}_{++}^{3}$, $y\geq x_{1}^{3}x_{2}$
if and only if $y^{1/4}\geq x_{1}^{3/4}x_{2}^{1/4}$. The following set is
maximal ${\mathcal{S}}_{\mathrm{st}}$-free in
${\mathcal{G}}=\mathbb{R}_{+}^{3}$:
${\mathcal{C}}_{5}\coloneqq\\{(x,y)\in\mathbb{R}_{+}^{3}:\tilde{y}^{1/4}+\frac{1}{4}\tilde{y}^{-3/4}(y-\tilde{y})\leq
x_{1}^{3/4}x_{2}^{1/4}\\},$ where $\tilde{y}\in\mathbb{R}_{++}$. See Fig. 3(b)
for $\tilde{y}=0.2$.

(a) ${\mathcal{S}}_{\mathrm{st}}$ and ${\mathcal{C}}_{4}$ from Example 5.

(b) ${\mathcal{S}}_{\mathrm{st}}$ and ${\mathcal{C}}_{5}$ from Example 6.

Figure 3: ${\mathcal{S}}_{\mathrm{st}}$ and ${\mathcal{S}}_{\mathrm{st}}$-free
sets from Examples 5 and 6.

###  4.2 Intersection cuts

We focus on the separation of intersection cuts for the extended formulation
of SP. In Sec. 2 we presented a method to construct a simplicial cone
${\mathcal{R}}$ from an LP relaxation. The vertex of this cone is a relaxation
solution $\tilde{z}=(\tilde{x},\tilde{y})$.

We assume that the LP relaxation includes all linear constraints from (2). If
$\tilde{z}$ is infeasible for (2), then $\tilde{z}$ does not belong to the
signomial lift. Thus, there is a signomial term $g_{i}$ such that
$\tilde{y}_{i}\neq g_{i}(\tilde{x})$. Given the reduced form $g^{\prime}_{i}$,
we obtain a set of signomial terms ${\mathcal{S}}_{\mathrm{st}}$: If
$g_{i}(\tilde{x})>\tilde{y}_{i}$, we choose ${\mathcal{S}}_{\mathrm{st}}$ to
be the epigraph of $g^{\prime}_{i}$; otherwise, we choose it to be the
hypograph of $g^{\prime}_{i}$. This signomial term set yields a signomial
term-free set ${\mathcal{C}}$ in (12) containing $(\tilde{u},\tilde{v})$ in
its interior (Lemma 1). Using orthogonal lifting of Cor. 1, we can transform
${\mathcal{C}}$ into a signomial-lift-free set $\bar{{\mathcal{C}}}$.

We next show how to construct an intersection cut in (7). It suffices to
compute step lengths $\eta^{\ast}_{j}$ in (6) along extreme rays $r^{j}$ of
${\mathcal{R}}$. Each step length $\eta^{\ast}_{j}$ corresponds to a boundary
point $\tilde{z}+\eta^{\ast}_{j}r^{j}$ in
$\operatorname{bd}(\bar{{\mathcal{C}}})$. The left-hand-side
$\psi_{\beta}(u)-{\Xi^{\psi_{\gamma}}_{\tilde{v}}}(v)$ of the inequality in
(12) is a concave function over
$(u,v)\in\mathbb{R}_{+}^{h}\times\mathbb{R}^{\ell}$. Its restriction along the
ray $\tilde{z}+\eta_{j}r^{j}\;(\eta_{j}\in\mathbb{R}_{+})$ is a univariate
concave function:

$\tau_{j}:\mathbb{R}_{+}\to\mathbb{R},\eta_{j}\mapsto\tau_{j}(\eta_{j})\coloneqq\psi_{\beta}(\tilde{u}+r^{j}_{u}\eta_{j})-{\Xi^{\psi_{\gamma}}_{\tilde{v}}}(\tilde{v}+r^{j}_{v}\eta_{j}),$

where $r^{j}_{u}$ and $r^{j}_{v}$ are the projections of $r^{j}$ on $u$ and
$v$ respectively. Let $\bar{\eta}_{j}\coloneqq\sup_{\eta_{j}\geq
0}\\{\eta_{j}:\tilde{u}+r^{j}_{u}\eta_{j}\geq 0\\}$. Therefore,
$\eta^{\ast}_{j}$ is the first point in $[0,\bar{\eta}_{j}]$ satisfying the
boundary condition: either $\tau_{j}(\eta^{\ast}_{j})=0$ or
$\eta^{\ast}_{j}=\bar{\eta}_{j}$. Since $\tau_{j}$ is a univariate concave
function and $\tau_{j}(0)>0$, there is at most one positive point in
$\mathbb{R}_{+}$ where $\tau_{j}$ is zero. We employ the bisection search
method [56] to find such $\eta^{\ast}_{j}$.

##  5 Convex outer approximation

In this section we propose a convex nonlinear relaxation for the extended
formulation (2) of SP. This relaxation is easy to derive and allows us to
generate valid linear inequalities, called outer approximation cuts, for SP.
Unlike intersection cuts, outer approximation cuts do not require an LP
relaxation a priori, so solvers can employ them to generate an initial LP
relaxation of (2).

To ensure the convergence of the sBB algorithm, the feasible region of the
extended formulation (2) should be compact. Therefore, we assume in the sequel
that the signomial lift is in a hypercube.

We construct the convex nonlinear relaxation by approximating each signomial
term set of the signomial lift within the hypercube. W.l.o.g., we consider a
signomial term set in hypergraph or epigraph form. As Subsec. 4.1, we can
convert it into normalized DDC formulation:

${\mathcal{S}}_{\mathrm{st}}=\\{(u,v)\in{\mathcal{U}}\times{\mathcal{V}}:\,\psi_{\beta}(u)-\psi_{\gamma}(v)\leq
0\\},$ (13)

where $\max(\lVert\beta\rVert_{1},\lVert\gamma\rVert_{1})=1$, and
${\mathcal{U}},{\mathcal{V}}$ are two hypercubes in
$\mathbb{R}_{+}^{h},\mathbb{R}_{+}^{\ell}$ respectively. Due to Subsec. 5.3,
the signomial term set is usually nonconvex, so our construction involves
convexifying the concave function $\psi_{\beta}$ in (13). This procedure
yields a convex outer approximation of ${\mathcal{S}}_{\mathrm{st}}$, which is
non-polyhedral. Consequently, replacing ${\mathcal{S}}_{\mathrm{st}}$ by its
convex outer approximation, we obtain the convex nonlinear relaxation of (2).

Next, we introduce the procedure of convexification. We should import the
formal concepts of convex underestimators and convex envelopes. Given a
function $f$ and a closed set ${\mathcal{D}}\subseteq\mathbb{R}^{p}$, a convex
function $f^{\prime}:\operatorname{conv}({\mathcal{D}})\to\mathbb{R}$ is
called a convex underestimator of $f$ over ${\mathcal{D}}$, if for all
$x\in{\mathcal{D}}$ $f^{\prime}(x)\leq f(x)$. The convex envelope
$\operatorname{convenv}_{{\mathcal{D}}}(f)$ of $f$ is defined as the pointwise
maximum convex underestimator of $f$ over $D$.

The following lemma gives an extended formulation of the convex envelope of a
concave function over a polytope, where the formulation is uniquely determined
by the function values at the vertices of the polytope.

######  Lemma 4.

[26, Thm. 3] Let $P$ be a polytope in $\mathbb{R}^{n}$, let $f:P\to\mathbb{R}$
be a concave function over $P$, and let $Q$ be vertices of $P$. Then,
$\operatorname{convenv}_{P}(f)(x)=\max\\{\sum_{q\in
Q}\lambda_{q}f(q):\exists\lambda\in\mathbb{R}^{Q}_{+},\sum_{q\in
Q}\lambda_{q}=1,\,x=\sum_{q\in Q}\lambda_{q}q\\}$.

Based on the lemma above, we observe that the concave function $f$ is convex-
extensible from its vertices (i.e.,
$\operatorname{convenv}_{P}(f)(x)=\operatorname{convenv}_{Q}(f)(x)$ for $x\in
P$), and $\operatorname{convenv}_{P}(f)$ is a polyhedral function.

For the case of
$P={\mathcal{U}}\coloneqq\prod_{j\in[h]}[\underline{u}_{j},\overline{u}_{j}]$
and $f=\psi_{\beta}$, $Q=\\{q\in\mathbb{R}^{h}:\forall
j\in[h]\;q_{j}=\underline{u}_{j}\lor q_{j}=\overline{u}_{j}\\}$ is the set of
vertices of the hypercube ${\mathcal{U}}$. The lemma yields an extended
formulation of $\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta})$.
Replacing $\psi_{\beta}$ by its convex envelope
$\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta})$, we obtain the convex
outer approximation of ${\mathcal{S}}_{\mathrm{st}}$ in (13):

$\overline{{\mathcal{S}}}_{\mathrm{st}}\coloneqq\\{(u,v)\in{\mathcal{U}}\times{\mathcal{V}}:\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta})(u)\leq\psi_{\gamma}(v)\\}.$

By using this extended formulation, our convex nonlinear relaxation of SP
contains additional auxiliary variables. In particular, we need $2^{h}$
variables $\lambda_{q}$ to represent each convex envelope. For most SP
problems in MINLPLib where the degrees of the signomial terms are less than 6
and $h$ is less than 3, the convex nonlinear relaxation is computationally
tractable.

###  5.1 Outer approximation cuts

To increase efficiency, we propose a cutting plane algorithm to separate valid
linear inequalities in $(u,v)$-space from the extended formulation of the
convex outer approximation. This algorithm generates a low-dimensional
projected approximation of $\overline{{\mathcal{S}}}_{\mathrm{st}}$. Moreover,
the projection procedure converts the convex nonlinear relaxation into an LP
relaxation, which is suitable for many solvers.

Given a point $(\tilde{u},\tilde{v})\in{\mathcal{U}}\times{\mathcal{V}}$, the
algorithm determines whether it belongs to
$\overline{{\mathcal{S}}}_{\mathrm{st}}$. This verification can be done by
checking the sign of
$\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta})(\tilde{u})-\psi_{\gamma}(\tilde{v})$.
If
$\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta})(\tilde{u})-\psi_{\gamma}(\tilde{v})\leq
0$, then $(\tilde{u},\tilde{v})\in\overline{{\mathcal{S}}}_{\mathrm{st}}$.

Since $\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta})$ is a convex
polyhedral function, our cutting plane algorithm evaluates the function by
searching for an affine underestimator $a\cdot u+b$ of
$\operatorname{convenv}_{{\mathcal{U}}}(u)$ such that
$a\cdot\tilde{u}+b=\operatorname{convenv}_{{\mathcal{U}}}(\tilde{u})$. If
$(\tilde{u},\tilde{v})\notin\overline{{\mathcal{S}}}_{\mathrm{st}}$, then
$a\cdot u+b\leq\psi_{\gamma}(v)$ is a valid nonlinear inequality of
$\overline{{\mathcal{S}}}_{\mathrm{st}}$. Subsequently, our cutting plane
algorithm linearizes this inequality, resulting in an outer approximation cut
$a\cdot u+b\leq{\Xi^{\psi_{\gamma}}_{\tilde{v}}}(v)$: we recall that
${\Xi^{\psi_{\gamma}}_{\tilde{v}}}(v)$ is the linearization of
$\psi_{\gamma}(v)$ at $\tilde{v}$ defined in Eq. (5).

Due to Lemma 4, we can solve the following LP to find the affine
underestimator:

$\max_{a\in\mathbb{R}^{h},b\in\mathbb{R}}a\cdot\tilde{u}+b\quad\operatorname{s.t.}\forall
q\in Q\;a\cdot q+b\leq\psi_{\gamma}(q),$ (14)

where we omit the linear constraints that bound $(a,b)$. The maximum value
resulting from this LP is exactly
$\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta})(\tilde{u})$. The affine
undestimator $a\cdot u+b$ is called an _facet_ of the envelope
$\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta})$, if $a\cdot u+b\leq t$
is a facet of
$\operatorname{epi}(\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta}))$. It
should be noted that the solution of the LP is not necessarily a facet.

For $h=1,2$ we can provide explicit projected formulations of convex envelopes
of power functions. This allows us to obtain facets of
$\operatorname{convenv}_{{\mathcal{U}}}(\psi_{\beta})$ without having to solve
LPs. As a result, our cutting plane algorithm can efficiently separate outer
approximation cuts for low-order problems.

To simplify our representation, we translate and scale the domain of
$\psi_{\beta}$ to $[0,1]^{h}$. This leads to a new function
$s(w)\coloneqq\psi_{\beta}(u)$, where for all $j\in[h]$,
$u_{j}\coloneqq\overline{u}_{j}+(\overline{u}_{j}-\underline{u}_{j})w_{j}$.
After these transformations, we have ${\mathcal{U}}=[0,1]^{h}$ and
$Q=\\{0,1\\}^{h}$. W.l.o.g., we focus on the study and computation of facets
of $\operatorname{convenv}_{{\mathcal{U}}}(s)$. For $h=1$, the only facet is
$s(0)+(s(1)-s(0))w_{1}$.

A set $D\subseteq\mathbb{R}^{h}$ is called a _product set_ , if
$D=\bigtimes_{j\in[h]}D_{j}$ for $D_{j}\subseteq\mathbb{R}$. Moreover, a
function $f:D\to\mathbb{R}$ is _supermodular_ over $D$ ([66, Sec. 2.6.1]), if
the increasing difference condition holds: for all $w^{1},w^{2}\in
D,d\in\mathbb{R}^{h}_{+}$ such that $w^{1}\leq w^{2}$ and $w^{1}+d,w^{2}+d\in
D$, $f(w^{1}+d)-f(w^{1})\leq f(w^{2}+d)-f(w^{2})$. We find that the following
operations preserve supermodularity.

######  Lemma 5.

Let $w^{\prime}\in\mathbb{R}^{h},\rho\in\mathbb{R}^{h}_{++}$, and let
$D^{\prime}$ be a product subset of $D$. The following results hold:
(restriction) $f$ is supermodular over $D^{\prime}$;(translation)
$f(w+w^{\prime})$ is supermodular over $D-d$; (scaling) $f(\rho*w)$ is
supermodular over $D/\rho$, where $+,-,*,/$ are taken entry-wise.

###### Proof.

The results follow from the definition. ∎

We note that when $D=Q$, $d$ is in $Q$. We observe a useful property of $s$.

######  Proposition 2.

$s$ is supermodular over $Q$ and
$\operatorname{convenv}_{{\mathcal{U}}}(s)=\operatorname{convenv}_{{\mathcal{Q}}}(s)$.

###### Proof.

According to [66, Example 2.6.2], the signomial term $\psi_{\alpha}$ with
$\alpha>0$ is supermodular over $\mathbb{R}^{h}_{+}$. This implies that the
power function $\psi_{\beta}$ is supermodular over $\mathbb{R}^{h}_{+}$. By
Lemma 5, $s$ is supermodular over ${\mathcal{U}}=[0,1]^{h}$. As
$Q=\\{0,1\\}^{h}$ is a product subset of ${\mathcal{U}}$, $s$ is supermodular
over $Q$. After the scaling and translation, $s$ is still concave. By Lemma 4,
$\operatorname{convenv}_{{\mathcal{U}}}(s)=\operatorname{convenv}_{{\mathcal{Q}}}(s)$.
∎

Finding facets of $s$ can be reduced to a more general problem of finding
facets of supermodular functions over Boolean hypercubes. We note that a
similar argument can show that both power functions and multilinear terms over
any product subset of $\mathbb{R}^{h}_{+}$ are supermodular.

###  5.2 Projected convex envelopes of bivariate supermodular functions

We present a general characterization of projected convex envelopes of
supermodular functions and give a closed-form expression for bivariate cases.
Let $f$ be a supermodular function over $Q$. We can use a bit representation
to denote Boolean points in $Q$. For example, $10$ denotes the point $w$ that
$w_{1}=1$ and $w_{2}=0$. For an affine function $a\cdot w+b$, we call Boolean
points in $Q$ where $a\cdot w+b$ equals $f(w)$ its _supporting points_.

######  Lemma 6.

Each facet of $f$ is supported by $h+1$ affinely independent points in $Q$.

See the proof in the appendix. We can enumerate all possible subsets of $h+1$
affinely independent points of $Q$. Each such subset
$S\coloneqq\\{w^{1},\dots,w^{h+1}\\}$ determines a function over
$\mathbb{R}^{h}$ via the following affine combination:

$f_{S}(w)\coloneqq\left\\{\sum_{j\in[h+1]}\lambda_{j}f(w^{j}):\exists\lambda\in\mathbb{R}^{h+1}\,\sum_{j\in[h+1]}\lambda_{j}=1\land\sum_{j\in[h+1]}\lambda_{j}w^{j}=w\right\\}.$

Because of the affine independence of $S$, the Barycentric coordinate
$\lambda$ is unique for any $w$ in the above affine combination. We can
consider $f_{S}$ as a single-valued affine function and call it the _supported
function_ of $S$. Since $f_{S}(w)=f(w)$ solves the linear system $a\cdot
w+b=f(w)$ (for $w\in S$), we can compute $a,b$ which defines $f_{S}$. If the
supported function $f_{S}$ underestimates $f$, we call the subset $S$ _facet-
inducing_.

Assuming we have a collection of facets of $f$, we then determine whether
these facets define the convex envelope of $f$. We recall that the convex hull
of $h+1$ affinely independent points is an _$h$ -simplex_. A finite collection
of $h$-simplices $\\{P_{k}\\}_{k}$ is called a _triangulation_ of the unit
cube ${\mathcal{U}}$, if the following conditions hold: (i)
$\bigcup_{k}P_{k}={\mathcal{U}}$, (ii) $P_{k}\cap P_{k^{\prime}}$ is empty or
a face of both $P_{k},P_{k^{\prime}}$ for any $k,k^{\prime}$, (iii) the
vertices of $P_{k}$ are contained in $Q$ for all $k$.

######  Proposition 3.

Let $\\{S_{k}\\}_{k}$ be a collection of facet-inducing subsets of $Q$. For
each $k$, let $f_{S_{k}}$ be the supported function induced by $S_{k}$, and
let $P_{k}:=\operatorname{conv}(S_{k})$ be the simplex spanned by $S_{k}$. If
$\\{P_{k}\\}_{k}$ is a triangulation of ${\mathcal{U}}$, then
$\operatorname{convenv}_{{\mathcal{Q}}}(f)(w)=\max_{k}f_{S_{k}}(w)$ for all
$w\in{\mathcal{U}}$.

###### Proof.

Since $\bigcup_{k}P_{k}={\mathcal{U}}$, for any $w\in Q$, there exists $P_{k}$
such that $w\in P_{k}$. Since the vertices $S_{k}$ of $P_{k}$ are contained in
$Q$, $w$ must be in $S_{k}$. Therefore, $f_{S_{k}}(w)=f(w)$. This implies that
$f(w)=\max_{k}f_{S_{k}}(w)$ for all $w\in Q$, i.e., $\max_{k}f_{S_{k}}$ is an
exact convex underestimator. Suppose, to aim at a contradiction, that there
exists another convex underestimator $f^{\prime}$ of $f$ such that
$f^{\prime}(w)=f(w)$ for all $w\in Q$, and
$f^{\prime}(w^{\prime})>\max_{k}f_{S_{k}}(w^{\prime})$ for some
$w^{\prime}\in{\mathcal{U}}$. Again, since $\bigcup_{k}P_{k}={\mathcal{U}}$,
there exists $P_{k}$ such that $w^{\prime}\in P_{k}$, i.e.,
$w^{\prime}\in\operatorname{conv}(S_{k})$. Let
$S_{k}=\\{w^{1},\dots,w^{h+1}\\}$. It follows from
$w^{\prime}\in\operatorname{conv}(S_{k})$ that there exists
$\lambda\in[0,1]^{h+1}$ such that
$\sum_{j\in[h+1]}\lambda_{j}=1,\sum_{j\in[h+1]}\lambda_{j}w^{j}=w^{\prime}$.
Note that $S_{k}$ induces the supported function $f_{S_{k}}$, which has
supporting points $S_{k}$. This implies that
$f_{S_{k}}(w^{\prime})=\sum_{j\in[h+1]}\lambda_{j}f_{S_{k}}(w^{j})=\sum_{j\in[h+1]}\lambda_{j}f(w^{j})$.
By the convexity of $f^{\prime}$,
$f^{\prime}(w^{\prime})\leq\sum_{j\in[h+1]}\lambda_{j}f^{\prime}(w^{j})=\sum_{j\in[h+1]}\lambda_{j}f(w^{j})\leq
f_{S_{k}}(w^{\prime})\leq\max_{k}f_{S_{k}}(w^{\prime})$, which leads to a
contradiction. Thus, $\max_{k}f_{S_{k}}$ is the convex envelope of $f$ over
${\mathcal{Q}}$. ∎

The collection $\\{S_{k}\\}_{k}$ is called _envelope-inducing_ family in $Q$,
if the presupposition “$\\{P_{k}\\}_{k}$ is a triangulation” in Prop. 3 is
satisfied. Using the above result, we can construct an envelope-inducing
family for bivariate supermodular functions. Let

$S^{2}_{1}\coloneqq\\{00,10,01\\},S^{2}_{2}\coloneqq\\{11,10,01\\}.$ (15)

One can find that
$\operatorname{conv}(S^{2}_{1})=\\{(w_{1},w_{2})\in[0,1]^{2}:w_{1}+w_{2}\leq
1\\},\operatorname{conv}(S^{2}_{2})=\\{(w_{1},w_{2})\in[0,1]^{2}:w_{1}+w_{2}\geq
1\\}$ are two triangles in $[0,1]^{2}$. We have that

$\displaystyle f_{S^{2}_{1}}(w)=f(00)+(f(10)-f(00))w_{1}+(f(01)-f(00))w_{2},$
$\displaystyle
f_{S^{2}_{2}}(w)=f(11)+(f(01)-f(11))(1-w_{1})+(f(10)-f(11))(1-w_{2}).$

We show that these two affine functions define the convex envelope of $f$.

######  Theorem 4.

For $h=2$, $\\{S^{2}_{k}\\}_{k\in[2]}$ as in (15) is the envelope-inducing
family in $Q$.

###### Proof.

It is easy to see that, for all $k\in[2]$, $S^{2}_{k}$ is affinely independent
and $\\{\operatorname{conv}(S^{2}_{k})\\}_{k\in[2]}$ is a triangulation of
${\mathcal{U}}$. Therefore, it suffices to show that
$\\{S^{2}_{k}\\}_{k\in[2]}$ is facet-inducing, i.e.,
$f_{S^{2}_{1}},f_{S^{2}_{2}}$ are affine underestimators of $f$.

Case i. We note that, for all $w\in S^{2}_{1}=\\{00,10,01\\}$,
$f_{S^{2}_{1}}(w)=f(w).$ Note that $Q\smallsetminus S^{2}_{1}=\\{11\\}.$ It
follows from the definition of the affine function $f_{S^{2}_{1}}$ that

$f_{S^{2}_{1}}(11)=f_{S^{2}_{1}}(10)+(f_{S^{2}_{1}}(01)-f_{S^{2}_{1}}(00))=f(10)+(f(01)-f(00)).$

It follows from the supermodularity of $f$ that

$f(10)+(f(01)-f(00))\leq f(10)+(f(11)-f(10))=f(11).$

Thereby, $f_{S^{2}_{1}}$ underestimates $f$.

Case ii. We note that, for all $w\in S^{2}_{2}=\\{11,10,01\\}$,
$f_{S^{2}_{2}}(w)=f(w).$ Note that $Q\smallsetminus S^{2}_{2}=\\{00\\}.$ It
follows from the definition of the affine function $f_{S^{2}_{2}}$ that

$f_{S^{2}_{2}}(00)=f_{S^{2}_{2}}(10)-(f_{S^{2}_{1}}(11)-f_{S^{2}_{1}}(01))=f(10)+(f(11)-f(01)).$

It follows from the supermodularity of $f$ that

$f(10)-(f(11)-f(01))\leq f(10)-(f(10)-f(00))=f(00),$

which concludes the proof. ∎

###  5.3 Convexity and reverse-convexity

Our cutting plane algorithm can detect convexity/reverse-convexity of
signomial term sets. The detection is easily done by normalized DDC
formulations.

Denote by $e^{\ell}_{j}$ and $e^{h}_{j}$ the $j$-th unit vector in
$\mathbb{R}^{h}$ and $\mathbb{R}^{\ell}$, respectively. Then, we have the
following observations:

  1. i)

if ${\lVert\beta\rVert}_{1}=1,\gamma=0$, i.e., $\psi_{\beta}$ is concave and
$\psi_{\gamma}$ is 1, then ${\mathcal{S}}_{\mathrm{st}}$ is reverse-convex;

  2. ii)

if ${\lVert\beta\rVert}_{1}\leq 1,\gamma=e^{\ell}_{j}$ for some $j\in[\ell]$,
i.e., $\psi_{\beta}$ is concave and $\psi_{\gamma}$ is a linear univariate
function, then ${\mathcal{S}}_{\mathrm{st}}$ is reverse-convex;

  3. iii)

if $\beta=e^{h}_{j},{\lVert\gamma\rVert}_{1}\leq 1$ for some $j\in[h]$, i.e.,
$\psi_{\beta}$ is a linear univariate function and $\psi_{\gamma}$ is concave,
then ${\mathcal{S}}_{\mathrm{st}}$ is convex;

  4. iv)

if ${\lVert\beta\rVert}_{1}=0,{\lVert\gamma\rVert}_{1}=1$, i.e.,
$\psi_{\beta}$ is 1 and $\psi_{\gamma}$ is concave, then
${\mathcal{S}}_{\mathrm{st}}$ is convex.

We note that similar results are found in [17, 45]. The results in [17] are
proved by checking the negative/positive-semidefiniteness of the Hessian
matrix of a signomial term. According to the normalized DCC formulation, the
results are evident.

##  6 Computational results

In this section, we conduct computational experiments to assess the efficiency
of the proposed valid inequalities.

The MINLPLib dataset includes instances of MINLP problems containing signomial
terms, and some of these instances are SP problems. To construct our
benchmark, we select instances from MINLPLib that satisfy the following
criteria: (i) the instance contains signomial functions or polynomial
functions, (ii) the continuous relaxation of the instance is nonconvex. Our
benchmark consists of a diverse set of 251 instances in which nonlinear
functions consist of signomial and other functions. These problems come from
practical applications and can be solved by general purpose solvers.

Experiments are performed on a server with Intel Xeon W-2245 CPU @ 3.90GHz,
126GB main memory and Ubuntu 18.04 system. We use SCIP 8.0.3 [11] as a
framework for reading and solving problems as well as performing cut
separation. SCIP is integrated with CPLEX 22.1 as LP solver and IPOPT 3.14.7
as NLP solver.

We evaluate the efficiency of the proposed valid inequalities in four
different settings. In the first setting, denoted disable, none of the
proposed valid inequalities is applied. In the second setting, denoted oc,
only the outer approximation cuts are applied. The third setting, denoted ic,
applies only to the intersection cuts. The fourth setting combines both the oc
and ic settings by applying both cuts. We let SCIP’s default internal cuts
handle univariate signomial terms and multilinear terms. Our valid
inequalities only handle the other high-order signomial terms. The source
code, data, and detailed results can be found in our online repository:
github.com/lidingxu/ESPCuts.

Each test run uses SCIP with a particular setting to resolve an instance. To
solve the instances, we use the SCIP solver with its sBB algorithm and set a
time limit of 3600 seconds. In our benchmark, there are 150 instances
classified as _affected_ in which at least one of the settings oc, ic, and oic
settings adds cuts. Among the affected instances, there are 86 instances where
the default SCIP configuration (i.e., disable setting) runs for at least 500
seconds. Such instances are classified as _affected-hard_. For each test run,
we measure the runtime, the number of sBB search nodes, and the relative open
duality gap.

To aggregate the performance metrics for a given setting, we compute shifted
geometric means (SGMs) over our test set. The SGM for runtime includes a shift
of 1 second. The SGM for the number of nodes includes a shift of 100 nodes.
The SGM for relative distance includes a shift of 1$\%$. We also compute the
SGMs of the performance metrics over the subset of affected and affected-hard
instances. The performance results are shown in Table 1, where we also compute
the relative values of the SGMs of the performance metrics compared to the
disable setting. Our following analysis is based on the results of the
affected and affected-hard instances.

Setting | All | Affected | Affected-hard
---|---|---|---
solved | nodes | time | gap | solved | nodes | time | gap | solved | nodes | time | gap
disable | absolute | 138/251 | 6510.5 | 122.0 | 4.7% | 71/150 | 15592.4 | 253.6 | 5.7% | 7/86 | 175973.8 | 3600.0 | 26.7%
relative | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0
oc | absolute | 140/251 | 5954.1 | 118.0 | 4.5% | 73/150 | 13443.9 | 241.4 | 5.4% | 10/86 | 115262.3 | 2872.7 | 23.3%
relative | 0.91 | 0.97 | 0.97 | 0.86 | 0.95 | 0.95 | 0.65 | 0.8 | 0.87
ic | absolute | 140/251 | 6144.3 | 122.4 | 4.4% | 73/150 | 14081.5 | 252.1 | 5.2% | 10/86 | 128072.7 | 2994.1 | 22.0%
relative | 0.94 | 1.0 | 0.95 | 0.9 | 0.99 | 0.91 | 0.73 | 0.83 | 0.82
oic | absolute | 139/251 | 5934.6 | 117.7 | 4.6% | 72/150 | 13275.6 | 236.8 | 5.6% | 10/86 | 118054.1 | 2758.3 | 23.0%
relative | 0.91 | 0.96 | 0.99 | 0.85 | 0.93 | 0.98 | 0.67 | 0.77 | 0.86

Table 1: Summary of performance metrics on MINLPLib instances.

First, we note that the proposed valid inequalities lead to the successful
solution of 2 additional instances compared to the disable setting. The oc
setting solves 2 more instances than the disable setting.

The reductions in runtime and relative gap achieved by the oc setting are 5%
and 5%, respectively, for affected instances and 20% and 13%, respectively,
for affected-hard instances. The ic setting solves 2 more instances than the
disable setting. The reduction in runtime and relative gap achieved by the ic
setting is 1% and 9% for affected instances and 17% and 14% for affected-hard
instances, respectively. The oic setting resolves 1 additional instance
compared to the disable setting. The reduction in runtime and relative
distance achieved by the oic setting is 7% and 2%, respectively, for affected
instances and 23% and 14%, respectively, for affected-hard instances.

We note that the runtime does not provide much information about affected-hard
instances, since only 10 instances can be solved within 3600 seconds. For
these instances, the gap reduction is more useful to measure the reduction of
the search space by the proposed valid inequalities. However, for all affected
instances, the runtime is still important because it measures the speedup due
to the valid inequalities.

Second, we find that all cut settings have a positive effect on SCIP
performance, although the magnitude of the reduction varies. When we compare
the oc and ic settings, we find that the oc setting leads to a larger
reduction in runtime. This difference in runtime is due to the fact that
computing intersection cuts requires extracting a simplified cone from the LP
relaxation and applying bisection search along each ray of the cone. These
procedures require more computational resources compared to the construction
of outer approximation cuts.

On the other hand, the ic setting shows better performance in terms of
reducing gaps. Intersection cuts approximate the intersection of a signomial
term set with the simplicial cone, while outer approximation cuts approximate
the intersection of a signomial term set with a hypercube. Around the
relaxation point, the simplicial cone usually provides a better approximation
than the hypercube. Therefore, ic achieves a greater reduction in the relative
gap. However, the better simplicial conic approximation does yield a
significant improvement compared to the hypercubic approximation.

Finally, the oic setting combines both the oc and ic settings and achieves the
best reduction in runtime. However, for affected and affected-hard instances,
the setting shows different gap reduction results. In fact, the results for
affected-hard instances give more insight, since the goal of the valid
inequalities is to speed up convergence for hard instances. In this sense, the
oic setting achieves almost the best result, so it carries the best of both
valid inequalities. However, the improvement compared to each setting is not
significant.

In summary, the performances of the oc and ic settings are comparable. They
can lead to smaller duality gaps with less computation time, which is
desirable for solvers, and one can use either of them. Moreover, they do not
hurt each other.

##  7 Conclusion

In this paper we study valid inequalities for SP problems and propose two
types of valid linear inequalities: intersection cuts and outer approximation
cuts. Both are derived from normalized DCC formulations of signomial term
sets. First, we study general conditions for maximal ${\mathcal{S}}$-free
sets. We construct maximal signomial term-free sets from which we generate
intersection cuts. Second, we construct convex outer approximations of
signomial term sets within hypercubes. We provide extended formulations for
the convex envelopes of concave functions in the normalized DCC formulations.
Then we separate valid inequalities for the convex outer approximations by
projection. Moreover, when $h=2$, we use supermodularity to derive a closed-
form expression for the convex envelopes.

We present a comparative analysis of the computational results obtained with
the MINLPLib instances. This analysis demonstrates the effectiveness of the
proposed valid inequalities. The results show that intersection cuts and outer
approximation cuts have similar performance and their combination takes the
best of each setting. In particular, it is easy to implement outer
approximation cuts in general purpose solvers. In the future, we plan to
carefully optimize outer approximation cuts and develop them as an easy-to-use
plugin.

We currently deal with signomial terms explicitly present in the signomial
terms, but our results can be extended to deal with multiple signomial terms.
In the future, the proposed valid inequalities can approximate nonlinear
aggregations of constraints that define the signomial lift. Specifically,
given signomial constraints $\\{\psi_{\alpha^{i}}(x)=y_{i}\\}_{i\in[r]}$ with
any exponent vector $\zeta\in\mathbb{R}^{r}$, we can employ _signomial
aggregation_ to generate a new signomial constraint:
$\psi_{(\sum_{i\in[r]}\zeta_{i}\alpha^{i})}(x)=\psi_{\zeta}(y)$. This
constraint is valid for the signomial lift and encodes more variables and
terms. Next, we can apply the DCC reformulation to the constraints
$\psi_{(\sum_{i\in[r]}\zeta_{i}\alpha^{i})}(x)\leq\psi_{\zeta}(y)$ and
$\psi_{(\sum_{i\in[r]}\zeta_{i}\alpha^{i})}(x)\geq\psi_{\zeta}(y)$. Finally,
we can separate the proposed valid inequalities. As far as we know, the
signomial aggregation operator is not yet used for polynomial programming,
since it outputs a signomial constraint.

## Acknowledgments

We thank Fellipe Serrano for sharing his Ph.D. thesis with us [60]. We
appreciate the discussion with Antonia Chmiela, Mathieu Besançon, Stefan
Vigerske, and Ksenia Bestuzheva on SCIP. This publication was supported by the
“Integrated Urban Mobility” chair, which is supported by L’X - École
Polytechnique and La Fondation de l’École Polytechnique. Under no
circumstances do the partners of the Chair assume any liability for the
content of this publication, for which the author alone is responsible.

## Declarations

No conflicts of interest with the journal or funders.

## Appendix

###### Proof of Thm. 1.

It suffices to consider the case that ${\mathcal{C}}$ is a maximal
$\operatorname{epi}(g^{\prime}_{i})$-free set in ${\mathcal{G}}^{i}$.
W.l.o.g., we can assume that ${\mathcal{C}},{\mathcal{G}}^{i}$ are full-
dimensional in $\mathbb{R}^{I_{i}}$. Since
$\operatorname{epi}(g^{\prime}_{i})$ includes
$\operatorname{graph}(g^{\prime}_{i})$, ${\mathcal{C}}$, as an
$\operatorname{epi}(g^{\prime}_{i})$-free set, is also
$\operatorname{graph}(g^{\prime}_{i})$-free. First, we prove that
${\mathcal{C}}$ is a maximal $\operatorname{graph}(g^{\prime}_{i})$-free set
in ${\mathcal{G}}^{i}$. Assume, to aim at a contradiction, that
${\mathcal{C}}^{\prime}$ is a $\operatorname{graph}(g^{\prime}_{i})$-free set
that
${\mathcal{C}}\cap{\mathcal{G}}^{i}\subsetneq{\mathcal{C}}^{\prime}\cap{\mathcal{G}}^{i}$.
Suppose that
$\operatorname{epi}(g^{\prime}_{i})\cap\operatorname{int}({\mathcal{C}}^{\prime}\cap{\mathcal{G}}^{i})$
is not empty and contains $(x^{\prime}_{J_{i}},y^{\prime}_{i})$. As
${\mathcal{C}}$ is $\operatorname{epi}(g^{\prime}_{i})$-free, there exists a
point
$(x_{J_{i}},y_{i})\in\operatorname{int}({\mathcal{C}}\cap{\mathcal{G}}^{i})\subseteq\operatorname{int}({\mathcal{C}}^{\prime}\cap{\mathcal{G}}^{i})$
such that $(x_{J_{i}},y_{i})\in\operatorname{hypo}(g^{\prime}_{i})$. It
follows from the continuity of $g^{\prime}_{i}$ that there exists a point
$(x^{\ast}_{J_{i}},y^{\ast}_{i})\in\operatorname{graph}(g^{\prime}_{i})$ in
the line segment joining $(x_{J_{i}},y_{i})$ and
$(x^{\prime}_{J_{i}},y^{\prime}_{i})$. As
$\operatorname{int}({\mathcal{C}}^{\prime}\cap{\mathcal{G}}^{i})$ is convex,
we have that
$(x^{\ast}_{J_{i}},y^{\ast}_{i})\in\operatorname{int}({\mathcal{C}}^{\prime}\cap{\mathcal{G}}^{i})$,
which leads to a contradiction to
$\operatorname{graph}(g^{\prime}_{i})$-freeness of ${\mathcal{C}}^{\prime}$.
Therefore,
$\operatorname{epi}(g^{\prime}_{i})\cap\operatorname{int}({\mathcal{C}}^{\prime}\cap{\mathcal{G}}^{i})$
must be empty, so
${\mathcal{C}}^{\prime}\cap{\mathcal{G}}^{i}\subseteq\operatorname{hypo}(g^{\prime}_{i})$.
This means that ${\mathcal{C}}^{\prime}$ is also
$\operatorname{epi}(g^{\prime}_{i})$-free. However, note that
${\mathcal{C}}\cap{\mathcal{G}}^{i}\subsetneq{\mathcal{C}}^{\prime}\cap{\mathcal{G}}^{i}$,
this contradicts with the fact that ${\mathcal{C}}$ is a maximal
$\operatorname{epi}(g^{\prime}_{i})$-free set in ${\mathcal{G}}^{i}$.
Therefore, ${\mathcal{C}}$ is a maximal
$\operatorname{graph}(g^{\prime}_{i})$-free set in ${\mathcal{G}}^{i}$.
Secondly, we prove that $\bar{{\mathcal{C}}}$ is a maximal
${\mathcal{S}}_{\mathrm{lift}}$-free set in ${\mathcal{G}}$. Assume, to aim at
a contradiction, that there exists an ${\mathcal{S}}_{\mathrm{lift}}$-free set
$\bar{{\mathcal{D}}}$ in ${\mathcal{G}}$ such that
$\bar{{\mathcal{C}}}\cap{\mathcal{G}}\subsetneq\bar{{\mathcal{D}}}\cap{\mathcal{G}}$.
We look at their orthogonal projections on $\mathbb{R}^{I_{i}}$. It follows
from the decomposability that
${\mathcal{C}}\cap{\mathcal{G}}^{i}={\mathcal{C}}\cap\operatorname{proj}_{\mathbb{R}^{I_{i}}}({\mathcal{G}})=\operatorname{proj}_{\mathbb{R}^{I_{i}}}(\bar{{\mathcal{C}}}\cap{\mathcal{G}})\subseteq\operatorname{proj}_{\mathbb{R}^{I_{i}}}(\bar{{\mathcal{D}}}\cap{\mathcal{G}})$.
Denote
${\mathcal{D}}\coloneqq\operatorname{cl}(\operatorname{proj}_{\mathbb{R}^{I_{i}}}(\bar{{\mathcal{D}}}\cap{\mathcal{G}}))$,
which is a closed convex set in ${\mathcal{G}}^{i}$. Since
$\bar{{\mathcal{C}}}={\mathcal{C}}\times\mathbb{R}^{I^{c}_{i}}$,
${\mathcal{D}}$ must strictly include ${\mathcal{C}}\cap{\mathcal{G}}^{i}$.
Note that ${\mathcal{D}}$ is $\operatorname{graph}(g^{\prime}_{i})$-free.
Since ${\mathcal{C}}$ is a maximal $\operatorname{graph}(g^{\prime}_{i})$-free
set in ${\mathcal{G}}^{i}$, this implies that
${\mathcal{C}}\cap{\mathcal{G}}^{i}={\mathcal{D}}$, which leads to a
contradiction. ∎

###### Proof of Thm. 3.

Let ${\mathcal{C}}$ be a set satisfying the hypothesis. Suppose, to aim at a
contradiction, that there exists a closed convex set ${\mathcal{C}}^{\ast}$
such that ${\mathcal{C}}\subsetneq{\mathcal{C}}^{\ast}$ and
${\mathcal{C}}^{\ast}$ is an inner approximation of ${\mathcal{F}}$. Then,
there must exist an open ball $B$ such that
$B\subseteq{\mathcal{F}}\smallsetminus{\mathcal{C}}$ and
$B\subseteq{\mathcal{C}}^{\ast}$. Let $z^{\ast}$ be the center of $B$, so
$z^{\ast}\in\operatorname{int}({\mathcal{F}}\smallsetminus{\mathcal{C}})$.
W.l.o.g., we let
${\mathcal{C}}^{\ast}=\operatorname{conv}({\mathcal{C}}\cup\\{z^{\ast}\\})$,
which is a closed convex inner approximation of ${\mathcal{F}}$. Since
$z^{\ast}\notin{\mathcal{C}}$, by the hyperplane separation theorem, there
exists ${\lambda}\in\operatorname{dom}(\sigma_{{\mathcal{C}}})$ such that

${\lambda}\cdot z^{\ast}>\sigma_{{\mathcal{C}}}({\lambda}).$ (16)

For any such $\lambda$, by the hypothesis, there exists a point
$z^{\prime}\in\operatorname{bd}({\mathcal{F}})\cap\operatorname{bd}({\mathcal{C}})$
such that

${\lambda}\cdot z^{\prime}=\sigma_{{\mathcal{C}}}({\lambda}),$ (17)

and $z^{\prime}$ is an exposing point of ${\mathcal{C}}$. We want to show
that, for any
${\lambda^{\prime}}\in\operatorname{dom}(\sigma_{{\mathcal{C}}^{\ast}})$,
${\lambda^{\prime}}\cdot z^{\prime}<\sigma_{{\mathcal{C}}^{\ast}}({\lambda})$.
We consider the following three cases. First, we consider the case
$\lambda^{\prime}=\lambda$. Because $z^{\ast}\in{\mathcal{C}}^{\ast}$, by the
definition of support functions, we have that

${\lambda}\cdot z^{\ast}\leq\sup_{z\in{\mathcal{C}}^{\ast}}{\lambda}\cdot
z=\sigma_{{\mathcal{C}}^{\ast}}({\lambda}).$ (18)

It follows from (16), (17), and (18) that

$\displaystyle{\lambda}\cdot
z^{\prime}=\sigma_{{\mathcal{C}}}({\lambda})<{\lambda}\cdot
z^{\ast}\leq\sigma_{{\mathcal{C}}^{\ast}}({\lambda})=\sigma_{{\mathcal{C}}^{\ast}}({\lambda^{\prime}}).$
(19)

Second, we consider the case $\lambda^{\prime}=\rho\lambda$ for some $\rho>0$.
Since $\sigma_{{\mathcal{C}}^{\ast}}$ is positively homogeneous of degree 1,
it follows from (19) that $\lambda^{\prime}\cdot z^{\prime}={\rho\lambda}\cdot
z^{\prime}<\rho\sigma_{{\mathcal{C}}^{\ast}}({\lambda})=\sigma_{{\mathcal{C}}^{\ast}}({\lambda^{\prime}}).$
Last, we consider the case
${\lambda^{\prime}}\in\operatorname{dom}(\sigma_{{\mathcal{C}}^{\ast}})\smallsetminus\\{{\rho\lambda}\\}_{\rho>0}$.
By Lemma 2, $\sigma_{{\mathcal{C}}}\leq\sigma_{{\mathcal{C}}^{\ast}}$. By the
hypothesis that $z^{\prime}$ is an exposing point of ${\mathcal{C}}$, provided
that $\lambda^{\prime}\neq\rho\lambda$, we have that ${\lambda^{\prime}}\cdot
z^{\prime}<\sigma_{{\mathcal{C}}}({\lambda^{\prime}})\leq\sigma_{{\mathcal{C}}^{\ast}}({\lambda^{\prime}}).$
In summary, we have proved that for any
${\lambda^{\prime}}\in\operatorname{dom}(\sigma_{{\mathcal{C}}^{\ast}})$,
${\lambda^{\prime}}\cdot
z^{\prime}<\sigma_{{\mathcal{C}}^{\ast}}({\lambda^{\prime}})$. So by Lemma 2,
$z^{\prime}\in\operatorname{int}({\mathcal{C}}^{\ast})$. We find that
$z^{\prime}\in\operatorname{bd}({\mathcal{F}})\cap\operatorname{int}({\mathcal{C}}^{\ast})$.
This finding means a point near $z^{\prime}$ exists, which is in
${\mathcal{C}}^{\ast}$, but not in ${\mathcal{F}}$. Hence,
${\mathcal{C}}^{\ast}$ is not an inner approximation of ${\mathcal{F}}$, which
leads to a contradiction. ∎

###### Proof of Lemma 3.

Given $z\in\operatorname{dom}(f)$, $f(\rho z)=\rho^{d}f(z)$ is a real number
for any $\rho\in\mathbb{R}_{++}$, so
$\operatorname{int}(\operatorname{dom}(f))$ is a cone. Suppose that $f$ is
positive homogeneous of degree 1. For any $z\in\operatorname{dom}(f)$,
${\Xi^{f}_{\breve{z}}}(z)=f(\breve{z})+\nabla{f}(\breve{z})\cdot(z-\breve{z})=\nabla{f}(\breve{z})\cdot
z,$ where the second equation follows from Euler’s homogeneous function
theorem: $f(\breve{z})=\nabla{f}(\breve{z})\cdot\breve{z}$. For any
$z=\rho\breve{z}$ with $\rho\in\mathbb{R}_{++}$,
${\Xi^{f}_{\breve{z}}}(z)=\nabla{f}(\breve{z})\cdot\rho\breve{z}=\rho{\Xi^{f}_{\breve{z}}}(\breve{z})=\rho
f(\breve{z})=f(\rho\breve{z}),$ where the first and second equations follow
from the previous result, the third follows from that ${\Xi^{f}_{\breve{z}}}$
has the same value as $f$ at $\breve{z}$, and the last equation follows from
the homogeneity. ∎

###### Proof of Lemma 6.

We note that any hyperplane in $\mathbb{R}^{h+1}$ is uniquely determined by
$h+1$ affinely independent points. By definition, an affine underestimator
$a\cdot w+b$ of $f$ is a facet if and only if $a\cdot w+b\leq t$ is a facet of
the epigraph $\operatorname{epi}_{Q}(f)$. Then, the affine underestimator is a
facet, if and only if, there exists $h+1$ affinely independent points
$\\{(w^{i},t^{i})\\}_{i\in[h+1]}\subseteq\operatorname{epi}_{Q}(f)\subseteq\mathbb{R}^{h+1}$
such that for all $i\in[h+1]$, $a\cdot w^{i}+b=t^{i}$. Moreover, $t^{i}$ must
equal $f(w^{i})$, otherwise $a\cdot w^{i}+b=t^{i}<f(w^{i})$, which implies
that $a\cdot w+b\leq t$ does not underestimate $f$ at $w^{i}$. Therefore,
$w^{i}$ is the supporting point of $a\cdot w+b$. Note that
$\\{(w^{i},t^{i})\\}$ are affinely independent, if only if,
$\\{w^{i}\\}_{i\in[h+1]}$ are affinely independent. ∎

## References

  * [1] F. A. Al-Khayyal and J. E. Falk, Jointly constrained biconvex programming, Mathematics of Operations Research, 8 (1983), pp. 273–286.
  * [2] K. Andersen, Q. Louveaux, and R. Weismantel, An analysis of mixed integer linear sets based on lattice point free convex sets, Mathematics of Operations Research, 35 (2010), pp. 233–256.
  * [3] K. Andersen, Q. Louveaux, R. Weismantel, and L. A. Wolsey, Inequalities from two rows of a simplex tableau, in Integer Programming and Combinatorial Optimization, M. Fischetti and D. P. Williamson, eds., Berlin, Heidelberg, 2007, Springer Berlin Heidelberg, pp. 1–15.
  * [4] M. ApS, Mosek modeling cookbook, 2018.
  * [5] E. Balas, Intersection cuts—a new type of cutting planes for integer programming, Operations Research, 19 (1971), pp. 19–39.
  * [6] X. Bao, A. Khajavirad, N. V. Sahinidis, and M. Tawarmalani, Global optimization of nonconvex problems with multilinear intermediates, Mathematical Programming Computation, 7 (2015), pp. 1–37.
  * [7] A. Basu, S. S. Dey, and J. Paat, Nonunique lifting of integer variables in minimal inequalities, SIAM Journal on Discrete Mathematics, 33 (2019), pp. 755–783.
  * [8] P. Belotti, J. C. Góez, I. Pólik, T. K. Ralphs, and T. Terlaky, A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization, in Numerical Analysis and Optimization, Springer, 2015, pp. 1–35.
  * [9] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan, Mixed-integer nonlinear optimization, Acta Numerica, 22 (2013), pp. 1–131.
  * [10] P. Belotti, J. Lee, L. Liberti, F. Margot, and A. Wächter, Branching and bounds tighteningtechniques for non-convex minlp, Optimization Methods & Software, 24 (2009), pp. 597–634.
  * [11] K. Bestuzheva, A. Chmiela, B. Müller, F. Serrano, S. Vigerske, and F. Wegscheider, Global optimization of mixed-integer nonlinear programs with scip 8, arXiv preprint arXiv:2301.00587, (2023).
  * [12] D. Bienstock, C. Chen, and G. Muñoz, Intersection cuts for polynomial optimization, in Integer Programming and Combinatorial Optimization, A. Lodi and V. Nagarajan, eds., Cham, 2019, Springer International Publishing, pp. 72–87.
  * [13] M. R. Bussieck, A. S. Drud, and A. Meeraus, Minlplib—a collection of test models for mixed-integer nonlinear programming, INFORMS Journal on Computing, 15 (2003), pp. 114–119.
  * [14] S. Cafieri, J. Lee, and L. Liberti, On convex relaxations of quadrilinear terms, Journal of Global Optimization, 47 (2010), pp. 661–685.
  * [15] V. Chandrasekaran and P. Shah, Relative entropy relaxations for signomial optimization, SIAM Journal on Optimization, 26 (2016), pp. 1147–1173.
  * [16] R. Chares, Cones and interior-point algorithms for structured convex optimization involving powers and exponentials, PhD thesis, UCL-Université Catholique de Louvain Louvain-la-Neuve, Belgium, 2009.
  * [17] J.-S. Chen and C.-H. Huang, A note on convexity of two signomial functions, Journal of Nonlinear and Convex Analysis, 10 (2009), pp. 429–435.
  * [18] M. Conforti, G. Cornuéjols, and G. Zambelli, Integer programming, Springer International Publishing, Cham, 2014.
  * [19] M. Conforti, G. Cornuéjols, and G. Zambelli, Corner polyhedron and intersection cuts, Surveys in Operations Research and Management Science, 16 (2011), pp. 105–120.
  * [20] G. Cornuéjols, L. Wolsey, and S. Yıldız, Sufficiency of cut-generating functions, Mathematical Programming, 152 (2015), pp. 643–651.
  * [21] A. Costa and L. Liberti, Relaxations of multilinear convex envelopes: dual is better than primal, in International Symposium on Experimental Algorithms, Springer, 2012, pp. 87–98.
  * [22] A. Del Pia and R. Weismantel, Relaxations of mixed integer sets from lattice-free polyhedra, 4OR, 10 (2012), pp. 221–244.
  * [23] S. S. Dey and L. A. Wolsey, Lifting integer variables in minimal inequalities corresponding to lattice-free triangles, in Integer Programming and Combinatorial Optimization, A. Lodi, A. Panconesi, and G. Rinaldi, eds., Berlin, Heidelberg, 2008, Springer Berlin Heidelberg, pp. 463–475.
  * [24] M. Dressler and R. Murray, Algebraic perspectives on signomial optimization, SIAM Journal on Applied Algebra and Geometry, 6 (2022), pp. 650–684.
  * [25] R. J. Duffin, Linearizing geometric programs, SIAM review, 12 (1970), pp. 211–227.
  * [26] J. E. Falk and K. R. Hoffman, A successive underestimation method for concave minimization problems, Mathematics of Operations Research, 1 (1976), pp. 251–259.
  * [27] M. Fischetti, I. Ljubić, M. Monaci, and M. Sinnl, On the use of intersection cuts for bilevel optimization, Mathematical Programming, 172 (2018), pp. 77–103.
  * [28] M. Fischetti and M. Monaci, A branch-and-cut algorithm for mixed-integer bilinear programming, European Journal of Operational Research, 282 (2020), pp. 506–514.
  * [29] F. Glover, Convexity cuts and cut search, Operations Research, 21 (1973), pp. 123–134.
  * [30] R. E. Gomory, Some polyhedra related to combinatorial problems, Linear algebra and its applications, 2 (1969), pp. 451–558.
  * [31] T. He and M. Tawarmalani, A new framework to relax composite functions in nonlinear programs, Mathematical Programming, 190 (2021), pp. 427–466.
  * [32] T. He and M. Tawarmalani, Tractable relaxations of composite functions, Mathematics of Operations Research, 47 (2022), pp. 1110–1140.
  * [33] J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of convex analysis, Springer Berlin Heidelberg, Berlin, Heidelberg, 2001.
  * [34] F. Kılınç-Karzan, On minimal valid inequalities for mixed integer conic programs, Mathematics of Operations Research, 41 (2016), pp. 477–510.
  * [35] L. Liberti, Writing global optimization software, in Liberti and Maculan [36], pp. 211–262.
  * [36] L. Liberti and N. Maculan, eds., Global Optimization: from Theory to Implementation, Springer, Berlin, 2006.
  * [37] L. Liberti and C. C. Pantelides, Convex envelopes of monomials of odd degree, Journal of Global Optimization, 25 (2003), pp. 157–168.
  * [38] M.-H. Lin and J.-F. Tsai, Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems, European Journal of Operational Research, 216 (2012), pp. 17–25.
  * [39] M. Locatelli, Polyhedral subdivisions and functional forms for the convex envelopes of bilinear, fractional and other bivariate functions over general polytopes, Journal of Global Optimization, 66 (2016), pp. 629–668.
  * [40] M. Locatelli, Convex envelopes of bivariate functions through the solution of KKT systems, Journal of Global Optimization, 72 (2018), pp. 277–303.
  * [41] M. Locatelli and F. Schoen, On convex envelopes for bivariate functions over polytopes, Mathematical Programming, 144 (2014), pp. 65–91.
  * [42] J. Luedtke, M. Namazifar, and J. Linderoth, Some results on the strength of relaxations of multilinear functions, Mathematical programming, 136 (2012), pp. 325–351.
  * [43] A. Lundell, A. Skjäl, and T. Westerlund, A reformulation framework for global optimization, Journal of Global Optimization, 57 (2013), pp. 115–141.
  * [44] A. Lundell and T. Westerlund, Solving global optimization problems using reformulations and signomial transformations, Computers & Chemical Engineering, 116 (2018), pp. 122–134.
  * [45] C. D. Maranas and C. A. Floudas, Finding all solutions of nonlinearly constrained systems of equations, Journal of Global Optimization, 7 (1995), pp. 143–182.
  * [46] C. D. Maranas and C. A. Floudas, Global optimization in generalized geometric programming, Computers & Chemical Engineering, 21 (1997), pp. 351–369.
  * [47] G. P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems, Mathematical programming, 10 (1976), pp. 147–175.
  * [48] C. A. Meyer and C. A. Floudas, Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes, Journal of Global Optimization, 29 (2004), pp. 125–155.
  * [49] C. A. Meyer and C. A. Floudas, Trilinear monomials with positive or negative domains: Facets of the convex and concave envelopes, in Frontiers in Global Optimization, C. A. Floudas and P. Pardalos, eds., Boston, MA, 2004, Springer US, pp. 327–352.
  * [50] R. Misener and C. A. Floudas, ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations, Journal of Global Optimization, 59 (2014), pp. 503–526.
  * [51] R. Misener and C. A. Floudas, A framework for globally optimizing mixed-integer signomial programs, Journal of Optimization Theory and Applications, 161 (2014), pp. 905–932.
  * [52] S. Modaresi, M. R. Kılınç, and J. P. Vielma, Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, Mathematical Programming, 155 (2016), pp. 575–611, https://arxiv.org/abs/1302.2556.
  * [53] G. Muñoz and F. Serrano, Maximal quadratic-free sets, Mathematical Programming, 192 (2022), pp. 229–270.
  * [54] R. Murray, V. Chandrasekaran, and A. Wierman, Signomial and polynomial optimization via relative entropy and partial dualization, Mathematical Programming Computation, 13 (2021), pp. 257–295.
  * [55] T. T. Nguyen, J.-P. P. Richard, and M. Tawarmalani, Deriving convex hulls through lifting and projection, Mathematical Programming, 169 (2018), pp. 377–415.
  * [56] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. Flannery, Chapter 9: Root finding and nonlinear sets of equations, Book: Numerical Recipes: The Art of Scientific Computing, New York, Cambridge University Press,, 10 (2007).
  * [57] J.-P. P. Richard and S. S. Dey, The group-theoretic approach in mixed integer programming, in 50 Years of Integer Programming 1958-2008, Springer, 2010, pp. 727–801.
  * [58] A. D. Rikun, A convex envelope formula for multilinear functions, Journal of Global Optimization, 10 (1997), pp. 425–437.
  * [59] F. Serrano, Intersection cuts for factorable MINLP, in Integer Programming and Combinatorial Optimization, A. Lodi and V. Nagarajan, eds., Cham, 2019, Springer International Publishing, pp. 385–398.
  * [60] F. Serrano Musalem, On cutting planes for mixed-integer nonlinear programming, doctoral thesis, Technische Universität Berlin, Berlin, 2021.
  * [61] P. Shen, Linearization method of global optimization for generalized geometric programming, Applied Mathematics and Computation, 162 (2005), pp. 353–370.
  * [62] H. D. Sherali, Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta mathematica vietnamica, 22 (1997), pp. 245–270.
  * [63] E. Speakman and J. Lee, Quantifying double mccormick, Mathematics of Operations Research, 42 (2017), pp. 1230–1253.
  * [64] M. Tawarmalani, J.-P. P. Richard, and C. Xiong, Explicit convex and concave envelopes through polyhedral subdivisions, Mathematical Programming, 138 (2013), pp. 531–577.
  * [65] M. Tawarmalani and N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization, Mathematical programming, 103 (2005), pp. 225–249.
  * [66] D. M. Topkis, Supermodularity and complementarity, Princeton university press, Princeton, 2011.
  * [67] H. Tuy, Concave minimization under linear constraints with special structure, Optimization, 16 (1985), pp. 335–352.
  * [68] G. Xu, Global optimization of signomial geometric programming problems, European journal of operational research, 233 (2014), pp. 500–510.