A note on issues of over-conservatism in robust optimization with cost uncertainty

We identify and discuss issues of hidden over-conservatism in robust linear optimization, when the uncertainty set is polyhedral with a budget of uncertainty constraint. The decision-maker selects the budget of uncertainty to reflect his degree of risk aversion, i.e. the maximum number of uncertain parameters that can take their worst-case value. In the first setting, the cost coefficients of the linear programming problem are uncertain, as is the case in portfolio management with random stock returns. We provide an example where, for moderate values of the budget, the optimal solution becomes independent of the nominal values of the parameters, i.e. is completely disconnected from its nominal counterpart, and discuss why this happens. The second setting focusses on linear optimization with uncertain upper bounds on the decision variables, which has applications in revenue management with uncertain demand and can be rewritten as a piecewise linear problem with cost uncertainty. We show in an example that it is possible to have more demand parameters equal their worst-case value than what is allowed by the budget of uncertainty, although the robust formulation is correct. We explain this apparent paradox.     

Robust Duality for Fractional Programming Problems with Constraint-Wise Data Uncertainty

In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex–concave fractional program and the optimistic counterpart of its conventional Wolfe dual program with uncertain parameters. For linear fractional programming problems with constraint-wise interval uncertainty, we show that the dual of the robust counterpart is the optimistic counterpart in the sense that they are equivalent. Our results show that a worst-case solution of an uncertain fractional program (i.e., a solution of its robust counterpart) can be obtained by solving a single deterministic dual program. In the case of a linear fractional programming problem with interval uncertainty, such solutions can be found by solving a simple linear program.     

The projected newton method for solving inverse eigenvalue problems - the case of multiple eigenvaues

This paper deals with the optimal solution of ill-posed linear problems, i.e..linear problems for which the solution operator is unbounded. We consider worst-case ar,and averagecase settings. Our main result is that algorithms having finite error (for a given setting) exist if and only if the solution operator is bounded (in that setting). In the worst-case setting, this means that there is no algorithm for solving ill-posed problems having finite error. In the average-case setting, this means that algorithms having finite error exist if and only lf the solution operator is bounded on the average. If the solution operator is bounded on the average, we find average-case optimal information of cardinality n and optimal algorithms using this information, and show that the average error of these algorithms tends to zero as n→∞. These results are then used to determine the [euro]-complexity, i.e., the minimal costof finding an [euro]-accurate approximation. In the worst-case setting, the [euro]comp1exity of an illposed problem is infinite for all [euro]>0; that is, we cannot find an approximation having finite error and finite cost. In the average-case setting, the [euro]-complexity of an ill-posed problem is infinite for all [euro]>0 iff the solution operator is not bounded on the average, moreover, if the the solutionoperator is bounded on the average, then the [euro]-complexity is finite for all [euro]>0.     

Uncertain convex programs: randomized solutions and confidence levels

Many engineering problems can be cast as optimization problems subject to convex constraints that are parameterized by an uncertainty or instance parameter. Two main approaches are generally available to tackle constrained optimization problems in presence of uncertainty: robust optimization and chance-constrained optimization. Robust optimization is a deterministic paradigm where one seeks a solution which simultaneously satisfies all possible constraint instances. In chance-constrained optimization a probability distribution is instead assumed on the uncertain parameters, and the constraints are enforced up to a pre-specified level of probability. Unfortunately however, both approaches lead to computationally intractable problem formulations.In this paper, we consider an alternative randomized or scenario approach for dealing with uncertainty in optimization, based on constraint sampling. In particular, we study the constrained optimization problem resulting by taking into account only a finite set of N constraints, chosen at random among the possible constraint instances of the uncertain problem. We show that the resulting randomized solution fails to satisfy only a small portion of the original constraints, provided that a sufficient number of samples is drawn. Our key result is to provide an efficient and explicit bound on the measure (probability or volume) of the original constraints that are possibly violated by the randomized solution. This volume rapidly decreases to zero as N is increased.This work is supported in part by the European Commission under the project HYBRIDGE IST-2001-32460, and by MIUR under the project New methods for Identification and Adaptive Control for Industrial Systems, and the FIRB project Learning, randomization and guaranteed predictive inference for complex uncertain systems.Acknowledgement We wish to thank Professor Arkadi Nemirovski for his encouragement in pursuing this line of research. We also acknowledge the many valuable comments from anonymous reviewers that helped improve this paper.     

An approximation technique for robust nonlinear optimization

