# Extended cutting plane (ECP)

Authors: Kyung Je Lee (ChE 345 Spring 2015) Stewards: Dajun Yue, Fengqi You

## Introduction

### Background

Extended Cutting Plane is an optimization method suggested by Westerlund and Petersson in 1996 to solve Mixed-Integer NonLinear Programming (MINLP) problems[1]. ECP can be thought as an extension of Kelley's cutting plane method, which uses iterative Newton's method to refine feasible area and ultimately solve a problem within tolerable error. Therefore, ECP method does not require solving Non-Linear Programming(NLP) while Branch and Bound(BB) and Outer Approximation(OA) do require NLP solution for an upper bound. However, ECP generally requires more iterations. Although cutting plane method is criticized for its slow convergence, ECP is more efficient in cases where evaluation of non linear functions are time costly. For example, in optimization of a dynamic separation process done by Stefan Emet and Tapio Westerlund, ECP was 100 times faster than BB and 10 times faster than OA in solving the MINLP[2].

### Comparison with outer approximation

ECP is closely related to OA in that it uses first differential approximation to cut the plane. The difference is that OA solves a NLP problem for its upper bound while ECP only uses solution of MILP in each iteration. This means that OA is more efficient in main iteration loops. This advantage of OA is more prominent in strongly non-linear MINLP problems that are mainly consisted of continuous variables. However, in pure integer non-linear programming problems, OA method does not have any advantage over ECP. Although it takes less iterations for OA to converge, solving NLP problem in each iteration incur more computation work than solving MILP because MILP has only one additional linear constraints in each iteration.

### Formulation of MINLP problem

A general MINLP can be formulated as the following:

$\min_{x,y} Z=C_x^T x + C_y^T y$

$s.t. \quad g(x,y) \leq 0$

where, cx and cy are vectors with constants, x is a vector of continuous variables, y is a vector with discrete variables and g(x, y) is a vector with continuous convex functions, all defined on a set.

## ECP algorithm

Since g(x,y) is a convex function set and continuously differentiable it follows that

$g_i(x^k,y^k) + \left( \frac{\partial g_i}{\partial x}\right)_{x^k,y^k} (x-x^k) + \left( \frac{\partial g_i}{\partial y}\right)_{x^k,y^k} (y-y^k) \leq g_i(x,y)$

Also, if,

$max(g_i(x^k,y^k)) \leq 0$

then for all i

$g_i(x^k,y^k) \leq 0$

Using these properties, ECP algorithm is as follows:

Step 0. Set k=1. Leave out all nonlinear constraints and set up an MILP problem.

Step 1. Solve the MILP problem.

Step 2. Check if the solution satisfies nonlinear constraints. If all constraints are satisfied, in other words, if $g_i(x^k,y^k) \leq 0$ is true for all i, $(x^k, y^k)$ is a global optimum.

Step 3 If any of the constraints are not satisfied, add a constraint for most violated constraint, g

$g_i(x^k,y^k) + \left( \frac{\partial g_i}{\partial x}\right)_{x^k,y^k} (x-x^k) + \left( \frac{\partial g_i}{\partial y}\right)_{x^k,y^k} (y-y^k)\leq 0$
set k= k+1 and go to Step 1.

## Example

$\min z = -x_1-x_2$

$s.t. \quad g1(x_1,x_2) = 0.15(x_1-8)^2 + 0.1 (x_2-6)^2+0.025e^{x_1}x_2^{-2}-5 \leq 0$

$g2(x_1,x_2) = 1/x_1 + 1/x_2- x_1^{0.5}x_2^{0.5}+4 \leq 0$
$2x_1-3x_2-2 \leq 0$
$1\leq x_1 \leq 20,\quad 1\leq x_2\leq 20, \quad x_1\in \R \quad x_2 \in \N$

First MILP can be set-up by leaving out non-linear constraint $g_1$ and $g_2$

Visualization of how ECP is used to solve MINLP3

$\min z = -x_1-x_2$

$s.t. \quad2x_1-3x_2-2 \leq 0$

$1\leq x_1 \leq 20,\quad 1\leq x_2\leq 20$
$x_1\in \R \quad x_2 \in \N$

The first iteration gives $x_1^1 = 20, x_2^1=20$. This leads to $g_1(x_1^1,x_2^1)=30359, \quad g_2(x_1^1,x_2^1)= -15.9$ A new constraint is introduced for the second iteration with the most violated nonlinear constraint $g_1$

$\min z = -x_1-x_2$

$s.t. \quad g_1(x_1^1,x_2^1)+\triangledown g_1(x_1^1,x_2^1)^T(x-x_1^1,x-x_2^1) \leq 0$

$2x_1-3x_2-2 \leq 0$
$1\leq x_1 \leq 20,\quad 1\leq x_2\leq 20$
$x_1\in \R \quad x_2 \in \N$

Same procedure can be taken for consequent iterations, and with 17 iterations, ECP gives answer of $x_1^1 = 8.9, x_2^1=12$.

## Non-smooth Functions

In non-smooth functions, ECP algorithm can be generalized by relaxing continuous differentiability. Therefore, the only change in the algorithm is that subgradients are used instead of gradients. Subgradient of convex function $h$ at point$z_0$ is any vector $\xi$ that satifies $h(z_0) + \xi(z-z_0) \leq h(z)$

ECP is

## Reference

1. Tapio Westerlund, Frank Pettersson, An extended cutting plane method for solving convex MINLP problems, Computers & Chemical Engineering, Volume 19, Supplement 1, 11–14 June 1995, Pages 131-136, ISSN 0098-1354, http://dx.doi.org/10.1016/0098-1354(95)87027-X.

2. Stefan Emet and Tapio Westerlund. 2008. Solving a dynamic separation problem using MINLP techniques. Appl. Numer. Math. 58, 4 (April 2008), 395-406. DOI=10.1016/j.apnum.2007.01.023 http://dx.doi.org/10.1016/j.apnum.2007.01.023

3. An extended supporting hyperplane algorithm for convex MINLP problems http://blogs.abo.fi/ose/files/2014/10/ose2014_kronqvist.pdf