วิธีการจุดภายใน (หรือเรียกอีกอย่างว่าวิธีการกั้นหรือIPMs ) เป็นอัลกอริธึมสำหรับแก้ ปัญหา การหาค่าเหมาะสมที่สุดแบบนูนเชิงเส้นและไม่เชิงเส้น IPMs ผสมผสานข้อดีสองประการของอัลกอริธึมที่รู้จักกันก่อนหน้านี้:

• ในทางทฤษฎีแล้ว เวลาในการทำงานของวิธีการนี้เป็นแบบพหุนามซึ่งแตกต่างจากวิธีการซิมเพล็กซ์ที่มีเวลาในการทำงานแบบเลขชี้กำลังในกรณีที่เลวร้ายที่สุด
• ในทางปฏิบัติ วิธีการเหล่านี้ทำงานได้เร็วเท่ากับวิธีซิมเพล็กซ์ ซึ่งแตกต่างจากวิธีเอลลิปซอยด์ที่ในทางทฤษฎีมีเวลาการทำงานเป็นพหุนาม แต่ในทางปฏิบัติกลับช้ามาก

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

นักคณิตศาสตร์ชาวโซเวียต II Dikin ค้นพบวิธีจุดภายในในปี 1967 ^{[ 1 ]}วิธีนี้ได้รับการคิดค้นขึ้นใหม่ในสหรัฐอเมริกาในช่วงกลางทศวรรษ 1980 ในปี 1984 Narendra Karmarkarได้พัฒนาวิธีการเขียนโปรแกรมเชิงเส้นที่เรียกว่า^อัลกอริทึมของ Karmarkar [ ^{2 ]}ซึ่งทำงานในเวลาพหุนาม ( การดำเนินการกับตัวเลขL บิต โดยที่ nคือจำนวนตัวแปรและค่าคงที่) และมีประสิทธิภาพมากในทางปฏิบัติ บทความของ Karmarkar ทำให้เกิดความสนใจอย่างมากในวิธีจุดภายใน สองปีต่อมาJames Renegar ได้คิดค้นวิธีจุดภายในแบบ ติดตามเส้นทางวิธีแรกโดยมีเวลาทำงานวิธีนี้ได้รับการขยายจากปัญหาเชิงเส้นไปสู่ปัญหาการหาค่าเหมาะสมที่สุดแบบนูน โดยอาศัยฟังก์ชันกั้นที่สอดคล้องกันเองที่ใช้ในการเข้ารหัส เซต แบบนูน^{[ 3 ]}${\displaystyle O(n^{3.5}L)}$${\displaystyle O(n^{3}L)}$

ปัญหาการหาค่าเหมาะสมที่สุดแบบนูนใดๆ ก็สามารถแปลงเป็นการลดค่า (หรือเพิ่มค่า) ฟังก์ชันเชิงเส้นบนเซตแบบนูนได้โดยการแปลงเป็นรูปแบบเอพิกราฟ^{[ 4 ] : 143} แนวคิดของการเข้ารหัสเซตที่เป็นไปได้โดยใช้สิ่งกีดขวางและการออกแบบวิธีการแบบสิ่งกีดขวางได้รับการศึกษาโดย Anthony V. Fiacco, Garth P. McCormick และคนอื่นๆ ในช่วงต้นทศวรรษ 1960 แนวคิดเหล่านี้ได้รับการพัฒนาขึ้นเป็นหลักสำหรับการเขียนโปรแกรมแบบไม่เชิงเส้น ทั่วไป แต่ต่อมาถูกละทิ้งเนื่องจากมีวิธีการที่มีประสิทธิภาพมากกว่าสำหรับปัญหาประเภทนี้ (เช่นการเขียนโปรแกรมกำลังสองแบบลำดับ )

Yurii NesterovและArkadi Nemirovskiได้คิดค้นอุปสรรคประเภทพิเศษที่สามารถใช้ในการเข้ารหัสเซตแบบนูนใดๆ ก็ได้ พวกเขารับประกันว่าจำนวนการวนซ้ำของอัลกอริทึมจะถูกจำกัดด้วยพหุนามในมิติและความแม่นยำของคำตอบ^{[ 5 ] [ 3 ]}

กลุ่มของวิธีการติดตามเส้นทางคู่หลักภายในจุดถือว่าประสบความสำเร็จมากที่สุดอัลกอริทึมตัวทำนาย-ตัวแก้ไขของ Mehrotraเป็นพื้นฐานสำหรับการใช้งานส่วนใหญ่ของกลุ่มวิธีการนี้^{[ 6 ]}

