728x90
반응형
라그랑주 역학
1788 *라그랑지언 값으로 물체의 운동을 설명
-
라그랑지언 : 운동 에너지 - 위치 에너지 = 스칼라 값
-
스칼라 값: 질량 또는 온도와 같이 벡터와 달리 방향을 가지고 있지 않고 크기만 가지고 있는 물리량
-
벡터 : 스칼라 + 방향
=> 크기와 방향을 둘다 고료하는 벡터는 공간을 기술하는 데 3개의 성분이 필요, 스칼라는 하나만 필요 (계산 단순화)
라그랑지안 방법 : 제약조건을 쉽게 다루기 위한 기법
- 라그랑주 승수 도입: 원래 문제의 제약 조건에 각각 라그랑주 승수(λ)를 할당합니다. 이 승수는 각 제약 조건의 '가중치'나 '가격'으로 해석할 수 있습니다.
- 라그랑주 함수 구성: 원래 목적 함수에 제약 조건과 라그랑주 승수의 곱을 더하여 라그랑주 함수를 구성합니다. 이 함수는 원래 문제의 목적 함수와 제약 조건을 포함합니다.
- 문제의 완화: 라그랑주 함수를 최대화하거나 최소화하는 문제로 변환합니다. 이 과정에서 일부 제약 조건이 완화되어 원래 문제보다 풀기 쉬운 문제가 됩니다.
- 최적화: 라그랑주 함수를 최적화하여 해를 찾습니다. 이 과정은 대개 반복적인 계산을 통해 이루어집니다.
- 원래 문제로의 근사: 라그랑주 완화법을 통해 얻은 해는 원래 문제의 근사 해로 사용됩니다. 필요한 경우, 추가적인 휴리스틱이나 정교화 과정을 통해 더 나은 해를 얻을 수 있습니다.
라그랑주 완화법은 특히 복잡한 정수 프로그래밍 문제나 네트워크 흐름 문제 같은 분야에서 유용하게 사용됩니다. 이 방법을 사용하면 계산 복잡도가 높은 문제를 좀 더 효율적으로 다룰 수 있습니다.
이산 최적화 문제에 사용되는 라그랑지 승수는 미분이 불가능하다는 성질이 있어서 연속 공간의 최적화 문제에 비해 많은 제한이 있게 된다.
-> 극복: 서브그래디언트(subgradient) 알고리즘
분지 한계법을 위한 상한(upper bound)을 생성하기 위해 사용
[최적화 활용] DNN 제약조건에 포함되는 비선형 함수 처리
ReLU를 활성함수로 가지는 DNN의 노드는
-
SMT(Satisfiability Modulo Theoreis) 기반 기술로 논리적인 추론을 이용 하여 제약조건 문제를 해결
2. 정수 제약조건을 함께 사용하여 혼합 정수 선형 계획법 (Mixed Integer Linear Programming)으로 해결
시그모이드와 같은 활성함수를 포함하는 DNN의 경우, 라그랑주 완화법(Lagrangian Relaxation) 을 활용하여 근사적으로 문제를 해결
[오류] 적대적 예제(Adversarial Example) : 미세한 차이를 가지는 두 입력에 대하여 DNN이 완전히 다른 결과를 보이는 문제
Lagrangian relaxations
728x90
'08.Algorithm' 카테고리의 다른 글
| 프로그래밍 언어 - V 프로그래밍 (0) | 2023.12.13 |
|---|---|
| 자바 스크립트 - 현대 자바스크립트 프레임워크 (1) | 2023.12.05 |
| 정렬 알고리즘 - 시간복잡도 (Time Complexity), 공간복잡도 (Space Complexity) (0) | 2023.10.16 |
| 정렬 알고리즘 (0) | 2023.10.12 |
| 자료구조 (Data Structure) (0) | 2023.10.11 |
