ในทฤษฎีการหาค่าเหมาะสมที่สุด ทางคณิตศาสตร์ ปัญหาความสมบูรณ์แบบเชิงเส้น (LCP)เกิดขึ้นบ่อยครั้งในกลศาสตร์การคำนวณ และครอบคลุม การเขียนโปรแกรมกำลังสองที่รู้จักกันดีเป็นกรณีพิเศษ ปัญหานี้ได้รับการเสนอโดย Cottle และDantzigในปี 1968 ^{[ 1 ] [ 2 ] [ 3 ]}

เมื่อกำหนดเมทริกซ์จริงMและเวกเตอร์qแล้ว ปัญหาความสมบูรณ์แบบเชิงเส้น LCP( q , M ) จะค้นหาเวกเตอร์zและwที่สอดคล้องกับข้อจำกัดต่อไปนี้:

• ${\displaystyle w,z\geqslant 0,}$(กล่าวคือ ส่วนประกอบแต่ละส่วนของเวกเตอร์ทั้งสองนี้มีค่าไม่เป็นลบ )
• ${\displaystyle z^{T}w=0}$หรือกล่าวอีกนัยหนึ่งนี่คือ เงื่อนไข ความสมบูรณ์แบบเนื่องจากเงื่อนไขนี้บ่งชี้ว่า สำหรับทุกค่าจะมีเพียงหนึ่งในค่าและ เท่านั้นที่จะเป็นค่าบวกได้${\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.}$${\displaystyle i}$${\displaystyle w_{i}}$${\displaystyle z_{i}}$
• ${\displaystyle w=Mz+q}$

เงื่อนไขที่เพียงพอสำหรับการมีอยู่และความเป็นเอกลักษณ์ของคำตอบสำหรับปัญหานี้คือMต้องเป็น เมท ริกซ์สมมาตรบวกแน่นอนถ้าMเป็นเช่นนั้นLCP( q , M )มีคำตอบสำหรับทุกqแล้วMจะเป็นเมทริกซ์ Qถ้าMเป็นเช่นนั้นLCP( q , M )มีคำตอบที่ไม่ซ้ำกันสำหรับทุกqแล้วMจะเป็นเมทริกซ์ Pลักษณะเฉพาะทั้งสองนี้เพียงพอและจำเป็น^{[ 4 ]}

เวกเตอร์wเป็นตัวแปรส่วนเกิน [ ^{5 ] และ}โดยทั่วไปจะถูกละทิ้งหลังจาก พบ zแล้ว ด้วยเหตุนี้ ปัญหาจึงสามารถกำหนดได้ดังนี้:

• ${\displaystyle Mz+q\geqslant 0}$
• ${\displaystyle z\geqslant 0}$
• ${\displaystyle z^{\mathrm {T} }(Mz+q)=0}$(เงื่อนไขความสมบูรณ์แบบ)

การหาคำตอบของปัญหาความสมบูรณ์เชิงเส้นเกี่ยวข้องกับการลดค่าฟังก์ชันกำลังสองให้เหลือน้อยที่สุด

${\displaystyle f(z)=z^{T}(Mz+q)}$

ภายใต้ข้อจำกัด

${\displaystyle {Mz}+q\geqslant 0}$

${\displaystyle z\geqslant 0}$

ข้อจำกัดเหล่านี้ทำให้มั่นใจได้ว่าfจะมีค่าไม่เป็นลบเสมอ ค่าต่ำสุดของfจะเป็น 0 ที่zก็ต่อเมื่อzเป็นคำตอบของปัญหาความสมบูรณ์เชิงเส้น

ถ้าMเป็นเมทริกซ์บวกกำหนด (positive definite ) อัลกอริทึมใดๆ สำหรับแก้ปัญหาQP ที่เป็นนูน (อย่างเคร่งครัด) ก็สามารถแก้ปัญหา LCP ได้เช่นกัน อัลกอริทึมการสลับฐาน (basis-exchange pivoting algorithms) ที่ออกแบบมาเป็นพิเศษ เช่นอัลกอริทึมของ Lemkeและอัลกอริทึม simplex ของ Dantzigที่ดัดแปลงแล้ว ถูกนำมาใช้มานานหลายทศวรรษ นอกจากจะมีประสิทธิภาพในแง่ของเวลาในการประมวลผลแบบพหุนามแล้ว วิธีการจุดภายใน (interior-point methods) ยังมีประสิทธิภาพในทางปฏิบัติอีกด้วย

นอกจากนี้ ปัญหาการเขียนโปรแกรมเชิงกำลังสองระบุว่าเป็นการหาค่า ต่ำสุด โดยมีเงื่อนไขว่าQเป็นสมมาตร ${\displaystyle f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx}$${\displaystyle Ax\geqslant b}$${\displaystyle x\geqslant 0}$

ก็เหมือนกับการแก้ปัญหา LCP ด้วย

${\displaystyle q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix}}}$

เนื่องจาก เงื่อนไข Karush–Kuhn–Tuckerของปัญหา QP สามารถเขียนได้ดังนี้:

${\displaystyle {\begin{cases}v=Qx-A^{T}{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end{cases}}}$

โดยที่vคือตัวคูณลากรางจ์บนข้อจำกัดที่ไม่เป็นลบλคือตัวคูณบนข้อจำกัดอสมการ และsคือตัวแปรส่วนเกินสำหรับข้อจำกัดอสมการ เงื่อนไขที่สี่ได้มาจากการเสริมกันของแต่ละกลุ่มตัวแปร( x , s )กับเซตของเวกเตอร์ KKT (ตัวคูณลากรางจ์ที่เหมาะสมที่สุด) ซึ่งคือ( v , λ )ในกรณีนั้น

${\displaystyle z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{bmatrix}v\\s\end{bmatrix}}}$

