최적화 이론편집자 확인

목적 함수는 최적화 문제에서 최대화 또는 최소화하고자 하는 대상이 되는 함수를 가리킨다. 최적화의 핵심은 주어진 제약 조건 하에서 이 목적 함수의 값을 최대 또는 최소로 만드는 변수의 값을 찾는 것이다. 목적 함수는 비용, 이익, 거리, 에너지, 오차 등 최적화하려는 대상의 척도를 수학적으로 표현한 것으로, 이를 최소화하는 문제를 최소화 문제, 최대화하는 문제를 최대화 문제라고 부른다. 최대화 문제는 목적 함수에 -1을 곱하여 최소화 문제로 쉽게 변환할 수 있다.

목적 함수의 형태에 따라 최적화 문제의 분류와 해법이 달라진다. 예를 들어, 목적 함수와 모든 제약 조건이 변수의 선형 함수로 표현되면 선형 계획법 문제가 되며, 목적 함수나 제약 조건 중 하나라도 비선형이면 비선형 계획법 문제로 분류된다. 또한 목적 함수의 특성에 따라 문제의 난이도가 결정되는데, 볼록 함수를 최소화하는 볼록 최적화 문제는 비교적 효율적으로 전역 최적해를 찾을 수 있는 반면, 비볼록 함수의 경우 국소 최적해에 빠질 위험이 크다.

머신러닝에서는 모델의 예측 오차를 최소화하는 것을 목표로 하며, 이때 목적 함수는 흔히 손실 함수라고 불린다. 경제학 및 금융에서는 수익을 최대화하거나 위험을 최소화하는 함수가 목적 함수가 되며, 공학 설계에서는 구조물의 무게 최소화나 성능 최대화 등이 목적 함수로 설정된다. 이처럼 목적 함수는 다양한 분야의 실질적 문제를 수학적 형식으로 정의하는 출발점이 된다.

제약 조건은 최적화 문제에서 변수가 반드시 만족해야 하는 조건이나 제한을 의미한다. 이는 문제의 실현 가능 영역, 즉 해가 존재할 수 있는 공간의 범위를 정의하는 역할을 한다. 제약 조건은 일반적으로 등식 또는 부등식의 형태로 수학적으로 표현되며, 이를 만족하는 변수의 조합만이 문제의 유효한 후보 해가 될 수 있다. 제약 조건이 없는 문제는 무제약 최적화 문제로 분류된다.

제약 조건은 그 성질에 따라 여러 유형으로 나뉜다. 선형 계획법 문제에서는 모든 제약 조건이 변수들의 선형 등식 또는 부등식으로 이루어진다. 반면 비선형 계획법 문제에서는 하나 이상의 제약 조건이 비선형 함수로 표현된다. 또한, 변수가 정수 값만을 가져야 한다는 조건은 정수 계획법의 핵심 제약이다. 제약 조건은 또한 등식 제약과 부등식 제약으로 구분되며, KKT 조건과 같은 최적성 조건은 이들 제약이 최적해에 미치는 영향을 체계적으로 설명하는 이론적 틀을 제공한다.

실제 응용에서 제약 조건은 자원의 한계, 물리적 법칙, 예산, 시간, 기술적 제한 등을 반영한다. 예를 들어, 공급망 관리에서 창고의 보관 용량은 부등식 제약으로, 모든 수요를 충족시켜야 한다는 조건은 등식 제약으로 모델링될 수 있다. 엔지니어링 설계에서는 재료의 강도나 안전 기준이 중요한 제약 조건이 된다. 따라서 제약 조건을 정확히 정의하고 분석하는 것은 실용적이고 실행 가능한 최적해를 도출하는 데 필수적이다.

변수는 최적화 문제에서 결정되어야 하는 미지의 수량을 의미한다. 이는 최적화 모델의 핵심 구성 요소로, 목적 함수와 제약 조건의 입력값이 된다. 변수는 일반적으로 벡터 형태로 표현되며, 그 각각의 성분은 하나의 결정 요소를 나타낸다. 예를 들어, 공장에서 생산할 제품 A와 B의 수량, 투자 포트폴리오에서 각 자산에 배분할 금액, 또는 기계 학습 모델의 가중치 파라미터 등이 변수에 해당한다.

