วิธีการลากรางจ์เสริม (Augmented Lagrangian methods) เป็น อัลกอริทึมประเภทหนึ่งสำหรับการแก้ ปัญหา การหาค่าเหมาะสมที่สุดแบบมี ข้อจำกัด วิธีการ นี้มีความคล้ายคลึงกับวิธีการปรับโทษ (Penalty methods)ตรงที่มันแทนที่ปัญหาการหาค่าเหมาะสมที่สุดแบบมีข้อจำกัดด้วยชุดของปัญหาที่ไม่มีข้อจำกัด และเพิ่มพจน์ปรับโทษเข้าไปในฟังก์ชัน เป้าหมาย แต่ในวิธีการลากรางจ์เสริมนั้น จะเพิ่มพจน์อีกพจน์หนึ่งที่ออกแบบมาเพื่อเลียนแบบตัวคูณลากรางจ์ (Lagrange multiplier ) วิธี การลากรางจ์เสริมมีความเกี่ยวข้องกับ แต่ไม่เหมือนกับวิธีการตัวคูณลากรางจ์ (Lagrange multipliers method )

มองในอีกมุมหนึ่ง เป้าหมายที่ไม่ถูกจำกัดก็คือลากรางเจียนของปัญหาที่ถูกจำกัด โดยมีพจน์ปรับโทษเพิ่มเติม ( ส่วนเสริม )

เดิมทีวิธีการนี้รู้จักกันในชื่อวิธีการตัวคูณและได้รับการศึกษาในช่วงทศวรรษ 1970 และ 1980 ในฐานะทางเลือกที่เป็นไปได้สำหรับวิธีการลงโทษ มีการกล่าวถึงครั้งแรกโดยMagnus Hestenes ^{[ 1 ]}และต่อมาโดยMichael Powellในปี 1969 ^{[ 2 ]} R. Tyrrell Rockafellarได้ศึกษาวิธีการนี้ในส่วนที่เกี่ยวข้องกับFenchel dualityโดยเฉพาะอย่างยิ่งในส่วนที่เกี่ยวข้องกับวิธีการจุดใกล้เคียงการทำให้เป็นระเบียบแบบ Moreau–Yosidaและตัวดำเนินการโมโนโทนสูงสุดวิธีการเหล่านี้ถูกนำมาใช้ในการเพิ่มประสิทธิภาพเชิงโครงสร้าง นอกจากนี้ Dimitri Bertsekasยังได้ศึกษาวิธีการนี้ โดยเฉพาะอย่างยิ่งในหนังสือของเขาในปี 1982 ^{[ 3 ]}พร้อมกับส่วนขยายที่เกี่ยวข้องกับฟังก์ชันการทำให้เป็นระเบียบที่ไม่ใช่กำลังสอง (เช่นการทำให้เป็นระเบียบแบบเอนโทรปี ) การศึกษาแบบผสมผสานนี้ก่อให้เกิด "วิธีการตัวคูณเลขชี้กำลัง" ซึ่งจัดการกับข้อจำกัดความไม่เท่าเทียมกันด้วยฟังก์ชัน Lagrangian เสริมที่สามารถหาอนุพันธ์ได้สองครั้ง

ตั้งแต่ทศวรรษ 1970 เป็นต้นมาการเขียนโปรแกรมกำลังสองแบบลำดับ (SQP) และวิธีการจุดภายใน (IPM) ได้รับความสนใจมากขึ้น ส่วนหนึ่งเป็นเพราะสามารถใช้ ซับรูที นเมทริกซ์แบบเบาบาง จากไลบรารีซอฟต์แวร์เชิงตัวเลข ได้ง่ายกว่า และส่วนหนึ่งเป็นเพราะ IPM มีผลลัพธ์ความซับซ้อนที่ได้รับการพิสูจน์แล้วผ่านทฤษฎีของฟังก์ชันที่สอดคล้องกันเองวิธีการ Lagrangian เสริมได้รับการฟื้นฟูโดยระบบการเพิ่มประสิทธิภาพLANCELOT , ALGENCAN ^{[ 4 ] [ 5 ]}และAMPLซึ่งอนุญาตให้ใช้เทคนิคเมทริกซ์แบบเบาบางกับปัญหาที่ดูเหมือนหนาแน่นแต่ "แยกส่วนได้บางส่วน" วิธีนี้ยังคงมีประโยชน์สำหรับปัญหาบางอย่าง^{[ 6 ]}

