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

(→Problem Statement) |
(→Problem Statement) |
||

Line 11: | Line 11: | ||

=== Problem Statement === | === Problem Statement === | ||

[[File:function1.png|150px]] | [[File:function1.png|150px]] | ||

+ | |||

+ | <math>f(x)</math> and <math>g(x)</math> should be convex. | ||

=== Upper Bonding Subproblem === | === Upper Bonding Subproblem === |

## Revision as of 13:50, 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

and should be convex.

### Upper Bonding Subproblem

### Feasibility Subproblem

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