|
Optimization: principles and algorithms, by Michel Bierlaire
|
List of algorithms presented in the book [1]. More...
Files | |
| file | machineEpsilon.m |
| Algorithm 7.1: calculation of the machine epsilon. | |
| file | newtonNVariables.m |
| Algorithm 7.3: Newton's method, n variables. | |
| file | newtonOneVariable.m |
| Algorithm 7.2: Newton's method, one variable. | |
| file | newtonFinDiffNVariables.m |
| Algorithm 8.3: Newton's method with finite differences, n variables. | |
| file | newtonFinDiffOneVariable.m |
| Algorithm 8.1: Newton's method with finite differences, one variable. | |
| file | secantNVariables.m |
| Algorithm 8.4: Newton's secant method, n variables. | |
| file | secantOneVariable.m |
| Algorithm 8.2: Newton's secant method, one variable. | |
| file | conjugateGradient.m |
| Algorithm 9.2: Conjugate gradient algorithm for quadratic problems. | |
| file | quadraticDirect.m |
| Algorithm 9.1: Direct resolution of quadratic problems. | |
| file | newtonLocal.m |
| Algorithm 10.1: Local Newton for optimization. | |
| file | newtonLocalQuadratic.m |
| Algorithm 10.2: Local Newton for optimization using the quadratic model. | |
| file | goldenSection.m |
| Exact line search using golden section. | |
| file | initLineSearch.m |
| Algorithm 11.2: Initialization of the exact line search. | |
| file | lineSearch.m |
| Algorithm 11.5: Line search algorithm. | |
| file | modifiedCholesky.m |
| Algorithm 11:7: Modified Cholesky factorization. | |
| file | newtonLineSearch.m |
| Algorithm 11:8 Newton's method with line search . | |
| file | quadraticInterpolation.m |
| Algorithm 11.3: Exact line search using quadratic interpolation. | |
| file | steepestDescent.m |
| Algorithm 11.6: Steepest descent algorithm. | |
| file | steepestDescentCauchy.m |
| Steepest descent algorithm, calculating the Cauchy point at each iteration. | |
| file | dogleg.m |
| Algorithm 12.2: Dogleg method to find an approximation of the trust region subproblem. | |
| file | intersectionTrustRegion.m |
| Algorithm 12.1: Calculation of the intersection with the trust region. | |
| file | newtonTrustRegion.m |
| Algorithm 12.4: Newton's method with trust region. | |
| file | truncatedConjugateGradient.m |
| Algorithm 12.3: Truncated conjugate gradients method to find an approximation of the trust region subproblem. | |
| file | bfgs.m |
| Algorithm 13.1: BFGS method with line search. | |
| file | symmetricRankOne.m |
| Algorithm 13.2: SR1 method with trust region region. | |
| file | gaussNewton.m |
| Algorithm 14.1: Gauss-Newton method. | |
| file | kalmanFilter.m |
| Algorithms 14.2 and 14.3: Kalman filter update. | |
| file | nelderMead.m |
| Algorithm 15.1: Nelder-Mead algorithm. | |
| file | torczon.m |
| Algorithm 15.2: Torczon algorithm. | |
| file | pivoting.m |
| Algorithm 16.3: Pivoting of the simplex tableau. | |
| file | simplex.m |
| Algorithm 16.2: Simplex methos. | |
| file | simplexTableau.m |
| Algorithm 16.4: Phase II simplex algorithm with tableau. | |
| file | twoPhasesSimplex.m |
| Algorithm 16.5: Two phases simplex algorithm with tableau to solve a linear optimization problem in standard from. | |
| file | vertexEnumeration.m |
| Algorithm 16.1: Vertex enumeration Implementation of algorithm 16.1 of [1]. | |
| file | constrainedNewton.m |
| Algorithm 17.2: preconditioned projected gradient, or constrained Newton. | |
| file | dikin.m |
| Algorithm 17.3: Dikin's method. | |
| file | projectedGradient.m |
| Algorithm 17.1: projected gradient Implementation of algorithm 17.1 of [1]. | |
| file | longSteps.m |
| Algorithm 18.4: long steps interior point algorithm. | |
| file | predictorCorrector.m |
| Algorithm 18.3: Predictor-corrector interior point algorithm. | |
| file | restrictedSteps.m |
| Algorithm 18.2: Interior point algorithm with restricted steps. | |
| file | augmentedLagrangian.m |
| Algorithm 19.1: augmented Lagrangian algorithm. | |
| file | globalSqp.m |
| Algorithm 20.2: global SQP algorithm. | |
| file | localSqp.m |
| Algorithm 20.1: local SQP algorithm. | |
| file | circulationDecomposition.m |
| Algorithm 21.2: circulation decomposition. | |
| file | flowDecomposition.m |
| Algorithm 21.3: flow decomposition. | |
| file | jarnikPrim.m |
| Algorithm 21.4: Jarnik-Prim. | |
| file | nodeDivergence.m |
| Compute the divergence of a flow vector (Definition 21.13 of [1]) | |
| file | prepareNetwork.m |
| Prepares the network for efficient access to the data. | |
| file | simpleCycle.m |
| Algorithm 21.1: Generation of a simple cycle flow from a circulation. | |
| file | incidenceMatrix.m |
| Provide the incidence matrix of the network for the teanshipment problem. | |
| file | transhipment.m |
| Solve a transhipment problem with bound constraints. | |
| file | transhipmentTransform.m |
| Transform a transhipment problem into a problem in standard form. | |
| file | dijkstra.m |
| Algorithm 23.2: Dijkstra. | |
| file | enumeratePaths.m |
| Enumerate all simple paths between two nodes. | |
| file | shortestPath.m |
| Algorithm 23.1: shortest paths. | |
| file | fordFulkerson.m |
| Algorithm 24.2: Ford-Fulkerson. | |
| file | unsaturatedPath.m |
| Algorithm 24.1: unsaturated path. | |
| file | knapsackExact.m |
| Solves the knapsack problem using integer optimization. | |
| file | tspExact.m |
| Write the Traveling Salesman Problem (TSP) as an integer optimization problem in standard form. | |
| file | gomory.m |
| Algorithm 26.3: Gomory cuts for linear optimization. | |
| file | bestInsert.m |
| Identifies the best insertion in a tour for the TSP. | |
| file | getTourList.m |
| Transforms a tour stored as a sequence of cities into a list of successors. | |
| file | getTourSequence.m |
| Transform tour stored as list of successor, into a sequence of cities. | |
| file | insertCity.m |
| Inserts a city in a tour for the TSP. | |
| file | knapsackGreedy.m |
| Solves the knapsack problem using the greedy heuristic described in section 27.1.1 of [1]. | |
| file | ksLocalSearchDeterministic.m |
| Algorithm 27.3: local search for the knapsack problem. | |
| file | ksLocalSearchRandom.m |
| Implementation of a variant of the local search algorithm with random neighbors for the knapsack problen. | |
| file | ksRandomNeighbor.m |
| Algorithm 27.5: neighborhood for the knapsack problem. | |
| file | ksSimulatedAnnealing.m |
| Algorithm 27.7: simulated annealing for the knapsack problem. | |
| file | ksVns.m |
| Algorithm 27.5: VNS for the knapsack problem. | |
| file | randomFromAtoB.m |
| Compute a random integer between A and B. | |
| file | subtourLength.m |
| Calculate the length of a subtour of the TSP. | |
| file | tspInsertion.m |
| Algorithm 27.2: insertion heuristic for TSP. | |
| file | tspInsertionLocalSearch.m |
| Local search method for the TSP based on the insertion heuristic, as described in Section 27.3.2 of [1]. | |
| file | tspLocalSearch.m |
| Algorithm 27.3: local search for the TSP. | |
| file | tspNearestNeighbor.m |
| Algorithm 27.1: nearest neighbor heuristic for TSP. | |
| file | tspSimulatedAnnealing.m |
| Algorithm 27.7: simulated annealing for the TSP. | |
| file | tspTourLength.m |
| Calculate the length of a tour of the TSP. | |
| file | tspVns.m |
| Implements the VNS to solve the TSP, as described in Section 27.3.2 of [1]. | |
| file | twoOpt.m |
| Perform a 2-opt operation of a list of cities. | |
| file | twoOptNeighborhood.m |
| Generate the 2-opt neightborhood for the TSP. | |
| file | twoOptRandomNeighbor.m |
| Generate one random 2-opt neighbor for the TSP. | |
List of algorithms presented in the book [1].