2006 The distance between two convex sets

几何,凸集,凸多面体国外文献

LinearAlgebraanditsApplications416(2006)

184–213

http://wendang.chazidian.com/locate/laa

Thedistancebetweentwoconvexsets

AchiyaDax?

HydrologicalService,P.O.Box36118,Jerusalem91360,Israel

Received2February2005;accepted19March2006

SubmittedbyA.Berman

Abstract

Inthispaperweexplorethedualityrelationsthatcharacterizeleastnormproblems.ThepaperstartsbypresentinganewMinimumNormDuality(MND)theorem,onethatconsidersthedistancebetweentwoconvexsets.Roughlyspeakingthenewtheoremsaysthattheshortestdistancebetweenthetwosetsisequaltothemaximal“separation”betweenthesets,wheretheterm“separation”referstothedistancebetweenapairofparallelhyperplanesthatseparatesthetwosets.

Thesecondpartofthepaperbringsseveralexamplesofapplications.Theexamplesteachvaluablelessonsabouttheroleofdualityinleastnormproblems,andrevealnewfeaturesoftheseproblems.Onelessonexposesthepolardecompositionwhichcharacterizesthe“solution”ofaninconsistentsystemoflinearinequalities.AnotherlessonrevealsthecloselinksbetweentheMNDtheorem,theoremsofthealternatives,steepestdescentdirections,andconstructiveoptimalityconditions.

©2006ElsevierInc.Allrightsreserved.

Keywords:Anewminimumnormdualitytheorem;Thedistancebetweentwoconvexpolytopes;Thedistancebetweentwoellipsoids;Linearleastnormproblems;Inconsistentsystemsoflinearinequalities;Thepolardecompositionoftheleastdeviationproblem;Theoremsofthealternatives;Steepestdescentdirections;Constructiveoptimalityconditions;Thedoubleroleofdualityinleastnormproblems

1.Introduction

LetYbeanonemptyclosedconvexsetandletzbesomepointoutsideY.Thebestapproxima-tionproblemisto?ndapointy?∈YwhichisclosesttozamongallthepointsofY.Theinterestinthisproblemiscommontoseveralbranchesofmathematics,suchasApproximationTheory,FunctionalAnalysis,ConvexAnalysis,Optimization,NumericalLinearAlgebra,Statistics,andTel.:+97226442506;fax:+97226442529.

E-mailaddress:dax20@water.gov.il

