| dbo:abstract
|
- In der semidefiniten Programmierung (SDP, auch semidefinite Optimierung) werden Optimierungsprobleme untersucht, deren Variablen keine Vektoren, sondern symmetrische Matrizen sind. Als Nebenbedingung wird verlangt, dass diese Matrizen positiv (oder negativ) semidefinit sind, woraus sich der Name der Problemstellung ergibt. Anwendungen gibt es auf dem Gebiet der Approximationstheorie, der Kontrolltheorie, der kombinatorischen Optimierung, der optimalen Versuchsplanung und in der Technik. (de)
- Programación Semidefinida (SDP) es una subrama de la optimización convexa cuyo interés principal yace en la optimización de una función objetiva lineal (una función especificada por el usuario, que dicho usuario busca minimizar o maximizar)sobre la intersección del cono de matrices positivo semidefinidas con un espacio afín, i.e., un espectrahedro. La programación semidefinida es una rama relativamente nueva de optimización que está recibiendo creciente atención por varias razones. Muchos problemas prácticos en investigación de operaciones y optimización combinatoria pueden ser modelados o aproximados por programas semidefinidos. En teoría de control automático, los PSDs son utilizados en el contexto de desigualdades matriciales lineales. Los PSDs son de hecho un caso especial de programación cónica y pueden ser resueltos eficientemente por métodos de punto interior. Todos los programas lineales y los programas cuadráticos (convexos) pueden ser expresados como PSDs, y vía jerarquías de PSDs, las soluciones de problemas de optimización polinomial pueden ser aproximadas. La programación semidefinida ha sido utilizada en la optimización de sistemas complejos. En años recientes, algunos problemas de complejidad de consulta cuánticos han sido formulados en términos de programas semidefinidos. (es)
- Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron. Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems. In automatic control theory, SDPs are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming and can be efficiently solved by interior point methods.All linear programs and (convex) quadratic programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Semidefinite programming has been used in the optimization of complex systems. In recent years, some quantum query complexity problems have been formulated in terms of semidefinite programs. (en)
- En mathématiques et en informatique théorique, l'optimisation SDP ou semi-définie positive, est un type d'optimisation convexe, qui étend l'optimisation linéaire. Dans un problème d'optimisation SDP, l'inconnue est une matrice symétrique que l'on impose d'être semi-définie positive. Comme en optimisation linéaire, le critère à minimiser est linéaire et l'inconnue doit également satisfaire une contrainte affine. L'optimisation SDP se généralise par l'optimisation conique, qui s'intéresse aux problèmes de minimisation d'une fonction linéaire sur l'intersection d'un cône et d'un sous-espace affine. L'optimisation SDP s'est beaucoup développée à partir des années 1990, du fait de plusieurs découvertes. D'une part, beaucoup de problèmes pratiques ont pu être définis au moyen de ce formalisme (en recherche opérationnelle) ou ont trouvé une formalisation SDP approchée, mais précise (en optimisation combinatoire, en ). Par ailleurs, ces problèmes peuvent être résolus efficacement par divers algorithmes : points intérieurs (algorithmes polynomiaux), lagrangien augmenté, méthode des faisceaux (algorithme d'optimisation non différentiable), etc. (fr)
- 半正定値計画問題 (semidefinite programming) とは半正定値行列全体によって作られる凸錐体上での凸最適化問題 (convex optimization) の一つである． 半正定値計画問題は近年いくつかの理由で成長している最適化の一分野である．その理由として多くの実用例が考えられることがあげられるが，特にオペレーションズ・リサーチや組み合わせ最適化などの分野で広く研究が行われている．自動制御理論の分野では半正定値計画問題が線形不等式制約のもとで行われることが多い．半正定値計画問題は，凸錐体上の凸最適化問題の一種であり，内点法などにより効率よく解を与えることが可能であることも，応用が期待される一要因となっている．また半正定値計画問題の階層化により多項式最適化問題が近似的に解けるほか，複雑系の最適化にも応用が可能である． (ja)
- La Programmazione semidefinita (O SDP) è un sottocampo dell'ottimizzazione convessa che si occupa dell'ottimizzazione di una funzione obiettivo lineare (una funzione specificata dall'utente che l'utente vuole minimizzare o massimizzare) su una intersezione di un cono di matrici positive semidefinite con uno spazio affine, come uno . La programmazione semidefinita è relativamente un nuovo campo dell'ottimizzazione di cui sta accrescendo l'interesse in quanto molti problemi pratici di ricerca operativa e possono essere modellati o approssimati come problemi di programmazione semidefinita.Nella teoria del controllo automatico, la SDP è usata nel contesto di ineguaglianze delle matrici lineari poiché sono un caso speciale della programmazione conica e possono essere risolte efficientemente dai . Tutti i programmi lineari possono essere espressi come SDP, e attraverso gerarchie di SDP si possono approssimare le soluzioni ai problemi di ottimizzazione polinomiale.Negli ultimi anni alcuni problema di complessità quantistica sono stati formulati in termini di programmi semidefiniti. (it)
- Полуопределённое программирование (или SDP от англ. Semidefinite programming) — подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством. Полуопределённое программирование является относительно новой областью оптимизации, интерес к которой растёт по нескольким причинам. Много практических задач в областях исследования операций и комбинаторной оптимизации можно смоделировать или аппроксимировать как задачи полуопределённого программирования. В теории автоматического управления задачи SDP используются в контексте линейных матричных неравенств. Задачи SDP, фактически, являются частным случаем и могут быть эффективно решены методом внутренней точки.Все задачи линейного программирования могут быть выражены как задачи SDP, а с помощью иерархий задач SDP могут быть аппроксимированы решения задач полиномиальной оптимизации. Полуопределённое программирование используется при оптимизации сложных систем. В последние годы некоторые задачи сложности квантовых запросов были сформулированы в терминах полуопределённого программирования. (ru)
- 半正定规划（Semidefinite programming，SDP）是凸优化问题的一个分支，它具有线性目标函数（由用户指定的最大化或最小化函数），且其定义在半正定矩阵构成的与仿射空间的交集上，即。 在最佳化理論中，半正定規劃是一個相對較年輕的領域，並且基於各種原因，學界不斷的增加對它的興趣：許多作業研究和組合最佳化的問題都能建模成半正定規劃問題，或以半正定規劃的方式得到近似解；在自動控制理論中，半正定規劃用於處理线性矩阵不等式。此外，半正定規劃是的特例，因此實際上可以快速解掉。所有線性規劃問題都可以表示成半正定規劃，此外，多項式最佳化問題的解也可以透由半正定規劃逼近。 半正定規劃經常用於處理複雜系統的最佳化，而近年來，量子查詢複雜性理論的問題也經常被建模成半正定規劃。 (zh)
|
| rdfs:comment
|
- In der semidefiniten Programmierung (SDP, auch semidefinite Optimierung) werden Optimierungsprobleme untersucht, deren Variablen keine Vektoren, sondern symmetrische Matrizen sind. Als Nebenbedingung wird verlangt, dass diese Matrizen positiv (oder negativ) semidefinit sind, woraus sich der Name der Problemstellung ergibt. Anwendungen gibt es auf dem Gebiet der Approximationstheorie, der Kontrolltheorie, der kombinatorischen Optimierung, der optimalen Versuchsplanung und in der Technik. (de)
- 半正定値計画問題 (semidefinite programming) とは半正定値行列全体によって作られる凸錐体上での凸最適化問題 (convex optimization) の一つである． 半正定値計画問題は近年いくつかの理由で成長している最適化の一分野である．その理由として多くの実用例が考えられることがあげられるが，特にオペレーションズ・リサーチや組み合わせ最適化などの分野で広く研究が行われている．自動制御理論の分野では半正定値計画問題が線形不等式制約のもとで行われることが多い．半正定値計画問題は，凸錐体上の凸最適化問題の一種であり，内点法などにより効率よく解を与えることが可能であることも，応用が期待される一要因となっている．また半正定値計画問題の階層化により多項式最適化問題が近似的に解けるほか，複雑系の最適化にも応用が可能である． (ja)
- 半正定规划（Semidefinite programming，SDP）是凸优化问题的一个分支，它具有线性目标函数（由用户指定的最大化或最小化函数），且其定义在半正定矩阵构成的与仿射空间的交集上，即。 在最佳化理論中，半正定規劃是一個相對較年輕的領域，並且基於各種原因，學界不斷的增加對它的興趣：許多作業研究和組合最佳化的問題都能建模成半正定規劃問題，或以半正定規劃的方式得到近似解；在自動控制理論中，半正定規劃用於處理线性矩阵不等式。此外，半正定規劃是的特例，因此實際上可以快速解掉。所有線性規劃問題都可以表示成半正定規劃，此外，多項式最佳化問題的解也可以透由半正定規劃逼近。 半正定規劃經常用於處理複雜系統的最佳化，而近年來，量子查詢複雜性理論的問題也經常被建模成半正定規劃。 (zh)
- Programación Semidefinida (SDP) es una subrama de la optimización convexa cuyo interés principal yace en la optimización de una función objetiva lineal (una función especificada por el usuario, que dicho usuario busca minimizar o maximizar)sobre la intersección del cono de matrices positivo semidefinidas con un espacio afín, i.e., un espectrahedro. (es)
- En mathématiques et en informatique théorique, l'optimisation SDP ou semi-définie positive, est un type d'optimisation convexe, qui étend l'optimisation linéaire. Dans un problème d'optimisation SDP, l'inconnue est une matrice symétrique que l'on impose d'être semi-définie positive. Comme en optimisation linéaire, le critère à minimiser est linéaire et l'inconnue doit également satisfaire une contrainte affine. (fr)
- Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron. (en)
- La Programmazione semidefinita (O SDP) è un sottocampo dell'ottimizzazione convessa che si occupa dell'ottimizzazione di una funzione obiettivo lineare (una funzione specificata dall'utente che l'utente vuole minimizzare o massimizzare) su una intersezione di un cono di matrici positive semidefinite con uno spazio affine, come uno . (it)
- Полуопределённое программирование (или SDP от англ. Semidefinite programming) — подраздел выпуклого программирования, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством. (ru)
|