▲

최적화를 위한 알고리듬 [PDF 이북, 621p]

 (algorithmsbook.com)
54P by GN⁺ 2일전 | ★ favorite | 댓글 4개
  • 수학적 최적화의 원리와 알고리듬 전반을 체계적으로 다루는 교재로, 연속·이산 문제 모두를 포괄
  • 도함수 기반 기법부터 확률적·진화적 방법까지 다양한 접근법을 단계적으로 설명
  • 제약 조건, 이중성, 선형·이차 프로그래밍 등 실제 응용에 필요한 수학적 구조를 포함
  • 각 장마다 요약과 연습문제를 제공해 학습과 실습을 병행할 수 있도록 구성
  • MIT Press의 오픈 라이선스(CC BY-NC-ND) 로 배포

서문 및 개요

  • 이 책은 최적화 문제 해결을 위한 알고리듬의 이론과 구현을 다루는 교재로, 2판으로 출간
    • 저자는 Mykel J. Kochenderfer와 Tim A. Wheeler
    • MIT Press에서 발행, Creative Commons 비상업적·변경금지 라이선스로 공개
  • 서문과 감사의 글 이후, 13개 장으로 구성되어 있음
  • 각 장은 핵심 개념, 요약, 연습문제로 구성되어 학습 중심 구조를 유지

1장. 서론

  • 최적화의 역사, 과정, 수학적 정식화, 응용 분야를 소개
  • 극값(minima) 과 최적성 조건(optimality conditions) 을 설명
  • 전체 책의 개요와 요약, 연습문제 포함

2장. 도함수와 그래디언트

  • 단일 및 다변수 도함수의 정의와 계산 방법 설명
  • 수치 미분(numerical differentiation) 과 자동 미분(automatic differentiation) 기법 포함
  • 회귀 그래디언트와 확률적 근사 기법(SPSA) 다룸

3장. 브래킷팅(Bracketing)

  • 단봉성(unimodality) 개념과 초기 구간 찾기 절차 설명
  • 피보나치 탐색, 황금분할 탐색, 이차 근사 탐색 등 구간 기반 알고리듬 수록
  • Shubert-Piyavskii 및 이분법(bisection) 방법 포함

4장. 지역 하강(Local Descent)

  • 하강 방향 반복(descent direction iteration) 과 스텝 크기(step factor) 개념 설명
  • 선 탐색(line search) 및 근사 선 탐색 기법 포함
  • 신뢰 영역(trust region) 접근법과 종료 조건 다룸

5장. 1차 방법(First-Order Methods)

  • 그래디언트 하강법, 공액 그래디언트, 모멘텀, Nesterov 모멘텀 등 주요 기법 포함
  • AdaGrad, RMSProp, Adadelta, Adam, Hypergradient Descent 등 현대적 최적화 알고리듬 수록
  • 각 방법의 특징과 비교 요약 제공

6장. 2차 방법(Second-Order Methods)

  • 뉴턴법(Newton’s Method) 과 할선법(Secant Method) 설명
  • Levenberg-Marquardt 알고리듬 및 준-뉴턴(Quasi-Newton) 방법 포함
  • 요약과 연습문제로 마무리

7장. 직접 방법(Direct Methods)

  • 좌표 탐색, Powell, Hooke-Jeeves, 패턴 탐색, Nelder-Mead 단순스 방법 등 소개
  • 분할 사각형(Divided Rectangles) 기법 포함
  • 비도함수 기반 최적화 접근법 중심

8장. 확률적 방법(Stochastic Methods)

  • 노이즈 하강, 메쉬 적응 탐색, 무도함수 최적화 등 확률적 접근법 다룸
  • 시뮬레이티드 어닐링, 교차 엔트로피, 자연 진화 전략, 공분산 행렬 적응(CMA) 포함
  • 확률 기반 탐색의 효율성을 강조

9장. 집단 기반 방법(Population Methods)

  • 유전 알고리듬, 차분 진화, 입자 군집 최적화(PSO) 등 집단 탐색 기법 설명
  • Firefly, Cuckoo Search, 하이브리드 방법 포함
  • 집단 반복(population iteration) 구조로 문제 해결

10장. 제약 조건(Constraints)

  • 제약 최적화(constrained optimization) 의 기본 개념과 제약 유형 설명
  • 라그랑주 승수법, 슬랙 변수, 패널티 및 내부점(interior point) 방법 포함
  • 제약 제거 변환(transformations) 과 다중자 방법(method of multipliers) 다룸

11장. 이중성(Duality)

  • 이중 문제(dual problem) 와 원-이중(primal-dual) 방법 설명
  • 이중 상승(dual ascent) 및 ADMM(Alternating Direction Method of Multipliers) 포함
  • 분산 최적화(distributed methods) 응용 다룸

12장. 선형 프로그래밍(Linear Programming)

  • 문제 정식화, 심플렉스 알고리듬(Simplex Algorithm) , 이중 증명(dual certificates) 설명
  • 선형 제약 조건 하의 최적화 구조를 체계적으로 제시

13장. 이차 프로그래밍(Quadratic Programming)

  • 이차 목적 함수와 선형 제약 조건을 포함한 문제 정식화
  • 최소제곱(least squares) 문제와 선형 부등식 제약 다룸
  • 최단 거리 프로그래밍(least distance programming) 포함