ประมาณปี 2007 วิธีการลากรางจ์เสริม (Augmented Lagrangian Method) กลับมาได้รับความนิยมอีกครั้งในสาขาต่างๆ เช่นการลดสัญญาณรบกวนแบบ Total Variationและ การบีบอัดข้อมูล ( Compressed Sensing ) โดยเฉพาะอย่างยิ่ง วิธีการลากรางจ์เสริมแบบมาตรฐานรูปแบบหนึ่งที่ใช้การอัปเดตบางส่วน (คล้ายกับวิธี Gauss–Seidelสำหรับการแก้สมการเชิงเส้น) ซึ่งรู้จักกันในชื่อ วิธีการ สลับทิศทางของตัวคูณ (Alternating Direction Method of MultipliersหรือADMM)ได้รับความสนใจเป็นอย่างมาก

พิจารณาการแก้ปัญหาการหาค่าเหมาะสมที่สุดภายใต้ข้อจำกัดต่อไปนี้:

${\displaystyle \min f(\mathbf {x} )}$

ขึ้นอยู่กับ

${\displaystyle c_{i}(\mathbf {x} )=0~\forall i\in {\mathcal {E}},}$

โดยที่หมายถึงดัชนีสำหรับข้อจำกัดความเท่าเทียมกัน ปัญหานี้สามารถแก้ไขได้โดยใช้ชุดของปัญหาการหาค่าต่ำสุดแบบไม่มีข้อจำกัด เพื่อเป็นข้อมูลอ้างอิง เราจะแสดง ขั้นตอนที่ kของวิธีการลงโทษ ก่อน : ${\displaystyle {\mathcal {E}}}$

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+\mu _{k}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}.}$

วิธีการปรับโทษจะช่วยแก้ปัญหานี้ได้ จากนั้นในการวนซ้ำครั้งถัดไป มันจะแก้ปัญหาอีกครั้งโดยใช้ค่าที่มากขึ้นและใช้คำตอบเดิมเป็นค่าเริ่มต้นหรือ "การเริ่มต้นแบบอุ่นเครื่อง" ${\displaystyle \mu _{k}}$

วิธีการลากรางจ์เสริมใช้ฟังก์ชันเป้าหมายที่ไม่จำกัดเงื่อนไขดังต่อไปนี้:

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+{\frac {\mu _{k}}{2}}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}+\sum _{i\in {\mathcal {E}}}~\แลมบ์ดา _{i}c_{i}(\mathbf {x} )}$

และหลังจากแต่ละรอบการทำงาน นอกจากการอัปเดตแล้วตัวแปรยังได้รับการอัปเดตตามกฎอีกด้วย ${\displaystyle \mu _{k}}$${\displaystyle \lambda }$

${\displaystyle \lambda _{i}\leftarrow \lambda _{i}+\mu _{k}c_{i}(\mathbf {x} _{k})}$

คำตอบของปัญหาที่ไม่ถูกจำกัดใน ขั้นตอนที่ k อยู่ ที่ใด(เช่น) ${\displaystyle \mathbf {x} _{k}}$${\displaystyle \mathbf {x} _{k}={\text{argmin}}\Phi _{k}(\mathbf {x} )}$

ตัวแปรนี้เป็นการประมาณค่าตัวคูณลากรางจ์และความแม่นยำของการประมาณค่านี้จะดีขึ้นในทุกขั้นตอน ข้อได้เปรียบหลักของวิธีนี้คือ ต่างจากวิธีลงโทษไม่จำเป็นต้องใช้เพื่อแก้ปัญหาข้อจำกัดเดิม เนื่องจากมีพจน์ตัวคูณลากรางจ์ จึงสามารถมีค่าน้อยลงมาก และหลีกเลี่ยงภาวะไม่เสถียรได้^{[ 6 ]}อย่างไรก็ตาม ในทางปฏิบัติ มักจะฉายค่าประมาณตัวคูณลงในเซตที่มีขอบเขตขนาดใหญ่ (การป้องกัน) ซึ่งจะช่วยหลีกเลี่ยงความไม่เสถียรเชิงตัวเลขและนำไปสู่การบรรจบกันทางทฤษฎีที่แข็งแกร่ง^{[ 5 ]}${\displaystyle \lambda }$${\displaystyle \mu \rightarrow \infty }$${\displaystyle \mu }$

วิธีการนี้สามารถขยายเพื่อจัดการกับข้อจำกัดความไม่เท่าเทียมกันได้ สำหรับการอภิปรายเกี่ยวกับการปรับปรุงในทางปฏิบัติ โปรดดูเอกสารอ้างอิง^{[ 6 ] [ 5 ]}

