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.     

Motzkin decomposition of closed convex sets

Theodore Motzkin proved, in 1936, that any polyhedral convex set can be expressed as the (Minkowski) sum of a polytope and a polyhedral convex cone. This paper provides five characterizations of the larger class of closed convex sets in finite dimensional Euclidean spaces which are the sum of a compact convex set with a closed convex cone. These characterizations involve different types of representations of closed convex sets as the support functions, dual cones and linear systems whose relationships are also analyzed in the paper. The obtaining of information about a given closed convex set F and the parametric linear optimization problem with feasible set F from each of its different representations, including the Motzkin decomposition, is also discussed.     

Some characterizations of robust optimal solutions for uncertain convex optimization problems

In this paper, we consider robust optimal solutions for a convex optimization problem in the face of data uncertainty both in the objective and constraints. By using the properties of the subdifferential sum formulae, we first introduce a robust-type subdifferential constraint qualification, and then obtain some completely characterizations of the robust optimal solution of this uncertain convex optimization problem. We also investigate Wolfe type robust duality between the uncertain convex optimization problem and its uncertain dual problem by proving duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem. Moreover, we show that our results encompass as special cases some optimization problems considered in the recent literature.     

A Unifying Approach to Robust Convex Infinite Optimization Duality

This paper considers an uncertain convex optimization problem, posed in a locally convex decision space with an arbitrary number of uncertain constraints. To this problem, where the uncertainty only affects the constraints, we associate a robust (pessimistic) counterpart and several dual problems. The paper provides corresponding dual variational principles for the robust counterpart in terms of the closed convexity of different associated cones.     

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.     

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.     

Dual characterizations of the set containments with strict cone-convex inequalities in Banach spaces

We give characterizations of the containment of a convex set either in an arbitrary convex set or in a set described by reverse cone-convex inequalities in Banach spaces. The convex sets under consideration are the solution sets of an arbitrary number of cone-convex inequalities, which can be either weak or strict inequalities. These characterizations provide ways of verifying the containments either by comparing their corresponding dual cones or by checking the consistency of suitable associated systems. Particular cases of dual characterizations of set containments have played key roles in solving large scale knowledge-based data classification problems, where they are used to describe the containments as inequality constraints in optimization problems. The concept of evenly convex set is used to derive the dual conditions, characterizing the set containments.      

On robust duality for fractional programming with uncertainty data

In this paper, we present a duality theory for fractional programming problems in the face of data uncertainty via robust optimization. By employing conjugate analysis, we establish robust strong duality for an uncertain fractional programming problem and its uncertain Wolfe dual programming problem by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. We show that our results encompass as special cases some programming problems considered in the recent literature. Moreover, we also show that robust strong duality always holds for linear fractional programming problems under scenario data uncertainty or constraint-wise interval uncertainty, and that the optimistic counterpart of the dual is tractable computationally.     

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 H∞ control for a class of switched nonlinear cascade systems via multiple Lyapunov functions approach

This paper addresses the problem of robust H_∞ control for a class of switched nonlinear cascade systems with parameter uncertainty using the multiple Lyapunov functions (MLFs) approach. Each subsystem under consideration is composed of two cascade-connected parts. The uncertain parameters are assumed to be in a known compact set and are allowed to enter the system nonlinearly. Based on the explicit construction of Lyapunov functions, which avoids solving the Hamilton-Jacobi equations, sufficient conditions for the solvability of the robust H_∞ control problem are presented. As an application, the hybrid robust H_∞ control problem for a class of uncertain non-switched nonlinear cascade systems is solved when no single continuous controller is effective. Finally, a numerical example is provided to demonstrate the feasibility of the proposed method.     

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.     

Set Containment Characterization

Characterization of the containment of a polyhedral set in a closed halfspace, a key factor in generating knowledge-based support vector machine classifiers [7], is extended to the following: (i) containment of one polyhedral set in another; (ii) containment of a polyhedral set in a reverse-convex set defined by convex quadratic constraints; (iii) Containment of a general closed convex set, defined by convex constraints, in a reverse-convex set defined by convex nonlinear constraints. The first two characterizations can be determined in polynomial time by solving m linear programs for (i) and m convex quadratic programs for (ii), where m is the number of constraints defining the containing set. In (iii), m convex programs need to be solved in order to verify the characterization, where again m is the number of constraints defining the containing set. All polyhedral sets, like the knowledge sets of support vector machine classifiers, are characterized by the intersection of a finite number of closed halfspaces.     

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.     

Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard

