Duality gaps in nonconvex stochastic optimization

We consider multistage stochastic optimization models containing nonconvex constraints, e.g., due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes. The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal decomposition. The second group of results concerns large stochastic optimization models with loosely coupled components. The results provide conditions implying relations between the duality gaps of geographical decomposition and the duality gaps for scenario and nodal decomposition, respectively.Mathematics Subject Classification (1991): 90C15Acknowledgments. This work was supported by the Priority Programme Online Optimization of Large Scale Systems of the Deutsche Forschungsgemeinschaft. The authors wish to thank Andrzej Ruszczyski (Rutgers University) for helpful discussions.     

Duality of nonconvex optimization with positively homogeneous functions

We consider an optimization problem with positively homogeneous functions in its objective and constraint functions. Examples of such positively homogeneous functions include the absolute value function and the p-norm function, where p is a positive real number. The problem, which is not necessarily convex, extends the absolute value optimization proposed in Mangasarian (Comput Optim Appl 36:43–53, 2007). In this work, we propose a dual formulation that, differently from the Lagrangian dual approach, has a closed-form and some interesting properties. In particular, we discuss the relation between the Lagrangian duality and the one proposed here, and give some sufficient conditions under which these dual problems coincide. Finally, we show that some well-known problems, e.g., sum of norms optimization and the group Lasso-type optimization problems, can be reformulated as positively homogeneous optimization problems.     

Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid

In this paper a duality framework is discussed for the problem of optimizing a nonconvex quadratic function over an ellipsoid. Additional insight is obtained from the observation that this nonconvex problem is in a sense equivalent to a convex problem of the same type, from which known necessary and sufficient conditions for optimality readily follow. Based on the duality results, some existing solution procedures are interpreted as in fact solving the dual. The duality relations are also shown to provide a natural framework for sensitivity analysis.     

Duality algorithms for nonconvex variational principles

This paper describes, and analyzes, a method of successive approximations for finding critical points of a function which can be written as the difference of two convex functions. The method is based on using a non-convex duality theory. At each iteration one solves a convex, optimization problem. This alternates between the primal and the dual variables. Under very general structural conditions on the problem, we prove that the resulting sequence is a descent sequence, which converges to a critical point of the problem. To illustrate the method, it is applied to some weighted eigenvalue problems, to a problem from astrophysics, and to some semilinear elliptic equations.     

Duality theorems for a class of nonconvex programming problems

The object of this paper is to prove duality theorems for quasiconvex programming problems. The principal tool used is the transformation introduced by Manas for reducing a nonconvex programming problem to a convex programming problem. Duality in the case of linear, quadratic, and linear-fractional programming is a particular case of this general case.The authors are grateful to the referees for their kind suggestions.     

A nonconvex dissipative system and its applications (I)

In order to study the uniformly translating solution of some non-linear evolution equations such as the complex Ginzburg–Landau equation, this paper presents a qualitative analysis to a Duffing–van der Pol non-linear oscillator. Monotonic property of the bounded exact solution is established based on the construction of a convex domain. Under certain parametric choices, one first integral to the Duffing–van der Pol non-linear system is obtained by using the Lie symmetry analysis, which constitutes one of the bases for further work of obtaining uniformly translating solutions of the complex Ginzburg–Landau equation. Dedicated to Professor G. Strang on the occasion of his 70th birthday     

A nonconvex dissipative system and its applications (II)

This paper presents exact solutions in terms of implicit functions and hyperbolic functions to a nonconvex dissipative system, controlled by a Duffing–van der Pol nonlinear equation with a fifth-order nonlinearity. Applications to the complex Ginzburg–Landau equation are illustrated and several classes of uniformly translating solutions are obtained accordingly. Part of the work was announced at the International Conference on Complementarity, Duality, and Global Optimization in Science and Engineering, Virginia Tech. University, Blacksburg, Virginia, August 15–17, 2005. This work is supported by NSF Grant CCF–0514768.     

A hybrid stochastic optimization framework for composite nonconvex optimization

Mathematical Programming - We introduce a new approach to develop stochastic optimization algorithms for a class of stochastic composite and possibly nonconvex optimization problems. The main idea...     

On nonconvex optimization problems with separated nonconvex variables

A mathematical programming problem is said to have separated nonconvex variables when the variables can be divided into two groups: x=(x ₁,...,x _n ) and y=( y ₁,...,y _n ), such that the objective function and any constraint function is a sum of a convex function of (x, y) jointly and a nonconvex function of x alone. A method is proposed for solving a class of such problems which includes Lipschitz optimization, reverse convex programming problems and also more general nonconvex optimization problems.     

