강력한 최적화

견실한 최적화는 문제 자체 및/또는 그 해결책의 매개변수 값의 결정론적 변동성으로 나타낼 수 있는 불확실성에 대해 일정한 견실한 척도를 추구하는 최적화 문제를 다루는 최적화 이론의 분야다.

역사

견실한 최적화의 기원은 1950년대 근대적 의사결정 이론의 확립과 최악의 경우 분석과 월드의 맥시민 모델을 심각한 불확실성 치료를 위한 도구로 사용한 것으로 거슬러 올라간다.그것은 1970년대에 몇몇 과학과 기술 분야에서 평행한 발전을 이루면서 그 자체의 규율이 되었다.수년에 걸쳐 통계에 적용되어 왔지만, 운용 연구,^[1] 전기 공학,^[2][3] 제어 이론,^[4] 금융,^[5] 포트폴리오 관리^[6] 물류,^[7] 제조 공학,^[8] 화학 공학,^[9] 의학,^[10] 컴퓨터 과학에도 적용되어 왔다.엔지니어링 문제에서 이러한 공식은 종종 "Robust Design Optimization", RDO 또는 "Relability Based Design Optimization", RBDO라는 이름을 사용한다.

예 1

다음 선형 프로그래밍 문제를 고려하십시오.

${\displaystyle \max _{x,y}\{3x+2y\}\\mathrm {subject\ to}\x,y\geq 0;cx+dy\leq 10,\forall (c,d)\in P}$

여기서 $P{\displaystyle }$ ${\displaystyle P}$은(는) $R{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$ ${\$의 지정된 하위 집합이다$.$

이것을 '최적화' 문제로 만드는 것은 ${\displaystyle \mathrm{제약조건}}$의 $\forall {\displaystyle \mathrm{}}$(${\displaystyle c}$, ${\displaystyle d}$) ${\displaystyle \in }$ P ${\displaystyle \forall (c,d)\in P}$ 조항이다$$.Its implication is that for a pair ${\displaystyle (x,y)}$ to be admissible, the constraint ${\displaystyle cx+dy\leq 10}$ must be satisfied by the worst ${\displaystyle (c,d)\in P}$ pertaining to ${\displaystyle (x,y)}$, namely the pair ${\displaystyle (c,$$d)\$$p$}의 지정된 값$($$x$, y${\displaystyle }$)에 대해$$ $c{\displaystyle }$ ${\displaystyle x}$+ ${\displaystyle d}$ ${\displaystyle y}$ ${\$$displaystyle$$cx+dy$$}$의 값을 최대화하는$$ P$}.$

매개변수 공간 $P{\displaystyle }$ ${\displaystyle P}$이(가) 유한한 경우(정확하게 많은 요소로 구성됨) 이 강력한 최적화 문제 자체는 선형 프로그래밍 문제다. 각 $({\displaystyle c}$, ${\displaystyle d}$) ${\displaystyle \in }$ P ${\d$ 스타일$(c,d)\}$에 대해 선형 제약 $조건{\displaystyle }$ ${\displaystyle c}$ +${\displaystyle d}$ y${\displaystyle y}$ $[\d$ 스타일 $cx+dyleq 10}$이 있다$$$.$

$P{\displaystyle }$ ${\displaystyle P}$이(가) 유한 집합이 아니라면$$ 이 문제는 선형 반무한 프로그래밍 문제, 즉 결정 변수가 매우 많고 제약 조건이 무한히 많은 선형 프로그래밍 문제다.

분류

강력한 최적화 문제/모델에는 여러 분류 기준이 있다.특히, 강건성의 로컬 모델과 글로벌 모델을 다루는 문제와 강건성의 확률론적 모델과 비확률론적 모델을 구별할 수 있다.현대의 강력한 최적화는 주로 최악의 경우 지향적인 건전성의 비확률론적 모델을 다루며, 따라서 일반적으로 Wald's maximin 모델을 배치한다.

국부 강건성

매개변수의 공칭값에서 작은 동요에 대해 강건성을 추구하는 경우가 있다.국부 강건성의 매우 인기 있는 모델은 안정성 모델의 반지름이다.

${\displaystyle {\hat {\rho}}(x,{\hat {u}):=\max _{\rho \geq 0}\\{\rho :u\in S(x),\all u\in B(\rho ,{\hat {u})\}\}}$

where ${\displaystyle {\hat {u}}}$ denotes the nominal value of the parameter, ${\displaystyle B(\rho ,{\hat {u}})}$ denotes a ball of radius ${\displaystyle \rho }$ centered at ${\displaystyle {\hat {u}}}$ and ${\displaystyle S(x)}$ denotes the set of values of ${\displaystyle u}$$$결정 $x{\displaystyle }$ ${\displaystyle x}$과$($와) 관련된 주어진 안정성/성능 조건을 만족하는$$ ${\displaystyle u}.$

즉, 결정 $x{\displaystyle }$ ${\displaystyle x}$의 강건성(안정성의 반지름)은${\displaystyle \stackrel{}{}}$^ ${\$u}}}을(를) 중심으로 한 가장 큰 공의 반지름이며, 이 모든$$ 요소가 x ${\displaysty x}$에 부과된 안정성 요건을 충족한다$.$사진은 다음과 같다.

