Witsenhausen's counterexample

Witsenhausen's counterexample, shown in the figure below, is a deceptively simple toy problem in decentralized stochastic control. It was formulated by Hans Witsenhausen in 1968.[1] It is a counterexample to a natural conjecture that one can generalize a key result of centralized linear–quadratic–Gaussian control systems—that in a system with linear dynamics, Gaussian disturbance, and quadratic cost, affine (linear) control laws are optimal—to decentralized systems. Witsenhausen constructed a two-stage linear quadratic Gaussian system where two decisions are made by decision makers with decentralized information and showed that for this system, there exist nonlinear control laws that outperform all linear laws. The problem of finding the optimal control law remains unsolved.[2]

Statement of the counterexample

The statement of the counterexample is simple: two controllers attempt to control the system by attempting to bring the state close to zero in exactly two time steps. The first controller observes the initial state There is a cost on the input of the first controller, and a cost on the state after the input of the second controller. The input of the second controller is free, but it is based on noisy observations of the state after the first controller's input. The second controller cannot communicate with the first controller and thus cannot observe either the original state or the input of the first controller. Thus the system dynamics are

with the second controller's observation equation

The objective is to minimize an expected cost function,

where the expectation is taken over the randomness in the initial state and the observation noise , which are distributed independently. The observation noise is assumed to be distributed in a Gaussian manner, while the distribution of the initial state value differs depending on the particular version of the problem.

The problem is to find control functions

that give at least as good a value of the objective function as do any other pair of control functions. Witsenhausen showed that the optimal functions and cannot be linear.

Specific results of Witsenhausen

Witsenhausen obtained the following results:

  • An optimum exists (Theorem 1).
  • The optimal control law of the first controller is such that (Lemma 9).
  • The exact solution is given for the case in which both controllers are constrained to be linear (Lemma 11).
  • If has a Gaussian distribution and if at least one of the controllers is constrained to be linear, then it is optimal for both controllers to be linear (Lemma 13).
  • The exact nonlinear control laws are given for the case in which has a two-point symmetric distribution (Lemma 15).
  • If has a Gaussian distribution, for some values of the preference parameter a non-optimal nonlinear solution for the control laws is given which gives a lower value for the expected cost function than does the best linear pair of control laws (Theorem 2).

The significance of the problem

The counterexample lies at the intersection of control theory and information theory. Due to its hardness, the problem of finding the optimal control law has also received attention from the theoretical computer science community. The importance of the problem was reflected upon in the 47th IEEE Conference on Decision and Control (CDC) 2008, Cancun, Mexico,[2] where an entire session was dedicated to understanding the counterexample 40 years after it was first formulated.

The problem is of conceptual significance in decentralized control because it shows that it is important for the controllers to communicate[3] with each other implicitly in order to minimize the cost. This suggests that control actions in decentralized control may have a dual role: those of control and communication.

The hardness of the problem

The hardness of the problem is attributed to the fact that information of the second controller depends on the decisions of the first controller.[4] Variations considered by Tamer Basar[5] show that the hardness is also because of the structure of the performance index and the coupling of different decision variables. It has also been shown that problems of the spirit of Witsenhausen's counterexample become simpler if the transmission delay along an external channel that connects the controllers is smaller than the propagation delay in the problem. However, this result requires the channels to be perfect and instantaneous,[6] and hence is of limited applicability. In practical situations, the channel is always imperfect, and thus one can not assume that decentralized control problems are simple in presence of external channels.

A justification of the failure of attempts that discretize the problem came from the computer science literature: Christos Papadimitriou and John Tsitsiklis showed that the discrete version of the counterexample is NP-complete.[7]

Attempts at obtaining a solution

A number of numerical attempts have been made to solve the counterexample. Focusing on a particular choice of problem parameters , researchers have obtained strategies by discretization and using neural networks.[8] Further research (notably, the work of Yu-Chi Ho,[9] and the work of Li, Marden and Shamma[10]) has obtained slightly improved costs for the same parameter choice. The best known numerical results for a variety of parameters, including the one mentioned previously, are obtained by a local search algorithm proposed by S.-H. Tseng and A. Tang in 2017.[11] The first provably approximately optimal strategies appeared in 2010 (Grover, Park, Sahai) [12] where information theory is used to understand the communication in the counterexample. The optimal solution of the counterexample is still an open problem.

