البرمجة شبه المحددة

تُعرَّف مسألة البرمجة الخطية بأنها مسألة نسعى فيها إلى تعظيم أو تصغير دالة هدف خطية لمتغيرات حقيقية على متعدد السطوح . أما في البرمجة شبه المحددة، فنستخدم متجهات ذات قيم حقيقية، ويُسمح لنا بأخذ الضرب النقطي للمتجهات؛ وتُستبدل قيود عدم السلبية على المتغيرات الحقيقية في البرمجة الخطية بقيود شبه التحديد على متغيرات المصفوفات في البرمجة شبه المحددة . وبشكل أدق، يمكن تعريف مسألة البرمجة شبه المحددة العامة بأنها أي مسألة برمجة رياضية على الشكل التالي:

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{subject to}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{\text{ for all }}k\\\end{array}}}$

حيث${\displaystyle c_{i,j},a_{i,j,k}}$و${\displaystyle b_{k}}$هي أعداد حقيقية و${\displaystyle x^{i}\cdot x^{j}}$هو حاصل الضرب النقطي لـ${\displaystyle x^{i}}$و ${\displaystyle x^{j}}$.

أن${\displaystyle n\times n}$مصفوفة${\displaystyle M}$يُقال إن المصفوفة شبه موجبة إذا كانت مصفوفة غرام لبعض المتجهات (أي إذا وُجدت متجهات).${\displaystyle x^{1},\ldots ,x^{n}}$بحيث${\displaystyle m_{i,j}=x^{i}\cdot x^{j}}$للجميع${\displaystyle i,j}$). إذا كان هذا هو الحال، فإننا نرمز إلى ذلك بـ${\displaystyle M\succeq 0}$لاحظ أن هناك العديد من التعريفات المكافئة الأخرى لكونها شبه موجبة، على سبيل المثال، المصفوفات شبه الموجبة هي مصفوفات ذاتية الترافق لها قيم ذاتية غير سالبة فقط .

يرمز بـ${\displaystyle \mathbb {S} ^{n}}$مساحة الجميع${\displaystyle n\times n}$المصفوفات المتناظرة الحقيقية. الفضاء مزود بالضرب الداخلي (حيث${\displaystyle {\rm {trace}}}$يشير إلى الأثر ):

${\displaystyle \langle A,B\rangle$ :={\rm {trace}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.}

يمكننا إعادة كتابة البرنامج الرياضي الوارد في القسم السابق بشكل مكافئ على النحو التالي:

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle \leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

مكان الدخول${\displaystyle i,j}$في${\displaystyle C}$يُعطى بواسطة${\displaystyle {\frac {c_{i,j}+c_{j,i}}{2}}}$من القسم السابق و${\displaystyle A_{k}}$هو متناظر${\displaystyle n\times n}$مصفوفة${\displaystyle i,j}$المدخل رقم 1${\displaystyle {\frac {a_{i,j,k}+a_{j,i,k}}{2}}}$من القسم السابق. وبالتالي، فإن المصفوفات ${\displaystyle C}$و${\displaystyle A_{k}}$متناظرة، والمنتجات الداخلية المذكورة أعلاه محددة جيدًا.

لاحظ أنه إذا أضفنا متغيرات الركود بشكل مناسب، فيمكن تحويل هذا النموذج شبه المحدد إلى شكل معادلة :

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle =b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

لتبسيط الأمر، يمكن تحديد SDP بصيغة مختلفة قليلاً، ولكنها مكافئة. على سبيل المثال، يمكن إضافة التعبيرات الخطية التي تتضمن متغيرات عددية غير سالبة إلى مواصفات البرنامج. ويبقى هذا SDP لأن كل متغير يمكن تضمينه في المصفوفة.${\displaystyle X}$كمدخل قطري (${\displaystyle X_{ii}}$بالنسبة للبعض${\displaystyle i}$لضمان ذلك${\displaystyle X_{ii}\geq 0}$، قيود${\displaystyle X_{ij}=0}$يمكن إضافته للجميع${\displaystyle j\neq i}$كمثال آخر، لاحظ أنه لأي مصفوفة شبه موجبة محددة${\displaystyle X}$، توجد مجموعة من المتجهات${\displaystyle \{v_{i}\}}$بحيث يكون${\displaystyle i}$،${\displaystyle j}$دخول${\displaystyle X}$يكون${\displaystyle X_{ij}=(v_{i},v_{j})}$الضرب القياسي لـ${\displaystyle v_{i}}$و${\displaystyle v_{j}}$لذلك، غالبًا ما تُصاغ مسائل البرمجة شبه المحددة (SDPs) بدلالة تعابير خطية على حاصل الضرب القياسي للمتجهات. وبمعرفة حل مسألة البرمجة شبه المحددة في صورتها القياسية، فإن المتجهات${\displaystyle \{v_{i}\}}$يمكن استعادتها في${\displaystyle O(n^{3})}$الوقت (على سبيل المثال، باستخدام تحليل تشوليسكي غير الكامل لـ X).

على غرار البرمجة الخطية، بالنظر إلى برنامج برمجة شبه محددة عام من الشكل

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{i},X\rangle =b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}}$