${\displaystyle \mathrm{여기}}$서 직사각형 $U{\displaystyle (}$x ) ${\displaystyle U(x)}$은 $결정{\displaystyle }$ x ${\displaystyle x}$과(와) 연관된$$ 모든 값 $u{\displaystyle }$ ${\displaystyle u}$의 집합을 나타낸다$$$.$

글로벌 강건성

단순하고 추상적인 강력한 최적화 문제 고려

${\displaystyle \max _{x\in X}\{f(x):g(x,u)\leq b,\forall u\in U\}}}$

여기서 $U{\displaystyle }$ ${\displaystyle U}$은(는) 고려 중인$u{\displaystyle }$ {\$displaystyle u}$의 가능한 모든 값 집합을 의미한다$$.

이는 강건성 제약 조건 $g{\displaystyle }$ (${\displaystyle x}$ ,${\displaystyle u}$) ${\displaystyle \le }$ ${\displaystyle b,}$ ${\displaystyle \mathrm{\forall }}$ ${\displaystyle u}$u ${\displaystyle U}$ ${\$$displaystyle$ $g(x,u)\leq$ b$,\all$ $u\$$in$ U$}$이(가)의 가능한 모든 값을 나타낸다는$$ 점에서 글로벌 강건한 최적화 문제다$.$

어려운 점은 이러한 제약을 충족하는$$ x${\displaystyle }x{\displaystyle }$ ${\displaystyle X}$ ${\displaystyle x\in X}$이(가) 없다는 점에서 이러한 "글로벌" 제약이 너무 까다로울 수 있다는 점이다.그러나 그러한 ${\displaystyle x}$ ${\displaystyle \in }$ X ${\displaystyle$ x$\in X}$이(가) 존재한다고 해도, 인스트에 대한 $X{\displaystyle }$ ${\displaystyle$ x$\$in X$\}$의 다른 결정의 성능을 나타내지 않는$$ 매우 작은 보수가 $발생$하는 $솔루션{\displaystyle }$ X ${\displaystyle \in }$ ${\displaystyle X}$ ${\displaystyle \{\backslash \backslash }$$displaystytle$ $x$$\in X}$을($가)$를 산출한다는 점에서 제약조건이 너무 "보수적일 수 있다.ance, 건전성 제약 조건을 약간만 위반할 뿐 매우 큰 성과급 $f{\displaystyle ({}^{}}$ $){\displaystyle f(x')$을 산출하는$$ $x{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle \in }$ ∈ $∈$ { ${\displaystyle X}$'\$in X}$이 있을 수 있다$.$ 이러한 경우 건전성 제약 조건을 약간 완화하거나 문제의 진술을 수정할 필요가 있을 수 있다.

예 2.

