Explore the vast range of titles available.

Distributionally robust optimization is a paradigm for decision making under uncertainty where the uncertain problem data are governed by a probability distribution that is itself subject to uncertainty. The distribution is then assumed to belong to an ambiguity set comprising all distributions that are compatible with the decision maker’s prior information. In this paper, we propose a unifying framework for modeling and solving distributionally robust optimization problems. We introduce standardized ambiguity sets that contain all distributions with prescribed conic representable confidence sets and with mean values residing on an affine manifold. These ambiguity sets are highly expressive and encompass many ambiguity sets from the recent literature as special cases. They also allow us to characterize distributional families in terms of several classical and/or robust statistical indicators that have not yet been studied in the context of robust optimization. We determine conditions under which distributionally robust optimization problems based on our standardized ambiguity sets are computationally tractable. We also provide tractable conservative approximations for problems that violate these conditions.

A homogeneous interior-point algorithm for solving nonsymmetric convex conic optimization problems is presented. Starting each iteration from the vicinity of the central path, the method steps in the approximate tangent direction and then applies a correction phase to locate the next well-centered primal–dual point. Features of the algorithm include that it makes use only of the primal barrier function, that it is able to detect infeasibilities in the problem and that no phase-I method is needed. We prove convergence to ϵ -accuracy in O ( ν log ( 1 / ϵ ) ) iterations. To improve performance, the algorithm employs a new Runge–Kutta type second order search direction suitable for the general nonsymmetric conic problem. Moreover, quasi-Newton updating is used to reduce the number of factorizations needed, implemented so that data sparsity can still be exploited. Extensive and promising computational results are presented for the p -cone problem, the facility location problem, entropy maximization problems and geometric programs; all formulated as nonsymmetric convex conic optimization problems.

Recently, Bomze et al. introduced a sparse conic relaxation of the scenario problem of a two stage stochastic version of the standard quadratic optimization problem. When compared numerically to Burer’s classical reformulation, the authors showed that there seems to be almost no difference in terms of solution quality, whereas the solution time can differ by orders of magnitudes. While the authors did find a very limited special case, for which Burer’s reformulation and their relaxation are equivalent, no satisfying explanation for the high quality of their bound was given. This article aims at shedding more light on this phenomenon and give a more thorough theoretical account of its inner workings. We argue that the quality of the outer approximation cannot be explained by traditional results on sparse conic relaxations based on positive semidenifnite or completely positive matrix completion, which require certain sparsity patterns characterized by chordal and block clique graphs respectively, and put certain restrictions on the type of conic constraint they seek to sparsify. In an effort to develop an alternative approach, we will provide a new type of convex reformulation of a large class of stochastic quadratically constrained quadratic optimization problems that is similar to Burer’s reformulation, but lifts the variables into a comparatively lower dimensional space. The reformulation rests on a generalization of the set-completely positive matrix cone. This cone can then be approximated via inner and outer approximations in order to obtain upper and lower bounds, which potentially close the optimality gap, and hence can give a certificate of exactness for these sparse reformulations outside of traditional, known sufficient conditions. Finally, we provide some numerical experiments, where we asses the quality of the inner and outer approximations, thereby showing that the approximations may indeed close the optimality gap in interesting cases.

We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing redundant disjunctions and normalization. Using these DCs, we propose a branch-and-cut algorithm for the problem class we study, and a cutting-plane method for the problem variant with only binary variables. We present an extensive computational study on a diverse set of instances, including instances with binary and with integer variables, and instances with a single and with multiple linking constraints. Our computational study demonstrates that the proposed enhancements of our solution approaches are effective for improving the performance. Moreover, both of our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our binary instances.

This paper explores the potential of (nonlinear) conic constraints to tighten the relaxations of spatial branch-and-bound algorithms. More precisely, we contribute to the literature on the use of conic optimization for the efficient solution, to global optimality, of nonconvex polynomial optimization problems. Taking as baseline an RLT-based algorithm, we present different families of well-known conic-driven constraints: linear SDP-cuts, second-order cone constraints, and SDP constraints. We integrate these constraints in the baseline algorithm and present a thorough computational study to assess their performance, both with respect to each other and with respect to the standard RLT relaxations for polynomial optimization problems. Our main finding is that the different variants of nonlinear constraints (second-order cone and semidefinite) are the best performing ones in around 50 % of the instances in widely used test sets. Additionally, we discuss how one can benefit from the use of machine learning to decide on the most suitable constraints to add to a given instance. The computational results show that the machine learning approach significantly outperforms each of the individual approaches.