เราได้รับโปรแกรมแบบนูนในรูปแบบ: โดยที่ f เป็นฟังก์ชันแบบนูนและ G เป็นเซตแบบนูนโดยไม่เสียความเป็นทั่วไปเราสามารถสมมติว่าฟังก์ชันเป้าหมายfเป็นฟังก์ชันเชิงเส้นโดยปกติแล้ว เซตแบบนูนGจะถูกแทนด้วยเซตของอสมการแบบนูนและสมการเชิงเส้น สมการเชิงเส้นสามารถกำจัดได้โดยใช้พีชคณิตเชิงเส้นดังนั้นเพื่อความเรียบง่าย เราจึงสมมติว่ามีเพียงอสมการแบบนูนเท่านั้น และโปรแกรมสามารถอธิบายได้ดังนี้ โดยที่g _iเป็นฟังก์ชันแบบนูน: เราสมมติว่าฟังก์ชันข้อจำกัดอยู่ในตระกูลเดียวกัน (เช่น ฟังก์ชันกำลังสอง) เพื่อให้โปรแกรมสามารถแทนด้วยเวกเตอร์สัมประสิทธิ์ ที่มีจำนวนจำกัด (เช่น สัมประสิทธิ์ของฟังก์ชันกำลังสอง) มิติของเวกเตอร์สัมประสิทธิ์นี้เรียกว่าขนาดของโปรแกรม ตัวแก้ปัญหาเชิงตัวเลขสำหรับตระกูลโปรแกรมที่กำหนด คืออัลกอริทึมที่สร้างลำดับของคำตอบโดยประมาณx _tสำหรับt =1,2,... โดยใช้การดำเนินการทางคณิตศาสตร์จำนวนจำกัด เมื่อกำหนดเวกเตอร์สัมประสิทธิ์ ตัวแก้ปัญหาเชิงตัวเลขเรียกว่าลู่เข้าถ้าสำหรับโปรแกรมใดๆ จากตระกูลและε >0 ที่เป็นบวกใดๆ จะมีT บางค่า (ซึ่งอาจขึ้นอยู่กับโปรแกรมและε ) เช่นนั้น สำหรับt > T ใดๆ คำตอบโดยประมาณx _t จะเป็นค่าประมาณ εนั่นคือ: โดยที่คือคำตอบที่เหมาะสมที่สุด ตัวแก้ปัญหาเรียกว่าพหุนามถ้าจำนวนการดำเนินการทางคณิตศาสตร์ทั้งหมดในTขั้นตอนแรกมีค่าไม่เกิน$${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &x\in G.\end{aligned}}}$$$${\displaystyle {\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &g_{i}(x)\leq 0{\text{ for }}i=1,\dots ,m.\\\end{aligned}}}$$$${\displaystyle {\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad {\text{สำหรับ}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned}}}$$${\displaystyle f^{*}}$

poly(problem-size) * log( V / ε ),

โดยที่Vคือค่าคงที่ที่ขึ้นอยู่กับข้อมูล เช่น ผลต่างระหว่างค่าที่มากที่สุดและค่าที่น้อยที่สุดในเซตที่เป็นไปได้ กล่าวอีกนัยหนึ่งV / εคือ "ความแม่นยำสัมพัทธ์" ของคำตอบ ซึ่งก็คือความแม่นยำเมื่อเทียบกับสัมประสิทธิ์ที่มากที่สุด log( V / ε ) แสดงถึงจำนวน "หลักความแม่นยำ" ดังนั้น ตัวแก้ปัญหาจะเรียกว่า 'พหุนาม' หากความแม่นยำที่เพิ่มขึ้นแต่ละหลักต้องการจำนวนการดำเนินการที่เป็นพหุนามตามขนาดของปัญหา

ประเภทของวิธีการวัดจุดภายใน ได้แก่:

• วิธีการลดขนาดที่เป็นไปได้ : อัลกอริทึมของคาร์มาร์การ์เป็นวิธีแรก
• วิธีการติดตามเส้นทาง : อัลกอริทึมของJames Renegar ^{[ 7 ]}และ Clovis Gonzaga ^{[ 8 ]}เป็นอัลกอริทึมแรก
• วิธีการแบบคู่ดั้งเดิม

เมื่อกำหนดโปรแกรมการหาค่าเหมาะสมที่สุดแบบนูน (P) ที่มีข้อจำกัด เราสามารถแปลงเป็น โปรแกรม ที่ไม่มีข้อจำกัดได้โดยการเพิ่มฟังก์ชันกั้นโดยเฉพาะอย่างยิ่ง ให้bเป็นฟังก์ชันนูนเรียบที่กำหนดภายในบริเวณที่เป็นไปได้Gโดยที่สำหรับลำดับใดๆที่ลิมิตอยู่บนขอบของG : เรายังสมมติว่าbไม่เสื่อมสภาพ นั่นคือ : เป็นเมทริกซ์บวกแน่นอนสำหรับทุก x ใน interior(G) ทีนี้ ลองพิจารณาตระกูลของโปรแกรมต่อไปนี้:${\displaystyle \{x_{j}\in {\textbf {G}}\}}$${\displaystyle \lim _{j\to \infty }b(x_{j})=\infty }$${\displaystyle b''(x)}$${\displaystyle P_{t}=t\cdot f(x)+b(x)}$