Nonlinear equality and inequality constrained optimization problems with uncertain parameters can be addressed by a robust worst-case formulation that is, however, difficult to treat computationally. In this paper we propose and investigate an approximate robust formulation that employs a linearization of the uncertainty set. In case of any norm bounded parameter uncertainty, this formulation leads to penalty terms employing the respective dual norm of first order derivatives of the constraints. The main advance of the paper is to present two sparsity preserving ways for efficient computation of these derivatives in the case of large scale problems, one similar to the forward mode, the other similar to the reverse mode of automatic differentiation. We show how to generalize the techniques to optimal control problems, and discuss how even infinite dimensional uncertainties can be treated efficiently. Finally, we present optimization results for an example from process engineering, a batch distillation.     

Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations

We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of the worst-case distribution within this Wasserstein ball. The state-of-the-art methods for solving the resulting distributionally robust optimization problems rely on global optimization techniques, which quickly become computationally excruciating. In this paper we demonstrate that, under mild assumptions, the distributionally robust optimization problems over Wasserstein balls can in fact be reformulated as finite convex programs—in many interesting cases even as tractable linear programs. Leveraging recent measure concentration results, we also show that their solutions enjoy powerful finite-sample performance guarantees. Our theoretical results are exemplified in mean-risk portfolio optimization as well as uncertainty quantification.

     

Short sales in Log-robust portfolio management

This paper extends the Log-robust portfolio management approach to the case with short sales, i.e., the case where the manager can sell shares he does not yet own. We model the continuously compounded rates of return, which have been established in the literature as the true drivers of uncertainty, as uncertain parameters belonging to polyhedral uncertainty sets, and maximize the worst-case portfolio wealth over that set in a one-period setting. The degree of the manager’s aversion to ambiguity is incorporated through a single, intuitive parameter, which determines the size of the uncertainty set. The presence of short-selling requires the development of problem-specific techniques, because the optimization problem is not convex. In the case where assets are independent, we show that the robust optimization problem can be solved exactly as a series of linear programming problems; as a result, the approach remains tractable for large numbers of assets. We also provide insights into the structure of the optimal solution. In the case of correlated assets, we develop and test a heuristic where correlation is maintained only between assets invested in. In computational experiments, the proposed approach exhibits superior performance to that of the traditional robust approach.     

Robust discrete optimization and network flows

We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15     

A robust optimization approach for multicast network coding under uncertain link costs

Network coding is a technique that can be used to improve the performance of communication networks by performing mathematical operations at intermediate nodes. An important problem in coding theory is that of finding an optimal coding subgraph for delivering network data from a source node throughout intermediate nodes to a set of destination nodes with the minimum transmission cost. However, in many real applications, it can be difficult to determine exact values or specific probability distributions of link costs. Establishing minimum-cost multicast connections based on erroneous link costs might exhibit poor performance when implemented. This paper considers the problem of minimum-cost multicast using network coding under uncertain link costs. We propose a robust optimization approach to obtain solutions that protect the system against the worst-case value of the uncertainty in a prespecified set. The simulation results show that a robust solution provides significant improvement in worst-case performance while incurring a small loss in optimality for specific instances of the uncertainty.     

On the approximability of adjustable robust convex optimization under uncertainty

In this paper, we consider adjustable robust versions of convex optimization problems with uncertain constraints and objectives and show that under fairly general assumptions, a static robust solution provides a good approximation for these adjustable robust problems. An adjustable robust optimization problem is usually intractable since it requires to compute a solution for all possible realizations of uncertain parameters, while an optimal static solution can be computed efficiently in most cases if the corresponding deterministic problem is tractable. The performance of the optimal static robust solution is related to a fundamental geometric property, namely, the symmetry of the uncertainty set. Our work allows for the constraint and objective function coefficients to be uncertain and for the constraints and objective functions to be convex, thereby providing significant extensions of the results in Bertsimas and Goyal (Math Oper Res 35:284–305, 2010) and Bertsimas et al. (Math Oper Res 36: 24–54, 2011b) where only linear objective and linear constraints were considered. The models in this paper encompass a wide variety of problems in revenue management, resource allocation under uncertainty, scheduling problems with uncertain processing times, semidefinite optimization among many others. To the best of our knowledge, these are the first approximation bounds for adjustable robust convex optimization problems in such generality.     

Robust nonlinear optimization with conic representable uncertainty set

The robust optimization methodology is known as a popular method dealing with optimization problems with uncertain data and hard constraints. This methodology has been applied so far to various convex conic optimization problems where only their inequality constraints are subject to uncertainty. In this paper, the robust optimization methodology is applied to the general nonlinear programming (NLP) problem involving both uncertain inequality and equality constraints. The uncertainty set is defined by conic representable sets, the proposed uncertainty set is general enough to include many uncertainty sets, which have been used in literature, as special cases. The robust counterpart (RC) of the general NLP problem is approximated under this uncertainty set. It is shown that the resulting approximate RC of the general NLP problem is valid in a small neighborhood of the nominal value. Furthermore a rather general class of programming problems is posed that the robust counterparts of its problems can be derived exactly under the proposed uncertainty set. Our results show the applicability of robust optimization to a wider area of real applications and theoretical problems with more general uncertainty sets than those considered so far. The resulting robust counterparts which are traditional optimization problems make it possible to use existing algorithms of mathematical optimization to solve more complicated and general robust optimization problems.     

