Improve-and-Branch Algorithm for the Global Optimization of Nonconvex NLP Problems |
| |
Authors: | Marian G Marcovecchio María L Bergamini Pio A Aguirre |
| |
Institution: | 1. INGAR-Instituto de Desarrollo y Dise?o, Avellaneda 3657 – (S3002GJC), Santa Fe, Argentina
|
| |
Abstract: | A new algorithm to solve nonconvex NLP problems is presented. It is based on the solution of two problems. The reformulated
problem RP is a suitable reformulation of the original problem and involves convex terms and concave univariate terms. The
main problem MP is a nonconvex NLP that outer-approximates the feasible region and underestimate the objective function. MP
involves convex terms and terms which are the products of concave univariate functions and new variables. Fixing the variables
in the concave terms, a convex NLP that overestimates the feasible region and underestimates the objective function is obtained
from the MP. Like most of the deterministic global optimization algorithms, bounds on all the variables in the nonconvex terms
must be provided. MP forces the objective value to improve and minimizes the difference of upper and lower bound of all the
variables either to zero or to a positive value. In the first case, a feasible solution of the original problem is reached
and the objective function is improved. In general terms, the second case corresponds to an infeasible solution of the original
problem due to the existence of gaps in some variables. A branching procedure is performed in order to either prove that there
is no better solution or reduce the domain, eliminating the local solution of MP that was found. The MP solution indicates
a key point to do the branching. A bound reduction technique is implemented to accelerate the convergence speed. Computational
results demonstrate that the algorithm compares very favorably to other approaches when applied to test problems and process
design problems. It is typically faster and it produces very accurate results. |
| |
Keywords: | concave terms convex hull underestimating problem |
本文献已被 SpringerLink 等数据库收录! |