ในทางเทคนิคแล้ว โปรแกรมนี้มีข้อจำกัด เนื่องจากbถูกกำหนดไว้เฉพาะภายในของG เท่านั้น แต่ในทางปฏิบัติแล้ว สามารถแก้ปัญหานี้ได้ในฐานะโปรแกรมที่ไม่มีข้อจำกัด เนื่องจากตัวแก้ปัญหาใดๆ ที่พยายามลดค่าฟังก์ชันจะไม่เข้าใกล้ขอบเขตที่bเข้าใกล้ค่าอนันต์ ดังนั้น ( P _t ) จึงมีคำตอบเดียว – เราจะใช้ สัญลักษณ์ x *( t ) แทน ฟังก์ชันx * เป็นฟังก์ชันต่อเนื่องของtซึ่งเรียกว่าเส้นทางศูนย์กลางจุดลิมิตทั้งหมดของx * เมื่อtเข้าใกล้ค่าอนันต์ ล้วนเป็นคำตอบที่ดีที่สุดของโปรแกรมดั้งเดิม (P)

วิธีการติดตามเส้นทางคือวิธีการติดตามฟังก์ชันx * ตามลำดับที่เพิ่มขึ้น t1 _, t2 _, ... กล่าวคือ การคำนวณค่าประมาณxᵢ ที่ดีพอ สำหรับจุดx *( tᵢ ) โดยที่ผลต่างxᵢ _- x *( _{tᵢ )}เข้าใกล้ 0 เมื่อi เข้าใกล้ค่าอนันต์ จาก นั้นลำดับxᵢจะ เข้าใกล้คำตอบที่ดีที่สุดของ ( _P ) ซึ่งต้องระบุสามสิ่งต่อไปนี้ _:

• ฟังก์ชันกั้น b(x)
• นโยบายสำหรับการกำหนดพารามิเตอร์การลงโทษt _i .
• ตัวแก้ปัญหาการหาค่าเหมาะสมที่สุดแบบไม่มีข้อจำกัด ใช้ในการแก้ปัญหา ( P _i ) และหาx _iเช่นวิธีของนิวตันโปรดทราบว่าเราสามารถใช้x _i แต่ละตัว เป็นจุดเริ่มต้นในการแก้ปัญหาถัดไป ( P _i+1 ) ได้

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

Renegar ^{[ 7 ]}และ Gonzaga ^{[ 8 ]}พิสูจน์แล้วว่าอินสแตนซ์เฉพาะของวิธีการติดตามเส้นทางคือ polytime:

• ข้อจำกัด (และวัตถุประสงค์) เป็นฟังก์ชันเชิงเส้น
• ฟังก์ชันกั้นเป็นฟังก์ชันลอการิทึม : ${\displaystyle b(x)=-\sum _{j=1}^{m}\log({-g_{j}(x)})}$
• พารามิเตอร์การลงโทษtจะได้รับการปรับปรุงแบบเรขาคณิต นั่นคือโดยที่μเป็นค่าคงที่ (พวกเขาใช้โดยที่mคือจำนวนข้อจำกัดอสมการ)${\displaystyle t_{i+1}:=\mu \cdot t_{i}}$${\displaystyle \mu =1+0.001\cdot {\sqrt {m}}}$
• ตัวแก้ปัญหาคือวิธีของนิวตัน โดยจะ ดำเนินการ ทีละขั้นตอนของวิธีนิวตันสำหรับแต่ละขั้นตอนในเวลาt

พวกเขาพิสูจน์แล้วว่า ในกรณีนี้ ผลต่างx _i - x *( t _i ) จะมีค่าไม่เกิน 0.01 และ f( x _i ) - f* จะมีค่าไม่เกินดังนั้น ความแม่นยำของคำตอบจึงเป็นสัดส่วนกับดังนั้น การเพิ่มความแม่นยำอีกหนึ่งหลักจึงเพียงพอที่จะคูณt _iด้วย 2 (หรือค่าคงที่อื่นๆ) ซึ่งต้องใช้ขั้นตอนแบบนิวตัน เนื่องจากแต่ละขั้นตอนแบบนิวตันใช้การดำเนินการ O( mn ² ) ครั้ง ความซับซ้อนโดยรวมจึงเป็นการดำเนินการ O( m ^3/2 n ² ) ครั้งสำหรับความแม่นยำแต่ละหลัก ${\displaystyle {\frac {2m}{t_{j}}}}$${\displaystyle {\frac {1}{t_{j}}}}$${\displaystyle O({\sqrt {m}})}$

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

