资源描述：
《Convex Optimization Overview 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ConvexOptimizationOverviewZicoKolterOctober19,20071IntroductionManysituationsariseinmachinelearningwherewewouldliketooptimizethevalueofsomefunction.Thatis,givenafunctionf:Rn→R,wewanttofindx∈Rnthatminimizes(ormaximizes)f(x).Wehavealreadyseenseveralexamplesofoptimizationproble
2、msinclass:least-squares,logisticregression,andsupportvectormachinescanallbeframedasoptimizationproblems.Itturnsoutthatinthegeneralcase,findingtheglobaloptimumofafunctioncanbeaverydifficulttask.However,foraspecialclassofoptimizationproblems,knownasconvexoptimizationproblems,wec
3、anefficientlyfindtheglobalsolutioninmanycases.Here,“efficiently”hasbothpracticalandtheoreticalconnotations:itmeansthatwecansolvemanyreal-worldproblemsinareasonableamountoftime,anditmeansthattheoreticallywecansolveproblemsintimethatdependsonlypolynomiallyontheproblemsize.Thegoalo
4、fthesesectionnotesandtheaccompanyinglectureistogiveaverybriefoverviewofthefieldofconvexoptimization.Muchofthematerialhere(includingsomeofthefigures)isheavilybasedonthebookConvexOptimization[1]byStephenBoydandLievenVandenberghe(availableforfreeonline),andEE364,aclasstaughthere
5、atStanfordbyStephenBoyd.Ifyouareinterestedinpursuingconvexoptimizationfurther,thesearebothexcellentresources.2ConvexSetsWebeginourlookatconvexoptimizationwiththenotionofaconvexset.Definition2.1AsetCisconvexif,foranyx,y∈Candθ∈Rwith0≤θ≤1,θx+(1−θ)y∈C.Intuitively,thismeansthatif
6、wetakeanytwoelementsinC,anddrawalinesegmentbetweenthesetwoelements,theneverypointonthatlinesegmentalsobelongstoC.Figure1showsanexampleofoneconvexandonenon-convexset.Thepointθx+(1−θ)yiscalledaconvexcombinationofthepointsxandy.1(a)(b)Figure1:Examplesofaconvexset(a)andanon-con
7、vexset(b).2.1Examples•AllofRn.Itshouldbefairlyobviousthatgivenanyx,y∈Rn,θx+(1−θ)y∈Rn.•Thenon-negativeorthant,Rn.Thenon-negativeorthantconsistsofallvectorsin+Rnwhoseelementsareallnon-negative:Rn={x:x≥0∀i=1,...,n}.Toshow+ithatthisisaconvexset,simplynotethatgivenanyx,y∈Rnand0≤
8、θ≤1,+(θx+(1−θ)y)i=θxi+(1−θ)yi≥0∀i.•Normballs.Letk·kbesomenormonRn(e.g.,theEuclidea
