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.     

Support vector machine classifiers with uncertain knowledge sets via robust optimization

In this article we study support vector machine (SVM) classifiers in the face of uncertain knowledge sets and show how data uncertainty in knowledge sets can be treated in SVM classification by employing robust optimization. We present knowledge-based SVM classifiers with uncertain knowledge sets using convex quadratic optimization duality. We show that the knowledge-based SVM, where prior knowledge is in the form of uncertain linear constraints, results in an uncertain convex optimization problem with a set containment constraint. Using a new extension of Farkas' lemma, we reformulate the robust counterpart of the uncertain convex optimization problem in the case of interval uncertainty as a convex quadratic optimization problem. We then reformulate the resulting convex optimization problems as a simple quadratic optimization problem with non-negativity constraints using the Lagrange duality. We obtain the solution of the converted problem by a fixed point iterative algorithm and establish the convergence of the algorithm. We finally present some preliminary results of our computational experiments of the method.     

A new class of alternative theorems for SOS-convex inequalities and robust optimization

In this paper, we present a new class of alternative theorems for SOS-convex inequality systems without any qualifications. This class of theorems provides an alternative equations in terms of sums of squares to the solvability of the given inequality system. A strong separation theorem for convex sets, described by convex polynomial inequalities, plays a key role in establishing the class of alternative theorems. Consequently, we show that the optimal values of various classes of robust convex optimization problems are equal to the optimal values of related semidefinite programming problems (SDPs) and so, the value of the robust problem can be found by solving a single SDP. The class of problems includes programs with SOS-convex polynomials under data uncertainty in the objective function such as uncertain quadratically constrained quadratic programs. The SOS-convexity is a computationally tractable relaxation of convexity for a real polynomial. We also provide an application of our theorem of the alternative to a multi-objective convex optimization under data uncertainty.     

Strong duality for robust minimax fractional programming problems

We develop a duality theory for minimax fractional programming problems in the face of data uncertainty both in the objective and constraints. Following the framework of robust optimization, we establish strong duality between the robust counterpart of an uncertain minimax convex–concave fractional program, termed as robust minimax fractional program, and the optimistic counterpart of its uncertain conventional dual program, called optimistic dual. In the case of a robust minimax linear fractional program with scenario uncertainty in the numerator of the objective function, we show that the optimistic dual is a simple linear program when the constraint uncertainty is expressed as bounded intervals. We also show that the dual can be reformulated as a second-order cone programming problem when the constraint uncertainty is given by ellipsoids. In these cases, the optimistic dual problems are computationally tractable and their solutions can be validated in polynomial time. We further show that, for robust minimax linear fractional programs with interval uncertainty, the conventional dual of its robust counterpart and the optimistic dual are equivalent.     

Robust convex quadratically constrained programs

In this paper we study robust convex quadratically constrained programs, a subset of the class of robust convex programs introduced by Ben-Tal and Nemirovski [4]. In contrast to [4], where it is shown that such robust problems can be formulated as semidefinite programs, our focus in this paper is to identify uncertainty sets that allow this class of problems to be formulated as second-order cone programs (SOCP). We propose three classes of uncertainty sets for which the robust problem can be reformulated as an explicit SOCP and present examples where these classes of uncertainty sets are natural. Research partially supported by DOE grant GE-FG01-92ER-25126, NSF grants DMS-94-14438, CDA-97-26385, DMS-01-04282 and ONR grant N000140310514.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

Robust solutions of uncertain complex-valued quadratically constrained programs

In this paper, we discuss complex convex quadratically constrained optimization with uncertain data. Using S-Lemma, we show that the robust counterpart of complex convex quadratically constrained optimization with ellipsoidal or intersection-of-two-ellipsoids uncertainty set leads to a complex semidefinite program. By exploring the approximate S-Lemma, we give a complex semidefinite program which approximates the NP-hard robust counterpart of complex convex quadratic optimization with intersection-of-ellipsoids uncertainty set.     

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.     

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.     

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.     

SOS-Convex Semialgebraic Programs and its Applications to Robust Optimization: A Tractable Class of Nonsmooth Convex Optimization

In this paper, we introduce a new class of nonsmooth convex functions called SOS-convex semialgebraic functions extending the recently proposed notion of SOS-convex polynomials. This class of nonsmooth convex functions covers many common nonsmooth functions arising in the applications such as the Euclidean norm, the maximum eigenvalue function and the least squares functions with ? ₁-regularization or elastic net regularization used in statistics and compressed sensing. We show that, under commonly used strict feasibility conditions, the optimal value and an optimal solution of SOS-convex semialgebraic programs can be found by solving a single semidefinite programming problem (SDP). We achieve the results by using tools from semialgebraic geometry, convex-concave minimax theorem and a recently established Jensen inequality type result for SOS-convex polynomials. As an application, we show that robust SOS-convex optimization proble ms under restricted spectrahedron data uncertainty enjoy exact SDP relaxations. This extends the existing exact SDP relaxation result for restricted ellipsoidal data uncertainty and answers an open question in the literature on how to recover a robust solution of uncertain SOS-convex polynomial programs from its semidefinite programming relaxation in this broader setting.     