(المسألة الأولية أو P-SDP)، نُعرّف البرنامج شبه المحدد المزدوج (D-SDP) على النحو التالي:

${\displaystyle {\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&b^{T}y\\{\text{subject to}}&{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}}$

حيث بالنسبة لأي مصفوفتين${\displaystyle P}$و${\displaystyle Q}$،${\displaystyle P\succeq Q}$وسائل${\displaystyle P-Q\succeq 0}$.

تنص نظرية الازدواجية الضعيفة على أن قيمة مسألة البرمجة شبه المحددة الأولية (SDP) لا تقل عن قيمة مسألة البرمجة شبه المحددة الثنائية (SDP). وبالتالي، فإن أي حل ممكن لمسألة البرمجة شبه المحددة الثنائية يحد من قيمة مسألة البرمجة شبه المحددة الأولية، وعلى العكس من ذلك، فإن أي حل ممكن لمسألة البرمجة شبه المحددة الأولية يحد من قيمة مسألة البرمجة شبه المحددة الثنائية. وذلك لأن

${\displaystyle \langle C,X\rangle -b^{T}y=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}b_{i}=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\sum _{i=1}^{m}y_{i}A_{i},X\rangle \geq 0,}$

حيث أن المتباينة الأخيرة هي لأن كلا المصفوفتين شبه موجبة، ويشار أحيانًا إلى نتيجة هذه الدالة باسم فجوة الازدواجية.

عندما تتساوى قيمة برنامج البرمجة شبه المحددة (SDP) الأولي والثنائي، يُقال إن برنامج البرمجة شبه المحددة يحقق خاصية الازدواجية القوية . على عكس البرامج الخطية ، حيث يكون لكل برنامج خطي ثنائي هدف أمثل يساوي هدف البرنامج الأولي، لا يحقق كل برنامج برمجة شبه محددة خاصية الازدواجية القوية؛ بشكل عام، قد تكون قيمة برنامج البرمجة شبه المحددة الثنائي أقل بكثير من قيمة البرنامج الأولي، ويحقق كل من برنامج البرمجة شبه المحددة الأولي (P-SDP) وبرنامج البرمجة شبه المحددة الثنائي (D-SDP) الخصائص التالية:

