Numerical optimization = 数值最优化 /

introduction.

mathematicalformulation

example:atransportationproblem

continuousversusdiscreteoptimization

constrainedandunconstrainedoptimization

globalandlocaloptimization

stochasticanddeterministicoptimization

optimizationalgorithms

convexity

notesandreferences

fundamentalsofunconstrainedoptimization

2.1whatisasolution?

recognizingalocalminimum

nonsmoothproblems

2.2overviewofalgorithms

twostrategies:linesearchandtrustregion

searchdirectionsforlinesearchmethods

modelsfortrust-regionmethods

scaling

ratesofconvergence

.r-ratesofconvergence

notesandreferences

exercises

linesearchmethods

3.1steplength

thewolfeconditions

thegoldsteinconditions

sufficientdecreaseandbacktracking

3.2convergenceoflinesearchmethods

3.3rateofconvergence.

convergencerateofsteepestdescent

quasi-newtonmethods

newton'smethod

coordinatedescentmethods

3.4step-lengthselectionalgorithms

interpolation

theinitialsteplength

alinesearchalgorithmforthewolfeconditions

notesandreferences

exercises

trust-regionmethods

outlineofthealgorithm

4.1thecauchypointandrelatedalgorithms

thecauchypoint

improvingonthecauchypoint

thedoglegmethod

two-dimensionalsubspaceminimization

steihaug'sapproach..

4.2usingnearlyexactsolutionstothesubproblem

characterizingexactsolutions

calculatingnearlyexactsolutions

thehardcase

proofoftheorem4.3

4.3globalconvergence

reductionobtainedbythecauchypoint

convergencetostationarypoints

convergenceofalgorithmsbasedonnearlyexactsolutions

4.4otherenhancements

scaling

non-euclideantrustregions

notesandreferences

exercises

conjugategradientmethods

5.1thelinearconjugategradientmethod

conjugatedirectionmethods

basicpropertiesoftheconjugategradientmethod

apracticalformoftheconjugategradientmethod

rateofconvergence

preconditioning

practicalpreconditioners

5.2nonlinearconjugategradientmethods

thefletcher-reevesmethod

thepolak-ribi~remethod

quadraticterminationandrestarts

numericalperformance

behaviorofthefletcher-reevesmethod

globalconvergence

notesandreferences

exercises

practicalnewtonmethods

6.1inexactnewtonsteps

6.2linesearchnewtonmethods

linesearchnewton-cgmethod

modifiednewton'smethod

6.3hessianmodifications

eigenvaluemodification

addingamultipleoftheidentity

modifiedcholeskyfactorization

gershgorinmodification

modifiedsymmetricindefinitefactorization

6.4trust-regionnewtonmethods

newton-doglegandsubspace-minimizationmethods

accuratesolutionofthetrust-regionproblem

trust-regionnewton-cgmethod

preconditioningthenewton-cgmethod

localconvergenceoftrust-regionnewtonmethods

notesandreferences

exercises

calculatingderivatives

7.1finite-differencederivativeapproximations

approximatingthegradient

approximatingasparsejacobian

approximatingthehessian;

approximatingasparsehessian

7.2automaticdifferentiation

anexample

theforwardmode

thereversemode

vectorfunctionsandpartialseparability

calculatingjacobiansofvectorfunctions

calculatinghessians:forwardmode

calculatinghessians:reversemode

currentlimitations

notesandreferences

exercises

quasi-newtonmethods

8.1thebfgsmethod

propertiesofthebfgsmethod

implementation

8.2thesr1method

propertiesofsr1updating

8.3thebroydenclass

properties9fthebroydenclass

8.4convergenceanalysis

globalconvergenceofthebfgsmethod

superlinearconvergenceofbfgs

convergenceanalysisofthesr1method

notesandreferences

exercises

large-scalequasi-newtonandpartiallyseparableoptimization

9.1limited-memorybfgs

relationshipwithconjugategradientmethods

9.2generallinaited-memoryupdating

compactrepresentationofbfgsupdating

sr1matrices

unrollingtheupdate

9.3sparsequasi-newtonupdates

9.4partiallyseparablefunctions

asimpleexample

internalvariables

9.5invariantsubspacesandpartialseparability

sparsityvs.partialseparability

grouppartialseparability

9.6algorithmsforpartiallyseparablefunctions

exploitingpartialseparabilityinnewton'smethod

quasi-newtonmethodsforpartiallyseparablefunctions

notesandreferences

exercises

10nonlinearleast-squaresproblems

10.1background

modeling,regression,statistics

linearleast-squaresproblems

10.2algorithmsfornonlinearleast-squaresproblems

thegauss-newtonmethod

thelevenberg-marquardtmethod

implementationofthelevenberg-marquardtmethod

large-residualproblems

large-scaleproblems

10.3orthogonaldistanceregression

notesandreferences

exercises..

11nonlinearequations

11.1localalgorithms

newton'smethodfornonlinearequations

inexactnewtonmethods

broyden'smethod

tensormethods

11.2practicalmethods

meritfunctions

linesearchmethods

trust-regionmethods

11.3continuation/homotopymethods

motivation

practicalcontinuationmethods

notesandreferences

exercises

12theoryofconstrainedoptimization

localandglobalsolutions

smoothness

12.1examples

asingleequalityconstraint

asingleinequalityconstraint

