95:
85:
64:
31:
322:
22:
533:
852:
I propose that the article be amended to remove reference to constraint qualification implying strong duality (Slater's condition can stay, as that claim is true). I think some additional discussion could be included near this statement the describe the general conditions for strong duality, but I am
841:
To give a concrete example, I cannot find any primary source stating that even LICQ (one of the strongest forms of constraint qualification) implies strong duality. This could be because constraint qualification statements do not always assume that the problem is convex, while Slater's condition does
192:
I added in the introduction the most general description of a Dual problem, since associating everything with the
Lagrange dual only for linear program is completely incorrect and misleading. Not only do dual problems exist for non-linear programs, but other types of dual problems exist as
837:
While it is true that Slater's condition implies strong duality, "constraint qualification" is not concerned with duality. Constraint qualification provides circumstances under which KKT conditions (or other first order conditions) are necessary for a primal solution to be a local minima.
508:
Should the
Lagrange dual function come before the dual problem in general? The Lagrange dual is just an example that is frequently utilized but is not "special" mathematically? Perhaps we can come up with a consensus for organization in this talk page before moving everything around.
666:, which is a stub and also quite difficult to read without the background in this article. If it really turns out that duality gap is such a large topic that it deserves a separate article, it would not be difficult to split it out from this article later.
273:
IMHO, the
Lagrangian duality section in this article should be roughly the same size as the linear-programming duality, and it should be larger than the sections on Fenchel duality, Wolfe duality, and surrogate duality. I assume that, similarly, the
176:
Just putting a note here, since I'm not able to deal with it now. Dual problems exist for nonlinear constrained optimization problems as well as linear programming problems. The principle is the same, although the mechanics might be
842:
assume that the primal problem is convex (at least, this is the convention in
Stephen Boyd's book). However, I cannot find any source which states that LICQ for a convex problem implies strong duality.
151:
907:
615:
I think it's basically fine. Before the general non-linear case, there should of course be a discussion of convex objective functions. See also Kiefer.Wolfowitz's comments above.
494:
Done. The article needs some restructuring, however. It should start explaining duality in general, including the
Lagrange dual function, before introducing the dual problem.
532:
for ideas how to structure the article. There are many kinds of duality, but
Lagrangean and Wolfe are perhaps the most important ones. More advanced topics can be found in
897:
834:
The article currently states that "If a constraint qualification such as Slater's condition holds and the original problem is convex, then we have strong duality".
912:
776:
772:
758:
480:
pages earlier today because I didn't think they fit well in this page as it is currently titled/defined, but if expanded then I fully approve of of such a move.
35:
922:
141:
270:
article needs expansion to cover nonlinear programming, linear programming, and combinatorial optimization uses, rather than just smooth optimization.
892:
845:
The most general conditions for strong duality rely on compactness of at least one of the primal feasible region and the dual feasible region. See:
902:
117:
917:
406:
It is the whole objective function that is the
Lagrangian dual function. The expression within parentheses is only the Lagrangian function.
407:
868:
371:
350:
108:
69:
724:
887:
647:
I think is a larger topic because of its use in algorithms and not just the "principle" of it. What does everyone else think?
819:
421:
Thank you for correcting this. By the way, in Boyd/Vandenberghe (chapter 5) an equality constraint is included as well.
44:
215:
for out-siders to understand? Maybe one or two simple examples might greatly help what is actually said ... Thanks,
292:
278:
article has an expanded treatment of LP duality, including primal-dual algorithms and the dual simplex algorithm.
775:
to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the
411:
810:
716:
375:
682:
propose also to define x being Đ„ RN, and saying explicitely that D is the domain where all constraints hold
864:
708:
794:
If you have discovered URLs which were erroneously considered dead by the bot, you can report them with
782:
690:
284:
263:
222:
50:
715:. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit
94:
218:
856:
749:
367:
199:
386:
You are correct. I updated the page in the 1 spot I noticed it said 'upper bound' in that context.
21:
686:
267:
238:
643:
since each of those topics is really inseparable from a discussion of the dual problem. However,
364:
The solution to the dual problem provides a lower bound for the primal problem, not upper bound.
353:
for that content in the latter page, and it must not be deleted as long as the latter page exists.
116:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
853:
not sure if that discussion is better placed in the dedicated Strong
Duality wikipedia article.
275:
259:
194:
100:
779:
before doing mass systematic removals. This message is updated dynamically through the template
84:
63:
795:
860:
671:
652:
620:
605:
540:
524:
514:
499:
485:
462:
457:
into this article, as they don't have much potential for expansion. Comments are appreciated.
426:
391:
308:
246:
182:
725:
https://web.archive.org/web/20110724151508/http://or.journal.informs.org/cgi/reprint/11/3/399
237:
I think the discussion on
Lagrange duality would fit more naturally here than in the article
802:
530:
527:
761:, "External links modified" talk page sections are no longer generated or monitored by
636:
473:
450:
801:
If you found an error with any archives or the URLs themselves, you can fix them with
881:
728:
667:
648:
640:
616:
601:
536:
510:
495:
481:
477:
458:
454:
422:
387:
338:
304:
242:
178:
872:
824:
694:
675:
656:
624:
609:
544:
518:
503:
489:
466:
430:
415:
395:
379:
312:
297:
250:
226:
203:
186:
768:
663:
644:
113:
767:. No special action is required regarding these talk page notices, other than
211:
Could anybody help to make "Problem statement in the linear case" a bit easier
90:
262:
belongs here; you may also include material or consider merger with
846:
402:
expression within parentheses is not the Lagrangian dual function
449:. Then it would be natural to merge the newly created articles
342:
316:
15:
734:
When you have finished reviewing my changes, please set the
719:
for additional information. I made the following changes:
441:
I think this article should have a broader title such as
712:
346:
333:
328:
631:
Proposed merge with strong/weak duality + duality gap
112:, a collaborative effort to improve the coverage of
771:using the archive tool instructions below. Editors
729:http://or.journal.informs.org/cgi/reprint/11/3/399
584:Other Duality Concepts (Wolfe, Fenchel, others?)
908:Knowledge level-5 vital articles in Mathematics
757:This message was posted before February 2018.
662:My proposal was based on the present article
8:
830:Constraint qualification and strong duality
561:Here are my thoughts for the organization:
854:
707:I have just modified one external link on
320:
58:
847:https://en.wikipedia.org/Minimax_theorem
327:Text and/or other creative content from
898:Knowledge vital articles in Mathematics
472:I agree with this idea. I created the
60:
19:
913:C-Class vital articles in Mathematics
746:to let others know (documentation at
7:
579:Non-Linear (mention of weak duality)
106:This article is within the scope of
447:Duality (mathematical optimization)
49:It is of interest to the following
576:Linear (mention of strong duality)
345:on 13 May 2011. The former page's
14:
923:Mid-priority mathematics articles
711:. Please take a moment to review
126:Knowledge:WikiProject Mathematics
893:Knowledge level-5 vital articles
129:Template:WikiProject Mathematics
93:
83:
62:
29:
20:
146:This article has been rated as
903:C-Class level-5 vital articles
1:
825:07:47, 17 December 2016 (UTC)
120:and see a list of open tasks.
918:C-Class mathematics articles
695:23:29, 3 November 2013 (UTC)
625:08:17, 17 January 2012 (UTC)
610:22:58, 16 January 2012 (UTC)
545:21:57, 16 January 2012 (UTC)
519:19:57, 16 January 2012 (UTC)
504:16:33, 16 January 2012 (UTC)
490:21:43, 15 January 2012 (UTC)
467:21:18, 15 January 2012 (UTC)
360:lower bound! not upper bound
227:07:08, 20 October 2009 (UTC)
204:17:35, 14 October 2010 (UTC)
523:I would suggest looking at
431:14:40, 5 January 2012 (UTC)
416:14:04, 5 January 2012 (UTC)
396:14:52, 4 January 2012 (UTC)
380:05:19, 4 January 2012 (UTC)
172:not just linear programming
939:
788:(last update: 5 June 2024)
704:Hello fellow Wikipedians,
873:02:03, 2 April 2017 (UTC)
676:22:58, 8 March 2012 (UTC)
657:22:20, 8 March 2012 (UTC)
635:I support the merge with
337:was copied or moved into
187:23:47, 26 June 2008 (UTC)
145:
78:
57:
313:13:24, 13 May 2011 (UTC)
298:21:28, 12 May 2011 (UTC)
251:21:06, 12 May 2011 (UTC)
152:project's priority scale
700:External links modified
109:WikiProject Mathematics
888:C-Class vital articles
709:Duality (optimization)
443:Duality (optimization)
264:Lagrangian relaxation
36:level-5 vital article
769:regular verification
132:mathematics articles
759:After February 2018
738:parameter below to
600:What do you think?
573:Lagrangian Duality
568:Weak/Strong Duality
351:provide attribution
334:Lagrange multiplier
268:Lagrange multiplier
239:Lagrange multiplier
813:InternetArchiveBot
764:InternetArchiveBot
565:Duality Principle
303:Merger performed.
276:linear programming
260:Lagrangian duality
241:. Any objections?
101:Mathematics portal
45:content assessment
875:
859:comment added by
789:
370:comment added by
357:
356:
296:
166:
165:
162:
161:
158:
157:
930:
823:
814:
787:
786:
765:
753:
557:New Organization
382:
336:
324:
323:
317:
295:
289:
282:
207:
134:
133:
130:
127:
124:
103:
98:
97:
87:
80:
79:
74:
66:
59:
42:
33:
32:
25:
24:
16:
938:
937:
933:
932:
931:
929:
928:
927:
878:
877:
832:
817:
812:
780:
773:have permission
763:
747:
717:this simple FaQ
702:
633:
559:
439:
404:
365:
362:
332:
321:
285:
283:
235:
233:Proposed merger
213:
197:
174:
131:
128:
125:
122:
121:
99:
92:
72:
43:on Knowledge's
40:
30:
12:
11:
5:
936:
934:
926:
925:
920:
915:
910:
905:
900:
895:
890:
880:
879:
831:
828:
807:
806:
799:
732:
731:
723:Added archive
701:
698:
684:
683:
679:
678:
632:
629:
628:
627:
598:
597:
594:
591:
588:
585:
582:
581:
580:
577:
571:
570:
569:
558:
555:
554:
553:
552:
551:
550:
549:
548:
547:
474:strong duality
451:Strong duality
438:
437:Requested move
435:
434:
433:
403:
400:
399:
398:
361:
358:
355:
354:
349:now serves to
325:
301:
300:
281:Best regards,
279:
271:
257:
234:
231:
212:
209:
202:comment added
173:
170:
168:
164:
163:
160:
159:
156:
155:
144:
138:
137:
135:
118:the discussion
105:
104:
88:
76:
75:
67:
55:
54:
48:
26:
13:
10:
9:
6:
4:
3:
2:
935:
924:
921:
919:
916:
914:
911:
909:
906:
904:
901:
899:
896:
894:
891:
889:
886:
885:
883:
876:
874:
870:
866:
862:
858:
850:
848:
843:
839:
835:
829:
827:
826:
821:
816:
815:
804:
800:
797:
793:
792:
791:
784:
778:
774:
770:
766:
760:
755:
751:
745:
741:
737:
730:
726:
722:
721:
720:
718:
714:
710:
705:
699:
697:
696:
692:
688:
681:
680:
677:
673:
669:
665:
661:
660:
659:
658:
654:
650:
646:
642:
638:
630:
626:
622:
618:
614:
613:
612:
611:
607:
603:
595:
592:
589:
586:
583:
578:
575:
574:
572:
567:
566:
564:
563:
562:
556:
546:
542:
538:
534:
531:
528:
525:
522:
521:
520:
516:
512:
507:
506:
505:
501:
497:
493:
492:
491:
487:
483:
479:
475:
471:
470:
469:
468:
464:
460:
456:
452:
448:
444:
436:
432:
428:
424:
420:
419:
418:
417:
413:
409:
408:147.8.182.107
401:
397:
393:
389:
385:
384:
383:
381:
377:
373:
369:
359:
352:
348:
344:
340:
335:
330:
326:
319:
318:
315:
314:
310:
306:
299:
294:
290:
288:
280:
277:
272:
269:
265:
261:
258:
255:
254:
253:
252:
248:
244:
240:
232:
230:
228:
224:
220:
216:
210:
208:
205:
201:
196:
189:
188:
184:
180:
171:
169:
153:
149:
143:
140:
139:
136:
119:
115:
111:
110:
102:
96:
91:
89:
86:
82:
81:
77:
71:
68:
65:
61:
56:
52:
46:
38:
37:
27:
23:
18:
17:
861:Rileyjmurray
855:— Preceding
851:
844:
840:
836:
833:
811:
808:
783:source check
762:
756:
743:
739:
735:
733:
706:
703:
685:
641:weak duality
634:
599:
560:
478:weak duality
455:Weak duality
446:
442:
440:
405:
372:147.8.182.48
366:— Preceding
363:
339:Dual problem
329:this version
302:
286:
236:
229:true_bsmile
217:
214:
190:
175:
167:
148:Mid-priority
147:
107:
73:Mid‑priority
51:WikiProjects
34:
750:Sourcecheck
664:duality gap
645:duality gap
256:Hi Isheden!
219:True bsmile
198:—Preceding
123:Mathematics
114:mathematics
70:Mathematics
882:Categories
820:Report bug
596:References
177:different.
803:this tool
796:this tool
343:this edit
293:Wolfowitz
39:is rated
869:contribs
857:unsigned
809:Cheers.—
687:Rramberg
590:See Also
368:unsigned
736:checked
713:my edit
668:Isheden
649:Zfeinst
617:Isheden
602:Zfeinst
587:History
537:Isheden
511:Zfeinst
496:Isheden
482:Zfeinst
459:Isheden
423:Isheden
388:Zfeinst
347:history
305:Isheden
243:Isheden
200:undated
193:well...
191:--: -->
179:Cretog8
150:on the
41:C-class
744:failed
637:strong
529:, and
287:Kiefer
266:. The
195:q4444q
47:scale.
593:Notes
341:with
28:This
865:talk
740:true
691:talk
672:talk
653:talk
639:and
621:talk
606:talk
541:talk
515:talk
500:talk
486:talk
476:and
463:talk
453:and
427:talk
412:talk
392:talk
376:talk
309:talk
247:talk
223:talk
183:talk
777:RfC
754:).
742:or
727:to
445:or
331:of
142:Mid
884::
871:)
867:•
849:.
790:.
785:}}
781:{{
752:}}
748:{{
693:)
674:)
655:)
623:)
608:)
543:)
535:.
526:,
517:)
502:)
488:)
465:)
429:)
414:)
394:)
378:)
311:)
249:)
225:)
185:)
863:(
822:)
818:(
805:.
798:.
689:(
670:(
651:(
619:(
604:(
539:(
513:(
498:(
484:(
461:(
425:(
410:(
390:(
374:(
307:(
291:.
245:(
221:(
206:.
181:(
154:.
53::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