Consider the case where the objective is to satisfy a constraint ${\displaystyle g(x,u)\leq b,}$. where ${\displaystyle x\in X}$ denotes the decision variable and ${\displaystyle u}$ is a parameter whose set of possible values in ${\displaystyle U}$. If there is no ${\displaystyle x\in$$$$g{\displaystyle }$( ${\displaystyle x}$ ,${\displaystyle u}$) ${\displaystyle \le }$ ${\displaystyle b,}$ ${\displaystyle \mathrm{\forall }}$ ${\displaystyle u}$u ${\displaystyle u}$ ${\displaystyle g(x,u)\leq$ b$,\forall u\in$ U$}$과 $같은$ X$}$ 그렇다면 다음과 같은 직관적인 강건성 측정이 그 자체를 암시한다$.$

$[\displaystyle \rho(x):=\max _{Y\subseteq U}\{size(Y):g(x,u)\leq b,\forall u\in Y\\,\x\in X}$

여기서 $s{\displaystyle }$ ${\displaystyle i}$ ${\displaystyle z}$ ${\displaystyle e}$( ${\displaystyle Y}$) ${\displaystyle size(Y)}$은 $집합{\displaystyle }$ Y ${\displaystyle Y}$의 "size"의 적절한 척도를 의미한다$.$ 예를 들어, $U{\displaystyle }$ ${\displaystyle U}$이(가) 유한 집합인 경우 s ${\displaystyle i}$ ${\displaystyle z}$ ${\displaystyle e(Y)}$ ${\displaystystylease$$(Y)$는 집합 $Y}$의 카디널리티로 정의할 수 있다$$$.$

즉, 결정의 견고성은 이 집합의 각$$ $u{\displaystyle }$ ${\$displaystyle $u$$}$에 대해 제약$$ 조건 $g{\displaystyle }$ (${\displaystyle }$x ,${\displaystyle u}$ )${\displaystyle b}$b ${\displaystyle g(x,u)\leq b}$이(가) 충족되는$$ $U{\displaystyle }$ ${\$$displaystyle u$$}$의 가장 큰 부분 집합의 크기라고 할 수 있다.최적의 결정은 강건성이 가장 큰 결정이다.

이는 다음과 같은 강력한 최적화 문제를 산출한다.

${\displaystyle \max _{x\in X,Y\subseteq U}\{size(Y):g(x,u)\leq b,\forall u\in Y\}}$

글로벌 강건성에 대한 이러한 직관적인 개념은 그것이 유도하는 강력한 최적화 문제들이 대개 (항상 해결이) 매우 어렵기 때문에 실무에서 자주 사용되지 않는다.

예 3

강력한 최적화 문제를 고려하십시오.

${\displaystyle z(U):=\max _{x\in X}\\{f(x):g(x,u)\leq b,\fall u\in U\}}}$

여기서 $g{\displaystyle }$ ${\displaystyle g}$은(는) $X{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle U}$ {\$displaystyle X\time$ U$}$의$$실제 값 함수로서, 강건성 제약 조건 $g{\displaystyle }$( x ,${\displaystyle u}$)${\displaystyle b}$ ,${\displaystyle \mathrm{\forall }u}$ U ${\displaystystyle$g$(x,u)\leq$ b$,\all$u$\in$ U$}$이 너무 까다롭기$$ 때문에 이 문제에 대한 실행 가능한 해결책이 없다고 가정한다.

