Finiteness in restricted simplicial decomposition |
| |
Authors: | DW Hearn S Lawphongpanich JA Ventura |
| |
Institution: | Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA |
| |
Abstract: | Simplicial decomposition is an important form of decomposition for large non-linear programming problems with linear constraints. Von Hohenbalken has shown that if the number of retained extreme points is n + 1, where n is the number of variables in the problem, the method will reach an optimal simplex after a finite number of master problems have been solved (i.e., after a finite number of major cycles). However, on many practical problems it is infeasible to allocate computer memory for n + 1 extreme points. In this paper, we present a version of simplicial decomposition where the number of retained extreme points is restricted to r, 1 ? r ? n + 1, and prove that if r is sufficiently large, an optimal simplex will be reached in a finite number of major cycles. This result insures rapid convergence when r is properly chosen and the decomposition is implemented using a second order method to solve the master problem. |
| |
Keywords: | large scale optimization simplicial decomposition non-linear programming |
本文献已被 ScienceDirect 等数据库收录! |
|