Spelling suggestions: "subject:"semidefinite erogramming"" "subject:"semidefinite grogramming""
31 
A BranchandCut Algorithm based on Semidefinite Programming for the Minimum kPartition ProblemGhaddar, Bissan January 2007 (has links)
The minimum kpartition (MkP) problem is a wellknown
optimization problem encountered in various applications most
notably in telecommunication and physics. Formulated in the early
1990s by Chopra and Rao, the MkP problem is the problem of
partitioning the set of vertices of a graph into k disjoint
subsets so as to minimize the total weight of the edges joining
vertices in different partitions.
In this thesis, we design and implement a branchandcut algorithm
based on semidefinite programming (SBC) for the MkP problem. We
describe and study the properties of two relaxations of the MkP
problem, the linear programming and the semidefinite programming
relaxations. We then derive a new strengthened relaxation based on
semidefinite programming. This new relaxation provides tighter
bounds compared to the other two discussed relaxations but suffers
in term of computational time. We further devise an iterative
clustering heuristic (ICH), a novel heuristic that finds feasible
solution to the MkP problem and we compare it to the hyperplane
rounding techniques of Goemans and Williamson and Frieze and
Jerrum for k=2 and for k=3 respectively. Our computational
results support the conclusion that ICH provides a better feasible
solution for the MkP. Furthermore, unlike the hyperplane
rounding, ICH remains very effective in the presence of negative
edge weights. Next we describe in detail the design and
implementation of a branchandcut algorithm based on semidefinite
programming (SBC) to find optimal solution for the MkP problem.
The ICH heuristic is used in our SBC algorithm to provide feasible
solutions at each node of the branchandcut tree. Finally, we
present computational results for the SBC algorithm on several
classes of test instances with k=3, 5, and 7. Complete graphs
with up to 60 vertices and sparse graphs with up to 100 vertices
arising from a physics application were considered.

32 
Numerical Stability in Linear Programming and Semidefinite ProgrammingWei, Hua January 2006 (has links)
We study numerical stability for interiorpoint methods applied to Linear Programming, LP, and Semidefinite Programming, SDP. We analyze the difficulties inherent in current methods and present robust algorithms. <br /><br /> We start with the error bound analysis of the search directions for the normal equation approach for LP. Our error analysis explains the surprising fact that the illconditioning is not a significant problem for the normal equation system. We also explain why most of the popular LP solvers have a default stop tolerance of only 10<sup>8</sup> when the machine precision on a 32bit computer is approximately 10<sup>16</sup>. <br /><br /> We then propose a simple alternative approach for the normal equation based interiorpoint method. This approach has better numerical stability than the normal equation based method. Although, our approach is not competitive in terms of CPU time for the NETLIB problem set, we do obtain higher accuracy. In addition, we obtain significantly smaller CPU times compared to the normal equation based direct solver, when we solve wellconditioned, huge, and sparse problems by using our iterative based linear solver. Additional techniques discussed are: crossover; purification step; and no backtracking. <br /><br /> Finally, we present an algorithm to construct SDP problem instances with prescribed strict complementarity gaps. We then introduce two <em>measures of strict complementarity gaps</em>. We empirically show that: (i) these measures can be evaluated accurately; (ii) the size of the strict complementarity gaps correlate well with the number of iteration for the SDPT3 solver, as well as with the local asymptotic convergence rate; and (iii) large strict complementarity gaps, coupled with the failure of Slater's condition, correlate well with loss of accuracy in the solutions. In addition, the numerical tests show that there is no correlation between the strict complementarity gaps and the geometrical measure used in [31], or with Renegar's condition number.

33 
On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic ProgrammingDing, Yichuan 17 May 2007 (has links)
Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound for a QCQP with many constraints. In this thesis, we first review some important results on QCQP, like the SProcedure, and the strength of Lagrangian Relaxation and the semidefinite relaxation. Then we focus on two special classes of QCQP, whose objective and constraint functions take the form trace(X^TQX + 2C^T X) + β, and trace(X^TQX + XPX^T + 2C^T X)+ β respectively, where X is an n by r real matrix. For each class of problems, we proposed different semidefinite relaxation formulations and compared their strength. The theoretical results obtained in this thesis have found interesting applications, e.g., solving the Quadratic Assignment Problem.

