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.     

Fenchel duality theorem in multiobjective programming problems with set functions

In this paper, we characterize a vector-valued convex set function by its epigraph. The concepts of a vector-valued set function and a vector-valued concave set function are given respectively. The definitions of the conjugate functions for a vector-valued convex set function and a vector-valued concave set function are introduced. Then a Fenchel duality theorem in multiobjective programming problem with set functions is derived.     

带有极值函数的多目标双层规划问题的对偶

For a multiobjective bilevel programming problem(P) with an extremal-value function,its dual problem is constructed by using the Fenchel-Moreau conjugate of the functions involved.Under some convexity and monotonicity assumptions,the weak and strong duality assertions are obtained.     

Linearly constrained convex programming as unconstrained differentiable concave programming

Recently, Fang proposed approximating a linear program in Karmarkar's standard form by adding an entropic barrier function to the objective function and using a certain geometric inequality to transform the resulting problem into an unconstrained differentiable concave program. We show that, by using standard duality theory for convex programming, the results of Fang and his coworkers can be strengthened and extended to linearly constrained convex programs and more general barrier functions.This research was supported by the National Science Foundation, Grant No. CCR-91-03804.     

On duality theory in multiobjective programming

In this paper, we study different vector-valued Lagrangian functions and we develop a duality theory based upon these functions for nonlinear multiobjective programming problems. The saddle-point theorem and the duality theorem are derived for these problems under appropriate convexity assumptions. We also give some relationships between multiobjective optimizations and scalarized problems. A duality theory obtained by using the concept of vector-valued conjugate functions is discussed.The author is grateful to the reviewer for many valuable comments and helpful suggestions.     

一类特殊DC规划的对偶性

根据共轭函数和DC规划的性质，给出一类特殊DC规划的共轭对偶并讨论其对偶规划的特殊性质，然后利用该性质，把对这类特殊DC规划的求解转化为对一个凸规划的求解。     

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.     

Composite geometric programming

Geometric programming is based on functions called posynomials, the terms of which are log-linear. This class of programs is extended from the composition of an exponential and a linear function to an exponential and a convex function. The resulting duality theory for composite geometric programs retains many of the qualities of geometric programming duality, while at the same time encompassing new areas of application. As an application, composite geometric programming is applied to exponential geometric programming. A pure dual is developed for the first time and used to solve a problem from the literature.This research was supported by the Air Force Office of Scientific Research, Grant No. AFOSR-83-0234.     

On Duality for a Class of Quasiconcave Multiplicative Programs

Multiplicative programs are a difficult class of nonconvex programs that have received increasing attention because of their many applications. However, given their nonconvex nature, few theoretical results are available. In this paper, we study a particular case of these programs which involves the maximization of a quasiconcave function over a linear constraint set. Using results from conjugate function theory and generalized geometric programming, we derive a complete duality theory. The results are further specialized to linear multiplicative programming.     

A new geometric condition for Fenchel's duality in infinite dimensional spaces

In 1951, Fenchel discovered a special duality, which relates the minimization of a sum of two convex functions with the maximization of the sum of concave functions, using conjugates. Fenchel's duality is central to the study of constrained optimization. It requires an existence of an interior point of a convex set which often has empty interior in optimization applications. The well known relaxations of this requirement in the literature are again weaker forms of the interior point condition. Avoiding an interior point condition in duality has so far been a difficult problem. However, a non-interior point type condition is essential for the application of Fenchel's duality to optimization. In this paper we solve this problem by presenting a simple geometric condition in terms of the sum of the epigraphs of conjugate functions. We also establish a necessary and sufficient condition for the ε-subdifferential sum formula in terms of the sum of the epigraphs of conjugate functions. Our results offer further insight into Fenchel's duality. Dedicated to Terry Rockafellar on his 70th birthday     

A New Self-Dual Embedding Method for Convex Programming

In this paper we introduce a conic optimization formulation to solve constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for a standard primal-dual path following approach for solving the embedded problem. Moreover, there are two immediate logarithmic barrier functions for the primal and dual cones. We show that these two logarithmic barrier functions are conjugate to each other. The explicit form of the conjugate functions are in fact not required to be known in the algorithm. An advantage of the new approach is that there is no need to assume an initial feasible solution to start with. To guarantee the polynomiality of the path-following procedure, we may apply the self-concordant barrier theory of Nesterov and Nemirovski. For this purpose, as one application, we prove that the barrier functions constructed this way are indeed self-concordant when the original constraint functions are convex and quadratic. We pose as an open question to find general conditions under which the constructed barrier functions are self-concordant.     

Duality and optimality for convex extremal problems described by discrete inclusions

