shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
시장 균형 계산(, 또는 경쟁 균형 계산(competitive equilibrium computation) 또는 청산 가격 계산(clearing-prices computation))은 경제학과 컴퓨터 과학의 교차점에 있는 계산 문제이다. 이 문제의 입력은 자원 집합과 에이전트 집합으로 구성된 시장이다. 피셔 시장과 애로-드브뢰 시장과 같이 다양한 종류의 시장이 있으며, 자원은 가분적이거나 비가분적일 수 있다. 필요한 출력은 경쟁 균형이며, 이는 가격 벡터(각 자원에 대한 가격)와 할당(각 에이전트에 대한 자원 묶음)으로 구성되어 각 에이전트가 예산에 따라 가능한 최상의 묶음을 얻고 시장이 청산되는(모든 자원이 할당되는) 상태를 의미한다.
경쟁 균형이 항상 파레토 효율적이라는 사실 때문에 시장 균형 계산은 흥미롭다. 모든 구매자가 동일한 소득을 가지는 피셔 시장의 특수한 경우는 특히 흥미로운데, 이 설정에서는 경쟁 균형이 무질투적이기도 하기 때문이다. 따라서 시장 균형 계산은 공정하고 효율적인 할당을 찾는 방법이다.
시장 균형 계산의 입력은 다음 요소로 구성된다.
필요한 출력은 다음 요소들을 포함해야 한다:
출력은 다음 요구사항을 충족해야 한다:
이러한 요구사항을 충족하는 가격과 할당을 경쟁 균형(CE) 또는 시장 균형이라고 한다. 가격은 또한 균형 가격 또는 청산 가격이라고도 한다.
효용 함수의 종류.
시장 균형 계산은 에이전트의 효용 함수에 대한 다양한 가정 하에 연구되어 왔다.
부분 선형 및 오목한 효용은 종종 PLC라고 불리며; 분리 가능하기도 한 경우 SPLC라고 불린다.
스카프는 스페르너 보조정리를 사용하여 CE의 존재를 처음으로 보였다( 피셔 시장 참조). 그는 또한 근사 CE를 계산하는 알고리즘을 제시했다.
메릴은 근사 CE를 위한 확장된 알고리즘을 제시했다.
카카데, 컨스, 오르티즈는 에이전트가 그래프에 위치하고 인접한 에이전트 간에만 거래가 발생할 수 있는 일반화된 애로-드브뢰 시장에서 근사 CE를 위한 알고리즘을 제시했다. 그들은 비선형 효용을 고려했다.
뉴먼과 프리막은 선형 효용을 가진 애로-드브뢰 시장에서 CE를 찾는 타원체 방법의 두 가지 변형을 연구했다. 그들은 내접 타원체 방법이 외접 타원체 방법보다 계산 효율적임을 증명했다.
난이도 결과.
어떤 경우에는 근사 CE를 계산하는 것이 PPAD-hard이다.
정확한 알고리즘.
데바누르, 파파디미트리우, 사베리, 바지라니는 선형 효용 함수를 가진 피셔 시장에서 균형을 정확하게 계산하는 다항 시간 알고리즘을 제시했다. 그들의 알고리즘은 KKT 조건과 볼록 프로그램의 강화된 설정에서 원시-쌍대 패러다임을 사용한다. 그들의 알고리즘은 약 다항식적이다: formula_24개의 최대 흐름 문제를 해결하며, 따라서 formula_25 시간에 실행된다. 여기서 umax와 Bmax는 각각 최대 효용과 예산이다.
올린은 선형 효용을 가진 피셔 시장 모델에 대해 개선된 알고리즘을 제시했으며, formula_26 시간에 실행된다. 그는 이후 자신의 알고리즘을 개선하여 강다항 시간에 실행되도록 했다: formula_27.
데바누르와 칸난은 모든 자원이 재화(효용이 양수)인 오목 효용 함수를 가진 애로-드브뢰 시장에 대한 알고리즘을 제시했다:
코데노티, 맥쿤, 페누마차, 바라다라잔은 대체 탄력성이 1/2 이상인 대체 탄력성 효용을 가진 애로-드브뢰 시장에 대한 알고리즘을 제시했다.
나쁜 재화와 혼합 마나.
보고몰나이아, 물랭, 산도미르스키, 야노브스카이아는 나쁜 재화(음의 효용을 가진 품목)를 가진 피셔 시장과 재화와 나쁜 재화의 혼합을 가진 피셔 시장에서 CE의 존재와 특성을 연구했다. 재화 설정과 달리, 자원이 나쁜 재화인 경우 CE는 선형 효용을 가진 경우에도 어떤 볼록 최적화 문제도 해결하지 못한다. CE 할당은 실현 가능한 효용 집합의 파레토 프론티어에서 효용의 곱의 지역 최소값, 지역 최대값, 안장점에 해당한다. CE 규칙은 다중값이 된다. 이 연구는 이러한 시장에서 CE를 찾는 알고리즘에 대한 여러 연구로 이어졌다:
n과 m이 모두 변수인 경우, 문제는 계산적으로 어려워진다:
주요 기법.
가성비 (Bang-for-buck).
효용이 선형일 때, 에이전트 i의 가성비(BPB 또는 효용-대-화폐)는 지불한 가격으로 나눈 i의 효용으로 정의된다. 단일 자원의 BPB는 formula_28이며; 총 BPB는 formula_29이다.
선형 효용을 가진 피셔 시장에서 CE를 찾는 데 있어 핵심적인 관찰은, 어떤 CE에서든 그리고 어떤 에이전트 i에 대해서든:
모든 제품 formula_4에 잠재적 구매자, 즉 formula_33인 구매자 formula_6가 있다고 가정하자. 그러면 위 부등식은 formula_35, 즉 모든 가격이 양수임을 의미한다.
셀 분해.
셀 분해는 가능한 가격 공간 formula_36을 초평면 또는 더 일반적으로 다항 곡면을 사용하여 작은 "셀"로 분할하는 과정이다. 셀은 각 곡면의 어느 쪽에 놓이는지를 지정함으로써 정의된다(다항 곡면의 경우, 셀은 준대수 집합이라고도 알려져 있다). 각 셀에 대해 시장 청산 가격 벡터(즉, 시장 청산 할당이 존재하는 해당 셀 내의 가격)를 찾거나, 해당 셀에 시장 청산 가격 벡터가 포함되어 있지 않음을 확인한다. 문제는 다음 속성을 가진 분해를 찾는 것이다:
볼록 최적화: 동차 효용.
모든 에이전트의 효용이 동차 함수인 경우, 피셔 모델의 균형 조건은 아이젠버그-게일 볼록 프로그램이라는 볼록 최적화 프로그램의 해로 작성될 수 있다. 이 프로그램은 예산에 따라 결정되는 가중치로 구매자 효용의 가중 기하 평균을 최대화하는 할당을 찾는다. 동등하게, 이는 효용 로그의 가중 산술 평균을 최대화한다:
(공급량은 1로 정규화되므로).
이 최적화 문제는 카루시-쿤-터커 조건(KKT)을 사용하여 해결할 수 있다. 이 조건은 가격 formula_46으로 해석될 수 있는 라그랑주 승수를 도입한다. 아이젠버그-게일 프로그램을 최대화하는 모든 할당에서 모든 구매자는 요구되는 묶음을 받는다. 즉, 아이젠버그-게일 프로그램의 해는 시장 균형을 나타낸다.
바지라니의 알고리즘: 선형 효용, 약다항 시간.
동차 효용의 특별한 경우는 모든 구매자가 선형 효용 함수를 가질 때이다. 각 자원이 잠재적 구매자, 즉 해당 자원에서 양의 효용을 얻는 구매자를 가진다고 가정한다. 이 가정 하에 시장 청산 가격은 존재하며 유일하다. 증명은 아이젠버그-게일 프로그램에 기반한다. KKT 조건은 최적 해(할당 formula_47 및 가격 formula_48)가 다음 부등식을 만족함을 의미한다:
모든 제품 formula_4에 잠재적 구매자, 즉 formula_33인 구매자 formula_6가 있다고 가정하자. 그러면 부등식 3은 formula_35, 즉 모든 가격이 양수임을 의미한다. 그러면 부등식 2는 모든 공급이 소진됨을 의미한다. 부등식 4는 모든 구매자의 예산이 소진됨을 의미한다. 즉, 시장이 청산된다. 로그 함수는 엄밀히 오목 함수이므로, 두 개 이상의 균형 할당이 있다면 두 할당에서 각 구매자가 얻는 효용은 동일해야 한다(한 구매자의 효용 감소가 다른 구매자의 효용 증가로 상쇄될 수 없다). 이는 부등식 4와 함께 가격이 유일함을 의미한다.
바지라니는 선형 피셔 시장에서 균형 가격과 할당을 찾는 알고리즘을 제시했다. 이 알고리즘은 위 조건 4에 기반한다. 이 조건은 균형 상태에서 모든 구매자가 현재 가격에서 최대 BPB를 제공하는 제품만 구매한다는 것을 의미한다. 구매자가 현재 가격에서 제품이 최대 BPB를 제공하는 경우 "좋아한다"고 하자. 가격 벡터가 주어지면, 각 간선의 용량이 해당 간선을 통해 "흐르는" 총액을 나타내는 흐름 네트워크를 구성한다. 네트워크는 다음과 같다:
가격 벡터 p는 ({s},V\{s})와 (V\{t},{t}) 두 절단이 최소 컷일 때만 균형 가격 벡터이다. 따라서 균형 가격 벡터는 다음 방식으로 찾을 수 있다:
이 문제를 약다항 시간에 해결하는 알고리즘이 있다.
온라인 계산.
최근 가오, 페이사코비치, 크로어는 시장 균형의 온라인 계산을 위한 알고리즘을 제시했다.
"Reach for the Sky"는 미국 록 밴드 파이어하우스가 발매한 다섯 번째 싱글이다. 그들의 두 번째 음반인 Hold Your Fire의 첫 번째 싱글로, 이 곡은 빌보드 핫 100에서 83위, 앨범 록 트랙 차트에서 27위를 기록했다. 이 곡은 기타리스트 빌 레버티와 보컬리스트 C. J. 스네어가 작곡했다.
윌리엄 G. 레버티 2세(영어: William G. Leverty II, 1962년 1월 30일~)는 미국의 기타리스트이다. 그는 하드 록 밴드 FireHouse의 창립 멤버이며 밴드의 많은 히트곡을 작곡했다. 2000년대 내내 레버티는 솔로 활동도 병행하여 Wanderlust, Southern Exposure, Deep South, Drive, Divided We Fall 등 다섯 장의 앨범을 발매했다. 창립 멤버이자 보컬리스트인 C. J. 스네어의 사망 이후, 레버티는 드러머 Michael Foster와 함께 밴드에서 유일하게 활동 중인 원년 멤버이다.
버지니아주 리치먼드에서 태어난 레버티는 4살 때 부모님에게 기타를 선물받았지만, 14살이 되어서야 기타 연주를 진지하게 시작했다. 같은 시기에 레버티는 고등학교에서 음악 이론을 공부하기 시작했다. 1984년, 레버티의 밴드인 White Heat는 드러머 오디션을 열었고, 이 자리에서 레버티는 동향 출신이자 오랜 밴드 동료이자 공동 작업자인 Michael Foster를 만났다. 1988년, 레버티와 포스터의 White Heat는 C. J. 스네어와 페리 리처드슨과 합류했다. 1989년 Epic Records와 계약하기 전, White Heat는 밴드 이름을 FireHouse로 변경했다. 파이어하우스는 전 세계적으로 700만 장 이상의 앨범을 판매했으며, "가장 좋아하는 새로운 헤비 메탈/하드 록 아티스트"로 1991년 아메리칸 뮤직 어워드를 수상했다.
1993년, 레버티는 파이어하우스의 가장 높은 차트 순위에 오른 싱글 "Love of a Lifetime"으로 미국 작곡가, 작가 및 출판사 협회(ASCAP) 작곡가 상을 수상했다.
2004년, 파이어하우스와 15년 동안 활동한 레버티는 첫 솔로 앨범인 Wanderlust를 발매했다. 2007년 10월 9일, 레버티는 첫 연주곡이자 두 번째 솔로 앨범인 Southern Exposure를 발매했고, 이어서 2009년에는 세 번째 앨범인 Deep South를 발매했다. 그의 네 번째 솔로 앨범인 Drive는 2013년 2월에 발매되었다. 레버티는 2020년에 다섯 번째 앨범인 Divided We Fall을 발매했다.
2013년, 레버티는 슈퍼그룹 Flood the Engine을 결성했다. FTE는 레버티, 지미 쿤스(Cactus), 키스 혼(Tanya Tucker, Waylon Jennings, Trisha Yearwood, Luke Bryan), 앙드레 라벨(Vinnie Vincent)로 구성되어 있다. Flood the Engine은 2013년에 유일한 앨범인 Flood The Engine을 발매했다.
1990년대 내내 레버티는 야마하 기타 개발과 협찬 계약을 맺었다. 그는 16년 동안 야마하 퍼시피카 모델을 연주했다.
2006년 7월 4일, GREM USA는 레버티가 기타 제조업체와 독점 협찬 계약을 맺었다고 발표했다. GREM 기타는 "더 빌 레버티 프리 래디컬" 모델을 제작했다.
2012년, 레버티는 C.R. Alsip Guitars와 협력하기 시작했고 기타 제조업체의 첫 번째 협찬 연주자가 되었다. 레버티는 C.R. 알십의 마스터 루티에이자 소유주인 제이크 윌로비와 시제품 제작 단계에서 긴밀하게 협력했다. 얼마 후, 레버티의 C.R. 알십 기타인 "럭키 13"이 탄생했다. 레버티의 두 번째 알십 기타인 "골디"는 그의 네 번째 솔로 앨범인 Drive에 실렸다.
레버티는 1996년에 아내 크리스와 결혼했으며, 슬하에 자녀 한 명을 두고 있다.
정침(丁綝, ? ~ ?)은 신나라 ~ 후한 초기의 군인으로, 자는 유춘(幼春)이며 영천군 정릉현(定陵縣) 사람이다.
씩씩하고 용맹스러웠으며, 무략(武略)을 갖추고 있었다. 왕망 때 영양위(潁陽尉)를 지냈다.
유수는 영양을 공격하였으나 방비가 굳건해 무너뜨리지 못했는데, 정침의 설득을 받은 재(宰)가 항복한 덕에 입성할 수 있었고, 유수는 이를 기뻐하여 정침을 편장군(偏將軍)에 임명하고 종군케 하였다. 정침은 병사들을 이끌고 강을 건너고, 각지에 격문을 뿌리는 한편 둔영을 공략하여, 하남·진류·영천 등 21개 현을 정벌하였다.
한편 이 과정에서, 부성(父城)을 지키던 같은 군 사람 영천군연(郡掾) 풍이가 유수의 병사들에게 사로잡혔다. 정침은 자신과 함께 유수를 따르던 풍이의 종형 풍효(馮孝)·같은 군 사람 여안(呂晏)과 함께 풍이를 유수에게 추천하였다. 이후 풍이는 유수의 진영에 투항하였고, 이때부터 유수에게 중용되어 활약하게 되었다.
건무 원년(25년), 유수가 후한을 건국하고 황제에 즉위하였고(광무제), 이때 정침은 하남태수에 임명되었다. 이 즈음에 광무제는 공신들에게 그들이 원하는 대로 봉토를 하사하였는데, 모두가 풍요로운 땅을 골랐으나 정침은 고향 땅을 달라고 하였다. 누군가가 정침에게 그 이유를 물으니, 정침은 이렇게 대답하였다.
이 말을 들은 광무제는 정침을 정릉현 신안향후(新安鄕侯)에 봉하여 식읍 5천 호를 내렸고, 훗날 능양후(陵陽侯)로 옮겼다.
아들 정홍은 관직이 위위에 이르렀다.
페리 리처드슨(Perry Richardson, 1963년 7월 7일 출생)은 2000년까지 하드 록 밴드 파이어하우스에서 활동했으며 현재 스트라이퍼의 베이시스트로 활동하고 있는 미국의 베이시스트이다.
리처드슨은 콘웨이, 사우스캐롤라이나주에 있는 콘웨이 고등학교를 졸업하고 1980년 사우스캐롤라이나/코스탈 캐롤라이나 대학교에서 경영학 학사 학위를 받았다.
리처드슨은 노스캐롤라이나주에서 C. J. 스네어를 만나 Maxx Warrior라는 밴드를 시작했다. 결국 그들은 빌 레버티와 마이클 포스터(White Heat라는 밴드와 연주하고 있었다)를 만났다. 넷은 샬럿에서 모여 1989년에 파이어하우스를 시작했다. 밴드와 함께 그들은 전 세계적으로 7백만 장 이상의 앨범을 판매했으며, 1991년 "가장 좋아하는 신인 헤비메탈/하드록 아티스트"로 아메리칸 뮤직 어워드를 수상했다. 그는 1995년 사우스캐롤라이나 엔터테인먼트 명예의 전당에 헌액되었다.
2000년 파이어하우스를 떠난 후, 리처드슨은 컨트리 음악 연주자 크레이그 모건과 트레이스 애드킨스의 베이스를 연주했다.
2017년 10월 30일, 크리스천 메탈 밴드 스트라이퍼는 리처드슨이 팀 게인즈를 대신할 새로운 베이시스트가 될 것이라고 발표했다.
다양한 선호를 가진 사람들 사이에 물건을 할당할 때, 두 가지 주요 목표는 파레토 효율성과 공정성이다. 물건이 분할 불가능하기 때문에 공정한 할당이 존재하지 않을 수 있다. 예를 들어, 단 하나의 집과 두 사람이 있을 때, 집의 모든 할당은 한 사람에게는 불공평할 것이다. 따라서 최소최대몫 공정성(MMS), 항목 하나까지의 비선점성(EF1), 항목 하나까지의 비례성(PROP1), 항목 하나까지의 공평성(EQ1)과 같은 몇 가지 일반적인 근사치들이 연구되어 왔다. 효율적인 대략 공정한 항목 할당() 문제는 파레토 효율적(PE)이면서 이러한 공정성 개념 중 하나를 만족하는 할당을 찾는 것이다. 이 문제는 2016년에 처음 제시되었고 그 이후로 상당한 주목을 받아왔다.
M으로 표시되는 유한한 물건들의 집합이 있다. n개의 에이전트가 있다. 각 에이전트 i는 물건들의 각 부분집합에 값을 할당하는 가치 함수 Vi를 가진다. 목표는 M을 n개의 부분집합 X1...,Xn으로 분할하고, 각 부분집합 Xi를 에이전트 i에게 할당하여, 할당이 파레토 효율적이고 대략적으로 공정하게 만드는 것이다. 대략적인 공정성에는 다양한 개념이 있다.
효율적인 대략적인 비선점적 할당.
할당은 모든 에이전트가 자신의 몫의 가치가 다른 에이전트의 몫의 가치만큼 높다고 믿는 경우 비선점적 (EF)이라고 불린다. 두 에이전트 i와 j에 대해, j의 묶음에서 최대 하나의 항목이 제거되면 i가 j를 선점하지 않는 경우 항목 하나까지의 비선점적 (EF1)이라고 불린다. 공식적으로:
일부 초기 알고리즘은 약한 형태의 효율성을 만족하지만 PE는 아닌 대략적으로 공정한 할당을 찾을 수 있었다.
이는 PE와 EF1을 모두 만족하는 할당을 찾는 문제로 이어졌다.
최대 내쉬 복지 규칙.
카라기아니스, 쿠로카와, 물랑, 프로카치아, 샤, 왕는 PE+EF1 할당의 존재를 처음으로 증명했다. 그들은 모든 에이전트가 양의 가산 유틸리티를 가질 때, 유틸리티 곱을 최대화하는 모든 할당(내쉬 복지라고도 함)이 EF1임을 증명했다. 최대화 할당이 PE임은 명백하므로, PE+EF1 할당의 존재가 뒤따른다.
최대 곱 할당은 바람직한 속성을 가지고 있지만, 다항 시간 내에 계산할 수 없다. 최대 곱 할당을 찾는 것은 NP-난해이며 심지어 APX-hard이다. 이로 인해 최대 곱을 근사하려는 다양한 연구가 이루어졌으며, 근사 계수는 다음과 같이 개선되었다.
그러나 이러한 근사치는 EF1을 보장하지 않는다. 최근의 일부 알고리즘은 대략적인 최대 곱과 공정성을 모두 보장한다.
최대 곱 해법은 가치 평가가 이진일 때(각 항목의 가치가 0 또는 1) 특히 매력적이다.
비가산 가치 평가.
에이전트의 효용이 가산적이지 않더라도, 최대 곱 해법이 반드시 EF1은 아니다. 그러나 에이전트의 효용이 적어도 준모듈러라면, 최대 곱 해법은 약한 속성인 항목 1을 제외한 한계 비선점성(MEF1)을 만족한다. 이는 각 에이전트 i가 자신의 묶음을 (j의 묶음에서 가장 좋은 항목을 제거한) 한계효용만큼 또는 그 이상으로 평가한다는 것을 의미한다. 공식적으로:
더 일반적인 효용 함수에 대해서도 비슷한 근사치가 발견되었다.
혼합 가치 평가.
마틴과 월시는 "혼합 만나"(양수와 음수 모두를 가질 수 있는 가산 가치 평가)에서 효용의 곱을 최대화하는 것(또는 효용의 음수 곱을 최소화하는 것)이 EF1을 보장하지 않는다는 것을 보여준다. 그들은 또한 EFX3 할당이 동일한 효용을 가질 때도 존재하지 않을 수 있음을 증명한다. 그러나 삼차 효용을 가질 때, EFX와 PO 할당, 또는 EFX3과 PO 할당은 항상 존재한다. 그리고 동일한 효용을 가질 때, EFX와 PO 할당은 항상 존재한다. 이 경우 다항 시간 알고리즘이 있다.
가격 인상 알고리즘.
바르만, 크리슈나무르티, 바이스는 양의 가산 가치 평가를 위한 PE+EF1 할당을 찾는 의사 다항 시간 알고리즘을 제시했다. 그들은 다음 결과를 증명했다.
그들의 알고리즘은 피셔 시장에서의 경쟁 균형 개념을 기반으로 한다. 다음 개념들을 사용한다.
매개변수 e가 주어지면, 이 알고리즘은 fPO와 3e-pEF1을 모두 만족하는 할당을 찾는 것을 목표로 한다. 여러 단계로 진행된다.
1단계: 초기 MBB 할당+가격 (X, p) 구성
2단계: MBB 계층 내 가격 비선점 제거:
3단계: 가격 인상. 다음 세 가지 중 하나가 발생할 때까지 MBB 계층의 모든 객체 가격을 동일한 배율로 인상한다.
먼저, 위 알고리즘이 고정된 e&gt;0에 대해 모든 값이 (1+e)의 거듭제곱인 인스턴스에서 실행된다고 가정한다.
이제, 일반적인 가치 평가를 가진 인스턴스가 있다고 가정한다. 우리는 각 가치 평가를 (1+e)의 가장 가까운 거듭제곱으로 반올림한 반올림된 인스턴스에서 위 알고리즘을 실행한다. 각 에이전트 i와 객체 o에 대해, 반올림된 값 Vi'(o)는 Vi(o)와 (1+e)Vi(o) 사이에 있다는 점에 유의한다.
일반화 조정 승자.
아지즈, 카라기아니스, 이가라시, 월시는 혼합 가치 평가(객체가 양수 및 음수 유틸리티를 모두 가질 수 있음)에 EF1 조건을 확장했다. 그들은 두 에이전트에 대해 O(m2) 시간에 PO+EF1 할당을 찾는 조정 승자 절차의 일반화를 제시했다.
효율적인 대략적인 비례 할당.
객체 할당은 모든 에이전트가 자신의 몫의 가치를 모든 항목 가치의 최소 1/n로 평가하는 경우 비례적 (PROP)이라고 불린다. 에이전트 i에 대해, 그의 묶음에 최대 하나의 항목이 추가되면 i가 묶음을 전체 가치의 최소 1/n로 평가하는 경우 항목 하나까지의 비례적 (PROP1)이라고 불린다. 공식적으로, 모든 i에 대해 (M은 모든 재화의 집합):
PROP1 조건은 코니처, 프리먼, 샤가 공정한 공공 의사 결정의 맥락에서 도입했다. 그들은 이 경우 PE+PROP1 할당이 항상 존재한다고 증명했다.
모든 EF1 할당은 PROP1이므로, 비분할 항목 할당에서도 PE+PROP1 할당이 존재한다. 문제는 그러한 할당이 PE+EF1 알고리즘보다 빠른 알고리즘으로 찾아질 수 있는지 여부이다.
바르만과 크리슈나무르티는 재화(양의 효용을 가진 객체)에 대한 PE+PROP1 할당을 찾는 알고리즘을 제시했다.
브란제이와 산도미르스키는 PROP1 조건을 잡일(음의 효용을 가진 객체)로 확장했다. 공식적으로, 모든 i에 대해:
그들은 잡일에 대한 PE+PROP1 할당을 찾는 알고리즘을 제시했다. 객체의 수 또는 에이전트의 수(또는 둘 다)가 고정되어 있다면 이 알고리즘은 강력한 다항 시간이다.
아지즈, 카라기아니스, 이가라시, 월시는 PROP1 조건을 혼합 가치 평가(객체가 양수 및 음수 효용을 모두 가질 수 있음)로 확장했다. 이 설정에서 할당은 각 에이전트 i에 대해, i의 묶음에서 음수 항목 하나를 제거하거나 i의 묶음에 양수 항목 하나를 추가하면, i의 효용이 총량의 최소 1/n인 경우 PROP1이라고 불린다. 그들의 일반화 조정 승자 알고리즘은 두 에이전트에 대한 PE+EF1 할당을 찾으며, 이러한 할당은 PROP1이기도 하다.
아지즈, 물랑, 산도미르스키는 에이전트나 객체의 수가 고정되지 않고, 에이전트들이 다른 권리를 가지고 있더라도, 일반적인 혼합 가치 평가를 가진 분수적으로 PE(PE보다 강력함)이며 PROP1인 할당을 찾는 강력한 다항 시간 알고리즘을 제시했다.
효율적인 대략적인 공평한 할당.
객체 할당은 모든 에이전트의 주관적 가치가 동일할 때 공평적 (EQ)이라고 불린다. 이 개념을 연구하는 동기는 인간 피험자들이 비선점 할당보다 공평한 할당을 선호한다는 실험 결과에서 비롯된다. 할당은 두 에이전트 i와 j에 대해, j의 묶음에서 최대 하나의 항목이 제거되면 i의 주관적 가치가 j의 가치만큼 높을 때 항목 하나까지 공평적 (EQ1)이라고 불린다. 공식적으로, 모든 i, j에 대해:
더 강력한 개념은 어떤 항목까지도 공평적 (EQx)이다. 두 에이전트 i와 j에 대해, j의 묶음에서 어떤 단일 항목이 제거되든 i의 주관적 가치는 j의 가치만큼 높다.
EQx 할당은 구르베, 모노, 틀리란이 "거의 질투 없음"이라는 다른 용어를 사용하여 처음 연구했다. 그들은 할당된 모든 재화의 합집합이 주어진 매트로이드의 기저라는 추가 요구 사항이 있더라도 부분 EQx 할당이 항상 존재함을 증명했다. 그들은 비선점 그래프 절차와 유사한 알고리즘을 사용했다. 숙솜퐁은 모든 할당이 한 선의 연속적인 부분집합이어야 한다는 추가 요구 사항이 있더라도 EQ1 할당이 존재함을 증명했다.
프리먼, 시카르, 바이스, 시아는 다음과 같은 더 강력한 결과를 증명했다.
소수의 에이전트를 위한 알고리즘.
브레더렉, 카치마르키크, 크놉, 니더마이어는 에이전트가 적고(작은 n) 항목 유형이 적으며(작은 m), 항목 유형당 효용이 상한선(V)으로 제한되지만, 각 유형의 항목이 많을 수 있는 설정을 연구한다. 이 설정에 대해 그들은 다음 메타 정리를 증명한다(정리 2): 효율성 기준 E와 공정성 기준 F가 주어졌을 때, 만약 formula_9이 고정되어 있다면, E와 F가 다음 속성을 만족하는 한, E-효율적이면서 F-공정한 할당이 존재하는지 여부를 다항 시간에 결정할 수 있다.
그런 다음, 그들은 여러 일반적인 공정성 및 효율성 기준이 이러한 속성을 만족함을 증명한다. 여기에는 다음이 포함된다.
그들의 알고리즘의 실행 시간은 입력 크기(비트 단위)에 formula_11를 곱한 값이며, 여기서 d는 결과 ILP의 변수 수로 formula_12이다.
그들은 나중에 이러한 문제들 중 일부에 대해 더 실용적인 알고리즘을 개발했다.
마이클 해리슨 스위트(Michael Harrison Sweet, 1963년 7월 4일~)는 미국의 음악가이다. 그는 헤비 메탈 밴드 스트라이퍼의 공동 설립자, 작곡가, 기타리스트, 리드 보컬이다. 그는 또한 성공적인 솔로 활동을 했으며 2007년부터 2011년까지 보스턴의 보컬리스트이자 기타리스트로 활동했다.
스트라이퍼.
1980년대 초, 스위트와 그의 형은 Roxx Regime이라는 밴드를 결성하여 작은 공연장에서 연주했다. 그들은 스위트가 밴드에서 유일한 기타리스트인 트리오로 한동안 활동했다. 이 밴드는 나중에 스트라이퍼가 되었다. 밴드는 헤비 메탈이 사탄적이라는 고정관념에 도전하고 크리스천 록을 주류로 이끌었다.
밴드에서 스위트는 리드 보컬과 리드 기타를 맡았을 뿐만 아니라, 밴드의 대부분의 음악을 작곡하고 공동 프로듀싱 및 편곡을 담당했다. 밴드는 다섯 장의 성공적인 스튜디오 앨범을 녹음했다. 밴드의 명성은 1990년대에 쇠퇴했다.
스트라이퍼의 리드 보컬/리드 기타리스트로 9년간 활동한 후, 스위트는 솔로 활동을 추구하기 위해 1992년에 밴드를 떠났다. 그는 먼저 Unstryped라는 데모 앨범을 발표했는데, 이 앨범에는 밴드를 위해 의도되었다고 주장되는 여러 곡이 수록되어 있었다. 스위트는 나중에 이 곡들 중 일부를 자신의 첫 정규 앨범에 포함시켰다.
그의 동명 데뷔 앨범은 1994년에 발매되어 25만 장 이상 판매되었다. 이어서 1996년에는 약간 더 부드러운 Real이라는 앨범을 발표하여 도브 어워드 후보에 올랐다. Real 발매 직후, 스위트는 이 두 앨범을 발매했던 Benson Records를 떠났다.
이 기간 동안 스위트와 그의 아내 카일은 매사추세츠주로 이사했고, 그곳에서 스위트는 장인의 캠핑장/크랜베리 사업인 Maple Park에서 일했다. 1998년에는 Truth라는 독립 데모 앨범을 발매하여 비평가들의 찬사를 받았다. 그는 Restless Records와 계약을 맺고 2000년에 새로운 곡 목록과 새로운 아트워크로 Truth를 재발매했다.
2007년 8월 19일, 스위트는 보스턴의 톰 숄츠로부터 보스턴의 Bank of America Pavilion에서 열린 브래드 델프의 삶을 기리는 콘서트 Come Together: A Tribute to the Life of 브래드 델프에서 리드 보컬리스트이자 기타리스트 중 한 명이 되어달라는 요청을 받았다. 숄츠는 이어서 스위트에게 스틱스를 오프닝 밴드로 하는 보스턴의 2008년 여름 투어에 합류해달라고 요청했다.
스위트는 보스턴에서 리드 보컬, 백 보컬, 기타 연주를 맡았다. 스위트는 2007년 8월 19일에 보스턴의 마지막 공연이 될 예정이었던 행사에 참여하도록 요청받았다. 이는 자선 및 추모 공연이었으며, 새미 헤이거, 미키 토머스, 앤 윌슨과 같은 유명인사들이 초대 손님으로 참석했다. 톰 숄츠는 스위트가 고인이 된 브래드 델프에 대해 쓴 글에 감동했고, 이어서 스위트가 노래하고 기타를 연주하는 것을 들었다. 숄츠는 스위트의 재능에 깊은 인상을 받아 그를 밴드에 영구 멤버로 초청했다. 보스턴은 스틱스를 오프닝 밴드로 하여 2008년 투어 일정을 잡기 시작했다. 스위트는 세트리스트의 약 절반에 걸쳐 리드 보컬을 담당했으며, 전체 세트 동안 기타를 연주하고 솔로 연주도 소화했다. 2011년 8월, 스위트가 스트라이퍼에 대한 그의 우선순위와 기여에 집중하기 위해 보스턴을 떠났다고 발표되었다.
스트라이퍼 재결합.
1999년, 스위트는 푸에르토리코 콘서트에서 전 스트라이퍼 밴드 동료인 오즈 폭스와 팀 게인즈와 재회했다. 이 콘서트에는 폭스와 게인즈의 밴드인 SinDizzy가 출연했다. 스위트는 솔로 아티스트로 초대되었다. 그들 셋은 네 곡을 함께 연주했다. 이듬해, 첫 번째 스트라이퍼 엑스포가 뉴저지주에서 열렸고, 전체 라인업이 다시 한 번 재결합했다.
원래 베이시스트 팀 게인즈는 2005년에 그룹을 떠나 트레이시 페리로 교체되었지만, 밴드는 계속 함께 작업하여 스위트가 프로듀싱한 Reborn이라는 새 앨범을 발매했다. 그러나 그는 솔로 활동도 계속했다. 2006년 8월, 그는 스위트가 다시 쓰고 편곡한 전통 찬송가를 수록한 Him이라는 솔로 앨범을 발매했다. 밴드는 이어서 2009년 7월에 스위트가 프로듀싱한 앨범 Murder by Pride를 발매했다. Firehouse 밴드의 전 멤버였던 페리 리처드슨이 현재 밴드의 베이시스트이다. 페리는 밴드에 새로운 생명을 불어넣었고, 그들은 현재 투어를 진행 중이며 2020년에 발매될 새 스튜디오 앨범을 계획하고 있다.
2007년, 스위트는 2년간의 난소암 투병 끝에 2009년 3월 5일에 사망한 그의 아내 카일을 기리며 Touched라는 앨범을 발매했다.
2009년 9월, 스트라이퍼는 원년 멤버들과 함께 25주년 월드 투어 "Rocking the Hell Out of You for 25 years"를 시작했다. 이 투어에는 두 개의 오프닝 밴드가 참여했는데, Manic Drive와 Flight Patterns로, 후자에는 스위트의 아들 마이클 스위트 주니어가 포함되어 있다.
2011년 2월 15일, 스트라이퍼는 스위트가 프로듀싱한 새 음반 The Covering을 발매했다.
2013년, 스트라이퍼는 프런티어스 레코드를 통해 Second Coming과 No More Hell to Pay 두 장의 스튜디오 앨범을 발매했다. 그들은 2013년 11월에 선셋 스트립의 위스키 어 고고에서 녹음된 라이브 앨범과 DVD인 Stryper: Live at the Whiskey를 발매했다. 스위트는 또한 Lynch Mob의 설립자이자 전 도켄 멤버인 조지 린치와 함께 Only to Rise라는 앨범을 녹음하여 Sweet &amp; Lynch라는 이름으로 발매했다. 스위트는 2015년 2월 4일 에디 트렁크 팟캐스트에서 이 그룹에 대해 논의했다. 이 그룹은 또한 전 화이트 라이온 및 전 메가데스 멤버인 제임스 로멘조가 베이스를, 전 화이트스네이크 및 전 포리너 멤버인 브라이언 티치가 드럼을 맡았다. Only to Rise는 2015년 1월 27일에 발매되었다.
스트라이퍼가 새 앨범 Fallen을 개발하는 것 외에, 스위트는 Rat Pak Records와 계약을 맺고 2016년 초에 새 솔로 앨범 One Sided War를 발매할 것이라고 확인했다.
2016년 11월 Antihero Magazine과의 인터뷰에서 스위트는 2017년 11월에 발매된 Unified라는 또 다른 Sweet &amp; Lynch 앨범을 녹음 중이라고 확인했다. 그 이후 스위트는 조지 린치가 여러 프로젝트에 참여하여 앨범을 홍보하기 위한 투어를 할 수 없었고, 자신이 대부분의 홍보를 해야 한다고 느껴 Sweet &amp; Lynch가 끝났을 수도 있다고 공식적으로 언급했다.
스위트는 스트라이퍼의 멤버로서 2018년 4월 20일 God Damn Evil을 발매했다. 앨범 제목 때문에 불쾌하다는 평가를 받았고 "부모 지도" 라벨이 붙었으며 월마트에서 판매 금지되었다. 이러한 논란에도 불구하고 앨범은 대부분의 주요 음악 차트에서 잘 팔리고 순위에 올랐다. 페리 리처드슨은 앨범에 참여하지 않았지만 앨범을 홍보하는 투어에 참여했다.
스위트는 2019년 후반에 RatPak Records에서 열 번째 스튜디오 앨범인 Ten을 발매했다.
스위트는 또한 2020년 9월 4일에 발매된 스트라이퍼의 Even the Devil Believes에서 기타리스트, 리드 보컬, 프로듀서로 참여했다.
스위트는 스트라이퍼의 첫 번째 비디오를 제작하던 중 아내 카일을 만났다. 그들은 22년 동안 결혼 생활을 했으며 두 자녀를 두었다. 2009년, 카일은 2년간의 암 투병 끝에 사망했다.
2010년 1월 8일, 마이클은 리사 샴페인과 결혼했다.
2023 Return to the Light
• 발매 2023년 11월 17일
• 레이블: Frontiers Music SR
마이클 포스터(Michael Foster, 1964년 12월 9일 출생)는 록 밴드 파이어하우스의 드러머이자 창립 멤버로 가장 잘 알려진 미국 음악가이다. 보컬리스트 C. J. 스네어의 사망 이후, 포스터와 기타리스트이자 창립 멤버인 빌 레버티는 밴드에 남아있는 유일한 원년 멤버이다.
포스터는 리치먼드, 버지니아주에서 제임스 어니스트와 패트리샤(옛 성씨 발렌티) 포스터 사이에서 태어났다. 그는 다니엘 숀이라는 남동생이 있다. 5살 때 어머니가 그에게 첫 번째 진짜 드럼 세트를 주었고, 그는 그것을 연습하는 데 몇 시간을 바쳤다. 그는 학교 밴드에서 연주했고 결국 음악 이론과 다른 타악기들을 배웠다.
1984년, 포스터는 화이트 히트(White Heat)라는 밴드의 오디션을 보았는데, 그 밴드에는 빌 레버티가 기타리스트로 있었다. 그는 그 자리를 얻었고, 결국 그들은 캐롤라이나 지역을 순회하면서 C. J. 스네어와 페리 리처드슨을 만났다. 네 명은 1988년 화이트 히트(White Heat)로 합류했고 1990년 에픽 레코드에서 첫 발매를 하기 전에 이름을 파이어하우스(Firehouse)로 변경했다. 파이어하우스는 전 세계적으로 7백만 장 이상의 앨범을 판매했으며 여러 국제적인 히트곡을 냈다.
포스터는 2012년 12월부터 2013년 2월까지 워런트의 드러머 스티븐 스위트가 목 부상에서 회복하는 동안 그를 대신했다.
포스터는 1995년 9월 15일에 로리 밍지와 결혼했다. 그들은 두 딸과 한 아들을 두었다.
앨런 매켄지(Allen McKenzie, 1960년 1월 1일 출생)는 미국의 음악가로, 하드 록/글램 메탈 밴드 파이어하우스의 베이스 기타리스트로 가장 잘 알려져 있다.
매켄지는 1977년 가족과 함께 애크런으로 이사하기 전 오하이오주 잭슨의 시골 지역에서 자랐다. 1978년 6월, 매켄지는 가필드 고등학교를 졸업했다. 9월에 그는 미국 육군에 입대하여 서독 란다우에서 3년, 미국 내에서 3년간 복무했다.
2005년 10월 8일, 그는 아내 티나와 결혼했다. 그들은 세 자녀를 두고 있다.
매켄지는 2014년 7월에 자신의 취향에 맞게 맞춤 제작된 C.R. 알십 베이스를 연주하기 시작했다. 매켄지는 2012년 밴드 멤버 빌 레버티를 통해 C.R. Alsip Guitars의 마스터 루티어 제이크 윌로비를 만났다. 매켄지는 레버티의 기타를 듣고 윌로비에게 베이스 기타 제작에 관심이 있는지 물었다. 윌로비는 동의했고, 2014년 매켄지와 함께 무대에 처음 등장한 상징적인 "기네스 하프" 5현 베이스를 제작했다.
폭스.
군대를 떠난 매켄지는 애크런의 음악계에 참여하여 커버 밴드들과 함께 연주했다. 매켄지는 우연히 자신과 같은 고무 정유 공장에서 일하던 데이브 잭슨을 만났다. 그들은 1985년 후반에 폭스(Foxx)라는 지역 하드 록 밴드를 결성했다. 폭스는 두 장의 앨범 - Foxx (1989)와 Stick It Out (1991) -을 발매하고 투어를 했다. 폭스는 1992년에 해체되었지만, 2012년 12월에 재결합하여 가끔 공연을 하고 있다.
1993년, 매켄지는 클리블랜드, 오하이오에 기반을 둔 프로그레시브 록 밴드 퀘스트(Quest)에 합류했다. 퀘스트에 합류하면서 그는 가수, 키보드 연주자, 작곡가로서의 관심사를 탐구할 수 있었다. 1994년 말, 퀘스트는 Opposite sides of the picket fence라는 CD를 발매했다. 1994년 여름, 퀘스트는 카이어호가폴스의 블러섬 뮤직 센터에서 예스 콘서트의 오프닝 공연을 했다. 퀘스트의 프로그 록 CD는 실패했고 1995년 그룹은 해체되었다.
피스트리.
매켄지는 하드 록 밴드 피스트리(Peacetree)에 베이스 기타리스트로 합류했다. 이 밴드는 일라이자 블랙이 프론트를 맡았다. 피스트리는 Insense (1996), Wonderful Day (1998), Nice to meet you (2000) 세 장의 CD를 발매했다. Nice to meet you는 피스트리에게 2000년 클리블랜드 프리 타임스 음악 시상식에서 "최고의 하드 록 밴드" 후보 지명을 안겨주었다. 피스트리는 머틀리 크루, 스틱스, 신데렐라, 닐 영과 같은 전국 투어를 하는 밴드의 오프닝 공연을 했다. 피스트리는 또한 더 제니 존스 쇼에도 출연했다.
워런트의 가수 재니 레인.
피스트리는 2002년에 해체되었다. 매켄지는 지역 클래식 록 밴드 JAK 밴드에서 연주했다. 그는 또한 일라이자 블랙이 이끄는 새로운 밴드와 리허설을 했다. 그 후, 밴드 워런트의 원년 보컬인 재니 레인이 자신의 CD Back Down to One을 홍보하기 위한 솔로 투어에 매켄지를 초대했다. 매켄지는 2002년 10월부터 2003년 3월까지 레인과 함께 작업했다.
파이어하우스.
2004년, 매켄지는 레인의 기타리스트 빌리 모리스와 파이어하우스의 현재 사운드 엔지니어 토니 아비타의 추천으로 파이어하우스에 합류했다. 파이어하우스는 미국, 캐나다, 멕시코, 푸에르토리코, 일본, 인도, 브라질, 스페인, 이탈리아, 그리스, 영국을 투어했다. 앨런은 밴드의 나머지 멤버들과 함께 CD Monster Ballads Christmas (2007년 발매된 "Rockin' Around The Christmas Tree"), Hell Bent Forever-A Tribute To Judas Priest (2008년 발매된 "You've Got Another Thing Coming"), DVD Metal Mania Stripped Across America (2005년 발매된 "Don't Treat Me Bad"), 그리고 2011년에 재녹음된 "베스트 오브" 앨범인 밴드의 최신 정규 CD Full Circle에 기여했다.
수학적 최적화에서 타원체 방법()은 볼록 집합 위에서 볼록 함수를 최소화하는 반복법이다. 타원체 방법은 매 단계마다 부피가 균일하게 감소하는 일련의 타원면들을 생성하여 볼록 함수의 최소값을 포함한다.
유리수 데이터를 가진 실행 가능한 선형 계획법 문제에 특화될 때, 타원체 방법은 입력 크기에 대해 다항식 단계 내에서 최적 해를 찾는 알고리즘이다.
타원체 방법은 오랜 역사를 가지고 있다. 반복법으로서 초기 버전은 나움 Z. 쇼어에 의해 소개되었다. 1972년, 실제 볼록 최소화를 위한 근사 알고리즘이 아르카디 네미로프스키와 데이비드 B. 유딘(유딘)에 의해 연구되었다.
유리수 데이터를 가진 선형 계획법 문제를 푸는 알고리즘으로서 타원체 알고리즘은 레오니트 하치얀에 의해 연구되었다. 하치얀의 업적은 선형 프로그램의 다항 시간 해법을 증명한 것이다. 이것은 이론적인 관점에서 중요한 진전이었다. 당시 선형 문제를 푸는 표준 알고리즘은 단체법 (알고리즘)으로, 일반적으로 문제 크기에 선형적으로 비례하는 실행 시간을 가지지만, 문제 크기에 대해 지수적으로 비례하는 예시도 존재했다. 따라서 모든 경우에 대해 다항식으로 보장되는 알고리즘을 갖는 것은 이론적인 돌파구였다.
하치얀의 연구는 선형 프로그램을 푸는 알고리즘의 실행 시간이 다항식임을 처음으로 증명할 수 있음을 보여주었다. 그러나 실제로는 이 알고리즘은 상당히 느리고 실용적인 관심은 거의 없었지만, 훨씬 더 실용적인 용도로 판명된 후속 작업에 영감을 주었다. 특히, 내부점법인 카르마카르의 알고리즘은 실제적으로 타원체 방법보다 훨씬 빠르다. 카르마카르의 알고리즘은 최악의 경우에도 더 빠르다.
타원체 알고리즘은 계산 복잡도 이론가들이 문제의 차원과 데이터의 크기에 따라 달라지지만 행 수에는 의존하지 않는 (최악의 경우) 경계를 달성할 수 있도록 했기 때문에 수년 동안 조합 최적화 이론에서 중요하게 유지되었다. 21세기에 들어서야 유사한 복잡도 특성을 가진 내부점 알고리즘이 등장했다.
볼록 최소화 문제는 다음 요소들로 구성된다.
또한, 최소화자 formula_7를 포함하는 초기 타원면 formula_8이 다음과 같이 정의된다.
여기서 formula_10이고 formula_11는 formula_12의 중심이다.
마지막으로, 볼록 집합 formula_5에 대한 분리 오라클의 존재가 필요하다. 점 formula_14이 주어졌을 때, 오라클은 다음 두 가지 답변 중 하나를 반환해야 한다.
타원체 방법의 결과는 다음 중 하나이다:
어디에서나 0인 함수의 부등식 제약 최소화는 단순히 실행 가능한 점을 식별하는 문제에 해당한다. 선형 계획법 문제는 선형 실행 가능성 문제(즉, 일부 선형 부등식 및 등식 제약 조건 하에서 0 함수를 최소화)로 환원될 수 있음이 밝혀졌다. 이를 수행하는 한 가지 방법은 원시 및 이중 선형 프로그램을 하나의 프로그램으로 결합하고, 원시 해의 값이 이중 해의 값보다 나쁘지 않다는 추가 (선형) 제약 조건을 추가하는 것이다. 다른 방법은 선형 프로그램의 목표를 추가 제약 조건으로 처리하고 이진 탐색을 사용하여 최적 값을 찾는 것이다.
제약 없는 최소화.
알고리즘의 k번째 반복에서, 우리는 타원체의 중심에 있는 점 formula_26를 가지고 있다.
우리는 절단 평면 오라클에 질의하여 다음을 만족하는 벡터 formula_28을 얻는다.
그러므로 우리는 다음을 결론짓는다.
우리는 formula_31을 위에서 설명한 반타원체를 포함하는 최소 부피의 타원체로 설정하고 formula_32를 계산한다. 업데이트는 다음과 같이 주어진다.
정지 기준은 다음 속성에 의해 주어진다.
부등식 제약 최소화.
제약 최소화를 위한 알고리즘의 k번째 반복에서, 우리는 이전과 같이 타원체 formula_36의 중심에 있는 점 formula_26를 가지고 있다. 우리는 또한 현재까지의 실행 가능한 반복의 가장 작은 목적 함수 값을 기록하는 formula_38 값 목록을 유지해야 한다. 점 formula_26가 실행 가능한지에 따라 다음 두 작업 중 하나를 수행한다:
볼록 프로그램에서의 성능.
이론적 실행 시간 복잡도 보장.
실수 RAM 모델에서 타원체 방법의 실행 시간 복잡도 보장은 다음 정리에 의해 주어진다.
형태의 볼록 최적화 문제군을 고려해보자: f(x)를 최소화하되, x는 G 안에 있어야 한다, 여기서 f는 볼록 함수이고 G는 볼록 집합(유클리드 공간 Rn의 부분 집합)이다. 이 문제군 내의 각 문제 p는 데이터 벡터 Data(p)로 표현되는데, 예를 들어 함수 f와 실행 가능 영역 G를 나타내는 행렬 및 벡터의 실수 값 계수들이다. 문제 p의 크기, Size(p),는 Data(p)의 요소(실수) 수로 정의된다. 다음 가정이 필요하다:
이러한 가정 하에, 타원체 방법은 "R-다항식"이다. 이는 모든 문제 인스턴스 "p"와 모든 근사 비율 "ε"&gt;0에 대해 다음을 만족하는 해 x를 찾는 방법이 존재한다는 것을 의미한다:
formula_47,
다음 산술 연산 수를 사용하여:
여기서 "V"("p")는 데이터에 의존하는 양이다. 직관적으로, 이는 각 추가 정확도 자리에 필요한 연산 수가 Size("p")에 대해 다항식이라는 것을 의미한다. 타원체 방법의 경우:
타원체 방법은 최대 formula_50 단계를 필요로 하며, 각 단계는 Poly(Size(p)) 산술 연산을 필요로 한다.
실제 성능.
타원체 방법은 평면 위치 문제와 같은 저차원 문제에서 사용되며, 여기서 수치적으로 안정적이다. 네미로프스키와 벤-탈은 변수 수가 최대 20-30개일 때 효율적이라고 말한다. 이는 제약 조건의 수가 수천 개라도 마찬가지인데, 반복 횟수가 제약 조건의 수에 의존하지 않기 때문이다. 그러나 변수가 많은 문제에서는 반복 횟수가 O("n"2)로 증가하므로 타원체 방법은 매우 비효율적이다.
심지어 "작은" 크기의 문제에서도 수치적 불안정성과 실제적인 성능 저하를 겪는다.
이론적 중요성.
타원체 방법은 조합 최적화에서 중요한 이론적 기법이다. 계산 복잡도 이론에서 타원체 알고리즘은 복잡성이 열의 수와 계수의 디지털 크기에 따라 달라지지만 행의 수에는 의존하지 않기 때문에 매력적이다.
타원체 방법을 사용하여 많은 볼록 집합에서의 알고리즘 문제가 다항 시간 동치임을 보일 수 있다.
선형 프로그램에서의 성능.
레오니트 하치얀은 타원체 방법을 선형 계획법의 특별한 경우에 적용했다: cTx를 최소화하되, Ax ≤ b를 만족해야 한다, 여기서 A,b,c의 모든 계수는 유리수이다. 그는 선형 프로그램이 다항 시간 안에 해결될 수 있음을 보여주었다. 다음은 하치얀 정리의 개요이다.
1단계: 최적화를 탐색으로 축소. 선형 계획법 쌍대성 정리는 위의 최소화 문제를 탐색 문제로 축소할 수 있음을 말한다: Ax ≤ b ; ATy = c ; y ≤ 0 ; cTx=bTy를 만족하는 x,y를 찾아라. 첫 번째 문제는 두 번째 문제가 해결 가능할 때만 해결 가능하다. 문제가 해결 가능할 경우, 두 번째 문제 해의 "x"-성분은 첫 번째 문제의 최적 해이다. 따라서 지금부터는 다음 문제를 해결해야 한다고 가정할 수 있다: Rz ≤ r을 만족하는 z ≥ 0을 찾아라. 모든 유리수 계수를 공통 분모로 곱하여 모든 계수가 정수라고 가정할 수 있다.
2단계: 탐색을 실행 가능성 확인으로 축소. 문제 Rz ≤ r을 만족하는 z ≥ 0을 찾아라는 이진 결정 문제로 축소될 수 있다: "Rz ≤ r을 만족하는 z ≥ 0이 존재하는가?". 이는 다음과 같이 수행될 수 있다. 결정 문제에 대한 답이 "아니오"이면, 탐색 문제에 대한 답은 "없음"이고, 우리는 완료된다. 그렇지 않으면, 첫 번째 부등식 제약 조건 "R1z" ≤ "r1"를 취한다. 이를 등식 "R1z" = "r1"로 바꾸고, 결정 문제를 다시 적용한다. 답이 "예"이면 등식을 유지하고, 답이 "아니오"이면 부등식이 불필요하다는 의미이므로 제거할 수 있다. 그런 다음 다음 부등식 제약 조건으로 진행한다. 각 제약 조건에 대해 등식으로 변환하거나 제거한다. 마지막으로, 등식 제약 조건만 남게 되며, 이는 선형 방정식 시스템을 해결하는 어떤 방법으로도 해결할 수 있다.
3단계: 결정 문제는 다른 최적화 문제로 축소될 수 있다. 잔여 함수 f(z) := max[(Rz)1-r1, (Rz)2-r2, (Rz)3-r3...]를 정의한다. 분명히, "f"("z")≤0은 "Rz" ≤ "r"일 때만 성립한다. 따라서 결정 문제를 해결하려면 최소화 문제 min"z" "f"("z")를 해결하는 것으로 충분하다. 함수 "f"는 볼록하다 (선형 함수들의 최댓값이다). 최소값을 "f"*로 나타낸다. 그러면 결정 문제에 대한 답은 f*≤0일 때만 "예"이다.
4단계: 최적화 문제 min"z" "f"("z")에서, "z"는 문제 데이터의 비트 길이인 "L"에 대해 변의 길이가 2"L"인 상자 안에 있다고 가정할 수 있다. 따라서 우리는 유계 볼록 프로그램을 가지며, 이는 타원체 방법으로 "L"에 대한 다항식 시간에 임의의 정확도 ε까지 해결할 수 있다.
5단계: 만약 f*&gt;0이면, f*&gt;2-poly(L)이 어떤 다항식에 대해 성립함을 증명할 수 있다. 따라서 정확도 ε=2-poly(L)을 선택할 수 있다. 그러면 타원체 방법으로 찾은 ε-근사 해는 f*&gt;0일 때만 양수이고, 이는 결정 문제가 해결 불가능할 때만 성립한다.
타원체 방법은 각 단계에서 어떤 절단면이 사용되는지에 따라 여러 변형이 있다.
다양한 절단.
중앙 절단 타원체 방법에서, 절단은 항상 현재 타원체의 중심을 통과한다. 입력은 유리수 "ε"&gt;0, 약한 분리 오라클에 의해 주어진 볼록체 "K", 그리고 S(0,"R") (원점 주위 반지름 R의 구)이 "K"를 포함하는 숫자 "R"이다. 출력은 다음 중 하나이다:
단계 수는 formula_51이고, 필요한 정확도 자릿수는 "p" := 8"N"이며, 분리 오라클의 필요한 정확도는 "d" := 2−"p"이다.
깊은 절단 타원체 방법에서, 절단은 각 단계에서 타원체의 절반 이상을 제거한다. 이것은 "K"가 비어 있음을 더 빨리 발견하게 한다. 그러나 "K"가 비어 있지 않을 때는 중앙 절단 방법이 실행 가능한 점을 더 빨리 찾는 예시도 있다. 깊은 절단 사용은 실행 시간의 차수에는 영향을 미치지 않는다.
얕은 절단 타원체 방법에서, 절단은 각 단계에서 타원체의 절반 미만을 제거한다. 이 변형은 실제로는 그다지 유용하지 않지만, 이론적 중요성을 지닌다: 다른 변형으로는 도출할 수 없는 결과를 증명할 수 있게 한다. 입력은 유리수 "ε"&gt;0, 얕은 분리 오라클에 의해 주어진 볼록체 "K", 그리고 S(0,"R")이 "K"를 포함하는 숫자 "R"이다. 출력은 양의 정부호 행렬 A와 점 a로, 다음 중 하나를 만족한다:
단계 수는 formula_52이고, 필요한 정확도 자릿수는 "p" := 8"N"이다.
다른 타원체.
또한 외접 타원체와 내접 타원체 방법 사이에도 구별이 있다.
이 방법들은 실행 시간 복잡도(아래에서 n은 변수의 수이고 엡실론은 정확도)에서 차이가 있다:
이 방법들의 상대적 효율성은 분리 초평면을 찾는 데 필요한 시간에 따라 달라지며, 이는 응용 분야에 따라 다르다: 실행 시간이 formula_58이고 formula_59이면 외접 방법이 더 효율적이지만, formula_60이면 내접 방법이 더 효율적이다.