34 
CuttingPlane Separation Strategies for Semidefinite Programming Models to Solve SingleRow Facility Layout ProblemsYen, Ginger January 2008 (has links)
The singlerow facility layout problem (SRFLP) is concerned with finding the optimal linear placement of n departments with different lengths in a straight line. It is typically achieved by minimizing the cost associated with the interactions between the departments. The semidefinite programming (SDP) relaxation model that incorporates cutting planes proposed recently by Anjos, Kennings, and Vannelli (AKV) was considered a breakthrough in the field. This thesis presents a new SDP model AKV' and compares the two relaxations. The AKV' is largely based on the previous model, but it reduces the number of linear constraints from O(n³) to O(n²). Therefore, it reduces the computing time at the expense of a slightly weaker lower bound. However, AKV' is observed to pay off as the instance size increases. By examining the gap for both the AKV and AKV' relaxations, we notice that both relaxations generate very small gaps at the root node, which demonstrates the effectiveness of the relaxations.
Six different strategies are presented to separate the cutting planes for the mediumsized SRFLP. In combination with the two SDP relaxations, we compare the six strategies using three instances of different characteristics. An overall best strategy is deduced from the computational results, but the best choice of relaxations and the best number of cuts added at each iteration changes depending on the characteristics of the instances. Two new cutting plane strategies are proposed for large instances. This allows the solution to optimality of new instances with 36 departments, which is higher than previously published results in literature. We also briefly point out how the computing time can vary greatly between different sets of data of the same size due to the characteristics of the department lengths.

35 
A Robust Optimization Approach to the Selfscheduling Problem Using Semidefinite ProgrammingLandry, Jason Conrad January 2009 (has links)
In deregulated electricity markets, generating companies submit energy bids which are derived from a selfschedule. In this thesis, we propose an improved semidefinite programmingbased model for the selfscheduling problem. The model provides the profitmaximizing generation quantities of a single generator over a multiperiod horizon and accounts for uncertainty in prices using robust optimization. Within this robust framework, the price information is represented analytically as an ellipsoid. The riskadversity of the decision maker is taken into account by a scaling parameter. Hence, the focus of the model is directed toward the tradeoff between profit and risk. The bounds obtained by the proposed approach are shown to be significantly better than those obtained by a meanvariance approach from the literature. We then apply the proposed model within a branchandbound algorithm to improve the quality of the solutions. The resulting solutions are also compared with the meanvariance approach, which is formulated as a mixedinteger quadratic programming problem. The results indicate that the proposed approach produces solutions which are closer to integrality and have lower relative error than the meanvariance approach.

36 
Moment Problems with Applications to ValueAtRisk and Portfolio ManagementTian, Ruilin 07 May 2008 (has links)
Moment Problems with Applications to ValueAtRisk and Portfolio Management By Ruilin Tian May 2008 Committee Chair: Dr. Samuel H. Cox Major Department: Risk Management and Insurance My dissertation provides new applications of moment theory and optimization to financial and insurance risk management. In the investment and managerial areas, one often needs to determine some measure of risk, especially the risk of extreme events. However, complete information of the underlying outcomes is usually unavailable; instead one has access to partial information such as the mean, variance, mode, or range. In Chapters 2 and 3, we find the semiparametric upper and lower bounds for the valueatrisk (VaR) with incomplete information, that is, moments of the underlying distribution. When a single variable is concerned, bounds on VaR are computed to obtain a 100% confidence interval. When the sample financial data have a global maximum, we show that unimodal assumption tightens the optimal bounds. Next we further analyze a function of two correlated random variables. Specifically, we find bounds on the probability of two joint extreme events. When three or more variables are involved, the multivariate problem can sometimes be converted to a single variable problem. In all cases, we use the physical measure rather than the commonly used equivalent pricing probability measure. In addition to solving these problems using the traditional approach based on the geometry of a moment problem, a more efficient method is proposed to solve a general class of moment bounds via semidefinite programming. In the last part of the thesis, we apply optimization techniques to improve financial portfolio risk management. Instead of considering VaR, we work with a coherent risk measure, the conditional VaR (CVaR). As an extension of Krokhmal et al. (2002), we impose CVaRrelated functions to the portfolio selection problem. The CVaR approach sets a βlevel CVaR as the objective function and maximizes the worst case on the tail of the distribution. The CVaRlike constraints approach adds a set of CVaRlike constraints to the traditional Markowitz problem, reshaping the portfolio distribution. Both methods greatly increase the skewness of portfolios, although the CVaR approach may lose control of the variance. This capability of increasing skewness is very attractive to the investors who may prefer higher probability of obtaining higher returns. We compare the CVaRrelated approaches to some other popular portfolio optimization methods. Our numerical analysis provides empirical support for the superiority of the CVaRlike constraints approach in terms of portfolio efficiency.

