순서형 최적화

수학적 최적화에서 순서형 최적화는 부분 순서의 집합("포셋")^[1][2][3][4]에서 값을 취하는 함수의 최대화다.순서형 최적화는 대기열 네트워크 이론에 응용이 있다.

수학적 기초

정의들

부분 순서는 반사성, 비대칭성, 전이성인 집합 P에 대한 이진 관계 "치수"로, 즉 P에 있는 모든 a, b, c에 대해 다음과 같은 것이 있다.

• a ≤ a (변수);
• if b 및 b ≤인 경우, a = b(대칭);
• 만약 ≤ b와 b ≤ c가 있다면, ≤ c (투명성)이다.

즉 부분 순서는 비대칭 사전 순서다.

부분 순서가 있는 세트를 부분 순서 집합(포셋이라고도 함)이라고 한다.다른 종류의 주문이 의미하는 것이 없는 것이 분명한 한, 주문 집합이라는 용어는 양자리에도 가끔 사용된다.특히, 완전히 순서가 정해진 세트는 "순서된 세트"라고도 할 수 있으며, 특히 이러한 구조물이 포셋보다 더 일반적인 영역에서는 더욱 그러하다.

구별 요소 a, 부분 순서가 정해진 집합 P의 b, 만약 if b 또는 b ≤ a, a와 비교 가능하다.그렇지 않으면 비할 데 없는 것이다.포셋의 각 두 요소가 비교 가능한 경우 포셋은 완전히 순서가 정해진 세트 또는 체인(예: 순서가 정해진 자연수)이라고 한다.두 원소 하나하나가 비할 데 없는 포셋을 안티케인이라고 한다.

예

수학에서 발생하는 양성의 표준 예는 다음과 같다.

• 표준에 의해 주문된 실수는 동등하지 않은 관계 ≤ (완전히 주문된 집합이기도 함)이다.
• 포함 순서에 따라 지정된 집합(전원 집합)의 하위 집합 집합 집합
• 포함에 의해 정렬된 벡터 공간의 하위 스페이스 세트.
• 부분 순서가 정해진 P의 경우, P의 모든 원소를 포함하는 시퀀스 공간, 여기서 시퀀스 a는 의 모든 항목이 b의 해당 항목보다 앞에 있으면 시퀀스 b보다 선행한다.공식적으로 (a_n)_{n∈${\displaystyle \mathbb {N} }$} ≤ (b_n)_{n∈${\displaystyle \mathbb {N} }$} $N$의 모든 N에 대한_n ≤ b인_n 경우(b) ${\$ {$N}$ $\}.$
• 세트 X와 부분 순서가 지정된 세트 P의 경우, X에서 P까지의 모든 기능을 포함하는 함수 공간이며, 여기서 f g g는 X에서 모든 X에 대해 f(x) g g(x)인 경우에만 해당된다.
• 도달 가능성으로 정렬된 방향 아세클릭 그래프의 꼭지점 세트.
• 구분 가능성의 관계를 갖춘 자연수 집합.

아르테마

Poset P에는 "가장 위대하다"와 "최저"라는 몇 가지 개념이 있는데, 특히 다음과 같다.

• 최대 요소 및 최소 요소:모든 원소 a in P, ≤ g에 대해 원소 g는 가장 큰 원소다.모든 원소 a in P, ≥ m에 대해 원소 m은 최소 원소다.포셋은 하나의 최대 요소 또는 최소 요소만 가질 수 있다.
• 최대 요소 및 최소 요소:P에 원소 g는 a > g와 같은 원소 a가 없는 경우 최대 원소다. 마찬가지로 P에도 원소 m은 < m과 같은 원소 a가 없는 경우 최소 원소다.포셋이 가장 큰 원소를 가지고 있다면 그것은 고유한 최대 원소여야 하지만, 그렇지 않으면 두 개 이상의 최대 원소가 있을 수 있고, 마찬가지로 최소 원소와 최소 원소에 대해서도 유사하다.
• 상한 및 하한:P의 부분 집합 A의 경우, P의 요소 x는 각 요소 a의 in x인 경우 A의 상한이다.특히 x는 A의 상한이 되기 위해 A에 있을 필요는 없다.마찬가지로 P의 원소 x는 각 원소 a의 for x인 경우 A의 하한이다.P의 가장 큰 요소는 P 자체의 상한이며, 최소 요소는 P의 하한이다.

예를 들어, 1은 다른 모든 원소를 나누기 때문에 최소 원소지만, 이 집합은 최대 원소도 없고 최대 원소도 없다: g는 2g을 나누기 때문에 2g은 g보다 크며 g는 최대가 될 수 없다.대신 우리가 1보다 큰 자연수만 고려한다면, 결과의 poset은 최소 요소를 가지고 있지 않지만, 모든 prime 숫자는 최소 요소다.이 포셋에서 60은 {2,3,5}의 상한(최소 상한은 아님)이고 2는 {4,6,8,12}의 하한이다.

