Quiz-7 (2026.03.30) // 범위: ~03wk

1. 알고리즘

강의노트에 소개된 아래의 두 알고리즘을 비교하자.

Important

- 차원이 높아져서 당환스럽지만, 아래의 방식으로 알고리즘을 설계하면 최소값을 잘 찾을 것 같다.

1. 아무값이나 \(x_{sol},y_{sol}\)이라 주장한다.
2. 1에서 선택한 \((x_{sol},y_{sol})\)근처의 값을 조사한다. 즉 아래의 값들을 조사한다.그리고 가장 \(f(x,y)\)를 작게만드는 값으로 update를 함.
   • \((x_{sol},y_{sol}-0.1)\)
   • \((x_{sol}-0.1,y_{sol}-0.1)\)
   • \((x_{sol}+0.1,y_{sol}-0.1)\)
   • \((x_{sol},y_{sol})\)
   • \((x_{sol}-0.1,y_{sol})\)
   • \((x_{sol}+0.1,y_{sol})\)
   • \((x_{sol},y_{sol}+0.1)\)
   • \((x_{sol}-0.1,y_{sol}+0.1)\)
   • \((x_{sol}+0.1,y_{sol}+0.1)\)
3. 2에서 업데이트된 \((x_{sol}',y_{sol}')\)을 다시 1의 \((x_{sol},y_{sol})\)로 해석하고 1-2를 반복한다.

- 위의 방식과 다르지만 아래의 방식도 가능할 것 같다.

1. 아무값이나 \(x_{sol},y_{sol}\)이라 주장한다.
2. 1에서 선택한 \((x_{sol},y_{sol})\)에 대하여 다음을 수행한다.
   • \(f(x_{sol}-0.1, y_{sol}), f(x_{sol},y_{sol}), f(x_{sol}+0.1,y_{sol})\)를 비교하여 \(x\)의 이동방향을 결정한다.
   • \(f(x_{sol}, y_{sol}-0.1), f(x_{sol},y_{sol}), f(x_{sol},y_{sol}+0.1)\)를 비교하여 \(y\)의 이동방향을 결정한다.
   • 결정된 방향으로 동시에 이동하여 \(x_{sol},y_{sol}\)을 update한다.
3. 2에서 업데이트된 \((x_{sol}',y_{sol}')\)을 다시 1의 \((x_{sol},y_{sol})\)로 해석하고 1-2를 반복한다.

(1) 두 알고리즘이 다른 결과를 주는 경우를 찾아라.

Note풀이 보기

함수 정의: 생략 (굳이 수식을 쓸필요 없이 아래와 같은 값을 가지는 함수를 상상하기만해도 충분)

시작점: \((x_{sol}, y_{sol}) = (0, 0)\)

\(y \backslash x\)	\(-0.1\)	\(0\)	\(0.1\)
\(0.1\)	-100	0	0
\(0\)	0	0	0
\(-0.1\)	0	0	0

알고리즘 1에 의한 업데이트 알고리즘 2에 의한 업데이트

(2) \(f(x,y)\)가 아래로 볼록한 모양이면 (즉 \(f(x,y)\)가 convex function 이면) 두 알고리즘은 항상 같은 결과를 주는가? 같은결과를 준다고 생각하면 이유를 쓰고, 다른 결과를 준다고 생각하면 그 예를 구체적으로 잡아라 (즉 \(f(x,y)\)의 수식자체를 구체적으로 잡을 것)

Note풀이 보기

함수 정의: \(f(x, y) = 10(x + y)^2 + (x - y)^2\) (convex function)

Tip

아래로 볼록한 함수인지는 3주차 강의노트의 plot_surface_3d 로 확인하시면 됩니다.

시작점: \((x_{sol}, y_{sol}) = (0.1, -0.1)\)

\(y \backslash x\)	\(0.0\)	\(0.1\)	\(0.2\)
\(0.0\)	0.00	0.11	0.44
\(-0.1\)	0.11	0.04	0.19
\(-0.2\)	0.44	0.19	0.16

알고리즘 1에 의한 업데이트 알고리즘 2에 의한 업데이트