# Difference between revisions of "Extended cutting plane (ECP)"

m |
|||

Line 43: | Line 43: | ||

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

− | + | ::<math> 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 </math> | |

− | ::<math> 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 </math> | + | |

− | + | ||

::set k= k+1 and go to Step 1. | ::set k= k+1 and go to Step 1. | ||

Line 58: | Line 56: | ||

First MILP can be set-up by leaving out non-linear constraint <math> g_1</math> and <math> g_2</math> | First MILP can be set-up by leaving out non-linear constraint <math> g_1</math> and <math> g_2</math> | ||

− | [[File:ECP.PNG|350px|thumb|right|Visualization of how ECP is used to solve MINLP<sup> | + | [[File:ECP.PNG|350px|thumb|right|Visualization of how ECP is used to solve MINLP<sup>4</sup>]] |

<math> \min z = -x_1-x_2 </math> | <math> \min z = -x_1-x_2 </math> | ||

Line 68: | Line 66: | ||

The first iteration gives <math>x_1^1 = 20, x_2^1=20 </math>. | The first iteration gives <math>x_1^1 = 20, x_2^1=20 </math>. | ||

This leads to <math>g_1(x_1^1,x_2^1)=30359, \quad g_2(x_1^1,x_2^1)= -15.9 </math> | This leads to <math>g_1(x_1^1,x_2^1)=30359, \quad g_2(x_1^1,x_2^1)= -15.9 </math> | ||

+ | |||

A new constraint is introduced for the second iteration with the most violated nonlinear constraint <math>g_1</math> | A new constraint is introduced for the second iteration with the most violated nonlinear constraint <math>g_1</math> | ||

Line 82: | Line 81: | ||

==Non-smooth Functions== | ==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 <math>h</math> at point<math>z_0</math> is any vector <math>\xi</math> that satifies | 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 <math>h</math> at point<math>z_0</math> is any vector <math>\xi</math> that satifies | ||

− | <math>h(z_0) + \xi(z-z_0) \leq h(z)</math> | + | <math>h(z_0) + \xi(z-z_0) \leq h(z)</math> <sup> 3 </sup> |

==Conclusion== | ==Conclusion== | ||

− | ECP is | + | ECP is an extension of cutting plane(CP) method that is used to solve NLP problems. The application of cutting plane to MINLP is rather straight forward and the strength of ECP lies in that it is simple and robust. Therefore, it is suitable for solving large MINLP problems with moderate degree of non-linearity and complex system that require extensive computational work. ECP only requires one additional constraint to improve one solution for MILP problem at each iteration whereas both NLP and MILP problems are solved in other MINLP methods. However, since there is only one adjustment made at a time, it has slow convergence to solution. |

Line 94: | Line 93: | ||

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 | 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 | + | 3.Tapio Westerlund, Hans Skrifvars, Iiro Harjunkoski, Ray Pörn, An extended cutting plane method for a class of non-convex MINLP problems, Computers & Chemical Engineering, Volume 22, Issue 3, 28 February 1998, Pages 357-365, ISSN 0098-1354, http://dx.doi.org/10.1016/S0098-1354(97)00000-8. |

+ | (http://www.sciencedirect.com/science/article/pii/S0098135497000008) | ||

+ | |||

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

## Latest revision as of 23:38, 7 June 2015

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

## Contents |

## 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:

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

Also, if,

then for all i

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 is true for all i, is a global optimum.

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

- set k= k+1 and go to Step 1.

## Example

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

The first iteration gives .
This leads to

A new constraint is introduced for the second iteration with the most violated nonlinear constraint

Same procedure can be taken for consequent iterations, and with 17 iterations, ECP gives answer of .

## 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 at point is any vector that satifies
^{ 3 }

## Conclusion

ECP is an extension of cutting plane(CP) method that is used to solve NLP problems. The application of cutting plane to MINLP is rather straight forward and the strength of ECP lies in that it is simple and robust. Therefore, it is suitable for solving large MINLP problems with moderate degree of non-linearity and complex system that require extensive computational work. ECP only requires one additional constraint to improve one solution for MILP problem at each iteration whereas both NLP and MILP problems are solved in other MINLP methods. However, since there is only one adjustment made at a time, it has slow convergence to solution.

## 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.Tapio Westerlund, Hans Skrifvars, Iiro Harjunkoski, Ray Pörn, An extended cutting plane method for a class of non-convex MINLP problems, Computers & Chemical Engineering, Volume 22, Issue 3, 28 February 1998, Pages 357-365, ISSN 0098-1354, http://dx.doi.org/10.1016/S0098-1354(97)00000-8. (http://www.sciencedirect.com/science/article/pii/S0098135497000008)

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