เราได้รับปัญหาการหาค่าเหมาะสมที่สุดแบบนูน (P) ใน "รูปแบบมาตรฐาน":

ลดค่าc ^T x st xในG ให้เหลือน้อย ที่สุด

โดยที่Gเป็นเซตแบบนูนและปิด เรายังสามารถสมมติว่าGมีขอบเขต (เราสามารถทำให้มีขอบเขตได้ง่ายๆ โดยการเพิ่มข้อจำกัด | x |≤ RสำหรับR ที่มีขนาดใหญ่พอสมควร ) ^{[ 3 ] : มาตรา 4}

ในการใช้ระเบียบวิธีจุดภายใน เราจำเป็นต้องมีกำแพงกั้นที่สอดคล้องกันเองสำหรับGให้bเป็นกำแพงกั้นที่สอดคล้องกันเองระดับ M สำหรับ Gโดยที่M ≥ 1 คือพารามิเตอร์ความสอดคล้องกันเอง เราสมมติว่าเราสามารถคำนวณค่าของbค่าเกรเดียนต์ และเมทริกซ์เฮสเซียนของมันได้ อย่าง มีประสิทธิภาพ สำหรับทุกจุด x ภายในG

สำหรับทุกt > 0 เรากำหนดฟังก์ชันเป้าหมายแบบมีค่าปรับf _t (x) := t c ^T x + b( x )เรากำหนดเส้นทางของค่าต่ำสุดโดย: x*(t) := arg min f _t (x)เราประมาณเส้นทางนี้ตามลำดับที่เพิ่มขึ้นt _iลำดับนี้เริ่มต้นด้วยกระบวนการเริ่มต้นสองเฟสที่ไม่ธรรมดา จากนั้นจะได้รับการปรับปรุงตามกฎต่อไปนี้: . ${\displaystyle t_{i+1}:=\mu \cdot t_{i}}$

สำหรับแต่ละtiเราจะหาค่าต่ำสุดโดยประมาณของf _tiซึ่งแทนด้วยx _iค่าต่ำสุดโดยประมาณนี้ถูกเลือกเพื่อให้เป็นไปตาม "เงื่อนไขความใกล้เคียง" ต่อไปนี้ (โดยที่_Lคือค่าความคลาดเคลื่อนของเส้นทาง ):

${\displaystyle {\sqrt {[\nabla _{x}f_{t}(x_{i})]^{T}[\nabla _{x}^{2}f_{t}(x_{i})]^{-1}[\nabla _{x}f_{t}(x_{i})]}}\leq L}$.

ในการหาx _{i +1}เราเริ่มต้นด้วยx _iและใช้วิธีการของนิวตันแบบหน่วงเราใช้วิธีการนี้หลายขั้นตอน จนกระทั่ง "ความสัมพันธ์ใกล้ชิด" ข้างต้นเป็นไปตามเงื่อนไข จุดแรกที่สอดคล้องกับความสัมพันธ์นี้จะถูกกำหนดให้เป็นx i _{+1 [} ^{3 ] :มาตรา 4}

อัตราการล convergence ของวิธีนี้กำหนดโดยสูตรต่อไปนี้ สำหรับทุกi : ^{[ 3 ] : Prop.4.4.1}

${\displaystyle c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i}}$

เมื่อพิจารณาแล้ว จำนวนขั้นตอนของนิวตันที่จำเป็นในการเปลี่ยนจากx _iเป็นx _{i +1}จะมีค่าสูงสุดเป็นจำนวนคงที่ ซึ่งขึ้นอยู่กับrและL เท่านั้น โดยเฉพาะอย่างยิ่ง จำนวนขั้นตอนของนิวตันทั้งหมดที่จำเป็นในการหา คำตอบโดยประมาณของ ε (กล่าวคือ การหาxในGที่c ^T x - c* ≤ ε ) จะมีค่าสูงสุดดังนี้: ^{[ 3 ] : ทฤษฎีบท 4.4.1} ${\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}$

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1\right)}$

โดยที่ปัจจัยคงที่ O(1) ขึ้นอยู่กับrและL เท่านั้น จำนวนขั้นตอนของนิวตันที่จำเป็นสำหรับขั้นตอนการเริ่มต้นสองขั้นตอนมีค่าสูงสุดดังนี้: ^{[ 3 ] : ทฤษฎีบท 4.5.1}

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1\right)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{\text{Var}}_{G}(c)}{\epsilon }}+1\right)}$

โดยที่ปัจจัยคงที่ O(1) ขึ้นอยู่กับrและL เท่านั้น และ และเป็นจุดบางจุดภายในGโดยรวมแล้ว ความซับซ้อนของนิวตันโดยรวมในการหา คำตอบโดยประมาณ εมีค่าสูงสุดเพียงเท่านั้น${\displaystyle {\text{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x}$${\displaystyle {\bar {x}}}$

${\displaystyle O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)}$โดยที่ V เป็นค่าคงที่ที่ขึ้นอยู่กับปัญหา: .${\displaystyle V={\frac {{\text{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}})}}}}$