0024-3795/$-seefrontmatter(2006ElsevierInc.Allrightsreserved.doi:10.1016/j.laa.2006.03.022

几何,凸集,凸多面体国外文献

A.Dax/LinearAlgebraanditsApplications416(2006)184–213

185

Fig.1.TheNirenberg–LuenbergerMNDtheorem.

other?elds.However,thedualitypropertiesofthisproblemarenotquitewellknownbehindtheHahn–Banachtheoryonboundedlinearfunctionalsinnormedlinearvectorspaces.Oneaimofthispaperis,therefore,topointattentiontotheelegancyofthedualityrelationswhichcharacterizethebestapproximationproblem.AsecondaimistoshowthatinRmtheseresultscanbederivedfromsimplegeometricarguments,withoutinvokingtheHahn–BanachtheoremorthedualitytheoremsofLagrangeandFenchel.Athirdaimofthispaperistoestablishanewdualitytheorem,onethatconsidersthedistancebetweentwoconvexsets.

TheMinimumNormDuality(MND)theoremconsidersthedistancebetweenapointzandaconvexsetY.ItsaysthattheshortestdistancefromztoYisequaltothemaximumofthedistancesfromztoanyhyperplaneseparatingzandY(seeFig.1).Thisfundamentalobservationgivesrisetoseveralusefuldualityrelationsinbestapproximationproblems,linearleastnormproblems,andtheoremsofthealternative.Asfarasweknow,the?rststatementoftheMNDtheoremisduetoNirenberg[40],whoestablishedthisassertioninanynormedlinearspacebyapplyingtheHahn–Banachtheorem.Thename“MNDtheorem”wascoinedbyLuenberger[29],whoalsoderivedthe“alignment”relationbetweenprimalanddualsolutions.

ThenewMNDtheoremconsidersthedistancebetweentwoconvexsets.Roughlyspeakingitsaysthattheshortestdistancebetweenthetwosetsisequaltothemaximal“separation”betweenthesets,wheretheterm“separation”referstothedistancebetweenapairofparallelhyperplanesthatseparatesthetwosets(seeFig.2).

InordertodistinguishbetweenthetwoMNDtheoremswerefertothe?rstoneastheNi-renberg–LuenbergerMNDtheorem.(AlthoughitisquitepossiblethatthetheoremwasknownearlierasresultofthegeometricHahn–Banachtheorem.)ItisnotedinthelastsectionthatthenewMNDtheoremcanbederivedfromthe?rstone.However,whileformerproofsofthe

几何,凸集,凸多面体国外文献

186A.Dax/LinearAlgebraanditsApplications416(2006)

184–213

Fig.2.ThenewMNDtheorem.

Nirenberg–LuenbergertheoremrelyontheHahn–Banachtheoreminageneralnormedlinearvectorspace,e.g.,[19,20,27,29,40],thereareseveralpracticalapplicationswhichconsiderconvexsetsinRm.Seethesecondpartofthepaper.Thisraisesthequestionofwhetherwecan?ndadirectproofthatdoesnotrelyontheHahn–Banachtheory.Afurtheraimofthispaperis,therefore,toprovideanelementaryproofwhichisbasedonsimplegeometricideas.ForthispurposethecomingdiscussionisrestrictedtoconvexsetsinRm.

Theplanofourpaperisasfollows.The?rstpartcontainsnecessarybackground.Section2explainsthebasicfactsondualnormsandalignment.Section3derivesanexplicitformulaforthedistancebetweenapointandhyperplane.Thisformulaisusedtocalculatethedistancebetweentwoparallelhyperplanes.ThenecessaryfactsonsupportfunctionsandseparatinghyperplanesaregiveninSection4.ThereaderwhoisfamiliarwiththeseissuesmayskiptoSection5,inwhichthenewMNDtheoremisproved.

Thesecondpartofthepaperbringsseveralexamplesofapplications.Theexamplesteachvaluablelessonsaboutdualityinlinearleastnormproblems,andrevealseveralnewfeaturesoftheseproblems.Onelessonexposestheroleofthepolardecompositionwhen“solving”aninconsistentsystemoflinearinequalities.AnotherlessonrevealsthecloselinksbetweentheMNDtheorem,theoremsofthealternative,steepestdescentdirections,andconstructiveoptimalityconditions.

几何,凸集,凸多面体国外文献

A.Dax/LinearAlgebraanditsApplications416(2006)184–213187

Part1:Anewminimumnormdualitytheorem

2.Normsandduality

AnormonRmisareal-valuedfunction??·??whichmapseachvectorxinRmintoarealnumber??x??andsatis?esthefollowingthreerequirements:

(a)??x?? 0?x∈Rmand??x??=0?x=0;

(b)??x+z??????x??+??z???x,z∈Rm;

(c)??ax??=|a|·??x???a∈R,x∈Rm.

Recallthat??x??isaconvexfunctionwhiletheunitnormball

B={x|??x????1}

isaclosedboundedconvexsetwhichcontainstheorigininitsinterior;seeRefs.[25,49].Thedualnormto??·??isdenotedby??·????.Thisnormisobtainedfrom??·??inthefollowingway.Givenavectorz∈Rm,then??z????isde?nedbythefollowingrule:

??z????=maxxTz.??x????1

Forthesakeofclaritywementionthat

xz=Tm??

i=1xiziforallx=(x1,...,xm)T∈Rmandz=(z1,...,zm)T∈Rm.

SinceBisacompactset,theoptimalvalueisattainedforsomevectorx∈B.Theabovede?nitionimpliesthegeneralHölderinequality

|xTz|????x????z????,

xTz=??x????z????

issaidtobealignedwithrespectto??·??or??·????.

AwellknownexampleofdualnormsinRmisrelatedtothe??pnorm

??1/p??m??|xi|p,??x??p=

i=1?x,z∈Rm,andthat??·??isthedualnormto??·????.Apairofvectorsthatsatisfytheequality

where1<p<∞isarealnumber.Thedualnormisthe??qnorm

??1/q??m??|zi|q,??z??q=

i=1

whereq=p/(p?1).Thatis,1/p+1/q=1.Thispairofdualnormssatis?estheHölderinequality

m??

i=1|xizi|????x??p??z??q,

几何,凸集,凸多面体国外文献

188A.Dax/LinearAlgebraanditsApplications416(2006)184–213

andthevectorsxandzarealignedifandonlyif

sign(xi)=sign(zi)and(|xi|/??x??p)1/q=(|zi|/??z??q)1/pfori=1,...,m,

e.g.,[29]or[54].Similardualityrelationsholdbetweenthe??1norm

m????x??1=|xi|

i=1

andthe??∞norm

??z??∞=max|zi|,i=1,...,m

butthealignmentrelationsneedsomecorrections.Whenp=q=2weobtaintheEuclideannorm,??1/2??m????x??2=(xTx)1/2=xi2,

i=1

whichisprivilegedtobeitsowndual.

LetzbeagivenpointinRm.Then,x∈Rmisadualvectorofzwithrespectto??·??ifitsatis?es??x??=1andxTz=??z????.Theuniquenessofthedualvectorisrelatedtothequestionofwhether??·??isastrictlyconvexnorm.Recallthatanorm??·??issaidtobestrictlyconvexiftheunitsphere{x|??x??=1}containsnolinesegment.Now,onecanverifythatanorm??·??isstrictlyconvexifandonlyifeachz∈Rmhasauniquedualvector.

Anorm??·??iscalledsmoothif,ateachboundarypointofB,thereisauniquehyper-planethatsupportsB.OfcourseasmoothnormisnotnecessarilystrictlyconvexandviceTu=nTx}beaversa.However,thereareinterestinglinksbetweentheseproperties.Let{u|n000msupportinghyperplaneofBatapointx0,??x0??=1,withanormalvectorn0∈R.Thatis,Tx??nTx?x∈B.(TheexistenceofasupportinghyperplaneisestablishedinSection4.)Then000

lastinequalitymeansthatx0isadualvectorofn0withrespectto??·??.Thisshowsthatx0andn0arealignedandthatn0/??n0????isadualvectorofx0withrespectto??·????(seeFig.3).Therefore,ifthereismorethanonesupportinghyperplaneatx0,thenthedualvectorofx0withrespectto??·????isnotunique.Inotherwords,??·????isstrictlyconvexifandonlyif??·??issmooth.Itisalsoworthwhilementioningthatanormissmoothifandonlyifitiscontinuouslydifferentiableateachpointx=/0;e.g.,[44,pp.113–118].Forfurtherdiscussionofdualnormsandtheirpropertiessee

[18,25,26,46,54].

3.Thedistancebetweenparallelhyperplanes

Let??·??besomearbitrarynorminRmandlet??·????denotethecorrespondingdualnorm.AhyperplaneinRmisasetoftheform

H={x|aTx=α},

wherea∈Rmandα∈R.ThedistancebetweenHandapointz∈Rmisde?nedas

dist(z,H)=inf??z?x??.x∈H

Assume?rstthatzliesinthepositivesideofH.Thatis,aTz>α.Inthiscaseonecanverifythat

(3.1)dist(z,H)=(aTz?α)/??a????.

Otherwise,whenzliesinthenegativesideofH,

dist(z,H)=(α?aTz)/??a????.