# Reverse Bridge Theorem under Constraint Partition

Authors: Minghao Yin; Tingting Zou; Wenxiang Gu
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

Reverse bridge theorem (RBTH) has been proved to be both a necessary and sufficient condition for solving Nonlinear programming problems. In this paper, we first propose three algorithms for finding constraint minimum points of continuous, discrete, and mixed-integer nonlinear programming problems based on the reverse bridge theorem. Moreover, we prove that RBTH under constraint partition is also a necessary and sufficient condition for solving nonlinear programming problems. This property can help us to develop an algorithm using RBTH under constraints. Specifically, the algorithm first partitions mixed-integer nonlinear programming problems (MINLPs) by their constraints into some subproblems in similar forms, then solves each subproblem by using RBTH directly, and finally resolves those unsatisfied global constraints by choosing appropriate penalties. Finally, we prove the soundness and completeness of our algorithm. Experimental results also show that our algorithm is effective and sound.


---

## Body

## 1. Introduction

Nonlinear programming problems (NLPs) play an important role in both manufacturing systems and industrial processes and have been widely used in the fields of operations research, planning and scheduling, optimal control, engineering designs, and production management [1–7]. Due to its significance in both academic and engineering applications, different kinds of approaches have been proposed to solve NLPs and obtained some achievements. In [8], we propose a general approach, called reverse bridge theorem (RBTH), which can significantly reduce the complexity in solving NLPs. We also prove in [8] that RBTH is a necessary and sufficient condition for solving NLPs. Compared to other methods such as extended saddle-point condition (ESPC) [9, 10], RBTH has two obvious advantages. Firstly, the core inequality of RBTH is formed by only one subinequality and one subequality; thus RBTH is easier to handle. Secondly, RBTH does not need extra conditions for solving NLPs and therefore can be used more widely. However, in [8] we do not provide any concrete algorithm to solve NLPs using RBTH. Consequently, in this paper, we first present three algorithms for solving discrete nonlinear programming problems (DNLPs), continuous nonlinear programming problems (CNLPs), and mixed-integer nonlinear programming problems (MINLPs), respectively. After that, we prove the soundness and completeness of these algorithms.On the other hand, constraint partition has been proved to be an attractive approach for solving large-scale problems in NLPs recently [11–18]. Based on the regular constraint structure of a problem instance, we can cluster its constraints into multiple loosely coupled partitions. Accordingly, the original problem can be partitioned by its constraints into several subproblems, each of which is a relaxation of the problem and can be solved in exponentially less time than the original problem. In Section 4 of this paper, we first prove that RBTH under constraint partition is a necessary and sufficient condition for solving nonlinear programming problems. Then we further prove that this necessary and sufficient condition can be rewritten into N+2 necessary conditions. This property can help us to develop a novel algorithm using RBTH under constraint partition. Specifically speaking, the algorithm firstly partitions a nonlinear programming problem into several relaxed subproblems, each of which is then solved by using RBTH. After that the algorithm resolves the unsatisfied global constraints by choosing appropriate penalties. Finally, we prove that this algorithm is sound and complete.The paper is organized as follows. After this introduction, we recall some basic notions and related work in Section2. Then in Section 3, we introduce how to solve nonlinear programming problems using RBTH. In Section 4, we show how to solve nonlinear programming problems using RBTH under constraint partition. In Section 5, simulations and comparisons based on some benchmarks are carried out, which show that our algorithm is both effective and efficient. In the last section we conclude this paper.


## 2. Basic Concepts and Related Work

In this section, firstly we recall some basic concepts that will be used in this paper. For details, we refer to [1–7].


### 2.1. Basic Concepts

Generally speaking, nonlinear programming problems can be divided into three categories, that is, continuous nonlinear programming problems, discrete nonlinear programming problems, and mixed-integer nonlinear programming problems. The general forms of these nonlinear programming problems are as follows:Definition 2.1 (Continuous Nonlinear Programming).
A continuous nonlinear programming problem (CNLP) is defined as(2.1)(Pc):minxf(x)wherex=(x1,x2,…,xv)T∈ℜv,subjecttoh(x)=(h1(x),h2(x),…,hm(x))T=0,g(x)=(g1(x),g2(x),…,gr(x))T≤0,
where x∈ℜv are continuous variables. The function f is assumed to be continuous and differentiable, and the constraint functions  g and h can be discontinuous, nondifferentiable, and not in closed form.Definition 2.2 (Discrete Nonlinear Programming).
A discrete nonlinear programming problem (DNLP) is defined as(2.2)(Pd):minyf(y)wherey=(y1,y2,…,yw)T∈ℜw,subjecttoh(y)=(h1(y),h2(y),…,hm(y))T=0,g(y)=(g1(y),g2(y),…,gr(y))T≤0,
where  y∈ℜw are discrete variables. The functions f, g,  and h may be assumed discontinuous, nondifferentiable, or not even given in closed form.Definition 2.3 (Mixed-Integer Nonlinear Programming).
A mixed-integer nonlinear programming problem (MINLP) is defined as(2.3)(Pm):minx,yf(x,y)subjecttoh(x,y)=(h1(x,y),h2(x,y),…,hm(x,y))T=0,g(x,y)=(g1(x,y),g2(x,y),…,gr(x,y))T≤0,
where x∈ℜv are continuous variables, and y∈ℜw are discrete variables. The function f is bounded below and is assumed to be continuous and differentiable with respect to x, and the constraint functions  g  and h are general functions that can be discontinuous, non-differentiable, or not even given in closed form.The aims of solving continuous, discrete, and mixed-integer nonlinear programming problems are, respectively, to find the constrained minima with respect to neighbourhood of a continuous pointx, a discrete point y, and a mixed point (x,y).Definition 2.4 (Constrained Minimum of CNLP).
Pointx* is a constrained minimum of Pc (CMc), if x* is feasible and f(x*)≤f(x) for all feasible x in the neighbourhood of x*, that is, x∈Nc(x*)={x′:∥x′-x*∥≤ξandξ→0}.Definition 2.5 (Constrained Minimum of DNLP).
Pointy* is a constrained minimum of Pd (CMd), if y* is feasible and f(y*)≤f(y) for all feasible  y in a neighbourhood of y*.Definition 2.6 (Constrained Minimum of MINLP).
Point(x*,y*) is a constrained minimum of Pm (CMm), if (x*,y*) is feasible and f(x*,y*)≤f(x,y) for all feasible (x,y) in a neighbourhood of (x*,y*).


### 2.2. Related Work

In the following, we introduce some existing methods for solving nonlinear programming problems.


#### 2.2.1. Necessary Karush-Kuhn-Tucker (KKT) Condition [18, 19]

KKT is mainly designed for solving continuous nonlinear programming problems. The penalty function ofPc is a Lagrangian function with Lagrange-multiplier vectors α=(α1,α2,…,αm)T∈ℜm and β=(β1,β2,…,βr)T∈ℜr, which is defined as
(2.4)L(x,α,β)=f(x)+αTh(x)+βTg(x).Theorem 2.7 (see [19]).
If pointx* is a CMc of Pc and a regular point (gradient vectors of equality constraints and active inequality constraints are linearly independent), then there exist unique α*∈ℜm and β*∈ℜrsuch that
(2.5)∇xL(x*,α*,β*)=0,
where βj=0  for all  j∉A(x*)={i∣gi(x*)=0} (the set of active constraints), and βj≥0 otherwise.
The uniquex,α, and β that satisfy equation (2.5) can be found by solving equation (2.5) as a system of nonlinear equations. Because KKT is just a necessary condition, there exist some points that are not CMc. Moreover, the approach is limited to solving CNLPs with continuous and differentiable functions.


#### 2.2.2. Sufficient Saddle-Point (SP) Condition [6]

The concept of saddle point has been widely studied during the past decades.Theorem 2.8 (see [6]).
For continuous and differentiable constraint functions, pointx* is CMc of Pc if there exist unique α*∈ℜm and β*∈ℜr that satisfy the following saddle-point condition at x*:
(2.6)L(x*,α,β)≤L(x*,α*,β*)≤L(x,α*,β*),
for all x∈Nc(x*) and all α∈ℜm and β∈ℜr.
The existing saddle-point condition is only a sufficient but not necessary condition. This means that there exist someα* and β* that do not satisfy (2.6) for each CMc x* of Pc.


#### 2.2.3. The Necessary and Sufficient Reverse Bridge Theorem (RBTH) [8]