แต่ละขั้นตอนของนิวตันใช้ การคำนวณเลขคณิต O( n³ ⁾

เพื่อเริ่มต้นวิธีการติดตามเส้นทาง เราต้องการจุดในบริเวณภายในสัมพัทธ์ของพื้นที่ที่เป็นไปได้Gกล่าวอีกนัยหนึ่งคือ ถ้าGถูกกำหนดโดยอสมการg _i ( x ) ≤ 0 แล้วเราต้องการx บางค่า ที่g _i ( x ) < 0 สำหรับทุกiใน 1,..., mถ้าเราไม่มีจุดดังกล่าว เราจำเป็นต้องหาจุดนั้นโดยใช้วิธีที่เรียกว่าเฟสI ^{[ 4 ] : 11.4} วิธีเฟส I ง่ายๆ คือการแก้โปรแกรมแบบนูนต่อไปนี้: กำหนดให้คำตอบที่เหมาะสมที่สุดเป็น x*, s * $${\displaystyle {\begin{aligned}{\text{minimize}}\quad &s\\{\text{subject to}}\quad &g_{i}(x)\leq s{\text{ for }}i=1,\dots ,m\end{aligned}}}$$

• ถ้าs *<0 เราจะทราบว่า x* เป็นจุดภายในของปัญหาเดิม และสามารถดำเนินการต่อใน "ขั้นตอนที่สอง" ซึ่งก็คือการแก้ปัญหาเดิมได้
• ถ้าs *>0 แสดงว่าโปรแกรมดั้งเดิมนั้นไม่สามารถหาคำตอบได้ เนื่องจากบริเวณที่เป็นไปได้นั้นว่างเปล่า
• ถ้าs * = 0 และค่านี้เกิดขึ้นได้จากคำตอบ x* บางคำตอบ แสดงว่าปัญหานั้นสามารถแก้ไขได้ แต่ไม่มีจุดภายใน ถ้าหากค่านี้ไม่ได้เกิดขึ้นจากคำตอบ x* แสดงว่าปัญหานั้นไม่สามารถแก้ไขได้

สำหรับโปรแกรมนี้ การหาจุดภายในทำได้ง่าย: เราสามารถเลือกx = 0 ได้ตามอำเภอใจ และเลือกsให้เป็นจำนวนใดๆ ที่มากกว่า max( f ₁ (0),..., f _m (0)) ดังนั้นจึงสามารถแก้ปัญหาได้โดยใช้วิธีจุดภายใน อย่างไรก็ตาม เวลาในการทำงานจะแปรผันตรงกับ log(1/ s *) เมื่อ s* เข้าใกล้ 0 การหาคำตอบที่แน่นอนสำหรับปัญหาในเฟสที่ 1 ก็จะยากขึ้นเรื่อยๆ และทำให้ตัดสินใจได้ยากขึ้นว่าปัญหาดั้งเดิมนั้นสามารถแก้ไขได้หรือไม่

การรับประกันทางทฤษฎีถือว่าพารามิเตอร์การลงโทษเพิ่มขึ้นในอัตราดังนั้นจำนวนขั้นตอนของนิวตันที่ต้องการในกรณีที่เลวร้ายที่สุดคือในทางทฤษฎี ถ้าμมีค่ามากกว่า (เช่น 2 หรือมากกว่า) จำนวนขั้นตอนของนิวตันที่ต้องการในกรณีที่เลวร้ายที่สุดจะอยู่ในอย่างไรก็ตาม ในทางปฏิบัติμ ที่มากขึ้น จะนำไปสู่การลู่เข้าที่เร็วขึ้นมาก วิธีเหล่านี้เรียกว่า วิธี ขั้นตอนยาว^{[ 3 ] : ส่วนที่ 4.6} ในทางปฏิบัติ ถ้าμอยู่ระหว่าง 3 ถึง 100 โปรแกรมจะลู่เข้าภายใน 20-40 ขั้นตอนของนิวตัน โดยไม่คำนึงถึงจำนวนข้อจำกัด (แม้ว่าเวลาทำงานของแต่ละขั้นตอนของนิวตันจะเพิ่มขึ้นตามจำนวนข้อจำกัดก็ตาม) ค่าที่แน่นอนของμภายในช่วงนี้มีผลกระทบต่อประสิทธิภาพน้อยมาก^{[ 4 ] : บทที่ 11} ${\displaystyle \mu =\left(1+r/{\sqrt {M}}\right)}$${\displaystyle O({\sqrt {M}})}$${\displaystyle O(M)}$

สำหรับวิธีการลดศักยภาพ ปัญหาจะถูกนำเสนอในรูปแบบกรวย : ^{[ 3 ] : มาตรา 5}

ลดค่าc ^T x st xใน{b+L} ∩ Kให้ เหลือน้อยที่สุด

โดยที่bเป็นเวกเตอร์ใน R ⁿ , L เป็นปริภูมิย่อยเชิงเส้นใน R ⁿ (ดังนั้นb + Lเป็นระนาบเชิงเส้น ) และKเป็นกรวยนูนปลายแหลม ปิด ที่มีภายในไม่ว่างเปล่า โปรแกรมแบบนูนทุกโปรแกรมสามารถแปลงเป็นรูปแบบกรวยได้ ในการใช้วิธีการลดศักยภาพ (โดยเฉพาะการขยายอัลกอริทึมของ Karmarkarไปสู่การเขียนโปรแกรมแบบนูน) เราต้องการสมมติฐานต่อไปนี้: ^{[ 3 ] : มาตรา 6}

• A. เซตที่เป็นไปได้{b+L} ∩ Kมีขอบเขต และตัดกับส่วนภายในของกรวยK
• B. เราได้รับคำตอบที่เป็นไปได้อย่างเคร่งครัดx ^ ล่วงหน้า ซึ่งก็คือคำตอบที่เป็นไปได้ภายในK
• ค. เราทราบค่าเป้าหมายที่เหมาะสมที่สุด c* ของปัญหาไว้ล่วงหน้าแล้ว
• D. เราได้รับสิ่งกีดขวางที่สอดคล้องกันเอง แบบ M -logarithmically-homogeneous FสำหรับกรวยK

ข้อสมมติ A, B และ D เป็นสิ่งที่จำเป็นในวิธีการจุดภายในส่วนใหญ่ ข้อสมมติ C เป็นข้อสมมติเฉพาะของวิธีการของ Karmarkar ซึ่งสามารถแก้ไขได้โดยใช้ "ค่าวัตถุประสงค์แบบเลื่อน" นอกจากนี้ยังสามารถลดโปรแกรมให้อยู่ในรูปแบบของ Karmarkar ได้อีกด้วย :

ลดค่าs ^T x st xในM ∩ Kและe ^T x = 1 ให้เหลือน้อยที่สุด

โดยที่Mเป็นปริภูมิย่อยเชิงเส้นของ ใน R ⁿและค่าเป้าหมายที่เหมาะสมที่สุดคือ 0 วิธีการนี้ใช้ฟังก์ชันศักย์สเกลาร์ ดังต่อไปนี้:

v ( x ) = F ( x ) + M ln ( s ^T x )

โดยที่Fคือ สิ่งกีดขวางที่สอดคล้องกันเอง Mสำหรับกรวยที่เป็นไปได้ สามารถพิสูจน์ได้ว่า เมื่อxเป็นไปได้อย่างแท้จริงและv ( x ) มีค่าเล็กมาก (ลบมาก) xจะมีค่าประมาณที่เหมาะสมที่สุด แนวคิดของวิธีการลดศักยภาพคือการปรับเปลี่ยนxเพื่อให้ศักยภาพในแต่ละรอบลดลงอย่างน้อยค่าคงที่X (โดยเฉพาะX = 1/3 - ln(4/3)) ซึ่งหมายความว่า หลังจากiรอบ ความแตกต่างระหว่างค่าเป้าหมายและค่าเป้าหมายที่เหมาะสมที่สุดจะมีค่าไม่เกิน V * exp( -iX / M ) โดยที่Vเป็นค่าคงที่ที่ขึ้นอยู่กับข้อมูล ดังนั้น จำนวนขั้นตอนของนิวตันที่จำเป็นสำหรับคำตอบโดยประมาณε จะมีค่าไม่ เกิน ${\displaystyle O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)+1}$

