Semidefinite programming (original) (raw)

About DBpedia

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.

Property Value
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)
dbo:wikiPageExternalLink http://www.optimization-online.org/DB_HTML/2002/12/585.html https://www.math.cmu.edu/~reha/sdpt3.html http://www-user.tu-chemnitz.de/~helmberg/semidef.html https://stanford.edu/~boyd/papers/pdf/semidef_prog.pdf http://www.cs.elte.hu/~lovasz/semidef.ps http://ocw.mit.edu/courses/sloan-school-of-management/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/lecture-notes/sdp094_digest.pdf
dbo:wikiPageID 4993539 (xsd:integer)
dbo:wikiPageLength 23474 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1121394789 (xsd:integer)
dbo:wikiPageWikiLink dbr:Scalar_(mathematics) dbc:Real_algebraic_geometry dbr:David_P._Williamson dbr:Cone_(linear_algebra) dbr:Convex_optimization dbr:Correlation dbr:Correlation_matrix dbr:Matrix_(mathematics) dbr:Maximum_cut dbc:P-complete_problems dbr:Eigenvalues_and_eigenvectors dbr:Graph_(discrete_mathematics) dbr:Conformal_bootstrap dbr:Conformal_field_theory dbr:Conic_optimization dbr:Objective_function dbr:László_Lovász dbr:MOSEK dbr:Cholesky_decomposition dbr:Combinatorial_optimization dbr:Trace_(linear_algebra) dbr:Weak_duality dbr:Linear_matrix_inequality dbr:Linear_programming dbr:Affine_space dbc:Convex_optimization dbr:Partition_of_a_set dbr:Gram_matrix dbr:Quadratic_programming dbr:Strong_duality dbc:Linear_programming dbr:Dot_product dbr:Augmented_Lagrangian_method dbr:Positive-definite_matrix dbr:Alternating_direction_method_of_multipliers dbr:Approximation_ratio dbr:Max_cut dbr:Inner_product_space dbr:Michel_Goemans dbr:Operations_research dbr:Optimization dbr:Slack_variable dbr:Unique_games_conjecture dbr:Slater's_condition dbr:Nonlinear_programming dbr:Polytope dbr:Self-adjoint dbr:Spectrahedron dbr:Dual_problem dbr:P_=_NP dbr:Interior_point_methods dbr:Nonsmooth_optimization
dbp:wikiPageUsesTemplate dbt:ISBN dbt:Reflist dbt:Mathematical_optimization_software dbt:Optimization_algorithms
dcterms:subject dbc:Real_algebraic_geometry dbc:P-complete_problems dbc:Convex_optimization dbc:Linear_programming
gold:hypernym dbr:Subfield
rdf:type yago:WikicatP-completeProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 dbo:Disease yago:State100024720
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)
rdfs:label Semidefinite Programmierung (de) Programación Semidefinida (es) Optimisation SDP (fr) Programmazione semidefinita (it) 半正定値計画問題 (ja) Semidefinite programming (en) Полуопределённое программирование (ru) 半正定规划 (zh)
owl:sameAs freebase:Semidefinite programming yago-res:Semidefinite programming wikidata:Semidefinite programming dbpedia-de:Semidefinite programming dbpedia-es:Semidefinite programming dbpedia-fa:Semidefinite programming dbpedia-fr:Semidefinite programming dbpedia-it:Semidefinite programming dbpedia-ja:Semidefinite programming dbpedia-ru:Semidefinite programming dbpedia-zh:Semidefinite programming https://global.dbpedia.org/id/293zK
prov:wasDerivedFrom wikipedia-en:Semidefinite_programming?oldid=1121394789&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Semidefinite_programming
is dbo:academicDiscipline of dbr:Yurii_Nesterov
is dbo:wikiPageRedirects of dbr:Algorithms_for_semidefinite_programming dbr:Semi-definite_programming dbr:Semidefinite_program dbr:Semidefinite_programs
is dbo:wikiPageWikiLink of dbr:Nl_(format) dbr:Quantum_money dbr:Approximation_algorithm dbr:JuMP dbr:Betweenness dbr:David_P._Williamson dbr:Definite_matrix dbr:List_of_numerical_analysis_topics dbr:Quantum_refereed_game dbr:Tsirelson's_bound dbr:Convex_optimization dbr:Analysis_of_Boolean_functions dbr:Mathematical_optimization dbr:Maximum_cut dbr:Geometric_rigidity dbr:Quantum_nonlocality dbr:Semidefinite_embedding dbr:Quadratically_constrained_quadratic_program dbr:Quantum_coin_flipping dbr:Quantum_optimization_algorithms dbr:Clique_problem dbr:Frankl–Rödl_graph dbr:Graph_coloring dbr:Conic_optimization dbr:Convex_cone dbr:Min-entropy dbr:Lovász_number dbr:MOSEK dbr:Computational_hardness_assumption dbr:Yurii_Nesterov dbr:Fulkerson_Prize dbr:Matrix_completion dbr:Mutilated_chessboard_problem dbr:Avner_Magen dbr:Gadget_(computer_science) dbr:Joint_spectral_radius dbr:K-means_clustering dbr:Karloff–Zwick_algorithm dbr:Large_margin_nearest_neighbor dbr:Linear_matrix_inequality dbr:Linear_programming dbr:AMPL dbr:Cut_(graph_theory) dbr:Euclidean_distance_matrix dbr:Diamond_norm dbr:Dimensionality_reduction dbr:Graph_flattenability dbr:Kazhdan's_property_(T) dbr:Kim-Chuan_Toh dbr:Second-order_cone_programming dbr:Quadratic_programming dbr:2-satisfiability dbr:Hyperparameter_optimization dbr:Arkadi_Nemirovski dbr:Chebyshev's_inequality dbr:Sum-of-squares_optimization dbr:Yinyu_Ye dbr:Point-set_registration dbr:Grothendieck_inequality dbr:Algorithms_for_semidefinite_programming dbr:Michel_Goemans dbr:Naum_Z._Shor dbr:Christine_Bachoc dbr:SDP dbr:Stochastic_block_model dbr:Scenario_optimization dbr:Unique_games_conjecture dbr:Extension_complexity dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Octeract_Engine dbr:Robert_J._Vanderbei dbr:Planted_clique dbr:SuanShu_numerical_library dbr:Flag_algebra dbr:Multiplicative_weight_update_method dbr:Sparse_PCA dbr:TOMLAB dbr:Outline_of_statistics dbr:Randomized_rounding dbr:Spectrahedron dbr:SOS-convexity dbr:Semi-definite_programming dbr:Semidefinite_program dbr:Semidefinite_programs
is foaf:primaryTopic of wikipedia-en:Semidefinite_programming