References

  1. ^ Witsenhausen, Hans. "A counterexample in stochastic optimum control." SIAM J. Control, Volume 6, Issue 1, pp. 131–147 (February 1968)
  2. ^ a b Ho, Yu-Chi, "Review of the Witsenhausen problem". Proceedings of the 47th IEEE Conference on Decision and Control (CDC), pp. 1611–1613, 2008.
  3. ^ Mitterrand and Sahai. "Information and Control: Witsenhausen revisited". Learning, control and hybrid systems, 1999, Springer.
  4. ^ Ho, Yu-Chi. "Team decision theory and information structures". Proceedings of the IEEE, Vol. 68, No.6, June 1980.
  5. ^ Basar, Tamer. "Variations on the theme of the Witsenhausen counterexample". 47th IEEE Conference on Decision and Control Cancun, Mexico, Dec. 9–11, 2008.
  6. ^ Rotkowitz, M.; Cogill, R.; Lall, S.; "A Simple Condition for the Convexity of Optimal Control over Networks with Delays," Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC '05. 44th IEEE Conference on, pp. 6686–6691, 12–15 December 2005.
  7. ^ Christos Papadimitriou and John Tsitsiklis. "Intractable problems in control theory." 24th IEEE Conference on Decision and Control, 1985
  8. ^ Baglietto, Parisini, and Zoppoli. "Numerical solutions to the Witsenhausen counterexample by approximating networks." IEEE Transactions on Automatic Control. 2001.
  9. ^ Lee, Lau, and Ho. "The Witsenhausen counterexample: A hierarchical search approach for nonconvex optimization problems." IEEE Transactions on Automatic Control, 2001
  10. ^ Li, Marden, and Shamma. "Learning approaches to the Witsenhausen counterexample from a view of potential games." IEEE Conference on Decision and Control, 2009.
  11. ^ Tseng and Tang. "A Local Search Algorithm for the Witsenhausen's Counterexample." IEEE Conference on Decision and Control, 2017.
  12. ^ Grover, Sahai, and Park. "The finite-dimensional Witsenhausen counterexample." IEEE WiOpt 2010, ConCom workshop, Seoul, Korea.

Read other articles:

Questa voce sugli argomenti centri abitati del Nuovo Messico e basi militari è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Cannon Air Force BaseCDP(EN) Cannon Air Force Base Cannon Air Force Base – Veduta LocalizzazioneStato Stati Uniti Stato federato Nuovo Messico ConteaCurry TerritorioCoordinate34°22′58″N 103°19′20″W / 34.382778°N 103.322222°W34.382778; -103.32...

 

Not to be confused with Nelson Mandela Bridge. This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Nelson Mandela Bridges – news · newspapers · books · scholar · JSTOR (September 2011) (Learn how and when to remove this template message) 48°49′13″N 2°23′58″E / 48.82028°N 2.39944°E / 48.82028; 2...

 

Football tournament season 2016 NCAA Division I Field Hockey ChampionshipTournament detailsCountry United StatesTeams18Final positionsChampionsDelaware (1st title)Runner-upNorth Carolina (17th title match)Tournament statisticsMatches played17Goals scored68 (4 per match)← 20152017 →This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to a...

Сіндзі Окадзакі Сіндзі Окадзакі Особисті дані Народження 16 квітня 1986(1986-04-16) (37 років)   Такарадзука, Японія Зріст 173 см Вага 70 кг Громадянство  Японія Позиція нападник Інформація про клуб Поточний клуб «Уеска» Номер 12 Професіональні клуби* Роки Клуб І (г) 2005–2011 «...

 

Лераб Лінг, Монпельє, в Окситанії. Буддизм[a] є третьою за величиною релігією у Франції після християнства та ісламу. [1] У Франції є понад двісті центрів буддійської медитації, у тому числі близько двадцяти значних ретрит центрів у сільській місцевості. Буддистськ...

 