추가구조

그러한 많은 경우, 양전자에는 다음과 같은 추가 구조가 있다.예를 들어, 포셋은 격자 또는 부분 순서의 대수 구조일 수 있다.

선반

포셋(L, ≤)은 다음과 같은 두 개의 공리를 만족하면 격자( is子)이다.

이진 조인 존재

L의 임의의 두 요소 a와 b에 대해 {a, b} 집합에${\displaystyle }${$$b {\$displaystyle a\lor$b}(최소 상한 또는 우월함이라고도 함)의 조인이 있다.

이진 일치의 존재

L의 임의의 두 요소 a와 b에 대해 {a, b} 집합에 대해 ${\displaystyle \wedge }$ ${\displaystyle b}${\$displaystyle a\land$b}($$가장 큰 하한 또는 최소값이라고도 함)가 일치한다.

a와 b의 가입과 만남은 ${\displaystyle \mathrm{각각}}$ ${\displaystyle \vee }$ ${\displaystyle b}$$[\displaystyle a\lor b}$와 ${\displaystyle \wedge }$ b$[\displaystyle a\land b}$로 표시된다$.$이 정의는 $\vee {\displaystyle }$ ${\displaystyle \lor }$ 및$$ $\wedge {\displaystyle }$ ${\displaystyle \land }$ 이진$$ 연산을 만든다.첫 번째 공리는 L이 합류-세밀라티즈라고 말하고, 두 번째 공리는 L이 만남-세밀라티즈라고 말한다.두 작업 모두 순서와 관련하여 단조로움: ≤ a와₂ b ≤ b는₁₁₂₁ $\vee {\displaystyle }$ ${\displaystyle \lor$$}$b$$₁$$₂ ≤ ≤ a₂ { ${\$$displaystyle \land$$$}land ${\displaystyle }$ {\$displaystyle \land }$를₁₁₂₂ 의미한다.

이것은 격자의 모든 비어 있지 않은 유한 부분 집합에는 결합(최소)과 만남(최소)이 있다는 유도 논리로 이어진다.추가적인 가정으로 추가 결론이 가능할 수 있다. 이 주제에 대한 자세한 설명은 완전성(순서 이론)을 참조하십시오.

경계 격자는 최대(또는 최대) 및 최소(또는 최소) 요소를 가지며, 관례에 따라 1과 0(위 및 아래라고도 함)으로 표시된다.Any lattice can be converted into a bounded lattice by adding a greatest and least element, and every non-empty finite lattice is bounded, by taking the join (resp., meet) of all elements, denoted by ${\displaystyle \bigvee A=a_{1}\lor \cdots \lor a_{n}}$ (resp.${\displaystyle \bigwedge }$ ${\displaystyle A}$= ${\displaystyle {1\mathrm{}}_{}}$ ∧ ${\displaystyle \wedge }$ ${\displaystyle a_{}}$ n {\$displaystyle \bigwedge$ A$=a_{1}\land \cdots \land \land$a_$\{$$n$}}, $여기$서 A${\displaystyle }$=${\displaystyle {1\mathrm{}}_{}}$ ${\displaysty A=\{a_{1},\ldots,a_{n}.$

포셋은 모든 유한 요소 집합(빈 세트 포함)이 조인 및 일치를 갖는 경우에만 경계 격자다.여기서 빈 요소 집합의 조인은 최소 요소 element${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle \bigvee \varnothy=0}$으로 정의되며$,$ 빈 집합의 조인은 최대 요소 ${\displaystyle \bigwedge }$= ${\displaystyle 1}$ ${\displaystyle \bigwedge \varnothy=1}$로 정의된다$.$ 이 규칙은 만남과 결합성과 일치한다.유한 집합의 결합은 집합 결합의 결합과 같으며, 일반적으로 유한 집합의 결합은 집합 집합의 만남, 즉 포셋 L의 유한 하위 집합 A와 B의 충족과 같다.

$\displaystyle \bigvee \왼쪽(A\cup B\right)=\왼쪽(\bigvee A\right)\vee \왼쪽(\bigvee B\right)}$

그리고

$\displaystyle \bigwedge \left(A\cuppose B\right)=\왼쪽(\bigwedge A\right)\wedge \left(\bigwedge B\right)}$

잠깐, B를 빈 세트로 데려가는

$\displaystyle \bigvee \왼쪽(A\cup \emptyset \right)=\왼쪽(\bigvee \bigve \empt \right)=\ve 0=\bigvee A}$

그리고

$\displaystyle \bigwedge \bigwedge \bigwedge \bigwedge \bigwedge \bigwedge \bigwedge \right)\bigwedge 1=\bigwedge A}$

$A{\displaystyle }$ ${\displaystyle \cup \mathrm{\varnothing }}$ = ${\displaystyle A}$ ${\displaystyle A\cup \emptyset =A}$라는 사실과 일치한다$.$