twoinequalityconstraints

12.2first-orderoptimalityconditions

statementoffirst-ordernecessaryconditions

sensitivity

12.3derivationofthefirst-orderconditions

feasiblesequences

characterizinglimitingdirections:constraintqualifications

introducinglagrangemultipliers

proofoftheorem12.1

12.4second-orderconditions

second-orderconditionsandprojectedhessians

convexprograms

12.5otherconstraintqualifications

12.6ageometricviewpoint

notesandreferences

exercises

13linearprogramming:thesimplexmethod

linearprogramming

13.1optimalityandduality

optimalityconditions

thedualproblem

13.2geometryofthefeasibleset

basicfeasiblepoints

verticesofthefeasiblepolytope

13.3thesimplexmethod

outlineofthemethod

finiteterminationofthesimplexmethod

asinglestepofthemethod

13.4linearalgebrainthesimplexmethod

13.5other(important)details

pricingandselectionoftheenteringindex.

startingthesimplexmethod

degeneratestepsandcycling

13.6wheredoesthesimplexmethodfit?

notesandreferences

exercises

14linearprogramming:interior-pointmethods

14.1primal-dualmethods

outline

thecentralpath

aprimal-dualframework

path-followingmethods

14.2apracticalprimal-dualalgorithm

solvingthelinearsystems

14.3otherprimal-dualalgorithmsandextensions

otherpath-followingmethods

potential-reductionmethods

extensions

14.4analysisofalgorithm14.2

notesandreferences

exercises

15fundamentalsofalgorithrasfornonlinearconstrainedoptimization

initialstudyofaproblem

15.1categorizingoptimizationalgorithms

15.2eliminationofvariables

simpleeliminationforlinearconstraints

generalreductionstrategiesforlinearconstraints

theeffectofinequalityconstraints

15.3measuringprogress:meritfunctions

notesandreferences

exercises

16quadraticprogramming

anexample:portfoliooptimization

16.1equality-constrainedquadraticprograms

propertiesofequality-constrainedqps

16.2solvingthekktsystem

directsolutionofthekktsystem

range-spacemethod

null-spacemethod

amethodbasedonconjugacy

16.3inequality-constrainedproblems

optimalityconditionsforinequality-constrainedproblems

degeneracy

16.4active-setmethodsforconvexqp

specificationoftheactive-setmethodforconvexqp

anexample

furtherremarksontheactive-setmethod

finiteterminationoftheconvexqpalgorithm

updatingfactorizations

16.5active-setmethodsforindefiniteqp

illustration

choiceofstartingpoint

failureoftheactive-setmethod

detectingindefinitenessusingthelblrfactorizafion

16.6thegradient-projectionmethod

cauchypointcomputation

subspaceminimization

16.7interior-pointmethods

extensionsandcomparisonwithactive-setmethods.

16.8duality

notesandreferences

exercises

17penalty,barrier,andaugmentedlagrangianmethods

17.1thequadraticpenaltymethod

motivation

algorithmicframework

convergenceofthequadraticpenaltyfunction

17.2thelogarithmicbarriermethod

propertiesoflogarithmicbarrierfunctions

algorithmsbasedonthelog:barrierfunction

propertiesofthelog-barrierfunctionandframework17.2

handlingequalityconstraints

relationshiptoprimal-dualmethods

17.3exactpenaltyfunctions

17.4augmentedlagrangianmethod

motivationandalgorithmframework

extensiontoinequalityconstraints

propertiesoftheaugmentedlagrangian

practicalimplementation

17.5sequentiallinearlyconstrainedmethods

notesandreferences

exercises

18sequentialquadraticprogramming

18.1localsqpmethod

sqpframework

inequalityconstraints

iqpvs.eqp

18.2previewofpracticalsqpmethods

18.3stepcomputation

equalityconstraints

inequalityconstraints

18.4thehessianofthequadraticmodel

fullquasi-newtonapproximations

hessianofaugmentedlagrangian

reduced-hessianapproximations

18.5meritfunctionsanddescent

l8.6alinesearchsqpmethod

18.7reduced-hessiansqpmethods

somepropertiesofreduced-hessianmethods

updatecriteriaforreduced-hessianupdating

changesofbases

apracticalreduced-hessianmethod

18.8trust-regionsqpmethods

approachi:shiftingtheconstraints

approachii:twoellipticalconstraints

approachiii:se1qp(sequentialglquadraticprogramming)

18.9apracticaltrust-regionsqpalgorithm

18.10rateofconvergence

convergencerateofreduced-hessianmethods

18.11themaratoseffect

second-ordercorrection

watchdog(nonmonotone)strategy

notesandreferences

exercises

abackgroundmaterial

a.1elementsofanalysis,geometry,topology

topologyoftheeuclideanspacern

continuityandlimits

derivatives

directionalderivatives

meanvaluetheorem

implicitfunctiontheorem

geometryoffeasiblesets

ordernotation..

root-findingforscalarequations

a.2elementsoflinearalgebra

vectorsandmatrices

norms

subspaces

eigenvalues,eigenvectors,andthesingular-valuedecomposition

determinantandtrace

matrixfactorizations:cholesky,lu,qr

sherman-morrison-woodburyformula

interlacingeigenvaluetheorem

erroranalysisandfloating-pointarithmetic

conditioningandstability...