변수의 특성에 따라 최적화 문제의 유형이 크게 달라진다. 변수가 연속적인 실수 값을 취할 수 있으면 선형 계획법이나 비선형 계획법 문제가 된다. 반면, 변수가 정수 값만을 가져야 하는 경우, 이를 정수 계획법 문제라고 한다. 특히 일부 변수는 정수이고 다른 변수는 실수인 혼합 정수 계획법 문제도 널리 연구된다. 또한 변수가 0 또는 1과 같은 이진 값을 가지는 경우는 주로 조합 최적화 문제에서 등장한다.

변수의 수와 구조는 문제의 복잡도를 결정짓는 주요 요인이다. 변수의 개수가 많아질수록 탐색해야 하는 공간이 기하급수적으로 커져 문제를 푸는 것이 어려워진다. 이에 따라 효율적인 알고리즘 개발이 중요해진다. 또한, 변수들 사이에 특정한 관계나 구조(예: 네트워크 구조, 계층 구조)가 존재할 경우, 이를 활용한 전용 해법이 적용되기도 한다.

해 또는 최적해는 주어진 최적화 문제에서 모든 제약 조건을 만족하는 실현 가능 영역 내에서 목적 함수의 값을 최대화하거나 최소화하는 변수의 값을 의미한다. 최적해를 찾는 것이 최적화 이론의 궁극적인 목표이다.

최적해는 크게 국소 최적해와 전역 최적해로 구분된다. 국소 최적해는 주변의 다른 모든 실현 가능한 해와 비교했을 때 목적 함수 값이 더 좋은(최소화 문제에서는 더 작고, 최대화 문제에서는 더 큰) 해를 말한다. 반면, 전역 최적해는 실현 가능 영역 전체를 고려했을 때 가장 좋은 목적 함수 값을 가지는 해이다. 볼록 최적화 문제에서는 국소 최적해가 곧 전역 최적해가 되지만, 일반적인 비선형 계획법 문제에서는 여러 개의 국소 최적해가 존재할 수 있으며, 그 중 가장 좋은 것을 찾는 것이 훨씬 어려운 과제가 된다.

최적해의 존재성과 유일성은 문제의 특성에 따라 달라진다. 실현 가능 영역이 공집합이 아니고 유계일 경우, 연속 함수인 목적 함수는 최소한 하나의 최적해를 가진다는 보장이 있다. 선형 계획법 문제의 경우, 최적해가 존재한다면 그것은 실현 가능 영역의 꼭짓점(정점) 중 하나에서 찾을 수 있다는 것이 알려져 있다. 정수 계획법이나 조합 최적화 문제에서는 해가 정수 값이나 이산적인 조합으로 제한되므로, 실현 가능 영역이 연속적이지 않아 해를 찾는 방법이 근본적으로 다르다.

최적화 알고리즘은 이러한 최적해를 효율적으로 찾기 위해 개발된다. 단체법은 선형 계획법의 최적해를 찾는 대표적인 알고리즘이며, 경사 하강법은 비선형 문제에서 국소 최적해를 찾는 데 널리 사용된다. 전역 최적화를 위해서는 휴리스틱 알고리즘이나 메타휴리스틱 기법이 종종 적용된다.

선형 계획법은 목적 함수와 모든 제약 조건이 변수에 대한 선형 관계로 표현되는 최적화 문제를 다루는 분야이다. 이는 최적화 이론의 가장 기본적이고 역사가 깊은 부문 중 하나로, 특히 제한된 자원을 가장 효율적으로 배분하는 문제를 해결하는 데 널리 사용된다. 선형 계획법 문제는 일반적으로 특정 목표(예: 이익 최대화 또는 비용 최소화)를 나타내는 선형 목적 함수와, 기술적, 물리적, 시장적 제한을 나타내는 선형 등식 또는 부등식 제약 조건으로 구성된다. 이 문제의 해는 모든 제약 조건을 만족시키면서 목적 함수의 값을 최적화하는 변수들의 값, 즉 최적해를 찾는 것이다.

선형 계획법 문제의 해법으로 가장 유명한 것은 단체법이다. 이 알고리즘은 실현 가능 영역의 꼭짓점들을 체계적으로 탐색하여 최적해를 찾아내는 방법으로, 조지 버나드 댄치그에 의해 개발되었다. 단체법은 이론적으로는 지수 시간 알고리즘이지만, 실제 많은 응용 문제에서 매우 효율적으로 작동한다. 선형 계획법 문제는 그 구조상 최적해가 존재한다면 실현 가능 영역의 경계면 중 하나의 꼭짓점에서 발생한다는 것이 알려져 있으며, 이는 단체법이 효율적인 근거가 된다.

