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.

Optimal investment decisions often rely on assumptions about the models and their associated parameter values. Therefore, it is essential to assess suitability of these assumptions and to understand sensitivity of outcomes when they are altered. More importantly, appropriate approaches should be developed to achieve a robust decision. In this thesis, we carry out a sensitivity analysis on parameter values as well as model speci cation of an important problem in portfolio management, namely the optimal portfolio execution problem. We then propose more robust solution techniques and models to achieve greater reliability on the performance of an optimal execution strategy. The optimal portfolio execution problem yields an execution strategy to liquidate large blocks of assets over a given execution horizon to minimize the mean of the execution cost and risk in execution. For large-volume trades, a major component of the execution cost comes from price impact. The optimal execution strategy then depends on the market price dynamics, the execution price model, the price impact model, as well as the choice of the risk measure. In this study, rst, sensitivity of the optimal execution strategy to estimation errors in the price impact parameters is analyzed, when a deterministic strategy is sought to minimize the mean and variance of the execution cost. An upper bound on the size of change in the solution is provided, which indicates the contributing factors to sensitivity of an optimal execution strategy. Our results show that the optimal execution strategy and the e cient frontier may be quite sensitive to perturbations in the price impact parameters. Motivated by our sensitivity results, a regularized robust optimization approach is devised when the price impact parameters belong to some uncertainty set. We rst illustrate that the classical robust optimization might be unstable to variation in the uncertainty set. To achieve greater stability, the proposed approach imposes a regularization constraint on the uncertainty set before being used in the minimax optimization formulation. Improvement in the stability of the robust solution is discussed and some implications of the regularization on the robust solution are studied. Sensitivity of the optimal execution strategy to market price dynamics is then investigated. We provide arguments that jump di usion models using compound poisson processes naturally model uncertain price impact of other large trades. Using stochastic dynamic programming, we derive analytical solutions for minimizing the expected execution cost under jump di usion models and compare them with the optimal execution strategies obtained from a di usion process. A jump di usion model for the market price dynamics suggests the use of Conditional Value-at-Risk (CVaR) as the risk measure. Using Monte Carlo simulations, a smoothing technique, and a parametric representation of a stochastic strategy, we investigate an approach to minimize the mean and CVaR of the execution cost. The devised approach can further handle constraints using a smoothed exact penalty function.

A workforce plan states the number of workers required at any point in time. Efficient workforce plans can help companies achieve their organizational goals while keeping costs low. In ever increasing globalized work market, companies need a competitive edge over their competitors. A competitive edge can be achieved by lowering costs. Labour costs can be one of the significant costs faced by the companies. Efficient workforce plans can provide companies with a competitive edge by finding low cost options to meet customer demand. This thesis studies the problem of determining the required number of workers when there are two categories of workers. Workers belonging to the first category are trained to work on one type of task (called Specialized Workers); whereas, workers in the second category are trained to work in all the tasks (called Flexible Workers). This thesis makes the following three main contributions. First, it addresses this problem when the demand is deterministic and stochastic. Two different models for deterministic demand cases have been proposed. To study the effects of uncertain demand, techniques of Robust Optimization and Robust Mathemat- ical Programming were used. The thesis also investigates methods to solve large instances of this problem; some of the instances we considered have more than 600,000 variables and constraints. As most of the variables are integer, and objective function is nonlinear, a commercial solver was not able to solve the problem in one day. Initially, we tried to solve the problem by using Lagrangian relaxation and Outer approximation techniques but these approaches were not successful. Although effective in solving small problems, these tools were not able to generate a bound within run time limit for the large data set. A number of heuristics were proposed using projection techniques. Finally this thesis develops a genetic algorithm to solve large instances of this prob- lem. For the tested population, the genetic algorithm delivered results within 2-3% of optimal solution.

In this study, we address the long-term project pricing problem for a company that operates in the defense industry. The pricing problem is a bid project pricing problem which includes various technical and financial uncertainties, such as estimations of workhour content of the project and exchange &amp / inflation rates. We propose a Robust Optimization (RO) approach that can deal with the uncertainties during the project lifecycle through the identification of several discrete scenarios. The bid project&rsquo / s performance measures, other than the monetary measures, for R&amp / D projects are identified and the problem is formulated as a multi-attribute utility project pricing problem. In our RO approach, the bid pricing problem is decomposed into two parts which are v solved sequentially: the Penalty-Model, and the RO model. In the Penalty-Model, penalty costs for the possible violations in the company&rsquo / s workforce level due to the bid project&rsquo / s workhour requirements are determined. Then the RO model searches for the optimum bid price by considering the penalty cost from the Penalty-Model, the bid project&rsquo / s performance measures, the probability of winning the bid for a given bid price and the deviations in the bid project&rsquo / s cost. Especially for the R&amp / D type projects, the model tends to place lower bid prices in the expected value solutions in order to win the bid. Thus, due to the possible deviations in the project cost, R&amp / D projects have a high probability of suffering from a financial loss in the expected value solutions. However, the robust solutions provide results which are more aware of the deviations in the bid project&rsquo / s cost and thus eliminate the financial risks by making a tradeoff between the bid project&rsquo / s benefits, probability of winning the bid and the financial loss risk. Results for the probability of winning in the robust solutions are observed to be lower than the expected value solutions, whereas expected value solutions have higher probabilities of suffering from a financial loss.