The Aizenberg formula in nonconvex domains and some of its applications

The paper concerns the operator determined by the kernel of the Aizenberg integral representation for holomorphic functions. A special class of domains such that this operator acts from C^a ( ?W ) {C^\alpha }\left( {\partial \Omega } \right) to H^a ( W) {H^\alpha }\left( \Omega \right) is introduced. An example of a nonconvex domain that belongs to this class described. Bibliography: 4 titles.     

Duality and Lipschitzian selections in best approximation from nonconvex cones

Duality relationships in finding a best approximation from a nonconvex cone in a normed linear space in general and in the space of bounded functions in particular, are investigated. The cone and the dual problems are defined in terms of positively homogeneous super-additive functional on the space. Conditions are developed on the cone so that the duality gap between a pair of primal and dual problems does not exist. In addition, Lipschitz continuous selections of the metric projection are identified. The results are specialized to a convex cone. Applications are indicated to approximation problems.     

Duality for nonconvex absolute value programming and a characterization of linear max-min programs

In this paper a dual problem for nonconvex linear programs with absolute value functionals is constructed by means of a max-min problem involving bivalent variables. A relationship between the classical linear max-min problem and a linear program with absolute value functionals is developed. This program is then used to compute the duality gap between some max-min and min-max linear problems.     

Duality for unbounded order convergence and applications

Unbounded order convergence has lately been systematically studied as a generalization of almost everywhere convergence to the abstract setting of vector and Banach lattices. This paper presents a duality theory for unbounded order convergence. We define the unbounded order dual (or uo-dual) \({X_{uo}^\sim }\) of a Banach lattice X and identify it as the order continuous part of the order continuous dual \({X_n^\sim }\). The result allows us to characterize the Banach lattices that have order continuous preduals and to show that an order continuous predual is unique when it exists. Applications to the Fenchel–Moreau duality theory of convex functionals are given. The applications are of interest in the theory of risk measures in Mathematical Finance.     

The exact penalty map for nonsmooth and nonconvex optimization

Augmented Lagrangian duality provides zero duality gap and saddle point properties for nonconvex optimization. On the basis of this duality, subgradient-like methods can be applied to the (convex) dual of the original problem. These methods usually recover the optimal value of the problem, but may fail to provide a primal solution. We prove that the recovery of a primal solution by such methods can be characterized in terms of (i) the differentiability properties of the dual function and (ii) the exact penalty properties of the primal-dual pair. We also connect the property of finite termination with exact penalty properties of the dual pair. In order to establish these facts, we associate the primal-dual pair to a penalty map. This map, which we introduce here, is a convex and globally Lipschitz function and its epigraph encapsulates information on both primal and dual solution sets.     

Convexification procedures and decomposition methods for nonconvex optimization problems

In order for primal-dual methods to be applicable to a constrained minimization problem, it is necessary that restrictive convexity conditions are satisfied. In this paper, we consider a procedure by means of which a nonconvex problem is convexified and transformed into one which can be solved with the aid of primal-dual methods. Under this transformation, separability of the type necessary for application of decomposition algorithms is preserved. This feature extends the range of applicability of such algorithms to nonconvex problems. Relations with multiplier methods are explored with the aid of a local version of the notion of a conjugate convex function.This work was carried out at the Coordinated Science Laboratory, University of Illinois, Urbana, Illinois, and was supported by the National Science Foundation under Grant ENG 74-19332.     

Duality theorems for perturbed convex optimization

We show that if F, X are two locally convex spaces and $\text{h: F →}\text{R}\text{?}\text{, ?: F × X → R}$ are two convex functionals satisfying h(y) = ?(y, x₀) (y?F) for some x₀?X, then, under suitable assumptions, the computation of inf h(F) can be reduced to the computation of inf ?(H) on certain hyperplanes H of F × X. We give some applications.     

Separation theorems for nonconvex sets and application in optimization

The aim of this paper is to present separation theorems for two disjoint closed sets, without convexity condition. First, a separation theorem for a given closed cone and a point outside from this cone, is proved and then it is used to prove a separation theorem for two disjoint sets. Illustrative examples are provided to highlight the important aspects of these theorems. An application to optimization is also presented to prove optimality condition for a nonconvex optimization problem.