On the complexity of equalizing inequalities

被引：7

作者：

Jongen, HT ^{[1
]}

Stein, O ^{[1
]}

机构：

[1] Univ Aachen, Dept Math C, D-5100 Aachen, Germany

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2003年 / 27卷 / 04期

关键词：

Euler characteristic; interior point method; logarithmic smoothing; Morse theory; quadratic slack;

D O I：

10.1023/A:1026051901133

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study two approaches to replace a finite mathematical programming problem with inequality constraints by a problem that contains only equality constraints. The first approach lifts the feasible set into a high-dimensional space by the introduction of quadratic slack variables. We show that then not only the number of critical points but also the topological complexity of the feasible set grow exponentially. On the other hand, the second approach bases on an interior point technique and lifts an approximation of the feasible set into a space with only one additional dimension. Here only Karush-Kuhn-Tucker points with respect to the positive and negative objective function in the original problem give rise to critical points of the smoothed problem, so that the number of critical points as well as the topological complexity can at most double.

引用

页码：367 / 374

页数：8