37 
New Convex Relaxations for the Maximum Cut and VLSI Layout ProblemsFerreira Fialho dos Anjos, Miguel Nuno January 2001 (has links)
It is well known that many of the optimization problems which arise in applications are <I>hard</I>, which usually means that they are NPhard. Hence much research has been devoted to finding <I>good</I> relaxations for these hard problems. Usually a <I>good</I> relaxation is one which can be solved (either exactly or within a prescribed numerical tolerance) in polynomialtime. Nesterov and Nemirovskii showed that by this criterion, many convex optimization problems are good relaxations. This thesis presents new convex relaxations for two such hard problems, namely the MaximumCut (MaxCut) problem and the VLSI (Very Large Scale Integration of electronic circuits) layout problem. We derive and study the properties of two new strengthened semidefinite programming relaxations for the MaxCut problem. Our theoretical results hold for every instance of MaxCut; in particular, we make no assumptions about the edge weights. The first relaxation provides a strengthening of the wellknown GoemansWilliamson relaxation, and the second relaxation is a further tightening of the first. We prove that the tighter relaxation automatically enforces the wellknown triangle inequalities, and in fact is stronger than the simple addition of these inequalities to the GoemansWilliamson relaxation. We further prove that the tighter relaxation fully characterizes some low dimensional faces of the cut polytope via the rank of its feasible matrices. We also address some practical issues arising in the solution of these relaxations and present numerical results showing the remarkably good bounds computed by the tighter relaxation. For the VLSI layout problem, we derive a new relaxation by extending the <I>target distance</I> concept recently introduced by Etawil and Vannelli. The resulting AR (AttractorRepeller) model improves on the NLT (Nonlinear optimization Layout Technique) method of van Camp et al. by efficiently finding a good initial point for the NLT solver. Because the AR model is not a convex optimization problem, we isolate the source of the nonconvexity and thereby derive a convex version of the model. This derivation leads to the definition of certain generalized target distances with an interesting practical interpretation. Finally, we present numerical results that demonstrate the potential of the AR model.

38 
A BranchandCut Algorithm based on Semidefinite Programming for the Minimum kPartition ProblemGhaddar, Bissan January 2007 (has links)
The minimum kpartition (MkP) problem is a wellknown
optimization problem encountered in various applications most
notably in telecommunication and physics. Formulated in the early
1990s by Chopra and Rao, the MkP problem is the problem of
partitioning the set of vertices of a graph into k disjoint
subsets so as to minimize the total weight of the edges joining
vertices in different partitions.
In this thesis, we design and implement a branchandcut algorithm
based on semidefinite programming (SBC) for the MkP problem. We
describe and study the properties of two relaxations of the MkP
problem, the linear programming and the semidefinite programming
relaxations. We then derive a new strengthened relaxation based on
semidefinite programming. This new relaxation provides tighter
bounds compared to the other two discussed relaxations but suffers
in term of computational time. We further devise an iterative
clustering heuristic (ICH), a novel heuristic that finds feasible
solution to the MkP problem and we compare it to the hyperplane
rounding techniques of Goemans and Williamson and Frieze and
Jerrum for k=2 and for k=3 respectively. Our computational
results support the conclusion that ICH provides a better feasible
solution for the MkP. Furthermore, unlike the hyperplane
rounding, ICH remains very effective in the presence of negative
edge weights. Next we describe in detail the design and
implementation of a branchandcut algorithm based on semidefinite
programming (SBC) to find optimal solution for the MkP problem.
The ICH heuristic is used in our SBC algorithm to provide feasible
solutions at each node of the branchandcut tree. Finally, we
present computational results for the SBC algorithm on several
classes of test instances with k=3, 5, and 7. Complete graphs
with up to 60 vertices and sparse graphs with up to 100 vertices
arising from a physics application were considered.