โปรดทราบว่าในวิธีการติดตามเส้นทางนั้น นิพจน์จะเป็นแทนที่จะเป็นMซึ่งในทางทฤษฎีแล้วดีกว่า แต่ในทางปฏิบัติ วิธีการของคาร์มาร์การ์ช่วยให้สามารถก้าวไปสู่เป้าหมายได้ไกลขึ้นมาก ดังนั้นจึงอาจลู่เข้าได้เร็วกว่าที่รับประกันไว้ในทางทฤษฎี ${\displaystyle {\sqrt {M}}}$

แนวคิดของวิธีการคู่แบบดั้งเดิมนั้นง่ายต่อการสาธิตสำหรับการเพิ่มประสิทธิภาพแบบไม่เชิงเส้นที่ มีข้อจำกัด ^{[ 9 ] [ 10 ]}เพื่อความง่าย ให้พิจารณาปัญหาการเพิ่มประสิทธิภาพแบบไม่เชิงเส้นต่อไปนี้ที่มีข้อจำกัดความไม่เท่าเทียมกัน:

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f(x)\\{\text{subject to}}\quad &x\in \mathbb {R} ^{n},\\&c_{i}(x)\geq 0{\text{ for }}i=1,\ldots ,m,\\{\text{where}}\quad &f:\mathbb {R} ^{n}\to \mathbb {R} ,\ c_{i}:\mathbb {R} ^{n}\to \mathbb {R} .\end{aligned}}\quad (1)}$$