Robustness and duality in linear programming

In this paper, we consider a linear program in which the right hand sides of theconstraints are uncertain and inaccurate. This uncertainty is represented byintervals, that is to say that each right hand side can take any value in itsinterval regardless of other constraints. The problem is then to determine arobust solution, which is satisfactory for all possible coefficient values.Classical criteria, such as the worst case and the maximum regret, are appliedto define different robust versions of the initial linear program. Morerecently, Bertsimas and Sim have proposed a new model that generalizes the worstcase criterion. The subject of this paper is to establish the relationshipsbetween linear programs with uncertain right hand sides and linear programs withuncertain objective function coefficients using the classical duality theory. Weshow that the transfer of the uncertainty from the right hand sides to theobjective function coefficients is possible by establishing new dualityrelations. When the right hand sides are approximated by intervals, we alsopropose an extension of the Bertsimas and Sim's model and we show that themaximum regret criterion is equivalent to the worst case criterion.     

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.     

Centered solutions for uncertain linear equations

Our contribution is twofold. Firstly, for a system of uncertain linear equations where the uncertainties are column-wise and reside in general convex sets, we derive convex representations for united and tolerable solution sets. Secondly, to obtain centered solutions for uncertain linear equations, we develop a new method based on adjustable robust optimization (ARO) techniques to compute the maximum size inscribed convex body (MCB) of the set of the solutions. In general, the obtained MCB is an inner approximation of the solution set, and its center is a potential solution to the system. We use recent results from ARO to characterize for which convex bodies the obtained MCB is optimal. We compare our method both theoretically and numerically with an existing method that minimizes the worst-case violation. Applications to the input–output model, Colley’s Matrix Rankings and Article Influence Scores demonstrate the advantages of the new method.     

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 %.     

When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?

Adjustable robust optimization (ARO) generally produces better worst-case solutions than static robust optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we provide conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that when the uncertainty is constraint-wise, the problem is convex with respect to the adjustable variables and concave with respect to the uncertain parameters, the adjustable variables lie in a convex and compact set and the uncertainty set is convex and compact, then robust solutions are also optimal for the corresponding ARO problem. Furthermore, we prove that if some of the uncertain parameters are constraint-wise and the rest are not, then under a similar set of assumptions there is an optimal decision rule for the ARO problem that does not depend on the constraint-wise uncertain parameters. Also, we show for a class of problems that using affine decision rules that depend on all of the uncertain parameters yields the same optimal objective value as when the rules depend solely on the non-constraint-wise uncertain parameters. Finally, we illustrate the usefulness of these results by applying them to convex quadratic and conic quadratic problems.     

Robust solutions to uncertain linear complementarity problems

In this paper,we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain,and it is only known to belong to a prescribed uncertainty set.We propose the notion of the p- robust counterpart and the p-robust solution of uncertain linear complementarity problems.We discuss uncertain linear complementarity problems with three different uncertainty sets,respectively,including an unknown-but-bounded uncertainty set,an ellipsoidal uncertainty set and an intersection-of-ellipsoids uncertainty set,and present some sufficient and necessary(or sufficient) conditions which p- robust solutions satisfy.Some special cases are investigated in this paper.     

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.     

Log-robust portfolio management with parameter ambiguity

We present a robust optimization approach to portfolio management under uncertainty when randomness is modeled using uncertainty sets for the continuously compounded rates of return, which empirical research argues are the true drivers of uncertainty, but the parameters needed to define the uncertainty sets, such as the drift and standard deviation, are not known precisely. Instead, a finite set of scenarios is available for the input data, obtained either using different time horizons or assumptions in the estimation process. Our objective is to maximize the worst-case portfolio value (over a set of allowable deviations of the uncertain parameters from their nominal values, using the worst-case nominal values among the possible scenarios) at the end of the time horizon in a one-period setting. Short sales are not allowed. We consider both the independent and correlated assets models. For the independent assets case, we derive a convex reformulation, albeit involving functions with singular Hessians. Because this slows computation times, we also provide lower and upper linear approximation problems and devise an algorithm that gives the decision maker a solution within a desired tolerance from optimality. For the correlated assets case, we suggest a tractable heuristic that uses insights derived in the independent assets case.