In classical optimization problems, parameters are assumed to be fixed. However, most of the real life problems involve uncertainty. In such cases, classical optimization models may be used by fixing the uncertain coefficients with their mean or median value. However, such models are likely to give solutions that have unwanted objective value, or even worse, be infeasible for the true parameter value. In this thesis, we study methods to find risk-averse solutions for optimization problems with objective function uncertainty.
First, we look in to the cardinality constrained approach, which is commonly used in robust optimization. When applied to uncertain constraint coefficients, cardinality constrained uncertainty has advantages in that the robust model can be formulated as a linear model as long as the underlying problem is linear, and it provides theoretical upper bound on probability of its solution being infeasible. However, when applied to uncertain objective coefficients, some of the properties no longer hold and raises other issues like inconsistency of its solutions. We discuss the cause of the issues and state the necessary and sufficient condition to avoid one of the issues. We also suggest a new robust model that does not suffer from the issues, while preserving the merits of using the cardinality constrained uncertainty.
Secondly, we look into the method of using the weighted OWA (WOWA) criterion to two-stage problems as a means to obtain risk-averse robust solutions. The weighted OWA is a function that aggregates a set of values with weights assigned based on the rank and relative importance of each value. We apply the WOWA criterion to two-stage problems, and present decomposition algorithms to solve them. The algorithms are applied to a location-transportation problem with uncertain demands and computational results are presented.
Finally, we propose a new risk measure: weighted averaging of quantiles of expectation (WAQE), an extension of widely used conditional value at risk (CVaR). Under certain assumptions, WAQE is a coherent risk measure and it has close relation with weighted OWA when applied to discrete random variable. We show that a discrete random variable that minimizes WAQE with certain conditions is second order stochastic dominant. Also, we propose a delayed cut generation algorithm that minimizes WAQE in an optimization problem and test its computational performance though experiments.
일반적인 최적화 문제는 모든 계수가 고정되어 있고 변하지 않는다고 가정을 한다. 하지만 현실의 문제들은 불확실성을 내포하고 있는 경우가 대다수이다. 이런 불확실한 환경에서 단순히 평균값이나 중앙값을 이용하여 계수들을 고정시키고 최적화 문제를 풀게 될 경우, 얻은 해법이 실제 값에 따라 매우 안 좋은 목적 값을 가지거나 심지어는 실현불가능 할 수도 있다. 본 학위논문에서는 목적함수에 불확실성이 있는 최적화 문제에서 위험 회피적인 해법들을 찾는 방법들에 대해서 다룬다.
우선, 강건최적화에서 많이 사용되는 개수제한 불확실성 (cardinality constrained uncertainty)에 대 해서 살펴보도록 한다. 개수제한 불확실성은 제약식의 계수들이 불확실한 문제에 사용될 때, 바탕이 되는 문제가 선형계획법 모형으로 표현 될 경우 강건함을 적용한 문제도 선형계획법 문제로 표현이 가능하고, 얻은 해법의 실행불가능성에 대한 이론적인 상한 값을 제공해준다는 장점이 있다. 하지만, 목적함수가 불확실한 문제에 개수제한 불확실성이 사용될 경우 일부 장점들이 사라지며 얻은 해법들의 비일관성 등 여러 문제가 발생하게 된다. 우리는 이런 문제가 발생하는 원인을 분석하고 문제가 발생하지 않는 조건에 대해서 살펴본다. 또한, 언급한 문제점들이 발생하지 않으면서 개수제한 불확실성의 장점들을 보유하는, 목적함수가 불확실한 환경에서의 새로운 강건 모형을 제안한다.
두 번째로, 가중된 정렬 가중 평균화 (weighted ordered weighted averaging) 기준을 사용하여 두 단계 문제 (two-stage problem)에 대한 위험 회피적인 강건 해법을 찾는 방법에 대해 살펴본다. 가중된 정렬 가중 평균화란 어떤 값들의 집합을 값들의 크기의 순서와 각 값들의 상대적 중요도에 따라 가중하여 합하는 함수의 일종이다. 우리는 가중된 정렬 가중 평균화 기준을 불확실성이 있는 두 단계 문제에 적용하고, 이를 효율적으로 푸는 분해 알고리즘 (decomposition algorithm)을 제안한다. 또한, 해당 알고리즘을 수요가 불확실한 입지-수송 문제 (location-transportation problem)에 적용하여 알고리즘의 성능을 살펴본다.
마지막으로, 조건부 위험노출가치 (Conditional Value at Risk)을 확장한 평균값들의 백분위 가중평균 (weighted averaging of quantiles of expectation, WAQE)이라는 새로운 위험 척도 (risk measure)를 제안한다. WAQE는 증가하지 않는 가중 벡터를 사용하는 한 일관된 위험 척도 (coherent risk measure) 이며, 이산확률변수에 이를 적용하게 될 경우 가중된 정렬 가중 평준화 기준과 밀접한 관계를 갖게 된다. 우리는 특정 조건 하에서 WAQE를 최소화하는 이산확률변수는 이차 확률적 지배적임을 보이고, WAQE를 최소화하는 최적화 문제를 효율적으로 풀 수 있는 알고리즘을 제안한다. 마지막으로, 실험을 통해 WAQE 를 최소화하는 해법과 다른 위험척도를 최소화하는 해법을 비교하고, 제안한 알고리즘의 계산적 성능을 확인한다.