In [8], we propose RBTH as a method for finding a constrained minimum.Definition 2.9 (Penalty Function for CRBTH).
The penalty function ofPc with penalty-multiplier α∈ℜm and β∈ℜr is defined as
(2.7)Lc(x,α,β)=f(x)+αT|h(x)|+βTmax(0,g(x)),
where |h(x)|=(|h1(x)|,|h2(x)|,…,|hm(x)|) and max(0,g(x))=(max(0,g1(x)),max(0,g2(x)),…,max(0,gr(x))).Theorem 2.10 (see [8]).
Pointx* is CMc of Pc if and only if there exist finite α*≥0 and β*≥0 such that for any α**>α*, β**>β* the following condition is satisfied:
(2.8)Lc(x*,α,β)=Lc(x*,α**,β**)≤Lc(x,α**,β**)
for each x in the neighbourhood of x* and all α∈ℜm and β∈ℜr.Definition 2.11 (Penalty Function for DRBTH).
The penalty function ofPd with penalty-multiplier α∈ℜm and β∈ℜr is defined as
(2.9)Ld(x,α,β)=f(x)+αT|h(x)|+βTmax(0,g(x)),
where |h(x)|=(|h1(x)|,|h2(x)|,…,|hm(x)|) and max(0,g(x))=(max(0,g1(x)),max(0,g2(x)),…,max(0,gr(x))).Theorem 2.12 (see [8]).
Pointy* is CMd of Pd if and only if there exist finite α*≥0 and β*≥0 such that for any α**>α*, β**>β* the following condition is satisfied:
(2.10)Ld(y*,α,β)=Ld(y*,α**,β**)≤Ld(y,α**,β**),
for each y in the neighbourhood of y* and all α∈ℜm and β∈ℜr.Definition 2.13 (Penalty Function for MRBTH).
The penalty function ofPm with penalty-multiplier α∈ℜm and β∈ℜr is defined as
(2.11)Lm(x,y,α,β)=f(x,y)+αT|h(x,y)|+βTmax(0,g(x,y)),
where |h(x,y)|=(|h1(x,y)|,|h2(x,y)|,…,|hm(x,y)|) and max(0,g(x,y))=(max(0,g1(x,y)),max(0,g2(x,y)),…,max(0,gr(x,y))).Definition 2.14 (Mixed-Neighbourhood).
A mixed-neighbourhoodN(x,y) in mixed space ℜv×ℜw is defined as
(2.12)N(x,y)={(x′,y′)∣∥x′-x∥≤ξ,∥y′-y∥≤ξ,ξ→0,}.Theorem 2.15 (see [8]).
Point(x*,y*) is CMm of Pm if and only if there exist finite α*≥0 and β*≥0 such that for any α**>α*, β**>β* the following condition is satisfied:
(2.13)Lm(x*,y*,α,β)=Lm(x*,y*,α**,β**)≤Lm(x,y,α**,β**),
for all (x,y) in the neighbourhood of (x*,y*) and all α∈ℜm and β∈ℜr.


## 2.1. Basic Concepts

Generally speaking, nonlinear programming problems can be divided into three categories, that is, continuous nonlinear programming problems, discrete nonlinear programming problems, and mixed-integer nonlinear programming problems. The general forms of these nonlinear programming problems are as follows:Definition 2.1 (Continuous Nonlinear Programming).
A continuous nonlinear programming problem (CNLP) is defined as(2.1)(Pc):minxf(x)wherex=(x1,x2,…,xv)T∈ℜv,subjecttoh(x)=(h1(x),h2(x),…,hm(x))T=0,g(x)=(g1(x),g2(x),…,gr(x))T≤0,
where x∈ℜv are continuous variables. The function f is assumed to be continuous and differentiable, and the constraint functions  g and h can be discontinuous, nondifferentiable, and not in closed form.Definition 2.2 (Discrete Nonlinear Programming).
A discrete nonlinear programming problem (DNLP) is defined as(2.2)(Pd):minyf(y)wherey=(y1,y2,…,yw)T∈ℜw,subjecttoh(y)=(h1(y),h2(y),…,hm(y))T=0,g(y)=(g1(y),g2(y),…,gr(y))T≤0,
where  y∈ℜw are discrete variables. The functions f, g,  and h may be assumed discontinuous, nondifferentiable, or not even given in closed form.Definition 2.3 (Mixed-Integer Nonlinear Programming).
A mixed-integer nonlinear programming problem (MINLP) is defined as(2.3)(Pm):minx,yf(x,y)subjecttoh(x,y)=(h1(x,y),h2(x,y),…,hm(x,y))T=0,g(x,y)=(g1(x,y),g2(x,y),…,gr(x,y))T≤0,
where x∈ℜv are continuous variables, and y∈ℜw are discrete variables. The function f is bounded below and is assumed to be continuous and differentiable with respect to x, and the constraint functions  g  and h are general functions that can be discontinuous, non-differentiable, or not even given in closed form.The aims of solving continuous, discrete, and mixed-integer nonlinear programming problems are, respectively, to find the constrained minima with respect to neighbourhood of a continuous pointx, a discrete point y, and a mixed point (x,y).Definition 2.4 (Constrained Minimum of CNLP).
Pointx* is a constrained minimum of Pc (CMc), if x* is feasible and f(x*)≤f(x) for all feasible x in the neighbourhood of x*, that is, x∈Nc(x*)={x′:∥x′-x*∥≤ξandξ→0}.Definition 2.5 (Constrained Minimum of DNLP).
Pointy* is a constrained minimum of Pd (CMd), if y* is feasible and f(y*)≤f(y) for all feasible  y in a neighbourhood of y*.Definition 2.6 (Constrained Minimum of MINLP).
Point(x*,y*) is a constrained minimum of Pm (CMm), if (x*,y*) is feasible and f(x*,y*)≤f(x,y) for all feasible (x,y) in a neighbourhood of (x*,y*).


## 2.2. Related Work

In the following, we introduce some existing methods for solving nonlinear programming problems.


### 2.2.1. Necessary Karush-Kuhn-Tucker (KKT) Condition [18, 19]

KKT is mainly designed for solving continuous nonlinear programming problems. The penalty function ofPc is a Lagrangian function with Lagrange-multiplier vectors α=(α1,α2,…,αm)T∈ℜm and β=(β1,β2,…,βr)T∈ℜr, which is defined as
(2.4)L(x,α,β)=f(x)+αTh(x)+βTg(x).Theorem 2.7 (see [19]).
If pointx* is a CMc of Pc and a regular point (gradient vectors of equality constraints and active inequality constraints are linearly independent), then there exist unique α*∈ℜm and β*∈ℜrsuch that
(2.5)∇xL(x*,α*,β*)=0,
where βj=0  for all  j∉A(x*)={i∣gi(x*)=0} (the set of active constraints), and βj≥0 otherwise.
The uniquex,α, and β that satisfy equation (2.5) can be found by solving equation (2.5) as a system of nonlinear equations. Because KKT is just a necessary condition, there exist some points that are not CMc. Moreover, the approach is limited to solving CNLPs with continuous and differentiable functions.


### 2.2.2. Sufficient Saddle-Point (SP) Condition [6]

The concept of saddle point has been widely studied during the past decades.Theorem 2.8 (see [6]).
For continuous and differentiable constraint functions, pointx* is CMc of Pc if there exist unique α*∈ℜm and β*∈ℜr that satisfy the following saddle-point condition at x*:
(2.6)L(x*,α,β)≤L(x*,α*,β*)≤L(x,α*,β*),
for all x∈Nc(x*) and all α∈ℜm and β∈ℜr.
The existing saddle-point condition is only a sufficient but not necessary condition. This means that there exist someα* and β* that do not satisfy (2.6) for each CMc x* of Pc.


### 2.2.3. The Necessary and Sufficient Reverse Bridge Theorem (RBTH) [8]

