Search

Plain vanilla K-means clustering has proven to be successful in practice, yet it suffers from outlier sensitivity and may produce highly unbalanced clusters. To mitigate both shortcomings, we formulate a joint outlier detection and clustering problem, which assigns a prescribed number of data points to an auxiliary outlier cluster and performs cardinality-constrained K-means clustering on the residual data set, treating the cluster cardinalities as a given input. We cast this problem as a mixed-integer linear program (MILP) that admits tractable semidefinite and linear programming relaxations. We propose deterministic rounding schemes that transform the relaxed solutions to feasible solutions for the MILP. We also prove that these solutions are optimal in the MILP if a cluster separation condition holds. [ABSTRACT FROM AUTHOR]

The growth-optimal portfolio is designed to have maximum expected log return over the next rebalancing period. Thus, it can be computed with relative ease by solving a static optimization problem. The growth-optimal portfolio has sparked fascination among finance professionals and researchers because it can be shown to outperform any other portfolio with probability 1 in the long run. In the short run, however, it is notoriously volatile. Moreover, its computation requires precise knowledge of the asset return distribution, which is not directly observable but must be inferred from sparse data. By using methods from distributionally robust optimization, we design fixed-mix strategies that offer similar performance guarantees as the growth-optimal portfolio but for a finite investment horizon and for a whole family of distributions that share the same first- and second-order moments. We demonstrate that the resulting robust growth-optimal portfolios can be computed efficiently by solving a tractable conic program whose size is independent of the length of the investment horizon. Simulated and empirical backtests show that the robust growth-optimal portfolios are competitive with the classical growth-optimal portfolio across most realistic investment horizons and for an overwhelming majority of contaminated return distributions. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

A sharp upper bound on the probability of a random vector falling outside a polytope, based solely on the first and second moments of its distribution, can be computed efficiently using semidefinite programming. However, this Chebyshev-type bound tends to be overly conservative since it is determined by a discrete worst-case distribution. In this paper we obtain a less pessimistic Gauss-type bound by imposing the additional requirement that the random vector's distribution must be unimodal. We prove that this generalized Gauss bound still admits an exact and tractable semidefinite representation. Moreover, we demonstrate that both the Chebyshev and Gauss bounds can be obtained within a unified framework using a generalized notion of unimodality. We also offer new perspectives on the computational solution of generalized moment problems, since we use concepts from Choquet theory instead of traditional duality arguments to derive semidefinite representations for worst-case probability bounds. [ABSTRACT FROM AUTHOR]

We develop tractable semidefinite programming based approximations for distributionally robust individual and joint chance constraints, assuming that only the first- and second-order moments as well as the support of the uncertain parameters are given. It is known that robust chance constraints can be conservatively approximated by Worst-Case Conditional Value-at-Risk (CVaR) constraints. We first prove that this approximation is exact for robust individual chance constraints with concave or (not necessarily concave) quadratic constraint functions, and we demonstrate that the Worst-Case CVaR can be computed efficiently for these classes of constraint functions. Next, we study the Worst-Case CVaR approximation for joint chance constraints. This approximation affords intuitive dual interpretations and is provably tighter than two popular benchmark approximations. The tightness depends on a set of scaling parameters, which can be tuned via a sequential convex optimization algorithm. We show that the approximation becomes essentially exact when the scaling parameters are chosen optimally and that the Worst-Case CVaR can be evaluated efficiently if the scaling parameters are kept constant. We evaluate our joint chance constraint approximation in the context of a dynamic water reservoir control problem and numerically demonstrate its superiority over the two benchmark approximations. [ABSTRACT FROM AUTHOR]

Markov decision processes (MDPs) are powerful tools for decision making in uncertain dynamic environments. However, the solutions of MDPs are of limited practical use because of their sensitivity to distributional model parameters, which are typically unknown and have to be estimated by the decision maker. To counter the detrimental effects of estimation errors, we consider robust MDPs that offer probabilistic guarantees in view of the unknown parameters. To this end, we assume that an observation history of the MDP is available. Based on this history, we derive a confidence region that contains the unknown parameters with a prespecified probability 1 - β. Afterward, we determine a policy that attains the highest worst-case performance over this confidence region. By construction, this policy achieves or exceeds its worst-case performance with a confidence of at least 1 - β. Our method involves the solution of tractable conic programs of moderate size. [ABSTRACT FROM AUTHOR]

Portfolio optimization problems involving value at risk (VaR) are often computationally intractable and require complete information about the return distribution of the portfolio constituents, which is rarely available in practice. These difficulties are compounded when the portfolio contains derivatives. We develop two tractable conservative approximations for the VaR of a derivative portfolio by evaluating the worst-case VaR over all return distributions of the derivative underliers with given first- and second-order moments. The derivative returns are modelled as convex piecewise linear or--by using a delta-gamma approximation--as (possibly nonconvex) quadratic functions of the returns of the derivative underliers. These models lead to new worst-case polyhedral VaR (WPVaR) and worst-case quadratic VaR (WQVaR) approximations, respectively. WPVaR serves as a VaR approximation for portfolios containing long positions in European options expiring at the end of the investment horizon, whereas WQVaR is suitable for portfolios containing long and/or short positions in European and/or exotic options expiring beyond the investment horizon. We prove that--unlike VaR that may discourage diversification--WPVaR and WQVaR are in fact coherent risk measures. We also reveal connections to robust portfolio optimization. [ABSTRACT FROM AUTHOR]