Robust linear semi-infinite programming duality under uncertainty

In this paper, we propose a duality theory for semi-infinite linear programming problems under uncertainty in the constraint functions, the objective function, or both, within the framework of robust optimization. We present robust duality by establishing strong duality between the robust counterpart of an uncertain semi-infinite linear program and the optimistic counterpart of its uncertain Lagrangian dual. We show that robust duality holds whenever a robust moment cone is closed and convex. We then establish that the closed-convex robust moment cone condition in the case of constraint-wise uncertainty is in fact necessary and sufficient for robust duality. In other words, the robust moment cone is closed and convex if and only if robust duality holds for every linear objective function of the program. In the case of uncertain problems with affinely parameterized data uncertainty, we establish that robust duality is easily satisfied under a Slater type constraint qualification. Consequently, we derive robust forms of the Farkas lemma for systems of uncertain semi-infinite linear inequalities.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

What do robust equity portfolio models really do?

Most of previous work on robust equity portfolio optimization has focused on its formulation and performance. In contrast, in this paper we analyze the behavior of robust equity portfolios to determine whether reducing the sensitivity to input estimation errors is all robust models do and investigate any side-effects of robust formulations. Therefore, our focus is on the relationship between fundamental factors and robust models in order to determine if robust equity portfolios are consistently investing more in the factors opposed to individual asset movements. To do so, we perform regressions with factor returns to explain how robust portfolios behave compared to portfolios generated from the Markowitz’s mean-variance model. We find that robust equity portfolios consistently show higher correlation with the three fundamental factors used in the Fama-French factor model. Furthermore, more robustness among robust portfolios results in a higher correlation with the Fama-French three factors. In fact, we show that as equity portfolios under no constraints on portfolio weights become more robust, they consistently depend more on the market and large factors. These results show that robust models are betting on the fundamental factors instead of individual asset movements.     

鲁棒优化中的Pareto有效性

对于一般的不确定优化问题, 研究了鲁棒解的~Pareto 有效性. 首先, 证明了Pareto 鲁棒解集即是鲁棒解集的Pareto 有效集, 因此求Pareto 鲁棒解等价于求鲁棒解集的Pareto 有效元. 其次, 基于推广的epsilon-约束方法, 得到了Pareto 鲁棒解的生成方法.     

Tractable Approximations to Robust Conic Optimization Problems

In earlier proposals, the robust counterpart of conic optimization problems exhibits a lateral increase in complexity, i.e., robust linear programming problems (LPs) become second order cone problems (SOCPs), robust SOCPs become semidefinite programming problems (SDPs), and robust SDPs become NP-hard. We propose a relaxed robust counterpart for general conic optimization problems that (a) preserves the computational tractability of the nominal problem; specifically the robust conic optimization problem retains its original structure, i.e., robust LPs remain LPs, robust SOCPs remain SOCPs and robust SDPs remain SDPs, and (b) allows us to provide a guarantee on the probability that the robust solution is feasible when the uncertain coefficients obey independent and identically distributed normal distributions. The research of the author was partially supported by the Singapore-MIT alliance. The research of the author is supported by NUS academic research grant R-314-000-066-122 and the Singapore-MIT alliance.     

Adjustable robust counterpart of conic quadratic problems

This paper presents an approximate affinely adjustable robust counterpart for conic quadratic constraints. The theory is applied to obtain robust solutions to the problems of subway route design with implementation errors and a supply chain management with uncertain demands. Comparison of the adjustable solutions with the nominal and non-adjustable robust solutions shows that the adjustable (dynamic) robust solution maintains feasibility for all possible realizations, while being less conservative than the usual (static) robust counterpart solution.     

部分线性回归模型的M-估计

本文讨论部分线性回归模型的M-估计．用局部线性方法给出未知函数的M-估计，用两步估计方法给出参数的M-估计．进一步证明了未知函数的M-估计的弱一致性和渐近正态性，参数的M-估计的弱一致性．     

On 2-stage robust LP with RHS uncertainty: complexity results and applications

We investigate here the class—denoted R-LP-RHSU—of two-stage robust linear programming problems with right-hand-side uncertainty. Such problems arise in many applications e.g: robust PERT scheduling (with uncertain task durations); robust maximum flow (with uncertain arc capacities); robust network capacity expansion problems; robust inventory management; some robust production planning problems in the context of power production/distribution systems. It is shown that such problems can be formulated as large scale linear programs with associated nonconvex separation subproblem. A formal proof of strong NP-hardness for the general case is then provided, and polynomially solvable subclasses are exhibited. Differences with other previously described robust LP problems (featuring row-wise uncertainty instead of column wise uncertainty) are highlighted.     

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.     

Dual characterizations of set containments involving uncertain polyhedral sets in Banach spaces with applications

In this paper, we first give a dual characterization for set containments defined by lower semi-continuous and sublinear functions on Banach spaces. Next, we provide dual characterizations for robust polyhedral containments where a robust counterpart of an uncertain polyhedral set is contained in another polyhedral set or a polyhedral set is contained in a robust counterpart of an uncertain polyhedral set. Finally, as an application, we derive Lagrange multiplier characterizations for robust solutions of the robust uncertain linear programming problems.     