In [8], we propose RBTH as a method for finding a constrained minimum.Definition 2.9 (Penalty Function for CRBTH).
The penalty function ofPc with penalty-multiplier α∈ℜm and β∈ℜr is defined as
(2.7)Lc(x,α,β)=f(x)+αT|h(x)|+βTmax(0,g(x)),
where |h(x)|=(|h1(x)|,|h2(x)|,…,|hm(x)|) and max(0,g(x))=(max(0,g1(x)),max(0,g2(x)),…,max(0,gr(x))).Theorem 2.10 (see [8]).
Pointx* is CMc of Pc if and only if there exist finite α*≥0 and β*≥0 such that for any α**>α*, β**>β* the following condition is satisfied:
(2.8)Lc(x*,α,β)=Lc(x*,α**,β**)≤Lc(x,α**,β**)
for each x in the neighbourhood of x* and all α∈ℜm and β∈ℜr.Definition 2.11 (Penalty Function for DRBTH).
The penalty function ofPd with penalty-multiplier α∈ℜm and β∈ℜr is defined as
(2.9)Ld(x,α,β)=f(x)+αT|h(x)|+βTmax(0,g(x)),
where |h(x)|=(|h1(x)|,|h2(x)|,…,|hm(x)|) and max(0,g(x))=(max(0,g1(x)),max(0,g2(x)),…,max(0,gr(x))).Theorem 2.12 (see [8]).
Pointy* is CMd of Pd if and only if there exist finite α*≥0 and β*≥0 such that for any α**>α*, β**>β* the following condition is satisfied:
(2.10)Ld(y*,α,β)=Ld(y*,α**,β**)≤Ld(y,α**,β**),
for each y in the neighbourhood of y* and all α∈ℜm and β∈ℜr.Definition 2.13 (Penalty Function for MRBTH).
The penalty function ofPm with penalty-multiplier α∈ℜm and β∈ℜr is defined as
(2.11)Lm(x,y,α,β)=f(x,y)+αT|h(x,y)|+βTmax(0,g(x,y)),
where |h(x,y)|=(|h1(x,y)|,|h2(x,y)|,…,|hm(x,y)|) and max(0,g(x,y))=(max(0,g1(x,y)),max(0,g2(x,y)),…,max(0,gr(x,y))).Definition 2.14 (Mixed-Neighbourhood).
A mixed-neighbourhoodN(x,y) in mixed space ℜv×ℜw is defined as
(2.12)N(x,y)={(x′,y′)∣∥x′-x∥≤ξ,∥y′-y∥≤ξ,ξ→0,}.Theorem 2.15 (see [8]).
Point(x*,y*) is CMm of Pm if and only if there exist finite α*≥0 and β*≥0 such that for any α**>α*, β**>β* the following condition is satisfied:
(2.13)Lm(x*,y*,α,β)=Lm(x*,y*,α**,β**)≤Lm(x,y,α**,β**),
for all (x,y) in the neighbourhood of (x*,y*) and all α∈ℜm and β∈ℜr.


## 2.2.1. Necessary Karush-Kuhn-Tucker (KKT) Condition [18, 19]

KKT is mainly designed for solving continuous nonlinear programming problems. The penalty function ofPc is a Lagrangian function with Lagrange-multiplier vectors α=(α1,α2,…,αm)T∈ℜm and β=(β1,β2,…,βr)T∈ℜr, which is defined as
(2.4)L(x,α,β)=f(x)+αTh(x)+βTg(x).Theorem 2.7 (see [19]).
If pointx* is a CMc of Pc and a regular point (gradient vectors of equality constraints and active inequality constraints are linearly independent), then there exist unique α*∈ℜm and β*∈ℜrsuch that
(2.5)∇xL(x*,α*,β*)=0,
where βj=0  for all  j∉A(x*)={i∣gi(x*)=0} (the set of active constraints), and βj≥0 otherwise.
The uniquex,α, and β that satisfy equation (2.5) can be found by solving equation (2.5) as a system of nonlinear equations. Because KKT is just a necessary condition, there exist some points that are not CMc. Moreover, the approach is limited to solving CNLPs with continuous and differentiable functions.


## 2.2.2. Sufficient Saddle-Point (SP) Condition [6]

The concept of saddle point has been widely studied during the past decades.Theorem 2.8 (see [6]).
For continuous and differentiable constraint functions, pointx* is CMc of Pc if there exist unique α*∈ℜm and β*∈ℜr that satisfy the following saddle-point condition at x*:
(2.6)L(x*,α,β)≤L(x*,α*,β*)≤L(x,α*,β*),
for all x∈Nc(x*) and all α∈ℜm and β∈ℜr.
The existing saddle-point condition is only a sufficient but not necessary condition. This means that there exist someα* and β* that do not satisfy (2.6) for each CMc x* of Pc.


## 2.2.3. The Necessary and Sufficient Reverse Bridge Theorem (RBTH) [8]

In [8], we propose RBTH as a method for finding a constrained minimum.Definition 2.9 (Penalty Function for CRBTH).
The penalty function ofPc with penalty-multiplier α∈ℜm and β∈ℜr is defined as
(2.7)Lc(x,α,β)=f(x)+αT|h(x)|+βTmax(0,g(x)),
where |h(x)|=(|h1(x)|,|h2(x)|,…,|hm(x)|) and max(0,g(x))=(max(0,g1(x)),max(0,g2(x)),…,max(0,gr(x))).Theorem 2.10 (see [8]).
Pointx* is CMc of Pc if and only if there exist finite α*≥0 and β*≥0 such that for any α**>α*, β**>β* the following condition is satisfied:
(2.8)Lc(x*,α,β)=Lc(x*,α**,β**)≤Lc(x,α**,β**)
for each x in the neighbourhood of x* and all α∈ℜm and β∈ℜr.Definition 2.11 (Penalty Function for DRBTH).
The penalty function ofPd with penalty-multiplier α∈ℜm and β∈ℜr is defined as
(2.9)Ld(x,α,β)=f(x)+αT|h(x)|+βTmax(0,g(x)),
where |h(x)|=(|h1(x)|,|h2(x)|,…,|hm(x)|) and max(0,g(x))=(max(0,g1(x)),max(0,g2(x)),…,max(0,gr(x))).Theorem 2.12 (see [8]).
Pointy* is CMd of Pd if and only if there exist finite α*≥0 and β*≥0 such that for any α**>α*, β**>β* the following condition is satisfied:
(2.10)Ld(y*,α,β)=Ld(y*,α**,β**)≤Ld(y,α**,β**),
for each y in the neighbourhood of y* and all α∈ℜm and β∈ℜr.Definition 2.13 (Penalty Function for MRBTH).
The penalty function ofPm with penalty-multiplier α∈ℜm and β∈ℜr is defined as
(2.11)Lm(x,y,α,β)=f(x,y)+αT|h(x,y)|+βTmax(0,g(x,y)),
where |h(x,y)|=(|h1(x,y)|,|h2(x,y)|,…,|hm(x,y)|) and max(0,g(x,y))=(max(0,g1(x,y)),max(0,g2(x,y)),…,max(0,gr(x,y))).Definition 2.14 (Mixed-Neighbourhood).
A mixed-neighbourhoodN(x,y) in mixed space ℜv×ℜw is defined as
(2.12)N(x,y)={(x′,y′)∣∥x′-x∥≤ξ,∥y′-y∥≤ξ,ξ→0,}.Theorem 2.15 (see [8]).
Point(x*,y*) is CMm of Pm if and only if there exist finite α*≥0 and β*≥0 such that for any α**>α*, β**>β* the following condition is satisfied:
(2.13)Lm(x*,y*,α,β)=Lm(x*,y*,α**,β**)≤Lm(x,y,α**,β**),
for all (x,y) in the neighbourhood of (x*,y*) and all α∈ℜm and β∈ℜr.


## 3. Solving NLPs Using Reverse Bridge Theorem