이 분야는 운영 연구와 물류 분야에서 혁신을 일으켰다. 예를 들어, 공급망 관리에서의 운송 비용 최소화, 제조업에서의 원자재 배합 및 생산 계획 수립, 금융에서의 포트폴리오 최적화(위험 제약 하에서 기대 수익 극대화) 등에 광범위하게 적용된다. 또한 네트워크 흐름 문제나 일정 계획 문제 등도 선형 계획법으로 모델링될 수 있다.

선형 계획법의 이론적 기반은 강한 쌍대성 개념으로 보완된다. 모든 선형 계획법 문제(원문제)에는 그에 대응하는 쌍대 문제가 존재하며, 원문제의 최적값과 쌍대 문제의 최적값은 일치한다는 정리가 있다. 이 쌍대성 이론은 최적해에 대한 경제적 해석(예: 섀도우 가격)을 제공할 뿐만 아니라, 내점법과 같은 새로운 알고리즘 개발의 토대가 되었다. 내점법은 실현 가능 영역의 내부를 통해 최적해에 접근하는 방법으로, 대규모 희소 행렬 문제를 해결하는 데 효과적이다.

비선형 계획법은 목적 함수나 제약 조건 중 적어도 하나가 변수에 대해 비선형인 최적화 문제를 다루는 분야이다. 선형 계획법과 달리, 문제의 구조가 더 복잡하고 일반적이어서 해법 또한 다양하며 문제의 특성에 크게 의존한다. 비선형 문제는 공학 설계, 경제 모델링, 머신러닝의 모수 추정 등 현실 세계의 수많은 문제를 표현하는 데 필수적이다.

비선형 계획법 문제는 그 성질에 따라 크게 볼록 최적화 문제와 비볼록 최적화 문제로 나눌 수 있다. 볼록 최적화 문제는 목적 함수가 볼록 함수이고 제약 조건이 정의하는 실현 가능 영역이 볼록 집합인 경우로, 이때 찾은 국소 최적해는 전역 최적해가 보장된다. 반면, 비볼록 문제에서는 여러 개의 국소 최적해가 존재할 수 있어 전역 최적해를 찾는 것이 훨씬 어렵다.

이러한 문제를 풀기 위한 알고리즘은 크게 두 가지 접근법으로 구분된다. 한 가지는 경사 하강법과 같은 1계 또는 2계 도함수 정보를 이용하는 방법이며, 다른 한 가지는 유전 알고리즘, 모의 담금질 기법과 같은 휴리스틱 알고리즘이다. 도함수 기반 방법은 수렴 속도가 빠르지만 초기값에 민감하고 국소 해에 수렴할 위험이 있다. 반면, 휴리스틱 방법은 전역 최적해에 가까운 해를 찾을 가능성이 높지만 계산 비용이 크고 최적성 보장이 없다.

비선형 계획법의 이론적 기반을 제공하는 핵심 개념으로는 국소 최적점에서의 필요 조건을 제시하는 쿤-터커 조건이 있다. 이 조건은 등식 및 부등식 제약을 포함하는 일반적인 비선형 문제에 적용 가능하며, 라그랑주 승수법을 확장한 것이다. 또한, 내점법은 제약 조건이 있는 비선형 문제를 일련의 무제약 문제로 변환하여 효율적으로 해결하는 현대적인 알고리즘 패러다임으로 자리 잡았다.

정수 계획법은 최적화 문제에서 결정 변수 중 일부 또는 전부가 정수 값을 가져야 한다는 제약이 추가된 문제를 다루는 분야이다. 이는 선형 계획법 문제에 정수 조건이 부과된 정수 선형 계획법이 가장 대표적이지만, 목적 함수나 제약 조건이 비선형인 경우도 포함된다. 정수 조건은 제품의 개수, 차량의 대수, 사람의 수 등 불연속적인 의사결정을 모델링할 때 필수적이며, 이로 인해 문제의 복잡도가 크게 증가한다.

정수 계획법 문제는 일반적으로 조합 최적화 문제로 귀결되는 경우가 많다. 대표적인 예로는 물류 네트워크에서의 시설 입지 선정, 작업 순서 스케줄링, 운송 경로 최적화 등이 있다. 이러한 문제들은 변수가 0 또는 1의 값을 갖는 이진 결정을 요구하는 경우가 빈번하며, 이는 특정 선택의 유무(예: 공장 건설 여부, 경로 포함 여부)를 표현하는 데 유용하다.