Characterizing robust set containments and solutions of uncertain linear programs without qualifications

Qualification-free dual characterizations are given for robust polyhedral set containments where a robust counterpart of an uncertain polyhedral set is contained in another polyhedral set or a polyhedral set is contained in a robust counterpart of an uncertain polyhedral set. These results are used to characterize robust solutions of uncertain linear programs, where the uncertainty is defined in terms of intervals or l₁-balls. The hidden separable sub-linearity of the robust counterparts allows qualification-free dual characterizations.     

多目标优化问题鲁棒有效解与真有效解之间的关系

在一定条件下研究了多目标优化问题鲁棒有效解与真有效解之间的关系及鲁棒有效解的最优性条件.首先,给出多目标优化问题鲁棒弱有效解的概念,研究它与鲁棒有效解和真有效解之间的关系,举例说明了相关结果的合理性.其次,在次类凸和伪凸性假设下研究了鲁棒有效解的必要性条件和充分性条件.     

强部分逆网络流问题

Abstract. In this paper,a new model for inverse network flow problems,robust partial inverseproblem is presented. For a given partial solution,the robust partial inverse problem is to modify the coefficients optimally such that all full solutions containing the partial solution becomeoptimal under new coefficients. It has been shown that the robust partial inverse spanning treeproblem can be formulated as a combinatorial linear program,while the robust partial inverseminimum cut problem and the robust partial inverse assignment problem can be solved by combinatorial strongly polynomial algorithms.     

Robust stability of uncertain impulsive dynamical systems

This paper studies robust stability of uncertain impulsive dynamical systems. By introducing the concepts of uniformly positive definite matrix functions and Hamilton–Jacobi/Riccati inequalities, several criteria on robust stability, robust asymptotic stability and robust exponential stability are established. An example is also worked through to illustrate our results.     

Robust estimation of periodic autoregressive processes in the presence of additive outliers

This paper suggests a robust estimation procedure for the parameters of the periodic AR (PAR) models when the data contains additive outliers. The proposed robust methodology is an extension of the robust scale and covariance functions given in, respectively, Rousseeuw and Croux (1993) [28], and Ma and Genton (2000) [23] to accommodate periodicity. These periodic robust functions are used in the Yule-Walker equations to obtain robust parameter estimates. The asymptotic central limit theorems of the estimators are established, and an extensive Monte Carlo experiment is conducted to evaluate the performance of the robust methodology for periodic time series with finite sample sizes. The quarterly Fraser River data was used as an example of application of the proposed robust methodology. All the results presented here give strong motivation to use the methodology in practical situations in which periodically correlated time series contain additive outliers.     

Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

到达不确定呼叫中心人员配置的鲁棒优化模型

针对呼叫中心实际运营中顾客到达不确定的特点,采用鲁棒离散优化方法,建立呼叫中心人员配置的鲁棒模型。利用对偶原理将鲁棒模型转换易于求解的线性鲁棒对等式,通过调节模型中的鲁棒参数来权衡鲁棒解的保守性与最优性之间的关系,计算模型中约束违背概率上限来表示鲁棒解的可靠性。通过现实呼叫中心数据算例,验证了模型的有效性,分析了不同鲁棒水平下各时间段服务人员配置规律,以及系统最小成本与违背概率之间的权衡关系。最后,对到达扰动系数进行了敏感性分析。     

An Exact Formula for Radius of Robust Feasibility of Uncertain Linear Programs

We present an exact formula for the radius of robust feasibility of uncertain linear programs with a compact and convex uncertainty set. The radius of robust feasibility provides a value for the maximal ‘size’ of an uncertainty set under which robust feasibility of the uncertain linear program can be guaranteed. By considering spectrahedral uncertainty sets, we obtain numerically tractable radius formulas for commonly used uncertainty sets of robust optimization, such as ellipsoids, balls, polytopes and boxes. In these cases, we show that the radius of robust feasibility can be found by solving a linearly constrained convex quadratic program or a minimax linear program. The results are illustrated by calculating the radius of robust feasibility of uncertain linear programs for several different uncertainty sets.     

二阶可加混料模型稳健D-最优设计

本文研究了在给定两个随机模型先验测度r下的q分量二阶可加混料模型稳健D-最优设计。依据Kiefer次序下完备集的结果且结合稳健D-最优准则,给出了二阶可加模型稳健D-最优的相关理论,并得到了四分量可加模型稳健D-最优ξα_r~*=α_r~*ξ_1~*+(1-α_r~*)ξ_2~*,且利用等价性定理证明了ξα_r~*为稳健D-最优设计。同时基于α_r~*与先验测度r的关系,介绍了先验测度r选择的效率最大最小原则,得到了四分量二阶可加模型的最优先验测度r~*,且比较了四分量二阶可加混料模型稳健D-最优设计与D-最优设计的效率。     

Robust analysis and global optimization

In this paper, the properties of robust sets and robust functions are studied. Also, we study minimization of a robust function over a robust set and extend the optimality conditions of [3] and the algorithm of [4,5] to our case. The algorithm is shown to be effective.This research was supported by the National Science Foundation of China.