最优化理论期末作业.docx

最优化理论期末作业.docx

《最优化理论期末作业.docx》由会员分享，可在线阅读，更多相关《最优化理论期末作业.docx（38页珍藏版）》请在冰点文库上搜索。

最优化理论期末作业

FinalworkforCVXoptimization

BarrierMethodandPrimal-dualInterior-pointMethodforLinearProgramming

Name:

****

StudentID:

********

Major:

CommunicationandInformationSystem

2015/7/16Thursday

BarrierMethodandPrimal-dualInterior-pointMethod

forLinearProgramming

SchoolofInformationScienceandEngineering,

ShandongUniversity,P.R.China,250100

*@

Abstract：

Interior-pointmethods（IMP）forsolvingconvexoptimizationproblemsthatincludeinequalityconstraints.ThemostattractivefeaturesofIMPareitsspeedofconvergenceanditsrobustcapabilityofhandlingequalityandinequalityconstraints;makingitselfapracticaltoolforsolvinglarge-scaleoptimizationproblems.Inthispaper,twokindsofinterior-pointmethods—barriermethodandprimal-dualinterior-pointmethod,arediscussed.AndComparisonofthesetwomethodsisgiven,basedonsolvingthestandardLP.

Keywords:

Interior-pointmethod,Barriermethod,Primal-dualinterior-pointmethod,LP.

1Introduction

Theinterior-pointmethodisalmostusedtosolveconvexoptimizationproblemsthatincludeinequalityconstraints.Interior-pointmethodssolvetheproblem（ortheKKTconditions）byapplyingNewton’smethodtoasequenceofequalityconstrainedproblems,ortoasequenceofmodifiedversionsoftheKKTconditions.Wecanviewinterior-pointmethodsasanotherlevelinthehierarchyofconvexoptimizationalgorithms.Linearequalityconstrainedquadraticproblemsarethesimplest.FortheseproblemstheKKTconditionsareasetoflinearequations,whichcanbesolvedanalytically.Newton’smethodisthenextlevelinthehierarchy.WecanthinkofNewton’smethodasatechniqueforsolvingalinearequalityconstrainedoptimizationproblem,withtwicedifferentiableobjective,byreducingittoasequenceoflinearequalityconstrainedquadraticproblems.Interior-pointmethodsformthenextlevelinthehierarchy:

Theysolveanoptimizationproblemwithlinearequalityandinequalityconstraintsbyreducingittoasequenceoflinearequalityconstrainedproblems.

2Theorybasis

Inthischapterwediscussinterior-pointmethodsforsolvingconvexoptimizationproblemsthatincludeinequalityconstraints,

（2.1）

where

areconvexandtwicecontinuouslydifferentiable,and

with

.Weassumethattheproblemissolvable,i.e.,anoptimal

exists.Wedenotetheoptimalvalue

as

.

Wealsoassumethattheproblemisstrictlyfeasible,thismeansthatSlater’sconstraintqualificationholds,sothereexistdualoptimal

whichtogetherwith

satisfytheKKTconditions

（2.2）

Interior-pointmethodssolvetheproblem（2.1）（ortheKKTconditions（2.2））byapplyingNewton’smethodtoasequenceofequalityconstrainedproblems,ortoasequenceofmodifiedversionsoftheKKTconditions.

2.1BarrierMethod

Toapproximatelyformulatetheinequalityconstrainedproblem（2.1）asanequalityconstrainedproblemtowhichNewton’smethodcanbeapplied.Ourfirststepistorewritetheproblem（2.1）,makingtheinequalityconstraintsimplicityintheobjective:

（2.3）

where

istheindicatorfunctionforthenonpositivereals,

（2.4）

Figure1Thedashedlinesshowthefunction

andthesolidcurvesshow

for

.Thecurvefor

givesthebestapproximation.

Thebasicideaofthebarriermethodistoapproximatetheindicatorfunction

:

wheret>0isaparameterthatsetstheaccuracyoftheapproximation.Substituting

for

in（2.3）givestheapproximation

（2.5）

Theobjectivehereisconvex,since

isconvexandincreasingin

anddifferentiable.Assuminganappropriateclosednessconditionholds,Newton’smethodcanbeusedtosolveit.wemultiplytheobjectiveby

andconsidertheequivalentproblem

（2.6）

whichhasthesameminimizers.

Thealgorithmisasfollowing:

2.2Primal-dualinterior-pointmethods

Primal-dualinterior-pointmethodsareverysimilartothebarriermethod,withsomedifferences.

●Thereisonlyonelooporiteration,i.e.,thereisnodistinctionbetweeninnerandouteriterationsasinthebarriermethod.Ateachiteration,boththeprimalanddualvariablesareupdated.

●Thesearchdirectionsinaprimal-dualinterior-pointmethodareobtainedfromNewton’smethod,appliedtomodifiedKKTequations（i.e.,theoptimalityconditionsforthelogarithmicbarriercenteringproblem）.Theprimaldualsearchdirectionsaresimilarto,butnotquitethesameas,thesearchdirectionsthatariseinthebarriermethod.

●Inaprimal-dualinterior-pointmethod,theprimalanddualiteratesarenotnecessarilyfeasible.

Primal-dualinterior-pointmethodsareoftenmoreefficientthanthebarriermethod,especiallywhenhighaccuracyisrequired,sincetheycanexhibitbetterthanlinearconvergence.

Thebasicprimal-dualinterior-pointalgorithmisasfollowing:

3Problemsforexample

Inthissection,wegivetwoexamplestoexaminetheperformanceofthetwomethods,andgivethesimulationresult.

3.1AfamilyofStandardLPbyBarrierMethod

3.1.1Problemanalysis

Inthissectionweexaminetheperformanceofthebarriermethodasafunctionoftheproblemdimensions.WeconsiderLPsinstandardform,

（3.1）

with

andexplorethetotalnumberofNewtonstepsrequiredasafunctionofthenumberofvariables

andnumberofequalityconstraints

forafamilyofrandomlygeneratedprobleminstances.Wetake

i.e.,twiceasmanyvariablesasconstraints.

Theproblemsweregeneratedasfollows.Theelementsof

areindependentandidenticallydistributed,withzeromean,unitvariancenormaldistribution

.Wetake

wheretheelementsof

areindependent,anduniformlydistributedin[0,1].Thisensuresthattheproblemisstrictlyprimalfeasible,since

isfeasible.Toconstructthecostvector

wefirstcomputeavector

withelementsdistributedaccordingtoN（0,1）andavector

withelementsfromauniformdistributionon[0,1].Wethentake

.Thisguaranteesthattheproblemisstrictlydualfeasible,since

.Thealgorithmparametersweuseare

andthesameparametersforthecenteringstepsintheexamplesabove:

backtrackingparameters

andstoppingcriterion

.Theinitialpointisonthecentralpathwith

（i.e.,gapn）.Thealgorithmisterminatedwhentheinitialdualitygapisreducedbyafactor

.

Figure2theprogramchartofBarriermethod,usingNewton’smethodforcentralpath

Inthispart,theproblemwillbediscussedintwoparts:

oneistherelationshipbetweendualitygapsversusiterationnumber;theotheristheeffectofproblemsizeonthenumberofNewtonstepsrequired.

●Todiscusstherelationshipbetweendualitygapversusiterationnumber,thispapercomputesthedualitygapversusiterationnumberforthreeprobleminstances,withm=50,m=500,m=1000.

●ToexaminetheeffectofproblemsizeonthenumberofNewtonstepsrequired,thispapergenerate100probleminstancesforeachof20valuesofm,rangingfromm=10tom=1000.Wesolveeachofthese2000problemsusingthebarriermethod,nothingbutthenumberofNewtonstepsrequired.

3.1.2Simulationresultandanalysis

TheFigure3showsthedualitygapversusiterationnumberforthreeprobleminstances.Theplotsshowapproximatelylinearconvergenceofthedualitygap.TheplotsshowasmallincreaseinthenumberofNewtonstepsrequiredastheproblemsizegrowsfrom50constraints（100variables）to1000constraints（2000variables）.

Figure3ProgressofbarriermethodforasmallLP,showingdualitygapversuscumulativenumberofNewtonsteps.Threeplotsareshown,correspondingtothreevaluesoftheparameterµ:

2,50,and150.Ineachcase,wehaveapproximatelylinearconvergenceofdualitygap.

Figure4AveragenumberofNewtonstepsrequiredtosolve100randomly

generatedLPsofdifferentdimensions,withn=2m.

TheFigure4showsthemeanandstandarddeviationinthenumberofNewtonsteps,foreachvalueofm.Fromthecomputingconclusion,wecangetthatthestandarddeviationisaround2iterations,andappearstobeapproximatelyindependentofproblemsize.Sincetheaveragenumberofstepsrequiredisnear23（arrangedfrom17to29）,thismeansthatthenumberofNewtonstepsrequiredvariesonlyaround±10%.Thisbehavioristypicalforthebarriermethodingeneral:

ThenumberofNewtonstepsrequiredgrowsveryslowlywithproblemdimensions,andisalmostalwaysaroundafewtens.Ofcourse,thecomputationalefforttocarryoutoneNewtonstepgrowswiththeproblemdimensions.

3.1.3MainCodeforStandardLP

function[gaps,inniters]=logbarrier（A,x0,b,c,m,n）

MaxCalTime=1000;

x=x0;

u=20;

alpha=0.01;

beta=0.5;

t=1;

ErrNT=1e-5;

ErrGap=1e-3;

gaps=[];

inniters=[];

forinter1=1:

MaxCalTime

grad=t*c-（1./（x））;%

w=-（A*diag（x.^2）*A'）\（A*（grad.*（x.^2）））;

Xnt=-（A'*w+grad）.*（x.^2）;%

Lamd2=-（grad+A'*w）'*Xnt;%

ifLamd2<=2*ErrNT%

z=-w/t;

gap=x'*（c-A'*z）;

inniters=[inniters,inter1];

gaps=[gaps,gap];

if（gap

break;

end

t=min（t*u,（n+1）/ErrGap）;%

continue;

end

%

step=1;

while（min（x+step*Xnt）<0）

step=beta*step;

end

while（step*（t*c+A'*w）'*Xnt-sum（log（1+step*Xnt./x））>alpha*step*Lamd2）

step=beta*step;

end

%

x=x+step*Xnt;

end

end

3.2SmallLPforPrimal-dualinterior-pointmethods

3.2.1Problemanalysis

Inthissectionweillustratetheperformanceoftheprimal-dualinterior-pointmethodasafunctionoftheproblemdimensions.Weconsiderasmalllinearprogramminginequalityform,

（3.2）

with

.Thedataweregeneratedrandomly,insuchawaythattheproblemisstrictlyprimalanddualfeasible,withoptimalvalue