หากผ่อนปรนข้อจำกัดเรื่องค่าไม่เป็นลบของxมิติของปัญหา LCP สามารถลดลงเหลือจำนวนอสมการได้ ตราบใดที่Qไม่เป็นเมทริกซ์เอกฐาน (ซึ่งรับประกันได้หากเป็นเมทริกซ์บวกแน่นอน ) ตัวคูณvจะไม่ปรากฏอีกต่อไป และเงื่อนไข KKT แรกสามารถเขียนใหม่ได้ดังนี้:

${\displaystyle Qx=A^{T}{\lambda }-c}$

หรือ:

${\displaystyle x=Q^{-1}(A^{T}{\lambda }-c)}$

เมื่อคูณทั้งสองข้างด้วย Aก่อนแล้วลบด้วยbเราจะได้:

${\displaystyle Ax-b=AQ^{-1}(A^{T}{\lambda }-c)-b\,}$

ด้านซ้าย เนื่องมาจากเงื่อนไข KKT ข้อที่สอง จึงเป็นsโดยการแทนที่และเรียงลำดับใหม่:

${\displaystyle s=(AQ^{-1}A^{T}){\lambda }+(-AQ^{-1}c-b)\,}$

กำลังโทรอยู่ตอนนี้

${\displaystyle {\begin{aligned}M&:=(AQ^{-1}A^{T})\\q&:=(-AQ^{-1}c-b)\end{aligned}}}$

เรามี LCP เนื่องมาจากความสัมพันธ์แบบเสริมกันระหว่างตัวแปรส่วนเกินsและตัวคูณลากรางจ์λเมื่อเราแก้ปัญหานี้ได้แล้ว เราก็สามารถหาค่าของxจากλ ได้ โดยใช้เงื่อนไข KKT ข้อแรก

สุดท้ายนี้ ยังสามารถจัดการกับข้อจำกัดความเท่าเทียมกันเพิ่มเติมได้อีกด้วย:

${\displaystyle A_{eq}x=b_{eq}}$

สิ่งนี้ทำให้เกิดเวกเตอร์ของตัวคูณลากรางจ์μ ซึ่งมี มิติ เท่ากับ${\displaystyle b_{eq}}$

สามารถตรวจสอบได้อย่างง่ายดายว่าค่าMและQสำหรับระบบ LCP นั้นแสดงได้ดังนี้: ${\displaystyle s=M{\lambda }+Q}$

${\displaystyle {\begin{aligned}M&:={\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{eq}\end{bmatrix}}-b\end{aligned}}}$

จากค่า λเราสามารถกู้คืนค่าของทั้งxและตัวคูณลากรางจ์ของสมการμ ได้ ดังนี้:

${\displaystyle {\begin{bmatrix}x\\\mu \end{bmatrix}}={\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\-b_{eq}\end{bmatrix}}}$

ในความเป็นจริง ตัวแก้ปัญหา QP ส่วนใหญ่ทำงานบนสูตร LCP รวมถึงวิธีจุดภายในการหมุนหลัก/ความสมบูรณ์ และวิธีเซตแอคทีฟ^{[ ​​1 ] [ 2 ]}ปัญหา LCP สามารถแก้ไขได้ด้วยอัลกอริทึมไขว้ เช่น กัน^{[ 6 ] [ 7 ] [ 8 ] [ 9 ]}ในทางกลับกัน สำหรับปัญหาความสมบูรณ์เชิงเส้น อัลกอริทึมไขว้จะสิ้นสุดอย่างจำกัดก็ต่อเมื่อเมทริกซ์เป็นเมทริกซ์เพียงพอ^{[ 8 ] [ 9 ]}เมทริกซ์เพียงพอเป็นการวางนัยทั่วไปของทั้งเมทริกซ์บวกกำหนดและเมทริกซ์ Pซึ่งไมเนอร์หลักแต่ละตัวเป็นบวก^{[ 8 ] [ 9 ] [ 10 ]} ปัญหา LCP ดังกล่าวสามารถแก้ไขได้เมื่อมีการกำหนดสูตรแบบนามธรรมโดยใช้ทฤษฎีเมทริกซ์เชิง ทิศทาง ^{[ 11 ] [ 12 ] [ 13 ]}

• ทฤษฎีความสมบูรณ์แบบ
• เอนจิ้ นฟิสิกส์แบบแรงกระตุ้น/ข้อจำกัดสำหรับเกมใช้แนวทางนี้
• พลศาสตร์การสัมผัสพลศาสตร์การสัมผัสด้วยวิธีการที่ไม่ราบเรียบ
• เกมไบเมทริกซ์สามารถลดรูปเป็น LCP ได้

• R. Chandrasekaran. "เกมไบเมทริกซ์" ( PDF)หน้า  5–7 สืบค้นเมื่อ 18 ธันวาคม 2015

• LCPSolve — ขั้นตอนง่ายๆ ใน GAUSS สำหรับแก้ปัญหาความสมบูรณ์แบบเชิงเส้น
• Siconos /Numerics เป็นซอฟต์แวร์โอเพนซอร์สภายใต้ลิขสิทธิ์ GPL ที่เขียนด้วยภาษา C ซึ่งนำอัลกอริทึมของ Lemke และวิธีการอื่นๆ มาใช้ในการแก้ปัญหา LCP และ MLCP