이 책은 수학적 최적화라는 사고방식의 기초를 확실히 다지기 위해 최적화 문제로 모델링하는 법과 기본적인 최적화 알고리즘을 다룬다. 또한 이해를 돕기 위해 떠올리기 쉬운 구체적인 사례와 연습 문제가 수록되어 있다.
이 책의 구성
1장_수학적 최적화 입문
수학적 최적화는 주어진 제약조건하에서 목적 함숫값을 최소(또는 최대)로 하는 설루션을 구하는 최적화 문제를 말하며, 현실 사회의 의사결정이나 문제를 해결하는 수단입니다. 1장에서는 예시와 함께 수학적 최적화의 개요에 대해 설명합니다.
2장_선형 계획
선형 계획 문제는 가장 기본적인 최적화 문제로, 대규모의 문제 사례를 현실적인 계산 수단으로 푸는 효과적인 알고리즘이 개발되어 있습니다. 선형 계획 문제의 정식화, 선형 계획 문제의 대표적인 알고리즘인 단체법에 대해 알아보고, 수학적 최적화에서 가장 중요한 개념인 쌍대 문제와 완화 문제를 설명합니다.
3장_비선형 계획
비선형 계획 문제는 적용 범위가 매우 넓기 때문에, 다채로운 비선형 계획 문제를 효율적으로 푸는 범용적인 알고리즘 개발은 어렵습니다. 비선형 계획 문제의 정식화, 효율적으로 풀 수 있는 비선형 계획 문제의 특징을 설명한 뒤 제약이 없는 최적화 문제와 제약이 있는 최적화 문제의 대표적인 알고리즘을 설명합니다.
4장_정수 계획과 조합 최적화 문제
선형 계획 문제에서 변수가 정숫값만 갖는 정수 계획 문제는 산업이나 학술 등 폭넓은 분야에서 현실 문제를 정식화할 수 있는 범용적인 최적화 문제 중 하나입니다. 정수 계획 문제의 정식화, 조합 최적화 문제의 어려움을 평가하는 계산 복잡성 이론의 기본적인 사고방식에 대해 알아봅니다. 또한 몇 가지 특수한 정수 계획 문제의 효율적인 알고리즘과 정수 계획 문제의 대표적인 알고리즘인 분기 한정법과 절제 평면법을 설명한 뒤, 임의의 문제를 예로 들어 근사 성능을 보증하며 실행 가능한 설루션을 구하는 근사 알고리즘과 많은 문제 사례에 대해 고품질의 실행 가능한 설루션을 구할 수 있는 국소 탐색 알고리즘 및 메타 휴리스틱에 대해 설명합니다.
대상 독자
최적화 이론에 관심 있는 학생과 연구원 및 수학적 최적화와 관련 업무에 종사하는 실무자
수학 관련 전공자가 아니더라도 인공지능 분야나 기타 여러 산업 분야에서 최적화 알고리즘 적용에 대한 공부를 하고 싶은 독자
저자소개
저자
우메타니 슌지
1974년생. 정보학 박사. 2002년 교토대학 대학원 정보학 연구과 박사 후기 과정을 수료한 뒤 연구 지도 인정을 받고 자퇴하였다. 현재 오사카대학 대학원 정보과 수학적 최적화 기부 강좌 교수이며 수학적 최적화와 알고리즘 운영 부문에 종사하고 있다. 특히 규모가 크면서 계산이 난해한 조합 최적화 문제에 대한 실용적 알고리즘 개발, 수학적 최적화 모델 및 알고리즘 구현 문제가 주요 연구 분야다.
역자
김모세
대학 졸업 후 소프트웨어 엔지니어, 소프트웨어 품질 엔지니어, 애자일 코치 등 다양한 부문에서 소프트웨어 개발에 참여했다. 재미있는 일, 나와 조직이 성장하도록 돕는 일에 보람을 느껴 2019년부터 번역을 시작했다. 옮긴 책으로는 『인간 vs. AI 정규표현식 문제 풀이 대결』(제이펍, 2023), 『실무에 바로 쓰는 일잘러의 마이크로카피 작성법』(제이펍, 2023), 『애자일 개발의 기술 2/e』(에이콘, 2023), 『타입스크립트, 리액트, Next.js로 배우는 실전 웹 애플리케이션 개발』(위키북스, 2023), 『플레이어를 생각하는 게임 UI 디자인 노하우』(한빛미디어, 2023) 등이 있다. 이 책은 옮긴이 소개를 작성하는 시점으로 44번째 번역서이다.
수학적 최적화는 현실 속의 문제를 합리적으로 해결하는 방법 중 하나입니다. 수학적 최적화를 빠르게 이해하기 위해서는 문제를 최적화하기 위한 모델링 방법을 익히고 효율적인 알고리즘이 적용된 최적화 문제를 살펴봐야 합니다. 이 책은 수학적 최적화라는 사고방식의 기초를 확실히 다지기 위해 최적화 문제로 모델링하는 법과 기본적인 최적화 알고리즘을 다룹니다. 또한 이해를 돕기 위해 떠올리기 쉬운 구체적인 사례와 연습 문제가 수록되어 있습니다.
추천사
“수학적 최적화 문제 해결을 위한 책이다. 직면한 문제를 해결하려면 먼저 모델링하여 적절한 최적화 방법을 적용하는 절차를 밟아야 한다. 이 책은 풍부한 실제 사례를 통해 모델링의 핵심을 설명하고 다양한 최적화 기법을 알기 쉽게 해설하고 있다. 최적화 분야 전반을 알기 위한 최적의 설루션으로 추천하고 싶다.”
수학적 최적화는 주어진 제약조건 아래 목적 함숫값을 최소(또는 최대)로 만드는 최적화 문제를 이용하여 현실 사회에서 의사결정이나 문제 해결을 실현하는 수단이다.
‘알고리즘과 데이터 구조’, ‘미적분’, ‘선형대수’와 같은 컴퓨터 과학과 수학적 지식을 전제로 하고 있으며, (생략)
이 책은 “최적화”라는 단어에 끌려서 선택하게 되었다. 그리고 간과하지 못한 사실은 그 앞에 “수학적”이라는 단어가 따라온다는 것이다.
중등 교육 과정에 있던 수학과 대학에서 선형대수(행렬, 벡터)를 배운 부분을 제외하면 나는 수학과 거리가 아주 멀다. 선수 지식으로 요구하는 미적분은 배운 적도 없을뿐더러, 시간 복잡도를 표기할 때 나오는 log조차 문외한이라 매번 찾아본다. 갑자기 고해성사하는 이유가 무엇인가 함은, 이 책이 나 같은 수포자에게 쉬운 책은 절대 아니라는 사실을 말하기 위해서다.
책은 네 개의 챕터와 부록으로 연습 문제가 구성되어 있다.
수학적 최적화 입문
선형 계획
비선형 계획
정수 계획과 조합 최적화
미적분과 선형 대수를 학습하지 않은 사람은 3장 ‘비선형 학습’ 쪽이 수학적 최적화 입문에 낫다는 소개가 있어 3장을 먼저 읽고, 그나마 익숙한 단어들이 있는 4장을 읽었다.
3.1 에서는 비선형 계획 문제의 예로 시설 배치 문제, 원 채우기 문제, 포트폴리오 선택 문제 등을 제시한다. 그중에 시설 배치 문제의 정의는 다음과 같다.
어떤 기업은 n 곳의 점포 개점에 맞춰, 배송 센터 설치를 검토하고 있다. 이때 어떤 장소에 배송 센터를 배치하면 좋을 것인가?
다른 챕터에서도 마찬가지로 도입부에 제시하는 문제들은 대체로 현실 세계에서 일어나는(혹은 일어날법한) 문제들을 제시한다. 그래서 수학은 잘 모르지만, 와닿지 않는 수학 문제를 툭 던지는 것보다 흥미롭게 읽을 수 있었다. (XXX 쉽다는 얘기 절대 아님 XXX)
문제 소개, 풀이 과정, 알고리즘 설명 형식으로 내용이 구성되어 있으며, 모든 챕터의 마지막에는 배운 내용을 연습할 수 있는 연습 문제가 제공된다. 아쉬운 점을 꼽자면 번역에서 Solution을 설루션으로 번역한 부분이 어색하다는 정도?
책의 내용은 좋은데 초라한 수학적 지식이 발목을 잡아서 아쉬움이 남는다.
딥러닝같이 최적화가 필요한 분야나, 알고리즘을 수학적으로 깊게 접근하고 싶은 사람에게 추천하고 싶다.
최적화하고 싶은 목적과 그에 수반되는 제한사항을 수학을 통해 기술하고 해(solution)을 구하는 것
다양한 분야에 활용되고 있지만, 특히 요즘엔 인공지능이라는 이름으로 불리는 머신러닝과 딥러닝이 대표적인 예시
"제대로 배우는 수학적 최적화"
최적화의 기초: 최적화에 대해 입문하는 사람을 위한 기초적인 내용
선형 계획: 선형 계획 문제의 형태 및 풀이 방식(단체법)
비선형 계획: 비선형 계획 문제의 형태 및 풀이 방식(제약 X-경사 하강법, 뉴턴 법, 준 뉴턴 법/제약 O-확장 라그랑주 함수 법, 내점 법, 순차 2차 계획법)
정수 계획: 정수 계획 문제의 형태 및 풀이 방식(탐욕 알고리즘, 동적 계획법)
이 책의 특징들
Positive
누구보다 수학에 진심인 저자!
목적에 따라 처음부터 끝까지 따라하지 않고 필요한 순서대로 읽거나, 원하는 부분만 발췌해서 읽어도 충분히 도움이 되도록 구성
연습문제를 통해 학습에 도움이 되도록 구성
Negative
수학에 너무 진심이라 선형대수, 미적분학, 해석학 중 몇 가지는 알고 있어야 함(여기에 다른 내용들도 추가될 수 있는데, 내가 아는 선이 여기까지라..)
중간중간 오탈자가 보여 거슬림(아직 크게 문제 될 부분은 못찾았지만 꽤 많긴 하다)
참고 문헌에 대해 책에 잘 정리 되었지만, 국내(한국)에서는 접하기 어려운 책들로 보임
이 책은 ________ 추천한다!
수학 전공자로써 최적화에 대해 입문하고 싶다면
공학 전공자들이 최적화 수업을 들어야 한다면 부교재로 활용하는 것을
기타 수학에 어느정도 흥미가 있는 사람들이 최적화에 대해 본격적으로 알고 싶다면
P.S. 대학원때 간신히 들으며 쫓아갔던 Convex optimization(볼록 최적화)라는 수업이 있었는데, 그 당시에는 원론적인 최적화 기법에 대한 소개보다는 문제 정식화와 프로그래밍을 통한 풀이 위주의 수업이었다. 그 당시 배웠던 내용이 가물가물하긴 하지만, 드문드문 반가운 내용들도 있어 나름 재미있는 시간이었다. 물론 이번 리뷰는 2주라는 짧은 시간이 주어져 많은 내용을 찬찬히 읽어보진 못했지만, 추후 진지하게 한 번쯤은 읽어볼 만한 책이라 생각된다.
코딩 테스트를 위한 알고리즘들을 공부하다보니, 결국엔 수학이 가장 중요하다는 것을 여러번 느낍니다. 기업 코딩테스트를 위해 반드시 깊은 수학적 지식이 필요한건 아니지만, 지식이 있다면 분명 도움이 될것이라는 생각에 제대로 배우는 수학적 최적화를 선택해 읽어봤습니다.
먼저, 전체적인 느낌은 충분히 실생활 또는 업무에서 필요할만한 문제들을 다룬다는 것입니다. 가끔 알고리즘 문제들을 보면, 마치 찢은 달력을 보고 특정 날짜를 추론하는 어릴적 수학문제 처럼, 썩 와닿지 않는 경우를 가져와 문제들을 가져오는 일들이 종종 있었습니다. 이 책도 여러 수학문제들을 다루다보면 그럴것 같았지만, 생각보다 와닿는 문제들로 알고리즘을 다뤄 좀더 몰입감(?)을 갖고 읽을 수 있었습니다.
주의하셔야할 부분은, 알고리즘을 위한 코드는 단 한줄도 나오지 않습니다. 코딩이 아닌, 수식을 통한 알고리즘 최적화를 다루는 책입니다.
보시는 것처럼, 특정 알고리즘의 수행 예시와 최적화하기 위한 추가 개념들을 상세하게 알려줍니다.
전 필요하다고 생각되는 알고리즘이 있을 때, 해당하는 챕터를 읽는 식으로 활용하고 있습니다. 아무래도 책이 수식과 풀이로 이루어져있다보니 소설처럼 읽기는 무리가 조금 있습니다.
입문서이면서도 수준이 상당하다, 기본적으로 수학과 알고리즘을 다루고 있기에 단순한 초심자가 보기에는 필요한 관련 기초지식이 필수적이다. 특히나 선형대수, 미적분과 같은 수학적 지식과 알고리즘이나 자료구조와 같은 컴퓨터 공학적 지식을 복합적으로 필요로 하기에 만만히 볼만한 책은 아니다.
수학적 최적화는 주어진 제약조건에서 목적 함수의 값을 최소/최대로 만드는 최적화 문제를 이용하여 현실 세계의 의사결정 등과 같은 문제 해결을 실현하는 수단으로 다양한 산업 분야와 학문적 영역에서 많은 문제를 최적화 문제로 모델화 하여 처리 또는 연구에 활용되고 있다.
더군다나 데이터의 양이 과거에 비해 엄청나게 커진 시대에 살고 있는 우리로서는 좀 더 효과적인 알고리즘의 개발이 요구되는 것이 현실이다.
이 책은 그간 알려진 대표적인 최적화 문제와 알고리즘을 소개하고 있다. 다만 수학적 접근을 통한 내용의 전개가 이뤄지기에 관련 기초지식이 충분이 갖춰지지 않는 경우 페이지를 넘기기가 쉽지 않을 것이다. 다음 그림에는 이 책에서 다루고 있는 최적화 문제와 알고리즘이 정리되어 있다.
책의 근간은 수학이다, 그래서 접근이 쉽지 않다.
최대한 그림, 도식 등을 동원해서 쉽게 설명하고자 노력한 흔적이 곳곳에 있다.
머신러닝이나 딥러닝 입문시 가장 처음 접근하게 되는 경사하강법도 일종의 수학적 최적화중 하나이다.
최적화 문제중 가장 널리 알려진 것이라고 해도 과언이 아닌 외판원 문제나 다익스트라 알고리즘도 조합 최적화 문제의 일종이다.
쉽지 않은 책이다.
하지만 최적화라는게 현실 세계에서 발생하는 여러 문제에 접목해볼 수 있는 것이다 보니 학문의 영역에서 현실 세계를 연결시켜주는 중간 매개체 역할을 해줄 수 있는 분야하 보니 꼭 넘어야할 산이 아닐까?
이를 위한 입문에 도움을 줄 수 있는 잘 쓰여진 책이나 4~6개월정도 진득하게 정독하며 공부해야할 책이 아닌가 싶다. 요즘 머신러닝이다 딥러닝이다 해서 관련 공학적으로 필요한 수학 입문서들이 많은데 기초적인 공학적 수학을 공부했다면 이 수학적 최적화를 공부해야 비로서 현실 문제를 수학적으로 바라보고 풀어볼 수 있는 인사이트가 생기기 될 것이다.
나도 책 리뷰를 위해 2주정도 퀵하게 훌터봤으나 찬찬히 정독을 해야할 시간이다, 그리고 나의 부족함을 찾아내고 보완해야겠지... 지난한 시간이 되겠지만 해내야 한다... ^^
인공지능 시대라 해도 최적화는 다양한 층위의 기술을 죄다 써야 현안을 해결할 만하다고 단언하는 바이다.
한빛미디어에서 출간한 책을 여러 권 읽어 오면서, 이제서야 내가 배우고 싶은 주제만 오롯이 달달달 설명한 책을 만났지만 마음이 복잡해졌다. 부끄럽게도 수학에 능숙한 편이 못 되어 제대로 배우기 힘들었기 때문이다. 이 책에 나오는 여러 개념이나 기법을 이 책을 통해 처음 접했다면 이 책을 끝까지 읽어내기도 힘들다. 고교수학에 어느 정도 자신이 있는 이는 두려움 없이 도전해도 좋겠다.
목차를 보면 전통적인 최적화 외에 머신러닝과 유관한 내용도 꽤 되었다. 알고리듬 교재 같은 면도 있다. 최적화를 익힘에 있어 확실히 도움이 될 만한 책인데 진입장벽이 결코 낮지 않다. 뒷표지에 최적의 입문서 운운했지만 그렇지 못하다. 이 책에서 소개하는 입문서는 대체로 일본에서 출판했기에 소개가 도움이 되지 않는다. 답답해졌다.
모르는 사안은 달리 알아서 찾아 봐야 하겠지만, 이 책의 의의는 분명하다. 최적화라는 주제에 나오는 방대한 사안을 빠짐 없이 언급했기 때문이다. 최적화로 도서를 검색했을 때에 전통적인 내용만 다루거나 머신러닝 얘기만 하는 식으로 갈리는 게 실태라 이런 어려운 책도 분명히 도움이 된다. 용기를 내길 바란다. 영 힘들 때에는 일단 엑셀의 '해찾기' 기능부터 도전하면 좋다. 상당히 강력한 최적화 기능이다.
사과 1개는 800원, 아이스크림 1개는 500원이라고 가정하면 이를 수리적으로 접근해볼 수 있을 겁니다.
사과 개수를 x, 아이스크림 개수를 y라고 할 때, 효용함수 U(x, y) = 100x + 50y 라고 할 수 있고, 비용함수 C(x, y) = 800x + 500y ≤ 5000 이라고 세울 수 있겠죠.이를 수학적 최적화를 이용해 풀면, 주어진 예산을 효율적으로 사용하고 효용도 가장 크게 할 수 있는 최적의 소비 조합을 찾을 수 있게 됩니다.이게 최적화의 기본이라고 할 수 있죠! 매력적이지 않나요?
Q. 그럼 누구에게 추천하는 책인가요?
이 책은 대학 혹은 대학원에서 수학적 최적화를 처음 학습하는 학생이나,
최적화의 개념을 실무에서 응용하고자 하는 실무자에게 추천하는 책입니다.
개인적으로는 경제학이나 통계학, 산업공학을 공부하는 학부생,
그리고 기계학습을 심도있게 공부하려는 분들에게 추천하는 책입니다.
저도 기계학습을 잘하고 싶은 사람으로서 최적화는 심도있게 공부해야겠단 생각이 점점 들더라고요.
그런 의미에서 이 책을 처음 보았을 때 '이건 무조건 신청해서 받아야헤...' 라고 생각했답니다.
본인의 독서 목적에 따라 추천 방법이 나와있습니다.
이를 참고하셔서 어떻게 읽을지 판단하시면 되겠습니다.
Q. 이 책의 장점은 무엇인가요?
이 책의 가장 큰 장점은 시중에서 찾기 힘든 최적화 번역서라는 겁니다.
통상 최적화 책은 Convex Optimization라고 불리는 외국 서적들이 대다수였는데요.
위키 형식으로 모두를 위한 최적화였나... 암튼 훌륭하신 분들께서 만들어놓은 무료 파일이 있는데,위키 형식이다보니 이런 서적 형태의 학습서가 제겐 더 절실하긴 했습니다.그런 의미에서 최적화 책을 번역서로 심도있게 공부할 수 있다는 게 가장 큰 장점이지 않나 싶습니다.
또한 예제 문제뿐만 아니라, 예제에 대한 해설도 책에 수록되어 있습니다.특히 대학교 전공 서적이 예제만 있고 솔루션은 없어서 정말 화가 난 순간이 많았는데, 이 책은 그렇지가 않아서 좋습니다.
다만 내용이 어려운 만큼, 베이스가 없으면 정말 읽기가 힘들 거라 생각합니다.
그리고 일본어가 베이스인 원서를 번역하다보니 그 용어가 좀 어색해요.
설루션이라든지 ... 뭐 근데 사실 수학 용어를 번역하는 것만큼 어색한 것도 없는 것 같습니다.
이번달에는 어떤 책을 볼까 하다가 최적화 책이 있어서 골랐다. 물론 코드를 최적화해서 똑같은 문제를 적은 메모리를 사용하도록 메모리 최적화를 한다거나, 더 높은 프레임으로 프레임 개선을 하는 것이 아니라, 수학적 최적화이다.
기계공학부 수업에는 최적화 문제(Optimization Problem) 에 관한 과목이 있었고, 나는 들어보진 않았지만 교수님과 같이 하는 연구에서 최적화 문제를 다뤘다.
그때는 그냥 아 이렇게 하면 되는구나 하면서 구현만 했는데, 정확하게 어떤 노테이션으로 수식을 적는지, 어떤 의미를 지니는지 잘 몰랐다. 어떻게 해야하는지는 교수님께서 알려주시니까 그대로 구현만 했다. 그래서 이번에 최적화 문제에 대한 지식을 얻고자 이 책을 선택했다.
책을 펼치자마자 수학적 최적화에 대한 설명이 시작된다. 수학적 최적화에 대한 개념은 꽤나 간단한 것 같다. 제약 조건을 만족시키는 목적 함수값이 최대 또는 최소가 되는 x값을 찾는 문제이다. 제약조건이나 목적함수가 가진 수식의 형태에 따라서 선형, 비선형으로 나뉘고 제약조건이 부등식인지 등식인지 그리고 미분 가능한지에 따라서도 구체적인 알고리즘이 달라진다.
정의부터 차근차근 필요한 개념들을 설명해주며 수학 기호들과 그래프들이 난무한 것을 볼 수 있다.
이렇게 다양한 분야에서 최적화 문제를 다룰 수 있다. 문제를 어떻게 fomulation할지, 어떤 파라미터를 설정할지, 어떤 제약조건과 목적함수를 둘지 정말 많은 모델링이 가능하다. 전반적인 분야들의 최적화 문제 풀이들을 보면서 지식들을 쌓아 갈 수 있을 것이다.
최적화 문제는 정말 다양한 문제에 대해서 다룰 수 있다.
딥러닝에서도 신경망들의 웨이트를 조절해갈때, 최적화 기법을 사용한다. 대표적으로 경사 하강법이 있는데, 이것 또한 최적화 문제이다.
연구하면서 대충 넘어간 수식이나 개념들을 이 책에서 다시 한번 보면서 이해할 수 있어서 좋았던 것 같다. 책은 사실 수식 투성이다. 미분이나 이산수학, 선형대수를 모르면 이 책을 따라가기 어렵다. 그래서 수학적 최적화이기도 하다. 정말 이런 수식들을 보면 좀 토나오긴 하지만.. 그래도 푸는게 아니면 대충 느낌은 온다. 풀어보진 않아서 완전히 내것이 되진 않지만, 그래도 이런 것들이 있구나 하고 알고 있는게 언젠간 도움이 될 것 같긴 하다. 이 책에서는 대표적인 최적화 문제에 대해서 전반적으로 다룬다. 그래서 다양한 부분에서 인사이트를 얻을 수 있다.
처음에는 단순히 재미있어보이는 주제를 가진 책을 리뷰하려하였다. 그래서 고른게 위 책 '제대로 배우는 수학적 최적화'이다. 하지만 재미있는 주제가 아니었을 뿐더러 굉장히 어려운 주제를 가진 책이여서 한줄 한줄 진땀 흘리면서 읽게 되었다.
사실 제대로라는 표현히 이 쯤 되면 맞는 것 같기도 하다.
책의 내용은 선형대수학, 정수론, 이산수학(전반적으로 컴퓨터로 해결을 하는 문제)에 관련되어서 다룰 수 있는 일부분에 대해서 수학적으로 증명하고 해결하는 책이다.
솔직히 이 책을 읽으면서 반성을 많이 하였다. 어디서 본듯한 수학적 기호와, 공식이 있었지만 기억이 나지 않았다. 사실 '머리에 익지 않아서 표현이 들어오지 않았다'라는 표현히 좀 더 적절하다.
이 책을 읽기전에 선형대수학에 대한 전반적인 지식이 있으면 매우 좋을 것 같다. 선형대수학의 지식이 부족하다면 글 한줄한줄 읽는 것에 매우 여러움을 느낄법도 하다. 또한 편미분에 관련된 기초적인 지식이 있는 것도 중요할 것 같다. 중간 중간 편미분에 관련된 공식이 등장하기도 한다.
사실 이 부분 때문에 책을 읽을 때에 매우 고된 작업이었다.
아마 인공지능에 관심이 있다면 경사하강법에 대한 기본적인 이론을 알고 있을 것이다. 이 책에서는 경사하강법에 대해서 증명과 공식에 대해서 수학을 좋아한다면 매우 반가울 듯이 많이 제공한다.
안타깝게도 수학과는 이제 거리가 먼 나 같은 서버개발자는 까만 것은 글씨오, 흰 것은 종이요 하면서 읽었다.
모처럼 그나마 반가운 주제도 등장한다. 컴퓨터과학생이라면 한 번은 들어봤을 법한 냅색문제. 이 책에서는 컴퓨터로 해결할 수 있는 문제에 대해서 수학적으로 증명을 한다. 앞에서의 선형대수학의 늪에 빠져 해매던 나에게 그나마 빛이 되었던 주제다.
정수론과 관련된 문제에 대해서도 수학적인 증명과 풀이 방식을 제공한다.
읽으면 읽을수록 대학 때 수학 공부 좀 많이 해둬야 겠다는 생각이였다.
이 책은 전적으로 초보를 위한 책이 절대 아니다. 수학적인 관심이 매우 높고, 수학적으로 문제를 풀려고 하는 사람, 수학적 증명을 좋아하는 사람은 매우 행복해하면서 읽을 수 있겠지만, 서버 개발만 주로 다루는 나는 앞장에서 부터 등장하는 수학적 기호에 매우 당황할 수 밖에 없었다.
컴퓨터로 문제를 해결하는 사람이 수학을 좋아한다면 이 책을 보고 통찰을 깨달을 수 있겠다고 예상한다.
먼저 이 책에 대해 들어가기에 앞서서 이 책을 보려는 사람들은 이산수학, 미적분, 선형대수학에 대한 사전 지식이 어느 정도 있는 상태에서 봤으면 한다. 안그러면 각 챕터별로 부족한 지식을 여러 자료를 통해서 보충하면서 봐야할 것이다. 이 책은 프로그래밍과 딥러닝 등에서 기저에 깔려있는 수학적 문제들에 대한 본질적인 부분을 파고들어서 해결을 하는 데 초점을 맞춘 책이다. 대학에서 교재로 사용하기 좋아 보이는 책이다.
책에서 다루는 문제들과 해당 알고리즘에 대한 구조도이다. 이 부분에서 본인의 기초 지식이 부족하거나 하는 부분은 스스로 보안을 해서 이해해야할 것이다.
꽤 다양한 수학적 문제를 다루지만, 비전공자인 나에게 비선형계획법 등은 쉽지 않았다.
이 책의 아쉬운 점 중에 하나는 수식에 약간 오탈자들이 있다는 것이다. 설명의 오탈자가 아닌 수식에 오탈자가 있는 경우, 조금 헷갈리고 짜증나기도 한다. 블로그나 구글링을 통해 다른 자료를 보면 수식에 오타가 있음을 알 수 있는데 이를 감별하는데 있어 조금 스트레스를 받을 수 있으니 그 점은 유념하고 이 책을 보자. 그러니, 이 책만 봐서는 안되고, 구글링을 통해 여러 자료랑 같이 보는 것이 더 좋을 것이다. 한 가지 더 아쉬운 점은 책에서 부자연스럽게 용어를 해석한 것이 있다는 것이다. 이런 부분에 익숙한 사람들도 있겠지만 번역서에서 흔히 나오는 문제들 중 하나인데 이런 부분은 역시 아쉽다.
책에는 정말 많은 수식들이 나와서 대학에서 공업수학을 어느 정도 공부했거나, 산업공학과 출신 또는 수학을 좋아하는 사람이 아니라면 공부하기 벅찰 것이다. 이 책을 보고 싶다면 반드시 미적분학, 선형대수학 등은 미리 공부하고 보는 게 좋을 것이다. 다시한 번 말하지만, 실무에 바로 적용할 수 있거나 하는 책은 아니며 대학에서 교재로 사용할 법한 책들이다. 그래도 최적화에 대해 다루는 책 자체가 번역서든 무엇이든 국내에 많지 않기에 일단 두고두고 보다가 mooc 에서 관련 강의 등을 공부하다가 어려우면 다시 이 책을 참고서로 보거나 하는 등으로 활용하면 좋을 것 같다.
우리는 많은 상황에서 최적화라는 말을 사용합니다. 네비게이션의 최단경로찾기나 프로젝트의 마감을 준수하면서 비용을 최소화, 혹은 인력을 최대로 활용하기위한 일정 계획, 혹은 여러 공장들을 가진 기업에서 물류창고를 짓기 위한 입지 선정 등 많은 최적화 문제들이 존재하고 이를 해결하고자 하는 수요는 항상 존재해왔습니다. 이런 문제들을 해결하기 위해 주어진 제약조건들 하에서 이익이나 비용등을 나타내는 목적함수를 최대/최소화 하는 해를 구하는 것을 수리 계획법, 혹은 수학적 최적화라고 합니다.
위에서 예시로 든 다양한 최적화 문제는 수리 최적화 모델로 나타낼 수 있고, 수학적인 속성이나 문제를 해결하기 위한 알고리즘 설계를 통해 최적, 혹은 최적에 가까운 해를 찾아낼 수 있습니다. 특히, 많은 분들이 딥러닝을 접하며 한번쯤 들으셨을 경사하강법(gradient descent) 또한 손실 함수를 최소화 하기 위한 파라미터(해)를 찾기 위해 기울기라는 수학적 속성을 이용하여 해를 찾아 나가는 최적화 문제를 풀기위한 알고리즘입니다.
이 책의 내용
수리적 최적화를 공부하는 입장에서 이 책은 대학원, 혹은 산업공학과 4학년 전공교재로 사용해도 좋을 것 같다는 생각이 들 정도로 알차게 구성되어 있습니다. 책의 두께가 생각보다 얇아서 많은 내용을 얕게 다루지 않을까 걱정했는데, 그 생각이 기우일 정도로 한장한장 가득 채워 내용이 담겨있습니다.
이 책에서는 산업공학, 컴퓨터공학을 전공하며 한번씩 들어보았을 선형계획법 문제부터 비선형 계획법, 정수 계획법, 조합 최적화 등의 주제를 다루고, 그 안에서 각 문제의 수학적 특성과 문제를 해결할 수 있는 알고리즘에 대해서 소개하고 있습니다. 그 뿐만 아니라 후반부에서는 메타휴리스틱 기법까지도 다루며 독자들에게 최적화 문제를 풀 수 있는 직관적이고 검증된 방법론에 대해서 설명합니다.
이 책을 읽으며 여러 점이 인상깊었는데, 첫 번째로 선형 계획법 문제를 해결할 때 많이 사용되는 심플렉스 알고리즘(단체법)을 표가 아닌 수리적 특성을 기반으로 설명해 준다는 것입니다. 많은 경영 과학 수업에서 이 알고리즘을 간략하게 배우거나 표를 이용하여 푸는 방법을 배우게 되는데, 표 기반의 심플렉스 알고리즘은 좋은 프레임워크이기는 하나 그 이론적 배경을 모두 이해하지 않고 단순히 행렬의 기본행 연산만 수행하는 꼴이 되는 경우가 많습니다. 심플렉스 알고리즘의 수학적 배경까지 모두 설명하면서 알고리즘을 만들어가는 부분이 있다는 점에서 대학 교재로 사용되는 책들보다 훨씬 더 훌륭하다고 느껴졌습니다.
두 번째로 인상깊었던 점은 비선형 계획법에 있었습니다. 비선형 계획법에서 반드시 알아야 할 볼록 집합, 볼록 함수, 그리고 subgradient와 semidefinite이라는 개념을 소개하고 이를 하나로 연결시키는 부분에서 간결하면서 필요한 정리와 증명을 통해 풀어나가는 스토리텔링이 아주 좋다고 느껴졌습니다. 적당한 난이도와 적절한 수준의 내용으로 필요한 개념을 이해시키는 것이 매우 어려운 일인데도 매끄럽게 잘 풀어나가는 점이 인상깊었습니다.
아쉬운점
열심히 latex 작업하셨을 역자님과 편집자님께는 죄송하지만, 수식에 오탈자가 타 책에 비해 많아 보였습니다. 타 책에 비해 압도적으로 많은 수식이 있기도 하고 전공자이기 때문에 꼼꼼히 보기도 해서 그럴 수 있지만, 수식으로 풀어나가는 이야기가 많은 책이기에 조금 아쉬움이 남았습니다.
그리고 설루션이라는 번역이 조금 어색하다고 느껴졌습니다. 흔하게 쓰이는 '솔루션', 혹은 '해'로 표기해도 되지 않았을까 하는 생각이 들었습니다.
대상 독자
최적화를 조금 더 깊게 공부하고 싶은 산업공학과 전공자들에게 먼저 추천하고 싶습니다. 수학적인 내용이 많기 때문에 비 공학 출신 분들에게 권하기는 조금 어려울 것 같고 미적분학, 선형대수 강의를 수강하고 선형계획법에 대해서 공부한 적 있는 분들이 본다면, 수업에서 배웠던 내용보다 조금 더 넓은 세계를 볼 수 있는 지도가 되지 않을까 생각됩니다.
딥러닝에 관심이 많아 이 책을 보려고 하시는 분들은 비선형 계획법과 책 중간중간에 등장하는 최적화에 관련된 이론들(KKT 조건 등)이 도움이 되실 것 같습니다. 최적화 관점에서 보자면, 딥러닝의 파라미터를 찾는 방법도 최적화 문제이기 때문에 기존과는 조금 다른 관점에서 딥러닝을 살펴보실 수 있는 기회가 될 것 같습니다.
또한 정수 계획법과 조합 최적화 부분은 잘 알려진 외판원 문제(TSP)나 최단 경로 문제도 다루고 있을 뿐 아니라 동적 계획법이나 크루스컬 알고리즘 등 관련된 알고리즘도 다루고 있기 때문에 컴퓨터 공학이나 알고리즘을 공부하시는 분들에게도 참고하기 좋은 내용들이 많이 있습니다.
아마 중학교 때부터 사람들이 방정식이라는 것을 접하고, 수학이라는 게 참 어려운 것이 답, 혹은 해를 찾는 것이라는 것을 깨닫는다. 물론 이차방정식, 삼차방정식은 해를 풀 수 있는 기법들이 제공되어 쉽게 풀 수 있다고는 하지만, 이런 식들을 다른 식들과 연계되면 그 해를 구하는 과정이 조금 더 복잡해진다. 재미있는 것은 대학교를 졸업하고, 취업을 해도 이 해를 구하는 과정은 계속된다는 것이다. 오히려 학생때 접했던 것처럼 명확한 수학 공식이 아니라, 글로 표현된 현상을 이해하고, 이에 대한 최적점을 찾는 것이다. 보통 이런 과정을 Optimization, 최적화라고 표현하는 것 같다.
인공지능 영역에서도 이 최적화과정이 필요하다. 신경망을 학습시킬 때도 예측값과 실제값간의 오차를 줄이기 위한 최적의 해를 찾아야 하고, 강화학습을 적용해서 길을 찾는 에이전트를 학습시킬때도, 각 상태가 제공하는 정보를 조합하여 최적의 경로, 혹은 정책을 찾는 일을 해야 한다. 물론 현재는 이런 최적화를 자동으로 해주는 도구들도 많이 나와있기 때문에, 예전처럼 현상을 수식으로 모델링하고, 손으로 직접 풀어야하는 수고로움은 조금 덜어졌지만, 그래도 단순히 도구를 쓰는 것에서 넘어서, 원론적으로 최적화에 대한 이해를 하려면, 그런 수고로움도 어느정도 감내해야 하지 않을까 싶다.
제대로 배우는 수학적 최적화
이번에 소개할 책은 전형적인 "수학"책이다. 아마 고등학교때 접했던 "수학의 정석"이나, 혹시 대학교에서 수학 관련 수업을 듣고 오래 지났다면, 이 책이 익숙해지기 전까지는 조금 시간이 필요할 것이다. 여기서 전형적인 "수학"책이라고 한 것은 책안에 담고 있는 내용들이 실무에서 바로 적용할 수 있을 법한 어떤 실용적인 기법들을 담고 있는 것이 아니라, 수많은 정의와 정리, 증명, 그리고 예시들이 담겨져 있다는 것이다. (사실 책 소개 홈페이지에서 책의 난이도를 초중급으로 표기했는데, 개인적으로는 이 책에서 다루고 있는 내용은 적어도 중고급의 수준은 아닌가 싶다.)
나는 개인적인 필요성에 의해서 이 책을 선택했다. 사실 하고 있는 일이기도 하지만, 주어진 데이터들이 있을때, 이를 어떻게 하면 선형 방정식으로 잘 모델링하고, 이에 대한 최적화를 수행하는 것이 필요하다. 강화학습에서도 우리가 모르는 환경에 대해서 잘 모델링하고, 이 모델에 대한 해를 찾아야 최적제어를 할 수 있는데, 그런 과정이 너무 어렵다. 특히 나는 수학 전공도 아니었기 때문에, 단순히 해석학에서 다루는 수준의 내용만 알고 있었던 터라, 기본적인 최적화 이론에 대한 복습부터 예시에 적용해볼 수 있는 이론들에 대해서 살펴볼 필요가 있었다.
이 책은 전체적으로 다음과 같이 크게 4가지 영역으로 나눠서 책의 내용을 설명하고 있다.
수학적 최적화 입문
선형 계획 (Linear Programming)
비선형 계획 (Non-Linear Programming)
정수 계획과 조합 최적법 (Integer Programming & Combinational Optimization)
보통 수학적 최적화이라고 하면 언급되는 연속 최적화 문제와 조합 최적화 문제에 대한 내용이 담겨져 있으며, 각 주제별로 배우고 싶은 독자도 입문 파트에 소개되어 있는 패스대로 책을 살펴보면 전반적인 최적화 내용을 살펴볼 수 있다. 이 책이 좋은 점은 정의와 정리의 내용을 뒷바침할 수 있는 다양한 예시들이 제공되는 점이고, 각 장별 마지막에 제공되는 연습문제에도 해설이 달려있어, 내용 복습에 도움이 될 수 있다는 것이다. 특히 비교적 최근에 많이 다뤄지는 조합최적법에서는 아마 알고리즘에 대해서 공부한 사람이라면 한번쯤 들어봤을 법한 동적 계획법이나 외판원 문제에 대한 수학적 해석법이 담겨있어서, 단순히 코드로 문제 해결을 구현하기 보다는 문제에 대한 원론적인 이해를 해보려는 사람한테는 지식을 넓게 확장시킬 수 있지 않을까 생각된다.
책의 원서가 일본어로 되어있다보니, 책에서 번역된 용어들이 한문에서 읽어온 것처럼 부자연스러운 부분은 살짝 있다. 서두에서도 언급했다시피 나는 최적화 수업을 들어본 적이 없기 때문에 바르게 쓰이는 용어에 대해서는 잘 알지 못하나 duality같은 용어를 쌍대로 표현하고, 어떤 용어는 영어 그대로 풀어쓴 부분도 있어서 좀 어색한 느낌이 있었다. 내용과는 별개인 것이긴 하지만...
사실 최적화 이론에 대해서 공개된 강의나 책이 많지 않기 때문에 일반적인 사람이 단순히 호기심만 가지고 접근하기에는 너무 심화된 주제이긴 하다. 나같은 경우에도 찾다찾다 Stanford에서 공개한 Convex Optimization 강의(Boyd 교수가 진행한 내용인데, 무료로 수강할 수 있다.)를 통해서 대략적인 내용만 파악하는 정도였었고, 내용 자체가 너무 어려웠다.
그래도 어느 정도 입문부터 최적화에 활용할 수 있는 알고리즘이나 도구, 예시에 대한 소개가 곁들여진 책이 나와서 옆에 두고 볼 만한 책이라 생각한다. 뭔가 실무에 바로 적용할 수 있는 마법과 같은 책이 아니지만, 책에서 소개된 이론에 대한 명확한 이해가 이뤄진다면, 최적화가 필요한 다른 분야에도 쉽게 적용할 수 있지 않을까 싶다.
한빛미디어에서 우메타니 슌지(현재 오사카대학교 교수 재직, 수학적 최적화 모델 및 알고리즘 구현 문제 연구중)가 집필한 "제대로 배우는 수학적 최적화"라는 책이 출간되었다. 수학적 최적화라는 개념 자체가 꽤나 다양한 영역에서 다양한 문제로 나타나고 있기 때문에, 베이직한 개념을 숙지해두고, 여러 기법들을 다 알진 못하더라도, 짧게라도 키워드 등으로 기억해두면, 앞으로 실무에서 다양한 문제를 푸는 중요한 Key가 될 수 있을 것 같기 때문에 이 책을 읽게 되었다.
이 책에서 말하는 수학적 최적화란 아래와 같다.
주어진 제약조건 아래 목적 함숫값을 최소(또는 최대)로 만드는 최적화 문제를 이용하여 현실 사회에서 의사결정이나 문제 해결을 실현하는 수단이다.
수학적 최적화 절차는 현실 문제를 최적화 문제로 정식화하고, 이 최적화 문제는 상수, 변수, 제약조건, 목적함수 라는 요소로 이루어져있다. 그 다음 알고리즘을 이용하여 솔루션을 구하게 되면 계산결과를 분석 및 검증하여 최적화 문제와 알고리즘을 재검토 하는 과정을 반복적으로 거쳐 해결책이 도출된다.
수학적 최적화 개념은 이 책만으로는 모든 범위를 다룰 수 없을 만큼 General 한 분야이기 때문에, 이 책에서는 그래도 최대한 가능한 많은 최적화 문제와 알고리즘을 소개해두었으며, 수학적 최적화에 대해 처음 접하는 사람들이라면 충분한 시간을 들이라고 조언해주고 있었다. 왜냐하면 이 책은 알고리즘과 데이터 구조, 미적분, 선형대수의 기본적인 지식을 전제로 하기 때문이다!
현실 문제에서 수학적 최적화를 이용하여 문제를 해결하기 위해서는 그 문제를 최적화 문제로 모델링 하기 위해 구체적인 기법이나 효율적인 알고리즘으로 알려져 있는 최적화 문제를 다양하게 알아야 한다. 실제로 현실에서 주어지는 문제를 최적화 문제로 모델링 할 때 기존의 최적화 문제를 잘 변형하거나 조합해야한다고 한다.
이 책의 목차는 간략하게 언급하면 아래와 같다.
1. 수학적 최적화 입문
2. 선형 계획
3. 비선형 계획
4. 정수 계획과 조합 최적화
Appendix 연습문제 정답 및 해설
책 도입부에서는 수학적 최적화 개념과 절차를 간단한 야채주스 문제로 설명하고 있었다. 수학적 최적화에서 "최적화 문제를 푼다"라는 표현은 "최적의 솔루션 하나를 구한다"를 의미하기 때문에 여러 최적의 솔루션이 존재할 가능성이 있다. 이러한 모든 최적 솔루션을 구하는 문제를 열거 문제(Enumeration Problem)라고 하며, 최적화 문제에 반드시 최적 솔루션이 존재한다고 단정할 수는 없다. 최적화 문제는 다음 네 가지로 분류된다.
1. 실행 불능 : 제약조건을 만족하는 솔루션이 존재하지 않음 (실행 가능 영역이 공집합임)
2. 한계가 없음(유한하지 않음) : 목적 함숫값을 한없이 개선할 수 있으므로 최적 솔루션이 존재하지 않음
3. 한계가 있지만(유한함) 최적 솔루션이 존재하지 않음 : 목적 함숫값은 유한하지만 최적 솔루션이 존재하지 않음
4. 최적 솔루션이 존재함 : 유한한 최적값과 최적 솔루션이 존재함
이 책에서 소개할 최적화 문제와 알고리즘은 다음과 같다. 처음 이 책을 접하는 사람들이 순서와 공부 방향을 설정하기 위해 보면 좋을 것 같다. 개인적인 생각이지만, 현직 교수가 집필해서 그런지 딱 커리큘럼을 짜서 공부하려는 학생 또는 교수를 위한 책인게 느껴졌다(굿). 마지막에 연습문제도 있기 때문에 대학에서 수학적 최적화를 다루는 과목에서 교재로 로 쓰면 좋을 것 같은 책이다.
또한 앞서 설명했듯 이 책은 선형대수와 미적분, 그리고 기본적인 수학 알고리즘에 대한 이해가 있어야 책을 볼 수 있다. 그 만큼 벡터, 미분, 행렬, 부등식 등 정말 많은 수식들과 증명 문제들이 다수 포함되어 있기에 조금 어려울 순 있다 ^^;; 하지만 그 만큼 많은 내용을 담아냈고, 아무래도 최적화 문제는 실 생활에서 가장 많이 사용 될 수 있기에 사례들을 문제 마다 수록해 놓아서 이해하는데 어려움은 없었던 책이다.
" 오페라 하우스는 본래 700만 호주달러로 1963년초에 문을 열 예정이었으나 10년 뒤에 1400만 호주달러로 열었다.
나심 탈레브 <블랙스완> "
나심 탈레브의 설명에 따르면, "인식론적 오만"은 알고 있는 것은 "과대평가"하고, 불확실성은 "과소평가"하게 만든다는 겁니다. 그래서 호주 오페라 하우스에 대한 계획은 10년이나 뒤틀어졌고, 책정된 예산은 두배가 더 필요하게 되었던 거죠. <보이지 않는 고릴라>에서 저자들은 본래 설계대로 공사했었다면 4500만 호주달러가 추가로 필요했을거라고 설명해주고 있죠.
다시말해 무언가를 잘 이해하고 파악하고 있다는 인간의 착각은 엄청난 대참사를 일으킨다는 걸 알 수 있습니다. <보이지 않는 고릴라>에서 저자들은 사람들에게 농구공을 몇번 패스하는지 세어보라고 지시하고는 농구 팀원들 사이에 고릴라 탈을 쓴 사람이 지나가게 합니다. 어떤 실험에서도 참가자 반정도는 "고릴라"를 보지 못한다고 하네요.
" 1883년 스페인 바르셀로나에서 사그라다 파밀리아 성당의 건축을 지휘한 건축가 안토니 가우디는 1886년 10년 후면 성당이 완공될 것이라고 장담했다. 하지만 이 성당의 완공시점은 그가 죽은 지 꼭 100년 후인 2026년으로 예상된다.
<보이지 않는 고릴라> "
10년후 완공될거라 장담했던, "파밀리아 성당"은 100년이 넘게 걸렸습니다. 그리고 제가 리뷰하고 있는 이 책의 표지에 "파밀리아 성당"의 모습을 담고 있군요. 저자는 이 책의 집필이 한없이 늦어지는 것을 두고, 어떤 학생이 던진 말을 귀담아 들었다가 책의 표지로 썼다고 이야기 하고 있습니다. 수학적 최적화가 필요한 가장 상징적인 사건이었기 때문 아닌가 싶네요.
인간의 "인식론적 오만"은 불가항력적입니다. 아무리 똑똑하고, 유명하고, 이성적인 사람들이라도 빠져나갈 수 없죠. 그래서 이를 극복하기 위한 도구가 필요한데요. 그게 바로 수학이 아닌가 싶습니다. 그리고 이 책은 "인식론적 오만"을 극복할 수 있는 수학적 지식을 제공하고 있습니다. 그러니 이 책이 "사그라다 파밀리아 성당"과 많은 연관이 있는 것 아닐까 싶군요. 책을 집필하는데 파밀리아 성당 처럼 시간이 계속 늦어졌지만, 사실 이 책의 내용은 그런 "인식론적 오만"의 폐해를 막을 수 있는 도구를 제공해주고 있는 셈이니까요.
문제는 책의 분량입니다. 저자는 "저자의 말"에서 6개월에 보기엔 어려운 분량이라고 이야기하고 있거든요. 아마 교제로 사용하려는 목적을 두고 책을 저술했던것 같은데, 학교에서 교제로 쓰려면 한 학기안에 책을 볼 수 있어야 하죠. 하지만, 그 분량을 넘어선다는 지적인듯 합니다.
하지만 저는 시간이 1년 넘게 필요하더라도 이 책을 차근차근 볼 생각입니다. 리뷰를 위해서 내용을 보다 보니, 인공지능이나 데이타분석 관련 책에서 나오는 용어들이 많이 눈에 띄더군요. 대충대충 '그런가보다...' 하는 마음으로 넘어가던 내용들을 제대로 이해할 수 있는 기회가 될 수 있을 테니까요.
앞으로 세상은, 엄청난 데이터가 바다를 이루는 세상이 될 겁니다.
소프트웨어 개발자로서, 또는 어떤 분야의 전문가라 해도... 우리가 아는 것보다 모르는 것이 더 많고, 인식론적 오만에 빠져서 엉뚱한 길로 내달리기 충분한 상황에 내몰리게 되겠죠.
그럴때 우리를 지켜줄 수 있는 무기는 이런 수학적 배경이 아닐까 싶습니다. 개인적으로 수포자로 오랜시간 살아왔는데... 이 책은 시간이 걸려서라도 꼭 이해하고 넘어가야 하는 책이라고 부여잡게 되는 이유입니다.
음 일단 당연하게 들릴 수도 있지만 수학적 지식을 많이 다진 후에 읽어야 한다. 이것을 말하는 이유는 나는 다지지 않은 후에 읽어서 읽을때 고생을 했기 때문이다... 뭐 내가 잘 몰랐지만 읽을 수 있었던 이유는 설명이 자세한건 당연하고 그림이 친절? 하기 때문이다. 또 책을 읽으면서 지루하지 않을까? 라는 생각을 잠시 했었는데 이건 좀 괜한 걱정이였다. 왜냐하면 한번 읽으면 한 챕터를 다 읽기 전까지 내가 많이 읽었다는 사실을 모를정도로 재밌게 읽히기 때문이다. 물론 이해가 완벽하게 다 되는건 아니지만 완벽하게 이해하지 못한 나도 이정도로 재밌어 한다면 완벽하게 이해할 수 있는사람이 읽으면 얼마나 재밌게 느낄지 궁금해졌다. 그래서 수학을 완전 열심히 공부하고 다시 읽어보기로...! 아무튼 자신이 최적화를 배우고 싶은데 재밌으면서 친절한 입문서를 찾고 있다면 이 책이 딱이라고 추천해주고 싶은 책이다.
책의 리뷰에 앞서. 이 책은 어려운 책이다 @_@.. 기본적인 미적분과 선형대수 그리고 데이터 구조와 알고리즘의 유도식 및 점화식 등에 대한 지식 없이 이 책을 접한다면, 상당한 피로를 호소할 수 있다.
따라서 앞서 말한 지식들에 대해서 본인이 충분히 알고 있고, 이를 통해 보다 심화된 지식을 얻고자 하는 의지가 있는 독자 혹은 충분한 인내심을 가지고 반복하여 학습을 할 마음이 있는 독자들에게 권하는 책이다.
이 책은 세상의 현상들을 수학적으로 해석한 책이다. 솔직히 우리가 살고 있는 세상은 수학으로 이뤄진 세상이며, 다만 우리는 이를 가시적으로 보고 이해하기에 세상을 이루는 것은 수학이 아닌 물질 그 자체라고 생각하는 것이리라 생각된다.
딥러닝도 그렇고 우리가 생각하는 뇌의 역치도 그렇고 각 신경들 전달 물질, 나아가 원자와 핵 모두가 물리, 즉 논리로 이루어져 있다. 어느 하나 논리(수학)이 빠지지 않은 것이 없다. 아마도 논리가 없다는 것은 진정한 무일 것이다. 즉 void(null)이 되는 것이다.
아.. 책에 들어가기 전에 사문이 길었다. 이 책은 앞서 말한 것과 같이 세상의 문제들을 수학적으로 표현하여 이를 지해롭게 해결하기 위한 접근법과 해석하는 방법에 대해서 설명하고 있다.
【책의 구성】 '제대로 배우는 수학적 최적화'의 책의 구성은 어떠한가.
이 책은 CONTENTS를 제외한다면 총 4개의 챕터로 구성되어 있으며 연속 최적화 문제, 이산 최적화 문제 두 개의 그룹으로 나누어 책의 내용이 구성되어 있다.
솔직히 연속 최적화 문제는 블로거에게 큰 흥미가 없어서 이산 최적화 문제의 챕터들만 몇 가지 추려 중점적으로 리뷰해 보았다. (그렇다고 연속 최적화 문제가 중요하지 않다는 것은 아니므로 반드시 읽어보시길 권장한다.)
각 챕터의 구성은 소쳅터를 중심으로 해당 알고리즘의 배경을 설명하고, 이에 대한 시간 복잡도와 점화식을 단계?라는 형태로 표현하고 있다. (각 챕터마다 구성이 조금씩 상이하기에 정확히 이러하다고 단정 짓긴 어려운 구조이다.) 또한 수리적 식이 자주 등장하는데 이해하고 보면 그리 어려운 수준은 아니다.(앞서 말한 지식들에 대해서 충분히 알고 있다면 말이다.!) 그렇기에 시간을 들여 차근차근 읽어보면 충분히 이해하고 지식을 얻어 갈수 있는 책이다.
4챕터 : 탐욕 알고리즘
탐욕 알고리즘에 관한 수리적 접근을 설명하고 있다. 일반적으로 전산 학부에서 배우는 탐욕 알고리즘이란. 바로 앞에 있는 최대치를 취하여 최종적으로 가장 높은 이익을 취하는 알고리즘을 의미한다.
하지만 보편적으로는 위의 알고리즘을 이용한 접근이 설루션이 될 수 있지만, 냅색(knapsack) 알고리즘처럼 탐욕 접근법으로 해결을 시도했다간 낭패를 보는 경우도 있다는 것을 명심하도록 하자.
간략하게 여기서 정리한 탐욕 알고리즘의 수리적 조건은 하기와 같다.
초기 설루션의 조건은 하기와 같다. (순수 우리 표현에 따르면 솔루션이 아닌 설루션이 맞다.[책에는 설루션으로 쓰여있음])
- 초기 설루션 x = (0,0,0) t로 한다. (초깃값을 의미. 0으로 배열을 초기화함을 의미한다.)
- 시그마 xi = B를 만족하면 종료한다. ( 즉 사용할 수 있는 최댓값에 달하면 그리드 탐색은 더 이상 수행하지 않음을 의미한다.)
- di(xi)-max dk(xk)를 만족하는 사업 j를 구한다. xj = xj +1로 하고 단계 2로 돌아간다. (즉, 변화량 최대 치의 값을 만족하는 각 값들의 합을 의미함)
이를 통해 해당 알고리즘의 대략적인 수리적 점화/접근 식을 얻을 수 있으며, 이를 수학적으로 추론함으로써 시간 복잡도 역시 어느 정도 예측이 가능해진다.
복잡해 보이지만 알맹이를 이해하면 그리 어렵지? 않은 흐름이다.
4챕터 : 동적 계획법 // 최소 비용 탄성 매칭 문제
앞서 탐욕 알고리즘에 대해서 간략하게 살펴보았다. 그렇다면 당연히 동적 계획법에 대해서도 살펴봐야 하는 것이 알고리즘의 스텝이라면 스텝이라 할 수 있다.
점화식과 수식을 세우는 것도 모든 상황에 따라 다양할 수 있다. 따라서 아래의 예시는 하나의 예시일 뿐임을 사전에 말씀드린다.
- j = n 이면 종료한다. 그렇지 않으면 j = j+1로 한다. (종료 조건과 다음 스텝으로 넘어갈 조건에 대해서 명시한다.)
- f(1, j) = f(1, j-1) + cj로 한다. f(i, j)=min{f(i-1, j-1), f(i-1, j), f(i, j-1)} +cij(i=2, .., m)으로 하고 단계 2로 돌아간다. (실제로 DP Table을 이용한 값을 도출하는 부분이다. 이전 수행했던 값들을 기반으로 현재 최상의 값을 구하는 스텝이라고 생각하면 된다.)
우리가 일반적으로 프로그래밍 대회나 혹은 알고리즘 스터디를 하다 보면 배우는 내용을 수리 식으로 정리한 내용들이다. 보기엔 어려워 보이나 앞서 언급한 것처럼 내용을 알고 보면 이해하기에 그리 어렵지 않음을 알 수 있다.
【 "제대로 배우는 수학적 최적화"를 읽고서…….】
이 책은 수리학에서 사용하는 용어가 많이 등장한다. 굉장히 나에겐 생소했던 부분이기도 하다. 가령 하강 방향이라던가 수렴비라던가 국소 수렴성이라던가 라그랑주 제곱수라는 표현이라든가 굉장히 생소한 용어들이다. 이제껏 전산학을 나름 오래 해 왔으나 한 번도 들어보진 용어들이다. 아마도 수리학 분야에서 사용하는 용어들이나 공식 혹은 정리들이지 않을까 싶다.
전산학도 어찌 보면 수리학에서 시작한 학문이라 할 수 있다. 다만 전산학의 경우 이산수학에 그 기틀을 다지고 있다고 봐도 과언이 아닐 것이다. 그만큼 수학과 전산학은 때려야 땔 수 없는 관계에 있는 것이다.
이번 리뷰에서는 내가 잘 아는 부분을 중심으로 챕터 내용을 요약해 보았다. 다른 부분들도 위와 크게 다르지 않다. 가정을 세우고 가정을 검증하고 가정대로 수행하고 최종적으로 가정을 입증(증명) 하는 과정으로 책의 구성이 이루어져 있다.
다만 확실한 것은 이 책은 한번 읽고 덮는 그런 책은 아니라는 것이다. 내용이 무겁다. 한번 읽어서는 확실히 내 것으로 만들 수 없다. 필자도 서문에서 언급하였듯, 책을 여러 번 숙독하고 회독해야 최종적으로 내 것으로 만들 수 있는 그런 책이다.
그렇기에 꾸준한 마음으로, 한결같은 호기심으로 전산학전 난제와 접근법을 수리적으로 표현하고 해석하여 풀이할 준비가 되어있는 사람들이 이 책으로 공부한다면 틀림없이 많은 것을 얻어 갈 수 있을 것이라 생각된다.
#본 도서는 "한빛미디어 <나는 리뷰어다> 활동을 위해서 책을 제공받아 작성된 서평입니다.
최적화 알고리즘에 대해서 딥하게 알고 싶다!!! 라고 하시는 분들에게 추천 드립니다. 알고리즘에 대해서 수학을 통해서 소개를 하고 있기에 기본적으로 미분/적분, 선형대수, 데이터구조 등에 대해서 알고 있어야 이해하실 수 있습니다. 모든 페이지에 수학공식이 들어가 있으며 각 Chapter가 끝날 때마다 연습문제가 있습니다.
크게 선형계획, 비선형계획, 정수계획 그리고 알고리즘 성능 등을 통한 조합 최적화로 구분해서 수학적 최적화 알고리즘에 대해서 기술하고 있습니다. 책을 읽다 보면 수학적인 부분이 많이 차지하기에 지루하고 힘들 수도 있습니다. 기초를 알아야 알고리즘에 대해서 정확하게 이해할 수 있기에 당연한 것이긴 합니다만 기술한 내용과 관련해서 사용되고 있는 기술 들을 소개하면 읽기도 쉽고 이해를 도울 수 있을 것이라고 생각됩니다.
사실 최적화 알고리즘은 실생활의 많은 곳에서 사용되고 있습니다. 인공지능, 빅데이터 뿐만 아니라 네트워크, 클라우드 등 거의 대부분에서 사용할 수 있는데요. 네트워크라고 한다면 컴퓨터 네트워크 뿐만 아니라 길을 찾을 때 사용하시는 앱이나 네비게이션을 예로 들 수 있습니다.
이러한 사용예를 함께 설명하거나 실제 적용예를 분석하는 방법으로 설명해줬으면 더 좋았을 것 같습니다. 책에서도 이러한 시도가 없어던 것은 아닙니다. 예를 들면 제품 추천 문제 중 하나에서는 대량의 데이터를 이용한 고객의 선호 분석에 대해서 설명하고 있는데 독자가 읽기에 편한 방식이 아니라 수학적인 접근으로서만 설명하고 있습니다.
마지막으로 이 책의 지은이는 우메타니 슌지라는 오사카대학 교수님인데 번역서다 보니 아쉬운 부분들이 보였습니다. 대표적으로 솔루션을 설루션이라고 하거나 음수가 아닌.. 을 비부라고 번역이 되어 있습니다.
수학적 최적화는 주어진 제약조건 하에서 목적 함수값을 최소 또는 최대로 만드는 최적화 문제를 현실 사회에서 의사결정이나 문제 해결을 실현하는 수단이다. 특히 최근 산업이나 학술 영역에서 다양한 문제를 최적화 문제로 모델화하고 이를 수학적으로 풀수 있음을 인식하고 있다. 이미 다양한 최적화 솔루션이 공개되고 있으며, 현실 문제 해결을 위한 유용한 도구로 수학적 최적화 이외의 분야에서도 빠르게 보급되고 있다.
이미 다양한 최적화 솔루션이 나와 있는데 굳이 수학적 최적화를 따로 공부해야 할까? 현실 세계에서 수집된 다양한 데이타에 근거한 최적화 문제를 해결하기 위해서는 보다 효율적인 알고리즘 개발이 필요하다. 따라서 최적화 솔루션을 사용하더라도 자신이 처리해야 할 최적화 문제를 모델링하고 최적화 문제에 대한 기본적인 알고리즘, 그리고 사고방식을 제대로 이해하는 것은 필요하다고 볼 수 있다.
이 책은 알고리즘과 데이타구조, 미적분, 선형 대수 등에 대한 기본 지식을 전제로 하고 있다. 따라서 기본 지식이 부족하다면 최적화 문제를 풀기 위해 제시하는 함수와 그 함수를 풀기 위한 과정을 이해하는 것은 쉽지 않다. 다만 증명과정을 정확히 이해하지 못하더라도 어떤 방법으로 최적화 문제를 푸는지에 대한 감은 익힐 수 있기 때문에 너무 어렵게 접근할 필요는 없을 것 같다.
솔직히 9페이지에 나오는 기호 목록을 보면 과연 이책을 제대로 이해할 수 있을까하는 걱정이 앞서기도 한다. 하지만 1장에 나오는 수학적 최적화 입문을 읽어 보면 이 책에서 할려고 하는 것이 무엇인지 대략 이해할 수 있다. 대표적인 최적화 문제 형태와 그 최적화 문제를 해결하기 위한 알고리즘에 대한 전반적인 부분을 소개한다. 이를 통해 대략적인 방향을 잡을 수 있다.
각 장을 시작하기 전에 그 장에서 설명하고자 하는 것을 간략하게 설명하고 있다. 2장 선형계획에서는 선형 계획 문제의 개념과 선형 계획 문제의 대표 알고리즘인 단체법, 그리고 완화 문제와 쌍대 문제를 설명한다. 3장 비선형 계획에서는 범용적인 알고리즘 개발이 어렵기 때문에 비선형 계획 문제의 특징을 설명하고 제약 없는 최적화 문제와 제약 있는 최적화 문제에 대한 대표적인 알고리즘을 설명한다. 4장 정수 계획과 조합 최적화에서는 산업이나 학술 등 폭넓은 분야에서 현실 문제를 정식화할 수 있는 범용적인 최적화 문제로서 복잡한 계산에 대한 어려움에 기반한 기본적인 사고 방식을 설명한다. 몇몇 특수한 문제에 대한 알고리즘을 설명하고 임의의 문제 사례에 대해 근사 알고리즘과 휴리스틱에 대해 설명하고 있다.
책의 대부분이 수식과 최적화 문제를 해결하기 위한 증명 과정으로 이루어져 있다고 해도 과언이 아니다. 하지만 제시된 최적화 문제는 우리가 일상 생활에서 자주 접하는 문제들로 제시되어 있기 때문에 현실과 무관한 증명이 나열된 것은 아니기 때문에 조금은 더 집중할 수 있는 것 같다.
책의 초반에 저자는 6개월 정도의 진도를 기준으로 학습을 진행하기에는 분량이 너무 많을 수 있다고 언급하고 있다. 나 자신도 증명에 대한 부분은 대부분 이해하지 못하고 넘어간 것 같다. 저자 말대로 여유를 가지고 문제 하나하나에 대한 증명을 천천히 따라가면서 공부하듯이 다시 시작해봐야 할 것 같다.
2021년 9월에 출간된 <제대로 배우는 수학적 최적화>에 대해 소개합니다. 이 책의 부제는 '최적화 모델링부터 알고리즘까지'입니다. '수학적 최적화'는 주어진 제약조건 아래 목적 함숫값을 최소(또는 최대)로 만드는 최적화 문제를 이용하여 현실 사회에서 의사결정이나 문제 해결을 실현하는 수단입니다. 이 책은 수학적 최적화라는 사고방식의 기초를 확실히 익히기 위해 모델링하는 방법과 기본적인 최적화 알고리즘을 다루고 있습니다.
이 책의 저자는 '우메타니 슌지'이며, 일본 오사카대학교 대학원 정보과 교수로 재직 중에 있습니다. 역자는 김모세 님으로 번역에 대해서는 개인적으로 호불호가 있을 것으로 판단합니다.
<제대로 배우는 수학적 최적화>는 420여 페이지로 구성되어 있어 휴대하면서 읽기에 부담스럽지 않습니다. 다만 최근 출시된 한빛미디어 책은 전차책으로도 출간되므로 전자책을 읽을 수 있는 장치를 보유하신 분이라면 전자책으로 만나보는 것도 좋을 것 같습니다.
한빛미디어 평가단에 참가하여 작성한 글이며, 한빛미디어에서 제공해준 책을 읽고 작성했음을 밝힙니다.
이 책의 매력은?
<제대로 배우는 수학적 최적화>는 수학적 베이스(선형대수, 미적분 등)가 탄탄한 분이라면 매력적인 책이라고 느껴질 것이고, 그렇지 않은 분이라면 어려운 책이라고 생각합니다.
이 책은 수학적 최적화에 대한 설명을 시작으로, 선형 계획, 비선형 계획, 정수 계획과 조합 최적화 문제를 다루고 있습니다. 이 책의 장점은 다양한 예제를 활용하여 저자가 전달하고자 하는 메시지를 효과적으로 전달하고 있습니다. 어느 정도 기본 베이스를 내재하고 있는 분들은 이 책을 활용하여 다양한 수학적 최적화 법칙을 이해할 수 있습니다.
이 책에서 아쉬운 점은 너무 수학적인 관점으로 집필(물론 수학을 전공하신 분들이 바라보면 다르게 바라볼 수도 있겠지만…)한 것 같습니다. 제가 CS 전공자라서 그런지는 모르겠지만, 컴퓨터를 활용하여 이 책에서 배운 이론들을 실험할 수 있는 환경을 제공했다면 독자들의 이해도를 조금 더 높여줄 수 있지 않았을까? 라는 생각이 들었습니다.
이 책은 한 번 읽고 끝낼 수 있는 책은 아닙니다. 오랜 시간을 투자해야 하는 책입니다. 이 책에서 배운 지식을 독자의 내재된 지식과 결합하여 다양하게 활용할 수 있도록 시도해 본다면 조금 더 만족도가 높은 책으로 남을 것 같습니다.
마치면서
이 책을 신청할 때부터 '쉬운 책은 아니겠구나라'는 느낌이 들었습니다. <제대로 배우는 수학적 최적화>는 알고리즘과 데이터 구조, 미적분, 선형 대수 등의 기본적인 지식을 보유하고 있어야 합니다. 이 지식이 내재화되어 있지 않다면, 이 책과 함께 하는 시간이 즐겁지 않게 느껴질 수 있습니다. 하지만 이 책은 매력적인 책입니다. 이 책을 읽을 때, 너무 수식에 얽매이지 말고 저자가 이야기하는 문제 해결 방법의 본질에 집중해서 읽는다면, 조금 더 효과적일 것 같습니다.
번역에서의 단어 선택은 조금 아쉬운 부분입니다. 다소 낯선 단어로 말미암아, 읽을 때 불편하게 느껴지는 부분이 있습니다.
매우 어려운 책이었다. 책의 기본적인 내용은 알고리즘을 어떻게하면 수학적으로 최적화할 수 있을지에 대한 예시들과 풀이 방법에 대해 나와있다. 단순히 미적분에 그치지 않고 이산수학 등 꽤 공부를 해야 알 수 있는 내용들이 있어 난해한 부분들이 있었다. 그래도 모든 내용을 못읽을 정도는 아니였고, 정수 계획과 조합 최적화에서 설비 배치 문제 사례 등 해당 분야에서 공부를 한 사람들이라면 이해하기 상대적으로 쉬운 내용들도 있어 다행이다 싶었다.
다른 챕터들의 내용들이 충실할 것으로 예상하지만 기초가 많이 쌓이질 않은 상황에서 크게 보는 건 의미가 없을 듯 하고, 주로 정수 계획과 조립 최적화 위주로 책을 본 것 같다. 최단 경로 문제라던가 할당 문제, 혹은 최소 전역 트리 문제 등 비록 코딩 툴에 대한 내용이 거의 나오질 않음에도, 코딩 테스트를 진행하시는 분들이라면 알고리즘 설계 방법에 대해 알 수 있어 꽤 도움이 될 것으로 예상한다.
다른 챕터에는 매우 큰 범위의 문제를 해결하기 위한, 선형, 비선형 둘 다 포함하여, 솔루션들이 포함되어 있어 구입 후 용도에 맞게 읽으면 좋을 것 같다. 다만 기본 수학적 지식이 부족하다면 이보다 쉬운 책을 읽는 편이 좋을 것으로 보인다.
제목에서부터 `수학`이라는 말이 들어가는 것을 보면 알 수 있듯이 최적화 이론을 공부하기 위해서는 선수 지식들이 필요합니다. 최적화 문제란 간단하게 설명하면 어떤 목적 함수의 결과 값을 최적화(최대화 또는 최소화)하는 솔루션을 찾는 문제입니다. 단순하게 보면 수학 문제로 밖에 안 보이지만 거의 대부분의 머신러닝, 딥러닝 분야에서 쓰입니다. 예를 들어서 Gredient discent, Convex optimization 등이 쓰이죠. 다양한 수학적 지식들과 알고리즘으로 이루어져 있기 때문에 선수 지식들이 꽤 필요한 편이며 대표적으로 선형대수, 대표적인 알고리즘, 자료구조, 미적분 등을 알고 있어야합니다.
전 이 책을 읽기 위한 준비가 됐다고 생각했었는데 전혀 그렇지 않았습니다. 선수지식들을 모두 공부해봤어도 읽는데 어려움이 있었습니다. 처음 이 책을 대충 훑어봤을 때는 수치해석과 비슷하다고 느껴 `비슷한 내용이니 크게 어렵지 않겠지?`라는 생각을 했었습니다. 완전 어리석은 생각이었습니다.
다양한 예시 문제 적용
단순히 수학적인 지식만 설명하는 것이 아닌 수학적 최적화의 사고방식을 알려주기 위해 예시를 들어 `어떻게 하면 최적화 할 수 있을까?`에 대한 답을 알려줍니다. 전 이부분이 이 책의 가장 큰 장점이라고 생각합니다. 어짜피 수많은 이론들을 알아봤자 그걸 이해하지도 못하고, 적용할 수도 없다면 무의미해집니다. 이 책에서는 구체적으로 예시를 들면서 설명해주니 이해하기 쉬웠습니다.
연습문제와 참고문헌
개념만 공부하면 기억에 오래 남지 않는다고 생각해서 수학 책에 연습 문제가 있다는 것이 좋다고 생각합니다. 공부하는 학생 입장에서도 도움이 꽤 되며 이 책은 다른 책들과 다르게 연습문제에 대한 해설도 부록으로 제공해줍니다. 문제를 먼저 풀어보고 해설과 비교해볼 수 있겠죠.
참고문헌도 매 단원이 끝날 때마다 열심히 공부하라고 넣어주십니다. 이 책의 범위가 매우 방대하다는 것을 예상할 수 있죠. 매단원마다 많은 양의 책들을 참고하라고 추천해주시는데 참고문헌이 대부분 일본어 책이라서 조금 부담됩니다. 그래도 영어로 쓰여진 몇몇 책들을 알려주셔서 나중에 필요한 내용들이 있다면 참고하거나 읽어볼 예정입니다.
대상 독자
전 일단 첫번째로 `최적화 이론에 관심 있는 사람`이 읽으셨으면 좋겠습니다. 관심도 없는데 머신러닝, 딥러닝에 관련되어 있다고 해서 공부하시는 건 추천드리지 않습니다. 컴퓨터 공학과 기준으로 학부생이 읽는 것도 별로 추천드리고 싶지는 않습니다. 읽어도 4학년 때 머신러닝 수업을 들으면서 읽어보시고 다른 책으로 먼저 최적화 이론에 대해 공부해보는 것을 추천드립니다.
최적화 지식에 대해 전반적으로 알고 싶으신 분이 읽으셨으면 좋겠습니다. 이 책은 수학적 최적화에 대해 기본 지식을 배우기 위한 책입니다. 결국 입문서라는 거죠. 더 자세히 공부해보고 싶으시다면 이 책에 나와있는 참고문헌의 책들과 같이 읽어보시길 바랍니다.
수학적 최적화는 주어진 제약조건하에서 목적 함숫값을 최소(또는 최대)로 하는 설루션을 구하는 최적화 문제를 말하며, 현실 사회의 의사결정이나 문제를 해결하는 수단입니다. 1장에서는 예시와 함께 수학적 최적화의 개요에 대해 설명합니다.
2장_선형 계획
선형 계획 문제는 가장 기본적인 최적화 문제로, 대규모의 문제 사례를 현실적인 계산 수단으로 푸는 효과적인 알고리즘이 개발되어 있습니다. 선형 계획 문제의 정식화, 선형 계획 문제의 대표적인 알고리즘인 단체법에 대해 알아보고, 수학적 최적화에서 가장 중요한 개념인 쌍대 문제와 완화 문제를 설명합니다.
3장_비선형 계획
비선형 계획 문제는 적용 범위가 매우 넓기 때문에, 다채로운 비선형 계획 문제를 효율적으로 푸는 범용적인 알고리즘 개발은 어렵습니다. 비선형 계획 문제의 정식화, 효율적으로 풀 수 있는 비선형 계획 문제의 특징을 설명한 뒤 제약이 없는 최적화 문제와 제약이 있는 최적화 문제의 대표적인 알고리즘을 설명합니다.
4장_정수 계획과 조합 최적화 문제
선형 계획 문제에서 변수가 정숫값만 갖는 정수 계획 문제는 산업이나 학술 등 폭넓은 분야에서 현실 문제를 정식화할 수 있는 범용적인 최적화 문제 중 하나입니다. 정수 계획 문제의 정식화, 조합 최적화 문제의 어려움을 평가하는 계산 복잡성 이론의 기본적인 사고방식에 대해 알아봅니다. 또한 몇 가지 특수한 정수 계획 문제의 효율적인 알고리즘과 정수 계획 문제의 대표적인 알고리즘인 분기 한정법과 절제 평면법을 설명한 뒤, 임의의 문제를 예로 들어 근사 성능을 보증하며 실행 가능한 설루션을 구하는 근사 알고리즘과 많은 문제 사례에 대해 고품질의 실행 가능한 설루션을 구할 수 있는 국소 탐색 알고리즘 및 메타 휴리스틱에 대해 설명합니다.
[대상 독자]
- 최적화 이론에 관심 있는 학생과 연구원 및 수학적 최적화와 관련 업무에 종사하는 실무자
- 수학 관련 전공자가 아니더라도 인공지능 분야나 기타 여러 산업 분야에서 최적화 알고리즘 적용에 대한 공부를 하고 싶은 독자
[서평]
우메타니 슌지의 “しっかり学ぶ数理最適化 モデルからアルゴリズムまで (ＫＳ情報科学専門書)”작품을 김모세님 께서 번역한 책(제대로 배우는 수학적 최적화)이다.
단체법(심플렉스 법)을 이용한 해법에 대해서 구체적 예를 제시하고 일반적인 솔루션을 위한 방법은 쉽고 좋습니다. 상호 문제, 완화 문제에 대해서 라그랑주 완화 문제 진행도 자연스럽습니다.
별 1개를 뺀 이유 대해서 말하겠습니다. “기본적으로는 좋은 책이라는 전제”입니다.
이책에서는 각 이슈가 예를들어 "이를 XXX이라 한다"라고 말했을 때의 참조 대상이 구체적인 예가 되는 것이 많이 있습니다.(예를 들면 p48의 "여유 변수"는 구체적인 예의 x3, x4, x5를 가리키고 있습니다. 이 직후의 기본 변수 및 해당 변수에 대해서도 정의와 의미 설명이 부족합니다.)
물론 분위기는 알고, 유추할 수도 있습니다. 그러나 수학 서적으로, 이런 용어의 도입과 사용은 이해가 더 희미하게 되므로 어렵다라고 생각합니다.
하지만, 적어도 수학적 최적화만으로도 책을 살 의미가 있다고 생각합니다.
알고리즘과 데이터 구조, 미적분, 선형대수의 선행 지식이 어느 정도 있어야 내용을 이해 할수 있습니다. 이 책에서 알고리즘과 수학적 최적화 모델 및 구현 문제에 대해서 어떻게 해결 해야 하는지 배울수 있습니다. 책의 내용을 완전히 이해하고 연습문제를 풀수 있는 수준까지 된다면 현업에서 해결 해야 할 수학적 모델 최적화를 적용하는데 크게 어려움이 없을것이라 생각합니다.
이 책은 일본교토대학 박사후 과정을 수료한 우메타니가 지은 책이다. 최근에라고 표현하기도 뭐할 정도가 되었지만 머신러닝&딥러닝 AI가 핫하다. 머신러닝&딥러닝과 연관성이 있는 주제가 최적화이다. 그리고 코딩테스트에 알고리즘을 묻는 회사들이 많은 데 그래프이론 등에서 알고리즘 최적화가 관련이 있다. 굳이 비유를 하자면 더하기와 곱하기의 관계 또는 곱하기연산과 shift연산 정도의 관계로 이해할 수 있다.
이 책의 장점은 기초적인 내용을 방대하게 다루고 있다. 기초라고 하지만 읽다보면 수면제 대용으로 쓰기 적당할 정도의 난이도가 있다. 천천히 읽으면 쉽지만 빠르게 읽으면 무슨소리인지 모를 수준이다. 또 다른 장점은 실생활에 또는 산업계에 실제로 있을 만한 문제들에 대한 예시가 한글로 친절하게 자세히 번역되어 굉장히 많이 언급되고 정리 복습 및 연습문제와 참고자료가 친절하게 있다.
이 책의 단점은 기본 선형대수를 모르면 읽기가 어렵고 일본어로 되어 있는 책을 번역하다보니 일본식 표기법(솔루션-->설루션, ??? --> 생, 방향성이 있는 --> 유향 or 유행, 근원 --> 기저, 음수가 아닌 --> 비부, 규제화 --> 정칙화, 공식화 --> 정식화...)이라 약간 어색하고 참고자료에 소개된 자료가 일본어 책이 많고 책이 얇지 않아 들고 다니기가 약간 부담이 된다.
이 책을 읽기 전에 필요한 선수지식은 수학기호와 선형대수와 유명한 수학 용어 & 정리 (예를 들면 라그랑주, 헤시안 행렬 ...) 등이고 경영학이나 경제학 등을 알고 있으면 책을 더 재미있게 읽을 수 있다.
대학교 기초 교재로 활용하면 좋을 만한 책인데 약간 아쉬운 점은 실습용코드가 없다는 점과 너무 많은 이론들에 대한 절대진리표 같은 최종 정리가 있으면 좋겠다
이 책은 경영, 경제, 공업수학등에서 배우는 최적화 문제와 관련된 이야기를 다루고 있는데 저자인 우메타니 슌지는 1974년생 정보학 박사로 정보학을 전공하였으며 현재 오사카대학 대학원에서 수학적 최적화 교수로 있으며 수학적 최적화와 알고리즘 운영에 대해 주 관심을 가지고 종사하고 있다 한다.
내용은 전체적으로 미국식 수학기호 나열과 난해한 수식으로 꽉채워진 책이 아니라 우리가 고등학교때 많이, 쉽게 보아온 수학정석 스타일로 서술되어 있어 친숙하고 감성적인 느낌이 드는 책이다.
책은 총 3파트로 1파트 선형계획, 2파트 비선형계획, 3파트 정수계획과 조합최적화로 구성되어 있는데 1파트에선 일반적인 제약조건하 최소, 최대값을 구하기 위한 선형계획법을 시작으로 단체법, 완화 문제, 쌍대정리를 다루고 있다.
2파트에선 비선형 계획중 제약이 없는 최적화 문제와 관련 딥러닝 이해에 필요한 경사하강법, 뉴턴법, 준뉴턴법등을 설명하고 있으며 제약이 있는 최적화문제로 유효 제약법, 페널티 함수법과 배리어 함수법, 확장 라그랑주 함수법을 다루고 있다.
3파트에선 정수계획과 조합 최적화를 주제로 하고 있는데 정수계획에 대한 개념 설명을 시작으로 정수계획문제, 컴퓨터 과학분야에서 주로 배웠던 알고리즘 계산과 복잡도평가, 문제 난이도와 NP, 탐욕 알고리즘, 동적 계획법, 분기 한정법, 절제 평면법, 근사 알고리즘, 국소 탐색 알고리즘, 메타 휴리스틱등을 다룬다.
전체적으로 책을 훑어 본 느낌은 초중급자부터 중급자들이 보기에 좋은 내용으로 보이며 책의 서술이 미국이나 유럽의 저자들이 서술한 책보다 일본, 한국 수학책 느낌을 받게되어 본능적으로 어렵고 꺼리게 되는 수학에 대한 거부감을 줄여주는데 조금이나마 기여를 하는듯 싶다.
다만, 한가지 아쉬운 점은 책 내용 중 수학적 내용을 컴퓨터로 응용해 볼 수 있는 매트랩, 파이썬등의 예제까지 확장 서술되지 않고 이론 수학을 중점으로 다루고 있어 향후 저자가 본 책을 중심으로 컴퓨터 응용 서적을 저술하면 어떨까 하는 생각이다.
어차피 학문 길 특히 수학에는 왕도가 없으므로 무한정 저자의 저술을 기다리기 보다 독자 스스로 시간이 좀 걸리더라도 거북이처럼 엉금엉금 컴퓨테이션을 통해 이론을 컴퓨터화로 실행 하면서 한단계씩 원하는 목적에 다가가는게 아름다운 모습일 것 같다.
