1 Introduction

Many optimization problems involve both discrete and continuous variables and can be modelled as mixed-integer nonlinear programming problems (MINLPs) that arise from practical applications. Problems defined by convex functions are known as convex MINLPs, but they are still non-convex problems due to the presence of discrete variables. Over the past decades, convex MINLPs have become an active research area and several methods have been developed. Readers are invited to consult references [1–6] for more details.

Convex MINLP with continuously differentiable functions has been extensively studied, while convex but not continuously differentiable functions appear in optimization problems. Therefore, it is natural to study convex MINLP by relaxing the differentiability assumption. Motivated by this, we consider convex MINLP with partial differentiability, one version of relaxed differentiability, and use outer approximation method to establish an appropriate algorithm for solving it.

Duran and Grossmann [1] introduced outer approximation (OA) method to deal with a class of MINLPs, whose functions are dependent linearly on discrete variables. An extension of this OA method was given by Fletcher and Leyffer [2]. They generalized OA method to deal with one wider class of MINLPs defined by convex and continuously differentiable functions. This OA method was mainly studied in [7, 8] to equivalently reformulate convex MINLP as one MILP master program. Along the line given in [1, 2, 7, 8], we study the OA method for solving convex MINLP with partial differentiability and use subgradients and KKT conditions to establish one outer approximation algorithm for finding optimal solutions.

2 Preliminaries

Let \(\langle \cdot , \cdot \rangle \) denote the duality pairing between two elements of \({\mathbb {R}}^n\). Let \(\Omega \) be a closed and convex set of \({\mathbb {R}}^n\) and \(x\in \Omega \). We denote by \(T(\Omega , x)\) the contingent cone of \(\Omega \) at \(x\); that is, \(v\in T(\Omega , x)\) if and only if there exist a sequence \(\{v_k\}\) in \({\mathbb {R}}^n\) converging to \(v\) and a sequence \(t_k\) in \(]0, +\infty [\) decreasing to \(0\) such that \(x+t_kv_k\in \Omega \) for all \(k\in \mathbb {N}\). Let \(N(\Omega , x)\) denote the normal cone of \(\Omega \) at \(x\), that is

$$\begin{aligned} N(\Omega , x):=\{\gamma \in {\mathbb {R}}^n: \langle \gamma , z-x \rangle \le 0\ \ \mathrm{for\ all} \ z\in \Omega \}. \end{aligned}$$

It is known that normal cone and contingent cone are the polar of each other.

Let \(\psi : {\mathbb {R}}^n\times {\mathbb {R}}^p\rightarrow {\mathbb {R}}\) be a continuous and convex function and \((\bar{x}, \bar{y})\in {\mathbb {R}}^n\times {\mathbb {R}}^p\). Recall that a vector \((C, D)\in {\mathbb {R}}^{n\times p}\) is said to be a subgradient of \(\psi \) at \((\bar{x}, \bar{y})\) iff

$$\begin{aligned} \psi (x, y)\ge \psi (\bar{x}, \bar{y})+(C, D)^T\begin{pmatrix}x-\bar{x}\\ y-\bar{y}\end{pmatrix} \ \ \mathrm{for\ all} \ (x, y)\in {\mathbb {R}}^n\times {\mathbb {R}}^p. \end{aligned}$$

where \((C, D)^T\) is the transpose of matrix \((C, D)\). The set of all such subgradients, denoted by \(\partial \psi (\bar{x}, \bar{y})\), is said to be the subdifferential of \(\psi \) at \((\bar{x}, \bar{y})\). When \(\bar{y}\) is fixed, the subdifferential of \(\psi (\cdot , \bar{y})\) at \(\bar{x}\) is defined by

$$\begin{aligned} \partial \psi (\cdot , \bar{y})(\bar{x}):=\big \{C\in {\mathbb {R}}^n: \psi (x, \bar{y})\ge \psi (\bar{x}, \bar{y})+\langle C, x-\bar{x}\rangle \ \ \mathrm{for\ all} \ x\in {\mathbb {R}}^n\big \}. \end{aligned}$$

