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.     

Robust optimization approximation for joint chance constrained optimization problem

Chance constraint is widely used for modeling solution reliability in optimization problems with uncertainty. Due to the difficulties in checking the feasibility of the probabilistic constraint and the non-convexity of the feasible region, chance constrained problems are generally solved through approximations. Joint chance constrained problem enforces that several constraints are satisfied simultaneously and it is more complicated than individual chance constrained problem. This work investigates the tractable robust optimization approximation framework for solving the joint chance constrained problem. Various robust counterpart optimization formulations are derived based on different types of uncertainty set. To improve the quality of robust optimization approximation, a two-layer algorithm is proposed. The inner layer optimizes over the size of the uncertainty set, and the outer layer optimizes over the parameter t which is used for the indicator function upper bounding. Numerical studies demonstrate that the proposed method can lead to solutions close to the true solution of a joint chance constrained problem.     

Eventual convexity of chance constrained feasible sets

In decision-making problems where uncertainty plays a key role and decisions have to be taken prior to observing uncertainty, chance constraints are a strong modelling tool for defining safety of decisions. These constraints request that a random inequality system depending on a decision vector has to be satisfied with a high probability. The characteristics of the feasible set of such chance constraints depend on the constraint mapping of the random inequality system, the underlying law of uncertainty and the probability level. One characteristic of particular interest is convexity. Convexity can be shown under fairly general conditions on the underlying law of uncertainty and on the constraint mapping, regardless of the probability-level. In some situations, convexity can only be shown when the probability-level is high enough. This is defined as eventual convexity. In this paper, we will investigate further how eventual convexity can be assured for specially structured chance constraints involving Copulae. The Copulae have to exhibit generalized concavity properties. In particular, we will extend recent results and exhibit a clear link between the generalized concavity properties of the various mappings involved in the chance constraint for the result to hold. Various examples show the strength of the provided generalization.     

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.     

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.     

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.     

Lagrangian duality of concave minimization subject to linear constraints and an additional facial reverse convex constraint

This paper is concerned with the global optimization problem of minimizing a concave function subject to linear constraints and an additional facial reverse convex constraint. Here, the feasible set is the union of some faces of the polyhedron determined by the linear constraints. Several well-known mathematical problems can be written or transformed into the form considered. The paper addresses the Lagrangian duality of the problem. It is shown that, under slight assumptions, the duality gap can be closed with a finite dual multiplier. Finite methods based on solving concave minimization problems are also proposed. We deal with the advantages accrued when outer approximation, cutting plane, or branch-and-bound methods are used for solving these subproblems.This research was supported in part by the Hungarian National Research Foundation, Grant OTKA 2568. The author wishes to thank the Associate Editor and the referees for their valuable comments.     

Solving non-linear portfolio optimization problems with the primal-dual interior point method

Stochastic programming is recognized as a powerful tool to help decision making under uncertainty in financial planning. The deterministic equivalent formulations of these stochastic programs have huge dimensions even for moderate numbers of assets, time stages and scenarios per time stage. So far models treated by mathematical programming approaches have been limited to simple linear or quadratic models due to the inability of currently available solvers to solve NLP problems of typical sizes. However stochastic programming problems are highly structured. The key to the efficient solution of such problems is therefore the ability to exploit their structure. Interior point methods are well-suited to the solution of very large non-linear optimization problems. In this paper we exploit this feature and show how portfolio optimization problems with sizes measured in millions of constraints and decision variables, featuring constraints on semi-variance, skewness or non-linear utility functions in the objective, can be solved with the state-of-the-art solver.     

Solving mixed-integer robust optimization problems with interval uncertainty using Benders decomposition

Uncertainty and integer variables often exist together in economics and engineering design problems. The goal of robust optimization problems is to find an optimal solution that has acceptable sensitivity with respect to uncertain factors. Including integer variables with or without uncertainty can lead to formulations that are computationally expensive to solve. Previous approaches for robust optimization problems under interval uncertainty involve nested optimization or are not applicable to mixed-integer problems where the objective or constraint functions are neither quadratic, nor linear. The overall objective in this paper is to present an efficient robust optimization method that does not contain nested optimization and is applicable to mixed-integer problems with quasiconvex constraints (? type) and convex objective funtion. The proposed method is applied to a variety of numerical examples to test its applicability and numerical evidence is provided for convergence in general as well as some theoretical results for problems with linear constraints.     

Construction of Test Problems for Concave Minimization Under Linear and Nonlinear Constraints

This paper presents a method for constructing test problems with known global solutions for concave minimization under linear constraints with an additional convex constraint and for reverse convex programs with an additional convex constraint. The importance of such a construction can be realized from the fact that the well known d.c. programming problem can be formulated in this form. Then, the method is further extended to generate test problems with more than one convex constraint, tight or untight at the global solution.     

An outcome space approach for generalized convex multiplicative programs

This paper addresses the problem of minimizing an arbitrary finite sum of products of two convex functions over a convex set. Nonconvex problems in this form constitute a class of generalized convex multiplicative problems. Convex analysis results allow to reformulate the problem as an indefinite quadratic problem with infinitely many linear constraints. Special properties of the quadratic problem combined with an adequate outer approximation procedure for handling its semi-infinite constrained set enable an efficient constraint enumeration global optimization algorithm for generalized convex multiplicative programs. Computational experiences illustrate the proposed approach.     

Optimization of chance constraint programming with sum-of-fractional objectives – An application to assembled printed circuit board problem