We have proved that RBTH is a necessary and sufficient condition for constrained local optima under a range of penalties in [8]. However, in [8] we do not provide any concrete algorithm to solve NLPs using RBTH. Consequently, in this paper, we first present three algorithms for solving CNLPs, DNLPs, and MINLPs, respectively.We first present an algorithm, called RBTH_CNLP, to find the constrained minimum of CNLPs, as is shown in Algorithm1. According to Theorem 2.10, if x* is a local minimum of a CNLP with respect to x, x* must be a constrained minimum of the CNLP as well. Therefore, given an arbitrary CNLP Pc, to find its constrained minimum, we only need to find its local minimum. According to formula (2.8), let Lc be the penalty function of Pc; a reverse bridge point is the local minimum of Lc. Consequently, in order to find the constraint minimum of a CNLP, we only need to find its reverse bridge point. In this way, we design our algorithm RBTH_CNLP. The key idea of the algorithm is to increase α** and β** gradually and to minimize Lc(x,α**,β**) simultaneously until α**>α*, β**>β*.Algorithm 1:The solving procedure for finding CMc of Pc.
ProcedureRBTH_CNLP (Pc,x,α̅,β̅)α→0,β→0repeatincrease  αi by δ if (hi(x)≠0andαi<α̅i) for i=1,…,m;increase  βj by δ if (gj(x)≰0andβj<β̅j) for j=1,…,r;repeatperform descent of Lc(x,α,β) with respect to x;untila local minimum of Lc(x,α,β) is found;untila CMc of Pc is found or  (αi>α̅i for all hi(x)≠0 and βj>β̅j for all gj(x)≰0).return CMc if found;end_procedureAs we can see in Algorithm1, we first initialize the values of α** and β**. Then the algorithm is executed to find a local minimum x* of Lc(x,α**,β**)according to formula (2.8). If point x* is not a feasible solution of Pc, then the algorithm increases the penalties corresponding to the violated constraints. The process is repeated until we find that a CMc or α** (resp., β**) is larger than its maximum bound α̅ (resp., β̅).Algorithm2 shows the algorithm RBTH_DNLP to solve discrete nonlinear programming problems. The idea of this algorithm is similar to algorithm RBTH_CNLP. Algorithm RBTH_DNLP first initializes the values of α** and β**, then gradually increases α** and β**, and minimizes Ld(y,α**,β**) until α**>α*, β**>β*.Algorithm 2:The solving procedure for finding CMd of Pd.
ProcedureRBTH_DNLP (Pd,y,α̅,β̅)α→0,β→0;repeatincrease  αi by δif (hi(y)≠0andαi<α̅i) for i=1,…,m;increase  βj by δ if (gj(y)≰0andβj<β̅j) for j=1,…,r;repeatperform descent of Ld(y,α,β) with respect to y;until a local minimum of Ld(y,α,β) is found;untila CMd of Pd is found or (αi>α̅iforallhi(y)≠0andβj>β̅jforallgj(y)≰0).return CMd if found;end_procedureIn order to solve MINLPs using RBTH, we need to define two neighbourhoods, that is, discrete neighbourhood and mixed neighbourhood.Definition 3.1 (Discrete Neighbourhood).
A discrete neighbourhoodNd(y) of y in discrete space ℜw is a finite set of points {y′∈ℜw} in such a way that y′ is reachable from y in one step, that y′∈Nd(y)⇔y∈Nd(y′), and that it is possible to reach every y′′ from any y in one or more steps through neighbouring points.Definition 3.2 (Mixed Neighbourhood).
A mixed neighbourhoodNm(x,y) in mixed space ℜv×ℜw is defined as
(3.1)Nm(x,y)=Nc(x)|y+Nd(y)|x={(x′,y)∣x′∈Nc(x)}⋃{(x,y′)∣y′∈Nd(y)},
where Nc(x) is continuous neighbourhood of variable x, and Nd(y) is discrete neighbourhood of variable y.Corollary 3.3.
According to Definition3.2 and Theorem 2.15, the RBTH in formula (2.13) can be rewritten into two following necessary conditions that, collectively, are sufficient:
(3.2)Lm(x*,y*,α,β)=Lm(x*,y*,α**,β**)≤Lm(x*,y,α**,β**),y∈Nd(y*),Lm(x*,y*,α**,β**)≤Lm(x,y*,α**,β**),x∈Nc(x*).Based on the corollary, we present an algorithm RBTH_MINLP, as is seen in Algorithm3, to find the constrained minimum of MINLPs. According to Theorem 2.15 as we mentioned in Section 2, if the point (x*,y*) is a local minimum of an MINLP with respect to (x,y), this point must also be a constrained minimum of the MINLP. This means that given an arbitrary MINLP Pm, to find its constrained minimum, we only need to find its local minimum. On the other hand, according to formula (2.13), let Lm be the penalty function of Pm; a reverse bridge point is the local minimum of Lm. In this sense, in order to find a MINLP’s constrained minimum, we only need to find the reverse bridge point.Algorithm 3:The resolving procedure for finding CMm of Pm.
Procedure RBTH_MINLP(Pm,x,y,α̅,β̅)α→0, β→0;repeatincrease  αi by δif (hi(x)≠0andαi<α̅i) for i=1,…,m;increase  βj by δ if (gj(x)≰0andβj<β̅j) for j=1,…,r;repeatperformdescent of Lm(x,y,α,β) with respect to  x for given  y;until a local minimum of Lm(x,y,α,β) with respect to  x is found;repeatperform descent of Lm(x,y,α,β) with respect to  y for given  x;until a local minimum of Lm(x,y,α,β) with respect to  y is found;until a CMm of Pm is found or (αi>α̅ifor all hi(x)≠0  and βj>β̅j for all gj(x)≰0)return CMm if found;end_procedureIn the procedure of RBTH_MINLP, we first initialize the values ofα** and β**. In the first inner loop, we focus on finding the local minimum x* of Lm(x,y,α,β) with respect to the continuous neighbourhoods of x; in the second inner loop, we are devoted to looking for the local minimum y* by Lm(x,y,α,β) with respect to the discrete neighbourhoods of y. If the local minimum point (x*,y*) violates global constraints of Pm, we increase the penalties of violated constraints in the outer loop. The process is repeated until we find that a CMm of Pm or α** (resp., β**) is larger than α̅ (resp., β̅).Obviously, the main idea of all the three algorithms RBTH_CNLP, RBTH_DNLP, and RBTH_MINLP is to find the reverse bridge points for CNLPs, DNLPs, and MINLPs, respectively. According to Theorems2.10, 2.12 and 2.15 as we mentioned in Section 2, we know that these reverse bridge points are also constraint minima of NLPs. Because CRBTH, DRBTH, and MRBTH are all necessary and sufficient conditions for solving CNLPs, DNLPs, and MINLPs, respectively, as we proved in [8], the following theorem stands.Theorem 3.4.
Given a CNLP (DNLP, MINLP, resp.), if there exists a solution, the algorithm RBTH_CNLP (RBTH_DNLP, RBTH_MINLP, resp.) can find the solution; if algorithm RBTH_CNLP (RBTH_DNLP, RBTH_MINLP, resp.) finds a solution, then it must be the solution of the CNLP.In this section, we have shown that RBTH is an effective method for solving NLPs. However, it is difficult and expensive to solve some large-scale NLPs by RBTH because of their huge search spaces and several constraints in different form. Thus, in the next section, we further propose an approach to solve large-scale NLPs using RBTH under constraint partition.


## 4. RBTH under Constraint Partition

In this section, we show how to solve a nonlinear programming problem using RBTH under constraint partition. Because CNLPs and DNLPs can be regarded as special cases of MINLPs, in this section we only focus on MINLPs. Constraint partitioning has led to a major breakthrough in solving nonlinear programming problems in operations research and engineering applications [11–18]. In this section, we first prove that RBTH under constraint partition is also a necessary and sufficient condition for solving MINLPs. Then we prove that this necessary and sufficient condition can be rewritten into several necessary conditions by providing a partitioned neighbourhood. After that, we present an algorithm for solving MINLPs and prove that this algorithm is sound and complete.


### 4.1. RBTH for Partitioned Subproblems

