Robust ranking and portfolio optimization

The portfolio optimization problem has attracted researchers from many disciplines to resolve the issue of poor out-of-sample performance due to estimation errors in the expected returns. A practical method for portfolio construction is to use assets’ ordering information, expressed in the form of preferences over the stocks, instead of the exact expected returns. Due to the fact that the ranking itself is often described with uncertainty, we introduce a generic robust ranking model and apply it to portfolio optimization. In this problem, there are n objects whose ranking is in a discrete uncertainty set. We want to find a weight vector that maximizes some generic objective function for the worst realization of the ranking. This robust ranking problem is a mixed integer minimax problem and is very difficult to solve in general. To solve this robust ranking problem, we apply the constraint generation method, where constraints are efficiently generated by solving a network flow problem. For empirical tests, we use post-earnings-announcement drifts to obtain ranking uncertainty sets for the stocks in the DJIA index. We demonstrate that our robust portfolios produce smaller risk compared to their non-robust counterparts.     

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.     

Variable-sized uncertainty and inverse problems in robust optimization

In robust optimization, the general aim is to find a solution that performs well over a set of possible parameter outcomes, the so-called uncertainty set. In this paper, we assume that the uncertainty size is not fixed, and instead aim at finding a set of robust solutions that covers all possible uncertainty set outcomes. We refer to these problems as robust optimization with variable-sized uncertainty. We discuss how to construct smallest possible sets of min–max robust solutions and give bounds on their size.A special case of this perspective is to analyze for which uncertainty sets a nominal solution ceases to be a robust solution, which amounts to an inverse robust optimization problem. We consider this problem with a min–max regret objective and present mixed-integer linear programming formulations that can be applied to construct suitable uncertainty sets.Results on both variable-sized uncertainty and inverse problems are further supported with experimental data.     

Two-stage network constrained robust unit commitment problem

For a current deregulated power system, a large amount of operating reserve is often required to maintain the reliability of the power system using traditional approaches. In this paper, we propose a two-stage robust optimization model to address the network constrained unit commitment problem under uncertainty. In our approach, uncertain problem parameters are assumed to be within a given uncertainty set. We study cases with and without transmission capacity and ramp-rate limits (The latter case was described in Zhang and Guan (2009), for which the analysis part is included in Section 3 in this paper). We also analyze solution schemes to solve each problem that include an exact solution approach and an efficient heuristic approach that provides tight lower and upper bounds for the general network constrained robust unit commitment problem. The final computational experiments on an IEEE 118-bus system verify the effectiveness of our approaches, as compared to the nominal model without considering the uncertainty.     

A robustness approach to uncapacitated network design problems

In this paper, we address uncapacitated network design problems characterised by uncertainty in the input data. Network design choices have a determinant impact on the effectiveness of the system. Design decisions are frequently made with a great degree of uncertainty about the conditions under which the system will be required to operate. Instead of finding optimal designs for a given future scenario, designers often search for network configurations that are “good” for a variety of likely future scenarios. This approach is referred to as the “robustness” approach to system design. We present a formal definition of “robustness” for the uncapacitated network design problem, and develop algorithms aimed at finding robust network designs. These algorithms are adaptations of the Benders decomposition methodology that are tailored so they can efficiently identify robust network designs. We tested the proposed algorithms on a set of randomly generated problems. Our computational experiments showed two important properties. First, robust solutions are abundant in uncapacitated network design problems, and second, the proposed algorithms performance is satisfactory in terms of cost and number of robust network designs obtained.     

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.     

Solving maximum fuzzy clique problem with neural networks and its applications

The maximum clique problem is an important problem in graph theory. Many real-life problems are still being mapped into this problem for their effective solutions. A natural extension of this problem that has emerged very recently in many real-life networks, is its fuzzification. The problem of finding the maximum fuzzy clique has been formalized on fuzzy graphs and subsequently addressed in this paper. It has been shown here that the problem reduces to an unconstrained quadratic 0–1 programming problem. Using a maximum neural network, along with mutation capability of genetic adaptive systems, the reduced problem has been solved. Empirical studies have been done by applying the method on stock flow graphs to identify the collusion set, which contains a group of traders performing unfair trading among themselves. Additionally, it has been applied on a gene co-expression network to find out significant gene modules and on some benchmark graphs.     

A partitioning algorithm for the multicommodity network flow problem

A partitioning algorithm for solving the general minimum cost multicommodity flow problem for directed graphs is presented in the framework of a network flow method and the dual simplex method. A working basis which is considerably smaller than the number of capacitated arcs in the given network is employed and a set of simple secondary constraints is periodically examined. Some computational aspects and preliminary experimental results are discussed.     