ปัญหาการหาค่าเหมาะสมที่สุดที่ถูกจำกัดด้วยความไม่เท่าเทียมกันนี้ได้รับการแก้ไขโดยการแปลงให้เป็นฟังก์ชันเป้าหมายที่ไม่ถูกจำกัด ซึ่งเราหวังว่าจะสามารถหาค่าต่ำสุดได้อย่างมีประสิทธิภาพ โดยเฉพาะอย่างยิ่งฟังก์ชันอุปสรรคแบบ ลอการิทึม ที่เกี่ยวข้องกับ (1) คือ $${\displaystyle B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)}$$

นี่คือค่าสเกลาร์บวกขนาดเล็ก ซึ่งบางครั้งเรียกว่า "พารามิเตอร์อุปสรรค" เมื่อลู่เข้าสู่ศูนย์ ค่าต่ำสุดของควรลู่เข้าสู่คำตอบของ (1) ${\displaystyle \mu }$${\displaystyle \mu }$${\displaystyle B(x,\mu )}$

เกรเดียนต์ของฟังก์ชันที่หาอนุพันธ์ได้จะใช้สัญลักษณ์ ส่วนเกรเดียนต์ของฟังก์ชันกั้นจะ ใช้สัญลักษณ์ แทน${\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle \nabla h}$$${\displaystyle \nabla B(x,\mu )=\nabla f(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x).\quad (3)}$$

นอกเหนือจากตัวแปรดั้งเดิม ("ตัวแปรหลัก") แล้วเรายังได้เพิ่มตัวแปรคู่ที่ได้รับ แรงบันดาล ใจจากตัวคูณลากรางจ์อีก ด้วย${\displaystyle x}$${\displaystyle \lambda \in \mathbb {R} ^{m}}$$${\displaystyle c_{i}(x)\lambda _{i}=\mu ,\quad \forall i=1,\ldots ,m.\quad (4)}$$

สมการ (4) บางครั้งเรียกว่าเงื่อนไข "ความสมบูรณ์ที่ถูกรบกวน" เนื่องจากมีความคล้ายคลึงกับ "ความหย่อนยานที่เสริมกัน" ในเงื่อนไข KKT

เราพยายามค้นหาค่าเหล่านั้นซึ่งความชันของฟังก์ชันกั้นเป็นศูนย์ ${\displaystyle (x_{\mu },\lambda _{\mu })}$

เมื่อแทนค่าจาก (4) ลงใน (3) เราจะได้สมการสำหรับเกรเดียนต์: โดยที่เมทริกซ์คือเมทริกซ์จาโคเบียนของข้อจำกัด ${\displaystyle 1/c_{i}(x)=\lambda _{i}/\mu }$$${\displaystyle \nabla B(x_{\mu },\lambda _{\mu })=\nabla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5)}$$${\displaystyle J}$${\displaystyle c(x)}$

แนวคิดเบื้องหลัง (5) คือเกรเดียนต์ของควรอยู่ในปริภูมิย่อยที่ครอบคลุมโดยเกรเดียนต์ของข้อจำกัด "ความสมบูรณ์ที่ถูกรบกวน" ที่มีขนาดเล็ก(4) สามารถเข้าใจได้ว่าเป็นเงื่อนไขที่ว่าคำตอบควรอยู่ใกล้ขอบเขตหรือการฉายภาพของเกรเดียนต์บนเวกเตอร์ปกติของส่วนประกอบข้อจำกัดควรเกือบเป็นศูนย์ ${\displaystyle f(x)}$${\displaystyle \mu }$${\displaystyle c_{i}(x)=0}$${\displaystyle \nabla f}$${\displaystyle c_{i}(x)}$

ให้เป็นทิศทางการค้นหาสำหรับการอัปเดตแบบวนซ้ำเมื่อใช้วิธีการของนิวตันกับ (4) และ (5) เราจะได้สมการสำหรับ: ${\displaystyle (p_{x},p_{\lambda })}$${\displaystyle (x,\lambda )}$${\displaystyle (p_{x},p_{\lambda })}$$${\displaystyle {\begin{pmatrix}H(x,\lambda )&-J(x)^{T}\\\operatorname {diag} (\lambda )J(x)&\operatorname {diag} (c(x))\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-\nabla f(x)+J(x)^{T}\lambda \\\mu 1-\operatorname {diag} (c(x))\lambda \end{pmatrix}},}$$