Given an arbitrary mixed-integer nonlinear programming problemPt, we can partition its constraints into N+1 stages. Each stage t (t=0,1,…,N) includes ut local variables, mt local equality constraints, and rt local inequality constraints. Here local constraints restrict the variables of each stage, and global constraints restrict all the variables of problems. By applying this partition, the variable vector z∈Z of the problem Pt can be decomposed into N+1 subvectors z(0),z(1),…,z(N), where z(t)=(z1(t),…,zut(t))T is a vector of dynamic state variables in mixed space and stage t. In this sense, the MINLP formulation Pt is as follows:
(4.1)(Pt):minzJ(z)subjecttoh(t)(z(t))=0,g(t)(z(t))≤0,H(z)=0,G(z)≤0,
where J is assumed to be continuous and differentiable with respect to z, h(t)=(h1(t),…,hmt(t))T and g(t)=(g1(t),…,grt(t))T are vectors of local-constraint functions that involve z(t) and time in stage t, and H=(H1,…,Hp)Tand G=(G1,…,Gq)T are vectors of global-constraint functions that involve state variables and time in two or more stages.A solutionz of Pt can be regarded as the assignments of all the variables in z. The goal of solving Pt is then to find a constraint minimum with respect to all the feasible solutions in its mixed neighbourhood. It is clear that the partition of each stage needs to be further decomposed into discrete and continuous parts; however, we do not consider such situation for the purpose of simplification. In the following, we define the penalty function of Pt and then propose the partitioned necessary and sufficient RBTH condition on CMm of Pt.Definition 4.1 (Penalty Function).
The penalty function forPt and the corresponding penalty function in staget are defined as follows:
(4.2)Lm(z,α,β,γ,η)=J(z)+∑t=0N{α(t)T|h(t)(z(t))|+β(t)Tmax(0,g(t)(z(t)))}+γT|H(z)|+ηTmax(0,G(z)),Γm(z,α(t),β(t),γ,η)=J(z)+α(t)T|h(t)(z(t))|+β(t)Tmax(0,g(t)(z(t)))+γT|H(z)|+ηTmax(0,G(z)),
where α(t)=(α1(t),…,αmt(t))T∈ℜmt and β(t)=(β1(t),…,βrt(t))T∈ℜrtare the penalty vectors for the local constraints in stage t, t=0,1,…,N; γ=(γ1,…,γp)∈ℜp and η=(η1,…,ηq)∈ℜq are the penalty vectors for the global constraints.Theorem 4.2.
Solutionz* is a CMm of Pt with respect to its mixed neighbourhood if and only if there exist finite α*≥0, β*≥0, γ*≥0, and η*≥0 for any α**>α*, β**>β*, γ**>γ*, and η**>η* such that the following RBTH condition is satisfied:
(4.3)Lm(z*,α,β,γ,η)=Lm(z*,α**,β**,γ**,η**)≤Lm(z,α**,β**,γ**,η**),
for all α∈ℜΣi=0Nmi,β∈ℜΣi=0Nri,γ∈ℜp,η∈ℜq,andz∈Nm(z*).Proof.
The proof consists of two parts.
“⇒” parts: given a constraint minimum z*, we need to prove that there exist finite α*≥0, β*≥0, γ*≥0, and η*≥0 to satisfy formula (4.3).
Equality Part:
z* is a feasible solution; so it satisfies all local constraints and global constraints. Therefore, we obtain
(4.4)Lm(z*,α**,β**,γ**,η**)=J(z*)+∑t=0N{α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))}+γ**T|H(z*)|+η**Tmax(0,G(z*))=J(z*),Lm(z*,α,β,γ,η)=J(z*)+∑t=0N{α(t)T|h(t)(z*(t))|+β(t)Tmax(0,g(t)(z*(t)))}+γT|H(z*)|+ηTmax(0,G(z*))=J(z*).
So, Lm(z*,α,β,γ,η)=Lm(z*,α**,β**,γ**,η**).Inequality Part:
It is as follows.
(1)  z* is the unique minimum of J(·). For any z, |H(z)|≥0, max(0,G(z))≥0, |h(t)(z(t))|≥0, andmax(0,g(t)(z(t)))≥0. Therefore the following equation is right regardless of the choice of the penalties:
(4.5)Lm(z,α**,β**,γ**,η**)≥J(z)≥J(z*)=Lm(z*,α**,β**,γ**,η**).
(2)  z* is not the unique minimum of J(·) or is not a minimum of J(·). Assume that there exists some z′, which satisfies J(z′)≤J(z*).(i)
J(z′)=J(z*), H(z′)=0, G(z′)≤0, h(t)(z′(t))=0, and g(t)(z′(t))≤0. This means that z′ is another CMm of Pt. Therefore, regardless of the choice of penalties, the inequality of formula (4.3) is satisfied.(ii)
J(z′)=J(z*), and z′ violates some constraints. We suppose that it violates a global equality constraint function Hi(·) (the case with a global inequality constraint or a local constraint is similar), and thus γ*≥0 is enough.(iii)
J(z′)≤J(z*), and z′ is a feasible solution. This is impossible because z* is not CMm of Pt in this situation.(iv)
J(z′)≤J(z*), and z′ violates some constraints. We suppose that it violates a global equality constraint function Hi(·) (the case with a global inequality constraint or a local constraint is similar), so |Hi(z′)|≠0. Therefore, let γ*=(J(z*)-J(z′))/|Hi(z′)|. Then we have Lm(z*,α**,β**,γ**,η**)=J(z*),
(4.6)Lm(z′,α**,β**,γ**,η**)=J(z′)+∑t=0N{α(t)**T|h(t)(z′(t))|+β(t)**Tmax(0,g(t)(z′(t)))}+γ**T|H(z′)|+η**Tmax(0,G(z′))≥J(z′)+γi**|Hi(z′)|>J(z′)+J(z*)-J(z′)|Hi(z′)||Hi(z′)|=J(z*).Thus Lm(z*,α**,β**,γ**,η**)≤Lm(z,α**,β**,γ**,η**).
“⇐” parts: assume that formula (4.3) is satisfied; we need to prove that z* is a CMm of Pt. Because Lm(z*,α,β,γ,η)=Lm(z*,α**,β**,γ**,η**), we have
(4.7)J(z*)+∑t=0N{α(t)T|h(t)(z*(t))|+β(t)Tmax(0,g(t)(z*(t)))}+γT|H(z*)|+ηTmax(0,G(z*))=J(z*)+∑t=0N{α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))}+γ**T|H(z*)|+η**Tmax(0,G(z*)),
for any α(t), β(t),γ, η and t=0,1,…,N. Thus we can obtain |H(z*)|=0, max(0,G(z*))=0, |h(t)(z*(t))|=0 andmax(0,g(t)(z*(t)))=0. Therefore z* is a feasible solution.
In the following, we prove thatz* is minimum for all feasible solutions. Assume that z′ is another feasible solution; we have
(4.8)Lm(z*,α**,β**,γ**,η**)=J(z*)+∑t=0N{α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))}+γ**T|H(z*)|+η**Tmax(0,G(z*))=J(z*),Lm(z′,α**,β**,γ**,η**)=J(z′)+∑t=0N{α(t)**T|h(t)(z′(t))|+β(t)**Tmax(0,g(t)(z′(t)))}+γ**T|H(z′)|+η**Tmax(0,G(z′))=J(z′).
Because Lm(z*,α**,β**,γ**,η**)≤Lm(z,α**,β**,γ**,η**), we get J(z*)≤J(z′). Therefore, z* is a constrained minimum of Pt.In order to partition RBTH into several independent necessary conditions efficiently, we define the mixed neighbourhood of solutionz* as follows.Definition 4.3 (Partitioned Mixed Neighbourhood).
The partitioned mixed neighbourhood ofz∈Z, denoted by Nm(z), is defined as
(4.9)Nm(z)=⋃i=0NNp(t)(z)=⋃i=0N{z′∣z′(t)∈Nm(z(t)),z′(i∣i≠t)=z(i)},
where Nm(z(t)) is the mixed-space neighbourhood of variable vector z(t) in stage t.Based on this definition, we can further partition the condition described in formula (4.3) into multiple conditions.Theorem 4.4.
GivenNm(z), the RBTH in formula (4.3) can be rewritten into N+2 following necessary conditions that, collectively, are sufficient:
(4.10)Γm(z*,α(t),β(t),γ**,η**)=Γm(z*,α(t)**,β(t)**,γ**,η**)≤Γm(z,α(t)**,β(t)**,γ**,η**)(4.11)Lm(z*,α(t)**,β(t)**,γ,η)=Lm(z*,α(t)**,β(t)**,γ**,η**)
for all z∈Nm(t)(z*),  α(t)∈ℜmt,  β(t)∈ℜrt,  γ∈ℜp,  η∈ℜq,andt=0,1,…,N.Proof.
We prove that formula (4.3) is equivalent to the combined formula (4.10) and formula (4.11).
“⇒” parts: given a z* satisfying formula (4.3), we need to prove that it also satisfies formula (4.10) and formula (4.11). For all t=0,1,…,N, any point z∈Nm(t)(z*) is also a point in Nm(z*); therefore J(z*)≤J(z),H(z*)=0, max(0,G(z*))=0, h(t)(z*(t))=0, andmax(0,g(t)(z*(t)))=0:
(4.12)Γm(z,α(t)**,β(t)**,γ**,η**)=J(z)+α(t)**T|h(t)(z(t))|+β(t)**Tmax(0,g(t)(z(t)))+γ**T|H(z)|+η**Tmax(0,G(z))≥J(z),Γm(z*,α(t)**,β(t)**,γ**,η**)=J(z*)+α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))+γ**T|H(z*)|+η**Tmax(0,G(z*))=J(z*).
Therefore, Γm(z*,α(t),β(t),γ**,η**)≤Γm(z,α(t)**,β(t)**,γ**,η**).
Then we can know that the equality in formula (4.10) and the equality in formula (4.11) hold in case of z* satisfying all the constraints.
“⇐” parts: we prove this part by contradiction. Assume that z* satisfies formula (4.10) and formula (4.11) but does not satisfy formula (4.3). The equality in formula (4.3) cannot be violated because the equality in formula (4.10) and the equality in formula (4.11) imply that all local and global constraints are satisfied. Therefore, the inequality in formula (4.3) is unsatisfied. In this case, there exists some Nm(z*) and a unique t′ where z∈Nm(t)(z*) such that
(4.13)Lm(z*,α**,β**,γ**,η**)≰Lm(z,α**,β**,γ**,η**).
But
(4.14)Lm(z,α**,β**,γ**,η**)=J(z)+∑t=0N{α(t)**T|h(t)(z(t))|+β(t)**Tmax(0,g(t)(z(t)))}+γ**T|H(z)|+η**Tmax(0,G(z)),Lm(z*,α**,β**,γ**,η**)=J(z*)+∑t=0N{α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))}+γ**T|H(z*)|+η**Tmax(0,G(z*))=J(z*).
Therefore
(4.15)J(z*)≰J(z)+α(t′)**T|h(t)(z(t′))|+β(t′)**Tmax(0,g(t)(z(t′)))+γ**T|H(z)|+η**Tmax(0,G(z)).
This implies that
(4.16)Γm(z*,α(t′)**,β(t′)**,γ**,η**)≰Γm(z,α(t′)**,β(t′)**,γ**,η**)
holds for t=t′, which contradicts our assumption.
Therefore, anyz* that satisfies formula (4.10) and formula (4.11) must also satisfy (4.3).
Theorem4.4 proves that the original RBTH mentioned in Theorem 2.15 can be partitioned into N+1 necessary conditions as formula (4.10) and a global necessary condition as formula (4.11). Consequently, local reverse bridge points, which satisfy formula (4.10) in stage t, are local minimum of the original RBTH in stage t. The above reverse bridge points are essentially the solutions of solving the following MINLP Pt(t), in which we add the global constraints to the original objective function J(z):
(4.17)(Pt(t)):minz(t)J(t)(z)=J(z)+γT|H(z)|+ηTmax(0,G(z))subjecttoh(t)(z(t))=0,g(t)(z(t))≤0.In brief, solving the original problem can be reduced to solve multiple MINLPs defined byPt(t) in formula (4.17) and to increase the penalties of violated global constraints defined in formula (4.11). Therefore, by partitioning the original problem and solving each subproblem, Theorem 4.4 leads to a significant reduction on computational complexity.