부록 및 기타 정보

  • 각 장 말미에 요약과 연습문제 수록
  • MIT Press가 2025년판으로 발행, 비상업적 공유 허용(CC BY-NC-ND)
  • LaTeX 기반 조판, 문의는 bugs@algorithmsbook.com 으로 안내
▲
plorrr 1일전  [-]

지금은 접근이 안되네요ㅠ

답변달기
▲
slimeyslime 13시간전  [-]

https://algorithmsbook.com/optimization/#download
지금은 링크가 조금 바뀌었는지, 여기에서 PDF를 보거나 다운받을 수 있네요.

답변달기
▲
GN⁺ 2일전  [-]
Hacker News 의견

  • HN 메인에 최적화(optimization) 주제가 올라온 게 반가움
    내가 만든 LP 시각화 사이트를 소개하고 싶음. 선형계획법(Linear Programming) 알고리즘이 제약 조건이나 목적함수가 바뀔 때 어떻게 반응하는지를 시각적으로 볼 수 있음
    데모 페이지에 들어가면 다각형이 자동으로 그려지고, 꼭짓점이나 제약선을 드래그하면서 알고리즘의 반복(iteration)을 관찰할 수 있음
    아직 완성도는 높지 않지만, 시각적 학습을 좋아하는 사람이라면 재미있게 쓸 수 있을 것 같음. 피드백 환영함

    • 정말 멋진 프로젝트라고 생각함

  • 메타휴리스틱(metaheuristics) 관련 자료를 공유하고 싶음

  • 521쪽짜리 CC 라이선스 최적화 교재인데 정말 훌륭해 보임
    초반에는 자동미분 기반의 최신 gradient-based 알고리즘(예: Adam)을 다루고, 후반부(12장)는 선형최적화(simplex 등)를 다룸
    연습문제도 많고, 내가 오래 기다리던 바로 그런 책이었음
    최적화 알고리즘은 단순히 문제를 푸는 게 아니라, “일반 문제 해결기”를 향한 시도라고 생각함. 프로그램이 해답을 직접 찾는 대신, ‘해답이 어떤 형태일지’를 정의하고 그 위에 최적화를 적용하는 방식임
    현재 AI도 이런 접근을 기반으로 하고 있음

    • 완전한 일반 문제 해결기는 불가능하다는 no free lunch 정리를 떠올리게 함

  • Kochenderfer의 이 책과 이전 저서 Decision Making Under Uncertainty(PDF)는 내가 가장 좋아하는 기술서 중 하나임
    설명이 명확하고 시각화가 훌륭하며, gradient descent 외의 다양한 최적화 사고방식을 다룸
    코드가 Julia로 되어 있지만, 다른 언어로 옮기기 어렵지 않음. 언어에 얽매이지 말고 개념에 집중해야 함
    최적화는 단순한 테크닉이 아니라, 어려운 문제를 푸는 사고방식 자체임

    • 실용적인 문제 해결에도 off-the-shelf solver를 활용하면 좋음. 예를 들어 문제를 MILP나 SMT로 재구성하면 빠르게 기준 성능을 얻을 수 있음. 명세와 계산을 분리하는 사고를 배울 수 있음
    • 최적화 학습을 위해 다른 추천 자료가 있는지 궁금함. 나는 업무에서 multi-armed bandit을 자주 쓰는데, 다른 알고리즘도 탐색해보고 싶음
    • Kochenderfer의 다른 교재 목록은 공식 사이트에서 볼 수 있음
    • Julia 예제 코드는 LLM으로 자동 변환해도 됨

  • 이 책은 CMA-ES, surrogate model, Gaussian process 등을 한 권에 다루는 드문 자료임
    학부 연구 시절 이런 책이 있었다면 정말 도움이 되었을 것 같음. 예전엔 관련 내용이 여러 논문과 책에 흩어져 있었음

  • 박사과정 때 이 책을 여러 번 정독했음. 신경망과 수치해석을 연구했는데, 깊이와 폭의 균형이 잘 잡혀 있음
    지금도 참고서로 자주 활용함

  • 책에 Firefly, Cuckoo Search 같은 메타휴리스틱이 포함된 걸 보고 놀람
    이 알고리즘들은 학계에서 신뢰받지 못하고, ITOR 논문에서도 비판받았음
    이런 방식만 연구하는 소규모 커뮤니티가 서로 인용하며 버블을 형성하고 있음. 학회에서도 종종 논란이 됨

  • 다목적 최적화(multiobjective optimization) 챕터가 훌륭했음
    이 주제에 집중한 다른 책이나 자료가 있는지 궁금함

  • 이 책과 Nocedal & Wright의 Numerical Optimization을 비교해줄 수 있는지 궁금함

    • 이 책은 여러 방법을 백과사전식으로 폭넓게 다루지만, 실용적 사용법은 깊게 다루지 않음. 반면 Nocedal & Wright는 대학원 수준의 교재로, 소수의 핵심 알고리즘을 깊이 있게 설명함. 예를 들어 Interior Point Method는 이 책에선 2~3쪽 요약이지만, Nocedal & Wright에서는 한 챕터(약 25쪽)를 할애함
    • 다음엔 책 제목(Numerical Optimization, Jorge Nocedal & Stephen J. Wright)을 먼저 언급해주면 좋겠음
답변달기