This paper is devoted to the Hamiltonian approach for extremal problems concerning convex (multi-valued) mapping. The approach exploits the concept of a Hamiltonian function permitting simplified proofs and useful mathematical insights. Moreover it provides in a duality framework a common point ox view upon the methods used. by Rockafellar, (the theory of convex processes), Pshenichnyi (the conjugate transformation method) and CASS (the symmetric duality scheme) to construct optimality conditions. The theory is used to develop a complete characterization of optimal solutions for multi-period convex programming problems.     

Stable zero duality gaps in convex programming: Complete dual characterisations with applications to semidefinite programs

The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel's duality.     

一类二层凸规划的对偶二层规划

本文讨论上层目标函数以下层子系统目标函数的最优值作为反馈的一类二层凸规划的对偶规划问题 ,在构成函数满足凸连续可微等条件的假设下 ,建立了二层凸规划的 Lagrange对偶二层规划 ,并证明了基本对偶定理 .     

Multiplicative Programming Problems: Analysis and Efficient Point Search Heuristic

Multiplicative programming problems are difficult global optimization problems known to be NP-hard. At the same time, these problems have some important applications in engineering, finance, economics, and other fields. This article has two purposes. The first is to present an analysis that shows several relationships between concave multiplicative programs and concave minimization problems, and between concave multiplicative programs and certain multiple-objective mathematical programs. The second purpose is to propose and report computational results for a heuristic efficient-point search algorithm that we have designed for use on linear multiplicative programming problems. To our knowledge, this is the first heuristic algorithm of its type. The theoretical and algorithmic results given in the article offer some potentially important new avenues for analyzing and solving multiplicative programming problems of various types.     

一般形式多阶段有补偿问题的广义对偶理论

本文在文［１］的基础上，讨论一般形式多阶段有补偿非线性随机规划问题的广义对偶理论与最优化性条件．通过发掘凸规划对偶理论的本质，首先推广了与通常规划问题对偶理论有关的概念的含义，由此构造出所论问题在等价意义下的广义原始泛函与广义对偶泛函，进而得到其广义对偶理论，所得结论不仅能恰当合理地反映问题本身的属性，而且有关定理的表述形式简明、结论较强，可直接应用于多阶段有补偿问题的其它理论研究与数值求解算法的设计中去．上述结果与所用研究方法均推广和发展了通常的对偶理论     

ON SUFFICIENCY AND DUALITY OF SOLUTIONS FOR QUASI Bs-INVEX SEMI-INFINITE PROGRAMMING

1　IntroductionRecently,various kinds of generalized convex functions were introduced.Bector andSingh[1 ] introduced a class of functions which called B-vex function.Bector,Suneja,andLalitha[2 ] introduced quasi B-vex function,pseudo B-vex function,B-invex function,quasi B-invex function,and pseudo B-invex function.We[3] extended invex function[4] ,gave thedefinitions of the symmetricη-function,symmetricη-pseudoconvex function,symmetricη-quasiconvex function for symmetric differentiable…     

Duality of a Nonconvex Sum of Ratios

For mathematical programs with objective involving a sum of ratios of affine functions, there are few theoretical results due to the nonconvex nature of the program. In this paper, we derive a duality theory for these programs by establishing their connection with geometric programming. This connection allows one to bring to bear the powerful theory and computational algorithms associated with geometric programming.     

Fast value iteration: an application of Legendre-Fenchel duality to a class of deterministic dynamic programming problems in discrete time*

ABSTRACT

We propose an algorithm, which we call ‘Fast Value Iteration’ (FVI), to compute the value function of a deterministic infinite-horizon dynamic programming problem in discrete time. FVI is an efficient algorithm applicable to a class of multidimensional dynamic programming problems with concave return (or convex cost) functions and linear constraints. In this algorithm, a sequence of functions is generated starting from the zero function by repeatedly applying a simple algebraic rule involving the Legendre-Fenchel transform of the return function. The resulting sequence is guaranteed to converge, and the Legendre-Fenchel transform of the limiting function coincides with the value function.     

An unconstrained dual approach to solving Karmarkar-type linear programs using conventional barrier functions

This paper proposes an unconstrained dual approach and an efficient algorithm for solving Karmarkar-type linear programming problems. Conventional barrier functions are incorporated as a perturbation term in the derivation of the associated duality theory. An optimal solution of the original linear program can be obtained by solving a sequence of unconstrained concave programs, or be approximated by solving one such dual program with a sufficiently small perturbation parameter. A globally convergent curved-search algorithm with a quadratic rate of convergence is designed for this purpose. Based on our testing results, we find that the computational procedure is very efficient and can be a viable approach for solving linear programming problems.