In this thesis, performance of relay-assisted Device-to-device (D2D) communication is investigated where D2D traffic is carried through relay nodes. I develop resource management schemes to maximize end-to-end rate as well as conversing rate requirements for cellular and D2D UEs under total power constraint. I also develop a low-complexity distributed solution using the concept of message passing. Considering the uncertainties in wireless links (e.g., when interference from other relay nodes and the link gains are not exactly known), I extend the formulation using robust resource allocation techniques. In addition, a distributed solution approach using stable matching is developed to allocate radio resources in an efficient and computationally inexpensive way under the bounded channel uncertainties. Numerical results show that, there is a distance threshold beyond which relay-assisted D2D communication significantly improves network performance at the cost of small increase in end-to-end delay when compared to conventional approach.

Stochastic programming is a mathematical technique for decision making under uncertainty using probabilistic statements in the problem objective and constraints. In practice, the distribution of the unknown quantities are often known only through observed or simulated data. This dissertation discusses several methods of using this data to formulate, solve, and evaluate the quality of solutions of stochastic programs. The central contribution of this dissertation is to investigate the use of techniques from simulation and statistics to enable data-driven models and methods for stochastic programming. We begin by extending the method of overlapping batches from simulation to assessing solution quality in stochastic programming. The Multiple Replications Procedure, where multiple stochastic programs are solved using independent batches of samples, has previously been used for assessing solution quality. The Overlapping Multiple Replications Procedure overlaps the batches, thus losing the independence between samples, but reducing the variance of the estimator without affecting its bias. We provide conditions under which the optimality gap estimators are consistent, the variance reduction benefits are obtained, and give a computational illustration of the small-sample behavior. Our second result explores the use of phi-divergences for distributionally robust optimization, also known as ambiguous stochastic programming. The phi-divergences provide a method of measuring distance between probability distributions, are widely used in statistical inference and information theory, and have recently been proposed to formulate data-driven stochastic programs. We provide a novel classification of phi-divergences for stochastic programming and give recommendations for their use. A value of data condition is derived and the asymptotic behavior of the phi-divergence constrained stochastic program is described. Then a decomposition-based solution method is proposed to solve problems computationally. The final portion of this dissertation applies the phi-divergence method to a problem of water allocation in a developing region of Tucson, AZ. In this application, we integrate several sources of uncertainty into a single model, including (1) future population growth in the region, (2) amount of water available from the Colorado River, and (3) the effects of climate variability on water demand. Estimates of the frequency and severity of future water shortages are given and we evaluate the effectiveness of several infrastructure options.

Observers are used in the monitoring and control of dynamical systems to deduce the values of unmeasured states. Designing an observer requires having an accurate model of the plant — if the model parameters are characterized imprecisely, the observer may not provide reliable estimates. An interval observer, which comprises an upper and lower observer, bounds the plant's states from above and below, given the range of values of the imprecisely characterized parameters, i.e., it defines an interval in which the plant's states must lie at any given instant. We propose a linear programming-based method of interval observer design for two cases: 1) only the initial conditions of the plant are uncertain; 2) the dynamical parameters are also uncertain. In the former, we optimize the transient performance of the interval observers, in the sense that the volume enclosed by the interval is minimized. In the latter, we optimize the steady state performance of the interval observers, in the sense that the norm of the width of the interval is minimized at steady state. Interval observers are typically designed to characterize the widest interval that bounds the states. This thesis proposes an interval observer design method that utilizes additional, but still-incomplete information, that enables the designer to identify tighter bounds on the uncertain parameters under certain operating conditions. The number of bounds that can be refined defines a class of systems. The definition of this class is independent of the specific parameters whose bounds are refined. Applying robust optimization techniques, under a cardinality constrained model of uncertainty, we design a single observer for an entire class of systems. These observers guarantee a minimum level of performance with respect to the aforementioned metrics, as we optimize the worst-case performance over a given class of systems. The robust formulation allows the designer to tune the level of uncertainty in the model. If many of the uncertain parameter bounds can be refined, the nominal performance of the observer can be improved, however, if few or none of the parameter bounds can be refined, the nominal performance of the observer can be designed to be more conservative.