39 
Numerical Stability in Linear Programming and Semidefinite ProgrammingWei, Hua January 2006 (has links)
We study numerical stability for interiorpoint methods applied to Linear Programming, LP, and Semidefinite Programming, SDP. We analyze the difficulties inherent in current methods and present robust algorithms. <br /><br /> We start with the error bound analysis of the search directions for the normal equation approach for LP. Our error analysis explains the surprising fact that the illconditioning is not a significant problem for the normal equation system. We also explain why most of the popular LP solvers have a default stop tolerance of only 10<sup>8</sup> when the machine precision on a 32bit computer is approximately 10<sup>16</sup>. <br /><br /> We then propose a simple alternative approach for the normal equation based interiorpoint method. This approach has better numerical stability than the normal equation based method. Although, our approach is not competitive in terms of CPU time for the NETLIB problem set, we do obtain higher accuracy. In addition, we obtain significantly smaller CPU times compared to the normal equation based direct solver, when we solve wellconditioned, huge, and sparse problems by using our iterative based linear solver. Additional techniques discussed are: crossover; purification step; and no backtracking. <br /><br /> Finally, we present an algorithm to construct SDP problem instances with prescribed strict complementarity gaps. We then introduce two <em>measures of strict complementarity gaps</em>. We empirically show that: (i) these measures can be evaluated accurately; (ii) the size of the strict complementarity gaps correlate well with the number of iteration for the SDPT3 solver, as well as with the local asymptotic convergence rate; and (iii) large strict complementarity gaps, coupled with the failure of Slater's condition, correlate well with loss of accuracy in the solutions. In addition, the numerical tests show that there is no correlation between the strict complementarity gaps and the geometrical measure used in [31], or with Renegar's condition number.

40 
CuttingPlane Separation Strategies for Semidefinite Programming Models to Solve SingleRow Facility Layout ProblemsYen, Ginger January 2008 (has links)
The singlerow facility layout problem (SRFLP) is concerned with finding the optimal linear placement of n departments with different lengths in a straight line. It is typically achieved by minimizing the cost associated with the interactions between the departments. The semidefinite programming (SDP) relaxation model that incorporates cutting planes proposed recently by Anjos, Kennings, and Vannelli (AKV) was considered a breakthrough in the field. This thesis presents a new SDP model AKV' and compares the two relaxations. The AKV' is largely based on the previous model, but it reduces the number of linear constraints from O(n³) to O(n²). Therefore, it reduces the computing time at the expense of a slightly weaker lower bound. However, AKV' is observed to pay off as the instance size increases. By examining the gap for both the AKV and AKV' relaxations, we notice that both relaxations generate very small gaps at the root node, which demonstrates the effectiveness of the relaxations.
Six different strategies are presented to separate the cutting planes for the mediumsized SRFLP. In combination with the two SDP relaxations, we compare the six strategies using three instances of different characteristics. An overall best strategy is deduced from the computational results, but the best choice of relaxations and the best number of cuts added at each iteration changes depending on the characteristics of the instances. Two new cutting plane strategies are proposed for large instances. This allows the solution to optimality of new instances with 36 departments, which is higher than previously published results in literature. We also briefly point out how the computing time can vary greatly between different sets of data of the same size due to the characteristics of the department lengths.

Page generated in 0.0831 seconds