ในการหาค่าเหมาะสมที่สุดทางคณิตศาสตร์วิธีการลงโทษ (penalty methods)เป็นอัลกอริธึมประเภทหนึ่งที่ใช้ในการแก้ปัญหา การหาค่าเหมาะสมที่สุดภายใต้ข้อจำกัด

วิธีการปรับโทษ (penalty method) แทนที่ปัญหาการหาค่าเหมาะสมที่สุดแบบมีข้อจำกัดด้วยชุดของปัญหาแบบไม่มีข้อจำกัด ซึ่งในอุดมคติแล้วคำตอบของปัญหาแบบไม่มีข้อจำกัดจะลู่เข้าสู่คำตอบของปัญหาแบบมีข้อจำกัดเดิม ปัญหาแบบไม่มีข้อจำกัดเหล่านี้เกิดขึ้นจากการเพิ่มพจน์ที่เรียกว่าฟังก์ชันปรับโทษ (penalty function ) เข้าไปในฟังก์ชันเป้าหมาย (objective function)ซึ่งประกอบด้วยพารามิเตอร์ปรับโทษคูณด้วยค่าที่ใช้วัดการละเมิดข้อจำกัด ค่าที่ใช้วัดการละเมิดจะมีค่าไม่เป็นศูนย์เมื่อมีการละเมิดข้อจำกัด และจะมีค่าเป็นศูนย์ในบริเวณที่ไม่มีการละเมิดข้อจำกัด

สมมติว่าเรากำลังแก้ปัญหาที่มีข้อจำกัดดังต่อไปนี้:

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

ขึ้นอยู่กับ

${\displaystyle c_{i}(\mathbf {x} )\leq 0~\forall i\in I.}$

ปัญหานี้สามารถแก้ไขได้โดยใช้ชุดของปัญหาการหาค่าต่ำสุดแบบไม่มีข้อจำกัด

${\displaystyle \min f_{p}(\mathbf {x} ):=f(\mathbf {x} )+p~\sum _{i\in I}~g(c_{i}(\mathbf {x} ))}$

ที่ไหน

${\displaystyle g(c_{i}(\mathbf {x} ))=\max(0,c_{i}(\mathbf {x} ))^{2}.}$

ในสมการข้างต้นคือฟังก์ชันค่าปรับภายนอกในขณะที่คือสัมประสิทธิ์ค่าปรับเมื่อสัมประสิทธิ์ค่าปรับเป็น 0 จะได้f _p = fซึ่งหมายความว่าเราไม่ได้นำข้อจำกัดมาพิจารณา ${\displaystyle g(c_{i}(\mathbf {x} ))}$${\displaystyle p}$${\displaystyle p}$

ในแต่ละรอบของการดำเนินการวิธีนี้ เราจะเพิ่มค่าสัมประสิทธิ์การลงโทษ(เช่น เพิ่มขึ้นเป็น 10 เท่า) แก้ปัญหาที่ไม่มีข้อจำกัด และใช้คำตอบนั้นเป็นค่าเริ่มต้นสำหรับการคาดเดาในรอบถัดไป คำตอบของปัญหาที่ไม่มีข้อจำกัดในรอบต่อๆ ไปจะลู่เข้าสู่คำตอบของปัญหาที่มีข้อจำกัดเดิมในเชิงอะซิมโทติก ${\displaystyle p}$

ฟังก์ชันการลงโทษทั่วไปในการเพิ่มประสิทธิภาพแบบมีข้อจำกัด ได้แก่ ฟังก์ชันการลงโทษ กำลังสองและฟังก์ชันการลงโทษเชิงเส้นแบบ เดดโซน ^{[ 1 ]}

ก่อนอื่นเราจะพิจารณาเซตของตัวเพิ่มประสิทธิภาพทั่วโลกของปัญหาดั้งเดิม X* ^{[ 2 ] : ทฤษฎีบท 9.2.1} สมมติว่าวัตถุประสงค์fมีเซตระดับ ที่มีขอบเขต และปัญหาดั้งเดิมนั้นสามารถหาคำตอบได้ ดังนั้น:

• สำหรับค่าสัมประสิทธิ์การลงโทษp ทุก ค่า เซตของตัวปรับค่าเหมาะสมที่สุดทั่วโลกของปัญหาที่มีการลงโทษ X _p * จะไม่ว่างเปล่า
• สำหรับทุก ε>0 จะมีสัมประสิทธิ์ปรับโทษp อยู่ ซึ่งทำให้เซต X _p * อยู่ในบริเวณใกล้เคียง ε ของเซต X*

