Convexity and optimization with copulæ structured probabilistic constraints

Probability constraints play a key role in optimization problems involving uncertainties. These constraints request that an inequality system depending on a random vector has to be satisfied with a high enough probability. In specific settings, copulæ can be used to model the probabilistic constraints with uncertainty on the left-hand side. In this paper, we provide eventual convexity results for the feasible set of decisions under local generalized concavity properties of the constraint mappings and involved copulæ. The results cover all Archimedean copulæ. We consider probabilistic constraints wherein the decision and random vector are separated, i.e. left/right-hand side uncertainty. In order to solve the underlying optimization problem, we propose and analyse convergence of a regularized supporting hyperplane method: a stabilized variant of generalized Benders decomposition. The algorithm is tested on a large set of instances involving several copulæ among which the Gaussian copula. A Numerical comparison with a (pure) supporting hyperplane algorithm and a general purpose solver for non-linear optimization is also presented.     

Convexity of chance constraints with independent random variables

We investigate the convexity of chance constraints with independent random variables. It will be shown, how concavity properties of the mapping related to the decision vector have to be combined with a suitable property of decrease for the marginal densities in order to arrive at convexity of the feasible set for large enough probability levels. It turns out that the required decrease can be verified for most prominent density functions. The results are applied then, to derive convexity of linear chance constraints with normally distributed stochastic coefficients when assuming independence of the rows of the coefficient matrix.     

Properties of Chance Constraints in Infinite Dimensions with an Application to PDE Constrained Optimization

Chance constraints represent a popular tool for finding decisions that enforce the satisfaction of random inequality systems in terms of probability. They are widely used in optimization problems subject to uncertain parameters as they arise in many engineering applications. Most structural results of chance constraints (e.g., closedness, convexity, Lipschitz continuity, differentiability etc.) have been formulated in finite dimensions. The aim of this paper is to generalize some of these well-known semi-continuity and convexity properties as well as a stability result to an infinite dimensional setting. The abstract results are applied to a simple PDE constrained control problem subject to (uniform) state chance constraints.     

Convexity of chance constrained programming problems with respect to a new generalized concavity notion

In this paper, convexity of chance constrained problems have been investigated. A new generalization of convexity concept, named h-concavity, has been introduced and it has been shown that this new concept is the generalization of the ??-concavity. Then, using the new concept, some of the previous results obtained by Shapiro et al. [in Lecture Notes on Stochastic Programming Modeling and Theory, SIAM and MPS, 2009] on properties of ??-concave functions, have been extended. Next the convexity of chance constraints with independent random variables is investigated. It will be shown how concavity properties of the mapping related to the decision vector have to be combined with suitable properties of decrease or increase for the marginal densities in order to arrive at convexity of the feasible set for large enough probability levels and then sufficient conditions for convexity of chance constrained problems which has been introduced by Henrion and Strugarek [in Convexity of chance constraints with independent random variables. Comput. Optim. Appl. 41:263?C276, 2008] has been extended in this paper for a wider class of real functions.     

Convexity of Gaussian chance constraints and of related probability maximization problems

We investigate here conditions for convexity of solutions sets defined by chance constraints, along with conditions for (local) concavity of associated probability functions. Even restricting to the case of coefficient vectors with nondegenerate multivariate Gaussian distributions, only sufficient conditions could be found so far in the literature. In the present paper, a necessary and sufficient condition for local concavity of the probability function for a given individual Gaussian chance constraint is obtained. A sufficient condition for the case of a two-sided (bilateral) chance constraint is also deduced. The results obtained are shown to be useful in the analysis of various (nonconvex) probability maximization problem such as: (a) maximizing the joint probability of satisfaction of several independent Gaussian chance constraints; (b) looking for the best linear discriminant function for two given Gaussian mixtures. Computational experiments are reported for the latter problem.     

Multivalued convexity and optimization: A unified approach to inequality and equality constraints

Multivalued functions satisfying a general convexity condition are examined in the first section. The second section establishes a general transposition theorem for such functions and develops an abstract multiplier principle for them. In particular both convex inequality and linear equality constraints are seen to satisfy the same generalized constraint qualification. The final section examines quasi-convex programmes.     