This paper presents a procedure to solve a chance constraint programming problem with sum-of-fractional objectives. The problem and the solution procedure are described with the help of a practical problem – assembled printed circuit boards (PCBs). Errors occurring during assembling PCBs are in general classified into three kinds, viz. machine errors, manual errors and other errors. These errors may lead to the rejection of the major portion of the production and hence result the manufacturer a huge loss. The problem is decomposed to have two objective functions; one is a sum-of-fractional objectives and the other is a non-linear objective with bounded constraints. The interest is to maximize the sum-of-fractional objectives and to minimize the non-linear objective, subject to stochastic and non-stochastic bounded environment. The first problem deals with the maximization of the profit (maximizing sum-of-fractional objectives) and the second deals with the minimization of the loss (errors), so as to obtain the maximum profit after removing the number of defective PCBs.     

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.     

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.     

A majorization–minimization algorithm for split feasibility problems

The classical multi-set split feasibility problem seeks a point in the intersection of finitely many closed convex domain constraints, whose image under a linear mapping also lies in the intersection of finitely many closed convex range constraints. Split feasibility generalizes important inverse problems including convex feasibility, linear complementarity, and regression with constraint sets. When a feasible point does not exist, solution methods that proceed by minimizing a proximity function can be used to obtain optimal approximate solutions to the problem. We present an extension of the proximity function approach that generalizes the linear split feasibility problem to allow for non-linear mappings. Our algorithm is based on the principle of majorization–minimization, is amenable to quasi-Newton acceleration, and comes complete with convergence guarantees under mild assumptions. Furthermore, we show that the Euclidean norm appearing in the proximity function of the non-linear split feasibility problem can be replaced by arbitrary Bregman divergences. We explore several examples illustrating the merits of non-linear formulations over the linear case, with a focus on optimization for intensity-modulated radiation therapy.     

ℓ1-Minimization with Magnitude Constraints in the Frequency Domain

In this paper, we study the -optimal control problem with additional constraints on the magnitude of the closed-loop frequency response. In particular, we study the case of magnitude constraints at fixed frequency points (a finite number of such constraints can be used to approximate an -norm constraint). In previous work, we have shown that the primal-dual formulation for this problem has no duality gap and both primal and dual problems are equivalent to convex, possibly infinite-dimensional, optimization problems with LMI constraints. Here, we study the effect of approximating the convex magnitude constraints with a finite number of linear constraints and provide a bound on the accuracy of the approximation. The resulting problems are linear programs. In the one-block case, both primal and dual programs are semi-infinite dimensional. The optimal cost can be approximated, arbitrarily well from above and within any predefined accuracy from below, by the solutions of finite-dimensional linear programs. In the multiblock case, the approximate LP problem (as well as the exact LMI problem) is infinite-dimensional in both the variables and the constraints. We show that the standard finite-dimensional approximation method, based on approximating the dual linear programming problem by sequences of finite-support problems, may fail to converge to the optimal cost of the infinite-dimensional problem.     

Smooth boundary integration method in a linear two-dimensional problem of incompressible fluid and solid

This paper presents a new application of a theoretical and computational method of smooth boundary integration which belongs to the methods of boundary integral equations. Smooth integration is not a method of approximation. In its final analytical form, a smooth-kernel integral equation is computerized easily and accurately.

Smooth integration is associated with a “pressure-vorticity” formulation which covers linear problems in elasticity and fluid mechanics. The solution presented herein is essentially the same as that reported in an earlier paper for regular elasticity. The constraint of incompressibility does not cause difficulties in the pressure-vorticity formulation.

The linear fluid mechanics problem formulated and solved in this paper covers Stokes' problem of a slow viscous flow, and has a wider interpretation. The translational inertia forces are incorporated in the linear problem, as in Euler's dynamic theory of inviscid flow. The centrifugal inertia forces are left for the non-linear problem. The linear problem is perceived as a step in solution of the non-linear problems.     

Neuro-fuzzy based constraint programming

Constraint programming models appear in many sciences including mathematics, engineering and physics. These problems aim at optimizing a cost function joint with some constraints. Fuzzy constraint programming has been developed for treating uncertainty in the setting of optimization problems with vague constraints. In this paper, a new method is presented into creation fuzzy concept for set of constraints. Unlike to existing methods, instead of constraints with fuzzy inequalities or fuzzy coefficients or fuzzy numbers, vague nature of constraints set is modeled using learning scheme with adaptive neural-fuzzy inference system (ANFIS). In the proposed approach, constraints are not limited to differentiability, continuity, linearity; also the importance degree of each constraint can be easily applied. Unsatisfaction of each weighted constraint reduces membership of certainty for set of constraints. Monte-Carlo simulations are used for generating feature vector samples and outputs for construction of necessary data for ANFIS. The experimental results show the ability of the proposed approach for modeling constrains and solving parametric programming problems.     

Stochastic programming problems with generalized integrated chance constraints

If the constraints in an optimization problem are dependent on a random parameter, we would like to ensure that they are fulfilled with a high level of reliability. The most natural way is to employ chance constraints. However, the resulting problem is very hard to solve. We propose an alternative formulation of stochastic programs using penalty functions. The expectations of penalties can be left as constraints leading to generalized integrated chance constraints, or incorporated into the objective as a penalty term. We show that the penalty problems are asymptotically equivalent under quite mild conditions. We discuss applications of sample-approximation techniques to the problems with generalized integrated chance constraints and propose rates of convergence for the set of feasible solutions. We will direct our attention to the case when the set of feasible solutions is finite, which can appear in integer programming. The results are then extended to the bounded sets with continuous variables. Additional binary variables are necessary to solve sample-approximated chance-constrained problems, leading to a large mixed-integer non-linear program. On the other hand, the problems with penalties can be solved without adding binary variables; just continuous variables are necessary to model the penalties. The introduced approaches are applied to the blending problem leading to comparably reliable solutions.