(أ) لنفترض أن المسألة الأولية (P-SDP) محدودة من الأسفل وقابلة للحل تمامًا (أي، يوجد ${\displaystyle X_{0}\in \mathbb {S} ^{n},X_{0}\succ 0}$بحيث${\displaystyle \langle A_{i},X_{0}\rangle =b_{i}}$،${\displaystyle i=1,\ldots ,m}$ثم يوجد حل أمثل${\displaystyle y^{*}}$إلى (D-SDP) و

${\displaystyle \langle C,X^{*}\rangle =b^{T}y^{*}.}$

(ii) لنفترض أن المسألة الثنائية (D-SDP) محدودة من الأعلى وقابلة للحل تمامًا (أي، ${\displaystyle \sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C}$بالنسبة للبعض${\displaystyle y_{0}\in \mathbb {R} ^{m}}$ثم يوجد حل أمثل${\displaystyle X^{*}}$إلى (P-SDP) ويتحقق التساوي من (i).

يُعد شرط سلاتر شرطًا كافيًا لتحقيق الازدواجية القوية في مسائل البرمجة شبه المحددة (وبشكل عام، في أي مسألة تحسين محدبة) . كما يُمكن تحقيق الازدواجية القوية في مسائل البرمجة شبه المحددة دون شروط انتظام إضافية باستخدام مسألة ازدواجية موسعة اقترحها رامانا. ^{[ 2 ] [ 3 ]}

لنفترض وجود ثلاثة متغيرات عشوائية${\displaystyle A}$،${\displaystyle B}$، و${\displaystyle C}$مجموعة معينة من معاملات الارتباط${\displaystyle \rho _{AB},\ \rho _{AC},\rho _{BC}}$تكون ممكنة إذا وفقط إذا

${\displaystyle {\begin{pmatrix}1&\rho _{AB}&\rho _{AC}\\\rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _{BC}&1\end{pmatrix}}\succeq 0.}$

تُسمى هذه المصفوفة مصفوفة الارتباط . لنفترض أننا نعلم من بعض المعرفة المسبقة (النتائج التجريبية لتجربة ما، على سبيل المثال) أن${\displaystyle -0.2\leq \rho _{AB}\leq -0.1}$و${\displaystyle 0.4\leq \rho _{BC}\leq 0.5}$مشكلة تحديد أصغر وأكبر القيم التي${\displaystyle \rho _{AC}\ }$يمكن أن يأخذ ما يلي:

${\displaystyle {\begin{array}{rl}{\displaystyle \min /\max }&x_{13}\\{\text{subject to}}&-0.2\leq x_{12}\leq -0.1\\&0.4\leq x_{23}\leq 0.5\\&{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0\end{array}}}$

لقد حددنا${\displaystyle \rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23}}$للحصول على الإجابة، يمكن صياغة ذلك باستخدام برنامج شبه محدد. نتعامل مع قيود المتباينات عن طريق زيادة مصفوفة المتغيرات وإدخال متغيرات راكدة ، على سبيل المثال

${\displaystyle \mathrm {tr} \left(\left({\begin{array}{cccccc}0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right)\cdot \left({\begin{array}{cccccc}1&x_{12}&x_{13}&0&0&0\\x_{12}&1&x_{23}&0&0&0\\x_{13}&x_{23}&1&0&0&0\\0&0&0&s_{1}&0&0\\0&0&0&0&s_{2}&0\\0&0&0&0&0&s_{3}\end{array}}\right)\right)=x_{12}+s_{1}=-0.1}$

حل هذه المسألة البرمجية شبه المحددة يعطي القيم الدنيا والقصوى لـ${\displaystyle \rho _{AC}=x_{13}\ }$مثل${\displaystyle -0.978}$و${\displaystyle 0.872}$على التوالى.

لننظر في المشكلة

تقليل${\displaystyle {\frac {(c^{T}x)^{2}}{d^{T}x}}}$

رهناً بـ${\displaystyle Ax+b\geq 0}$

حيث نفترض أن${\displaystyle d^{T}x>0}$حينما${\displaystyle Ax+b\geq 0}$.

إدخال متغير مساعد${\displaystyle t}$يمكن إعادة صياغة المشكلة:

تقليل${\displaystyle t}$

رهناً بـ${\displaystyle Ax+b\geq 0,\,{\frac {(c^{T}x)^{2}}{d^{T}x}}\leq t}$

في هذه الصيغة، يكون الهدف دالة خطية للمتغيرات${\displaystyle x,t}$.

يمكن كتابة القيد الأول على النحو التالي:

${\displaystyle {\textbf {diag}}(Ax+b)\geq 0}$

حيث المصفوفة${\displaystyle {\textbf {diag}}(Ax+b)}$هي مصفوفة مربعة قيم عناصر قطرها الرئيسي تساوي عناصر المتجه${\displaystyle Ax+b}$.

يمكن كتابة القيد الثاني على النحو التالي:

${\displaystyle td^{T}x-(c^{T}x)^{2}\geq 0}$

تعريف${\displaystyle D}$كما يلي

${\displaystyle D=\left[{\begin{array}{cc}t&c^{T}x\\c^{T}x&d^{T}x\end{array}}\right]}$

يمكننا استخدام نظرية مكملات شور لنرى أن

${\displaystyle D\succeq 0}$

(بويد وفاندنبيرغ، 1996)

البرنامج شبه المحدد المرتبط بهذه المسألة هو

تقليل${\displaystyle t}$

رهناً بـ${\displaystyle \left[{\begin{array}{ccc}{\textbf {diag}}(Ax+b)&0&0\\0&t&c^{T}x\\0&c^{T}x&d^{T}x\end{array}}\right]\succeq 0}$

تُعدّ البرامج شبه المحددة أدوات مهمة لتطوير خوارزميات تقريبية لمسائل التعظيم الصعبة من نوع NP. تعود أول خوارزمية تقريبية قائمة على برنامج شبه محدد إلى ميشيل غويمانز وديفيد ب. ويليامسون (JACM، 1995). ^{[ 1 ] : الفصل 1.} درسوا مسألة القطع الأقصى : بالنظر إلى رسم بياني G = ( V , E )، المطلوب هو إخراج تجزئة للرؤوس V بحيث تُعظّم عدد الحواف المتقاطعة من جانب إلى آخر. يمكن التعبير عن هذه المسألة كبرنامج تربيعي صحيح .

تحقيق أقصى استفادة${\displaystyle \sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},}$بحيث يكون كل${\displaystyle v_{i}\in \{1,-1\}}$.

ما لم يكن P = NP ، لا يمكننا حل مسألة التعظيم هذه بكفاءة. ومع ذلك، لاحظ غومانز وويليامسون إجراءً عامًا من ثلاث خطوات لمعالجة هذا النوع من المسائل:

1. قم بتحويل برنامج التربيع الصحيح إلى برنامج شبه محدد. (يمكن اشتقاق ذلك أيضًا باستخدام المستوى الأول من التسلسل الهرمي لمجموع المربعات .)
2. حل مسألة البرمجة شبه المحددة (ضمن هامش خطأ إضافي صغير بشكل تعسفي)${\displaystyle \epsilon }$).
3. قم بتقريب حل SDP للحصول على حل تقريبي لبرنامج التربيع الصحيح الأصلي.

للحصول على أفضل النتائج، فإن الاسترخاء الطبيعي هو

${\displaystyle \max \sum _{(i,j)\in E}{\frac {1-\langle v_{i},v_{j}\rangle }{2}},}$بحيث${\displaystyle \lVert v_{i}\rVert ^{2}=1}$، حيث يكون التعظيم على المتجهات${\displaystyle \{v_{i}\}}$بدلاً من الأعداد الصحيحة.

هذه مسألة برمجة شبه محددة (SDP) لأن دالة الهدف والقيود كلها دوال خطية لضرب المتجهات الداخلي. حل مسألة البرمجة شبه المحددة يعطي مجموعة من متجهات الوحدة في${\displaystyle \mathbf {R^{n}} }$بما أن المتجهات ليست بالضرورة على استقامة واحدة، فإن قيمة هذا البرنامج المُخفف لا يمكن أن تتجاوز قيمة برنامج الأعداد الصحيحة التربيعي الأصلي. وأخيرًا، يلزم إجراء عملية تقريب للحصول على التقسيم. يختار غومانز وويليامسون ببساطة مستوىً فائقًا عشوائيًا منتظمًا يمر بنقطة الأصل، ويقسمان الرؤوس وفقًا لموقع المتجهات المقابلة على هذا المستوى الفائق. يُظهر تحليل مباشر أن هذه العملية تحقق نسبة تقريب متوقعة (ضمان أداء) قدرها 0.87856 - ε. (القيمة المتوقعة للقطع هي مجموع احتمالية قطع الحافة على طولها، وهي تتناسب مع الزاوية).${\displaystyle \cos ^{-1}\langle v_{i},v_{j}\rangle }$بين المتجهات عند نهايتي الحافة فوق${\displaystyle \pi }$مقارنة هذا الاحتمال بـ${\displaystyle (1-\langle v_{i},v_{j}\rangle )/{2}}$(في التوقع تكون النسبة دائمًا على الأقل 0.87856.) بافتراض فرضية الألعاب الفريدة ، يمكن إثبات أن نسبة التقريب هذه هي الأمثل بشكل أساسي.

منذ الورقة البحثية الأصلية لجويمانز وويليامسون، تم تطبيق البرمجة شبه المحددة لتطوير العديد من خوارزميات التقريب. وفي وقت لاحق، طور براساد راغافيندرا إطارًا عامًا لمسائل إرضاء القيود استنادًا إلى فرضية الألعاب الفريدة . ^{[ 4 ]}

طُبقت البرمجة شبه المحددة لإيجاد حلول تقريبية لمسائل التحسين التوافقي، مثل حل مسألة القطع الأقصى بنسبة تقريبية تبلغ 0.87856. كما تُستخدم البرمجة شبه المحددة في الهندسة لتحديد مخططات التنسيغريتي، وتظهر في نظرية التحكم كمتباينات خطية مصفوفية ، وفي مسائل معامل القطع الناقص العكسي كقيود محدبة وغير خطية وشبه محددة. ^{[ 5 ]} كما تُستخدم على نطاق واسع في الفيزياء لتقييد نظريات الحقول المطابقة باستخدام التمهيد المطابق . ^{[ 6 ]}

طريقة القطع الناقص هي طريقة عامة للبرمجة المحدبة، ويمكن استخدامها على وجه الخصوص لحل مسائل البرمجة شبه المحددة (SDP). في سياق مسائل البرمجة شبه المحددة، توفر طريقة القطع الناقص الضمان التالي: ^{[ 1 ] : نظرية 2.6.1} : لنفترض مسألة برمجة شبه محددة بالصيغة المعادلة التالية:

${\displaystyle {\begin{array}{rl}{\displaystyle \max _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle \\{\text{subject to}}&\langle A_{k},X\rangle =b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}}$

ليكن L هو الفضاء الجزئي الأفيني للمصفوفات في S n التي تحقق القيود المعادلاتية m ؛ لذلك يمكن كتابة SDP على النحو التالي:${\displaystyle \max _{X\in L}\langle C,X\rangle {\text{ subject to }}X\succeq 0}$لنفترض أن جميع المعاملات في مسألة البرمجة شبه المحددة (SDP) أعداد نسبية. ولتكن R حدًا أعلى معطى صراحةً لأقصى معيار فروبينيوس لحل ممكن، و ε > 0 ثابتًا. تُسمى المصفوفة X في S n عميقة من الرتبة ε إذا كانت كل مصفوفة Y في L n بمسافة فروبينيوس لا تتجاوز ε من X تحقق شرط الجدوى.${\displaystyle Y\succeq 0}$. يدل${\displaystyle v_{deep}:=\sup\{\langle C,X\rangle :X{\text{ is }}\epsilon {\text{-deep}}\}}$. يُعيد الشكل الإهليلجي أحد المخرجات التالية:

• مصفوفة X* في L (أي، تحقق جميع قيود المساواة الخطية بدقة)، بحيث تكون مسافة فروبينيوس بين X* وبعض الحلول الممكنة على الأكثر ε (أي، تحقق تقريبًا قيد المتباينة).${\displaystyle X\succeq 0}$)، و${\displaystyle \langle C,X^{*}\rangle \geq v_{deep}-\epsilon }$(أي القيمة الموضوعية المثلى تقريبًا).
• شهادة تفيد بأن المشكلة ليس لها حلول عميقة من الدرجة ε (أي أن المشكلة غير قابلة للحل تقريبًا).

وقت التشغيل متعدد الحدود في الترميزات الثنائية للمدخلات وفي log(R/ ε )، في نموذج آلة تورينج .

لاحظ أنه، بشكل عام، قد يكون R أسيًا مضاعفًا بالنسبة إلى n. في هذه الحالة، يكون ضمان وقت التشغيل لطريقة القطع الناقص أسيًا بالنسبة إلى n . ولكن في معظم التطبيقات، لا يكون R كبيرًا جدًا. في هذه الحالات، تُعد طريقة القطع الناقص الطريقة الوحيدة المعروفة التي تضمن وقت تشغيل متعدد الحدود في نموذج آلة تورينج. ^{[ 1 ] : 23} ولكن عمليًا، لا يكون أداؤها جيدًا.

تعتمد معظم البرامج على طرق النقاط الداخلية (CSDP، MOSEK ، SeDuMi، SDPT3 ، DSDP، SDPA). تتميز هذه الطرق بقوتها وكفاءتها في حل مسائل البرمجة شبه المحددة الخطية العامة، إلا أنها محدودة بكونها طرقًا من الدرجة الثانية، وتتطلب تخزين وتحليل مصفوفة كبيرة (وغالبًا ما تكون كثيفة). نظريًا، تعتمد أحدث خوارزميات البرمجة شبه المحددة عالية الدقة ^{[ 7 ] [ 8 ] على هذا النهج.}

تتجنب طرق الرتبة الأولى لتحسين المخروط حساب وتخزين وتحليل مصفوفة هيسيان كبيرة، وتتميز بقدرتها على التعامل مع مسائل أكبر بكثير من طرق النقطة الداخلية، على حساب الدقة. تُطبَّق إحدى طرق الرتبة الأولى في برنامج Splitting Cone Solver (SCS). ^{[ 9 ]} وهناك طريقة أخرى من طرق الرتبة الأولى وهي طريقة الاتجاه المتناوب للمضاعفات (ADMM). ^{[ 10 ]} تتطلب هذه الطريقة في كل خطوة إسقاط المصفوفات شبه المحددة على المخروط.

يقوم برنامج ConicBundle بصياغة مسألة البرمجة شبه المحددة (SDP) كمسألة تحسين غير ملساء ، ويحلها باستخدام طريقة الحزمة الطيفية للتحسين غير الملساء. يُعد هذا النهج فعالاً للغاية لفئة خاصة من مسائل البرمجة شبه المحددة الخطية.

تتشابه الخوارزميات القائمة على طريقة لاغرانج المعززة (PENSDP) في سلوكها مع طرق النقطة الداخلية، ويمكن تخصيصها لبعض المسائل واسعة النطاق جدًا. وتستخدم خوارزميات أخرى معلومات منخفضة الرتبة وإعادة صياغة مسألة البرمجة شبه المحددة (SDP) كمسألة برمجة غير خطية (SDPLR، ManiSDP). ^{[ 11 ]}

تم اقتراح خوارزميات لحل مسائل البرمجة شبه المحددة (SDPs) تقريبًا. يهدف هذا النوع من الخوارزميات بشكل أساسي إلى تقليل التعقيد في التطبيقات التي تتطلب حلولًا تقريبية مع ضرورة تقليل التعقيد إلى أدنى حد. من أبرز الطرق المستخدمة في كشف البيانات في أنظمة MIMO اللاسلكية طريقة الاسترخاء شبه المحدد التقريبي المثلثي (TASER) ^{[ 12 ]} ، والتي تعتمد على عوامل تحليل Cholesky للمصفوفة شبه المحددة بدلًا من المصفوفة نفسها. تحسب هذه الطريقة حلولًا تقريبية لمسألة شبيهة بمسألة القطع الأقصى، وهي حلول غالبًا ما تكون قابلة للمقارنة مع الحلول الدقيقة، ولكن في 10-20 تكرارًا فقط للخوارزمية. وقد طور هازان ^{[ 13 ]} خوارزمية تقريبية لحل مسائل البرمجة شبه المحددة مع شرط إضافي يتمثل في أن يكون أثر مصفوفة المتغيرات مساويًا لـ 1.