Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint

This paper extends and completes the discussion by Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted) about the quadratic programming over one quadratic constraint (QP1QC). In particular, we relax the assumption to cover more general cases when the two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence. Under such an assumption, the nonconvex (QP1QC) problem can be solved through a dual approach with no duality gap. This is unusual for general nonconvex programming but we can explain by showing that (QP1QC) is indeed equivalent to a linearly constrained convex problem, which happens to be dual of the dual of itself. Another type of hidden convexity can be also found in the boundarification technique developed in Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted).     

Robust topology optimization for multi-material structures under interval uncertainty

In this paper, we propose an efficient method to design robust multi-material structures under interval loading uncertainty. The objective of this study is to minimize the structural compliance of linear elastic structures. First, the loading uncertainty can be decomposed into two unit forces in the horizontal and vertical directions based on the orthogonal decomposition, which separates the uncertainty into the calculation coefficients of structural compliance that are not related to the finite element analysis. In this manner, the time-consuming procedure, namely, the nested double-loop optimization, can be avoided. Second, the uncertainty problem can be transformed into an augmented deterministic problem by means of uniform sampling, which exploits the coefficients related to interval variables. Finally, an efficient sensitivity analysis method is explicitly developed. Thus, the robust topology optimization (RTO) problem considering interval uncertainty can be solved by combining orthogonal decomposition with uniform sampling (ODUS). In order to eliminate the influence of numerical units when comparing the optimal results to deterministic and RTO solutions, the relative uncertainty related to interval objective function is employed to characterize the structural robustness. Several multi-material structure optimization cases are provided to demonstrate the feasibility and efficiency of the proposed method, where the magnitude uncertainty, directional uncertainty, and combined uncertainty are investigated.     

Estimating sample mean under interval uncertainty and constraint on sample variance

Traditionally, practitioners start a statistical analysis of a given sample x₁, … , x_n by computing the sample mean E and the sample variance V. The sample values x_i usually come from measurements. Measurements are never absolutely accurate and often, the only information that we have about the corresponding measurement errors are the upper bounds Δ_i on these errors. In such situations, after obtaining the measurement result , the only information that we have about the actual (unknown) value x_i of the ith quantity is that x_i belongs to the interval . Different values x_i from the corresponding intervals lead, in general, to different values of the sample mean and sample variance. It is therefore desirable to find the range of possible values of these characteristics when x_i ∈ x_i.Often, we know that the values x_i cannot differ too much from each other, i.e., we know the upper bound V₀ on the sample variance V : V ? V₀. It is therefore desirable to find the range of E under this constraint. This is the main problem that we solve in this paper.     

Cooperation under interval uncertainty

In this paper, the classical theory of two-person cooperative games is extended to two-person cooperative games with interval uncertainty. The core, balancedness, superadditivity and related topics are studied. Solutions called ψ ^α-values are introduced and characterizations are given.     

Approximate solutions to convex optimization problems under stochastic uncertainty

In this paper, we survey two standard philosophies for finding minimizing solutions of convex objective functions affected by uncertainty. In a first approach, the solution should minimize the expected value of the objective w.r.t. uncertainty (average approach), while in a second one it should minimize the worst-case objective (worst-case, or min-max approach). Both approaches are however numerically hard to solve exactly, for general dependence of the cost function on the uncertain data. Here, a brief account is given on two techniques based on uncertainty randomization that permit to solve efficiently some suitable probabilistic relaxation of the indicated problems, with full generality with respect to the way in which the uncertainty enters the problem data. A specific application to uncertain least-squares problems is examined. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Robust solutions for network design under transportation cost and demand uncertainty

In many applications, the network design problem (NDP) faces significant uncertainty in transportation costs and demand, as it can be difficult to estimate current (and future values) of these quantities. In this paper, we present a robust optimization-based formulation for the NDP under transportation cost and demand uncertainty. We show that solving an approximation to this robust formulation of the NDP can be done efficiently for a network with single origin and destination per commodity and general uncertainty in transportation costs and demand that are independent of each other. For a network with path constraints, we propose an efficient column generation procedure to solve the linear programming relaxation. We also present computational results that show that the approximate robust solution found provides significant savings in the worst case while incurring only minor sub-optimality for specific instances of the uncertainty.     

Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint

In this paper, we consider the problem of minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that under a mild assumption, this problem can be solved by solving a linearly constrained convex univariate minimization problem. Finally, the superior efficiency of the new approach compared to the known semidefinite relaxation and a known approach from the literature is demonstrated by solving several randomly generated test problems.     

Robust risk-taking under a sustainable constraint

We consider a model in which the representative investor makes optimal portfolio and consumption choices robust to ambiguity with a sustainable constraint. We find that the influences of ambiguity on risk-taking are two ways. Those are gambling when the risk-free interest rate is less than a critical value, but derisk when the risk-free interest rate is greater than the critical value. Moreover, the erosion of ambiguity on consumption is more substantial in constrained cases, and ambiguity will magnify welfare losses.     

Robust combinatorial optimization with variable cost uncertainty

