Global saddle-point duality for quasi-concave programs,II

A saddle-point duality is proposed for the quasi-concave non-differentiable case of the maximization of the minimum between a finite number of functions. This class of problems contains quasi-concave (convex) programs that are known to be irreducible to convex ones. With the aid of the saddle-point duality involving conjugate-like operators, a Lagrangian is presented, the saddle-points of which give the exact global solutions. A few particular cases are discussed, among them the Von Neumann economic model and discrete rational approximation.     

A convex-like duality scheme for quasi-convex programs

This paper describes a symmetric duality relation for quasi-convex programs. We are able to strengthen previous results and to define necessary and sufficient conditions for the absence of duality gap. In the present scheme one can generate quasi-convex quasi-concave Lagrangians and discuss the correspondence between saddle points of the Lagrangians and the solutions to the dual and primal programs. The present scheme is very similar to Rockafellar's scheme for convex programs and in this sense it may be viewed as a unified approach. Several examples are also given.     

Proximal level bundle methods for convex nondifferentiable optimization,saddle-point problems and variational inequalities

We study proximal level methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. We show that they enjoy almost optimal efficiency estimates. We give extensions for solving convex constrained problems, convex-concave saddle-point problems and variational inequalities with monotone operators. We present several variants, establish their efficiency estimates, and discuss possible implementations. In particular, our methods require bounded storage in contrast to the original level methods of Lemaréchal, Nemirovskii and Nesterov.This research was supported by the Polish Academy of Sciences.Supported by a grant from the French Ministry of Research and Technology.     

Output learning and duality in joint production programs

Summary Output learning is incorporated into a short-run static cost-minimizing model of the multiproduct, multifactor firm which employs a fixed-coefficients technology. The firm's output processes or activities are ultimately specified as functions of the activity variables themselves, thus rentering a generalization to a concave program. A Lagrange dual formulation is then used to obtain the indirect cost objective. Given that this optimal cost function is differentiable and satisfies a regularity condition, its price derivatives serve as input demand functions while its derivatives with respect to the minimum output requirements yield a set of (implicit) marginal costs or dual variables.     

Duality theorems for certain programs involving minimum or maximum operations

The relation of two mathematical programs—the so-called primal, (P) and dual, (D)—Are studied when (P) is a maximization of the minimum of two functions and (D) is the minimization of the maximum of two functions, and the function-pair of (D) are derived by certain, conjugate-like operators from that of (P). It is demonstrated that the weak duality holds when at least one of the pair is continuous. When further premises are met the strong duality is proved. From these results the usual Fenchel-duality may be deducted as well as few other primal-dual pairs.     

Optimality conditions and duality in multiple objective programming involving semilocally convex and related functions

A nonlinear multiple objective programming problem is considered where the functions involved are nondifferentiable. By considering the concept of weak minima, the Fritz John type and Karush-Kuhn- Tucker type necessary optimality conditions and Wolfe and Mond-Weir type duality results are given in terms of the right differentials of the functions. The duality results are stated by using the concepts of generalized semilocally convex functions     

Perfect duality for convexlike programs

The minimizing problem for a convex program has a dual problem, that is, the maximizing problem of the Lagrangian. Although these problems have a duality gap in general, the duality gap can be eliminated by relaxing the constraint of the minimizing problem, so that the constraint is enforced only in the limit. We extend this result to the convexlike case. Moreover, we obtain a necessary condition for optimality for minimizing problems whose objective function and constraint mapping have convex Gateaux derivative.The authors are indebted to Professor W. Takahashi of Tokyo Institute of Technology for his valuable comments, and also to the referees for their helpful suggestions.     

Optimality conditions for nondifferentiable convex semi-infinite programming

This paper gives characterizations of optimal solutions to the nondifferentiable convex semi-infinite programming problem, which involve the notion of Lagrangian saddlepoint. With the aim of giving the necessary conditions for optimality, local and global constraint qualifications are established. These constraint qualifications are based on the property of Farkas-Minkowski, which plays an important role in relation to certain systems obtained by linearizing the feasible set. It is proved that Slater's qualification implies those qualifications.     

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.     

Convex approximations to sparse PCA via Lagrangian duality

We derive a convex relaxation for cardinality constrained Principal Component Analysis (PCA) by using a simple representation of the L₁ unit ball and standard Lagrangian duality. The resulting convex dual bound is an unconstrained minimization of the sum of two nonsmooth convex functions. Applying a partial smoothing technique reduces the objective to the sum of a smooth and nonsmooth convex function for which an efficient first order algorithm can be applied. Numerical experiments demonstrate its potential.     

