SDP의 이중 문제에 대한 도움말

3
Vicente Merino 2018-11-02 23:24.

Semidefinite 프로그래밍 문제의 이중을 찾는 데 문제가 있습니다.

$$\min\;\;(tr(U)+tr(V))/2$$

$$s.t.\;\; \left[ \begin{array}{cc} U & X \\ X^T & V \end{array} \right]\succeq0$$

$$X_{ij}=M_{ij}\;\;(i,j)\in\Omega$$

어디 $tr()$ 추적 연산자입니다. $U, V$$X$ 문제의 행렬 변수이며 $M$ 주어진 행렬입니다.

일반 SDP에는 다음과 같은 Primal Dual 쌍이있는 것으로 알려져 있습니다.

$$P) \;\; \min \;\; tr(C^TX)$$

$$s.t.\;\; tr(A_{i}^TX)=b_i\;\;i=1,...,m$$ $$X\succeq 0$$

$$D)\;\; \max b^Ty$$

$$s.t.\;\; \sum_{i=1}^{m}A_iy_i + S = C $$ $$S\succeq0$$

하지만 내 문제를이 양식으로 수정하는 방법을 찾을 수 없습니다.

1 answers

4
Soroosh Shafiee 2018-11-06 01:09.

모든 것을 표준 형식으로 변환하기 만하면됩니다. 표준 형식으로 원시 문제를 작성하는 것은 쉽습니다. 사실, 우리는 설정할 수 있습니다

$$ C = \left[ \begin{array}{cc} I/2 & 0 \\ 0 & I/2 \end{array} \right], A_k = \left[ \begin{array}{cc} 0 & 1_{ij}/2 \\ 1_{ji}/2 & 0 \end{array} \right], b_k = M_{ij}, \forall (i,j) \in \Omega.$$

따라서 이중은 $$ \max ~ tr(Y, M) $$ $$ s.t. ~ \left[ \begin{array}{cc} I/2 & -Y/2 \\ -Y^\top/2 & I/2 \end{array} \right] \succeq 0$$ 어디 $M$ 다음과 같은 경우 요소가 0 인 행렬입니다. $(i,j) \notin \Omega$ 그렇지 않으면 $M_{ij}$.

Related questions

MORE COOL STUFF

케이트 블란쳇, 3일 만에 남편과 잤고 25년 만에 여전히 결혼

케이트 블란쳇, 3일 만에 남편과 잤고 25년 만에 여전히 결혼

케이트 블란쳇은 남편을 만났을 때 전형적인 데이트 조언을 무시했습니다.

마이클 쉰이 비영리 배우인 이유

마이클 쉰이 비영리 배우인 이유

Michael Sheen은 비영리 배우이지만 정확히 무엇을 의미합니까?

Hallmark Star Colin Egglesfield는 RomaDrama Live에서 스릴 넘치는 팬과의 만남을 제공합니다! [독점적인]

Hallmark Star Colin Egglesfield는 RomaDrama Live에서 스릴 넘치는 팬과의 만남을 제공합니다! [독점적인]

Hallmark 스타 Colin Egglesfield는 RomaDrama Live에서 스릴 넘치는 팬 만남에 대해 설명했습니다! 그리고 대회에서의 그의 INSPIRE 프로그램.

'북부 노출'을 온라인으로 스트리밍할 수 없는 이유

'북부 노출'을 온라인으로 스트리밍할 수 없는 이유

Northern Exposure가 90년대의 가장 인기 있는 쇼 중 하나가 된 이유를 알아보려면 Blu-ray 또는 DVD 플레이어의 먼지를 털어내야 합니다.

신장 결석은 고통스럽지만 통증의 원인은 놀랍습니다.

신장 결석은 고통스럽지만 통증의 원인은 놀랍습니다.

신장 결석이 있으면 등을 찔린 것처럼 느낄 수 있습니다. 그러나 그것이 타는 듯한 고통을 일으키는 돌인가 아니면 다른 무엇인가?

깨끗한 물을 유지하기 위해 머리카락을 기부하세요

깨끗한 물을 유지하기 위해 머리카락을 기부하세요

미용실에서 깎은 머리카락과 개인 기부금은 유출된 기름을 흡수하고 환경을 보호하는 매트로 용도를 변경할 수 있습니다.

백악관에서 가장 기억에 남는 결혼식 살펴보기

백악관에서 가장 기억에 남는 결혼식 살펴보기

지난 200여 년 동안 백악관에서 결혼한 사람은 극소수에 불과합니다. 그들은 누구이며 결혼식을 성사시키기 위해 필요한 것은 무엇입니까?

흰색, 빨간색 또는 분홍색 중 가장 달콤한 자몽은 무엇입니까?

흰색, 빨간색 또는 분홍색 중 가장 달콤한 자몽은 무엇입니까?

과즙이 많은 자몽을 먹을 생각만 하면 입이 떡벌어지나요? 자몽에는 몸에 필요한 비타민과 항산화제가 풍부하기 때문에 주무르세요.

헤이 NFL, Joe Burrow와 Kyler Murray는 여성의 권리를 지원하는 데 약간의 도움을 줄 수 있습니다

헤이 NFL, Joe Burrow와 Kyler Murray는 여성의 권리를 지원하는 데 약간의 도움을 줄 수 있습니다

