The distance between two convex sets

被引：27

作者：

Dax, Achiya ^{[1
]}

机构：

[1] Hydrol Serv, IL-91360 Jerusalem, Israel

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2006年 / 416卷 / 01期

关键词：

a new minimum norm duality theorem; the distance between two convex polytopes; the distance between two ellipsoids; linear least norm problems; inconsistent systems of linear inequalities; the polar decomposition of the least deviation problem; theorems of the alternatives; steepest descent directions; constructive optimality conditions; the double role of duality in least norm problems;

D O I：

10.1016/j.laa.2006.03.022

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we explore the duality relations that characterize least norm problems. The paper starts by presenting a new Minimum Norm Duality (MND) theorem, one that considers the distance between two convex sets. Roughly speaking the new theorem says that the shortest distance between the two sets is equal to the maximal "separation" between the sets, where the term "separation" refers to the distance between a pair of parallel hyperplanes that separates the two sets. The second part of the paper brings several examples of applications. The examples teach valuable lessons about the role of duality in least norm problems, and reveal new features of these problems. One lesson exposes the polar decomposition which characterizes the "solution" of an inconsistent system of linear inequalities. Another lesson reveals the close links between the MND theorem, theorems of the alternatives, steepest descent directions, and constructive optimality conditions. (c) 2006 Elsevier Inc. All rights reserved.

引用

页码：184 / 213

页数：30

共 54 条

[1]

[Anonymous], PIVOTING EXTENSION

[2]

[Anonymous], 1991, NUMERICAL LINEAR ALG

[3]

[Anonymous], 1985, FINITE ALGORITHMS OP

[4]

[Anonymous], 2001, LECT MODERN CONVEX O, DOI 10.1137/1.9780898718829.ch6