스탠퍼드 AA203 2강 최적화 이론 정리: 최적성 필요조건부터 라그랑주 승수까지

핵심 메시지

• 최적성 필요조건은 후보를 걸러내는 필터다. 국소 최솟값이라면 기울기가 0이어야 하지만, 기울기가 0이라고 해서 국소 최솟값이 보장되지는 않는다.
• 2차 근사까지 쓰면 조건이 강해진다. 국소 최솟값에서는 헤세 행렬이 양의 준정부호여야 하고, 반대로 기울기가 0이면서 헤세 행렬이 양의 정부호이면 그 점은 국소 최솟값이라는 충분조건이 된다.
• 볼록 함수에서는 국소 최솟값이 곧 전역 최솟값이고, 미분 가능하다면 기울기가 0이라는 아주 국소적인 검사만으로 전역 최적성을 판정할 수 있다.
• 경사법은 하강 방향과 보폭이라는 두 선택으로 갈린다. 방향은 기울기에 양의 정부호 행렬을 곱해 만들며, 항등 행렬을 쓰면 최급강하법, 헤세 행렬의 역행렬을 쓰면 곡률까지 반영하는 방향이 된다.
• 등식 제약이 붙으면 기울기가 0이라는 조건이 라그랑주 승수 정리로 확장된다. 목적 함수의 기울기가 제약 함수 기울기들의 선형 결합과 같아야 하며, 기하학적으로는 두 등고선이 접한다는 뜻이다.

쉽게 이해하기

이 강의는 최적화 자체를 가르치는 수업이 아니라 최적·학습 기반 제어를 다루는 수업의 2강이다. 강의자는 고전적인 비선형 최적화에서 얻은 통찰이 최적제어로 거의 그대로 옮겨 가기 때문에 먼저 짚고 간다고 밝힌다. 출발점은 국소 최솟값의 정의다. 어떤 점이 국소 최솟값이라면 그 점을 아주 조금 흔들었을 때 함수 값이 커져야 한다는 사실에서, 1차 테일러 근사를 이용해 각 편미분이 0보다 크거나 같으면서 동시에 작거나 같아야 한다는 결론이 나오고, 그 결과 모든 편미분이 0, 즉 기울기가 0이라는 유명한 필요조건이 유도된다.

다만 이 조건에는 두 가지 단서가 붙는다. 첫째, 기울기가 0인 점은 국소 최댓값일 수도 있으므로 필요조건일 뿐 충분조건이 아니다. 둘째, 이 조건은 정의역의 열린 집합 안쪽에서만 성립한다. 구간의 끝점처럼 경계에 놓인 최솟값은 기울기가 0이 아닐 수 있기 때문이다. 조건을 강화하려면 2차 근사가 필요하다. 기울기가 0인 상황에서 남는 2차 항이 항상 0 이상이어야 하므로 헤세 행렬은 양의 준정부호가 되고, 이를 양의 정부호로 한 단계 더 올리면 그 점 주변에서 함수가 곧바로 커지므로 충분조건이 된다.

볼록성은 이 강의가 특별히 강조하는 성질이다. 두 점을 잇는 선분이 집합 안에 남으면 볼록 집합이고, 그래프 위 두 점을 잇는 선분이 함수 그래프보다 위에 놓이면 볼록 함수다. 볼록 함수에서는 국소 최솟값이 전역 최솟값이 되고, 엄격하게 볼록하면 전역 최솟값이 많아야 하나이며, 미분 가능하면 기울기가 0이라는 조건이 전역 최적성의 필요충분조건이 된다. 강의자는 뒤에서 다룰 궤적 최적화가 문제를 볼록 문제로 근사해 풀고 그 해에서 다시 볼록화해 반복하는 전략을 쓰며, 이것이 로봇 시스템 궤적 최적화에서 가장 널리 쓰이는 방법 중 하나라고 예고한다.