Nonsmooth Multiobjective Problems and Generalized Vector Variational Inequalities Using Quasi-Efficiency

In this paper, a multiobjective problem with a feasible set defined by inequality, equality and set constraints is considered, where the objective and constraint functions are locally Lipschitz. Here, a generalized Stampacchia vector variational inequality is formulated as a tool to characterize quasi- or weak quasi-efficient points. By using two new classes of generalized convexity functions, under suitable constraint qualifications, the equivalence between Kuhn–Tucker vector critical points, solutions to the multiobjective problem and solutions to the generalized Stampacchia vector variational inequality in both weak and strong forms will be proved.     

A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints

The vehicle routing problem with stochastic demands (VRPSD) consists in designing optimal routes to serve a set of customers with random demands following known probability distributions. Because of demand uncertainty, a vehicle may arrive at a customer without enough capacity to satisfy its demand and may need to apply a recourse to recover the route’s feasibility. Although travel times are assumed to be deterministic, because of eventual recourses the total duration of a route is a random variable. We present two strategies to deal with route-duration constraints in the VRPSD. In the first, the duration constraints are handled as chance constraints, meaning that for each route, the probability of exceeding the maximum duration must be lower than a given threshold. In the second, violations to the duration constraint are penalized in the objective function. To solve the resulting problem, we propose a greedy randomized adaptive search procedure (GRASP) enhanced with heuristic concentration (HC). The GRASP component uses a set of randomized route-first, cluster-second heuristics to generate starting solutions and a variable-neighborhood descent procedure for the local search phase. The HC component assembles the final solution from the set of all routes found in the local optima reached by the GRASP. For each strategy, we discuss extensive computational experiments that analyze the impact of route-duration constraints on the VRPSD. In addition, we report state-of-the-art solutions for a established set of benchmarks for the classical VRPSD.     

Some kind of Pareto stationarity for multiobjective problems with equilibrium constraints

ABSTRACT

In this paper, we derive some optimality and stationarity conditions for a multiobjective problem with equilibrium constraints (MOPEC). In particular, under a generalized Guignard constraint qualification, we show that any locally Pareto optimal solution of MOPEC must satisfy the strong Pareto Kuhn-Tucker optimality conditions. We also prove that the generalized Guignard constraint qualification is the weakest constraint qualification for the strong Pareto Kuhn-Tucker optimality. Furthermore, under certain convexity or generalized convexity assumptions, we show that the strong Pareto Kuhn-Tucker optimality conditions are also sufficient for several popular locally Pareto-type optimality conditions for MOPEC.     

广义凸多目标规划的Mond─Weir型对偶性

本文研究带不等式和等式约束的多目标规划的Ｍｏｎｄ－Ｗｅｉｒ型对偶性理论。在目标和约束是广义凸的假设下，证明了弱对偶定理、直接对偶定理以及逆对偶定理     

广义Minimax不等式及不动点定理

最近,许多作者推广了著名的Ky Fan的minimax不等式.本文提出了T-对角凸凹性条件,发展了这一方面的主要结果.其次,我们讨论了一些不动点问题,推广了Fan-Glicksberg不动点定理.     

GENERALIZED ROSENTHAL'S INEQUALITY FOR BANACH-SPACE-VALUED MARTINGALES

A generalized Rosenthal's inequality for Banach-space-valued martingales is proved, which extends the corresponding results in the previous literatures and character-izes the p-uniform smoothness and q-uniform convexity of the underlying Banach space. As an application of this inequality, the strong law of large numbers for Banach-space-valued martingales is also given.     

Saddle points and gap functions for weak generalized Ky Fan inequalities

In this paper, we employ the image space analysis method to investigate a weak generalized Ky Fan inequality with cone constraints. Some regular weak separation functions are introduced, and generalized Lagrangian functions are constructed by using these regular weak separation functions. Under suitable convexity assumptions and Slater condition, the existence of solution for the weak generalized Ky Fan inequality with cone constraints is equivalent to a saddle point of the generalized Lagrangian functions. Moreover, we also use the regular weak separation functions to construct gap functions for the weak generalized Ky Fan inequality with cone constraints, and obtain its error bound.     