We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates better Value-at-Risk objective functions, especially for vectors with few non-zero components. An example of budget function is constructed from the probabilistic bounds computed by Bertsimas and Sim. We provide an asymptotically tight bound for the cost reduction obtained with the new model. We turn then to the tractability of the resulting optimization problems. We show that when the budget function is affine, the resulting optimization problems can be solved by solving n+1$n+1$ deterministic problems. We propose combinatorial algorithms to handle problems with more general budget functions. We also adapt existing dynamic programming algorithms to solve faster the robust counterparts of optimization problems, which can be applied both to the traditional budgeted uncertainty model and to our new model. We evaluate numerically the reduction in the price of robustness obtained with the new model on the shortest path problem and on a survivable network design problem.     

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

Robust solutions and risk measures for a supply chain planning problem under uncertainty

We consider a strategic supply chain planning problem formulated as a two-stage stochastic integer programming (SIP) model. The strategic decisions include site locations, choices of production, packing and distribution lines, and the capacity increment or decrement policies. The SIP model provides a practical representation of real-world discrete resource allocation problems in the presence of future uncertainties which arise due to changes in the business and economic environment. Such models that consider the future scenarios (along with their respective probabilities) not only identify optimal plans for each scenario, but also determine a hedged strategy for all the scenarios. We

1. 1)
   exploit the natural decomposable structure of the SIP problem through Benders’ decomposition,
    
2. 2)
   approximate the probability distribution of the random variables using the generalized lambda distribution, and
    
3. 3)
   through simulations, calculate the performance statistics and the risk measures for the two models, namely the expected-value and the here-and-now.
    

     

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.     

Robust optimization in spline regression models for multi-model regulatory networks under polyhedral uncertainty

In our study, we integrate the data uncertainty of real-world models into our regulatory systems and robustify them. We newly introduce and analyse robust time-discrete target–environment regulatory systems under polyhedral uncertainty through robust optimization. Robust optimization has reached a great importance as a modelling framework for immunizing against parametric uncertainties and the integration of uncertain data is of considerable importance for the model’s reliability of a highly interconnected system. Then, we present a numerical example to demonstrate the efficiency of our new robust regression method for regulatory networks. The results indicate that our approach can successfully approximate the target–environment interaction, based on the expression values of all targets and environmental factors.     

Solving linear optimization over arithmetic constraint formula

Since Balas extended the classical linear programming problem to the disjunctive programming (DP) problem where the constraints are combinations of both logic AND and OR, many researchers explored this optimization problem under various theoretical or application scenarios such as generalized disjunctive programming (GDP), optimization modulo theories (OMT), robot path planning, real-time systems, etc. However, the possibility of combining these differently-described but form-equivalent problems into a single expression remains overlooked. The contribution of this paper is two folded. First, we convert the linear DP/GDP model, linear-arithmetic OMT problem and related application problems into an equivalent form, referred to as the linear optimization over arithmetic constraint formula (LOACF). Second, a tree-search-based algorithm named RS-LPT is proposed to solve LOACF. RS-LPT exploits the techniques of interval analysis and nonparametric estimation for reducing the search tree and lowering the number of visited nodes. Also, RS-LPT alleviates bad construction of search tree by backtracking and pruning dynamically. We evaluate RS-LPT against two most common DP/GDP methods, three state-of-the-art OMT solvers and the disjunctive transformation based method on optimization benchmarks with different types and scales. Our results favor RS-LPT as compared to existing competing methods, especially for large scale cases.     

A robust algorithm for quadratic optimization under quadratic constraints

Most existing methods of quadratically constrained quadratic optimization actually solve a refined linear or convex relaxation of the original problem. It turned out, however, that such an approach may sometimes provide an infeasible solution which cannot be accepted as an approximate optimal solution in any reasonable sense. To overcome these limitations a new approach is proposed that guarantees a more appropriate approximate optimal solution which is also stable under small perturbations of the constraints.     

Robust hierarchical production planning under uncertainty

We consider aggregation of products with similar characteristics in a two-level hierarchical production planning model. A robust aggregate plan at the upper level is such that, at the lower level, a disaggregation policy exists even when detailed demands may vary within some given bounds. We provide necessary and sufficient conditions for the robustness of an aggregate plan and obtain a closed form expression of these conditions. A set of more manageable sufficient conditions is also presented.Institut National des Sciences Appliquées de Toulouse.     

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.     

Generalized linear fractional programming under interval uncertainty

Data in many real-life engineering and economical problems suffer from inexactness. Herein we assume that we are given some intervals in which the data can simultaneously and independently perturb. We consider a generalized linear fractional programming problem with interval data and present an efficient method for computing the range of optimal values. The method reduces the problem to solving from two to four real-valued generalized linear fractional programs, which can be computed in polynomial time using an appropriate interior point method solver.     

Portfolio optimization under shortfall risk constraint

This paper solves a utility maximization problem under utility-based shortfall risk constraint, by proposing an approach using Lagrange multiplier and convex duality. Under mild conditions on the asymptotic elasticity of the utility function and the loss function, we find an optimal wealth process for the constrained problem and characterize the bi-dual relation between the respective value functions of the constrained problem and its dual. This approach applies to both complete and incomplete markets. Moreover, the extension to more complicated cases is illustrated by solving the problem with a consumption process added. Finally, we give an example of utility and loss functions in the Black–Scholes market where the solutions have explicit forms.     

Sparse solutions to random standard quadratic optimization problems

The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In this paper we focus on a special scenario of the StQP where all the elements of the data matrix Q are independently identically distributed and follow a certain distribution such as uniform or exponential distribution. We show that the probability that such a random StQP has a global optimal solution with k nonzero elements decays exponentially in k. Numerical evaluation of our theoretical finding is discussed as well.