ทฤษฎีบทนี้มีประโยชน์ส่วนใหญ่เมื่อf _pเป็นฟังก์ชันนูน เนื่องจากในกรณีนี้ เราสามารถหาค่าเหมาะสมที่สุดทั่วโลกของf _pได้

ทฤษฎีบทที่สองพิจารณาตัวเพิ่มประสิทธิภาพเฉพาะที่^{[ 2 ] : ทฤษฎีบท 9.2.2} ให้ x* เป็นตัวเพิ่มประสิทธิภาพเฉพาะที่ที่ไม่เสื่อมสภาพของปัญหาดั้งเดิม ("ไม่เสื่อมสภาพ" หมายความว่าเกรเดียนต์ของข้อจำกัดที่ใช้งานอยู่เป็นอิสระเชิงเส้นและเงื่อนไขความเหมาะสมที่เพียงพออันดับสองเป็นไปตามเงื่อนไข) จากนั้นจะมีบริเวณใกล้เคียง V* ของ x* และp ₀ >0 บางค่า ซึ่งสำหรับทุกp > p ₀วัตถุประสงค์ที่ถูกลงโทษf _pจะมีจุดวิกฤตเพียงจุดเดียวใน V* (แสดงด้วย x*(p)) และ x*( p ) จะเข้าใกล้ x* เมื่อp →∞ นอกจากนี้ ค่าวัตถุประสงค์f (x*( p )) จะเพิ่มขึ้นอย่างอ่อน ๆ กับp

อัลกอริทึมการเพิ่มประสิทธิภาพการ บีบอัดภาพสามารถใช้ฟังก์ชันปรับโทษเพื่อเลือกวิธีที่ดีที่สุดในการบีบอัดโซนสีให้เป็นค่าตัวแทนเดียว^{[ 3 ] [ 4 ]}วิธีการปรับโทษมักใช้ในกลศาสตร์เชิงคำนวณ โดยเฉพาะในวิธีองค์ประกอบจำกัดเพื่อบังคับใช้เงื่อนไข เช่นการ สัมผัส

ข้อดีของวิธีการลงโทษคือ เมื่อเรามีเป้าหมายที่ถูกลงโทษโดยไม่มีข้อจำกัด เราสามารถใช้วิธีการเพิ่มประสิทธิภาพแบบไม่มีข้อจำกัดใดๆ เพื่อแก้ปัญหาได้ ข้อเสียคือ เมื่อค่าสัมประสิทธิ์การลงโทษpเพิ่มขึ้น ปัญหาแบบไม่มีข้อจำกัดจะกลายเป็นปัญหาที่ไม่เสถียร - ค่าสัมประสิทธิ์มีขนาดใหญ่มาก และอาจทำให้เกิดข้อผิดพลาดเชิงตัวเลขและการลู่เข้าที่ช้าของการลดค่าแบบไม่มีข้อจำกัด^{[ 2 ] : Sub.9.2}

วิธีการแบบมีสิ่งกีดขวาง (Barrier methods)เป็นอัลกอริทึมทางเลือกอีกประเภทหนึ่งสำหรับการหาค่าเหมาะสมที่สุดภายใต้ข้อจำกัด วิธีการเหล่านี้ยังเพิ่มเทอมคล้ายค่าปรับเข้าไปในฟังก์ชันเป้าหมาย แต่ในกรณีนี้ ค่าที่ได้จากการวนซ้ำจะถูกบังคับให้อยู่ภายในโดเมนที่เป็นไปได้ และสิ่งกีดขวางจะทำหน้าที่ผลักดันให้ค่าที่ได้จากการวนซ้ำอยู่ห่างจากขอบเขตของโดเมนที่เป็นไปได้ ในทางปฏิบัติแล้ว วิธีการเหล่านี้มีประสิทธิภาพมากกว่าวิธีการแบบมีค่าปรับ (Penalty methods)

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

อัลกอริทึมการเขียนโปรแกรมเชิงไม่เชิงเส้นอื่นๆ:

• การเขียนโปรแกรมกำลังสองแบบลำดับ
• การเขียนโปรแกรมเชิงเส้นต่อเนื่อง
• การเขียนโปรแกรมเชิงเส้น-กำลังสองแบบลำดับ
• วิธีการจุดภายใน