อ่าน 1 นาที
ความเป็นคู่ที่แข็งแกร่ง
ภาวะ ทวิลักษณ์ที่แข็งแกร่ง (Strong duality) เป็นเงื่อนไขใน การหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ ซึ่งค่าเป้าหมายที่เหมาะสมที่สุดในปัญหาหลักและ ค่าเป้าหมายที่เหมาะสมที่สุดในปัญหา คู่...
ความเป็นคู่ที่แข็งแกร่ง
ภาวะ ทวิลักษณ์ที่แข็งแกร่ง (Strong duality)เป็นเงื่อนไขในการหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ซึ่งค่าเป้าหมายที่เหมาะสมที่สุดในปัญหาหลักและ ค่าเป้าหมายที่เหมาะสมที่สุดในปัญหา คู่ ขนานนั้น เท่ากัน ตามคำนิยาม ภาวะทวิลักษณ์ที่แข็งแกร่งจะเป็นจริงก็ต่อเมื่อช่องว่างทวิลักษณ์ (Duality gap ) เท่ากับ 0 เท่านั้น ซึ่งตรงข้ามกับภาวะทวิลักษณ์ที่อ่อนแอ (Weak duality ) (ปัญหาหลักมีค่าเหมาะสมที่สุดมากกว่าหรือเท่ากับปัญหาคู่ขนาน กล่าวอีกนัยหนึ่ง คือ ช่องว่างทวิลักษณ์มากกว่าหรือเท่ากับศูนย์)
เงื่อนไขที่เพียงพอ
เงื่อนไขแต่ละข้อต่อไปนี้เพียงพอที่จะทำให้ทฤษฎีทวิภาวะแบบเข้มแข็ง (strong duality) เป็นจริงได้:
- โดยที่คือฟังก์ชันการรบกวนที่เชื่อมโยงปัญหาหลักและปัญหาคู่ และคือคู่สังยุคของ(ซึ่งได้มาจากการสร้างช่องว่างทวิภาวะ )
- เป็นฟังก์ชันนูนและกึ่งต่อเนื่อง ล่าง (เทียบเท่ากับจุดแรกตามทฤษฎีบทเฟนเชล-โมโร )
- ปัญหาหลักคือปัญหาการหาค่าเหมาะสมที่สุดเชิงเส้น
- เงื่อนไขของ Slaterสำหรับปัญหาการหาค่าเหมาะสมที่สุดแบบนูน[ 1 ] [ 2 ]
ความเป็นคู่ที่แข็งแกร่งและความซับซ้อนในการคำนวณ
ภายใต้เงื่อนไขบางประการ (เรียกว่า "คุณสมบัติข้อจำกัด") หากปัญหาสามารถแก้ไขได้ในเวลาพหุนาม ปัญหานั้นก็จะมีภาวะคู่ที่แข็งแกร่ง (ในความหมายของภาวะคู่แบบลากรางจ์ ) ยังคงเป็นคำถามที่เปิดกว้างว่าทิศทางตรงกันข้ามก็เป็นจริงด้วยหรือไม่ กล่าวคือ ภาวะคู่ที่แข็งแกร่งจะหมายถึงการแก้ไขได้ในเวลาพหุนามหรือไม่[ 3 ]
ดูเพิ่มเติม
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ ความเป็นคู่ที่แข็งแกร่ง
ภาวะ ทวิลักษณ์ที่แข็งแกร่ง (Strong duality) เป็นเงื่อนไขใน การหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ ซึ่งค่าเป้าหมายที่เหมาะสมที่สุดในปัญหาหลักและ ค่าเป้าหมายที่เหมาะสมที่สุดในปัญหา คู่...
เงื่อนไขที่เพียงพอ
เงื่อนไขแต่ละข้อต่อไปนี้เพียงพอที่จะทำให้ทฤษฎีทวิภาวะแบบเข้มแข็ง (strong duality) เป็นจริงได้:
ความเป็นคู่ที่แข็งแกร่งและความซับซ้อนในการคำนวณ
ภายใต้เงื่อนไขบางประการ (เรียกว่า "คุณสมบัติข้อจำกัด") หากปัญหาสามารถแก้ไขได้ในเวลาพหุนาม ปัญหานั้นก็จะมีภาวะคู่ที่แข็งแกร่ง (ในความหมายของ ภาวะคู่แบบลากรางจ์ ) ยังคงเป็นคำถามที่เปิดกว้างว่าทิศทางตรงกันข้ามก็เป็นจริงด้วยหรือไม่ กล่าวคือ...
ดูเพิ่มเติม
การเพิ่มประสิทธิภาพแบบนูน การเขียนโปรแกรมเชิงเส้น #ความเป็นคู่ โปรแกรมเชิงเส้นคู่ ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Strong_duality&oldid=1322739391 "