串联式多级火箭成本问题初论

本文以火箭最大速度值的一般变化规律为基础, 改进了以前考虑火箭发射的成本问题的常用数学模型：最省的最省推进剂方案, 详细研究了各种情况下串联式多级火箭的成本问题,并以算例验证了所得的新成本计算模型的有效性.     

Analytic approximation and differentiability of joint chance constraints

ABSTRACT

An inner–outer approximation approach was recently developed to solve single chance constrained optimization (SCCOPT) problems. In this paper, we extend this approach to address joint chance constrained optimization (JCCOPT) problems. Using an inner–outer approximation, two smooth parametric optimization problems are defined whose feasible sets converge to the feasible set of JCCOPT from inside and outside, respectively. Any optimal solution of the inner approximation problem is a priori feasible to the JCCOPT. As the approximation parameter tends to zero, a subsequence of the solutions of the inner and outer problems, respectively, converge asymptotically to an optimal solution of the JCCOPT. As a main result, the continuous differentiability of the probability function of a joint chance constraint is obtained by examining the uniform convergence of the gradients of the parametric approximations.     

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.     

A new distributionally robust p-hub median problem with uncertain carbon emissions and its tractable approximation method

The p-hub median problem is to determine the optimal location for p hubs and assign the remaining nodes to hubs so as to minimize the total transportation costs. Under the carbon cap-and-trade policy, we study this problem by addressing the uncertain carbon emissions from the transportation, where the probability distributions of the uncertain carbon emissions are only partially available. A novel distributionally robust optimization model with the ambiguous chance constraint is developed for the uncapacitated single allocation p-hub median problem. The proposed distributionally robust optimization problem is a semi-infinite chance-constrained optimization model, which is computationally intractable for general ambiguity sets. To solve this hard optimization model, we discuss the safe approximation to the ambiguous chance constraint in the following two types of ambiguity sets. The first ambiguity set includes the probability distributions with the bounded perturbations with zero means. In this case, we can turn the ambiguous chance constraint into its computable form based on tractable approximation method. The second ambiguity set is the family of Gaussian perturbations with partial knowledge of expectations and variances. Under this situation, we obtain the deterministic equivalent form of the ambiguous chance constraint. Finally, we validate the proposed optimization model via a case study from Southeast Asia and CAB data set. The numerical experiments indicate that the optimal solutions depend heavily on the distribution information of carbon emissions. In addition, the comparison with the classical robust optimization method shows that the proposed distributionally robust optimization method can avoid over-conservative solutions by incorporating partial probability distribution information. Compared with the stochastic optimization method, the proposed method pays a small price to depict the uncertainty of probability distribution. Compared with the deterministic model, the proposed method generates the new robust optimal solution under uncertain carbon emissions.     

Risk-averse feasible policies for large-scale multistage stochastic linear programs

We develop tractable semidefinite programming based approximations for distributionally robust individual and joint chance constraints, assuming that only the first- and second-order moments as well as the support of the uncertain parameters are given. It is known that robust chance constraints can be conservatively approximated by Worst-Case Conditional Value-at-Risk (CVaR) constraints. We first prove that this approximation is exact for robust individual chance constraints with concave or (not necessarily concave) quadratic constraint functions, and we demonstrate that the Worst-Case CVaR can be computed efficiently for these classes of constraint functions. Next, we study the Worst-Case CVaR approximation for joint chance constraints. This approximation affords intuitive dual interpretations and is provably tighter than two popular benchmark approximations. The tightness depends on a set of scaling parameters, which can be tuned via a sequential convex optimization algorithm. We show that the approximation becomes essentially exact when the scaling parameters are chosen optimally and that the Worst-Case CVaR can be evaluated efficiently if the scaling parameters are kept constant. We evaluate our joint chance constraint approximation in the context of a dynamic water reservoir control problem and numerically demonstrate its superiority over the two benchmark approximations.     

Distributionally robust chance constrained problem under interval distribution information

This paper is concerned with distributionally robust chance constrained problem under interval distribution information. Using worst-case CVaR approximation, we present a tractable convex programming approximation for distributionally robust individual chance constrained problem under interval sets of mean and covariance information. We prove the worst-case CVaR approximation problem is an exact form of the distributionally robust individual chance constrained problem. Then, our result is applied to worst-case Value-at-Risk optimization problem. Moreover, we discuss the problem under several ambiguous distribution information and investigate tractable approximations for distributionally robust joint chance constrained problem. Finally, we provide an illustrative example to show our results.     

Variable-sized uncertainty and inverse problems in robust optimization