Decomposition for adjustable robust linear optimization subject to uncertainty polytope

We present in this paper a general decomposition framework to solve exactly adjustable robust linear optimization problems subject to polytope uncertainty. Our approach is based on replacing the polytope by the set of its extreme points and generating the extreme points on the fly within row generation or column-and-row generation algorithms. The novelty of our approach lies in formulating the separation problem as a feasibility problem instead of a max–min problem as done in recent works. Applying the Farkas lemma, we can reformulate the separation problem as a bilinear program, which is then linearized to obtained a mixed-integer linear programming formulation. We compare the two algorithms on a robust telecommunications network design under demand uncertainty and budgeted uncertainty polytope. Our results show that the relative performance of the algorithms depend on whether the budget is integer or fractional.     

Robust maximum weighted independent-set problems on interval graphs

We study the maximum weighted independent-set problem on interval graphs with uncertainty on the vertex weights. We use the absolute robustness criterion and the min–max regret criterion to evaluate solutions. For a discrete scenario set, we find that the problem is NP-hard for each of the robustness criteria; we also provide pseudo-polynomial time algorithms when there is a constant number of scenarios and show that the problem is strongly NP-hard when the set of scenarios is unbounded. When the scenario set is a Cartesian product, we prove that the problem is equivalent to a maximum weighted independent-set problem on the same interval graph but without uncertainty for the first objective function and that the scenario set can be reduced for the second objective function.     

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     

Disturbance rejection in robust PdE-based MRAC laws for uncertain heterogeneous multiagent networks under boundary reference

Disturbance is a pervasive source of uncertainty in most applications. This paper presents model reference adaptive control (MRAC) laws for uncertain multiagent networks with a disturbance rejection capability. The algorithms proposed can also be viewed as the extension of the robust model reference adaptive control (MRAC) laws with disturbance rejection recently derived for systems described by parabolic and hyperbolic partial differential equations (PDEs) with spatially-varying parameters under distributed sensing and actuation to heterogeneous multiagent networks characterized by parameter uncertainty. The latter extension is carried out using partial difference equations (PdEs) on graphs that preserve parabolic and hyperbolic like cumulative network behavior. Unlike in the PDE case, only boundary input is specified for the reference model. The algorithms proposed directly incorporate this boundary reference input into the reference PdE to generate the distributed admissible reference evolution profile followed by the agents. The agent evolution thus depends only on the interaction with the adjacent agents, making the system fully decentralized. Numerical examples are presented as well. The resulting PdE MRAC laws inherit the robust linear structure of their PDE counterparts.     

Robust combinatorial optimization with variable budgeted uncertainty

We introduce a new model for robust combinatorial optimization where the uncertain parameters belong to the image of multifunctions of the problem variables. In particular, we study the variable budgeted uncertainty, an extension of the budgeted uncertainty introduced by Bertsimas and Sim. Variable budgeted uncertainty can provide the same probabilistic guarantee as the budgeted uncertainty while being less conservative for vectors with few non-zero components. The feasibility set of the resulting optimization problem is in general non-convex so that we propose a mixed-integer programming reformulation for the problem, based on the dualization technique often used in robust linear programming. We show how to extend these results to non-binary variables and to more general multifunctions involving uncertainty set defined by conic constraints that are affine in the problem variables. We present a computational comparison of the budgeted uncertainty and the variable budgeted uncertainty on the robust knapsack problem. The experiments show a reduction of the price of robustness by an average factor of 18 %.     

New product launch decisions with robust optimization

We consider a problem where a company must decide the order in which to launch new products within a given time horizon and budget constraints, and where the parameters of the adoption rate of these new products are subject to uncertainty. This uncertainty can bring significant change to the optimal launch sequence. We present a robust optimization approach that incorporates such uncertainty on the Bass diffusion model for new products as well as on the price response function of partners that collaborate with the company in order to bring its products to market. The decision-maker optimizes his worst-case profit over an uncertainty set where nature chooses the time periods in which (integer) units of the budgets of uncertainty are used for worst impact. This leads to uncertainty sets with binary variables. We show that a conservative approximation of the robust problem can nonetheless be reformulated as a mixed integer linear programming problem, is therefore of the same structure as the deterministic problem and can be solved in a tractable manner. Finally, we illustrate our approach on numerical experiments. Our model also incorporates contracts with potential commercialization partners. The key output of our work is a sequence of product launch times that protects the decision-maker against parameter uncertainty for the adoption rates of the new products and the response of potential partners to partnership offers.     

