A comparison of alternative c-conjugate dual problems in infinite convex optimization

In this work, we obtain a Fenchel–Lagrange dual problem for an infinite dimensional optimization primal one, via perturbational approach and using a conjugation scheme called c-conjugation instead of classical Fenchel conjugation. This scheme is based on the generalized convex conjugation theory. We analyse some inequalities between the optimal values of Fenchel, Lagrange and Fenchel–Lagrange dual problems and we establish sufficient conditions under which they are equal. Examples where such inequalities are strictly fulfilled are provided. Finally, we study the relations between the optimal solutions and the solvability of the three mentioned dual problems.     

Relaxation methods for problems with strictly convex separable costs and linear constraints

We consider the minimization problem with strictly convex, possibly nondifferentiable, separable cost and linear constraints. The dual of this problem is an unconstrained minimization problem with differentiable cost which is well suited for solution by parallel methods based on Gauss-Seidel relaxation. We show that these methods yield the optimal primal solution and, under additional assumptions, an optimal dual solution. To do this it is necessary to extend the classical Gauss-Seidel convergence results because the dual cost may not be strictly convex, and may have unbounded level sets. Work supported by the National Science Foundation under grant NSF-ECS-3217668.     

Some characterizations of robust optimal solutions for uncertain convex optimization problems

In this paper, we consider robust optimal solutions for a convex optimization problem in the face of data uncertainty both in the objective and constraints. By using the properties of the subdifferential sum formulae, we first introduce a robust-type subdifferential constraint qualification, and then obtain some completely characterizations of the robust optimal solution of this uncertain convex optimization problem. We also investigate Wolfe type robust duality between the uncertain convex optimization problem and its uncertain dual problem by proving duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem. Moreover, we show that our results encompass as special cases some optimization problems considered in the recent literature.     

On the generic properties of convex optimization problems in conic form

We prove that strict complementarity, primal and dual nondegeneracy of optimal solutions of convex optimization problems in conic form are generic properties. In this paper, we say generic to mean that the set of data possessing the desired property (or properties) has strictly larger Hausdorff dimension than the set of data that does not. Our proof is elementary and it employs an important result due to Larman [7] on the boundary structure of convex bodies. Received: September 1997 / Accepted: May 2000?Published online November 17, 2000     

A block hybrid method for solving generalized equilibrium problems and convex feasibility problem

A block hybrid projection algorithm for solving the convex feasibility problem and the generalized equilibrium problems for an infinite family of total quasi-?-asymptotically nonexpansive mappings is introduced. Under suitable conditions some strong convergence theorems are established in uniformly smooth and strictly convex Banach spaces with Kadec-Klee property. The results presented in the paper improve and extend some recent results.     

Convex risk functionals: Representation and applications

We introduce the family of law-invariant convex risk functionals, which includes a wide majority of practically used convex risk measures and deviation measures. We obtain a unified representation theorem for this family of functionals. Two related optimization problems are studied. In the first application, we determine worst-case values of a law-invariant convex risk functional when the mean and a higher moment such as the variance of a risk are known. Second, we consider its application in optimal reinsurance design for an insurer. With the help of the representation theorem, we can show the existence and the form of optimal solutions.     

Multistage stochastic convex programs: Duality and its implications

In this paper, we study alternative primal and dual formulations of multistage stochastic convex programs (SP). The alternative dual problems which can be traced to the alternative primal representations, lead to stochastic analogs of standard deterministic constructs such as conjugate functions and Lagrangians. One of the by-products of this approach is that the development does not depend on dynamic programming (DP) type recursive arguments, and is therefore applicable to problems in which the objective function is non-separable (in the DP sense). Moreover, the treatment allows us to handle both continuous and discrete random variables with equal ease. We also investigate properties of the expected value of perfect information (EVPI) within the context of SP, and the connection between EVPI and nonanticipativity of optimal multipliers. Our study reveals that there exist optimal multipliers that are nonanticipative if, and only if, the EVPI is zero. Finally, we provide interpretations of the retroactive nature of the dual multipliers. This work was supported by NSF grant DMII-9414680.     

On Stochastic Mirror-prox Algorithms for Stochastic Cartesian Variational Inequalities: Randomized Block Coordinate and Optimal Averaging Schemes

