ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Tue, 27 Sep 2022 21:10:08 GMT2022-09-27T21:10:08Z5081- Tight bounds on expected order statisticshttps://scholarbank.nus.edu.sg/handle/10635/44205Title: Tight bounds on expected order statistics
Authors: Bertsimas, D.; Natarajan, K.; Teo, C.-P.
Abstract: In this article, we study the problem of finding tight bounds on the expected value of the kth-order statistic E [Xk:n] under first and second moment information on n real-valued random variables. Given means E[Xi] = μi and variances Var [Xi] = σi 2, we show that the tight upper bound on the expected value of the highest-order statistic E[Xn:n] can be computed with a bisection search algorithm. An extremal discrete distribution is identified that attains the bound, and two closed-form bounds are proposed. Under additional covariance information Cov[Xi, Xj] = Qij, we show that the tight upper bound on the expected value of the highest-order statistic can be computed with semidefinite optimization. We generalize these results to find bounds on the expected value of the kth-order statistic under mean and variance information. For k < n, this bound is shown to be tight under identical means and variances. All of our results are distribution-free with no explicit assumption of independence made. Particularly, using optimization methods, we develop tractable approaches to compute bounds on the expected value of order statistics. © 2006 Cambridge University Press.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442052006-01-01T00:00:00Z
- A semidefinite optimization approach to the steady-state analysis of queueing systemshttps://scholarbank.nus.edu.sg/handle/10635/102755Title: A semidefinite optimization approach to the steady-state analysis of queueing systems
Authors: Bertsimas, D.; Natarajan, K.
Abstract: Computing the steady-state distribution in Markov chains for general distributions and general state space is a computationally challenging problem. In this paper, we consider the steady-state stochastic model Wd = g(W, X)where the equality is in distribution. Given partial distributional information on the random variables X, we want to estimate information on the distribution of the steady-state vector W. Such models naturally occur in queueing systems, where the goal is to find bounds on moments of the waiting time under moment information on the service and interarrival times. In this paper, we propose an approach based on semidefinite optimization to find such bounds. We show that the classical Kingman's and Daley's bounds for the expected waiting time in a GI/GI/1 queue are special cases of the proposed approach. We also report computational results in the queueing context that indicate the method is promising. © Springer Science+Business Media, LLC 2007.
Tue, 01 May 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027552007-05-01T00:00:00Z
- Tractable robust expected utility and risk models for portfolio optimizationhttps://scholarbank.nus.edu.sg/handle/10635/44208Title: Tractable robust expected utility and risk models for portfolio optimization
Authors: Natarajan, K.; Sim, M.; Uichanco, J.
Abstract: Expected utility models in portfolio optimization are based on the assumption of complete knowledge of the distribution of random returns. In this paper, we relax this assumption to the knowledge of only the mean, covariance, and support information. No additional restrictions on the type of distribution such as normality is made. The investor's utility is modeled as a piecewise-linear concave function. We derive exact and approximate optimal trading strategies for a robust (maximin) expected utility model, where the investor maximizes his worst-case expected utility over a set of ambiguous distributions. The optimal portfolios are identified using a tractable conic programming approach. Extensions of the model to capture asymmetry using partitioned statistics information and box-type uncertainty in the mean and covariance matrix are provided. Using the optimized certainty equivalent framework, we provide connections of our results with robust or ambiguous convex risk measures, in which the investor minimizes his worst-case risk under distributional ambiguity. New closed-form results for the worst-case optimized certainty equivalent risk measures and optimal portfolios are provided for two- and three-piece utility functions. For more complicated utility functions, computational experiments indicate that such robust approaches can provide good trading strategies in financial markets. © 2010 Wiley Periodicals, Inc.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442082010-01-01T00:00:00Z
- Persistence in discrete optimization under data uncertaintyhttps://scholarbank.nus.edu.sg/handle/10635/44206Title: Persistence in discrete optimization under data uncertainty
Authors: Bertsimas, D.; Natarajan, K.; Teo, C.-P.
Abstract: An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the network and determine a smaller set of arcs that will most probably be a part of the optimal solution under different realizations of the arc lengths. Building on a characterization of moment cones for single variate problems, and its associated semidefinite constraint representation, we develop a limited marginal moment model to compute the persistency of a decision variable. Under this model, we show that finding the persistency is tractable for zero-one optimization problems with a polynomial sized representation of the convex hull of the feasible region. Through extensive experiments, we show that the persistency computed under the limited marginal moment model is often close to the simulated persistency value under various distributions that satisfy the prescribed marginal moments and are generated independently.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442062006-01-01T00:00:00Z
- A mean-variance bound for a three-piece linear functionhttps://scholarbank.nus.edu.sg/handle/10635/102677Title: A mean-variance bound for a three-piece linear function
Authors: Natarajan, K.; Linyi, Z.
Abstract: In this article, we derive a tight closed-form upper bound on the expected value of a three-piece linear convex function E[max.(0, X, mX - z)] given the mean μ and the variance σ2 of the random variable X. The bound is an extension of the well-known mean-variance bound for E[max(0, X)]. An application of the bound to price the strangle option in finance is provided. © 2007 Cambridge University Press.
Mon, 01 Oct 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026772007-10-01T00:00:00Z
- Constructing risk measures from uncertainty setshttps://scholarbank.nus.edu.sg/handle/10635/44207Title: Constructing risk measures from uncertainty sets
Authors: Natarajan, K.; Pachamanova, D.; Sim, M.
Abstract: We illustrate the correspondence between uncertainty sets in robust optimization and some popular risk measures in finance and show how robust optimization can be used to generalize the concepts of these risk measures. We also show that by using properly defined uncertainty sets in robust optimization models, one can construct coherent risk measures and address the issue of the computational tractability of the resulting formulations. Our results have implications for efficient portfolio optimization under different measures of risk. © 2009 INFORMS.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442072009-01-01T00:00:00Z
- Persistency model and its applications in choice modelinghttps://scholarbank.nus.edu.sg/handle/10635/103933Title: Persistency model and its applications in choice modeling
Authors: Natarajan, K.; Teo, C.-P.
Abstract: Given a discrete maximization problem with a linear objective function where the coefficients are chosen randomly from a distribution, we would like to evaluate the expected optimal value and the marginal distribution of the optimal solution. We call this the persistency problem for a discrete optimization problem under uncertain objective, and the marginal probability mass function of the optimal solution is named the persistence value. In general, this is a difficult problem to solve, even if the distribution of the objective coefficient is well specified. In this paper, we solve a subclass of this problem when the distribution is assumed to belong to the class of distributions defined by given marginal distributions, or given marginal moment conditions. Under this model, we show that the persistency problem maximizing the expected objective value over the set of distributions can be solved via a concave maximization model. The persistency model solved using this formulation can be used to obtain important qualitative insights to the behavior of stochastic discrete optimization problems. We demonstrate how the approach can be used to obtain insights to problems in discrete choice modeling. Using a set of survey data from a transport choice modeling study, we calibrate the random utility model with choice probabilities obtained from the persistency model. Numerical results suggest that our persistency model is capable of obtaining estimates that perform as well, if not better, than classical methods, such as logit and cross-nested logit models. We can also use the persistency model to obtain choice probability estimates for more complex choice problems. We illustrate this on a stochastic knapsack problem, which is essentially a discrete choice problem under budget constraint.
Sun, 01 Mar 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1039332009-03-01T00:00:00Z
- Incorporating asymmetric distributional information in robust value-at-risk optimizationhttps://scholarbank.nus.edu.sg/handle/10635/44184Title: Incorporating asymmetric distributional information in robust value-at-risk optimization
Authors: Natarajan, K.; Pachamanova, D.; Sim, M.
Abstract: Value-at-Risk (VaR) is one of the most widely accepted risk measures in the financial and insurance industries, yet efficient optimization of VaR remains a very difficult problem. We propose a computationally tractable approximation method for minimizing the VaR of a portfolio based on robust optimization techniques. The method results in the optimization of a modified VaR measure, Asymmetry-Robust VaR (ARVaR), that takes into consideration asymmetries in the distributions of returns and is coherent, which makes it desirable from a financial theory perspective. We show that ARVaR approximates the Conditional VaR of the portfolio as well. Numerical experiments with simulated and real market data indicate that the proposed approach results in lower realized portfolio VaR, better efficient frontier, and lower maximum realized portfolio loss than alternative approaches for quantile-based portfolio risk minimization. © 2008 INFORMS.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/441842008-01-01T00:00:00Z