실제 계산으로 넘어가면 기울기가 0인 점을 모두 찾는 일이 버거워지므로 반복법을 쓴다. 초기 추정에서 시작해 매 단계 함수 값이 줄어들도록 갱신하는 방식인데, 갱신 규칙은 현재 점에 보폭과 방향을 곱해 더하는 형태이고 기울기와 방향의 내적이 음수이기만 하면 하강이 보장된다. 방향은 기울기에 양의 정부호 행렬을 곱해 만드는데, 항등 행렬이면 기울기 반대 방향으로 가는 단순한 선택이고 헤세 행렬의 역행렬이면 곡률 정보를 반영해 더 좋은 방향이 되지만 2차 미분 행렬을 계산해야 해 매 반복 비용이 크게 오른다. 강의자는 정교함과 비용 사이의 이런 맞바꿈이 수업 내내 반복될 주제라고 말한다.

보폭 선택도 만만치 않다. 함수 값을 가장 많이 줄이는 보폭을 매번 찾는 최소화 규칙은 합리적이지만 그 자체가 또 하나의 최소화 문제이고, 반대로 0.1처럼 고정값을 쓰는 가장 게으른 방법은 값이 크면 발산할 수 있다. 1차 근사는 현재 점 근처에서만 유효하므로 보폭이 커지면 근사가 알려 주는 정보 자체가 무의미해진다는 것이 핵심이다. 강의는 이어 수렴 보장과 종료 규칙, 수렴 속도라는 세 가지 남은 주제를 언급하고, 좌표 하강법이나 넬더-미드처럼 미분을 쓰지 않는 방법군도 있다고 짚은 뒤 등식 제약 문제로 넘어간다.

등식 제약 문제의 기본 결과는 라그랑주 승수 정리다. 제약이 m개면 승수도 m개가 존재해, 목적 함수의 기울기에 제약 함수 기울기들을 승수로 가중해 더한 값이 0이 된다는 내용이다. 제약이 없으면 그대로 기울기가 0인 조건으로 돌아온다. 강의자는 x1과 x2의 합을 최소화하되 두 변수의 제곱합이 2라는 제약을 두는 예제로 승수를 풀어 두 후보 (-1, -1)과 (1, 1)을 얻고, 함수 값이 더 작은 쪽이 최솟값임을 보인다. 기하학적으로 이 정리는 목적 함수의 기울기가 제약 함수 기울기가 만드는 공간에 놓인다는 뜻이고, 기울기는 등고선에 수직이므로 결국 두 곡선이 접하는 지점이 해가 된다. 정리가 성립하려면 제약 기울기들이 선형 독립이어야 한다는 정칙성 조건이 필요하며, 다음 시간에는 부등식 제약과 KKT 조건으로 이어진다고 예고한다.

주요 인사이트

• 필요조건과 충분조건의 구분이 실무적 의미를 갖는다. 필요조건은 후보를 걸러내는 필터일 뿐이라 통과했다고 최적이 되지 않지만, 통과하지 못하면 최적일 가능성이 아예 없어 탐색 범위를 크게 줄여 준다.
• 열린 집합이라는 단서는 사소해 보여도 결과를 바꾼다. 정의역의 경계에 놓인 점은 국소 최솟값이면서도 미분이 0이 아닐 수 있어, 기울기가 0인 점만 찾는 절차가 해를 놓칠 수 있다.
• 볼록성이 귀한 이유는 국소적인 검사 하나로 전역적인 결론을 얻기 때문이다. 기울기 계산은 한 점 주변만 들여다보는 일인데, 볼록 함수에서는 그 검사가 함수 전체에 대한 판정이 된다.
• 곡률 정보를 쓰는 방향은 반복 횟수를 줄여 주지만 매 반복이 비싸진다. 문제 규모에 따라 이 맞바꿈의 손익이 갈리므로 항상 더 정교한 알고리즘이 답은 아니다.
• 라그랑주 승수는 목적 자체가 아니라 방정식을 풀기 위한 수단으로 도입된다. 강의에서는 승수와 제약식을 합치면 미지수와 방정식의 개수가 맞아떨어져 풀 수 있다는 점이 핵심으로 제시된다.

자주 묻는 질문

관련 AI 소식