### 4.2. The Partitioning and Resolving Procedure

Algorithm4 shows the partitioning and resolving procedure for finding the reverse bridge points satisfying the conditions in Theorem 4.4. As is shown in the algorithm, γ* and η* are initialized firstly; the inner loop is then carried out to find a reverse bridge point of MINLP Pt(t) in each stage t, which can be implemented by the procedure RBTH_MINLP, as we introduced in Section 3. After all the subproblems are solved, the penalties corresponding to the violated global constraints are increased in the outer loop. The process is repeated until a CMm of Pt is found or γ** and η** are larger than their maximum bounds γ̅ and η̅.Algorithm 4:The partitioning and resolving procedure for finding CMm of Pt.
Procedure RBTH_partition_resolve_mixed(Pt,z,α¯,β̅,γ̅,η̅)γ→0,η→0;repeatincreaseγi by δ if (Hi(z)≠0andγi<γ̅i)for i=1,…,p;increaseηj by δ if (Gj(z)≰0andηj<η̅j) for j=1,…,q;for  t=0to  Ncall RBTH_MINLP (Pt(t),z,α¯,β̅) to solve Pt(t).end for;until a CMm of Pt is found or (γi>γ̅iforallHi(z)≠0andηj>η̅jforallGj(z)≰0).return CMm of Pt if found;end_procedureAccording to Theorems4.2 and 4.4, we know that solving the original problem can be reduced to solve multiple MINLPs. For every MINLP in stage t of original problem, algorithm RBTH_partition_resolve_mixed calls RBTH_MINLP to solve it. Moreover, Theorem 3.4 has proved that algorithm RBTH_MINLP is sound and complete for solving MINLPs. Therefore, the following theorem stands.Theorem 4.5.
Given a MINLP, if there exists a solution, the algorithm RBTH_partition_resolve_mixed can find the solution; if the algorithm finds a solution, then it must be the solution of the MINLP.


## 4.1. RBTH for Partitioned Subproblems