On connected domination in unit ball graphs

Given a simple undirected graph, the minimum connected dominating set problem is to find a minimum cardinality subset of vertices D inducing a connected subgraph such that each vertex outside D has at least one neighbor in D. Approximations of minimum connected dominating sets are often used to represent a virtual routing backbone in wireless networks. This paper first proposes a constant-ratio approximation algorithm for the minimum connected dominating set problem in unit ball graphs and then introduces and studies the edge-weighted bottleneck connected dominating set problem, which seeks a minimum edge weight in the graph such that the corresponding bottleneck subgraph has a connected dominating set of size k. In wireless network applications this problem can be used to determine an optimal transmission range for a network with a predefined size of the virtual backbone. We show that the problem is hard to approximate within a factor better than 2 in graphs whose edge weights satisfy the triangle inequality and provide a 3-approximation algorithm for such graphs. We also show that for fixed k the problem is polynomially solvable in unit disk and unit ball graphs.     

Optimizing cost flows by edge cost and capacity upgrade

We examine a network upgrade problem for cost flows. A budget can be distributed among the arcs of the network. An investment on each single arc can be used either to decrease the arc flow cost, or to increase the arc capacity, or both. The goal is to maximize the flow through the network while not exceeding bounds on the budget and on the total flow cost.

The problems are NP-hard even on series-parallel graphs. We provide an approximation algorithm on series-parallel graphs which, for arbitrary δ,>0, produces a solution which exceeds the bounds on the budget and the flow cost by factors of at most 1+δ and 1+, respectively, while the amount of flow is at least that of an optimum solution. The running time of the algorithm is polynomial in the input size and 1/(δ). In addition we give an approximation algorithm on general graphs applicable to problem instances with small arc capacities.     

Regularized robust optimization: the optimal portfolio execution case

An uncertainty set is a crucial component in robust optimization. Unfortunately, it is often unclear how to specify it precisely. Thus it is important to study sensitivity of the robust solution to variations in the uncertainty set, and to develop a method which improves stability of the robust solution. In this paper, to address these issues, we focus on uncertainty in the price impact parameters in an optimal portfolio execution problem. We first illustrate that a small variation in the uncertainty set may result in a large change in the robust solution. We then propose a regularized robust optimization formulation which yields a solution with a better stability property than the classical robust solution. In this approach, the uncertainty set is regularized through a regularization constraint, defined by a linear matrix inequality using the Hessian of the objective function and a regularization parameter. The regularized robust solution is then more stable with respect to variation in the uncertainty set specification, in addition to being more robust to estimation errors in the price impact parameters. The regularized robust optimal execution strategy can be computed by an efficient method based on convex optimization. Improvement in the stability of the robust solution is analyzed. We also study implications of the regularization on the optimal execution strategy and its corresponding execution cost. Through the regularization parameter, one can adjust the level of conservatism of the robust solution.     

A robust data envelopment analysis model with different scenarios

Input and output data, under uncertainty, must be taken into account as an essential part of data envelopment analysis (DEA) models in practice. Many researchers have dealt with this kind of problem using fuzzy approaches, DEA models with interval data or probabilistic models. This paper presents an approach to scenario-based robust optimization for conventional DEA models. To consider the uncertainty in DEA models, different scenarios are formulated with a specified probability for input and output data instead of using point estimates. The robust DEA model proposed is aimed at ranking decision-making units (DMUs) based on their sensitivity analysis within the given set of scenarios, considering both feasibility and optimality factors in the objective function. The model is based on the technique proposed by Mulvey et al. (1995) for solving stochastic optimization problems. The effect of DMUs on the product possibility set is calculated using the Monte Carlo method in order to extract weights for feasibility and optimality factors in the goal programming model. The approach proposed is illustrated and verified by a case study of an engineering company.     

Relaxed robust second-order-cone programming

In this paper, we propose an approximate optimization model for the robust second-order-cone programming problem with a single-ellipsoid uncertainty set for which the computational complexity is not known yet. We prove that this approximate robust model can be equivalently reformulated as a finite convex optimization problem.     

Robust optimization with applications to game theory

In this article, we investigate robust optimization equilibria with two players, in which each player can neither evaluate his opponent's strategy nor his own cost matrix accurately while may estimate a bounded set of the strategy or cost matrix. We obtain a result that solving this equilibria can be formulated as solving a second-order cone complementarity problem under an ellipsoid uncertainty set or a mixed complementarity problem under a box uncertainty set. We present some numerical results to illustrate the behaviour of robust optimization equilibria.