Finiteness in restricted simplicial decomposition

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

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 1985-01, Vol.4 (3), p.125-130
Main Authors: Hearn, D.W, Lawphongpanich, S, Ventura, J.A
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
large scale optimization
Mathematical programming
non-linear programming
Operational research and scientific management
Operational research. Management science
simplicial decomposition
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0167-6377
1872-7468
DOI:10.1016/0167-6377(85)90016-1