이러한 어려움을 극복하려면, $N{\displaystyle \mathcal{}}$ ${\$을(를) $u{\displaystyle }$ ${\displaystyle u}$의 "정상" 값을 나타내는$$ $U{\displaystyle }$ ${\displaystyle U}$의 비교적 작은 하위 집합으로 하고$$ 다음과$$ 같은 강력한 최적화 문제를 고려하십시오.

${\displaystyle z({\mathcal{N}):=\max _{x\in X}\\{f(x):g(x,u)\leq b,\all u\in {\mathcal{N}\}}}$

$N{\displaystyle \mathcal{}}$ ${\$은(는) $U{\displaystyle }$ ${\displaystyle U}$보다 훨씬 작기 때문에$,$ 최적의 $솔루션$은 U ${\displaystyle U}$의 많은 부분에서 잘 수행되지 않을 수 있으므로$$ $U{\displaystyle }$ ${\displaysty U}$에 대한 $u{\displaystyle }$ ${\displaystysty u}$의 가변성에 대해 견고하지 못할 수 있다$.$

이 어려움을 해결하는 한 가지 방법은 $설정$된 N ${\$ 밖에$$ 있는 $u{\displaystyle }$ ${\displaystyle u$$}$ 값에 대한$$ 제약 조건 $g{\displaystyle }$ ${\displaystyle (x}$, ${\displaystyle u}$) ${\displaystyle g(x,u)\leq$ b$}$을(를)를 제어된 방식으로$$ 완화하여 더 큰 위반이 $N$에서$허용$되도록 하는 것이다$.$$스타일 {\mathcal{N}}$이(가) 증가한다$$.예를 들어, 완화된 강건성 제약 조건을 고려하십시오.

${\displaystyle g(x,u)\leq b+\beta \cdot distit(u,{\mathcal{N})\\\ forall u\in U}$

여기서 $\beta {\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 0}$ ${\displaystyle \beta \geq$ 0$}$은(는) 제어 매개 변수이고 $d{\displaystyle }$ ${\displaystyle i}$ ${\displaystyle t(u\mathcal{}}$, N${\displaystyle }$) ${\displaystyle dist(u,{\$$mathcal{N})$은 $N{\displaystyle \mathcal{}}$ ${\displaystystyle$ $u}$에서 u$}$의 거리를 나타낸다$$$.$따라서 $\beta {\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle \beta =0}$의 경우 완화된 강건성 제약 조건이 원래의 강건성 제약으로 다시 감소한다.이는 다음과 같은 강력한 최적화 문제를 산출한다.

${\displaystyle z({\mathcal{N},U):=\max _{x\in X}\ \{f(x):g(x,u)\leq b+\beta \cdot distit(u,{\mathcal{N})\\\\forall u\in U\}}}}}$

$d{\displaystyle }$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle t}$ ${\displaystyle dist}$ 함수는 다음과 같은 방식으로 정의된다$$.

${\displaystyle dist(u,{\mathcal {N})\geq 0,\all u\in U}$

, 그리고

${\displaystyle dist(u,{{N}\mathcal})=0,\forall u\in{{N\mathcal}}}.$

따라서 편안한 문제에 최적의 솔루션 g(x,마)}. 그것은 또한 편안한 제약 조건을 충족하는 원래 제약 유{\displaystyle u}의 N{\displaystyle{{N\mathcal}내의 모든 값은}에 ≤ b{g(x,u)\leq b\displaystyle}을 만족한다.

${\displaystyle g(x,u)\leq b+\beta\cdot dist(u,{{N}\mathcal})}.$

N{\displaystyle{{N\mathcal}밖에서}}.

비확률론적 강력한 최적화 모델

강력한 최적화 이 지역의 압도적인 방법은 월드의 맥 시민 모델, 즉.

${\displaystyle \max_{x\in X}\min _ᆫf(x,u)}.$

어디의 최대{\displaystyle \max}은 의사 결정자를 나타내는 경우분{\displaystyle \min}X{X\displaystyle}및 U()){U())\displaystyle},{\displaystyle u}의 가능한 값 결정인데와 연관된 집합을 나타내는 결정 공간을 나타내는 자연, 즉 불확실성을 나타내는{\displaystyle)}.제네릭 모델의 고전 형식이고 종종 미니 맥스 또는 맥 시민 최적화 문제라 한다.그non-probabilistic(결정론적)모델과 광범위하게 강력한 최적화를 위해 신호 처리 분야 특히 용도로 사용되고 있다.[11][12][13]

그 고전적 형식 위의 등가물 수학적 프로그래밍(MP) 있다.

${\displaystyle \max_{x\in X,v\in \mathbb{R}})\{v:v\leq f(x,u),\forall u\in U())\}}.$