Optimality conditions for nonsmooth mathematical programs with equilibrium constraints,using convexificators

In this paper, we deal with constraint qualifications, stationary concepts and optimality conditions for a nonsmooth mathematical program with equilibrium constraints (MPEC). The main tool in our study is the notion of convexificator. Using this notion, standard and MPEC Abadie and several other constraint qualifications are proposed and a comparison between them is presented. We also define nonsmooth stationary conditions based on the convexificators. In particular, we show that GS-stationary is the first-order optimality condition under generalized standard Abadie constraint qualification. Finally, sufficient conditions for global or local optimality are derived under some MPEC generalized convexity assumptions.     

Optimization with multivariate stochastic dominance constraints

We consider stochastic optimization problems where risk-aversion is expressed by a stochastic ordering constraint. The constraint requires that a random vector depending on our decisions stochastically dominates a given benchmark random vector. We identify a suitable multivariate stochastic order and describe its generator in terms of von Neumann–Morgenstern utility functions. We develop necessary and sufficient conditions of optimality and duality relations for optimization problems with this constraint. Assuming convexity we show that the Lagrange multipliers corresponding to dominance constraints are elements of the generator of this order, thus refining and generalizing earlier results for optimization under univariate stochastic dominance constraints. Furthermore, we obtain necessary conditions of optimality for non-convex problems under additional smoothness assumptions.     

Optimality conditions for nonsmooth semi-infinite multiobjective programming

This paper is devoted to the study of nonsmooth multiobjective semi-infinite programming problems in which the index set of the inequality constraints is an arbitrary set not necessarily finite. We introduce several kinds of constraint qualifications for these problems, and then necessary optimality conditions for weakly efficient solutions are investigated. Finally by imposing assumptions of generalized convexity we give sufficient conditions for efficient solutions.     

A Linear Approximation for Chance-Constrained Programming

Decision environments involve the need to solve problems with varying degrees of uncertainty as well as multiple, potentially conflicting objectives. Chance constraints consider the uncertainty encountered. Codes incorporating chance constraints into a mathematical programming model are not available on a widespread basis owing to the non-linear form of the chance constraints. Therefore, accurate linear approximations would be useful to analyse this class of problems with efficient linear codes. This paper presents an approximation formula for chance constraints which can be used in either the single- or multiple-objective case. The approximation presented will place a bound on the chance constraint at least as tight as the true non-linear form, thus overachieving the chance constraint at the expense of other constraints or objectives.     

On Extensions of the Frank-Wolfe Theorems

In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we present a comprehensive study of the conditions under which the optimal solution set is nonempty, thus extending the so-called Frank-Wolfe theorem. In particular, we first prove a general continuity result for the solution set defined by a system of convex quadratic inequalities. This result implies immediately that the optimal solution set of the aforementioned problem is nonempty when all the quadratic functions involved are convex. In the absence of the convexity of the objective function, we give examples showing that the optimal solution set may be empty either when there are two or more convex quadratic constraints, or when the Hessian of the objective function has two or more negative eigenvalues. In the case when there exists only one convex quadratic inequality constraint (together with other linear constraints), or when the constraint functions are all convex quadratic and the objective function is quasi-convex (thus allowing one negative eigenvalue in its Hessian matrix), we prove that the optimal solution set is nonempty.     

The simplest proof of Lieb concavity theorem

In this paper, by applying jointly concavity and jointly convexity of generalized perspective of some elementary functions, we give the simplest proof of the well-known Lieb concavity theorem and Ando convexity theorem.     

Optimality and duality in constrained interval-valued optimization

Fritz John and Karush–Kuhn–Tucker necessary conditions for local LU-optimal solutions of the constrained interval-valued optimization problems involving inequality, equality and set constraints in Banach spaces in terms of convexificators are established. Under suitable assumptions on the generalized convexity of objective and constraint functions, sufficient conditions for LU-optimal solutions are given. The dual problems of Mond–Weir and Wolfe types are studied together with weak and strong duality theorems for them.