Difference between revisions of "Outer-approximation (OA)"

From optimization
Jump to: navigation, search
(Algorithm)
(Upper Bonding Subproblem)
Line 17: Line 17:
 
First, give initial values for binary variables. In the given problem, the binary variable is <math>y</math>. Fix all the <math>y</math> variables at <math>y^k</math> and solve the new non-linear problem.
 
First, give initial values for binary variables. In the given problem, the binary variable is <math>y</math>. Fix all the <math>y</math> variables at <math>y^k</math> and solve the new non-linear problem.
  
[[File:function2.png|180px]]
+
[[File:function2.png|175px]]
  
 
One of the following cases must occur:
 
One of the following cases must occur:
 
a) By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution <math>x^k</math>is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.
 
a) By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution <math>x^k</math>is greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem.
 
b) This NLP is infeasible. If the fixed <math>y^k</math> is not feasible, use the following NLP problem to obtain <math>x^k</math>
 
b) This NLP is infeasible. If the fixed <math>y^k</math> is not feasible, use the following NLP problem to obtain <math>x^k</math>
 +
 
=== Master Problem ===
 
=== Master Problem ===
  

Revision as of 14:10, 25 May 2014

--Xudansha (talk) 12:06, 25 May 2014 (CDT)Authors: Xudan Sha (ChE 345 Spring 2014) Steward: Dajun Yue, Fengqi You


Contents

General

Outer approximation is a basic approach for solving Mixed Integer Nonlinear Programming (MINLP) models suggested by Duran and Grossmann (1986) [1]. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the original problems. The new problems consist of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program.

Algorithm

Problem Statement

Function1.png

f(x) and g(x) should be convex.

Upper Bonding Subproblem

First, give initial values for binary variables. In the given problem, the binary variable is y. Fix all the y variables at y^k and solve the new non-linear problem.

Function2.png

One of the following cases must occur: a) By solving this NLP, a feasible solution is obtained. In this minimum problem, this feasible solution x^kis greater than the optimum solution. So we can use this solution as a upper bond. Go to the master problem. b) This NLP is infeasible. If the fixed y^k is not feasible, use the following NLP problem to obtain x^k

Master Problem

Convergence and Optimality

To obtain a global optimum, the original MINLP should be convex, which means that all the constraints and objective function should be convex. The proposed algorithm can be applied to non-convex problems, but there is no guarantee that the solution obtained by the algorithm is a global one.[2]

A Numerical Example

Conclusion

Reference

[1] Duran M A, Grossmann I E. An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J]. Mathematical programming, 1986, 36(3): 307-339. [2] Fletcher R, Leyffer S. Solving mixed integer nonlinear programs by outer approximation[J]. Mathematical programming, 1994, 66(1-3): 327-349.