In robust optimization, the general aim is to find a solution that performs well over a set of possible parameter outcomes, the so-called uncertainty set. In this paper, we assume that the uncertainty size is not fixed, and instead aim at finding a set of robust solutions that covers all possible uncertainty set outcomes. We refer to these problems as robust optimization with variable-sized uncertainty. We discuss how to construct smallest possible sets of min–max robust solutions and give bounds on their size.A special case of this perspective is to analyze for which uncertainty sets a nominal solution ceases to be a robust solution, which amounts to an inverse robust optimization problem. We consider this problem with a min–max regret objective and present mixed-integer linear programming formulations that can be applied to construct suitable uncertainty sets.Results on both variable-sized uncertainty and inverse problems are further supported with experimental data.     

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.     

Ambiguous chance constrained problems and robust optimization

In this paper we study ambiguous chance constrained problems where the distributions of the random parameters in the problem are themselves uncertain. We focus primarily on the special case where the uncertainty set of the distributions is of the form where ρ_p denotes the Prohorov metric. The ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according to the central measure The main contribution of this paper is to show that the robust sampled problem is a good approximation for the ambiguous chance constrained problem with a high probability. This result is established using the Strassen-Dudley Representation Theorem that states that when the distributions of two random variables are close in the Prohorov metric one can construct a coupling of the random variables such that the samples are close with a high probability. We also show that the robust sampled problem can be solved efficiently both in theory and in practice. Research partially supported by NSF grant CCR-00-09972. Research partially supported by NSF grants CCR-00-09972, DMS-01-04282, and ONR grant N000140310514.     

Data-Driven Robust Chance Constrained Problems: A Mixture Model Approach

This paper discusses the mixture distribution-based data-driven robust chance constrained problem. We construct a data-driven mixture distribution-based uncertainty set from the perspective of simultaneously estimating higher-order moments. Then, we derive a reformulation of the data-driven robust chance constrained problem. As the reformulation is not a convex programming problem, we propose new and tight convex approximations based on the piecewise linear approximation method. We establish the theoretical foundation for these approximations. Finally, numerical results show that the proposed approximations are practical and efficient.     

Robust assortment optimization using worst-case CVaR under the multinomial logit model

We consider robust assortment optimization problems with partial distributional information of parameters in the multinomial logit choice model. The objective is to find an assortment that maximizes a revenue target using a distributionally robust chance constraint, which can be approximated by the worst-case Conditional Value-at-Risk. We show that our problems are equivalent to robust assortment optimization problems over special uncertainty sets of parameters, implying the optimality of revenue-ordered assortments under certain conditions.     

Distributionally robust discrete optimization with Entropic Value-at-Risk

We study the discrete optimization problem under the distributionally robust framework. We optimize the Entropic Value-at-Risk, which is a coherent risk measure and is also known as Bernstein approximation for the chance constraint. We propose an efficient approximation algorithm to resolve the problem via solving a sequence of nominal problems. The computational results show that the number of nominal problems required to be solved is small under various distributional information sets.     

Nonlinear robust optimization via sequential convex bilevel programming

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min–max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min–max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min–max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.     

New product launch decisions with robust optimization

We consider a problem where a company must decide the order in which to launch new products within a given time horizon and budget constraints, and where the parameters of the adoption rate of these new products are subject to uncertainty. This uncertainty can bring significant change to the optimal launch sequence. We present a robust optimization approach that incorporates such uncertainty on the Bass diffusion model for new products as well as on the price response function of partners that collaborate with the company in order to bring its products to market. The decision-maker optimizes his worst-case profit over an uncertainty set where nature chooses the time periods in which (integer) units of the budgets of uncertainty are used for worst impact. This leads to uncertainty sets with binary variables. We show that a conservative approximation of the robust problem can nonetheless be reformulated as a mixed integer linear programming problem, is therefore of the same structure as the deterministic problem and can be solved in a tractable manner. Finally, we illustrate our approach on numerical experiments. Our model also incorporates contracts with potential commercialization partners. The key output of our work is a sequence of product launch times that protects the decision-maker against parameter uncertainty for the adoption rates of the new products and the response of potential partners to partnership offers.     

Quadratic optimization problems in robust beamforming

This paper presents a class of constrained optimization problems whereby a quadratic cost function is to be minimized with respect to a weight vector subject to an inequality quadratic constraint on the weight vector. This class of constrained optimization problems arises as a result of a motivation for designing robust antenna array processors in the field of adaptive array processing. The constrained optimization problem is first solved by using the primal-dual method. Numerical techniques are presented to reduce the computational complexity of determining the optimal Lagrange multiplier and hence the optimal weight vector. Subsequently, a set of linear constraints or at most linear plus norm constraints are developed for approximating the performance achievable with the quadratic constraint. The use of linear constraints is very attractive, since they reduce the computational burden required to determine the optimal weight vector.     

On two-stage convex chance constrained problems