It is easy to verify that, for any \((C, D)\in \partial \psi (\bar{x}, \bar{y})\), one has \(C\in \partial \psi (\cdot , \bar{y})(\bar{x})\) and \(D\in \partial \psi (\bar{x}, \cdot )(\bar{y})\).

3 Main Results

In this section, we mainly study convex MINLP with partial differentiability and reformulate this MINLP as one equivalent MILP master program. Then by solving a finite sequence of relaxed MILP master programs, we establish one outer approximation algorithm for this MINLP.

Let us make some assumptions:

  1. (A1)

    \(X\) is a nonempty, compact and convex set in \({\mathbb {R}}^n\) and \(Y\) is a discrete set of \({\mathbb {R}}^p\), and functions \(f, g_i: {\mathbb {R}}^n\times {\mathbb {R}}^p\rightarrow {\mathbb {R}}\) \((i=1,\ldots ,m)\) are convex and continuous.

  2. (A2)

    Moreover \(f(\cdot , y)\) and \(g(\cdot , y)\) are differentiable functions on \({\mathbb {R}}^n\) for any fixed \(y\in Y\).

The class of convex MINLPs considered in the whole paper is defined as follows:

$$\begin{aligned} \min \limits _{x,\,y} \ f(x, y), \ \ \mathrm{s.t.}\ \ g(x, y)\le 0,\quad x\in X,\quad y\in Y. \end{aligned}$$
(1)

Let us set:

$$\begin{aligned} V:=\big \{y\in Y: g(x, y)\le 0\ \ \mathrm{for\ some}\ x\in X\big \} \end{aligned}$$

is the set of all discrete assignments that give rise to feasible subproblems. For any fixed \(y\in Y\), we consider the following subproblem \(P(y)\):

$$\begin{aligned} P(y) \quad \quad \min \limits _{x} \ f(x, y)\ \ \mathrm{s.t.}\ \ g(x, y)\le 0,\quad x\in X. \end{aligned}$$

For the equivalent reformulation of problem (P), we assume that problem (P) satisfies the following Slater constraint qualification (A3):

  1. (A3)

    for any \(y\in Y\) producing feasible subproblem \(P(y)\), the following Slater constraint qualification holds:

    $$\begin{aligned} g(\hat{x}, y)<0\ \ { for\ some}\ \hat{x}\in X. \end{aligned}$$

For the convex MINLP, whose functions are continuously differentiable, Fletcher and Leyffer [2] and Bonami et al. [7] used gradients and first-order Taylor expansion to linearly approximate functions \(f, g\) and established one equivalent MILP master program with the help of KKT conditions. Under the partial differentiability assumption, we substitute gradients with subgradients and equivalently reformulate problem (P) of (1) along the line given in [2, 7].

Let \(y_j\in V\) be fixed and let \(x_j\) be an optimal solution to \(P(y_j)\). Take any subgradients \((A_j, B_j)\in \partial f(x_j, y_j)\), \((C_j^i, D_j^i)\in \partial g_i(x_j, y_j)\) for all \(i=1,\cdots ,m\) and set \(C_j:=(C_j^1,\ldots ,C_j^m), D_j:=(D_j^1,\ldots ,D_j^m)\). We first study the following problem:

$$\begin{aligned} LP(x_j, y_j) \left\{ \begin{array}{l} \min \limits _{x} \ \ f(x_j, y_j)+\langle (A_j, B_j),(x-x_j,0)^T\rangle \\ \mathrm{s.t.} \ \ \ g(x_j, y_j)+\langle (C_j, D_j),(x-x_j,0)^T\rangle \le 0, \\ \ \ \ \ \ \ \ x\in X. \end{array} \right. \end{aligned}$$
(2)

The following theorem establishes the equivalence between \(LP(x_j, y_j)\) and \(P(y_j)\). This equivalence plays a key role in the reformulation of problem (P).

Theorem 3.1

Let \(LP(x_j, y_j)\) be defined as (2). Then \(x_j\) is one optimal solution of \(LP(x_j, y_j)\), and \(f(x_j, y_j)\) is the optimal value of \(LP(x_j, y_j)\).

Proof

In order to prove Theorem 3.1, it suffices to show that

$$\begin{aligned} (A_j, B_j)^T \begin{pmatrix} x-x_j\\ 0 \end{pmatrix} \ge 0,\ \ \forall x\in X\ \mathrm{with}\ g(x_j, y_j)+(C_j, D_j)^T \begin{pmatrix} x-x_j\\ 0 \end{pmatrix}\le 0. \end{aligned}$$
(3)

Let \(x\in X\) be such that

$$\begin{aligned} g(x_j, y_j)+(C_j, D_j)^T \begin{pmatrix} x-x_j\\ 0 \end{pmatrix}\le 0. \end{aligned}$$
(4)

Using assumption (A2), one has that \( A_j=\triangledown _xf(x_j, y_j)\) and \(C_j^i=\triangledown _xg_i(x_j, y_j)\) for all \(i=1,\ldots ,m\). This and (4) imply that

$$\begin{aligned} (A_j, B_j)^T \begin{pmatrix} x-x_j\\ 0 \end{pmatrix}=\langle \triangledown _xf(x_j, y_j), x-x_j\rangle \end{aligned}$$

and

$$\begin{aligned} g_i(x_j, y_j)+\langle \triangledown _xg_i(x_j, y_j), x-x_j\rangle \le 0,\ \forall i=1,\ldots ,m. \end{aligned}$$
(5)

Noting that \(x_j\) solves \(P(y_j)\) and the Slater constraint qualification for \(g(\cdot , y_j)\) holds, it follows from KKT conditions that there exist \((\lambda _1,\ldots , \lambda _m)\in {\mathbb {R}}^m_+\) and \(\gamma \in N(X, x_j)\) such that \(\lambda _ig_i(x_j, y_j)=0\) \((\forall i=1,\ldots ,m)\) and

$$\begin{aligned} \triangledown _xf(x_j, y_j)+\sum _{i\in I(x_j)}\lambda _i\triangledown _xg_i(x_j, y_j)+\gamma =0 \end{aligned}$$
(6)

where \(I(x_j):=\big \{i\in \{1,\ldots , m\}: g_i(x_j, y_j)=0\big \}\). Using (4) and (5), one has

$$\begin{aligned} \langle \triangledown _xg_i(x_j, y_j), x-x_j\rangle \le 0, \ \ \forall i\in I(x_j). \end{aligned}$$
(7)

Since \(x-x_j\in T(X, x_j)\) by the convexity of \(X\), it follows from (6), (7) and \(\gamma \in N(X, x_j)\) that

$$\begin{aligned} \triangledown _xf(x_j, y_j)^T(x-x_j)=-\sum _{i\in I(x_j)}\lambda _i\triangledown _xg_i(x_j, y_j)^T(x-x_j)-\gamma ^T(x-x_j)\ge 0. \end{aligned}$$

Hence (3) holds. The proof is complete. \(\square \)

Let us set

$$\begin{aligned} T:=\big \{j: P(y_j)\ \mathrm{is \ feasible\ and } \ x_j\ \mathrm{is\ an \ optimal\ solution\ to}\ P(y_j)\big \}. \end{aligned}$$

For any \(j\in T\), take any subgradients \((A_j,B_j)\in \partial f(x_j, y_j), (C_j^i,D_j^i)\in \partial g_i(x_j, y_j)\) for all \(i=1,\ldots , m\) and set \(C_j:=(C_j^1,\ldots ,C_j^m), D_j:=(D_j^1,\ldots ,D_j^m)\). We consider the following MILP master program \((M_V)\):

$$\begin{aligned} (M_V)\left\{ \begin{array}{l} \min \limits _{x,y,\eta }\ \ \eta \\ \mathrm{s.t.}\ \ \ \, f(x_j, y_j)+(A_j, B_j)^T\begin{pmatrix}x-x_j\\ y-y_j\end{pmatrix}\le \eta \ \ \forall j\in T,\ \ \\ \ \ \ \ \ \ \ g(x_j, y_j)+(C_j, D_j)^T\begin{pmatrix}x-x_j\\ y-y_j\end{pmatrix}\le 0\ \ \forall j\in T,\\ \ \ \ \ \ \ \ x\in X, y\in V\ \mathrm{discrete \ variable}. \end{array} \right. \end{aligned}$$
(8)

Theorem 3.2

Master program \((M_V)\) in (8) and problem (1) are equivalent in the sense that they have the same optimal value and that the optimal solution \((\bar{x}, \bar{y})\) to problem (1) corresponds to the optimal solution \(( \bar{x}, \bar{y}, \bar{\eta })\) to \((M_V)\) with \(\bar{\eta }=f(\bar{x}, \bar{y})\).

For reformulating the problem (1) completely, it only suffices to represent suitably the constraint \(y\in V\). As pointed out by Fletcher and Leyffer [2] and Bonami et al. [7], it is necessary to include information from infeasible subproblems and then exclude discrete assignments producing infeasible subproblems.

Let \(y_l\in Y\) be such that \(P(y_l)\) is infeasible and let \(J_l\) be one subset of \(\{1,\ldots ,m\}\) such that there is some \(\bar{x}\in X\) satisfying

$$\begin{aligned} g_i(\bar{x}, y_l)< 0,\ \ \forall i\in J_l. \end{aligned}$$
(9)

Denote \(J_l^{\bot }:=\{1,\ldots ,m\}\backslash J_l\). To detect the infeasibility, we study the following nonlinear program

$$\begin{aligned} F(y_l)\left\{ \begin{array}{l} \min \limits _{x} \ \ \sum \limits _{i\in J_l^{\bot }}[g_i(x, y_l)]_+\\ \mathrm{s.t.}\ \ \ g_i(x, y_l)\le 0\ \ \forall i\in J_l,\\ \ \ \ \ \ \ \ x\in X, \end{array} \right. \end{aligned}$$
(10)

where \([g(x, y_l)]_+:=\max \{g(x, y_l), 0\}\).

Theorem 3.3

Let \(y_l\in Y\) be such that \(P(y_l)\) is infeasible and \(x_l\) solve nonlinear program \(F(y_l)\). Then for any subgradients \((C_l^i, D_l^i)\in \partial g_i(x_l, y_l)(\forall i=1,\ldots ,m)\), \(y_l\) is infeasible to the following constraint

$$\begin{aligned} \begin{array}{l} g_i(x_l, y_l)+(C_l^i, D_l^i)^T\begin{pmatrix}x-x_l\\ y-y_l\end{pmatrix}\le 0, \ \ \forall i\in J_l^{\bot }\cup J_l,\\ x\in X, y\in Y. \end{array} \end{aligned}$$

Proof

Since \(X\) is compact and \(g\) is continuous, one has \(\sum _{i\in J_l^{\bot }}[g_i(x_l, y_l)]_+>0\). Noting that \((C_l^i, D_l^i)\in \partial g_i(x_l, y_l)(\forall i=1,\ldots ,m)\), it follows that

$$\begin{aligned} C_l^i=\triangledown _xg_i(x_l, y_l), \ \ \forall i\in \{1,\ldots , m\}. \end{aligned}$$
(11)

Suppose to the contrary that there exists \(\hat{x}\in X\) such that

$$\begin{aligned} g_i(x_l, y_l)+\langle \triangledown _xg_i(x_l, y_l), \hat{x}-x_l\rangle \le 0, \ \ \forall i\in J_l^{\bot }\cup J_l. \end{aligned}$$
(12)

Since \(x_l\) solves \(F(y_l)\) and (9) holds, by KKT conditions, there exist \(\lambda _i\ge 0\) such that \(\lambda _ig_i(x_l, y_l)=0\) \((\forall i\in J_l)\) and

$$\begin{aligned} 0\in \sum _{i\in J_l^{\bot }}\partial [g_i(\cdot , y_l)]+(x_l)+\sum _{i\in J_l}\lambda _i\triangledown _xg_i(x_l, y_l)+ N(X, x_l). \end{aligned}$$
(13)

Denote \(J^1:=\{i\in J_l^{\bot }: g_i(x_l, y_l)=0\}\) and \(J^2:=\{i\in J_l^{\bot }: g_i(x_l, y_l)>0\}\). By virtue of [9, Theorem 2.4.18] and (13), there exist \(t_i\in [0, 1](i\in J^1)\) and \(\gamma \in N(X, x_l)\) such that

$$\begin{aligned} \sum _{i\in J^1}t_i\triangledown _xg_i(x_l, y_l)+\sum _{i\in J^2}\triangledown _xg_i(x_l, y_l)+\sum _{i\in J_l}\lambda _i\triangledown _xg_i(x_l, y_l)+\gamma =0. \end{aligned}$$
(14)

Let \(t_i\equiv 1\) for all \(i\in J^2\). Using (12) and (14), one has

$$\begin{aligned} 0&\ge \sum _{i\in J^1\cup J^2}t_ig_i(x_l, y_l)+\Big (\sum _{i\in J^1\cup J^2}t_i\triangledown _xg_i(x_l, y_l)+\sum _{i\in J_l}\lambda _i\triangledown _xg_i(x_l, y_l)+\gamma \Big )^T(\hat{x}-x_l)\\&\ge \sum _{i\in J^2}g_i(x_l, y_l)=\sum _{i\in J^{\bot }_l}[g_i(x_l, y_l)]_+, \end{aligned}$$

which contradicts \(\sum _{i\in J_l^{\bot }}[g_i(x_l, y_l)]_+>0\). The proof is complete. \(\square \)

Let us set

$$\begin{aligned} S:=\big \{l: P(y_l)\ \mathrm{is \ infeasible\ and}\ x_l\ \mathrm{solves}\ F(y_l)\big \}. \end{aligned}$$

Using Theorem 3.3, we obtain the following theorem which enables us to eliminate discrete assignments producing infeasible subproblems.

Theorem 3.4

Let \(l\in S\) and take any subgradients \((C_l^i, D_l^i)\in \partial g_i(x_l, y_l)\) for all \(i=1,\ldots ,m\). Then the following constraints

$$\begin{aligned} g(x_l, y_l)+(C_l, D_l)^T\begin{pmatrix}x-x_l\\ y-y_l\end{pmatrix}\le 0, \ \ \forall l\in S \end{aligned}$$
(15)

exclude all discrete assignments \(y_l\in Y\) satisfying \(P(y_l)\) is infeasible.

From Theorem 3.4, we add linearization from \(F(y_l)\) where \(P(y_l)\) is infeasible to correctly represent the constraints \(y\in V\) in (8) and give rise to the MILP master program (MP) that is equivalent to problem (1).

For any \(j\in T\), take any subgradients \((A_j, B_j)\in \partial f(x_j, y_j), (C_j^i, D_j^i)\in \partial g_i(x_j, y_j)\) for all \(i=1,\ldots ,m\) and set \(C_j:=(C_j^1,\ldots ,C_j^m), D_j:=(D_j^1,\ldots ,D_j^m)\), while for any \(l\in S\), take any subgradients \((C_l^i, D_l^i)\in \partial g_i(x_l, y_l)\) for all \(i=1,\ldots ,m\) and set \(C_l:=(C_l^1,\ldots ,C_l^m), D_l:=(D_l^1,\ldots ,D_l^m)\). We consider the following MILP master problem:

$$\begin{aligned} \mathrm{(MP)}\left\{ \begin{array}{l} \min \limits _{x,y,\eta } \ \ \eta \\ \mathrm{s.t.}\ \ \ \, f(x_j, y_j)+(A_j, B_j)^T\begin{pmatrix}x-x_j\\ y-y_j\end{pmatrix}\le \eta \ \ \forall j\in T,\ \ \\ \ \ \ \ \ \ \ g(x_j, y_j)+(C_j, D_j)^T\begin{pmatrix}x-x_j\\ y-y_j\end{pmatrix}\le 0\ \ \forall j\in T,\\ \ \ \ \ \ \ \ g(x_l, y_l)+(C_l, D_l)^T\begin{pmatrix}x-x_l\\ y-y_l\end{pmatrix}\le 0\ \ \forall l\in S,\\ \ \ \ \ \ \ \ x\in X, y\in Y\ \mathrm{discrete \ variable}. \end{array} \right. \end{aligned}$$
(16)

Theorem 3.5

Master program (MP) in (16) is equivalent to problem (1) in the sense that they have the same optimal value and that the optimal solution \((\bar{x}, \bar{y})\) to problem (1) corresponds to the optimal solution \((\bar{x}, \bar{y}, \bar{\eta })\) to (MP) with \(\bar{\eta }=f(\bar{x}, \bar{y})\).

Remark 3.1

As one extension of [2, Theorem1] and [7, Theorem1], Theorem 3.5 shows that the OA method can be used to equivalently reformulate problem (1) and any optimal solution of problem (1) is that of (MP) in (16). However, the converse may not hold necessarily. Consider the following MINLP:

$$\begin{aligned} \begin{array}{l} \min \limits _{x, y} \ \ f(x, y):=x_2,\\ \mathrm{s.t.}\ \ \ \, g(x, y):=x_1^2+x_2^2+|y|-2\le 0\\ \ \ \ \ \ \ \ \ x=(x_1, x_2)\in [-1,1]\times [-2,2], \\ \ \ \ \ \ \ \ \ y\in \{-1, 0, 1, 3\}. \end{array} \end{aligned}$$
(17)

This convex MINLP satisfies assumptions (A1)–(A3) and has the optimal value \(-\sqrt{2}\). Note that

$$\begin{aligned} \partial g \left( \left( 0,-\sqrt{2} \right) ,0 \right) = \left\{ \left( 0,-2\sqrt{2} \right) \right\} \times [-1,1]. \end{aligned}$$

By taking any \(t\in [-1,1]\) and using the reformulation as (16), problem (17) can be equivalently rewritten as

$$\begin{aligned} \begin{array}{l} \min \limits _{x, y, \eta } \ \ \eta \\ \mathrm{s.t}\ \ \ \ x_2\le \eta ,\\ \ \ \ \ \ \ \ -2\sqrt{2}x_2-4+ty\le 0,\\ \ \ \ \ \ \ \ -2x_2+y-3\le 0,\\ \ \ \ \ \ \ \ -2x_2-y-3\le 0,\\ \ \ \ \ \ \ \ 1+y-3\le 0,\\ \ \ \ \ \ \ \ x=(x_1, x_2)\in [-1,1]\times [-2,2], \\ \ \ \ \ \ \ \ y\in \{-1, 0, 1, 3\}. \end{array} \end{aligned}$$
(18)

Clearly for any \(x_1\not =0\), \((x,y,\eta )= \left( \left( x_1, -\sqrt{2} \right) , 0, -\sqrt{2} \right) \) is an optimal solution to problem (18), but \((x,y)= \left( \left( x_1, -\sqrt{2} \right) , 0 \right) \) is infeasible to problem (17).

Now, by solving relaxations of master program (MP) in (16), we formally state the outer approximation algorithm for problem (1) as follow:

Algorithm 1

(Outer approximation algorithm for problem (1))

Step 1. :

Given an initial discrete variable \(y_1\in Y\), set \(\mathrm{UBD}^0:=+\infty \), \(T_0=S_0:=\emptyset \) and let \(k:=1\).

Step 2. :

Solve subproblem \(P(y_k)\) and let the solution be \(x_k\); or solve nonlinear program \(F(y_k)\) if \(P(y_k)\) is infeasible and let the solution be \(x_k\). If \(P(y_k)\) is feasible, set \(T_k:=T_{k-1}\cup \{k\}, S_k:=S_{k-1}\) and \(UBD^k:=\min \{f(x_k, y_k), UBD^{k-1}\}\); otherwise set \(T_k:=T_{k-1}, S_k:=S_{k-1}\cup \{k\}\) and \(UBD^k:=UBD^{k-1}\).

Step 3. :

If \(k\in T_k\), take any subgradients \((A_k, B_k)\in \partial f(x_k, y_k)\), \((C_k^i, D_k^i)\in \partial g_i(x_j, y_j)(\forall i=1,\ldots ,m)\) and set \(C_k\!:=\!(C_k^1,\ldots ,C_k^m), D_k:=(D_k^1,\ldots ,D_k^m)\); otherwise (\(k\in S_k\)), take any subgradients \((C_k^i, D_k^i)\in \partial g_i(x_j, y_j)(\forall i=1,\ldots ,m)\) and set \(C_k:=(C_k^1,\ldots ,C_k^m), D_k:=(D_k^1,\ldots ,D_k^m)\). Solve the following relaxed MILP master program \(MP^k\):

$$\begin{aligned} MP^k\left\{ \begin{array}{l} \min \limits _{x,y,\eta } \ \ \eta \\ \mathrm{s.t.}\ \ \ \, \eta <UBD^k\\ \ \ \ \ \ \ \ f(x_j, y_j)+(A_j, B_j)^T\begin{pmatrix}x-x_j\\ y-y_j\end{pmatrix}\le \eta \ \ \forall j\in T_k,\ \ \\ \ \ \ \ \ \ \ g(x_j, y_j)+(C_j, D_j)^T\begin{pmatrix}x-x_j\\ y-y_j\end{pmatrix}\le 0\ \ \forall j\in T_k,\\ \ \ \ \ \ \ \ g(x_l, y_l)+(C_l, D_l)^T\begin{pmatrix}x-x_l\\ y-y_l\end{pmatrix}\le 0\ \ \forall l\in S_k,\\ \ \ \ \ \ \ \ x\in X, y\in Y\ \mathrm{discrete \ variable}. \end{array} \right. \end{aligned}$$
(19)

Denote \((\hat{x}, \hat{y}, \hat{\eta })\) the optimal solution to \(MP^k\). Let \(y_{k+1}:=\hat{y}\), obtaining a new discrete assignment, and set \(k:=k+1\). Return to Step 2 until \(MP^{k+1}\) is infeasible.

Remark 3.2

Constraint \(\eta <UBD^{k}\) in \(MP^k\) (19) is used to prevent any \(y_j\) \((j\in T_k)\) from being the optimal solution to the relaxed master program \(MP^k\). Further, as pointed out in [2], constraint \(\eta <UBD^{k}\) would be substituted with \(\eta \le UBD^{k}-\varepsilon \) in practice for some tolerance parameter \(\varepsilon >0\).

The following theorem shows that Algorithm 1 stated above is able to detect feasibility or infeasibility of problem (1) and the procedure terminates after a finite number of steps under the assumption of finite discrete assignments. The proof, similar to that of [2, Theorem1], can be obtained by using Theorems 3.1 and 3.3.

Theorem 3.6

Suppose assumptions (A1)–(A3) hold and the cardinality of discrete set \(Y\) is finite. Then either problem (1) is infeasible or Algorithm 1 terminates at \(k_0\)-th step for some \(k_0\in \mathbb {N}\) and there exists \(j_0\in T_{k_0-1}\cup \{k_0\}\) such that \(f(x_{j_0}, y_{j_0})\) equals the optimal value of problem (1).

4 Conclusions

The work in this paper is devoted to the study of the convex MINLP by relaxing the differentiability assumption and the construction of outer approximation algorithm for solving such MINLP. With the assumption of partial differentiability, the OA method and subgradients obtained from KKT conditions are used to linearize convex functions and reformulate this MINLP as an equivalent MILP master program. An example showing that some optimal solution of the reformulated master program is infeasible to the MINLP problem is given. By solving a finite sequence of subproblems and relaxed master programs, the outer approximation algorithm has been established to find optimal solutions of this MINLP. The convergence after a finite number of steps is also proved. This work is an extension of the OA method for solving convex MINLP under relaxed differentiability assumptions.