Farkas-type results for inequality systems with composed convex functions via conjugate duality

We present some Farkas-type results for inequality systems involving finitely many functions. Therefore we use a conjugate duality approach applied to an optimization problem with a composed convex objective function and convex inequality constraints. Some recently obtained results are rediscovered as special cases of our main result.     

Error bounds for inequality systems defining convex sets

The main goal in this paper is to devise an approach to explicitly calculate the constant in the Hoffman’s error bound for (not necessarily convex) inequality systems defining convex sets. We give a constructive proof of the Hoffman’s error bound and show that we can use our method to calculate the constant at least in simple cases.

     

Error bounds for convex differentiable inequality systems in Banach spaces

The paper is devoted to studying the Hoffman global error bound for convex quadratic/affine inequality/equality systems in the context of Banach spaces. We prove that the global error bound holds if the Hoffman local error bound is satisfied for each subsystem at some point of the solution set of the system under consideration. This result is applied to establishing the equivalence between the Hoffman error bound and the Abadie qualification condition, as well as a general version of Wang &; Pang's result [30], on error bound of Hölderian type. The results in the present paper generalize and unify recent works by Luo &; Luo in [17], Li in [16] and Wang &; Pang in [30].     

Error bound results for generalized D-gap functions of nonsmooth variational inequality problems

Solving a variational inequality problem can be equivalently reformulated into solving a unconstraint optimization problem where the corresponding objective function is called a merit function. An important class of merit function is the generalized D-gap function introduced in [N. Yamashita, K. Taji, M. Fukushima, Unconstrained optimization reformulations of variational inequality problems, J. Optim. Theory Appl. 92 (1997) 439-456] and Yamashita and Fukushima (1997) [17]. In this paper, we present new fractional local/global error bound results for the generalized D-gap functions of nonsmooth variational inequality problems, which gives an effective estimate on the distance between a specific point to the solution set, in terms of the corresponding function value of the generalized D-gap function. Numerical examples and a simple application to the free boundary problem are also presented to illustrate the significance of our error bound results.     

Convergence of duality bound method in partly convex programming

We discuss the convergence of a decomposition branch-and-bound algorithm using Lagrangian duality for partly convex programs in the general form. It is shown that this decomposition algorithm has all convergence properties as any known branch-and-bound algorithm in global optimization under usual assumptions. Thus, some strict assumptions discussed in the literature are avoidable.     

Generalized convex functionals and some duality results

The purpose of this paper is to discuss some generalizations of convex functionals and obtain some applications to optimality and duality     

A simplicial branch and duality bound algorithm for the sum of convex–convex ratios problem

This article presents a simplicial branch and duality bound algorithm for globally solving the sum of convex–convex ratios problem with nonconvex feasible region. To our knowledge, little progress has been made for globally solving this problem so far. The algorithm uses a branch and bound scheme where the Lagrange duality theory is used to obtain the lower bounds. As a result, the lower-bounding subproblems during the algorithm search are all ordinary linear programs that can be solved very efficiently. It has been proved that the algorithm possesses global convergence. Finally, the numerical experiments are given to show the feasibility of the proposed algorithm.     

New strong duality results for convex programs with separable constraints

It is known that convex programming problems with separable inequality constraints do not have duality gaps. However, strong duality may fail for these programs because the dual programs may not attain their maximum. In this paper, we establish conditions characterizing strong duality for convex programs with separable constraints. We also obtain a sub-differential formula characterizing strong duality for convex programs with separable constraints whenever the primal problems attain their minimum. Examples are given to illustrate our results.     

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.     

A note about linear inequality systems and duality

The optimization of a linear function on a closed convex set,F, can be stated as a linear semi-infinite program, sinceF is the solution set of (usually) infinite linear inequality systems, the so-called linear representations ofF. The duality properties of these programs are analyzed when the linear representation ofF ranges in some well known classes of linear inequality systems. This paper provides propositions on the duality diagrams of Farkas-Minkowski, canonically closed, compact and closed systems. Converse statements are also given.

---