Given an arbitrary mixed-integer nonlinear programming problemPt, we can partition its constraints into N+1 stages. Each stage t (t=0,1,…,N) includes ut local variables, mt local equality constraints, and rt local inequality constraints. Here local constraints restrict the variables of each stage, and global constraints restrict all the variables of problems. By applying this partition, the variable vector z∈Z of the problem Pt can be decomposed into N+1 subvectors z(0),z(1),…,z(N), where z(t)=(z1(t),…,zut(t))T is a vector of dynamic state variables in mixed space and stage t. In this sense, the MINLP formulation Pt is as follows:
(4.1)(Pt):minzJ(z)subjecttoh(t)(z(t))=0,g(t)(z(t))≤0,H(z)=0,G(z)≤0,
where J is assumed to be continuous and differentiable with respect to z, h(t)=(h1(t),…,hmt(t))T and g(t)=(g1(t),…,grt(t))T are vectors of local-constraint functions that involve z(t) and time in stage t, and H=(H1,…,Hp)Tand G=(G1,…,Gq)T are vectors of global-constraint functions that involve state variables and time in two or more stages.A solutionz of Pt can be regarded as the assignments of all the variables in z. The goal of solving Pt is then to find a constraint minimum with respect to all the feasible solutions in its mixed neighbourhood. It is clear that the partition of each stage needs to be further decomposed into discrete and continuous parts; however, we do not consider such situation for the purpose of simplification. In the following, we define the penalty function of Pt and then propose the partitioned necessary and sufficient RBTH condition on CMm of Pt.Definition 4.1 (Penalty Function).
The penalty function forPt and the corresponding penalty function in staget are defined as follows:
(4.2)Lm(z,α,β,γ,η)=J(z)+∑t=0N{α(t)T|h(t)(z(t))|+β(t)Tmax(0,g(t)(z(t)))}+γT|H(z)|+ηTmax(0,G(z)),Γm(z,α(t),β(t),γ,η)=J(z)+α(t)T|h(t)(z(t))|+β(t)Tmax(0,g(t)(z(t)))+γT|H(z)|+ηTmax(0,G(z)),
where α(t)=(α1(t),…,αmt(t))T∈ℜmt and β(t)=(β1(t),…,βrt(t))T∈ℜrtare the penalty vectors for the local constraints in stage t, t=0,1,…,N; γ=(γ1,…,γp)∈ℜp and η=(η1,…,ηq)∈ℜq are the penalty vectors for the global constraints.Theorem 4.2.
Solutionz* is a CMm of Pt with respect to its mixed neighbourhood if and only if there exist finite α*≥0, β*≥0, γ*≥0, and η*≥0 for any α**>α*, β**>β*, γ**>γ*, and η**>η* such that the following RBTH condition is satisfied:
(4.3)Lm(z*,α,β,γ,η)=Lm(z*,α**,β**,γ**,η**)≤Lm(z,α**,β**,γ**,η**),
for all α∈ℜΣi=0Nmi,β∈ℜΣi=0Nri,γ∈ℜp,η∈ℜq,andz∈Nm(z*).Proof.
The proof consists of two parts.
“⇒” parts: given a constraint minimum z*, we need to prove that there exist finite α*≥0, β*≥0, γ*≥0, and η*≥0 to satisfy formula (4.3).
Equality Part:
z* is a feasible solution; so it satisfies all local constraints and global constraints. Therefore, we obtain
(4.4)Lm(z*,α**,β**,γ**,η**)=J(z*)+∑t=0N{α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))}+γ**T|H(z*)|+η**Tmax(0,G(z*))=J(z*),Lm(z*,α,β,γ,η)=J(z*)+∑t=0N{α(t)T|h(t)(z*(t))|+β(t)Tmax(0,g(t)(z*(t)))}+γT|H(z*)|+ηTmax(0,G(z*))=J(z*).
So, Lm(z*,α,β,γ,η)=Lm(z*,α**,β**,γ**,η**).Inequality Part:
It is as follows.
(1)  z* is the unique minimum of J(·). For any z, |H(z)|≥0, max(0,G(z))≥0, |h(t)(z(t))|≥0, andmax(0,g(t)(z(t)))≥0. Therefore the following equation is right regardless of the choice of the penalties:
(4.5)Lm(z,α**,β**,γ**,η**)≥J(z)≥J(z*)=Lm(z*,α**,β**,γ**,η**).
(2)  z* is not the unique minimum of J(·) or is not a minimum of J(·). Assume that there exists some z′, which satisfies J(z′)≤J(z*).(i)
J(z′)=J(z*), H(z′)=0, G(z′)≤0, h(t)(z′(t))=0, and g(t)(z′(t))≤0. This means that z′ is another CMm of Pt. Therefore, regardless of the choice of penalties, the inequality of formula (4.3) is satisfied.(ii)
J(z′)=J(z*), and z′ violates some constraints. We suppose that it violates a global equality constraint function Hi(·) (the case with a global inequality constraint or a local constraint is similar), and thus γ*≥0 is enough.(iii)
J(z′)≤J(z*), and z′ is a feasible solution. This is impossible because z* is not CMm of Pt in this situation.(iv)
J(z′)≤J(z*), and z′ violates some constraints. We suppose that it violates a global equality constraint function Hi(·) (the case with a global inequality constraint or a local constraint is similar), so |Hi(z′)|≠0. Therefore, let γ*=(J(z*)-J(z′))/|Hi(z′)|. Then we have Lm(z*,α**,β**,γ**,η**)=J(z*),
(4.6)Lm(z′,α**,β**,γ**,η**)=J(z′)+∑t=0N{α(t)**T|h(t)(z′(t))|+β(t)**Tmax(0,g(t)(z′(t)))}+γ**T|H(z′)|+η**Tmax(0,G(z′))≥J(z′)+γi**|Hi(z′)|>J(z′)+J(z*)-J(z′)|Hi(z′)||Hi(z′)|=J(z*).Thus Lm(z*,α**,β**,γ**,η**)≤Lm(z,α**,β**,γ**,η**).
“⇐” parts: assume that formula (4.3) is satisfied; we need to prove that z* is a CMm of Pt. Because Lm(z*,α,β,γ,η)=Lm(z*,α**,β**,γ**,η**), we have
(4.7)J(z*)+∑t=0N{α(t)T|h(t)(z*(t))|+β(t)Tmax(0,g(t)(z*(t)))}+γT|H(z*)|+ηTmax(0,G(z*))=J(z*)+∑t=0N{α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))}+γ**T|H(z*)|+η**Tmax(0,G(z*)),
for any α(t), β(t),γ, η and t=0,1,…,N. Thus we can obtain |H(z*)|=0, max(0,G(z*))=0, |h(t)(z*(t))|=0 andmax(0,g(t)(z*(t)))=0. Therefore z* is a feasible solution.
In the following, we prove thatz* is minimum for all feasible solutions. Assume that z′ is another feasible solution; we have
(4.8)Lm(z*,α**,β**,γ**,η**)=J(z*)+∑t=0N{α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))}+γ**T|H(z*)|+η**Tmax(0,G(z*))=J(z*),Lm(z′,α**,β**,γ**,η**)=J(z′)+∑t=0N{α(t)**T|h(t)(z′(t))|+β(t)**Tmax(0,g(t)(z′(t)))}+γ**T|H(z′)|+η**Tmax(0,G(z′))=J(z′).
Because Lm(z*,α**,β**,γ**,η**)≤Lm(z,α**,β**,γ**,η**), we get J(z*)≤J(z′). Therefore, z* is a constrained minimum of Pt.In order to partition RBTH into several independent necessary conditions efficiently, we define the mixed neighbourhood of solutionz* as follows.Definition 4.3 (Partitioned Mixed Neighbourhood).
The partitioned mixed neighbourhood ofz∈Z, denoted by Nm(z), is defined as
(4.9)Nm(z)=⋃i=0NNp(t)(z)=⋃i=0N{z′∣z′(t)∈Nm(z(t)),z′(i∣i≠t)=z(i)},
where Nm(z(t)) is the mixed-space neighbourhood of variable vector z(t) in stage t.Based on this definition, we can further partition the condition described in formula (4.3) into multiple conditions.Theorem 4.4.
GivenNm(z), the RBTH in formula (4.3) can be rewritten into N+2 following necessary conditions that, collectively, are sufficient:
(4.10)Γm(z*,α(t),β(t),γ**,η**)=Γm(z*,α(t)**,β(t)**,γ**,η**)≤Γm(z,α(t)**,β(t)**,γ**,η**)(4.11)Lm(z*,α(t)**,β(t)**,γ,η)=Lm(z*,α(t)**,β(t)**,γ**,η**)
for all z∈Nm(t)(z*),  α(t)∈ℜmt,  β(t)∈ℜrt,  γ∈ℜp,  η∈ℜq,andt=0,1,…,N.Proof.
We prove that formula (4.3) is equivalent to the combined formula (4.10) and formula (4.11).
“⇒” parts: given a z* satisfying formula (4.3), we need to prove that it also satisfies formula (4.10) and formula (4.11). For all t=0,1,…,N, any point z∈Nm(t)(z*) is also a point in Nm(z*); therefore J(z*)≤J(z),H(z*)=0, max(0,G(z*))=0, h(t)(z*(t))=0, andmax(0,g(t)(z*(t)))=0:
(4.12)Γm(z,α(t)**,β(t)**,γ**,η**)=J(z)+α(t)**T|h(t)(z(t))|+β(t)**Tmax(0,g(t)(z(t)))+γ**T|H(z)|+η**Tmax(0,G(z))≥J(z),Γm(z*,α(t)**,β(t)**,γ**,η**)=J(z*)+α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))+γ**T|H(z*)|+η**Tmax(0,G(z*))=J(z*).
Therefore, Γm(z*,α(t),β(t),γ**,η**)≤Γm(z,α(t)**,β(t)**,γ**,η**).
Then we can know that the equality in formula (4.10) and the equality in formula (4.11) hold in case of z* satisfying all the constraints.
“⇐” parts: we prove this part by contradiction. Assume that z* satisfies formula (4.10) and formula (4.11) but does not satisfy formula (4.3). The equality in formula (4.3) cannot be violated because the equality in formula (4.10) and the equality in formula (4.11) imply that all local and global constraints are satisfied. Therefore, the inequality in formula (4.3) is unsatisfied. In this case, there exists some Nm(z*) and a unique t′ where z∈Nm(t)(z*) such that
(4.13)Lm(z*,α**,β**,γ**,η**)≰Lm(z,α**,β**,γ**,η**).
But
(4.14)Lm(z,α**,β**,γ**,η**)=J(z)+∑t=0N{α(t)**T|h(t)(z(t))|+β(t)**Tmax(0,g(t)(z(t)))}+γ**T|H(z)|+η**Tmax(0,G(z)),Lm(z*,α**,β**,γ**,η**)=J(z*)+∑t=0N{α(t)**T|h(t)(z*(t))|+β(t)**Tmax(0,g(t)(z*(t)))}+γ**T|H(z*)|+η**Tmax(0,G(z*))=J(z*).
Therefore
(4.15)J(z*)≰J(z)+α(t′)**T|h(t)(z(t′))|+β(t′)**Tmax(0,g(t)(z(t′)))+γ**T|H(z)|+η**Tmax(0,G(z)).
This implies that
(4.16)Γm(z*,α(t′)**,β(t′)**,γ**,η**)≰Γm(z,α(t′)**,β(t′)**,γ**,η**)
holds for t=t′, which contradicts our assumption.
Therefore, anyz* that satisfies formula (4.10) and formula (4.11) must also satisfy (4.3).
Theorem4.4 proves that the original RBTH mentioned in Theorem 2.15 can be partitioned into N+1 necessary conditions as formula (4.10) and a global necessary condition as formula (4.11). Consequently, local reverse bridge points, which satisfy formula (4.10) in stage t, are local minimum of the original RBTH in stage t. The above reverse bridge points are essentially the solutions of solving the following MINLP Pt(t), in which we add the global constraints to the original objective function J(z):
(4.17)(Pt(t)):minz(t)J(t)(z)=J(z)+γT|H(z)|+ηTmax(0,G(z))subjecttoh(t)(z(t))=0,g(t)(z(t))≤0.In brief, solving the original problem can be reduced to solve multiple MINLPs defined byPt(t) in formula (4.17) and to increase the penalties of violated global constraints defined in formula (4.11). Therefore, by partitioning the original problem and solving each subproblem, Theorem 4.4 leads to a significant reduction on computational complexity.


## 4.2. The Partitioning and Resolving Procedure