정수 계획법의 해법은 단체법과 같은 선형 계획법 알고리즘만으로는 부족하며, 다양한 전략이 결합된다. 대표적인 해법으로는 분지 한계법이 있는데, 이는 연속적인 선형 계획법 문제를 풀고, 정수 조건을 만족하지 않는 변수를 기준으로 문제를 분할하여 탐색 공간을 체계적으로 줄여나가는 방법이다. 또한, 휴리스틱 알고리즘이나 메타휴리스틱을 활용하여 실용적인 시간 내에 양질의 해를 찾는 접근법도 널리 사용된다.

이 분야는 운영 연구와 공학 설계의 핵심 도구로, 자원의 효율적 배분과 복잡한 시스템의 설계에 깊이 관여한다. 컴퓨팅 성능의 발전과 알고리즘의 정교화로 그 응용 범위는 인공지능과 머신러닝의 특징 선택, 금융에서의 포트폴리오 최적화에 이르기까지 계속해서 확대되고 있다.

볼록 최적화는 볼록 집합 위에서 정의된 볼록 함수를 최소화하거나 오목 함수를 최대화하는 문제를 다루는 최적화 이론의 중요한 하위 분야이다. 이 문제의 핵심 특징은 국소 최적해가 항상 전역 최적해와 일치한다는 점에 있다. 이는 비선형 계획법의 일반적인 문제에서 국소 최적점이 여러 개 존재할 수 있는 복잡성과 대비되는, 매우 강력한 성질이다. 이러한 수학적 특성 덕분에 볼록 최적화 문제는 비교적 효율적으로 해를 구할 수 있으며, 이론적 분석도 용이하다.

볼록 최적화 문제는 일반적으로 표준형으로 표현된다. 이는 목적 함수로 볼록 함수를 가지며, 제약 조건으로 정의된 실현 가능 영역이 볼록 집합을 이루는 형태를 의미한다. 대표적인 예로는 선형 계획법 문제가 있으며, 이는 목적 함수와 모든 제약 조건이 선형인 특수한 형태의 볼록 최적화 문제로 볼 수 있다. 또한, 2차 계획법이나 반정부호 계획법과 같은 보다 일반적인 형태도 중요한 볼록 최적화 문제의 범주에 속한다.

이 분야의 이론적 기반은 볼록 해석학에 있으며, 최적성의 필요충분조건을 규명하는 쿤-터커 조건이 핵심 도구로 사용된다. 볼록성 가정 하에서는 이 조건이 최적해를 찾는 강력한 기준이 된다. 해법 측면에서는 내점법과 같은 고급 알고리즘이 개발되어 대규모 볼록 문제를 효율적으로 풀 수 있게 되었으며, 이는 연산 연구와 공학 설계에 널리 응용된다.

볼록 최적화는 머신러닝, 신호 처리, 자동 제어, 금융 공학 등 현대 공학 및 과학의 다양한 분야에서 핵심 도구로 자리 잡고 있다. 특히 지지 벡터 머신의 학습 문제나 포트폴리오 최적화 문제 등은 전형적인 볼록 최적화 문제로 공식화되어 해결된다.

조합 최적화는 이산적인 선택 사항들로 구성된 문제를 다루는 최적화 이론의 한 분야이다. 변수들이 연속적인 값을 취하는 다른 분야와 달리, 여기서는 변수가 정수 값을 가지거나 특정한 조합(예: 경로, 할당, 순서) 중 하나를 선택하는 형태를 띤다. 이러한 문제는 종종 유한한 수의 가능한 해를 가지지만, 그 수가 너무 방대하여 모든 경우를 일일이 검토하는 것은 현실적으로 불가능한 경우가 많다.

대표적인 조합 최적화 문제로는 외판원 문제, 배낭 문제, 작업 스케줄링 문제, 최소 비용 신장 트리 문제, 정점 커버 문제 등이 있다. 이러한 문제들은 운영 연구, 물류, 통신 네트워크 설계, 생산 계획 등 다양한 실용적인 분야에서 자연스럽게 등장한다. 예를 들어, 여러 도시를 방문하는 최단 경로를 찾거나, 한정된 자원으로 최대의 가치를 얻는 물품 조합을 선택하는 문제가 여기에 해당한다.

많은 조합 최적화 문제는 계산 복잡도 이론에서 NP-난해 문제로 분류되어, 다항식 시간 내에 최적해를 보장하며 찾는 일반적인 알고리즘이 알려져 있지 않다. 따라서 실제 해법은 근사 알고리즘을 통해 근사해를 구하거나, 메타휴리스틱 알고리즘(예: 담금질 기법, 유전 알고리즘, 개미 집단 최적화)을 적용하여 실용적인 수준의 좋은 해를 탐색하는 방식으로 접근한다. 특정 문제 구조를 활용하는 분기 한정법이나 동적 계획법도 중요한 해법 도구이다.