As shown in previous work, robust linear programming problems featuring polyhedral right-hand side (RHS) uncertainty (a) arise in many practical applications; (b) frequently lead to robust equivalents belonging to the class of strongly NP-hard problems. In the present paper the case of ellipsoidal RHS uncertainty is investigated and similar complexity results are shown to hold even when restricting to simplified specially structured problems related to robust production planning under uncertain customer requirements. The proof is based on a reduction which significantly differs from the one used in the case of polyhedral RHS uncertainty.     

Isotone functions,dual cones,and networks

If the collection of all real-valued functions defined on a finite partially ordered set S of n elements is identified in the natural way with Rⁿ, it is obvious that the subset of functions that are isotone or order preserving with respect to the given partial order constitutes a closed, convex, polyhedral cone K in Rⁿ. The dual cone K^* of K is the set of all linear functionals that are nonpositive of K. This article identifies the important geometric properties of K, and characterizes a nonredundant set of defining equations and inequalities for K^* in terms of a special class of partitions of S into upper and lower sets. These defining constraints immediately imply a set of extreme rays spanning K and K^*. One of the characterizations of K^* involves feasibility conditions on flows in a network. These conditions are also used as a tool in analysis.     

Dual Characterizations of Set Containments with Strict Convex Inequalities

Characterizations of the containment of a convex set either in an arbitrary convex set or in the complement of a finite union of convex sets (i.e., the set, described by reverse-convex inequalities) are given. These characterizations provide ways of verifying the containments either by comparing their corresponding dual cones or by checking the consistency of suitable associated systems. The convex sets considered in this paper are the solution sets of an arbitrary number of convex inequalities, which can be either weak or strict inequalities. Particular cases of dual characterizations of set containments have played key roles in solving large scale knowledge-based data classification problems where they are used to describe the containments as inequality constraints in optimization problems. The idea of evenly convex set (intersection of open half spaces), which was introduced by W. Fenchel in 1952, is used to derive the dual conditions, characterizing the set containments.     

Mixed complementarity problems for robust optimization equilibrium in bimatrix game

In this paper, we investigate the bimatrix game using the robust optimization approach, in which each player may neither exactly estimate his opponent’s strategies nor evaluate his own cost matrix accurately while he may estimate a bounded uncertain set. We obtain computationally tractable robust formulations which turn to be linear programming problems and then solving a robust optimization equilibrium can be converted to solving a mixed complementarity problem under the l ₁ ∩ l _∞-norm. Some numerical results are presented to illustrate the behavior of the robust optimization equilibrium.     

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.     

Cutting plane versus compact formulations for uncertain (integer) linear programs

Robustness is about reducing the feasible set of a given nominal optimization problem by cutting ??risky?? solutions away. To this end, the most popular approach in the literature is to extend the nominal model with a polynomial number of additional variables and constraints, so as to obtain its robust counterpart. Robustness can also be enforced by adding a possibly exponential family of cutting planes, which typically leads to an exponential formulation where cuts have to be generated at run time. Both approaches have pros and cons, and it is not clear which is the best one when approaching a specific problem. In this paper we computationally compare the two options on some prototype problems with different characteristics. We first address robust optimization à la Bertsimas and Sim for linear programs, and show through computational experiments that a considerable speedup (up to 2 orders of magnitude) can be achieved by exploiting a dynamic cut generation scheme. For integer linear problems, instead, the compact formulation exhibits a typically better performance. We then move to a probabilistic setting and introduce the uncertain set covering problem where each column has a certain probability of disappearing, and each row has to be covered with high probability. A related uncertain graph connectivity problem is also investigated, where edges have a certain probability of failure. For both problems, compact ILP models and cutting plane solution schemes are presented and compared through extensive computational tests. The outcome is that a compact ILP formulation (if available) can be preferable because it allows for a better use of the rich arsenal of preprocessing/cut generation tools available in modern ILP solvers. For the cases where such a compact ILP formulation is not available, as in the uncertain connectivity problem, we propose a restart solution strategy and computationally show its practical effectiveness.     

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.