Semidefinite programming (SDP) problems typically utilize a constraint of the form X⪰xxT to obtain a convex relaxation of the condition X=xxT, where x∈Rn. In this paper, we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xxT. This branching technique is related to previous work of Saxeena et al. (Math Prog Ser B 124:383–411, 2010, https://doi.org/10.1007/s10107-010-0371-9) who used such an eigenvector to derive a disjunctive cut. We obtain excellent computational results applying the new branching technique to difficult instances of the two-trust-region subproblem.

In this paper we consider finding an approximate second-order stationary point (SOSP) of general nonconvex conic optimization that minimizes a twice differentiable function subject to nonlinear equality constraints and also a convex conic constraint. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier-augmented Lagrangian method for finding an approximate SOSP of this problem. Under some mild assumptions, we show that our method enjoys a total inner iteration complexity of O ~ ( ϵ - 11 / 2 ) and an operation complexity of O ~ ( ϵ - 11 / 2 min { n , ϵ - 5 / 4 } ) for finding an ( ϵ , ϵ ) -SOSP of general nonconvex conic optimization with high probability. Moreover, under a constraint qualification, these complexity bounds are improved to O ~ ( ϵ - 7 / 2 ) and O ~ ( ϵ - 7 / 2 min { n , ϵ - 3 / 4 } ) , respectively. To the best of our knowledge, this is the first study on the complexity of finding an approximate SOSP of general nonconvex conic optimization. Preliminary numerical results are presented to demonstrate superiority of the proposed method over first-order methods in terms of solution quality.

We consider linear programs with uncertain parameters, lying in some prescribed uncertainty set, where part of the variables must be determined before the realization of the uncertain parameters (nonadjustable variables), while the other part are variables that can be chosen after the realization (adjustable variables). We extend the Robust Optimization methodology ([1, 36, 9, 13, 14]) to this situation by introducing the Adjustable Robust Counterpart (ARC) associated with an LP of the above structure. Often the ARC is significantly less conservative than the usual Robust Counterpart (RC), however, in most cases the ARC is computationally intractable (NP-hard). This difficulty is addressed by restricting the adjustable variables to be affine functions of the uncertain data. The ensuing Affinely Adjustable Robust Counterpart (AARC) problem is then shown to be, in certain important cases, equivalent to a tractable optimization problem (typically an LP or a Semidefinite problem), and in other cases, having a tight approximation which is tractable. The AARC approach is illustrated by applying it to a multi-stage inventory management problem. [PUBLICATION ABSTRACT]

In this paper, we consider a data-driven distributionally robust two-stage stochastic linear optimization problem over 1-Wasserstein ball centered at a discrete empirical distribution. Differently from the traditional two-stage stochastic programming which involves the expected recourse function as the preference criterion and hence is risk-neutral, we take the conditional value-at-risk (CVaR) as the risk measure in order to model its effects on decision making problems. We mainly explore tractable reformulations for the proposed robust two-stage stochastic programming with mean-CVaR criterion by analyzing the first case where uncertainties are only in the objective function and then the second case where uncertainties are only in the constraints. We demonstrate that the first model can be exactly reformulated as a deterministic convex programming. Furthermore, it is shown that under several different support sets, the resulting convex optimization problems can be converted into computationally tractable conic programmings. Besides, the second model is generally NP-hard since checking constraint feasibility can be reduced to a norm maximization problem over a polytope. However, even with the case of uncertainty in constraints, tractable conic reformulations can be established when the extreme points of the polytope are known. Finally, we present numerical results to discuss how to control the risk for the best decisions and illustrate the computational effectiveness and superiority of the proposed models.

This paper studies the optimization of the joint selective maintenance and repairperson assignment problem when the quality of maintenance actions is uncertain, thus leading to uncertain post-maintenance reliability of system components. This situation is common in practice since maintenance actions are never perfect and are affected by several factors such as the qualification and the degree of expertise of the repairpersons, the maintenance methods and tools used, and naturally occurring operating environment variability. Using a robust optimization framework, the maintenance quality uncertainty is captured via non-symmetric budget uncertainty sets that enable the level of decision-maker conservatism to be controlled. Both the nominal (i.e., deterministic) and robust problems are reformulated as mixed-integer exponential conic programs that can be solved using currently available solvers. Extensive numerical experiments on benchmark instances show the favorable computational performance of the proposed reformulations and the value of considering maintenance quality uncertainty when developing selective maintenance plans.