좌표 하강법을 직접 구현하여 확인하기: 변수를 하나씩 움직이는 최적화가 느려지거나 멈추는 상황

서론

『분석가를 위한 수리 최적화 입문』(이토 모토하루・하라다 코헤이・마츠오카 유키, 소시무, 2026년)의 제4장은 '대규모 제약 조건 없는 최적화'를 다루는 장입니다. 내용이 많아 네 편으로 나누어 기사를 작성합니다. 이 글은 첫 번째 글로, 변수를 하나씩 움직이는 좌표 하강법을 다룹니다.

제3장에서 다룬 최단 강하법(Gradient Descent)이나 뉴턴 방법(Newton's Method)은 반복할 때마다 모든 변수를 동시에 움직였습니다. 그 때문에 매번 모든 변수에 대한 기울기(편미분을 나열한 벡터)를 계산합니다. 변수가 많은 문제에서는 이 계산이 무거워집니다.

좌표 하강법은 한 번의 반복에서 움직일 변수를 하나로 제한하는 방법입니다. 움직이는 변수가 하나라면, 풀 문제가 1변수의 최소화가 되며, 공식으로 답을 쓸 수 있는 경우도 많아집니다. scikit-learn의 Lasso나 ElasticNet 역시 이 방법을 사용해 계수를 구하고 있습니다.

본 기사에서는 좌표 하강법을 직접 구현하여 움직여보고 다음 질문에 답하는 것을 목표로 합니다.

• 좌표 하강법은 무엇을 어떻게 움직이는 방법인가. 기울기를 사용하는 방법과 무엇이 다른가?
• 변수들 간의 결속(상관관계)이 강하면 왜 느려지는가?
• 멈추는 조건을 '직전과의 차이'로 설정하면 왜 위험한가?
• 미분할 수 없는 함수에서는 왜 답이 아닌 점에서 멈추는가. Lasso는 왜 풀리는가?

수식은 고등학교 미분과 대학교 1학년 정도의 편미분을 사용합니다. 새로운 도구가 나올 때마다 짧은 예시로 설명하겠습니다.

이번에 만들 것

좌표 하강법 함수를 하나 만들어, 성질이 다른 두 가지 문제에 적용해 보겠습니다.

만들 파일은 다음 네 가지입니다.

이번에는 다음은 다루지 않습니다.

• 기울기를 사용하는 방법과의 계산 시간 비교. 좌표 하강법이 빠른지는 1변수 문제를 얼마나 저렴하게 풀 수 있는지에 따라 결정되며, 문제마다 다르기 때문입니다.
• 여러 변수를 한꺼번에 움직이는 블록 좌표 하강법 (K-means 법이 그 예시입니다).

표준화된 데이터에서는
| 값 | 표준화된 데이터로는 |
|​|
| 평균이 0이므로, 제곱의 평균은 분산 그 자체이며, 1이 된다 |
| 평균이 0이므로, 곱의 평균은 공분산 그 자체이다. 게다가 표준편차가 1이므로, 상관계수 그 자체가 된다. 이를 |

나머지 수치는 예시로 단순화하겠습니다. 마지막

1-4. 변수가 하나인 문제(1변수)를 손으로 풀어보기

1-3의 함수를 사용하여 좌표 하강법(Coordinate Descent)을 한 번 계산해 보겠습니다.

여기서,

2. Python으로 좌표 하강법 작성하기

2-1. 좌표 하강법 함수 만들기

"""좌표 하강법: 변수를 하나씩 선택하여, 그 변수만 움직여 목적함수를 최소화한다."""
import numpy as np
from scipy.optimize import minimize_scalar
...

가장 이해하기 어려운 부분은 다음 한 줄이라고 생각합니다.

t = minimize_scalar(lambda t: f(x + t * e)).x

이것은, 1-1의 식에서 현재 점 x로부터 i번째 변수만 t만큼 움직일 때, f가 가장 작아지는 t를 찾는 것입니다. 1-4와 같은 예시(

x

e

| 부분 | 의미 | 예시에서는 |
|---|---|
| x + t * e | i번째 변수만 t만큼 움직인 점 |
| lambda t: f(x + t * e) | t를 인수로 받아, 그 점에서 f의 값을 반환하는 함수. x와 e는 고정되어 있으므로, t만의 1변수 함수가 된다. |
| t가 1이라면 |
| minimize_scalar(...) | 전달된 1변수 함수가 최소가 되는 t를 수치 계산으로 찾는다. |
| 결과 등을 모아둔 OptimizeResult라는 객체를 반환한다. |
| .x | 결과 중, 찾아낸 t 값을 추출한다. |

약 1.5

lambda는 이름을 붙이지 않고 그 자리에서 만드는 작은 함수입니다. 다음과 같이 작성해도 같은 의미가 됩니다.

def g(t):
    return f(x + t * e) # x와 e는 고정되어 있고, t만 변할 수 있다
t = minimize_scalar(g).x

t를 몇 개 넣어보면,

minimize_scalar는 범위를 지정하지 않을 경우, Brent법이라는 방법으로 최소점을 찾습니다. 미분식을 전달할 필요가 없습니다. 1-4처럼, 2차 함수라면 1변수 문제를 식으로 풀 수 있지만, 여기서는 일부러 minimize_scalar에 맡겼습니다. 그렇게 하면, 식으로 풀기 어려운 문제(제4장)에도 같은 함수를 그대로 사용할 수 있습니다.

멈추는 조건인 lookback은 제3장에서 설명하겠습니다.

2-2. 변수 간의 결속력이 강하면 느려진다

1-3의 2차 함수를 사용하여,

"""변수의 2차 함수를 좌표 하강법으로 최소화하며, 변수 간의 결속력 rho에 따라 속도가 달라지는지 확인한다."""
from pathlib import Path
import matplotlib
...

uv run python quadratic.py

rho = 0.0 : 반복 4회, x = (1.0000, 1.0000), 답 = 1.0000
rho = 0.5 : 반복 21회, x = (0.6667, 0.6667), 답 = 0.6667
rho = 0.9 : 반복 105회, x = (0.5263, 0.5264), 답 = 0.5263
...

3. 종료 조건을 'n회 전'과 비교하기

3-1. 1회 전과 비교할 경우, 변수가 움직이지 않을 때 멈춘다

반복을 통해 해를 구하는 방법에서는 '목적 함수가 거의 감소하지 않으면 멈추는 것'이 자연스럽게 느껴집니다. 식으로 표현하면, 1회 전의 값과 비교하여

하지만 좌표 하강법(Coordinate Descent)에서는 특정 변수가 더 이상 움직일 수 없더라도 다른 변수를 움직이면 여전히 값이 감소하는 경우가 있습니다. 1-3의 이차 함수(

"""종료 조건을 '1회 전과의 차이'로 설정하면, 답에서 먼 지점에서 멈추는 것을 확인한다"""
from coordinate_descent import coordinate_descent
rho = 0.9
...

uv run python stopping.py

1회 전과 비교: 반복 1회, x = (-1.7000, 3.0000), f = 0.0550
2회 전과 비교: 반복 105회, x = (0.5263, 0.5264), f = -0.5263
답 : x = (0.5263, 0.5263), f = -0.5263

1회 전과 비교했을 때는 반복 1회 만에 멈췄습니다. 멈춘 지점의

3-2. 모든 변수를 한 번씩 움직여서 판정하기

변수가

'모든 변수를 한 번씩 움직여도 거의 감소하지 않았을 때'만 멈추기 때문에, 단지 하나의 변수만 움직이지 않았다고 해서 멈추지는 않습니다. 이번 예시에서는 coordinate_descent의 lookback의 기본값을 변수의 개수 n으로 설정한 것이 바로 이 때문입니다.

4. 미분할 수 없는 함수에서는 답이 아닌 지점에서 멈춘다

4-1. 오차의 절대값 합으로 회귀하기

웹 서버의 가상 모니터링 데이터(30분 분)를 사용하여, 1분당 요청 수를
오차 제곱합을 최소화하면, 큰 오차가 제곱되어 더욱 크게 계산되기 때문에 직선이 이상치에 끌립니다. 따라서, 오차의 절대값 합을 최소화합니다.

절대값

4-2. 좌표 하강법으로 풀고, 정확한 답과 비교하기

답안 확인에는 scikit-learn의 QuantileRegressor를 사용합니다. 예측하고 싶은 값의 분위점(중앙값 등)을 예측하는 회귀 모델로, quantile=0.5 (중앙값)로 설정하면 오차의 절대값 합을 최소화하는 문제와 동일한 답이 됩니다. 여기서는 문제를 선형 최적화(제6장에서 다룰 문제 유형)로 다시 작성하여 SciPy의 linprog로 풀고 있습니다.

"""오차의 절대값 합을 최소화하는 회귀에서는, 좌표 하강법이 답이 아닌 지점에서 멈추는 것을 확인한다"""
import numpy as np
from sklearn.linear_model import QuantileRegressor
...

uv run python lad_stuck.py

좌표 하강법 : a = 0.0967, b = 49.38, 절대값의 합 = 627.10 (158회)
QuantileRegressor: a = 0.0874, b = 54.91, 절대값의 합 = 620.04
참고(제곱합) : a = 0.1158, b = 53.25
...

결과를 순서대로 보면.

좌표 하강법은 답에 도달하지 못했다: 절대값의 합이 627.10에서 멈추었고, QuantileRegressor

여전히 620.04보다 큽니다. 기울기도 0.0967로, 정답인 0.0874와 차이가 납니다.
절댓값을 사용한 이유가 확인되었습니다: 제곱합을 최소로 만든 직선의 기울기는 0.1158로, 데이터 생성 시의 0.08에서 크게 벗어났습니다. 이는 이상치(outlier)에 의해 끌려갔기 때문입니다. 절댓값의 합을 최소로 한 정답(0.0874)은 0.08과 가까운 값입니다.
세로와 가로 모두 줄지 않지만, 대각선으로는 줄어듭니다: 멈춘 지점에서 a만 움직이거나 b만 움직이면 어느 방향으로든 절댓값의 합이 증가했습니다. 하지만 a와 b를 동시에 정답 방향으로 움직이자 감소했습니다.
우연이 아닙니다: 데이터를 다시 만들었을 때, 8가지 경우 중 6가지에서 정답보다 큰 값에 멈췄습니다.

4-3. 멈춘 지점에서 무슨 일이 일어나고 있는가

멈춘 지점에서는 오차가 거의 0인 데이터가 2건 있었습니다. 이는 직선이 정확히 두 개의 데이터 포인트를 통과하고 있다는 의미입니다.

막혔을 때 확인 항목

요약

이 글에서는 좌표 하강법을 직접 작성하여, 매끄러운 함수와 미분할 수 없는 함수에 적용해 보았습니다.

• 좌표 하강법은 변수를 하나씩 선택하여, 그 변수만 움직여 최소화하는 방법이며, 기울기(gradient)를 사용하지 않았습니다.
• 두 개의 설명변수로 만든 회귀의 이차 함수에서는, 설명변수 간 상관관계가 0일 경우 2회 만에 정답에 도달했지만, 0.9일 때는 105회, 0.99일 때는 850회가 걸렸습니다. 계곡이 비스듬하고 길쭉한 형태였기 때문에 세로와 가로의 작은 계단으로만 진행할 수 있었기 때문입니다 ($
  ho$). 종료 조건을 이전 값과의 차이로 설정했을 때, 움직이지 않는 변수를 선택한 첫 번째 회차에서 멈췄습니다. 변수 개수의 경우와 비교하여, 오차 절댓값 합을 최소화하는 회귀에서는 8가지 경우 중 6가지에서 정답보다 큰 값에 멈추었습니다. 멈춘 지점에서는 세로와 가로 모두 줄지 않지만, 대각선으로는 감소했습니다.

좌표 하강법이 적합한지는 '단일 변수 문제를 쉽게 풀 수 있는지'와 '변수들 간의 결속력이 얼마나 강한지'에 따라 결정됩니다. 변수를 하나씩 움직인다는 단순함은, 변수 간의 결속력이 약한 문제에서는 장점이 되었지만, 강한 문제에서는 약점이 되었습니다.

참고 자료

• 伊藤元治・原田耕平・松岡勇気『分析者のための数理最適化入門 アルゴリズムの仕組みから定式化の実践まで、網羅的に理解する』ソシム, 2026년, 제4장
• Wright, S. J. Coordinate Descent Algorithms. Mathematical Programming, 151, 3–34, 2015 (arXiv:1502.04759)
• 1.1. Linear Models - scikit-learn documentation
• Lasso - scikit-learn documentation
• QuantileRegressor - scikit-learn documentation
• minimize_scalar - SciPy Manual

토론