In this paper we develop approximation algorithms for two-stage convex chance constrained problems. Nemirovski and Shapiro (Probab Randomized Methods Des Uncertain 2004) formulated this class of problems and proposed an ellipsoid-like iterative algorithm for the special case where the impact function f (x, h) is bi-affine. We show that this algorithm extends to bi-convex f (x, h) in a fairly straightforward fashion. The complexity of the solution algorithm as well as the quality of its output are functions of the radius r of the largest Euclidean ball that can be inscribed in the polytope defined by a random set of linear inequalities generated by the algorithm (Nemirovski and Shapiro in Probab Randomized Methods Des Uncertain 2004). Since the polytope determining r is random, computing r is difficult. Yet, the solution algorithm requires r as an input. In this paper we provide some guidance for selecting r. We show that the largest value of r is determined by the degree of robust feasibility of the two-stage chance constrained problem—the more robust the problem, the higher one can set the parameter r. Next, we formulate ambiguous two-stage chance constrained problems. In this formulation, the random variables defining the chance constraint are known to have a fixed distribution; however, the decision maker is only able to estimate this distribution to within some error. We construct an algorithm that solves the ambiguous two-stage chance constrained problem when the impact function f (x, h) is bi-affine and the extreme points of a certain “dual” polytope are known explicitly. Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

Level bundle methods for constrained convex optimization with various oracles

We propose restricted memory level bundle methods for minimizing constrained convex nonsmooth optimization problems whose objective and constraint functions are known through oracles (black-boxes) that might provide inexact information. Our approach is general and covers many instances of inexact oracles, such as upper, lower and on-demand accuracy oracles. We show that the proposed level bundle methods are convergent as long as the memory is restricted to at least four well chosen linearizations: two linearizations for the objective function, and two linearizations for the constraints. The proposed methods are particularly suitable for both joint chance-constrained problems and two-stage stochastic programs with risk measure constraints. The approach is assessed on realistic joint constrained energy problems, arising when dealing with robust cascaded-reservoir management.     

Robust ranking and portfolio optimization

The portfolio optimization problem has attracted researchers from many disciplines to resolve the issue of poor out-of-sample performance due to estimation errors in the expected returns. A practical method for portfolio construction is to use assets’ ordering information, expressed in the form of preferences over the stocks, instead of the exact expected returns. Due to the fact that the ranking itself is often described with uncertainty, we introduce a generic robust ranking model and apply it to portfolio optimization. In this problem, there are n objects whose ranking is in a discrete uncertainty set. We want to find a weight vector that maximizes some generic objective function for the worst realization of the ranking. This robust ranking problem is a mixed integer minimax problem and is very difficult to solve in general. To solve this robust ranking problem, we apply the constraint generation method, where constraints are efficiently generated by solving a network flow problem. For empirical tests, we use post-earnings-announcement drifts to obtain ranking uncertainty sets for the stocks in the DJIA index. We demonstrate that our robust portfolios produce smaller risk compared to their non-robust counterparts.     

Adaptive and robust radiation therapy optimization for lung cancer

A previous approach to robust intensity-modulated radiation therapy (IMRT) treatment planning for moving tumors in the lung involves solving a single planning problem before the start of treatment and using the resulting solution in all of the subsequent treatment sessions. In this paper, we develop an adaptive robust optimization approach to IMRT treatment planning for lung cancer, where information gathered in prior treatment sessions is used to update the uncertainty set and guide the reoptimization of the treatment for the next session. Such an approach allows for the estimate of the uncertain effect to improve as the treatment goes on and represents a generalization of existing robust optimization and adaptive radiation therapy methodologies. Our method is computationally tractable, as it involves solving a sequence of linear optimization problems. We present computational results for a lung cancer patient case and show that using our adaptive robust method, it is possible to attain an improvement over the traditional robust approach in both tumor coverage and organ sparing simultaneously. We also prove that under certain conditions our adaptive robust method is asymptotically optimal, which provides insight into the performance observed in our computational study. The essence of our method – solving a sequence of single-stage robust optimization problems, with the uncertainty set updated each time – can potentially be applied to other problems that involve multi-stage decisions to be made under uncertainty.     

Relaxations and approximations of chance constraints under finite distributions

Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulation has a weak relaxation bound and is quite difficult to solve. In this paper, we review some recent results on improving the relaxation bounds and constructing approximate solutions for MILP formulations of chance constraints. We also discuss a recently introduced bicriteria approximation algorithm for covering type chance constrained problems. This algorithm uses a relaxation to construct a solution whose (constraint violation) risk level may be larger than the pre-specified threshold, but is within a constant factor of it, and whose objective value is also within a constant factor of the true optimal value. Finally, we present some new results that improve on the bicriteria approximation factors in the finite scenario setting and shed light on the effect of strong relaxations on the approximation ratios.