DESCENT APPROACHES FOR QUADRATIC BILEVEL PROGRAMMING

被引：241

作者：

VICENTE, L ^{[1
]}

SAVARD, G ^{[1
]}

JUDICE, J ^{[1
]}

机构：

[1] COLLO MILLITAIRE ROYAL ST JEAN,ST JEAN,PQ,CANADA

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 1994年 / 81卷 / 02期

关键词：

BILEVEL PROGRAMMING; NONCONVEX AND NONDIFFERENTIABLE OPTIMIZATION; QUADRATIC PROGRAMMING; COMPUTATIONAL COMPLEXITY;

D O I：

10.1007/BF02191670

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The bilevel programming problem involves two optimization problems where the data of the first one is implicitly determined by the solution of the second. In this paper, we introduce two descent methods for a special instance of bilevel programs where the inner problem is strictly convex quadratic. The first algorithm is based on pivot steps and may not guarantee local optimality. A modified steepest descent algorithm is presented to overcome this drawback. New rules for computing exact stepsizes am introduced and a hybrid approach that combines both strategies is discussed. It is proved that checking local optimality in bilevel programming is a NP-hard problem.

引用

页码：379 / 399

页数：21

共 29 条

[1]

AIYOSHI E, 1981, IEEE T SYST MAN CYB, V11, P444

[2] A SOLUTION METHOD FOR THE STATIC CONSTRAINED STACKELBERG PROBLEM VIA PENALTY METHOD [J].

AIYOSHI, E ;

SHIMIZU, K .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1984, 29 (12) :1111-1114

[3]

Al-Khayyal F. A., 1992, Annals of Operations Research, V34, P125, DOI 10.1007/BF02098176

[4]

ALKHAYYAL FA, 1987, MATH PROGRAM STUD, V31, P1

[5]

Anandalingam G., 1992, ANN OPERATIONS RES, V34

[6] OPTIMALITY CONDITIONS FOR THE BILEVEL PROGRAMMING PROBLEM [J].

BARD, JF .

NAVAL RESEARCH LOGISTICS, 1984, 31 (01) :13-26

[7] CONVEX 2-LEVEL OPTIMIZATION [J].

BARD, JF .

MATHEMATICAL PROGRAMMING, 1988, 40 (01) :15-27

[8] A BRANCH AND BOUND ALGORITHM FOR THE BILEVEL PROGRAMMING PROBLEM [J].

BARD, JF ;

MOORE, JT .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1990, 11 (02) :281-292

[9]

BI Z, 1991, 180O170591 U WAT TEC

[10]

BI Z, 1991, IEEE T AUTOMATIC CON

← 1 2 3 →