วิธีการตัวคูณทิศทางสลับ (ADMM) เป็นรูปแบบหนึ่งของแผนการลากรางจ์เสริมที่ใช้การอัปเดตบางส่วนสำหรับตัวแปรคู่ วิธีนี้มักนำไปใช้ในการแก้ปัญหาต่างๆ เช่น

${\displaystyle \min _{x}f(x)+g(Mx).}$

นี่เทียบเท่ากับปัญหาที่มีข้อจำกัด

${\displaystyle \min _{x,y}f(x)+g(y),\quad {\text{subject to}}\quad Mx=y.}$

แม้ว่าการเปลี่ยนแปลงนี้อาจดูเหมือนเล็กน้อย แต่ปัญหาสามารถแก้ไขได้โดยใช้วิธีการหาค่าเหมาะสมที่สุดแบบมีข้อจำกัด (โดยเฉพาะอย่างยิ่ง วิธี Augmented Lagrangian) และฟังก์ชันเป้าหมายสามารถแยกได้ในxและyการอัปเดตแบบคู่ต้องแก้ฟังก์ชันความใกล้เคียงในxและyพร้อมกัน เทคนิค ADMM ช่วยให้สามารถแก้ปัญหานี้ได้โดยประมาณโดยการแก้หาค่าx ก่อน โดยที่yคงที่ แล้วจึงแก้หาค่าyโดยที่xคงที่ แทนที่จะทำซ้ำกระบวนการนี้จนกว่าจะลู่เข้า (เช่นวิธี Jacobi ) อัลกอริทึม ADMM จะดำเนินการอัปเดตตัวแปรคู่โดยตรงแล้วจึงทำซ้ำกระบวนการนี้ วิธีนี้ไม่เทียบเท่ากับการหาค่าต่ำสุดที่แน่นอน แต่ยังคงลู่เข้าสู่คำตอบที่ถูกต้องภายใต้สมมติฐานบางประการ เนื่องจากไม่ได้หาค่าต่ำสุดหรือประมาณค่าต่ำสุดของ Augmented Lagrangian อัลกอริทึมนี้จึงแตกต่างจากวิธี Augmented Lagrangian ทั่วไป

ADMM สามารถมองได้ว่าเป็นการประยุกต์ใช้ของอัลกอริทึมการแยก Douglas-Rachfordและอัลกอริทึม Douglas-Rachford ก็เป็นตัวอย่างของอัลกอริทึมจุดใกล้เคียง รายละเอียด สามารถพบได้ในเอกสารอ้างอิง^{[ 7 ]} มีซอฟต์แวร์สมัยใหม่หลายแพ็กเกจ รวมถึง YALL1 ^{[ 8 ]} (2009), SpaRSA ^{[ 9 ]} (2009) และ SALSA ^{[ 10 ]} (2009) ซึ่งแก้ปัญหาBasis pursuitและรูปแบบต่างๆ และใช้ ADMM นอกจากนี้ยังมีแพ็กเกจที่ใช้ ADMM เพื่อแก้ปัญหาทั่วไปมากขึ้น ซึ่งบางแพ็กเกจสามารถใช้ประโยชน์จากคอร์ประมวลผลหลายตัวได้ (เช่น SNAPVX ^{[ 11 ]} (2015), parADMM ^{[ 12 ]} (2016))

การหาค่าเหมาะสมที่สุดแบบสุ่ม (Stochastic optimization) พิจารณาปัญหาการลดค่าฟังก์ชันความสูญเสียให้เหลือน้อยที่สุด โดยสามารถเข้าถึงตัวอย่างที่มีสัญญาณรบกวนของฟังก์ชัน (หรือเกรเดียนต์ของฟังก์ชัน) เป้าหมายคือการประมาณค่าพารามิเตอร์ที่เหมาะสมที่สุด (ตัวลดค่า) สำหรับแต่ละตัวอย่างใหม่ ด้วยการปรับเปลี่ยนบางอย่าง ADMM สามารถนำมาใช้ในการหาค่าเหมาะสมที่สุดแบบสุ่มได้ ในการตั้งค่าแบบสุ่ม จะสามารถเข้าถึงได้เฉพาะตัวอย่างที่มีสัญญาณรบกวนของเกรเดียนต์เท่านั้น ดังนั้นจึงใช้การประมาณค่าที่ไม่แม่นยำของลากรางจ์:

${\displaystyle {\hat {\mathcal {L}}__{\rho ,k}=f_{1}(x_{k})+\langle \nabla f(x_{k},\zeta _{k+1}),x\rangle +g(y)-z^{T}(Ax+By-c)+{\frac {\rho }{2}}\Vert ขวาน+บาย-ซี\Vert ^{2}+{\frac {\Vert x-x_{k}\Vert ^{2}}{2\eta _{k+1}}},}$

โดยที่ขนาดขั้นตอนเปลี่ยนแปลงตามเวลา^{[ 13 ]}${\displaystyle \eta _{k+1}}$

ADMM ถูกนำมาใช้เพื่อแก้ปัญหาที่มีการควบคุม โดยที่การเพิ่มประสิทธิภาพฟังก์ชันและการควบคุมสามารถดำเนินการได้ในระดับท้องถิ่น จากนั้นจึงประสานงานกันในระดับโลกผ่านข้อจำกัด^{[ 14 ] [ 15 ] [ 16 ] [ 17 ]}

ปัญหาการหาค่าเหมาะสมที่สุดแบบมีกลไกควบคุม (Regularization) มีความสำคัญอย่างยิ่งในมิติสูง เนื่องจากกลไกควบคุมเป็นกลไกธรรมชาติในการเอาชนะปัญหาความไม่เสถียร (ill-posedness) และส่งเสริมความเรียบง่าย (parsimony) ในคำตอบที่เหมาะสมที่สุด (เช่น ความเบาบางและอันดับต่ำ) ประสิทธิภาพของ ADMM ในการแก้ปัญหาแบบมีกลไกควบคุมอาจหมายความว่ามันอาจมีประโยชน์สำหรับการแก้ปัญหาการหาค่าเหมาะสมที่สุดแบบสุ่มในมิติสูง

• การเขียนโปรแกรมกำลังสองแบบลำดับ
• การเขียนโปรแกรมเชิงเส้นแบบลำดับ
• การเขียนโปรแกรมเชิงเส้น-กำลังสองแบบลำดับ

การใช้งานวิธี Augmented Lagrangian แบบโอเพนซอร์สและแบบไม่เสียค่าใช้จ่าย/เชิงพาณิชย์:

• Accord.NET (การใช้งานตัวเพิ่มประสิทธิภาพแบบ Augmented Lagrangian ในภาษา C#)
• ALGLIB (การใช้งานตัวแก้ปัญหาลากรางเจียนเสริมแบบปรับสภาพล่วงหน้าด้วยภาษา C# และ C++)
• PENNON (GPL 3, มีใบอนุญาตเชิงพาณิชย์ให้เลือก)
• LANCELOT (ใบอนุญาตใช้งานภายในฟรี มีตัวเลือกเชิงพาณิชย์แบบเสียค่าใช้จ่าย)
• MINOS (ยังใช้วิธี Lagrangian เสริมสำหรับปัญหาบางประเภทด้วย)
• รหัสสำหรับREASON ที่ได้รับอนุญาตภายใต้ Apache 2.0 นั้นมีให้ใช้งานทางออนไลน์^{[ 18 ]}
• ALGENCAN (การใช้งาน Fortran ของวิธี Lagrangian เสริมพร้อมการป้องกัน) มีให้ใช้งานทางออนไลน์^{[ 19 ]}
• NLOPT (การใช้งาน C++ ของตัวเพิ่มประสิทธิภาพ Lagrangian เสริม ซึ่งสามารถเข้าถึงได้จากภาษาการเขียนโปรแกรมต่างๆ^{[ 20 ] [ 21 ]} ) ^{[ 22 ]}
• PyProximal (การใช้งานวิธี Lagrangian เสริมในภาษา Python) ^{[ 23 ]}

• ฟังก์ชันกั้น
• วิธีจุดภายใน
• ตัวคูณลากรางจ์
• วิธีการลงโทษ

• Bertsekas, Dimitri P. (1999), การเขียนโปรแกรมเชิงไม่เชิงเส้น (ฉบับที่ 2), เบลมอนต์, แมสซาชูเซตส์: Athena Scientific , ISBN 978-1-886529-00-7
• Birgin, EG; Martínez, JM (2014), วิธีการลากรางจ์เสริมเชิงปฏิบัติสำหรับการเพิ่มประสิทธิภาพภายใต้ข้อจำกัด , ฟิลาเดลเฟีย: สมาคมคณิตศาสตร์อุตสาหกรรมและประยุกต์ , doi : 10.1137/1.9781611973365 , ISBN 978-1-611973-35-8
• Nocedal, Jorge; Wright, Stephen J. (2006), การเพิ่มประสิทธิภาพเชิงตัวเลข (ฉบับที่ 2), เบอร์ลิน, นิวยอร์ก: Springer-Verlag , ISBN 978-0-387-30303-1