Aleksandr TkachyovАлекса́ндр Ткачёв Informações pessoais Nome completo Aleksandr Vasilyevich Tkachyov Apelido Tkachev Modalidade Ginástica artística masculina Especialidade barra fixa Representante União Soviética Nascimento 4 de novembro de 1957 (66 anos)Semiluki - Voronezh Oblast, Rússia(ex-União Soviética) Nacionalidade russo Compleição Peso: 62 kg • Altura: 1,69 m Nível sênior Clube Dynamo Moscow Período em atividade 1975–1983 Medalhas Compe...

Choi Ji-ann Choi Ji-ann atau Choi Jae-woo (lahir 30 September 1997) adalah seorang penyanyi dan penari asal Korea Selatan. Ia tergabung dalam grup vokal laki-laki New Kidd. Ia merupakan mantan magang RBW. Ia pernah mengikuti program Produce 101 Season 2, namun sayangnya ia tereliminasi dengan menduduki peringkat ke-97. Ia sempat dipersiapkan untuk debut bersama RBW Boyz atau yang kini dikenal dengan nama Oneus, namun akhirnya ia memilih pindah ke J-Flo Entertainment.[1] Referensi ^ 7 ...

 

Lulu Kennedy-Cairns OBE (nama lahir Marie McDonald McLaughlin Lawrie; lahir 3 November 1948) adalah seorang penyanyi-penulis lagu asal Skotlandia. Ia dikenal karena memenangkan Kontes Lagu Eurovision dengan lagu Boom Bang-a-Bang Referensi Daftar pustaka Lulu, I Don't Want to Fight, TimeWarner Books, 2002 Lulu, Secrets To Looking Good, Harper Collins, 2010 Pranala luar Wikiquote memiliki koleksi kutipan yang berkaitan dengan: Lulu (penyanyi). Situs web resmi Lulu's Place Lulu Brit Award Petiti...

 

Municipality in Batangas, Philippines Municipality in Calabarzon, PhilippinesSan JuanMunicipalityMunicipality of San JuanGen. Luna Street, the town proper's main thoroughfare FlagSealMotto: Sama-sama Tayo sa Napapanahong PagbabagoAnthem: Bagong Araw (New Day)Map of Batangas with San Juan highlightedOpenStreetMapSan JuanLocation within the PhilippinesCoordinates: 13°49′34″N 121°23′46″E / 13.826°N 121.396°E / 13.826; 121.396CountryPhilippinesRegionCalaba...

Aktuelles Logo von Epic Records Epic Records ist ein US-amerikanisches Musiklabel. Zu den bekanntesten Künstlern, die bei Epic unter Vertrag stehen oder standen, zählen Fifth Harmony, Camila Cabello, Judas Priest, Rage Against the Machine, The Jacksons, Michael Jackson, Mariah Carey, Bethany Joy Lenz, Anastacia, Tori Amos, Fiona Apple, Future, Avril Lavigne, Good Charlotte, Tenacious D, Shakira und The Nightwatchman. Geschichte Epic wurde 1953 vom US-amerikanischen TV-Riesen und Mediennetzw...

 

2016 bombing in Karrada, Iraq July 2016 Karrada bombingPart of the War in IraqImmediate aftermath of the bombing, with smoke spewing from inside the buildingLocationKarrada, Baghdad, IraqDate3 July 2016; 7 years ago (2016-07-03) 00:05 AST (UTC+03)TargetWestern-style shopping centre in a multicultural & multi-faith district of Baghdad.Attack typeTruck bombing, suicide bombingDeaths347+[1][2]Injured250+Perpetrator Islamic State of Iraq and the Levant&#...

 

