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

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

일단 [[https://terms.naver.com/entry.naver?docId=3405174&cid=47324&categoryId=47324 수학백과 선형계획법]] 앞부분 참조

대체적으로 어떤 '제약, 제약조건 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
  https://mathworld.wolfram.com/GlobalOptimization.html (long)
 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]].

<<tableofcontents>>

= 선형계획법 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)이 있음.

Twins:
http://foldoc.org/linear+programming
[[https://terms.naver.com/entry.naver?docId=3405174&cid=47324&categoryId=47324 수학백과: 선형계획법]]
[[https://terms.naver.com/entry.naver?docId=779144&cid=42085&categoryId=42085 경제학사전: 선형계획]]

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

== 기하학적 방법 ==
== 대수적 방법 - 단체법 simplex method ==
심플렉스법

= 볼록최적화 convex optimization =
[[볼록최적화,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]]

free books en
Stephen P. Boyd - Stanford EE 교수
https://web.stanford.edu/~boyd/books.html
https://web.stanford.edu/~boyd/cvxbook/
https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

Twins:
[[WpEn:Convex_optimization]]
https://developers.google.com/machine-learning/glossary?hl=ko#convex-optimization

mentioned in [[비선형계획법,nonlinear_programming]] curr at [[선형성,linearity]]

Up: [[오목볼록,concave_and_convex]], esp. [[볼록,convex]] or convexity, curr at [[미적분,calculus#s-9]] [[최적화,optimization]]

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

= 조합최적화 combinatorial optimization =
조합최적화,combinatorial_optimization

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

[[WpKo:조합_최적화]]
[[WpEn:Combinatorial_optimization]]

= Bellman's Principle of Optimality =
## from 석준희 데이터학습지능
The principle of optimality
The sub-solutions of an optimal solution of a problem are optimal solution of its sub-solutions.
최적화의 원리 (principle of optimality): 원래 문제의 최적해의 부분해가 하위 문제의 최적해

= 방법 =
[[뉴턴_방법,Newton_method]]
[[라그랑주_곱셈자,Lagrange_multiplier]]
[[기울기하강,gradient_descent]]
[[SA,simulated_annealing]] - writing

[[WpEn:Category:Optimization_algorithms_and_methods]]

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

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

= 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연산자는 최대값이 발생하는 위치(함수의 독립변수)를 알려준다.

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

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

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

ex.
[[WpEn:Bounds-checking_elimination]] - rel. [[,bounds_checking]]
constant_folding - http://foldoc.org/constant+folding

[[Wiki:PrematureOptimization]]

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

profile-guided optimization (PGO) //// del ok
LLVM https://clang.llvm.org/docs/UsersManual.html#profile-guided-optimization
Rust https://doc.rust-lang.org/rustc/profile-guided-optimization.html

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

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

= SQL의 optimizer =
[[optimizer]]
{

... Google:SQL+Optimizer
}

= tmp bmks ko =
[[Namu:최적화#s-3]]

= 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/

Twins:
[[https://terms.naver.com/entry.naver?docId=4125461&cid=60207&categoryId=60207 수학백과: 최적화 문제]]
[[WpKo:수학적_최적화]]
[[WpEn:Mathematical_optimization]]
[[WpEn:Optimization_problem]] - [[문제,problem]]
https://mathworld.wolfram.com/Optimization.html - 현재 본문 없고 see also 6항목
https://mathworld.wolfram.com/topics/Optimization.html
https://everything2.com/title/optimization
https://artofproblemsolving.com/wiki/index.php/Optimization ([[Date(2022-02-09T05:53:52)]] 현재 basic)
[[https://en.citizendium.org/wiki/Optimization_(mathematics)]]
http://www.aistudy.com/math/optimization.htm

Up: [[최적성,optimality]]?, [[운용과학,operations_research]], [[applied_mathematics]],