Worst-case robust Omega ratio

The Omega ratio is a recent performance measure proposed to overcome the known shortcomings of the Sharpe ratio. Until recently, the Omega ratio was thought to be computationally intractable, and research was focused on heuristic optimization procedures. We have shown elsewhere that the Omega ratio optimization is equivalent to a linear program and hence can be solved exactly in polynomial time. This permits the investigation of more complex and realistic variants of the problem. The standard formulation of the Omega ratio requires perfect information for the probability distribution of the asset returns. In this paper, we investigate the problem arising from the probability distribution of the asset returns being only partially known. We introduce the robust variant of the conventional Omega ratio that hedges against uncertainty in the probability distribution. We examine the worst-case Omega ratio optimization problem under three types of uncertainty – mixture distribution, box and ellipsoidal uncertainty – and show that the problem remains tractable.     

A risk-based modeling approach for radiation therapy treatment planning under tumor shrinkage uncertainty

Robust optimization approaches have been widely used to address uncertainties in radiation therapy treatment planning problems. Because of the unknown probability distribution of uncertainties, robust bounds may not be correctly chosen, and a risk of undesirable effects from worst-case realizations may exist. In this study, we developed a risk-based robust approach, embedded within the conditional value-at-risk representation of the dose-volume constraint, to deal with tumor shrinkage uncertainty during radiation therapy. The objective of our proposed model is to reduce dose variability in the worst-case scenarios as well as the total delivered dose to healthy tissues and target dose deviations from the prescribed dose, especially, in underdosed scenarios. We also took advantage of adaptive radiation therapy in our treatment planning approach. This fractionation technique considers the response of the tumor to treatment up to a particular point in time and reoptimizes the treatment plan using an estimate of tumor shrinkage. The benefits of our model were tested in a clinical lung cancer case. Four plans were generated and compared: static, nominal-adaptive, robust-adaptive, and conventional robust (worst-case) optimization. Our results showed that the robust-adaptive model, which is a risk-based model, achieved less dose variability and more control on the worst-case scenarios while delivering the prescribed dose to the tumor target and sparing organs at risk. This model also outperformed other models in terms of tumor dose homogeneity and plan robustness.     

Portfolio selection under distributional uncertainty: A relative robust CVaR approach

Robust optimization, one of the most popular topics in the field of optimization and control since the late 1990s, deals with an optimization problem involving uncertain parameters. In this paper, we consider the relative robust conditional value-at-risk portfolio selection problem where the underlying probability distribution of portfolio return is only known to belong to a certain set. Our approach not only takes into account the worst-case scenarios of the uncertain distribution, but also pays attention to the best possible decision with respect to each realization of the distribution. We also illustrate how to construct a robust portfolio with multiple experts (priors) by solving a sequence of linear programs or a second-order cone program.     

A new distributionally robust p-hub median problem with uncertain carbon emissions and its tractable approximation method

The p-hub median problem is to determine the optimal location for p hubs and assign the remaining nodes to hubs so as to minimize the total transportation costs. Under the carbon cap-and-trade policy, we study this problem by addressing the uncertain carbon emissions from the transportation, where the probability distributions of the uncertain carbon emissions are only partially available. A novel distributionally robust optimization model with the ambiguous chance constraint is developed for the uncapacitated single allocation p-hub median problem. The proposed distributionally robust optimization problem is a semi-infinite chance-constrained optimization model, which is computationally intractable for general ambiguity sets. To solve this hard optimization model, we discuss the safe approximation to the ambiguous chance constraint in the following two types of ambiguity sets. The first ambiguity set includes the probability distributions with the bounded perturbations with zero means. In this case, we can turn the ambiguous chance constraint into its computable form based on tractable approximation method. The second ambiguity set is the family of Gaussian perturbations with partial knowledge of expectations and variances. Under this situation, we obtain the deterministic equivalent form of the ambiguous chance constraint. Finally, we validate the proposed optimization model via a case study from Southeast Asia and CAB data set. The numerical experiments indicate that the optimal solutions depend heavily on the distribution information of carbon emissions. In addition, the comparison with the classical robust optimization method shows that the proposed distributionally robust optimization method can avoid over-conservative solutions by incorporating partial probability distribution information. Compared with the stochastic optimization method, the proposed method pays a small price to depict the uncertainty of probability distribution. Compared with the deterministic model, the proposed method generates the new robust optimal solution under uncertain carbon emissions.     