제약조건은 이 모델에 명시적으로 통합될 수 있다.일반적인 제한된 클래식 형식은

${\displaystyle \max _{x\in X}\min _{u\in U(x)}\{f(x,u):g(x,u)\leq b,\all u\in U(x)\}}$

등가 제한 MP 형식은 다음과 같이 정의된다.

${\displaystyle \max _{x\in X,v\in \mathb {R}}\\{v:v\leq f(x,u),g(x,u)\leq b,\all u\in U(x)\}}}$

확률적으로 강력한 최적화 모델

이러한 모형은 확률 분포 함수에 의해 관심 모수의 "참" 값의 불확실성을 정량화한다.그들은 전통적으로 확률적 프로그래밍과 확률적 최적화 모델로 분류되어 왔다.최근에는 무작위화에 의해 얻어진 솔루션의 강건성 수준을 정량화할 수 있는 시나리오 최적화 등 엄격한 이론이 도입되어 확률적으로 강력한 최적화가 인기를 얻고 있다.이러한 방법은 데이터 기반 최적화 방법과도 관련이 있다.

강력한 상대

많은 강력한 프로그램에 대한 솔루션 방법에는 강력한 상대라고 불리는 결정론적 등가물을 생성하는 것이 포함된다.강력한 프로그램의 실질적인 어려움은 강력한 상대 프로그램이 계산적으로 추적 가능한지 여부에 달려 있다.^[14][15]

참고 항목

• 안정성 반지름
• 미니맥스
• 미니맥스 추정기
• 미니맥스 후회
• 강력한 통계량
• 강력한 의사 결정
• 확률적 프로그래밍
• 확률적 최적화
• 정보격차결정론
• 타구치 방법

참조

추가 읽기

