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

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

วิธีการทรงรีมีประวัติความเป็นมาอันยาวนาน ในฐานะวิธีการวนซ้ำ เวอร์ชันเบื้องต้นได้รับการแนะนำโดยNaum Z. Shorในปี 1972 อัลกอริทึมการประมาณค่าสำหรับการหาค่าต่ำสุดของรูปทรงนูน จริง ได้รับการศึกษาโดยArkadi Nemirovskiและ David B. Yudin (Judin)

อัลกอริทึมวงรี (Ellipsoid Algorithm) ซึ่งเป็นอัลกอริทึมสำหรับแก้ ปัญหา การเขียนโปรแกรมเชิงเส้นที่มีข้อมูลเชิงตรรกะ ได้รับการศึกษาโดยLeonid Khachiyanและความสำเร็จของ Khachiyan คือการพิสูจน์ว่า โปรแกรมเชิงเส้นสามารถแก้ได้ใน เวลาพหุนามนี่เป็นก้าวสำคัญจากมุมมองทางทฤษฎี: อัลกอริทึมมาตรฐานสำหรับการแก้ปัญหาเชิงเส้นในขณะนั้นคือ อัลกอริทึมซิ มเพล็กซ์ (Simplex Algorithm) ซึ่ง โดยทั่วไปแล้วมีเวลาทำงานเป็นเชิงเส้นตามขนาดของปัญหา แต่ก็มีตัวอย่างที่เวลาทำงานเป็นเลขชี้กำลังตามขนาดของปัญหา ดังนั้น การมีอัลกอริทึมที่รับประกันได้ว่าเป็นเวลาพหุนามในทุกกรณีจึงเป็นความก้าวหน้าทางทฤษฎีครั้งสำคัญ

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

อัลกอริทึมทรงรีช่วยให้นักทฤษฎีความซับซ้อนบรรลุขอบเขต (กรณีที่เลวร้ายที่สุด) ที่ขึ้นอยู่กับมิติของปัญหาและขนาดของข้อมูล แต่ไม่ขึ้นอยู่กับจำนวนแถว ดังนั้นจึงยังคงมีความสำคัญใน ทฤษฎี การเพิ่มประสิทธิภาพเชิงการจัดเรียงมาเป็นเวลาหลายปี^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}เฉพาะในศตวรรษที่ 21 เท่านั้นที่อัลกอริทึมจุดภายในที่มีคุณสมบัติความซับซ้อนที่คล้ายกันปรากฏขึ้น

ปัญหาการหาค่าต่ำสุดแบบนูนประกอบด้วยส่วนประกอบดังต่อไปนี้

• ฟังก์ชันนูน ที่ต้องการหาค่าต่ำสุดบนเวกเตอร์(ซึ่งประกอบด้วย ตัวแปร nตัว)${\displaystyle f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle x}$
• ข้อจำกัดความไม่เท่าเทียมแบบนูนในรูปแบบโดยที่ฟังก์ชันเป็นฟังก์ชันนูน ข้อจำกัดเหล่านี้กำหนดเซตแบบนูน${\displaystyle f_{i}(x)\leqslant 0}$${\displaystyle f_{i}}$${\displaystyle Q}$
• ข้อจำกัดความเท่าเทียมเชิงเส้นในรูปแบบ.${\displaystyle h_{i}(x)=0}$

นอกจากนี้ เรายังได้รับทรงรี เริ่มต้น ซึ่งกำหนดไว้ดังนี้ ${\displaystyle {\mathcal {E}}^{(0)}\subset \mathbb {R} ^{n}}$

${\displaystyle {\mathcal {E}}^{(0)}=\left\{z\in \mathbb {R} ^{n}\ :\ (z-x_{0})^{T}P_{(0)}^{-1}(z-x_{0})\leqslant 1\right\}}$

ประกอบด้วยตัวลดค่าต่ำสุดโดยที่และเป็นจุดศูนย์กลางของ ${\displaystyle x^{*}}$${\displaystyle P_{(0)}\succ 0}$${\displaystyle x_{0}}$${\displaystyle {\mathcal {E}}}$

สุดท้ายนี้ เราต้องการการมีอยู่ของออราเคิลการแยกสำหรับเซตแบบนูนเมื่อกำหนดจุดออราเคิลควรส่งคืนคำตอบหนึ่งในสองคำตอบ: ^{[ 5 ]}${\displaystyle Q}$${\displaystyle x\in \mathbb {R} ^{n}}$