쿤-터커 조건은 비선형 계획법 문제에서 최적해가 만족해야 하는 1차 필요 조건을 제공하는 중요한 정리이다. 이 조건은 해석학의 라그랑주 승수법을 부등식 제약 조건이 있는 최적화 문제로 일반화한 것으로, 해럴드 쿤과 앨버트 터커의 이름을 따서 명명되었다. 주로 볼록 최적화 문제에서 이 조건은 최적해에 대한 필요충분조건이 된다.

쿤-터커 조건은 목적 함수와 제약 조건 함수가 미분 가능하고, 특정 정규성 조건(예: 슬레이터 조건)을 만족할 때 적용된다. 이 조건은 최적점에서 목적 함수의 기울기가 활성 제약 조건들의 기울기의 음이 아닌 선형 결합으로 표현될 수 있음을 의미한다. 여기서 각 활성 제약 조건에 대응하는 승수(쿤-터커 승수)는 음수가 아니며, 보완성 여유 조건을 만족해야 한다.

이 조건은 이론적 분석뿐만 아니라 실제 알고리즘의 종료 기준으로도 활용된다. 예를 들어, 내점법이나 일부 휴리스틱 알고리즘은 반복 계산을 통해 쿤-터커 조건을 점진적으로 만족시키는 해를 찾아간다. 또한, 머신러닝의 서포트 벡터 머신 모델 학습 문제를 비롯한 다양한 공학 설계 및 경제학 문제의 최적화 공식화에서 핵심적인 역할을 한다.

쿤-터커 조건은 더 일반적인 KKT 조건의 특별한 경우로 이해될 수 있으며, KKT 조건은 등식 제약 조건까지 포함한 문제로 확장된 형태이다. 따라서 쿤-터커 조건은 부등식 제약만 있는 문제에 대한 KKT 조건과 동일하다고 볼 수 있다.

쿤-터커 조건은 제약 조건이 있는 비선형 최적화 문제에서 최적해가 만족해야 하는 1차 필요 조건이다. 이 조건은 라그랑주 승수법을 부등식 제약 조건이 있는 문제로 확장한 것으로, 최적해에서 목적 함수의 기울기와 제약 조건 함수의 기울기 사이에 특정한 관계가 성립함을 보여준다.

이 조건은 이후 카루시, 쿤, 터커의 연구를 거쳐 더욱 일반화되어, 오늘날 널리 알려진 KKT 조건으로 정립되었다. KKT 조건은 쿤-터커 조건에 등식 제약 조건을 포함시켜 일반화한 것으로, 최적해가 만족해야 하는 1차 필요 조건을 완전히 기술한다. 이 조건은 볼록 최적화 문제에서는 최적해에 대한 필요충분조건이 된다.

KKT 조건은 다음과 같은 요소들로 구성된다. 첫째, 정상성 조건으로, 목적 함수와 모든 활성 제약 조건 함수의 기울기가 선형 종속 관계에 있어야 한다. 둘째, 원문제의 제약 조건을 그대로 만족해야 하는 실현가능성 조건이다. 셋째, 보완성 여유 조건으로, 라그랑주 승수와 제약 조건의 값의 곱이 0이 되어야 한다. 마지막으로, 라그랑주 승수에 대한 비음성 조건이 부등식 제약 조건에 대해 요구된다.

이 조건은 비선형 계획법 문제를 분석하고 해법 알고리즘을 설계하는 데 이론적 토대를 제공한다. 특히, 내점법과 같은 현대적인 최적화 알고리즘은 KKT 조건을 만족하는 점을 찾는 과정으로 이해될 수 있다. 또한, 머신러닝에서 서포트 벡터 머신 모델의 학습 문제 등 다양한 공학 및 과학 분야의 최적화 문제 해결에 핵심적으로 적용된다.

단체법은 선형 계획법 문제를 풀기 위한 가장 대표적이고 효율적인 알고리즘이다. 이 방법은 주어진 제약 조건들로 정의된 실현 가능 영역이 볼록 다면체를 이루며, 최적해는 반드시 그 다면체의 꼭짓점(단체법에서는 기저 가능해라고 함) 중 하나에 존재한다는 원리에 기반한다. 알고리즘은 하나의 꼭짓점에서 시작하여 인접한 꼭짓점으로 이동하면서 목적 함수의 값을 지속적으로 개선해 나가며, 더 이상 개선될 수 없는 꼭짓점에 도달하면 그곳이 최적해임을 판정한다.