• H.J. 그린버그.수학 프로그래밍 용어집.월드 와이드 웹, http://glossary.computing.society.informs.org/, 1996-2006.ANNES Computing Society에서 편집.
• Ben-Tal, A.; Nemirovski, A. (1998). "Robust Convex Optimization". Mathematics of Operations Research. 23 (4): 769–805. CiteSeerX 10.1.1.135.798. doi:10.1287/moor.23.4.769.
• Ben-Tal, A.; Nemirovski, A. (1999). "Robust solutions to uncertain linear programs". Operations Research Letters. 25: 1–13. CiteSeerX 10.1.1.424.861. doi:10.1016/s0167-6377(99)00016-4.
• Ben-Tal, A.; Arkadi Nemirovski, A. (2002). "Robust optimization—methodology and applications". Mathematical Programming, Series B. 92 (3): 453–480. CiteSeerX 10.1.1.298.7965. doi:10.1007/s101070100286.
• Ben-Tal A, El Ghaoui, L., Nemirovski, A. (2006)Mathematical Programming, Volume 107(1-2)의 Robust Optimization에 관한 특별호.
• Ben-Tal A, El Ghaoui, L., Nemirovski, A. (2009)강력한 최적화.프린스턴 대학 출판부의 응용 수학의 프린스턴 시리즈.
• Bertsimas, D.; Sim, M. (2003). "Robust Discrete Optimization and Network Flows". Mathematical Programming. 98 (1–3): 49–71. CiteSeerX 10.1.1.392.4470. doi:10.1007/s10107-003-0396-4.
• Bertsimas, D.; Sim, M. (2006). "Tractable Approximations to Robust Conic Optimization Problems Dimitris Bertsimas". Mathematical Programming. 107 (1): 5–36. CiteSeerX 10.1.1.207.8378. doi:10.1007/s10107-005-0677-1.
• Chen, W.; Sim, M. (2009). "Goal Driven Optimization". Operations Research. 57 (2): 342–357. doi:10.1287/opre.1080.0570.
• Chen, X.; Sim, M.; Sun, P.; Zhang, J. (2008). "A Linear-Decision Based Approximation Approach to Stochastic Programming". Operations Research. 56 (2): 344–357. doi:10.1287/opre.1070.0457.
• Chen, X.; Sim, M.; Sun, P. (2007). "A Robust Optimization Perspective on Stochastic Programming". Operations Research. 55 (6): 1058–1071. doi:10.1287/opre.1070.0441.
• Dembo, R (1991). "Scenario optimization". Annals of Operations Research. 30 (1): 63–80. doi:10.1007/bf02204809.
• Dodson, B, Hammett, P 및 Klerx, R. (2014) 엔지니어 John Wiley & Sons, Inc.를 위한 최적화 및 강건성을 위한 확률론적 설계.ISBN 978-1-118-79619-1
• Gupta, S.K.; Rosenhead, J. (1968). "Robustness in sequential investment decisions". Management Science. 15 (2): 18–29. doi:10.1287/mnsc.15.2.B18.
• Kouvelis P.와 Yu G. (1997년).강력한 이산 최적화 및 애플리케이션, Kluwer.
• Mutapcic, Almir; Boyd, Stephen (2009). "Cutting-set methods for robust convex optimization with pessimizing oracles". Optimization Methods and Software. 24 (3): 381–406. CiteSeerX 10.1.1.416.4912. doi:10.1080/10556780802712889.
• Mulvey, J.M.; Vanderbei, R.J.; Zenios, S.A. (1995). "Robust Optimization of Large-Scale Systems". Operations Research. 43 (2): 264–281. doi:10.1287/opre.43.2.264.
• 네자드세이피, 오, 게이즐레이어스 H.J.M. 판덴 부가르드 A.H. (2018)"불확실성 전파에 대한 해석적 평가에 기초한 로봇 최적화"엔지니어링 최적화 51(9): 1581-1603. doi:10.1080/0305215X.2018.1536752.
• Rosenblat, M.J. (1987). "A robust approach to facility design". International Journal of Production Research. 25 (4): 479–486. doi:10.1080/00207548708919855.
• Rosenhead, M.J; Elton, M; Gupta, S.K. (1972). "Robustness and Optimality as Criteria for Strategic Decisions". Operational Research Quarterly. 23 (4): 413–430. doi:10.2307/3007957. JSTOR 3007957.
• 러스탐 B.와 하우 M.(2002년).Princeton University Press에서 최악의 경우 설계 및 위험 관리에 적용하기 위한 알고리즘.
• Sniedovich, M (2007). "The art and science of modeling decision-making under severe uncertainty". Decision Making in Manufacturing and Services. 1 (1–2): 111–136. doi:10.7494/dmms.2007.1.2.111.
• Sniedovich, M (2008). "Wald's Maximin Model: a Treasure in Disguise!". Journal of Risk Finance. 9 (3): 287–291. doi:10.1108/15265940810875603.
• Sniedovich, M (2010). "A bird's view of info-gap decision theory". Journal of Risk Finance. 11 (3): 268–283. doi:10.1108/15265941011043648.
• Wald, A (1939). "Contributions to the theory of statistical estimation and testing hypotheses". The Annals of Mathematics. 10 (4): 299–326. doi:10.1214/aoms/1177732144.
• Wald, A (1945). "Statistical decision functions which minimize the maximum risk". The Annals of Mathematics. 46 (2): 265–280. doi:10.2307/1969022. JSTOR 1969022.
• 월드, A. (1950년)뉴욕 주, 존 와일리, 통계적 의사결정 기능
• Shabanzadeh, Morteza; Fattahi, Mohammad (2015). "Generation Maintenance Scheduling via robust optimization". 2015 23rd Iranian Conference on Electrical Engineering. pp. 1504–1509. doi:10.1109/IranianCEE.2015.7146458. ISBN 978-1-4799-1972-7.

외부 링크

• ROMA: 간편한 강력한 최적화
• 심각한 불확실성 하에서 강력한 의사 결정
• 로부시마이저: 강력한 최적화 소프트웨어