Markov decision processes (MDPs) have proven to be a useful model for sequential decision- theoretic reasoning under uncertainty, yet they require the specification of a reward function that can require sophisticated human judgement to assess relevant tradeoffs. This dissertation casts the problem of specifying rewards as one of preference elicitation and aims to minimize the degree of precision with which a reward function must be specified while still allowing optimal or near-optimal policies to be produced. We demonstrate how robust policies can be computed for MDPs given only partial reward information using the minimax regret criterion. Minimax regret offers an intuitive bound on loss; however, it is computationally intractable in general. This work develops techniques for exploiting MDP structure to allow for offline precomputation that enables efficient online minimax regret computation. To complement this exact approach we develop several general approximations that offer both upper and lower bounds on minimax regret. We further show how approximations can be improved online during the elicitation procedure to balance accuracy and efficiency. To effectively reduce regret, we investigate a spectrum of elicitation approaches that range from the computationally-demanding optimal selection of complex queries about full MDP policies (which are informative, but, we believe, cognitively difficult) to the heuristic selection of simple queries that focus on a small set of reward parameters. Results are demonstrated on MDPs drawn from the domains of assistive technology and autonomic computing. Finally we demonstrate our framework on a realistic website optimization domain, per- forming elicitation on websites with tens of thousands of webpages. We show that minimax regret can be efficiently computed, and develop informative and cognitively reasonable queries that quickly lower minimax regret, producing policies that offer significant improvement in the design of the underlying websites.

Optimal investment decisions often rely on assumptions about the models and their associated parameter values. Therefore, it is essential to assess suitability of these assumptions and to understand sensitivity of outcomes when they are altered. More importantly, appropriate approaches should be developed to achieve a robust decision. In this thesis, we carry out a sensitivity analysis on parameter values as well as model speci cation of an important problem in portfolio management, namely the optimal portfolio execution problem. We then propose more robust solution techniques and models to achieve greater reliability on the performance of an optimal execution strategy. The optimal portfolio execution problem yields an execution strategy to liquidate large blocks of assets over a given execution horizon to minimize the mean of the execution cost and risk in execution. For large-volume trades, a major component of the execution cost comes from price impact. The optimal execution strategy then depends on the market price dynamics, the execution price model, the price impact model, as well as the choice of the risk measure. In this study, rst, sensitivity of the optimal execution strategy to estimation errors in the price impact parameters is analyzed, when a deterministic strategy is sought to minimize the mean and variance of the execution cost. An upper bound on the size of change in the solution is provided, which indicates the contributing factors to sensitivity of an optimal execution strategy. Our results show that the optimal execution strategy and the e cient frontier may be quite sensitive to perturbations in the price impact parameters. Motivated by our sensitivity results, a regularized robust optimization approach is devised when the price impact parameters belong to some uncertainty set. We rst illustrate that the classical robust optimization might be unstable to variation in the uncertainty set. To achieve greater stability, the proposed approach imposes a regularization constraint on the uncertainty set before being used in the minimax optimization formulation. Improvement in the stability of the robust solution is discussed and some implications of the regularization on the robust solution are studied. Sensitivity of the optimal execution strategy to market price dynamics is then investigated. We provide arguments that jump di usion models using compound poisson processes naturally model uncertain price impact of other large trades. Using stochastic dynamic programming, we derive analytical solutions for minimizing the expected execution cost under jump di usion models and compare them with the optimal execution strategies obtained from a di usion process. A jump di usion model for the market price dynamics suggests the use of Conditional Value-at-Risk (CVaR) as the risk measure. Using Monte Carlo simulations, a smoothing technique, and a parametric representation of a stochastic strategy, we investigate an approach to minimize the mean and CVaR of the execution cost. The devised approach can further handle constraints using a smoothed exact penalty function.

A workforce plan states the number of workers required at any point in time. Efficient workforce plans can help companies achieve their organizational goals while keeping costs low. In ever increasing globalized work market, companies need a competitive edge over their competitors. A competitive edge can be achieved by lowering costs. Labour costs can be one of the significant costs faced by the companies. Efficient workforce plans can provide companies with a competitive edge by finding low cost options to meet customer demand. This thesis studies the problem of determining the required number of workers when there are two categories of workers. Workers belonging to the first category are trained to work on one type of task (called Specialized Workers); whereas, workers in the second category are trained to work in all the tasks (called Flexible Workers). This thesis makes the following three main contributions. First, it addresses this problem when the demand is deterministic and stochastic. Two different models for deterministic demand cases have been proposed. To study the effects of uncertain demand, techniques of Robust Optimization and Robust Mathemat- ical Programming were used. The thesis also investigates methods to solve large instances of this problem; some of the instances we considered have more than 600,000 variables and constraints. As most of the variables are integer, and objective function is nonlinear, a commercial solver was not able to solve the problem in one day. Initially, we tried to solve the problem by using Lagrangian relaxation and Outer approximation techniques but these approaches were not successful. Although effective in solving small problems, these tools were not able to generate a bound within run time limit for the large data set. A number of heuristics were proposed using projection techniques. Finally this thesis develops a genetic algorithm to solve large instances of this prob- lem. For the tested population, the genetic algorithm delivered results within 2-3% of optimal solution.