Global optimization of nonconvex polynomial programming problems having rational exponents

被引:51
作者
Sherali, HD [1 ]
机构
[1] Virginia Polytech Inst & State Univ, Dept Ind & Syst Engn, Blacksburg, VA 24061 USA
基金
美国国家科学基金会;
关键词
polynomial programs; Reformulation-Linearization Technique (RLT); nonconvex programming; global optimization;
D O I
10.1023/A:1008249414776
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper considers the solution of nonconvex polynomial programming problems that arise in various engineering design, network distribution, and location-allocation contexts. These problems generally have nonconvex polynomial objective functions and constraints, involving terms of mixed-sign coefficients (as in signomial geometric programs) that have rational exponents on variables. For such problems, we develop an extension of the Reformulation-Linearization Technique (RLT) to generate linear programming relaxations that are embedded within a branch-and-bound algorithm. Suitable branching or partitioning strategies are designed for which convergence to a global optimal solution is established. The procedure is illustrated using a numerical example, and several possible extensions and algorithmic enhancements are discussed.
引用
收藏
页码:267 / 283
页数:17
相关论文
共 31 条
[1]   JOINTLY CONSTRAINED BICONVEX PROGRAMMING [J].
ALKHAYYAL, FA ;
FALK, JE .
MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (02) :273-286
[2]  
ALKHAYYAL FA, 1994, RELAXATION METHOD NO
[3]  
[Anonymous], J GLOBAL OPTIM, DOI DOI 10.1007/BF00121304
[4]  
[Anonymous], 1992, ARTE MEDIEVALE
[5]  
BRIMBERG J, 1991, NAV RES LOG, V38, P241, DOI 10.1002/1520-6750(199104)38:2<241::AID-NAV3220380209>3.0.CO
[6]  
2-Z
[7]   REVERSED GEOMETRIC-PROGRAMMING - A BRANCH-AND-BOUND METHOD INVOLVING LINEAR SUB-PROBLEMS [J].
COLE, F ;
GOCHET, W ;
VANASSCHE, F ;
ECKER, J ;
SMEERS, Y .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1980, 5 (01) :26-35
[8]   A COMPARISON BETWEEN A PRIMAL AND A DUAL CUTTING PLANE ALGORITHM FOR POLYNOMIAL GEOMETRIC-PROGRAMMING PROBLEMS [J].
COLE, F ;
GOCHET, W ;
SMEERS, Y .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1985, 47 (02) :159-180
[10]   SET OF GEOMETRIC PROGRAMMING TEST PROBLEMS AND THEIR SOLUTIONS [J].
DEMBO, RS .
MATHEMATICAL PROGRAMMING, 1976, 10 (02) :192-213