단체법의 핵심 연산은 행렬 연산, 특히 가우스 소거법을 활용한 피벗 연산이다. 이 과정은 현재의 기저 변수와 비기저 변수를 서로 교체하며 새로운 꼭짓점으로 이동하는 것을 수학적으로 구현한 것이다. 알고리즘의 효율성을 높이기 위해 다양한 피벗 규칙(예: 최대 코스트 계수 규칙)이 개발되었으며, 인공 변수를 도입하는 2단계 단체법이나 큰 M 방법은 초기 실현 가능 기저해를 찾는 데 사용된다.

단체법은 자원 배분, 생산 계획, 운송 문제 등 운영 연구와 경영 과학의 다양한 실제 문제 해결에 널리 적용되어 왔다. 그러나 최악의 경우 알고리즘 수행 시간이 변수의 수에 따라 지수적으로 증가할 수 있다는 이론적 한계가 지적되기도 했다. 이러한 한계를 극복하기 위한 노력의 일환으로 개발된 내점법 등 새로운 알고리즘들이 등장했지만, 단체법은 여전히 많은 상용 최적화 소프트웨어의 핵심 솔버로서 그 실용적 가치를 인정받고 있다.

경사 하강법은 비선형 계획법 문제, 특히 목적 함수가 미분 가능한 경우에 국소 최적해를 찾기 위해 널리 사용되는 반복적 알고리즘이다. 기본 아이디어는 현재 지점에서 목적 함수의 경사도(gradient)를 계산하고, 그 반대 방향으로 조금씩 이동하여 함수값을 점차 감소시키는 것이다. 이는 산에서 내리막 방향으로 걸어 내려가는 것에 비유할 수 있으며, 머신러닝 분야에서 신경망의 손실 함수를 최소화하는 모델 파라미터를 학습하는 데 핵심적으로 활용된다.

알고리즘의 핵심 매개변수는 학습률이다. 이는 각 반복에서 경사의 반대 방향으로 얼마나 큰 걸음을 내딛을지를 결정하는 값이다. 학습률이 너무 크면 최적점을 지나쳐 발산할 수 있고, 너무 작으면 수렴 속도가 매우 느려지거나 지역 최소점에 갇힐 수 있다. 이를 보완하기 위해 모멘텀, AdaGrad, Adam과 같은 다양한 변형 알고리즘이 개발되어 수렴 속도와 안정성을 개선하고 있다.

경사 하강법은 구현이 비교적 간단하고 대규모 데이터셋에 적용 가능하다는 장점이 있지만, 일반적으로 볼록 함수가 아닌 경우 국소 최적해에 수렴할 위험이 있으며, 전역 최적해를 보장하지는 않는다. 또한 목적 함수의 형태에 따라 정상점에 머무를 수도 있다. 이러한 한계에도 불구하고, 딥러닝과 데이터 과학을 비롯한 다양한 공학 및 과학 분야에서 가장 기본적이고 필수적인 최적화 도구로 자리 잡고 있다.

내점법은 제약 조건이 있는 최적화 문제를 푸는 알고리즘 계열로, 특히 볼록 최적화 문제에 효과적으로 적용된다. 이 방법의 핵심 아이디어는 최적해를 찾는 탐색 경로가 항상 문제의 실현 가능 영역의 내부에 머물도록 하는 것이다. 이를 위해 제약 조건을 명시적으로 다루기보다는, 목적 함수에 '벌칙 함수' 또는 '장벽 함수'를 추가하여 제약 조건의 경계 근처에서 함수 값이 급격히 증가하도록 만들어 자연스럽게 해가 영역 내부로 유도되게 한다.

주요 내점법에는 장벽법과 원-쌍대 내점법이 있다. 장벽법은 로그 장벽 함수와 같은 함수를 사용하여 제약 조건의 경계를 접근 불가능한 장벽으로 만든다. 원-쌍대 내점법은 더 정교한 방법으로, 원 문제와 쌍대 문제를 동시에 고려하며 중앙 경로를 따라 해를 찾아간다. 이 방법들은 선형 계획법과 2차 계획법, 반정부호 계획법 등 다양한 볼록 최적화 문제를 해결하는 데 널리 사용된다.

