Optimization Course [최민주 교수님 최적화 수업]

1. Linear programming
2. Simplex
3. Mixed integer programming
4. Binary integer programming
5. Goal programming
6. Network models, Graph theory
7. Minimum spanning tree
8. Stenier tree problem
9. A* (A star)
10. Non-linear optimization problems and nonlinear programming
11. Meta-heuristics
12. Genetic algorithm (GA)
13. Particle swarm optimization

Linear programming

: to find optimal value(s) for unknown parameter(s) to maximize/minimize a cost function

https://brilliant.org/wiki/linear-programming/

Simplex

: an algorithm to solve the linear programming iteratively (including mixed integer, binary integer, and goal programming)

https://www.youtube.com/watch?v=jh_kkR6m8H8

​

Mixed-integer (linear) programming

: types of the parameters are integer (not float or double)

https://www.youtube.com/watch?v=RhHhy-8sz-4&list=LL3ox-8ZsbTY0E9Y2-RYqTYw&index=4&t=6s

​

Binary integer (linear) programming

: types of the parameters are binary (zero or one)

https://www.youtube.com/watch?v=-3my1TkyFiM&list=LL3ox-8ZsbTY0E9Y2-RYqTYw&index=5&t=0s

​

Goal programming

: has multiple cost functions (= multiple goals)

https://www.youtube.com/watch?v=D1xYQdnmKvY

​

Network models, Graph theory

: network model is just like a neural network model, which consists of nodes and edges

: In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects

- graph theory video: https://www.youtube.com/watch?v=82zlRaRUsaY&list=PLsJWgOB5mIMAuH3cHa-MXukX6-RPpDXgl&index=4

Minimum spanning tree (MST)

: to find the shortest path for the traveling salesman person problem

: there are two main algorithms to find the minimum spanning tree.

1) Prims algorithm, 2) Kruskals algorithms

- Prims algorithm in detail: https://www.youtube.com/watch?v=jsmMtJpPnhU

- comparative explanation about the Prims and Kruskals: https://www.youtube.com/watch?v=4ZlRH0eK-qQ

Stenier tree problem

: to find the mimimum spanning tree, it adds "stenier point" to bridge the existing nodes.

- algorithm for the Stenier tree problem: more research is required, not yet understood.

A* (A star)

: 전산학 분야에 있어서, A* 알고리즘(A* algorithm 에이 스타 알고리듬[*])은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프/트리 탐색 알고리즘 중 하나이다.

https://www.youtube.com/watch?v=-L-WgKMFuhE

Non-linear optimization problems and nonlinear programming

: In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear.

Non-linear optimization problem ($x_0$ denotes an initial guess)

https://apmonitor.com/pdc/index.php/Main/NonlinearProgramming (includes the python code)

On the reference website, scipy.optimize is used and there are lots of multivariate optimization methods for minimize (link).

Meta-heuristics

: 휴리스틱이란? 합리적인 계산 비용으로 최적 또는 거의 최적의 솔루션을 찾는 기술

: 메타휴리스틱이란? 특정 문제에 특화되지 않고 자연에서 영감을 얻은 경험적 방법

: 자주 사용되는 메타휴리스틱 방법

• Genetic Algorithm(GA)
• Tabu Search(TS)
• Ant Colony Optimization(ACO)
• Partical Swarm Optimization(PSO)
• Simulated Annealing(SA)

https://zzsza.github.io/data/2019/03/26/metaheuristics/

​

Genetic algorithm (GA)

: In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover, and selection.

Particle swarm optimization (PSO)

: In computational science, particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. It solves a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formulae over the particle's position and velocity. Each particle's movement is influenced by its local best-known position but is also guided toward the best-known positions in the search-space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions. This is one of the EA algorithms.

A particle swarm searching for the global minimum of a function

a) Inertia: particle 자신의 이전 속도, b) Individual best(cognitive force): 각각 particle의 best known position으로부터의 거리, c) Swarm best(social force): swarm best known position과의 거리

https://www.youtube.com/watch?v=JhgDMAm-imI