Motivated by multi-user optimization problems and non-cooperative Nash games in uncertain regimes, we consider stochastic Cartesian variational inequality problems where the set is given as the Cartesian product of a collection of component sets. First, we consider the case where the number of the component sets is large and develop a randomized block stochastic mirror-prox algorithm, where at each iteration only a randomly selected block coordinate of the solution vector is updated through implementing two consecutive projection steps. We show that when the mapping is strictly pseudo-monotone, the algorithm generates a sequence of iterates that converges to the solution of the problem almost surely. When the maps are strongly pseudo-monotone, we prove that the mean-squared error diminishes at the optimal rate. Second, we consider large-scale stochastic optimization problems with convex objectives and develop a new averaging scheme for the randomized block stochastic mirror-prox algorithm. We show that by using a different set of weights than those employed in the classical stochastic mirror-prox methods, the objective values of the averaged sequence converges to the optimal value in the mean sense at an optimal rate. Third, we consider stochastic Cartesian variational inequality problems and develop a stochastic mirror-prox algorithm that employs the new weighted averaging scheme. We show that the expected value of a suitably defined gap function converges to zero at an optimal rate.     

Super-replication and utility maximization in large financial markets

We study the problems of super-replication and utility maximization from terminal wealth in a semimartingale model with countably many assets. After introducing a suitable definition of admissible strategy, we characterize superreplicable contingent claims in terms of martingale measures. Utility maximization problems are then studied with the convex duality method, and we extend finite-dimensional results to this setting. The existence of an optimizer is proved in a suitable class of generalized strategies: this class has also the property that maximal expected utility is the limit of maximal expected utilities in finite-dimensional submarkets. Finally, we illustrate our results with some examples in infinite dimensional factor models.     

New results on affine invariant points

We prove a conjecture of B. Grünbaum stating that the set of affine invariant points of a convex body equals the set of points invariant under all affine linear symmetries of the convex body. As a consequence we give a short proof of the fact that the affine space of affine linear points is infinite dimensional. In particular, we show that the set of affine invariant points with no dual is of the second category. We investigate extremal cases for a class of symmetry measures. We show that the centers of the John and Löwner ellipsoids can be far apart and we give the optimal order for the extremal distance between the two centers.     

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.     

Absolute optimal solution for a compact and convex game

This paper investigates the existence of absolute optimal solutions for a partition P in continuous and quasiconcave games. We show that the P-consistency property introduced in the paper, together with the quasiconcavity and continuity of payoffs, permits the existence of P-absolute optimal solutions in games with compact and convex strategy spaces. The P-consistency property is a general condition that cannot be dispensed with for the existence of P-absolute optimal solutions. We also characterize the existence of P-absolute optimal solutions by providing necessary and sufficient conditions. Moreover, we suggest an algorithm for efficiently computing P-absolute optimal solutions.     

Duality in infinite dimensional linear programming

We consider the class of linear programs with infinitely many variables and constraints having the property that every constraint contains at most finitely many variables while every variable appears in at most finitely many constraints. Examples include production planning and equipment replacement over an infinite horizon. We form the natural dual linear programming problem and prove strong duality under a transversality condition that dual prices are asymptotically zero. That is, we show, under this transversality condition, that optimal solutions are attained in both primal and dual problems and their optimal values are equal. The transversality condition, and hence strong duality, is established for an infinite horizon production planning problem.This material is based on work supported by the National Science Foundation under Grant No. ECS-8700836.     

A new risk criterion in fuzzy environment and its application