내점법의 가장 큰 장점은 다항 시간 안에 전역 최적해를 찾을 수 있다는 이론적 보장을 가지며, 실제로 대규모 선형 계획법 문제를 풀 때 단체법보다 훨씬 빠른 성능을 보이는 경우가 많다. 이로 인해 현대의 최적화 소프트웨어와 솔버의 핵심 알고리즘으로 자리 잡았다. 또한, 머신러닝의 서포트 벡터 머신 학습이나 공학 설계의 최적 제어 문제 등에도 응용된다.

이러한 방법들은 제약 조건을 직접 처리하는 활성 집합법과는 달리, 모든 반복에서 실현 가능한 내부 점을 유지하며 점진적으로 최적해에 수렴한다는 공통점을 가진다.

휴리스틱 알고리즘은 최적화 문제, 특히 정수 계획법이나 조합 최적화와 같이 해 공간이 매우 크거나 복잡하여 정확한 최적해를 구하는 데 필요한 계산 시간이 현실적으로 불가능한 문제를 다룰 때 사용된다. 이 방법들은 수학적으로 엄밀한 최적성을 보장하지는 않지만, 합리적인 시간 내에 실용적으로 우수한 해, 즉 근사 최적해를 찾는 데 초점을 맞춘다. 전역 최적해를 찾는 것이 목표이지만, 계산의 복잡도로 인해 국소 최적해에 머무를 위험이 큰 문제들에 널리 적용된다.

이러한 알고리즘의 대표적인 예로는 담금질 기법, 유전 알고리즘, 개미 집단 최적화, 타부 탐색 등이 있다. 예를 들어, 유전 알고리즘은 자연선택과 유전학의 원리를 모방하여 해를 염색체로 표현하고, 선택, 교차, 변이 연산을 반복하며 해를 진화시킨다. 담금질 기법은 금속 재료의 담금질 과정에서 영감을 얻어, 초기에는 비교적 나쁜 해로의 이동도 허용하다가 점차 그 확률을 줄여가며 국소 최적해에 갇히는 것을 방지하는 전략을 사용한다.

이들 방법은 물류 및 운송 분야의 차량 경로 문제, 생산 일정 계획, 통신 네트워크 설계, 인공지능 게임 전략 탐색 등 다양한 분야에서 성공적으로 활용되고 있다. 머신러닝의 하이퍼파라미터 튜닝이나 신경망 구조 탐색과 같은 문제에서도 휴리스틱 기법이 중요한 도구로 자리 잡고 있다.

최적화 이론은 공학 설계 분야에서 설계 변수들을 체계적으로 조정하여 성능, 효율, 비용, 안전성 등을 극대화하거나 최소화하는 핵심 도구로 활용된다. 공학자는 설계 문제를 수학적 모델로 정의하는데, 여기서 최소화 또는 최대화하려는 목표(예: 무게, 응력, 열 손실, 제조 비용)는 목적 함수로, 반드시 지켜야 하는 물리적 법칙이나 규격(예: 강도 한계, 공간 제약, 예산)은 제약 조건으로 표현된다. 이렇게 형성된 최적화 문제를 풀어 얻은 최적해는 설계자의 직관과 경험만으로는 도달하기 어려운 우수한 설계안을 제공한다.

구체적인 응용은 매우 다양하다. 항공우주공학에서는 항공기나 로켓의 형상을 설계하여 항력을 최소화하거나 추력을 최대화하는 데 비선형 계획법이 사용된다. 토목공학 및 구조공학에서는 교량, 빌딩과 같은 구조물의 부재 단면을 설계하여 전체 무게를 최소화하면서도 하중을 견딜 수 있도록 하는 문제를 풀기 위해, 종종 볼록 최적화나 정수 계획법이 적용된다. 전자공학에서는 집적회로의 배치와 배선을 최적화하여 면적을 줄이고 신호 지연을 최소화하는 조합 최적화 문제가 중요한 과제이다.

또한, 자동차 공학에서는 연비 향상과 배기 가스 저감을 위한 엔진 제어 매개변수 최적화, 로봇공학에서는 에너지 소비 최소화를 위한 경로 계획, 재료공학에서는 원하는 물성을 갖는 합금의 성분 비율 결정 등 거의 모든 공학 분야에서 최적화 기법이 깊이 관여한다. 이러한 최적화 과정은 컴퓨터 시뮬레이션과 결합되어, 실제 제작에 들어가기 전에 수많은 가상 설계 후보 중에서 가장 효율적인 해를 도출하는 디지털 프로토타이핑의 핵심을 이룬다.

