Spelling suggestions: "subject:"semidefinite abbauoptimierung"" "subject:"semidefinite ablaufoptimierung""
1 |
Glättungsverfahren für semidefinite Programme / Smoothing-type Methods for Semidefinite ProgramsNagel, Christian January 2003 (has links) (PDF)
In dieser Arbeit werden Algorithmen zur Lösung von linearen semidefiniten Programmen beschrieben. Unter einer geeigneten Regularitätsvoraussetzung ist ein semidefinites Programm äquivalent zu seinen Optimalitätsbedingungen. Die Optimalitätsbedingungen bzw. die Zentralen-Pfad-Bedingungen überführen wir zunächst durch matrixwertige NCP-Funktionen in ein nichtlineares Gleichungssystem. Dieses nichtlineare und teilweise nicht differenzierbare Gleichungssystem lösen wir dann mit einem Newton-ähnlichen Verfahren. Durch die Umformulierung in ein nichtlineares Gleichungssystem muss während der Iteration nicht mehr explizit die positive (Semi-)Definitheit der beteiligten Matrizen beachtet werden. Weiter wird gezeigt, dass dieser Ansatz im Gegensatz zu Inneren-Punkte-Methoden sofort symmetrische Suchrichtungen erzeugt. Um globale Konvergenz zu erhalten, werden verschiedene Globalisierungsstrategien (Schrittweitenbestimmung, Trust-Region-Ansatz) untersucht. Für das betrachtete Prädiktor-Korrektor-Verfahren und das Trust-Region-Verfahren wird lokal superlineare Konvergenz unter strikter Komplementarität und Nichtdegeneriertheit gezeigt. Die theoretische Untersuchung eines nichtglatten Newton-Verfahrens liefert ein lokal quadratisches Konvergenzverhalten ohne strikte Komplementarität, wenn die Nichtdegeneriertheitsvoraussetzung geeignet modifiziert wird. / In this thesis we consider algorithms to compute a solution of linear semidefinite programs. Under a suitable regularity condition a semidefinite program is equivalent to its optimality conditions. These optimality conditions, or central-path-conditions, are reformulated as a nonlinear system of equations via matrix-valued NCP-functions. This nonlinear and partly nonsmooth system of equations is solved with a Newton-type method. Because of the reformulation as a nonlinear system of equations, we do not need the iterates to be positive (semi-)definite. Moreover, this reformulation automatically computes symmetric search directions, in contrast to interior point methods. To obtain global convergence, different globalizations (line search, trust-region) are considered. For the predictor-corrector method and the trust-region-method global and local superlinear convergence is shown under strikt complementarity and nondegeneracy. The theoretical investigation of a nonsmooth version of Newton's methods yields locally quadratic convergence without strict complementarity if the nondegeneracy conditon is modified in a suitable way.
|
2 |
Lineare Algebra und Erfüllbarkeitsalgorithmen für zufällige FormelnNeupert, Sascha. January 2005 (has links)
Chemnitz, Techn. Univ., Diplomarb., 2005.
|
3 |
Image partitioning based on semidefinite programmingKeuchel, Jens. Unknown Date (has links) (PDF)
University, Diss., 2004--Mannheim.
|
4 |
Convex Mathematical Programs for Relational Matching of Object ViewsSchellewald, Christian. January 2005 (has links)
Mannheim, Univ., Diss., 2004.
|
5 |
Image partitioning based on semidefinite programmingKeuchel, Jens. January 2004 (has links)
Mannheim, Univ., Diss., 2004.
|
6 |
Mixed integer bilevel programming problemsMefo Kue, Floriane 13 November 2017 (has links) (PDF)
This thesis presents the mixed integer bilevel programming problems where some optimality conditions and solution algorithms are derived. Bilevel programming problems are optimization problems which are partly constrained by another optimization problem.
The theoretical part of this dissertation is mainly based on the investigation of optimality conditions of mixed integer bilevel program. Taking into account both approaches (optimistic and pessimistic) which have been developed in the literature to deal with this type of problem, we derive some conditions for the existence of solutions. After that, we are able to discuss local optimality conditions using tools of variational analysis for each different approach. Moreover, bilevel optimization problems with semidefinite programming in the lower level are considered in order to formulate more optimality conditions for the mixed integer bilevel program. We end the thesis by developing some algorithms based on the theory presented
|
7 |
Lineare Algebra und Erfüllbarkeitsalgorithmen für zufällige FormelnNeupert, Sascha 13 August 2005 (has links) (PDF)
Es werden effiziente Algorithmen vorgestellt, die
auf algebraischen Methoden beruhen um die
Unerfüllbarkeit aussagenlogischer 4-SAT Formeln zu
zertifizieren. Die Algorithmen werden implementiert
und auf praktische Weise hinsichtlich der Laufzeit
mit Backtracking-Algorithmen verglichen.
|
8 |
Branch-and-Cut for a Semidefinite Relaxation of Large-scale Minimum Bisection ProblemsArmbruster, Michael 22 June 2007 (has links) (PDF)
This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.
|
9 |
Glättungsverfahren für semidefinite ProgrammeNagel, Christian. Unknown Date (has links) (PDF)
Universiẗat, Diss., 2004--Würzburg. / Erscheinungsjahr an der Haupttitelstelle: 2003.
|
10 |
Optimizing Extremal Eigenvalues of Weighted Graph Laplacians and Associated Graph RealizationsReiß, Susanna 09 August 2012 (has links) (PDF)
This thesis deals with optimizing extremal eigenvalues of weighted graph Laplacian matrices. In general, the Laplacian matrix of a (weighted) graph is of particular importance in spectral graph theory and combinatorial optimization (e.g., graph partition like max-cut and graph bipartition). Especially the pioneering work of M. Fiedler investigates extremal eigenvalues of weighted graph Laplacians and provides close connections to the node- and edge-connectivity of a graph. Motivated by Fiedler, Göring et al. were interested in further connections between structural properties of the graph and the eigenspace of the second smallest eigenvalue of weighted graph Laplacians using a semidefinite optimization approach.
By redistributing the edge weights of a graph, the following three optimization problems are studied in this thesis: maximizing the second smallest eigenvalue (based on the mentioned work of Göring et al.), minimizing the maximum eigenvalue and minimizing the difference of maximum and second smallest eigenvalue of the weighted Laplacian. In all three problems a semidefinite optimization formulation allows to interpret the corresponding semidefinite dual as a graph realization problem. That is, to each node of the graph a vector in the Euclidean space is assigned, fulfilling some constraints depending on the considered problem.
Optimal realizations are investigated and connections to the eigenspaces of corresponding optimized eigenvalues are established.
Furthermore, optimal realizations are closely linked to the separator structure of the graph. Depending on this structure, on the one hand folding properties of optimal realizations are characterized and on the other hand the existence of optimal realizations of bounded dimension is proven. The general bounds depend on the tree-width of the graph. In the case of minimizing the maximum eigenvalue, an important family of graphs are bipartite graphs, as an optimal one-dimensional realization may be constructed.
Taking the symmetry of the graph into account, a particular optimal edge weighting exists.
Considering the coupled problem, i.e., minimizing the difference of maximum and second smallest eigenvalue and the single problems, i.e., minimizing the maximum and maximizing the second smallest eigenvalue, connections between the feasible (optimal) sets are established.
|
Page generated in 0.052 seconds