순서 대수구조

포셋은 부분적으로 순서가 정해진 대수적 구조일 수 있다.^{[5][6][1][7][8][9][10]}

In algebra, an ordered semigroup is a semigroup (S,•) together with a partial order ≤ that is compatible with the semigroup operation, meaning that x ≤ y implies z•x ≤ z•y and x•z ≤ y•z for all x, y, z in S. If S is a group and it is ordered as a semigroup, one obtains the notion of ordered group, and similarly if S is a monoid it may be called ord에레드가 있는 단면체의부분적으로 순서가 정해진 벡터 공간과 벡터 래티스는 다중 목표를 가진 최적화에 중요하다.^[11]

컴퓨터 과학 및 통계 분야의 순서형 최적화

순서형 최적화의 문제는 많은 분야에서 발생한다.컴퓨터 과학자들은 선택 알고리즘을 연구하는데, 이는 분류 알고리즘보다 간단하다.^[12][13]

통계적 의사결정 이론은 "최상의" 하위 모집단을 식별하거나 "최상의" 하위 모집단을 식별해야 하는 "선택 문제"를 연구한다.^{[14][15][16][17][18]}

적용들

1960년대 이후, 순서형 최적화의 분야는 이론과 응용 분야에서 확대되었다.특히 항이마트로이드와 "max-plus 대수"는 네트워크 분석과 대기열 이론, 특히 대기열 네트워크와 이산 이벤트 시스템에서 응용 분야를 찾아냈다.^[19][20][21]

참고 항목

• 확률적 최적화
• 계산 복잡성 이론
• 휴리스틱스
• 측정 수준("순서 데이터")

참조

추가 읽기

• 후지시게, 사토루 서브모듈라 함수와 최적화.제2판.이산수학연보, 58.2005년 암스테르담 B.V. xiv+395 pp.ISBN 0-444-52086-4
• 곤드란, 미셸; 미누스, 미셸 그래프, 다이오이드, 세미링. 새로운 모델 및 알고리즘.운영 연구/컴퓨터 과학 인터페이스 시리즈, 41. 스프링거, 2008.xx+383 페이지ISBN 978-0-387-75449-9
• 디트리히, B. L.; 호프만, A. J. 탐욕스러운 알고리즘에 대해, 부분적인 순서 집합과 서브모듈라 함수를 명령했다.IBM J. Res. 47조 (2003년), 1호, 25-30호.
• 무로타, 카즈오 이산 볼록 분석.이산수학과 응용에 관한 SIAM 모노그래프공업 및 응용 수학 협회(SIAM), 필라델피아, PA, 2003.xxii+389 페이지ISBN 0-89871-540-7
• 탑키스, 도널드 M초변형성과 상호보완성.경제연구의 프런티어.프린스턴 대학 출판부, 프린스턴, NJ, 1998.시이+272 페이지ISBN 0-691-03244-0
• 가수, 이반 추상 볼록스 분석.모노그래프와 고급 텍스트의 캐나다 수학 협회 시리즈.와일리-인터사이언스 출판물.존 와일리 & 선즈 주식회사, 1997년 뉴욕.xxii+491 페이지ISBN 0-471-16015-6
• 비외르네르, 안데르스, 지글러, 귄터 M.탐욕스러운 존재에 대한 소개.Matroid 응용 프로그램, 284–357, 수학 백과사전.앱, 40, 캠브리지 유니브1992년, 캠브리지, 프레스, 캠브리지,
• Zimmermann, U. 순서 대수 구조에서 선형 및 결합 최적화.앤. 이산수학. 10 (1981), 8+380 pp.
• 쿠닝하임 그린, 레이몬드 미니맥스 대수학경제학 및 수학 시스템 강의 노트, 166. 스프링거-베를라크, 1979년 베를린-뉴욕.xi+258 페이지ISBN 3-540-09113-0
• Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre (1992). Synchronization and linearity: An algebra for discrete event systems. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: John Wiley & Sons, Ltd. pp. xx+489. ISBN 0-471-93609-X. MR 1204266.
• Glasserman, Paul; Yao, David D. (1994). Monotone structure in discrete-event systems. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. New York: John Wiley & Sons, Inc. pp. xiv+297. ISBN 0-471-58041-4. MR 1266839.
• Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob (2006). Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. pp. xii+213. ISBN 978-0-691-11763-8. MR 2188299.
• Ho, Y.C, Srenivas, R, Vakili, P. "이연성 이벤트 동적 시스템의 순서 최적화", DEDS 2(2), 61-88, (1992)의 J.
• 알렌, 에릭, 그리고 마리자 D. 일리치. 전기 시장의 가격 기반 약속 결정.산업 통제력의 발전.런던: 스프링거, 1999.ISBN 978-1-85233-069-9

외부 링크

• Yu-Chi Ho에 의한 서수적 최적화에 관한 주석 서적