경제학 및 금융 분야는 최적화 이론의 가장 오래되고 중요한 응용 분야 중 하나이다. 경제학의 핵심 과제인 한정된 자원을 효율적으로 배분하는 문제는 본질적으로 최적화 문제로 모델링된다. 예를 들어, 기업의 이윤 극대화, 소비자의 효용 극대화, 정부의 사회후생 최대화 등은 모두 주어진 예산이나 기술적 제약 하에서 목적 함수를 최대화하는 문제로 표현된다. 이러한 모델링을 통해 경제 주체의 합리적 선택 행동을 체계적으로 분석할 수 있다.

금융 분야에서는 포트폴리오 이론이 대표적인 최적화 응용 사례이다. 해리 마코위츠의 현대 포트폴리오 이론은 투자자에게 주어진 위험 수준에서 기대 수익률을 최대화하거나, 목표 수익률을 달성하면서 위험을 최소화하는 최적의 자산 배분 포트폴리오를 찾는 방법을 제시한다. 이 문제는 일반적으로 2차 계획법이라는 비선형 최적화 기법을 사용하여 해결된다. 또한, 옵션 가격 결정, 리스크 관리, 알고리즘 트레이딩 전략 수립 등에도 다양한 최적화 기법이 활용된다.

이처럼 최적화 이론은 경제 및 금융 시스템의 정량적 분석과 의사결정을 위한 강력한 수학적 도구를 제공한다. 복잡한 시장 환경과 다양한 제약 조건 하에서 최선의 결정을 내리기 위해 이론과 실무 모두에서 지속적으로 발전하고 적용되고 있다.

머신러닝은 최적화 이론의 핵심 응용 분야 중 하나이다. 머신러닝 모델의 학습 과정은 본질적으로 주어진 데이터에 대해 모델의 예측 오차를 최소화하거나 가능도를 최대화하는 매개변수를 찾는 최적화 문제로 정의된다. 이때 최소화 또는 최대화하려는 함수는 손실 함수 또는 목적 함수라 불리며, 모델의 매개변수는 최적화의 변수에 해당한다.

머신러닝에서 널리 사용되는 경사 하강법은 비선형 계획법에 기반한 대표적인 최적화 알고리즘이다. 이 방법은 목적 함수의 기울기를 계산하여 매개변수를 반복적으로 업데이트하며 국소 최적해를 찾아간다. 신경망과 같은 복잡한 모델에서는 역전파 알고리즘을 통해 효율적으로 기울기를 계산한다. 또한, 정규화 항을 목적 함수에 추가하는 것은 모델의 과적합을 방지하기 위한 제약 조건의 역할을 한다.

고차원의 대규모 데이터를 다루는 현대 머신러닝에서는 확률적 경사 하강법이나 Adam과 같은 고급 최적화 기법이 필수적이다. 지도 학습뿐만 아니라 강화 학습에서도 정책의 기대 보상을 최대화하는 문제는 동적 계획법을 포함한 최적화 프레임워크로 접근된다. 따라서 최적화 이론은 머신러닝 모델의 성능과 효율성을 결정하는 수학적 기초를 제공한다.

최적화 이론은 물류 및 운영 연구 분야에서 자원의 효율적 배분과 시스템 운영의 최적화를 위한 핵심 도구로 널리 활용된다. 이 분야에서는 제한된 자원, 시간, 비용 하에서 최대의 성과를 내거나 최소의 비용을 달성하는 문제를 수학적으로 모델링하고 해결하는 데 초점을 맞춘다. 대표적인 응용으로는 공급망 관리, 운송 네트워크 설계, 창고 위치 선정, 재고 관리, 생산 계획 등이 있다.

이러한 문제들은 주로 선형 계획법이나 정수 계획법을 통해 모델링된다. 예를 들어, 여러 공장에서 여러 소매점으로 상품을 운송할 때 총 운송 비용을 최소화하는 문제는 고전적인 운송 문제로, 선형 계획법으로 풀 수 있다. 반면, 창고를 세울지 말지와 같은 이산적인 의사결정이 포함된 설비 입지 문제는 정수 계획법을 적용해야 한다.

복잡하고 대규모의 실세계 문제, 특히 조합 최적화 문제를 해결하기 위해 휴리스틱 알고리즘이나 메타휴리스틱이 많이 사용된다. 담금질 기법, 유전 알고리즘, 개미 집단 최적화 등의 방법은 전역 최적해에 가까운 우수한 해를 합리적인 시간 내에 찾는 데 기여한다. 이를 통해 물류 센터의 내부 작업 계획이나 대도시의 실시간 교통 정보를 반영한 배송 경로 최적화와 같은 동적이고 복잡한 문제를 처리할 수 있다.