المركز الوطني للصحة التكميلية والتكاملية تفاصيل الوكالة الحكومية البلد الولايات المتحدة  تأسست 1991  المركز بيثيسدا  الإدارة موقع الويب الموقع الرسمي  تعديل مصدري - تعديل   المركز الوطني للصحة التكميلية والتكاملية (إن سي سي آي إتش) (بالإنجليزية  National Center for Compl...

DuckGeografiaPaís  Estados UnidosEstado Carolina do NorteCounty of North Carolina Condado de DareÁrea 9,63 km2Área da água 35,02 %Altitude 4 mCoordenadas 36° 10′ 11″ N, 75° 45′ 19″ ODemografiaPopulação 742 hab. (2020)Densidade 77,1 hab./km2 (2020)FuncionamentoEstatuto vila dos Estados Unidos (en)HistóriaFundação 1 de maio de 2002IdentificadoresCódigo postal 27949Code FIPS 37-18060GNIS 10252922406400TGN 2074386Prefixo telefônico 252Website (en) ...

 

Japanese composer and conductor (1925–1989) This biography needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this biography. Unsourced material may be challenged and removed.Find sources: Yasushi Akutagawa – news · newspapers · books · scholar · JSTOR (January 2009) (Learn how and when to remove this template message) Yasushi AkutagawaYasushi AkutagawaBorn(1925-07-12)July 12, ...

 

Cushitic ethnic group in Ethiopia and Eritrea SahoሳሆTotal population250,000–650,000 (2015 estimate)[1]Regions with significant populations Eritrea253,000 (2010 estimate)[2] Ethiopia37,000 (2012 estimate)[3]LanguagesSahoReligionPredominantly Sunni IslamRelated ethnic groupsAfarSomali[4]Cushitic peoples The Saho are a Cushitic ethnic group who inhabit large sections of Eritrea and northern Ethiopia.[5][6] They speak Saho as a mothe...

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Aga Sampoerna – berita · surat kabar · buku · cendekiawan · JSTOR Aga SampoernaInformasi pribadiLahirLiem Swie Ling1915 Surabaya, Jawa Timur, Hindia BelandaMeninggal1994 SingapuraAnakPutera SampoernaOran...

 

Painting by Thomas Eakins The PianistThe Pianist: Portrait of Stanley AddicksYear1896Mediumoil paint, canvasDimensions23.5 in (60 cm) × 19.75 in (50.2 cm)LocationIndianapolis Museum of Art[edit on Wikidata] The Pianist: Portrait of Stanley Addicks is an 1896 oil-on-canvas portrait by the American painter Thomas Eakins. In the catolgue of Eakins's work it is numbered Goodrich #278.[1] The painting is in the permanent collection of the Indianapolis Museum of Art...

 

Kerala State Beverages (M&M) Corporation Ltd. (BEVCO)TypeKerala Public Sector UndertakingIndustryWholesale and Retail trading in IMFL(Indian Made Foreign Liquor), Beer, FMFL(Foreign Made Foreign Liquor)Founded23.02.1984HeadquartersBEVCO Tower, VikasBhavan P.O., Palayam, Thiruvananthapuram 695033, Thiruvananthapuram, KeralaArea servedKeralaKey peopleShri. Yogesh Gupta IPS, Chairman & Managing DirectorRevenue₹14576.21 crore (2021-22) [1] US$ 1.76 billionNumber of employees5,26...

2007 film by Carl Bessai NormalTheatrical release posterDirected byCarl BessaiWritten byCarl BessaiTravis McDonaldProduced byCarl BessaiStarring Carrie-Anne Moss Kevin Zegers Callum Keith Rennie Andrew Airlie Tygh Runyan Camille Sullivan Lauren Lee Smith Michael Riley Britt Irvin Allison Hossack Cameron Bright CinematographyCarl BessaiEdited byLisa BinkleyMusic byClinton ShorterDistributed byMongrel MediaRelease date September 10, 2007 (2007-09-10) Running time100 minutesCountr...

 

Nathan Deal John Nathan Deal (lahir 25 Agustus 1942) adalah seorang jaksa dan politikus Amerika Serikat yang menjabat sebagai Gubernur Georgia ke-82 dari 2011 sampai 2019. Ia terpilih dalam DPR sebagai anggota Partai Demokrat pada 1992 dan beralih ke Partai Republik pada 1995. Pada 1 Maret 2010, Deal mengumumkan pengunduran dirinya untuk maju ke pencalonan Gubernur Georgia. Referensi Pranala luar Wikimedia Commons memiliki media mengenai Nathan Deal. Wikiquote memiliki koleksi kutipan yang be...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!