Equivalence between a generalized fenchel duality theorem and a saddle-point theorem for fractional programs

The convex case of a fractional program is considered. By the aid of a duality theory for mathematical programming involving a maximum and minimum operator, and by defining new operators, we obtain three equivalent duality theorems for three pairs of primal-dual programs. The second and the third one are the saddle-point theorem and a generalized Fenchel duality theorem, respectively.     

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.     

Some relationships between lagrangian and surrogate duality in integer programming

Lagrangian dual approaches have been employed successfully in a number of integer programming situations to provide bounds for branch-and-bound procedures. This paper investigates some relationship between bounds obtained from lagrangian duals and those derived from the lesser known, but theoretically more powerful surrogate duals. A generalization of Geoffrion's integrality property, some complementary slackness relationships between optimal solutions, and some empirical results are presented and used to argue for the relative value of surrogate duals in integer programming. These and other results are then shown to lead naturally to a two-phase algorithm which optimizes first the computationally easier lagrangian dual and then the surrogate dual.     

Pseudo duality in mathematical programming: Unconstrained problems and problems with equality constraints

In this work non-convex programs are analyzed via Legendre transform. The first part includes definitions and the classification of programs that can be handled by the transformation. It is shown that differentiable functions that are represented as a sum of strictly concave and convex functions belong to this class. Conditions under which a function may have such representation are given. Pseudo duality is defined and the pseudo duality theorem for non linear programs with equality constraints is proved.The techniques described are constructive ones, and they enable tocalculate explicitly a pseudo dual once the primal program is given. Several examples are included. In the convex case these techniques enable the explicit calculation of the dual even in cases where direct calculation was not possible.     

Efficient group cuts for integer programs

Gomory's group relaxation for integer programs has been refined by column generation methods and dual ascent algorithms to identify a set of candidate solutions which are feasible in the relaxation but not necessarily so in the original integer program. Attempts at avoiding branch and bound procedures at this point have focussed on providing extra group constraints which eliminate all or most of the candidate solutions so that further ascent can take place. It will be shown that a single constraint usually of order 2 or 3, can eliminate all of the candidate solutions.     

An economic interpretation of stochastic programs

The purpose of this note is to interpret a class of stochastic programming problems in economic terms. The primal stochastic program is shown to represent a certain production program of an entrepreneur. The dual program, which is also a stochastic program, represents the problem of a contractor who desires to purchase the entrepreneur's resources and sell product back to him.     

Generalization of some duality theorems in nonlinear programming

Pseudoconvexity of a function on one set with respect to some other set is defined and duality theorems are proved for nonlinear programming problems by assuming a certain kind of convexity property for a particular linear combination of functions involved in the problem rather than assuming the convexity property for the individual functions as is usually done. This approach generalizes some of the well-known duality theorems and gives some additional strict converse duality theorems which are not comparable with the earlier duality results of this type. Further it is shown that the duality theory for nonlinear fractional programming problems follows as a particular case of the results established here.     

On optimizing functions which are defined in part by an approximation process

This paper studies an optimization problem in which the objective function can not be completely given in closed form. In particular, we assume that some part of the objective function must be computed by an approximation process. This paper develops a technique for solving a class of such problems. Examples demonstrating the technique and problem areas in which it has been successfully applied are also given.     

Duality for quasi-concave programs with explicit constraints

The idea of duality is now well established in the theory of concave programming. The basis of this duality is the concave conjugate transform. This has been exemplified in the development of generalised geometric programming. Much of the current research in duality theory is focused on relaxing the requirement of concavity. Here we develop a duality theory for mathematical programs with a quasi concave objective function and explicit quasi concave constraints. Generalisations of the concave conjugate transform are introduced which pair quasi concave functions as the concave conjugate transform does for concave functions. Optimality conditions are derived relating the primal quasi concave program to its dual. This duality theory was motivated by and has implications in certain problems of mathematical economics. An application to economics is given.     

A duality theorem for semi-infinite convex programs and their finite subprograms

In this paper, we first establish a general recession condition under which a semi-infinite convex program and its formal lagrangian dual have the same value. We go on to show that, under this condition, the following hold. First, every finite subprogram, with ‘enough’ of the given constraints, has the same value as its Lagrangian dual. Second, the weak value of the primal program is equal to the optimal value of the primal. The first draft of this work, entitled ‘Asymptotic Convex Programming’ was completed while the author was a member of the Department of Mathematical Sciences at the University of Delaware, Newark, DE 19711.