The minimum k-partition (MkP) problem is a well-known 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 branch-and-cut 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 branch-and-cut 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 branch-and-cut 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.

We study numerical stability for interior-point 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 ill-conditioning 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^-8 when the machine precision on a 32-bit computer is approximately 10^-16. <br /><br /> We then propose a simple alternative approach for the normal equation based interior-point 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 well-conditioned, 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.

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 S-Procedure, 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.

The single-row 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 medium-sized 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.

In deregulated electricity markets, generating companies submit energy bids which are derived from a self-schedule. In this thesis, we propose an improved semidefinite programming-based model for the self-scheduling problem. The model provides the profit-maximizing generation quantities of a single generator over a multi-period horizon and accounts for uncertainty in prices using robust optimization. Within this robust framework, the price information is represented analytically as an ellipsoid. The risk-adversity of the decision maker is taken into account by a scaling parameter. Hence, the focus of the model is directed toward the trade-off between profit and risk. The bounds obtained by the proposed approach are shown to be significantly better than those obtained by a mean-variance approach from the literature. We then apply the proposed model within a branch-and-bound algorithm to improve the quality of the solutions. The resulting solutions are also compared with the mean-variance approach, which is formulated as a mixed-integer quadratic programming problem. The results indicate that the proposed approach produces solutions which are closer to integrality and have lower relative error than the mean-variance approach.

Moment Problems with Applications to Value-At-Risk 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 value-at-risk (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 CVaR-related 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 CVaR-like constraints approach adds a set of CVaR-like 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 CVaR-related approaches to some other popular portfolio optimization methods. Our numerical analysis provides empirical support for the superiority of the CVaR-like constraints approach in terms of portfolio efficiency.

It is well known that many of the optimization problems which arise in applications are <I>hard</I>, which usually means that they are NP-hard. 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 polynomial-time. 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 Maximum-Cut (Max-Cut) 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 Max-Cut problem. Our theoretical results hold for every instance of Max-Cut; in particular, we make no assumptions about the edge weights. The first relaxation provides a strengthening of the well-known Goemans-Williamson relaxation, and the second relaxation is a further tightening of the first. We prove that the tighter relaxation automatically enforces the well-known triangle inequalities, and in fact is stronger than the simple addition of these inequalities to the Goemans-Williamson 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 (Attractor-Repeller) model improves on the NLT (Non-linear 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 non-convexity 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.

The minimum k-partition (MkP) problem is a well-known 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 branch-and-cut 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 branch-and-cut 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 branch-and-cut 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.

We study numerical stability for interior-point 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 ill-conditioning 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^-8 when the machine precision on a 32-bit computer is approximately 10^-16. <br /><br /> We then propose a simple alternative approach for the normal equation based interior-point 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 well-conditioned, 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.

The single-row 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 medium-sized 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.