• "ประเด็นอยู่ที่" หรือ -${\displaystyle x}$${\displaystyle Q}$
• "ประเด็นไม่ได้อยู่ที่และยิ่งไปกว่านั้น นี่คือระนาบที่แยกออกจาก" นั่นคือ เวกเตอร์ที่ทำให้สำหรับทุกๆ${\displaystyle x}$${\displaystyle Q}$${\displaystyle x}$${\displaystyle Q}$${\displaystyle c}$${\displaystyle c\cdot x<c\cdot y}$${\displaystyle y\in Q}$

ผลลัพธ์ของวิธีการทรงรีจะเป็นอย่างใดอย่างหนึ่งดังต่อไปนี้:

• จุดใดๆ ในรูปทรงหลายเหลี่ยม(เช่น จุดที่เป็นไปได้ใดๆ) หรือ -${\displaystyle Q}$
• การพิสูจน์ที่ว่างเปล่า${\displaystyle Q}$

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

ในการ วนซ้ำครั้งที่ kของอัลกอริทึม เราจะได้จุดที่อยู่ตรงกลางของทรงรี ${\displaystyle x^{(k)}}$

${\displaystyle {\mathcal {E}}^{(k)}=\left\{x\in \mathbb {R} ^{n}\ :\ \left(xx^{(k)}\right)^{T}P_{(k)}^{-1}\left(xx^{(k)}\right)\leqslant 1\right\}.}$

เราสอบถามออราเคิลระนาบตัดเพื่อรับเวกเตอร์ที่ทำให้ ${\displaystyle g^{(k+1)}\in \mathbb {R} ^{n}}$

${\displaystyle g^{(k+1)T}\left(x^{*}-x^{(k)}\right)\leqslant 0.}$

ดังนั้นเราจึงสรุปได้ว่า

${\displaystyle x^{*}\in {\mathcal {E}}^{(k)}\cap \left\{z\ :\ g^{(k+1)T}\left(zx^{(k)}\right)\leqslant 0\right\}.}$

เรากำหนดให้เป็นทรงรีที่มีปริมาตรน้อยที่สุดซึ่งบรรจุครึ่งทรงรีที่อธิบายไว้ข้างต้น และคำนวณการอัปเดตจะได้รับโดย ${\displaystyle {\mathcal {E}}^{(k+1)}}$${\displaystyle x^{(k+1)}}$

${\displaystyle {\begin{aligned}x^{(k+1)}&=x^{(k)}-{\frac {1}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}\\P_{(k+1)}&={\frac {n^{2}}{n^{2}-1}}\left(P_{(k)}-{\frac {2}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}{\tilde {g}}^{(k+1)T}P_{(k)}\right)\end{aligned}}}$

ที่ไหน

${\displaystyle {\tilde {g}}^{(k+1)}=\left({\frac {1}{\sqrt {g^{(k+1)T}P_{(k)}g^{(k+1)}}}}\right)g^{(k+1)}.}$

เกณฑ์การหยุดนั้นกำหนดโดยคุณสมบัติที่ว่า

${\displaystyle {\sqrt {g^{(k)T}P_{(k)}g^{(k)}}}\leqslant \epsilon \quad \Rightarrow \quad f(x^{(k)})-f\left(x^{*}\right)\leqslant \epsilon .}$

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

• หากเป็นไปได้ ให้ทำการอัปเดตในลักษณะเดียวกันกับกรณีที่ไม่มีข้อจำกัด โดยเลือกซับเกรเดียนต์ที่ตรงตามเงื่อนไข${\displaystyle x^{(k)}}$${\displaystyle g_{0}}$

${\displaystyle g_{0}^{T}(x^{*}-x^{(k)})+f_{0}(x^{(k)})-f_{\rm {best}}^{(k)}\leqslant 0}$

• หากเป็นไปไม่ได้และละเมิด ข้อจำกัดที่ jให้ปรับปรุงทรงรีด้วยการตัดความเป็นไปได้ การตัดความเป็นไปได้ของเราอาจเป็นอนุพันธ์ย่อยของซึ่งต้องเป็นไปตามเงื่อนไข${\displaystyle x^{(k)}}$${\displaystyle g_{j}}$${\displaystyle f_{j}}$