An extension of the Clark–Haussmann formula and applications

ABSTRACT

This work considers a financial market stochastic model where the uncertainty is driven by a multidimensional Brownian motion. The market price of the risk process makes the transition between real world probability measure and risk neutral probability measure. Traditionally, the martingale representation formulas under the risk neutral probability measure require the market price of risk process to be bounded. However, in several financial models the boundedness assumption of the market price of risk fails; for example a financial market model with the market price of risk following an Ornstein–Uhlenbeck process. This work extends the Clark–Haussmann representation formula to underlying stochastic processes which fail to satisfy the standard requirements. Our methodology is classical, and it uses a sequence of mollifiers. Our result can be applied to hedging and optimal investment in financial markets with unbounded market price of risk. In particular, the mean variance optimization problem can be addressed within our framework.     

Coradiant sets and $$\varepsilon $$-efficiency in multiobjective optimization

In multi-parametric programming an optimization problem is solved as a function of certain parameters, where the parameters are commonly considered to be bounded and continuous. In this paper, we use the case of strictly convex multi-parametric quadratic programming (mp-QP) problems with affine constraints to investigate problems where these conditions are not met. Based on the combinatorial solution approach for mp-QP problems featuring bounded and continuous parameters, we show that (i) for unbounded parameters, it is possible to obtain the multi-parametric solution if there exists one realization of the parameters for which the optimization problem can be solved and (ii) for binary parameters, we present the equivalent mixed-integer formulations for the application of the combinatorial algorithm. These advances are combined into a new, generalized version of the combinatorial algorithm for mp-QP problems, which enables the solution of problems featuring both unbounded and binary parameters. This novel approach is applied to mixed-integer bilevel optimization problems and the parametric solution of the dual of a convex problem.     

Analysis of Discrete L^2 Projection on Polynomial Spaces with Random Evaluations

We analyze the problem of approximating a multivariate function by discrete least-squares projection on a polynomial space starting from random, noise-free observations. An area of possible application of such technique is uncertainty quantification for computational models. We prove an optimal convergence estimate, up to a logarithmic factor, in the univariate case, when the observation points are sampled in a bounded domain from a probability density function bounded away from zero and bounded from above, provided the number of samples scales quadratically with the dimension of the polynomial space. Optimality is meant in the sense that the weighted $L^2$ norm of the error committed by the random discrete projection is bounded with high probability from above by the best $L^\infty $ error achievable in the given polynomial space, up to logarithmic factors. Several numerical tests are presented in both the univariate and multivariate cases, confirming our theoretical estimates. The numerical tests also clarify how the convergence rate depends on the number of sampling points, on the polynomial degree, and on the smoothness of the target function.     

Robust portfolio optimization with derivative insurance guarantees

Robust portfolio optimization aims to maximize the worst-case portfolio return given that the asset returns are allowed to vary within a prescribed uncertainty set. If the uncertainty set is not too large, the resulting portfolio performs well under normal market conditions. However, its performance may substantially degrade in the presence of market crashes, that is, if the asset returns materialize far outside of the uncertainty set. We propose a novel robust optimization model for designing portfolios that include European-style options. This model trades off weak and strong guarantees on the worst-case portfolio return. The weak guarantee applies as long as the asset returns are realized within the prescribed uncertainty set, while the strong guarantee applies for all possible asset returns. The resulting model constitutes a convex second-order cone program, which is amenable to efficient numerical solution procedures. We evaluate the model using simulated and empirical backtests and analyze the impact of the insurance guarantees on the portfolio performance.     

ROBUST MATHEMATICAL PROGRAMMING FOR NATURAL RESOURCE MODELING UNDER PARAMETRIC UNCERTAINTY

Abstract Inaccurate specification of model coefficients can lead to false or distorted findings in modeling investigations of natural resource management. Hence, this paper outlines a decision framework for optimization problems in which only the bounded set of outcomes for uncertain parameters is known. These models can be solved with standard mathematical programming software and are no larger than their deterministic equivalent. The robust approach is contrasted against deterministic analysis and is demonstrated for two applications regarding the management of natural resources. Deterministic plans are infeasible in at least 40% of cases when parameters vary from their point estimates. Inclusion of robust constraints immunizes against this infeasibility, thereby removing errors arising from false certainty. Additionally, incorporation of bounded parameters in the objective function yields interval‐valued sets containing potential outcomes. However, this increase in the general relevance of model output introduces some degree of suboptimality as deterministic plans are buffered to proactively account for potential variability. The cost of robustness increases with the simulated spread of uncertain coefficients but may be reduced through accounting for the uncertainty aversion of decision makers.