[최적화] Introduction to Optimization - Introduction

 

# 참고 교재 : Introduction to Optimization (4th edition, Wiley, Chong&Zak)

# 참고 수업 : 전자전기공학과 대학원 수업 Introduction to Optimization

 

---

책의 구성

PART1	definitions, notations, and relations from linear algebra, geometry, calculus
PART2	unconstrained optimization problem, various iterative optimization algorithm, least-squares optimization problem
PART3	constrained optimization 중에서 linear programming problem(simplex method, dual linear programming, nonsimplex algorithm)
PART4	nonlinear constrained optimization, multiobjective optimization

키워드를 기억해놨다가, 나중에 정리할 때 이 키워드 중심으로 정리하고자 합니다.

 

이 책의 목적은 학생들에게 최적화 이론과 방법에 대해서 소개하고, 최신 연구에 대해 적용해보는 데에 있다고 합니다. (예를 들면 feedforward neural network에 대해서 다루는 장이 있다.)

 

# 이 책과 강의에서 다루지 못한 것은 convex optimization인데, Stanford University의 Stephen Boyd 교수님이 강의를 하셨다고 해서 일단 링크를 저장!

youtu.be/McLq1hEq3UY

 

---

Introduction

최적화를 할 때는 주로 최대, 최소값을 구하는 문제에 직면합니다. 이차방정식 수준은 쉽게 최대, 최소를 구할 수 있고, 이차방정식에 더 나아가서 3차, 4차, 5차방정식이 되더라도 미분을 이용해서 일차미분이 0이 되는 지점의 값들을 비교함으로써 구할 수 있습니다.

 

이러한 최적화 문제는 더 확장되면 x,y에 대한 이차방정식까지 확장됩니다. 즉, (x,y)쌍은 벡터라고 볼 수 있습니다. x에 대한 이차방정식은 스칼라 값을 구하는 수준이고, 이제는 벡터 값을 구하는 것으로 확장됩니다.

 

최적화 문제는 주로 real-valued scalar에 대해서 다룹니다. 최적화문제에서는 minimize 문제가 기본적인 형태이며, 최대룰 구하려면 minimize -f(x) (=maximize f(x))로 나타낼 수 있습니다. 우리가 구하고자 하는 벡터 x는 decision variable, search parameter, optimization parameter라고 할 수 있습니다.

 

수업에서 다루지는 않지만 최적화 문제에서 matrix를 구하는 문제도 있습니다. matrix를 구하는 문제의 예시가 위의 그림에 나와있습니다.

 

 

최적화문제는 scalar에서 vector, matrix, sequence, waveform까지 확장될 수 있습니다.

 

 

<최적화 문제의 예시>

Markov decision process는 sequential decision problem에 대한 문제이고 Brachisto chrone problem은 질량이 굴러내려갈 때 그 시간을 최소화하는 길을 찾아내는 문제입니다. 즉, 함수를 최적화하는 문제이다.

(Brachisto chrone problem을 설명한 좋은 글이 있어서 링크 첨부 : suhak.tistory.com/617)

 

 

 

<최적화 문제에서 다루는 범위>

integer로 한정한다면, countably infinite set을 다루는 것이고, real value로 한정하면 uncountably infinite set을 다루는 것입니다.

예시로는 detection문제는 countable set에서 적절한 답을 찾아내는 문제이고, estimation은 무수히 많은 값들 중에서 답을 찾아내는 문제입니다. 특정 sample을 통해 mean을 추정하는 것처럼 말입니다.

 

discrete optimization과 continuous optimization에 대해서 잠깐 언급했는데, continuous는 미분 가능하므로 비교적 간단하지만 discrete는 data의 dimension이 매우 클 경우에 구하기 어렵다고 합니다.

continuous와 discrete를 모두 고려하는 mixed optimization 문제도 있습니다.

 

 

optimization에는 single-objective optimization과 multiple-objective optimization으로 나눌 수 있고,

mutiple-objective 문제일 때는 single solution이 아니라 여러 개의 solution이 존재할 수 있습니다.

 

 

---

p.s. 혹시라도 잘못된 내용이 있다면 알려주시면 감사하겠습니다! 저는 수업을 듣고, 책을 읽으면서 공부하는 내용을 정리하는 학생이라, 다소 부정확한 내용을 적을 수도 있습니다.