${\displaystyle g_{j}^{T}(zx^{(k)})+f_{j}(x^{(k)})\leqslant 0}$

สำหรับค่า zที่ เป็นไปได้ทั้งหมด

การรับประกันความซับซ้อนของเวลาในการรันของวิธีทรงรีใน แบบจำลอง RAM จริงนั้นกำหนดโดยทฤษฎีบทต่อไปนี้^{[ 7 ] : ทฤษฎีบท 8.3.1}

พิจารณากลุ่ม ปัญหา การหาค่าเหมาะสมที่สุดแบบนูนในรูปแบบ: ลดค่าf ( x ) ให้เหลือน้อยที่สุด โดยที่ xอยู่ในGโดยที่fเป็นฟังก์ชันนูน และGเป็นเซตแบบนูน (เซตย่อยของปริภูมิยุคลิดRn ⁾แต่ละปัญหาpในกลุ่มนี้แสดงด้วยเวกเตอร์ข้อมูล Data( p ) เช่น สัมประสิทธิ์ค่าจริงในเมทริกซ์และเวกเตอร์ที่แสดงถึงฟังก์ชันfและบริเวณที่เป็นไปได้Gขนาดของปัญหาp , Size( p ) ถูกกำหนดให้เป็นจำนวนองค์ประกอบ (จำนวนจริง) ใน Data( p )ข้อสมมติฐานต่อไปนี้มีความจำเป็น:

1. G (บริเวณที่เป็นไปได้) คือ:
   • มีขอบเขต;
   • มีพื้นที่ภายในที่ไม่ว่างเปล่า (ดังนั้นจึงมีจุดที่เป็นไปได้อย่างแท้จริง)
2. เมื่อกำหนดข้อมูล ( p ) แล้ว เราสามารถคำนวณโดยใช้การดำเนินการทางคณิตศาสตร์ poly(Size(p)) ได้ดังนี้:
   • ทรงรีที่บรรจุG ไว้ ภายใน
   • ขอบล่าง 'MinVol(p) > 0' ของปริมาตรG
3. เมื่อกำหนดข้อมูล ( p ) และจุดxในRn ^แล้วเราสามารถคำนวณโดยใช้การดำเนินการทางคณิตศาสตร์ poly(Size(p)) ได้ดังนี้:
   • ออราเคิลการแยกสำหรับG (กล่าวคือ: ยืนยันว่าxอยู่ในGหรือส่งคืนไฮเปอร์เพลนที่แยกx ออก จากG )
   • ออราเคิลลำดับที่หนึ่งสำหรับf (นั่นคือ: คำนวณค่าของf ( x ) และซับเกรเดียนต์f' ( x ))

ภายใต้สมมติฐานเหล่านี้ วิธีการทรงรีเป็น "พหุนาม R" ซึ่งหมายความว่ามีพหุนาม Poly อยู่จริง โดยที่สำหรับทุกกรณีปัญหาpและทุกอัตราส่วนการประมาณค่าε > 0 วิธีการนี้จะพบคำตอบ x ที่สอดคล้องกับเงื่อนไขต่อไปนี้:

${\displaystyle f(x)-\min _{G}f\leq \varepsilon \cdot [\max _{G}f-\min _{G}f]}$,

โดยใช้การคำนวณทางคณิตศาสตร์กับจำนวนจริงไม่เกินจำนวนต่อไปนี้:

${\displaystyle Poly(Size(p))\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)}$

โดยที่V ( p ) เป็นปริมาณที่ขึ้นอยู่กับข้อมูล ตามสัญชาตญาณแล้ว หมายความว่าจำนวนการดำเนินการที่จำเป็นสำหรับความแม่นยำที่เพิ่มขึ้นแต่ละหลักนั้นเป็นพหุนามใน Size( p ) ในกรณีของวิธีทรงรี เราจะได้:

${\displaystyle V(p)=\left[{\frac {Vol({\text{initial ellipsoid}})}{Vol(G)}}\right]^{1/n}\leq \left[{\frac {Vol({\text{initial ellipsoid}})}{MinVol(p)}}\right]^{1/n}}$.

วิธีการทรงรีต้องใช้ขั้นตอนอย่างมากที่สุด และแต่ละขั้นตอนต้องใช้การดำเนินการทางคณิตศาสตร์ Poly(Size(p)) ครั้ง ${\displaystyle 2(n-1)n\cdot \ln \left({\frac {V(p)}{\epsilon }}\right)}$

วิธีวงรีใช้กับปัญหาที่มีมิติต่ำ เช่น ปัญหาตำแหน่งระนาบ ซึ่งมีความเสถียรเชิงตัวเลข Nemirovsky และ BenTal ^{[ 7 ] : Sec.8.3.3} กล่าวว่ามีประสิทธิภาพหากจำนวนตัวแปรไม่เกิน 20-30 ซึ่งเป็นเช่นนั้นแม้ว่าจะมีข้อจำกัดหลายพันข้อก็ตาม เนื่องจากจำนวนการวนซ้ำไม่ขึ้นอยู่กับจำนวนข้อจำกัด อย่างไรก็ตาม ในปัญหาที่มีตัวแปรจำนวนมาก วิธีวงรีไม่มีประสิทธิภาพมากนัก เนื่องจากจำนวนการวนซ้ำเพิ่มขึ้นเป็น O( n ² )

แม้แต่กับปัญหาที่มีขนาด "เล็ก" ก็ยังประสบปัญหาเรื่องความไม่เสถียรทางตัวเลขและประสิทธิภาพที่ไม่ดีในทางปฏิบัติ

วิธีการทรงรีเป็นเทคนิคทางทฤษฎีที่สำคัญในการเพิ่มประสิทธิภาพเชิงการจัดเรียงในทฤษฎีความซับซ้อนของ การคำนวณ อัลกอริทึมทรงรีมีความน่าสนใจเนื่องจากความซับซ้อนของมันขึ้นอยู่กับจำนวนคอลัมน์และขนาดดิจิทัลของสัมประสิทธิ์ แต่ไม่ขึ้นอยู่กับจำนวนแถว

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

Leonid Khachiyanได้ประยุกต์ใช้วิธีวงรีกับกรณีพิเศษของการเขียนโปรแกรมเชิงเส้น : ลดค่า c ^T x st Ax ≤ bโดยที่สัมประสิทธิ์ทั้งหมดใน A,b,c เป็นจำนวนตรรกยะ เขาแสดงให้เห็นว่าโปรแกรมเชิงเส้นสามารถแก้ไขได้ในเวลาพหุนาม นี่คือโครงร่างของทฤษฎีบทของ Khachiyan ^{[ 7 ] : Sec.8.4.2}

ขั้นตอนที่ 1: ลดปัญหาการหาค่าเหมาะสมที่สุดให้เหลือเพียงปัญหาการค้นหา ทฤษฎีบททวิภาวะของการเขียนโปรแกรมเชิงเส้นกล่าวว่า เราสามารถลดปัญหาการหาค่าต่ำสุดข้างต้นให้เหลือเพียงปัญหาการค้นหาได้ดังนี้: หาค่าx, yที่ทำให้Ax ≤ b ; A ^T y = c ; y ≤ 0 ; c ^T x=b ^T y ปัญหาแรกจะแก้ได้ก็ต่อเมื่อปัญหาที่สองแก้ได้ ในกรณีที่ปัญหาแก้ได้ ส่วนประกอบ xของคำตอบของปัญหาที่สองจะเป็นคำตอบที่ดีที่สุดของปัญหาแรก ดังนั้น จากนี้ไป เราสามารถสมมติได้ว่าเราต้องแก้ปัญหาต่อไปนี้: หาค่า z ≥ 0 ที่ทำให้Rz ≤ rโดยการคูณสัมประสิทธิ์ตรรกยะทั้งหมดด้วยตัวส่วนร่วม เราสามารถสมมติได้ว่าสัมประสิทธิ์ทั้งหมดเป็นจำนวนเต็ม

ขั้นตอนที่ 2: ลดการค้นหาให้เหลือเพียงการตรวจสอบความเป็นไปได้ปัญหาการหาz ≥ 0 ที่ทำให้Rz ≤ rสามารถลดทอนให้เหลือปัญหาการตัดสินใจแบบไบนารีได้ดังนี้: " มีz ≥ 0ที่ทำให้Rz ≤ rหรือไม่? " สามารถทำได้ดังนี้ หากคำตอบของปัญหาการตัดสินใจคือ "ไม่" คำตอบของปัญหาการค้นหาก็คือ "ไม่มี" และเราก็เสร็จสิ้นกระบวนการ มิฉะนั้น ให้นำข้อจำกัดอสมการแรกR ₁ z ≤ r ₁มาแทนที่ด้วยสมการR ₁ z = r ₁แล้วนำปัญหาการตัดสินใจไปใช้อีกครั้ง หากคำตอบคือ "ใช่" เราจะคงสมการไว้ หากคำตอบคือ "ไม่" แสดงว่าอสมการนั้นซ้ำซ้อน และเราสามารถลบออกได้ จากนั้นเราจะดำเนินการต่อไปยังข้อจำกัดอสมการถัดไป สำหรับแต่ละข้อจำกัด เราจะแปลงเป็นสมการหรือลบออก สุดท้ายนี้ เรามีเพียงข้อจำกัดความเท่าเทียมกัน ซึ่งสามารถแก้ไขได้ด้วยวิธีการใดๆ ก็ได้สำหรับการแก้ระบบสมการเชิงเส้น

ขั้นตอนที่ 3 : ปัญหาการตัดสินใจสามารถลดทอนลงเป็นปัญหาการหาค่าเหมาะสมที่สุดที่แตกต่างออกไป กำหนดฟังก์ชันส่วนเหลือ f(z) := max[(Rz) ₁ -r ₁ , (Rz ) ₂ -r ₂ , (Rz) ₃ -r ₃ ,...] เห็นได้ชัดว่าf ( z )≤0 ก็ต่อเมื่อRz ≤ rดังนั้น ในการแก้ปัญหาการตัดสินใจ จึงเพียงพอที่จะแก้ปัญหาการหาค่าต่ำสุด: min _z f ( z ) ฟังก์ชันfเป็นฟังก์ชันนูน (เป็นค่าสูงสุดของฟังก์ชันเชิงเส้น) แทนค่าต่ำสุดด้วยf * ดังนั้น คำตอบของปัญหาการตัดสินใจคือ "ใช่" ก็ต่อเมื่อ f*≤0

ขั้นตอนที่ 4 : ในปัญหาการหาค่าเหมาะสมที่สุด min _z f ( z ) เราสามารถสมมติได้ว่าzอยู่ในกล่องที่มีความยาวด้าน 2 ^Lโดยที่Lคือความยาวบิตของข้อมูลปัญหา ดังนั้น เราจึงมีโปรแกรมแบบนูนที่มีขอบเขต ซึ่งสามารถแก้ไขได้จนถึงความแม่นยำ ε ใดๆ โดยใช้วิธีวงรี ในเวลาที่เป็นพหุนามใน L

ขั้นตอนที่ 5 : สามารถพิสูจน์ได้ว่า ถ้า f*>0 แล้ว f*>2 ^-poly(L)สำหรับพหุนามบางตัว ดังนั้น เราสามารถเลือกความแม่นยำ ε=2 ^-poly(L)ได้ จากนั้น คำตอบโดยประมาณ ε ที่พบโดยวิธีวงรีจะเป็นบวกก็ต่อเมื่อ f*>0 ก็ต่อเมื่อปัญหาการตัดสินใจไม่สามารถแก้ไขได้

วิธีการทรงรีมีหลายรูปแบบ ขึ้นอยู่กับว่าใช้การตัดแบบใดในแต่ละขั้นตอน^{[ 1 ] : มาตรา 3}

ในวิธีการตัดวงรีตรงกลาง^{[ 1 ]} : ^{82, 87–94} การตัดจะผ่านจุดศูนย์กลางของวงรีปัจจุบันเสมอ อินพุตคือจำนวนตรรกยะε >0, ทรงนูนKที่กำหนดโดยออราเคิลการแยกแบบอ่อนและจำนวนRที่ S(0, R ) (ทรงกลมรัศมี R รอบจุดกำเนิด) บรรจุKเอาต์พุตคือหนึ่งในสิ่งต่อไปนี้:

• (ก) เวกเตอร์ที่อยู่ห่างจาก K ไม่เกินεหรือ --
• ( b) เมทริกซ์บวกแน่นอนAและจุดaโดยที่ทรงรี E( A , a ) บรรจุKและปริมาตรของ E( A , a ) มีค่าไม่เกินε

จำนวนขั้นตอนคือ, จำนวนหลักความแม่นยำที่ต้องการคือp  := 8 Nและความแม่นยำที่ต้องการของออราเคิลการแยกคือd :  = 2 ^{− p}${\displaystyle N:=\lceil 5n\log(1/\epsilon )+5n^{2}\log(2R)\rceil }$

ในวิธีการตัดวงรีแบบลึก^{[ 1 ]} : ⁸³ การตัดจะลบวงรีออกไปมากกว่าครึ่งในแต่ละขั้นตอน ซึ่งทำให้การค้นพบว่าKว่างเปล่าเร็วขึ้น อย่างไรก็ตาม เมื่อKไม่ว่างเปล่า มีตัวอย่างที่วิธีการตัดตรงกลางจะพบจุดที่เป็นไปได้เร็วกว่า การใช้การตัดแบบลึกไม่ได้เปลี่ยนแปลงลำดับขนาดของเวลาการทำงาน

ในวิธีการตัดวงรีแบบตื้น^{[ 1 ]} : ^{83, 94–101} การตัดจะลบวงรีน้อยกว่าครึ่งหนึ่งในแต่ละขั้นตอน ตัวแปรนี้ไม่ค่อยมีประโยชน์ในทางปฏิบัติ แต่มีความสำคัญทางทฤษฎี: ช่วยให้สามารถพิสูจน์ผลลัพธ์ที่ไม่สามารถหาได้จากตัวแปรอื่น อินพุตคือจำนวนตรรกยะε >0, ทรงนูนKที่กำหนดโดยออราเคิลการแยกแบบตื้นและจำนวนRที่ S(0, R ) ประกอบด้วยKเอาต์พุตคือเมทริกซ์บวกแน่นอนAและจุดaที่เป็นไปตามเงื่อนไขข้อใดข้อหนึ่งต่อไปนี้:

• (a) ทรงรี E( A , a ) ได้รับการประกาศว่า "แข็งแกร่ง" โดยเทพพยากรณ์ หรือ -
• (b) Kอยู่ใน E( A , a ) และปริมาตรของ E( A , a ) มี ค่าไม่เกินε

จำนวนขั้นตอนคือและจำนวนหลักความแม่นยำที่ต้องการคือp  := 8 N${\displaystyle N:=\lceil 5n(n+1)^{2}\log(1/\epsilon )+5n^{2}(n+1)^{2}\log(2R)+\log(n+1)\rceil }$

นอกจากนี้ยังมีความแตกต่างระหว่างวิธีการทรงรีล้อมรอบและวิธีการทรงรีภายในด้วย: ^{[ 8 ]}

• ในวิธีการวงรีล้อมรอบแต่ละรอบจะค้นหาวงรีที่มี ปริมาตร น้อยที่สุดซึ่งบรรจุส่วนที่เหลือของวงรีก่อนหน้า วิธีนี้ได้รับการพัฒนาโดย Yudin และ Nemirovskii ^{[ 9 ]}
• ในวิธีการวงรีที่จารึกไว้แต่ละรอบจะค้นหาวงรีที่มี ปริมาตร มากที่สุดซึ่งบรรจุส่วนที่เหลือของวงรีก่อนหน้า วิธีนี้ได้รับการพัฒนาโดย Tarasov, Khachian และ Erlikh ^{[ 10 ]}

วิธีการทั้งสองแตกต่างกันในด้านความซับซ้อนของเวลาในการประมวลผล (ด้านล่างnคือจำนวนตัวแปร และ epsilon คือความแม่นยำ):

• วิธีการแบบจำกัดขอบเขตต้องใช้การทำซ้ำ โดยแต่ละรอบประกอบด้วยการหาไฮเปอร์เพลนที่แยกออกจากกันและการหาทรงรีที่จำกัดขอบเขตใหม่ การหาทรงรีที่จำกัดขอบเขตต้องใช้เวลา${\displaystyle O(n^{2})\ln {\frac {1}{\epsilon }}}$${\displaystyle O(n^{2})}$
• วิธีการสร้างวงรีแนบในต้องใช้การวนซ้ำ โดยแต่ละการวนซ้ำประกอบด้วยการหาไฮเปอร์เพลนที่แยกวงรีออกจากวงรีอื่น และการหาวงรีแนบในวงรีใหม่ การหาวงรีแนบในวงรีต้องใช้เวลาพอสมควรสำหรับค่าเล็กๆ ค่าหนึ่ง${\displaystyle O(n)\ln {\frac {1}{\epsilon }}}$${\displaystyle O(n^{3.5+\delta })}$${\displaystyle \delta >0}$

ประสิทธิภาพเชิงสัมพัทธ์ของวิธีการขึ้นอยู่กับเวลาที่ใช้ในการค้นหาไฮเปอร์เพลนที่แยก ซึ่งขึ้นอยู่กับการใช้งาน: หากรันไทม์เป็นวิธีการแบบวงกลมจะมีประสิทธิภาพมากกว่า แต่ถ้าวิธีการแบบวงกลมจะมีประสิทธิภาพมากกว่า^{[ 8 ]}${\displaystyle O(n^{t})}$${\displaystyle t\leq 2.5}$${\displaystyle t>2.5}$

• วิธีหาจุดศูนย์ถ่วงเป็นวิธีที่เข้าใจง่ายกว่าและใช้ขั้นตอนน้อยกว่า อย่างไรก็ตาม แต่ละขั้นตอนใช้ทรัพยากรในการคำนวณสูง เนื่องจากต้องคำนวณจุดศูนย์ถ่วงของรูปทรงหลายเหลี่ยมที่เป็นไปได้ในปัจจุบัน
• วิธีการจุดภายในก็ช่วยให้สามารถแก้ปัญหาการหาค่าเหมาะสมที่สุดแบบนูนได้ในเวลาพหุนามเช่นกัน แต่ประสิทธิภาพในทางปฏิบัติจะดีกว่าวิธีการทรงรีมาก

• Dmitris Alevras และ Manfred W. Padberg, การหาค่าเหมาะสมที่สุดเชิงเส้นและส่วนขยาย: ปัญหาและส่วนขยาย , Universitext, Springer-Verlag, 2001. (ปัญหาจาก Padberg พร้อมคำตอบ)
• V. Chandru และ MRRao, การเขียนโปรแกรมเชิงเส้น, บทที่ 31 ใน Algorithms and Theory of Computation Handbook , เรียบเรียงโดย MJAtallah, CRC Press 1999, หน้า 31-1 ถึง 31-37
• V. Chandru และ MRRao, การเขียนโปรแกรมจำนวนเต็ม, บทที่ 32 ในAlgorithms and Theory of Computation Handbook , เรียบเรียงโดย MJAtallah, CRC Press 1999, หน้า 32-1 ถึง 32-45
• George B. Dantzigและ Mukund N. Thapa. 1997. การเขียนโปรแกรมเชิงเส้น 1: บทนำ . Springer-Verlag.
• George B. Dantzigและ Mukund N. Thapa. 2003. การเขียนโปรแกรมเชิงเส้น 2: ทฤษฎีและส่วนขยาย . Springer-Verlag.
• L. Lovász : ทฤษฎีเชิงอัลกอริทึมของจำนวน กราฟ และความนูน , การประชุมระดับภูมิภาค CBMS-NSF ในสาขาคณิตศาสตร์ประยุกต์ ครั้งที่ 50, SIAM, ฟิลาเดลเฟีย, เพนซิลเวเนีย, 1986
• Kattta G. Murty, การเขียนโปรแกรมเชิงเส้น , Wiley, 1983.
• M. Padberg , การหาค่าเหมาะสมเชิงเส้นและการขยายเพิ่มเติม , ฉบับพิมพ์ครั้งที่สอง, Springer-Verlag, 1999.
• Christos H. Papadimitriouและ Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity , ฉบับแก้ไขตีพิมพ์ใหม่พร้อมคำนำฉบับใหม่, Dover.
• อเล็กซานเดอร์ ชไรเวอร์ทฤษฎี การ เขียนโปรแกรมเชิงเส้นและจำนวนเต็มจอห์น ไวลีย์และบุตรชาย, 1998, ISBN 0-471-98232-6

• EE364bหน้าเว็บหลักของรายวิชาจากมหาวิทยาลัยสแตนฟอร์ด