1155:) 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. The first provably approximately optimal strategies appeared in 2010 (Grover, Park, Sahai) where
1041:
The problem is of conceptual significance in decentralized control because it shows that it is important for the controllers to communicate 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
1063:
in the problem. However, this result requires the channels to be perfect and instantaneous, 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.
46:
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
1037:
community. The importance of the problem was reflected upon in the 47th IEEE Conference on
Decision and Control (CDC) 2008, Cancun, Mexico, where an entire session was dedicated to understanding the counterexample 40 years after it was first formulated.
1054:
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
62:
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
748:
1137:
1016:
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).
47:
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.
415:
358:
470:
218:
1050:
The hardness of the problem is attributed to the fact that information of the second controller depends on the decisions of the first controller. Variations considered by
837:
794:
894:
561:
91:
994:
957:
927:
666:
591:
299:
272:
245:
172:
145:
118:
1014:
929:
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).
635:
611:
247:
after the first controller's input. The second controller cannot communicate with the first controller and thus cannot observe either the original state
43:
753:
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
52:
677:
1159:
is used to understand the communication in the counterexample. The optimal solution of the counterexample is still an open problem.
614:
1087:
A number of numerical attempts have been made to solve the counterexample. Focusing on a particular choice of problem parameters
1243:
Rotkowitz, M.; Cogill, R.; Lall, S.; "A Simple
Condition for the Convexity of Optimal Control over Networks with Delays,"
1293:
Lee, Lau, and Ho. "The
Witsenhausen counterexample: A hierarchical search approach for nonconvex optimization problems."
1034:
1359:
1280:
Baglietto, Parisini, and
Zoppoli. "Numerical solutions to the Witsenhausen counterexample by approximating networks."
24:
1067:
A justification of the failure of attempts that discretize the problem came from the computer science literature:
1306:
Li, Marden, and Shamma. "Learning approaches to the
Witsenhausen counterexample from a view of potential games."
1090:
1354:
1033:. Due to its hardness, the problem of finding the optimal control law has also received attention from the
899:
The exact solution is given for the case in which both controllers are constrained to be linear (Lemma 11).
1260:
1068:
963:
960:
364:
307:
426:
638:
177:
799:
756:
1156:
1056:
1030:
27:
857:
485:
1060:
31:
66:
51:
972:
935:
905:
644:
569:
277:
250:
223:
150:
123:
96:
1264:
1144:
1072:
1152:
1140:
1026:
999:
620:
596:
35:
1348:
476:
1319:
Tseng and Tang. "A Local Search
Algorithm for the Witsenhausen's Counterexample."
1076:
1051:
20:
1332:
Grover, Sahai, and Park. "The finite-dimensional
Witsenhausen counterexample."
39:
1230:
Basar, Tamer. "Variations on the theme of the Witsenhausen counterexample".
1148:
1059:
along an external channel that connects the controllers is smaller than the
1204:
Mitterrand and Sahai. "Information and Control: Witsenhausen revisited".
996:
has a Gaussian distribution, for some values of the preference parameter
566:
where the expectation is taken over the randomness in the initial state
174:
of the second controller is free, but it is based on noisy observations
1175:
Witsenhausen, Hans. "A counterexample in stochastic optimum control."
1193:
Proceedings of the 47th IEEE Conference on Decision and Control (CDC)
1249:
European Control Conference. CDC-ECC '05. 44th IEEE Conference on
932:
The exact nonlinear control laws are given for the case in which
743:{\displaystyle u_{1}(x_{0})\quad {\text{and}}\quad u_{2}(y_{1})}
1217:
Ho, Yu-Chi. "Team decision theory and information structures".
854:
The optimal control law of the first controller is such that
668:
differs depending on the particular version of the problem.
1075:
showed that the discrete version of the counterexample is
641:
manner, while the distribution of the initial state value
301:
of the first controller. Thus the system dynamics are
1093:
1002:
975:
938:
908:
860:
802:
759:
680:
647:
623:
599:
572:
488:
429:
367:
310:
280:
253:
226:
180:
153:
126:
99:
69:
19:, shown in the figure below, is a deceptively simple
147:
after the input of the second controller. The input
42:
that one can generalize a key result of centralized
1232:
47th IEEE Conference on Decision and Control Cancun
1191:Ho, Yu-Chi, "Review of the Witsenhausen problem".
1131:
1008:
988:
951:
921:
888:
831:
788:
742:
660:
629:
605:
585:
555:
464:
420:with the second controller's observation equation
409:
352:
293:
266:
239:
212:
166:
139:
112:
85:
120:of the first controller, and a cost on the state
1179:, Volume 6, Issue 1, pp. 131–147 (February 1968)
1025:The counterexample lies at the intersection of
1267:. "Intractable problems in control theory."
847:Witsenhausen obtained the following results:
8:
1269:24th IEEE Conference on Decision and Control
1139:, researchers have obtained strategies by
1109:
1147:. Further research (notably, the work of
1114:
1092:
1001:
980:
974:
943:
937:
913:
907:
871:
859:
820:
807:
801:
777:
764:
758:
731:
718:
708:
698:
685:
679:
671:The problem is to find control functions
652:
646:
622:
598:
577:
571:
541:
536:
514:
509:
493:
487:
475:The objective is to minimize an expected
447:
434:
428:
398:
385:
372:
366:
341:
328:
315:
309:
285:
279:
258:
252:
231:
225:
198:
185:
179:
158:
152:
131:
125:
104:
98:
74:
68:
1321:IEEE Conference on Decision and Control
1308:IEEE Conference on Decision and Control
1168:
1132:{\displaystyle (k=0.2,\;\sigma _{0}=5)}
1295:IEEE Transactions on Automatic Control
1282:IEEE Transactions on Automatic Control
1251:, pp. 6686–6691, 12–15 December 2005.
7:
1206:Learning, control and hybrid systems
1187:
1185:
637:is assumed to be distributed in a
410:{\displaystyle x_{2}=x_{1}-u_{2},}
353:{\displaystyle x_{1}=x_{0}+u_{1},}
14:
1151:, and the work of Li, Marden and
44:linear–quadratic–Gaussian control
1334:IEEE WiOpt 2010, ConCom workshop
1083:Attempts at obtaining a solution
843:Specific results of Witsenhausen
50:
1021:The significance of the problem
713:
707:
58:Statement of the counterexample
1126:
1094:
877:
864:
851:An optimum exists (Theorem 1).
826:
813:
783:
770:
737:
724:
704:
691:
547:
529:
520:
502:
465:{\displaystyle y_{1}=x_{1}+z.}
1:
213:{\displaystyle y_{1}=x_{1}+z}
93:There is a cost on the input
17:Witsenhausen's counterexample
1035:theoretical computer science
832:{\displaystyle u_{2}(y_{1})}
789:{\displaystyle u_{1}(x_{0})}
1221:, Vol. 68, No.6, June 1980.
1046:The hardness of the problem
1376:
1234:, Mexico, Dec. 9–11, 2008.
889:{\displaystyle E(x_{1})=0}
593:and the observation noise
617:. The observation noise
556:{\displaystyle k^{2}E+E,}
613:, which are distributed
1219:Proceedings of the IEEE
30:. It was formulated by
1261:Christos Papadimitriou
1195:, pp. 1611–1613, 2008.
1133:
1069:Christos Papadimitriou
1010:
990:
964:symmetric distribution
953:
923:
890:
833:
790:
744:
662:
631:
607:
587:
557:
466:
411:
354:
295:
268:
241:
214:
168:
141:
114:
87:
86:{\displaystyle x_{0}.}
1134:
1011:
991:
989:{\displaystyle x_{0}}
954:
952:{\displaystyle x_{0}}
924:
922:{\displaystyle x_{0}}
891:
834:
791:
745:
663:
661:{\displaystyle x_{0}}
632:
608:
588:
586:{\displaystyle x_{0}}
558:
467:
412:
355:
296:
294:{\displaystyle u_{1}}
269:
267:{\displaystyle x_{0}}
242:
240:{\displaystyle x_{1}}
215:
169:
167:{\displaystyle u_{2}}
142:
140:{\displaystyle x_{2}}
115:
113:{\displaystyle u_{1}}
88:
1245:Decision and Control
1091:
1000:
973:
936:
906:
858:
800:
757:
678:
645:
621:
597:
570:
486:
427:
365:
308:
278:
251:
224:
178:
151:
124:
97:
67:
546:
519:
1360:Stochastic control
1157:information theory
1129:
1057:transmission delay
1031:information theory
1006:
986:
949:
919:
886:
839:cannot be linear.
829:
786:
740:
658:
627:
603:
583:
553:
532:
505:
462:
407:
350:
291:
264:
237:
210:
164:
137:
110:
83:
28:stochastic control
1208:, 1999, Springer.
1061:propagation delay
1009:{\displaystyle k}
711:
630:{\displaystyle z}
606:{\displaystyle z}
34:in 1968. It is a
32:Hans Witsenhausen
1367:
1337:
1330:
1324:
1317:
1311:
1304:
1298:
1291:
1285:
1278:
1272:
1258:
1252:
1247:, 2005 and 2005
1241:
1235:
1228:
1222:
1215:
1209:
1202:
1196:
1189:
1180:
1173:
1138:
1136:
1135:
1130:
1119:
1118:
1015:
1013:
1012:
1007:
995:
993:
992:
987:
985:
984:
958:
956:
955:
950:
948:
947:
928:
926:
925:
920:
918:
917:
895:
893:
892:
887:
876:
875:
838:
836:
835:
830:
825:
824:
812:
811:
795:
793:
792:
787:
782:
781:
769:
768:
749:
747:
746:
741:
736:
735:
723:
722:
712:
709:
703:
702:
690:
689:
667:
665:
664:
659:
657:
656:
636:
634:
633:
628:
612:
610:
609:
604:
592:
590:
589:
584:
582:
581:
562:
560:
559:
554:
545:
540:
518:
513:
498:
497:
471:
469:
468:
463:
452:
451:
439:
438:
416:
414:
413:
408:
403:
402:
390:
389:
377:
376:
359:
357:
356:
351:
346:
345:
333:
332:
320:
319:
300:
298:
297:
292:
290:
289:
273:
271:
270:
265:
263:
262:
246:
244:
243:
238:
236:
235:
219:
217:
216:
211:
203:
202:
190:
189:
173:
171:
170:
165:
163:
162:
146:
144:
143:
138:
136:
135:
119:
117:
116:
111:
109:
108:
92:
90:
89:
84:
79:
78:
54:
1375:
1374:
1370:
1369:
1368:
1366:
1365:
1364:
1345:
1344:
1341:
1340:
1336:, Seoul, Korea.
1331:
1327:
1318:
1314:
1305:
1301:
1292:
1288:
1279:
1275:
1265:John Tsitsiklis
1259:
1255:
1242:
1238:
1229:
1225:
1216:
1212:
1203:
1199:
1190:
1183:
1177:SIAM J. Control
1174:
1170:
1165:
1145:neural networks
1110:
1089:
1088:
1085:
1073:John Tsitsiklis
1048:
1042:communication.
1023:
998:
997:
976:
971:
970:
939:
934:
933:
909:
904:
903:
867:
856:
855:
845:
816:
803:
798:
797:
773:
760:
755:
754:
727:
714:
694:
681:
676:
675:
648:
643:
642:
619:
618:
595:
594:
573:
568:
567:
489:
484:
483:
443:
430:
425:
424:
394:
381:
368:
363:
362:
337:
324:
311:
306:
305:
281:
276:
275:
254:
249:
248:
227:
222:
221:
194:
181:
176:
175:
154:
149:
148:
127:
122:
121:
100:
95:
94:
70:
65:
64:
60:
12:
11:
5:
1373:
1371:
1363:
1362:
1357:
1355:Control theory
1347:
1346:
1339:
1338:
1325:
1312:
1299:
1286:
1273:
1253:
1236:
1223:
1210:
1197:
1181:
1167:
1166:
1164:
1161:
1141:discretization
1128:
1125:
1122:
1117:
1113:
1108:
1105:
1102:
1099:
1096:
1084:
1081:
1047:
1044:
1027:control theory
1022:
1019:
1018:
1017:
1005:
983:
979:
967:
946:
942:
930:
916:
912:
900:
897:
885:
882:
879:
874:
870:
866:
863:
852:
844:
841:
828:
823:
819:
815:
810:
806:
785:
780:
776:
772:
767:
763:
751:
750:
739:
734:
730:
726:
721:
717:
706:
701:
697:
693:
688:
684:
655:
651:
626:
602:
580:
576:
564:
563:
552:
549:
544:
539:
535:
531:
528:
525:
522:
517:
512:
508:
504:
501:
496:
492:
473:
472:
461:
458:
455:
450:
446:
442:
437:
433:
418:
417:
406:
401:
397:
393:
388:
384:
380:
375:
371:
360:
349:
344:
340:
336:
331:
327:
323:
318:
314:
288:
284:
261:
257:
234:
230:
209:
206:
201:
197:
193:
188:
184:
161:
157:
134:
130:
107:
103:
82:
77:
73:
59:
56:
36:counterexample
13:
10:
9:
6:
4:
3:
2:
1372:
1361:
1358:
1356:
1353:
1352:
1350:
1343:
1335:
1329:
1326:
1322:
1316:
1313:
1309:
1303:
1300:
1296:
1290:
1287:
1283:
1277:
1274:
1270:
1266:
1262:
1257:
1254:
1250:
1246:
1240:
1237:
1233:
1227:
1224:
1220:
1214:
1211:
1207:
1201:
1198:
1194:
1188:
1186:
1182:
1178:
1172:
1169:
1162:
1160:
1158:
1154:
1150:
1146:
1142:
1123:
1120:
1115:
1111:
1106:
1103:
1100:
1097:
1082:
1080:
1078:
1074:
1070:
1065:
1062:
1058:
1053:
1045:
1043:
1039:
1036:
1032:
1028:
1020:
1003:
981:
977:
968:
965:
962:
944:
940:
931:
914:
910:
901:
898:
883:
880:
872:
868:
861:
853:
850:
849:
848:
842:
840:
821:
817:
808:
804:
778:
774:
765:
761:
732:
728:
719:
715:
699:
695:
686:
682:
674:
673:
672:
669:
653:
649:
640:
624:
616:
615:independently
600:
578:
574:
550:
542:
537:
533:
526:
523:
515:
510:
506:
499:
494:
490:
482:
481:
480:
478:
477:cost function
459:
456:
453:
448:
444:
440:
435:
431:
423:
422:
421:
404:
399:
395:
391:
386:
382:
378:
373:
369:
361:
347:
342:
338:
334:
329:
325:
321:
316:
312:
304:
303:
302:
286:
282:
274:or the input
259:
255:
232:
228:
220:of the state
207:
204:
199:
195:
191:
186:
182:
159:
155:
132:
128:
105:
101:
80:
75:
71:
57:
55:
53:
48:
45:
41:
38:to a natural
37:
33:
29:
26:
25:decentralized
22:
18:
1342:
1333:
1328:
1320:
1315:
1307:
1302:
1294:
1289:
1281:
1276:
1268:
1256:
1248:
1244:
1239:
1231:
1226:
1218:
1213:
1205:
1200:
1192:
1176:
1171:
1086:
1066:
1049:
1040:
1024:
846:
752:
670:
565:
474:
419:
61:
49:
16:
15:
1077:NP-complete
1052:Tamer Basar
966:(Lemma 15).
21:toy problem
1349:Categories
1163:References
1143:and using
896:(Lemma 9).
40:conjecture
1149:Yu-Chi Ho
1112:σ
961:two-point
392:−
639:Gaussian
1323:, 2017.
1310:, 2009.
1284:. 2001.
1297:, 2001
1271:, 1985
1153:Shamma
959:has a
1263:and
1071:and
1029:and
796:and
1104:0.2
969:If
902:If
710:and
23:in
1351::
1184:^
1079:.
479:,
1127:)
1124:5
1121:=
1116:0
1107:,
1101:=
1098:k
1095:(
1004:k
982:0
978:x
945:0
941:x
915:0
911:x
884:0
881:=
878:)
873:1
869:x
865:(
862:E
827:)
822:1
818:y
814:(
809:2
805:u
784:)
779:0
775:x
771:(
766:1
762:u
738:)
733:1
729:y
725:(
720:2
716:u
705:)
700:0
696:x
692:(
687:1
683:u
654:0
650:x
625:z
601:z
579:0
575:x
551:,
548:]
543:2
538:2
534:x
530:[
527:E
524:+
521:]
516:2
511:1
507:u
503:[
500:E
495:2
491:k
460:.
457:z
454:+
449:1
445:x
441:=
436:1
432:y
405:,
400:2
396:u
387:1
383:x
379:=
374:2
370:x
348:,
343:1
339:u
335:+
330:0
326:x
322:=
317:1
313:x
287:1
283:u
260:0
256:x
233:1
229:x
208:z
205:+
200:1
196:x
192:=
187:1
183:y
160:2
156:u
133:2
129:x
106:1
102:u
81:.
76:0
72:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