Algorithm4 shows the partitioning and resolving procedure for finding the reverse bridge points satisfying the conditions in Theorem 4.4. As is shown in the algorithm, γ* and η* are initialized firstly; the inner loop is then carried out to find a reverse bridge point of MINLP Pt(t) in each stage t, which can be implemented by the procedure RBTH_MINLP, as we introduced in Section 3. After all the subproblems are solved, the penalties corresponding to the violated global constraints are increased in the outer loop. The process is repeated until a CMm of Pt is found or γ** and η** are larger than their maximum bounds γ̅ and η̅.Algorithm 4:The partitioning and resolving procedure for finding CMm of Pt.
Procedure RBTH_partition_resolve_mixed(Pt,z,α¯,β̅,γ̅,η̅)γ→0,η→0;repeatincreaseγi by δ if (Hi(z)≠0andγi<γ̅i)for i=1,…,p;increaseηj by δ if (Gj(z)≰0andηj<η̅j) for j=1,…,q;for  t=0to  Ncall RBTH_MINLP (Pt(t),z,α¯,β̅) to solve Pt(t).end for;until a CMm of Pt is found or (γi>γ̅iforallHi(z)≠0andηj>η̅jforallGj(z)≰0).return CMm of Pt if found;end_procedureAccording to Theorems4.2 and 4.4, we know that solving the original problem can be reduced to solve multiple MINLPs. For every MINLP in stage t of original problem, algorithm RBTH_partition_resolve_mixed calls RBTH_MINLP to solve it. Moreover, Theorem 3.4 has proved that algorithm RBTH_MINLP is sound and complete for solving MINLPs. Therefore, the following theorem stands.Theorem 4.5.
Given a MINLP, if there exists a solution, the algorithm RBTH_partition_resolve_mixed can find the solution; if the algorithm finds a solution, then it must be the solution of the MINLP.


## 5. Numerical Simulation Results and Comparisons

All of our algorithms are coded in C, and in our simulation, numerical experiments are performed on a PC with Pentium 3.0 GHz Processor and 1.0 GB memory. We first compare our algorithm CPRBTH (RBTH under constraint partition) to two of the best CNLP solvers, Lancelot [20] and SNOPT [21]. To test the performance of the proposed algorithms, computational simulations are carried out with some well-studied benchmark problems taken from the CUTE library [22]. These problems are all minimization problems. Some of these problems were constructed by researchers to test optimization algorithms, while others were from real applications, such as computer production planning in operations research. For each instance, the algorithm is independently executed 15 times for comparison. The experimental results are shown in Table 1. The first three columns show the problems IDs, the number of constraints (nc), and the number of variables (nv). The last six columns show the solutions (Sol.) and CPU times we obtain by using LANCELOT, SNOPT and CRBTH. Both the CPU time and the solutions are the average of the measure of the 15 executions of the algorithms. Numerical results indicate that the algorithm usually performs quite well in terms of CPU time and quality of solution found.Table 1
Results of solving selected CNLP benchmarks from the CUTE library. All timing results are in seconds. Here nc and nv represent the number of constraints and the number of variables, respectively. “—” means that no feasible solutions were found in the time limit (600 seconds). “*” means that solutions were obtained by submitting problems through commercial version of LANCELOT but no CPU times were available. Numbers in bold represent the best solutions among the three methods.
Test ProblemLANCELOTSNOPTCPRBTHIDncnvSol.TimeSol.TimeSol.TimeALJAZZAF3175.000.4675.000.0175.000.05ALLINITC4130.44*30.490.0130.490.10ALSOTAME210.0820.570.080.010.080.09AVION24945——9.47E70.019.47E70.10BATCH4673——2.59E50.012.59E50.11BT11530.8250.620.820.010.820.07BT12536.1880.476.190.016.190.07BT6520.2770.560.280.010.280.07CB2331.9520.601.950.011.950.07CRESC468——0.870.010.870.01CSFI154-49.070.63-49.080.01-49.080.09DIPIGRI74680.60.68680.630.01680.630.09DIXCHLNG1050.01.122.47E30.012.47E30.05DNIEPER61241.87E40.831.87E40.011.87E40.13EXPFITA5221.13E-30.650.000.010.000.10GAUSSELM1411-2.250.550.00104.900.000.12HIMMELBI10012-1735.61.23-1755.000.01-1755.000.13HIMMELP221-62.050.63-62.050.01-62.050.05HIMMELP625-59.010.69-59.010.01-59.010.05HONG4122.570.501.350.011.350.05HUBFIT210.01690.460.020.010.020.04LOADBAL31310.4530.690.450.010.450.12MADSEN360.6160.550.620.010.620.03MARATOS21-1.000.40-1.000.01-1.000.02MATRIX2620.000.520.000.010.000.01MISTAKE913-1.000.58-1.000.01-1.000.11MWRIGHT5324.970.5624.980.0124.980.01ODFITS106-23800.50-2380.030.01-2380.030.03OPTCNTRL3220550.000.51550.000.01550.000.03OPTPRLOC3030-16.424.02-16.420.01-16.420.11OPTHREGB2760.00.760.000.010.000.06PENTAGON6151.509E-40.560.000.010.000.09We then compare our algorithm with three famous MINLP solvers, MINLP_BB [23], BARON [24], and CPOPT [9]. MINLP_BB performs a branch and bound algorithm with a sequential-quadratic-programming solver for solving continuous problems. BARON is a MINLP solver implementing the branch and reduce algorithm. CPOPT is an MINLP solver implementing the extended saddle point condition under constraint partition algorithm. To test the performance of the proposed algorithms, computational simulations are carried out with some well-studied benchmark problems taken from the MacMINLP library [25]. The first three columns show the problems IDs, the number of constraints (nc), and the number of variables (nv). The last eight columns show the solutions (Sol.) and CPU times we obtain by MINLP_BB, BARON, CPOPT, and CPRBTH. Both the CPU time and the solutions are the average of the measure of the 15 executions of the algorithm. Because the results of MINLP_BB and BARON in [13] were obtained by submitting jobs to the NEOS server and BARON’s site, respectively, we accept the results of [13]. The other two solvers were run on a PC with Pentium 3.0 GHz Processor and 1.0 GB memory.  The experimental results are shown in Table 2. Compared to CPOPT, the solutions of CPRBTH are at least competitive, and the running cost of CPRBTH is relatively lower.Table 2
Results of solving selected MINLP benchmarks from the MacMINLP library. Here nc and nv represent the number of constraints and the number of variables, respectively. “—” means that no feasible solutions were found in the time limit (3600 seconds). Numbers in bold represent the best solutions among the three methods.
Test ProblemMINLP-BBBARONCPOPTCPRBTHIDncnvSol.TimeSol.TimeSol.TimeSol.TimeC-RELOAD-q-4914303733———-1.1366.32-1.1359.25C-RELOAD-q-104333813936————-1.14298.87-1.14110.22Ex12.6.3579219.62319.6423.119.613.3719.613.37Ex12.6.57613015.1410.3845.510.63.1910.42.1PUMP3424——13112497713078881.2513078996.33SPACE-960-i64975537————7.65E6179.127.65E697.22SPACE-960-ir36172657————7.64E6132.967.64E696.34SPACE-960841715137————7.84E61137.137.84E61311.13SPACE-960-r553712257————5.13E691.565.13E687.34STOCKCYCLE97480——436341n/a119948.76.12119948.65.47TRIMLON4242412.2108.311.08.31.668.32.77TRIMLON6364818.81915.61092.915.613.2515.67.92TRIMLON1272168————95.5298.1195.5345.50TRIMLOSS46410510.899——10.68.8710.67.88TRIMLOSS59016112.6190——10.775.3110.678.87TRIMLOSS6120215————22.168.1922.168.19TRIMLOSS7154345————26.758.1426.837.22TRIMLOSS12384800————138.8278.33138.1199.10


## 6. Conclusion

RBTH is a necessary and sufficient condition for constrained local optima under a range of penalties. In this paper, we first propose three algorithms to solve NLPs using RBTH and then prove that these algorithms are both sound and complete. Additionally, we combine RBTH with constraint partition to solve large-scale MINLPs. Specifically, we decompose the constraints of MINLPs into some easier subproblems that are significant relaxations of the original problem, each of which can be solved by using RBTH directly, and then resolve those violated global constraints across the subproblems via RBTH. In the final part, we present an algorithm for implementing this search procedure and also prove that the algorithm is sound and complete for solving MINLPs under constraint partition. Experimental results also show that our algorithm is both sound and complete.



---

*Source: 617398-2010-07-11.xml*