최적화,optimization

optimization problem/algorithm, optimizer, optimality, etc. 에 대해

최적화 문제: optimal(best) way of doing something을 찾는 것.
이것은 함수,function최대,maximum/최소,minimum 값,value을 찾는 것으로 reduce(환원,reduction)될 수 있음.
극값,extremum(rel. 최대최소,maximum_and_minimum)을 찾는.

일단 [https]수학백과 선형계획법 앞부분 참조

대체적으로 어떤 '제약, 제약조건 constraint'이 있고 그 한계 안에서 최적의 방법을 찾음.
tmp
{
https://blog.naver.com/birth1104/222255353645 보면 등식제약, 부등식제약이 있음 - 등식,equality, 부등식,inequality 제약,constraint(writing)
KKT_조건,KKT_condition은 부등식제약조건
}

제약,constraint이 없는 최적화는 unconstrained_optimization ? QQQ


정의는 간단. 실수값 함수 $f$ 에서 (특정 조건인...TBW) $x_0$ 를 찾는 것. (cz Optimization_(mathematics))

Sub:
global_optimization
discrete_optimization { WpEn:Discrete_optimization }
continuous_optimization { WpEn:Continuous_optimization }

hyperparameter_optimization - writing // ML에서.
하이퍼파라미터 최적화

Bayesian_optimization - writing // ML에서.
베이즈 최적화 / 베이지안 최적화
... Google:bayesian optimization

(TBD: 이 sub들 산업공학/OR에서 다루는 거랑, CS(algorithm)에서 다루는 거, ML에서 다루는 거... etc 이런식으로 분류할 수/나눌 수 있는지? 아님 그럴 수 없거나 그럴 필요 없는지?)

see also 알고리듬,algorithm#s-3 - 동적계획법,dynamic_programming,DP

머신러닝/딥러닝에서 말하는 최적화는 항상 손실함수,loss_function 비용함수,cost_function의 최소를 찾는 것과 연관인지? 예외가 있다면?

code_generation 에서 말하는 executable_code 에 대한 최적화는 goto 코드최적화,code_optimization and/or 컴파일러최적화,compiler_optimization.



1. 선형계획법 linear_programming LP


선형계획법,linear_programming
{
선형계획법, 선형계획, 리니어 프로그래밍, linear programming, LP

arguments가 linear constraints(선형 제약,constraint) 아래 있을 때, 선형함수,linear_function의 최대 또는 최소(최대최소,maximum_and_minimum)를 찾는 방법/절차(procedure)를 linear programming이라 한다. 간단한 방법으로는 simplex법이 있다. (foldoc)

최적화의 특수한 경우가 선형계획.
최적화문제 중 목적함수,objective_function제한조건,constraint이 모두 일차식으로 주어진 문제가 선형계획문제.
선형계획법은 선형계획문제를 해결하는 방법.
선형계획법에는 기하학적 방법과 대수적인 방법인 단체법(simplex method)이 있음.


Up: 최적화이론/최적화문제/최적화,optimization, OR,
}

1.1. 기하학적 방법

1.2. 대수적 방법 - 단체법 simplex method

심플렉스법

2. 볼록최적화 convex optimization


한국어 공개 책
"모두를 위한 컨벡스 최적화 (Convex Optimization For All)"
https://wikidocs.net/book/1896
convex_set, convex_function, 옌센_부등식,Jensen_inequality 앞부분에서 설명하고 시작함.
이후 다양한 주제 간략히 설명 e.g. 볼록최적화,convex_optimization 기울기하강,gradient_descent conditional_gradient coordinate_descent knapsack
Related: 기계학습,machine_learning 심층학습,deep_learning





QQQ 그럼 오목최적화라는 것도 있음? or 있을 수가 없음?

3. 조합최적화 combinatorial optimization

조합최적화,combinatorial_optimization

ex.
WpEn:Assignment_problem
배낭문제,knapsack_problem WpEn:Knapsack_problem
minimum_spanning_tree WpEn:Minimum_spanning_tree


4. Bellman's Principle of Optimality

The principle of optimality
The sub-solutions of an optimal solution of a problem are optimal solution of its sub-solutions.
최적화의 원리 (principle of optimality): 원래 문제의 최적해의 부분해가 하위 문제의 최적해

6. 관련

오목볼록,concave_and_convex, 최대최소. 이 두가지(네가지) 개념은 현재 goto 미적분,calculus 맨 밑에 있는데 독립 예정.

변분법,variational_calculus - 최적화 방법 중 하나.

7. Ivan Savov p379

변수,variable $x$ 에 대해 최적화하기 원하는 함수,function$f(x)$ 로 나타냈을 때,
  • $f$ 는 미분가능해야 한다.
  • $[x_i,x_f]$ : 제한 조건 constraint. $(x_i\le x\le x_f)$ (see 범위,range)
  • 최대점 global maximum
  • 극대점 local maximum
  • 최소점 global minimum
  • 극소점 local minimum
  • 극점 extremum : 함수 그래프의 극대점(꼭대기)과 극소점(골짜기 바닥) 모두를 나타내는 일반적 용어 (see 극값,extremum)
  • 안장점,saddle_point : 극대나 극소 어느 것도 아닌 점이지만 $f'(x)=0$ 인 위치. 예를 들어, 함수 $f(x)=x^3$$x=0$ 에서 안장점을 갖는다.
어떤 함수 $f(x)$$x^{\ast}$ 에서 최대값을 갖고, 그 최대값이 $f(x^{\ast})=M$ 이라고 가정하면 다음 표기가 적용된다.
  • $\operatorname{max}_x f(x)=M$ : 최대값
  • $\operatorname{argmax}_x f(x)=x^{\ast}$ : argmax연산자는 최대값이 발생하는 위치(함수의 독립변수)를 알려준다.

8. Programming의 최적화 / Compiler의 최적화

// 컴파일러최적화 compiler_optimization 코드최적화 code_optimization ..
컴파일러,compiler가 자동으로 하기도 하고 프로그래머가 manual로 하기도 함.

... 인터프리터,interpreter도 분명 code 최적화를 할 수 있으므로, 코드최적화,code_optimization가 더 범용 단어이므로 분류시 주의 ...
대상은 executable_code

프로그램의
  • 성능 향상 (실행 속도 향상)
  • 코드의 크기 감소, 사용 자원의 감소
등을 보통 목적으로 하는 듯, chk. 이건 각각 복잡도,complexity
  • time complexity
  • space complexity
와 유사성이 보이는데.



peephole_optimization
{
p PeepholeOptimization
https://everything2.com/title/Peephole optimization
}


Twins:
p TheOptimization
p CompilerCodeOptimization
http://foldoc.org/optimising compiler

rel.
컴파일러,compiler
compilation
코드,code esp executable_code

9. SQL의 optimizer

10. tmp bmks ko

11. Links ko

최적화 기법의 직관적 이해 (2015)
https://darkpgmr.tistory.com/149

함수최적화 기법 정리 (Levenberg–Marquardt 방법 등)
https://darkpgmr.tistory.com/142

딥러닝 최적화 알고리즘 알고 쓰자. 딥러닝 옵티마이저(optimizer) 총정리 (2019)
https://hiddenbeginner.github.io/deeplearning/2019/09/22/optimization_algorithms_in_deep_learning.html

http://www.aistudy.com/math/optimization.htm
"제약조건(constraints) 이 있을 수도 있는 상황에서 함수의 최대치와 최소치 (maxima and minima) 를 찾는 것과 관련"

최적화와 기계학습 (2019)
https://horizon.kias.re.kr/9286/