Zusammenfassung Die Optimierung einer linearen Funktion auf einer konvexen abgeschlossenen MengeF kann als semi-infinites lineares Programm aufgefaßt werden, daF als Durchschnitt (unendlich) vieler Halbräume dargestellt werden kann. Es werden Dualitätseigenschaften dieser Programme untersucht, wobei von verschiedenen linearen Darstellungen fürF ausgegangen wird. Die Arbeit enthält Sätze über Dualitätsbeziehungen von Farkas-Minkowski, kanonisch abgeschlossene, kompakte und abgeschlossene Systeme. Es werden auch umgekehrte Beziehungen angegeben.

     

Improved convex upper bound via conditional comonotonicity

Comonotonicity provides a convenient convex upper bound for a sum of random variables with arbitrary dependence structure. Improved convex upper bound was introduced via conditioning by Kaas et al. [Kaas, R., Dhaene, J., Goovaerts, M., 2000. Upper and lower bounds for sums of random variables. Insurance: Math. Econ. 27, 151-168]. In this paper, we unify these results in a more general context using the concept of conditional comonotonicity. We also construct an approximating sequence of convex upper bounds with nice convergence properties.     

Multiobjective duality for convex ratios

In this paper we present a duality approach for a multiobjective fractional programming problem. The components of the vector objective function are particular ratios involving the square of a convex function and a positive concave function. Applying the Fenchel-Rockafellar duality theory for a scalar optimization problem associated to the multiobjective primal, a dual problem is derived. This scalar dual problem is formulated in terms of conjugate functions and its structure gives an idea about how to construct a multiobjective dual problem in a natural way. Weak and strong duality assertions are presented.     

Gap functions for generalized vector equilibrium problems via conjugate duality and applications

In this article, gap functions for a generalized vector equilibrium problem (GVEP) with explicit constraints are investigated. Under a concept of supremum/infimum of a set, defined in terms of a closure of the set, three kinds of conjugate dual problems are investigated by considering the different perturbations to GVEP. Then, gap functions for GVEP are established by using the weak and strong duality results. As application, the proposed approach is applied to construct gap functions for a vector optimization problem and a generalized vector variational inequality problem.     

Explicit duality for convex homogeneous programs

When all the functions that define a convex program are positively homogeneous, then a dual convex program can be constructed which is defined in terms of the primal data only (the primal variables do not appear). Furthermore, the dualizing process, carried out on the dual program, yields the primal. Several well-known examples of convex programs with explicit duals are shown to be special cases.This research has been partially supported by the National Science Foundation under Grant GK-23153 and the United States Environmental Protection Agency under Grant R-801870 with the University of California.     

Norm duality for convex processes and applications

One can associate two norms with a Banach space convex process. These norms are dual to each other and the norm of a process agrees with the dual norm of its adjoint. This norm duality provides an extremely general and simple way of establishing surjectivity or boundedness properties of homogeneous (linear or convex) inequality systems.This research was partially supported by the Natural Sciences and Engineering Research Council of Canada.     

On duality for square root convex programs

Conjugate function theory is used to develop dual programs for nonseparable convex programs involving the square root function. This function arises naturally in finance when one measures the risk of a portfolio by its variance–covariance matrix, in stochastic programming under chance constraints and in location theory.     

Voronoi cells via linear inequality systems

The theory and methods of linear algebra are a useful alternative to those of convex geometry in the framework of Voronoi cells and diagrams, which constitute basic tools of computational geometry. As shown by Voigt and Weis in 2010, the Voronoi cells of a given set of sites T, which provide a tesselation of the space called Voronoi diagram when T is finite, are solution sets of linear inequality systems indexed by T. This paper exploits systematically this fact in order to obtain geometrical information on Voronoi cells from sets associated with T (convex and conical hulls, tangent cones and the characteristic cones of their linear representations). The particular cases of T being a curve, a closed convex set and a discrete set are analyzed in detail. We also include conclusions on Voronoi diagrams of arbitrary sets.     

Maximum likelihood estimation via duality for cell probabilities subject to convex and log-convex constraints

This article proposes a method for fitting models subject to a convex and log-convex constraint on the probability vector of a product multinomial （binomial） distribution. We present an iterative algorithm for finding the restricted maximum likelihood estimates （MLEs） of the probability vector and show that the algorithm converges to the true solution. Some examples are discussed to illustrate the method.