Since the observed values of security returns in real-world problems are sometimes imprecise or vague, an increasing effort in research is devoted to study the properties of risk measures in fuzzy portfolio optimization problems. In this paper, a new risk measure is suggested to gauge the risk resulted from fuzzy uncertainty. For this purpose, the absolute deviation and absolute semi-deviation are first defined for fuzzy variable by nonlinear fuzzy integrals. To compute effectively the absolute semi-deviations of single fuzzy variable as well as its functions, this paper discusses the methods of computing the absolute semi-deviation by classical Lebesgue–Stieltjes (L–S) integral. After that, several useful absolute deviation and absolute semi-deviation formulas are established for common triangular, trapezoidal and normal fuzzy variables. Applying the absolute semi-deviation as a new risk measure in portfolio optimization, three classes of fuzzy portfolio optimization models are developed by combining the absolute semi-deviation with expected value operator and credibility measure. Based on the analytical representation of absolute semi-deviations, the established fuzzy portfolio selection models can be turned into their equivalent piecewise linear or fractional programming problems. Since the absolute semi-deviation is a piecewise fractional function and pseudo-convex on the feasible subregions of deterministic programming models, we take advantage of the structural characteristics to design a domain decomposition method to separate a deterministic programming problem into three convex subproblems, which can be solved by conventional solution methods or general-purpose software. Finally, some numerical experiments are performed to demonstrate the new modeling idea and the effectiveness of the solution method.     

Robust duality for generalized convex programming problems under data uncertainty

In this paper we present a robust duality theory for generalized convex programming problems in the face of data uncertainty within the framework of robust optimization. We establish robust strong duality for an uncertain nonlinear programming primal problem and its uncertain Lagrangian dual by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. A robust strong duality theorem is given whenever the Lagrangian function is convex. We provide classes of uncertain non-convex programming problems for which robust strong duality holds under a constraint qualification. In particular, we show that robust strong duality is guaranteed for non-convex quadratic programming problems with a single quadratic constraint with the spectral norm uncertainty under a generalized Slater condition. Numerical examples are given to illustrate the nature of robust duality for uncertain nonlinear programming problems. We further show that robust duality continues to hold under a weakened convexity condition.     

Parametric Disjunctive Programming: One-Sided Differentiability of the Value Function

We consider a countable family of one-parameter convex programs and give sufficient conditions for the one-sided differentiability of its optimal value function. The analysis is based on the Borwein dual problem for a family of convex programs (a convex disjunctive program). We give conditions that assure stability of the situation of perfect duality in the Borwein theory.For the reader's convenience, we start with a review of duality results for families of convex programs. A parametric family of dual problems is introduced that contains the dual problems of Balas and Borwein as special cases. In addition, a vector optimization problem is defined as a dual problem. This generalizes a result by Helbig about families of linear programs.     

A Minimality Property for Entropic Solutions to Scalar Conservation Laws in 1 + 1 Dimensions

The Second Law of Thermodynamics asserts that the physical entropy of an adiabatic system is an increasing function in time. In this paper we will study a more stringent version of this law, according to which entropy should not only increase in time, but the rate of increase is optimal in absolute value among all possible evolutions. We will establish this property in the framework of non-linear scalar hyperbolic conservation law with strictly convex fluxes.     

Convex games with an infinite number of players and sequencing situations

In this paper we study convex games with an infinite countable set of agents and provide characterizations of this class of games. To do so, and in order to overcome some shortcomings related to the difficulty of dealing with infinite orderings, we need to use a continuity property. Infinite sequencing situations where the number of jobs is infinite countable can be related to convex cooperative TU games. It is shown that some allocations turn out to be extreme points of the core of an infinite sequencing game.     

Maximum Lebesgue extension of monotone convex functions

Given a monotone convex function on the space of essentially bounded random variables with the Lebesgue property (order continuity), we consider its extension preserving the Lebesgue property to as big solid vector space of random variables as possible. We show that there exists a maximum such extension, with explicit construction, where the maximum domain of extension is obtained as a (possibly proper) subspace of a natural Orlicz-type space, characterized by a certain uniform integrability property. As an application, we provide a characterization of the Lebesgue property of monotone convex function on arbitrary solid spaces of random variables in terms of uniform integrability and a “nice” dual representation of the function.     

Stochastic Optimal Control and Linear Programming Approach

We study a classical stochastic optimal control problem with constraints and discounted payoff in an infinite horizon setting. The main result of the present paper lies in the fact that this optimal control problem is shown to have the same value as a linear optimization problem stated on some appropriate space of probability measures. This enables one to derive a dual formulation that appears to be strongly connected to the notion of (viscosity sub) solution to a suitable Hamilton-Jacobi-Bellman equation. We also discuss relation with long-time average problems.