โดยที่คือเมทริกซ์เฮสเซียนของคือเมทริกซ์แนวทแยงของและคือเมทริกซ์แนวทแยงของ ${\displaystyle H}$${\displaystyle B(x,\mu )}$${\displaystyle \operatorname {diag} (\lambda )}$${\displaystyle \lambda }$${\displaystyle \operatorname {diag} (c(x))}$${\displaystyle c(x)}$

เนื่องจาก (1) (4) เงื่อนไข

${\displaystyle \lambda \geq 0}$

ควรบังคับใช้ในทุกขั้นตอน ซึ่งสามารถทำได้โดยการเลือกสิ่งที่เหมาะสม: ${\displaystyle \alpha }$

${\displaystyle (x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).}$

ต่อไปนี้เป็นกรณีพิเศษบางกรณีของโปรแกรมแบบนูนที่สามารถแก้ไขได้อย่างมีประสิทธิภาพด้วยวิธีการจุดภายใน^{[ 3 ] : มาตรา 10}

พิจารณาโปรแกรมเชิงเส้นในรูปแบบ: เราสามารถใช้วิธีการติดตามเส้นทางด้วยสิ่งกีดขวาง ฟังก์ชันมีความสอดคล้องในตัวเองโดยมีพารามิเตอร์M = m (จำนวนข้อจำกัด) ดังนั้น จำนวนขั้นตอนของนิวตันที่จำเป็นสำหรับวิธีการติดตามเส้นทางคือ O( mn² ⁾และความซับซ้อนของเวลาการทำงานทั้งหมดคือ O ( m³ ^/ 2n² ⁾$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b.\end{aligned}}.}$$$${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(b_{j}-a_{j}^{T}x).}$$${\displaystyle b}$

กำหนดให้โปรแกรมกำลังสองที่มีข้อจำกัดแบบกำลังสองในรูปแบบ: โดยที่เมทริกซ์ A _j ทั้งหมดเป็นเมทริกซ์บวกกึ่งกำหนดเราสามารถใช้วิธีการติดตามเส้นทางด้วยสิ่งกีดขวาง ฟังก์ชันเป็นสิ่งกีดขวางที่สอดคล้องกันเองโดยมีพารามิเตอร์M = mความซับซ้อนของนิวตันคือ O( (m+n)n ² ) และความซับซ้อนของเวลาการทำงานทั้งหมดคือ O( m ^1/2 (m+n) n ² ) $${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &d^{\top }x\\{\text{subject to}}\quad &f_{j}(x):=x^{\top }A_{j}x+b_{j}^{\top }x+c_{j}\leq 0\quad {\text{ for all }}j=1,\dots ,m,\end{aligned}}}$$$${\displaystyle b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).}$$${\displaystyle b}$

พิจารณาปัญหาในรูปแบบ ที่แต่ละเป็นเวกเตอร์ แต่ละเป็นสเกลาร์ และเป็นนอร์มL _pที่มีหลังจากแปลงเป็นรูปแบบมาตรฐานแล้ว เราสามารถใช้วิธีการติดตามเส้นทางด้วยสิ่งกีดขวางที่สอดคล้องกันเองโดยมีพารามิเตอร์M = 4 mความซับซ้อนของนิวตันคือ O( (m+n)n ² ) และความซับซ้อนของเวลาการทำงานทั้งหมดคือ O( m ^1/2 (m+n) n ² ) $${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{\top }x|_{p}\end{aligned}},}$$${\displaystyle u_{j}}$${\displaystyle v_{j}}$${\displaystyle |\cdot |_{p}}$${\displaystyle 1<p<\infty .}$

พิจารณาปัญหา

$${\displaystyle {\begin{aligned}\operatorname {minimize} \quad &f_{0}(x):=\sum _{i=1}^{k}c_{i0}\exp(a_{i}^{\top }x)\\{\text{subject to}}\quad &f_{j}(x):=\sum _{i=1}^{k}c_{ij}\exp(a_{i}^{\top }x)\leq d_{j}\quad {\text{ for all }}j=1,\dots ,m.\end{aligned}}}$$

มีสิ่งกีดขวางที่สอดคล้องกันเองโดยมีพารามิเตอร์ 2k + m วิธีการติดตามเส้นทางมีความซับซ้อนของนิวตัน O( ^{mk² +} k³ + n³ ) ^และความซับซ้อนโดยรวม O(( k + m ) ^{¹/ ²} [ mk² ⁺ k³ + n³ ] ⁾

สามารถใช้วิธีจุดภายในเพื่อแก้ปัญหาโปรแกรมกึ่งกำหนดเชิงบวกได้^{[ 3 ] : มาตรา 11}

• การปรับขนาดเชิงเส้น
• วิธีลากรางเจียนเสริม
• อัลกอริทึมแชมโบลล์-พ็อค
• เงื่อนไข Karush–Kuhn–Tucker
• วิธีการลงโทษ