Joe Burrow Roe v. Wade의 전복에 대해 아무 말도 하지 않음으로써 NFL이 응답한 것은 황당하지만 예측 가능한 PR 결과였습니다.

또 다른 날, 또 다른 unhinged LIV 기자 회견

또 다른 날, 또 다른 unhinged LIV 기자 회견

(L부터) Pat Perez, Brooks Koepka 및 Patrick Reed 사우디 아라비아의 LIV 골프 리그에 대한 또 다른 믿을 수 없는 기자 회견에서 스포츠 팬들은 Brooks Koepka로부터 헛소리를 내뱉고 질문을 회피하는 놀라운 마스터 클래스를 받았습니다. 패트릭 리드(Patrick Reed), 브라이슨 디섐보(Bryson DeChambeau), 팻 페레즈(Pat Perez)는 가장 최근에 PGA 투어에서 이탈한 사람들입니다.

Ms. Marvel의 가족 동창회는 악당보다 더 강타합니다.

Ms. Marvel의 가족 동창회는 악당보다 더 강타합니다.

Red Dagger와 Ms. Marvel은 협력합니다.

Three Arrows Capital, 6억 7500만 달러 비트코인 ​​대출 불이행 후 모든 자산 청산 명령

Three Arrows Capital, 6억 7500만 달러 비트코인 ​​대출 불이행 후 모든 자산 청산 명령

크립토 업계에서 가장 큰 침몰선 중 하나인 쓰리 애로우 캐피털(Three Arrows Capital)이 마침내 그 불행에서 벗어났습니다. 화요일, 부실한 크립토 헤지 펀드가 버진 아일랜드 법원에 의해 청산 명령을 받았습니다. 3AC에 대출을 했습니다.

Azealia Banks, 마이크 던지고 마이애미 프라이드 공연에서 폭풍 : '여기에 서게 되어 정말 기쁘지 않습니다'

Azealia Banks, 마이크 던지고 마이애미 프라이드 공연에서 폭풍 : '여기에 서게 되어 정말 기쁘지 않습니다'

"Wynwood Pride는 너무 빈민가였습니다. 나는 튕겨야 했습니다." Azealia Banks는 그녀가 공연 도중 무대 밖으로 돌진한 후 트위터에 썼습니다.

그리스 2의 캐스트: 그들은 지금 어디에 있습니까?

그리스 2의 캐스트: 그들은 지금 어디에 있습니까?

개봉 40년이 지난 지금, 그리스 2의 출연진을 만나보세요.

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

Sunset's Maya Vander를 매각하여 마이애미에서 자신의 부동산 회사를 시작합니다: '우리가 인수합니다'

Sunset's Maya Vander를 매각하여 마이애미에서 자신의 부동산 회사를 시작합니다: '우리가 인수합니다'

Maya Vander는 Netflix의 Selling Sunset의 첫 5개 시즌에 Oppenheim Group의 부동산 중개인으로 출연했습니다.

Suffragettes Indicam #3: Junho

Suffragettes Indicam #3: Junho

Mais um mês se findando — e metade do ano de 2022 já passou. Sabe o que isso significa? Não, não é hora de verificar se você está cumprindo com suas resoluções de Ano Novo.

Calin (Estudo de Caso UX/UI Design)

Calin (Estudo de Caso UX/UI Design)

Este projeto foi desenvolvido a partir de briefing fictício disponibilizado pelo site Tifólio, uma plataforma para designers. Briefing Matriz CSD Como ponto inicial utilizei como base algumas notícias atuais sobre meios de pagamento digital e com essas informações desenvolvi a Matriz CSD.

Times para plataformizar a produtividade das pessoas desenvolvedoras

Times para plataformizar a produtividade das pessoas desenvolvedoras

Plataformas Internas de Desenvolvimento (abreviado para IDP em inglês) provavelmente é a palavra-chave que você mais ouviu recentemente, mas por que isso se tornou uma forte tendência para empresas em momento de hiper-crescimento? Estive no The Developer’s Conference em Florianópolis no começo deste mês (03 de junho), falando um pouco mais sobre as motivações por trás de um IDP e como estamos endereçando esse assunto aqui no PicPay. Rotatividade e Onboarding Quando foi a última vez que alguém entrou no time em que você está atuando?Imagino que o período não passe por mais de 3 meses, sim, estamos em um momento de alta rotação de profissionais de TI, uma pesquisa do Gartner aponta que até o final de 2022, aproximademente 37 milhões de pessoas irão sair voluntariamente da empresa que atuam.

Este texto foi escrito por uma IA

Este texto foi escrito por uma IA

Eu adorei (não) escrever este texto! Você acreditaria se eu te dissesse que isso aqui foi escrito, em sua maioria, por uma Inteligência Artificial? Pois é, acredite ou não, mas é verdade! Não se assuste caso algo aleatório apareça ao decorrer deste texto ou que as informações sejam favoráveis para essa tecnologia… Inclusive, te desafio a encontrar o que foi eu e o que foi a máquina rs A inteligência artificial já é usada para criar textos, músicas e até filmes. Mas como ela consegue fazer isso? A inteligência artificial cria esses textos, músicas e filmes usando algoritmos.

Language