On various duality theorems in nonlinear programming

Recently, Gulati and Craven and Mond and Egudo established strict converse duality theorems for some of Mond-Weir duals for nonlinear programming problems. Here, we establish various duality theorems under weaker convexity conditions that are different from those of Gulati and Craven, Mond and Weir, and Mond and Egudo.The first author is thankful to the Natural Science and Engineering Research Council of Canada for financial support through Grant A-5319.     

A new class of alternative theorems for SOS-convex inequalities and robust optimization

In this paper, we present a new class of alternative theorems for SOS-convex inequality systems without any qualifications. This class of theorems provides an alternative equations in terms of sums of squares to the solvability of the given inequality system. A strong separation theorem for convex sets, described by convex polynomial inequalities, plays a key role in establishing the class of alternative theorems. Consequently, we show that the optimal values of various classes of robust convex optimization problems are equal to the optimal values of related semidefinite programming problems (SDPs) and so, the value of the robust problem can be found by solving a single SDP. The class of problems includes programs with SOS-convex polynomials under data uncertainty in the objective function such as uncertain quadratically constrained quadratic programs. The SOS-convexity is a computationally tractable relaxation of convexity for a real polynomial. We also provide an application of our theorem of the alternative to a multi-objective convex optimization under data uncertainty.     

Duality and saddle-point type optimality for generalized nonlinear fractional programming

In this paper, we establish two theorems of alternative with generalized subconvexlikeness. We introduce two dual models for a generalized fractional programming problem. Theorems of alternative are then applied to establish duality theorems and a saddle-point type optimality condition.     

Convexlike and concavelike conditions in alternative,minimax, and minimization theorems

Convexlike and concavelike conditions are of interest for extensions of the Von Neumann minimax theorem. Since the beginning of the 80's, these conditions also play a certain role in deriving generalized alternative theorems of the Gordan, Motzkin, and Farkas type and Lagrange multiplier results for constrained minimization problems.In this paper, we study various known convexlike conditions for vector-valued functions on a set and investigate convexlike and concavelike conditions for real-valued functions on a product setC×D, where we are mainly interested in the relationships between these conditions. At the end of the paper, we point out several conclusions from our results for the above-mentioned mathematical fields.The author is indebted to Dr. R. Reemtsen and Dr. V. Jeyakumar for their helpful comments during the preparations of this paper.     

Theorems of the alternative and optimality conditions

Several corrections to Ref. 1 are pointed out.     

Optimization of design tolerances using nonlinear programming

A possible mathematical formulation of the practical problem of computer-aided design of electrical circuits (for example) and systems and engineering designs in general, subject to tolerances onk independent parameters, is proposed. An automated scheme is suggested, starting from arbitrary initial acceptable or unacceptable designs and culminating in designs which, under reasonable restrictions, are acceptable in the worst-case sense. It is proved, in particular, that, if the region of points in the parameter space for which designs are both feasible and acceptable satisfies a certain condition (less restrictive than convexity), then no more than 2 ^k points, the vertices of the tolerance region, need to be considered during optimization.This paper was presented at the 6th Annual Princeton Conference on Information Sciences and Systems, Princeton, New Jersey, 1972. The author has benefitted from practical discussions with J. F. Pinel and K. A. Roberts of Bell-Northern Research. V. K. Jha programmed some numerical examples connected with this work. C. Charalambous, P. C. Liu, and N. D. Markettos have made helpful suggestions. The work was supported by Grant No. A-7239 from the National Research Council of Canada.     

On alternative theorems and necessary conditions for efficiency

In this article, we establish theorems of the alternative for a system described by inequalities, equalities and a set inclusion, which are generalizations of Tucker's classical theorem of the alternative, and develop Kuhn–Tucker necessary conditions for efficiency to mathematical programs in normed linear spaces involving inequality, equality and set constraints with positive Lagrange multipliers of all the components of objective functions.     

Generalized arcwise-connected functions and characterizations of local-global minimum properties

In this paper, new classes of generalized convex functions are introduced, extending the concepts of quasi-convexity, pseudoconvexity, and their associate subclasses. Functions belonging to these classes satisfy certain local-global minimum properties. Conversely, it is shown that, under some mild regularity conditions, functions for which the local-global minimum properties hold must belong to one of the classes of functions introduced.Dedicated to R. BellmanThe authors are indebted to I. Kozma, N. Megiddo, and A. Tamir for valuable discussions and to S. Schaible for valuable remarks. This research was partially supported by the Fund for the Encouragement of Research at the Technion.     

Mixed symmetric duality in non-differentiable multiobjective mathematical programming

Two mixed symmetric dual models for a class of non-differentiable multiobjective nonlinear programming problems with multiple arguments are introduced in this paper. These two mixed symmetric dual models unify the four existing multiobjective symmetric dual models in the literature. Weak and strong duality theorems are established for these models under some mild assumptions of generalized convexity. Several special cases are also obtained.     

Theorems of the alternative for multifunctions with applications to optimization: General results

Theorems of the alternative and separation theorems have been shown to be very useful concepts in constrained extremum problems (see, for instance, Refs. 1–12). Their use has stressed the concept of image of a constrained extremum problem, which has turned out to be a powerful and promising tool for investigating the main aspects of optimization (see Refs. 13 and 19). It should be pointed out that, in this approach, a finite-dimensional image problem can be associated to the given extremum problem, even if this is infinite-dimensional and provided that its constraints are expressed by functionals. Such a development can be carried on by means of theorems of the alternative for systems of single-valued functions.In this paper, theorems of the alternative for systems of multifunctions are studied, some general properties are stated, and connections with known results investigated. It is shown how the present approach can be used to analyze extremum problems, where the image of the domain of the constraining functions belongs to a functional space. Such a development will be carried on in a subsequent paper.Useful discussions with O. Ferrero and C. Zlinescu are gratefully acknowledged.     

Theorems on the representation of nonlinear mapping families and implicit function theorems

We derive a result on local representations of a nonlinear mapping family in a neighborhood of a 2-regular singularity. Theorems of this kind are special forms of implicit function theorems and contain many very important results of local nonlinear analysis. Translated fromMatematicheskie Zametki, Vol. 67, No. 1, pp. 57–68, January, 2000.     

Polyhedral functions and multiparametric linear programming

In a linear programming problem with a vector parameter appearing on the right-hand side, the minimum value of the objective is a polyhedral function of this parameter. We show how different characterizations of a polyhedral function correspond to different ways of solving the right-hand side multiparameteric linear programming problem.     

Current state of the art of algorithms and computer software for geometric programming

This paper attempts to consolidate over 15 years of attempts at designing algorithms for geometric programming (GP) and its extensions. The pitfalls encountered when solving GP problems and some proposed remedies are discussed in detail. A comprehensive summary of published software for the solution of GP problems is included. Also included is a numerical comparison of some of the more promising recently developed computer codes for geometric programming on a specially chosen set of GP test problems. The relative performance of these codes is measured in terms of their robustness as well as speed of computation. The performance of some general nonlinear programming (NLP) codes on the same set of test problems is also given and compared with the results for the GP codes. The paper concludes with some suggestions for future research.An earlier version of this paper was presented at the ORSA/TIMS Conference, Chicago, 1975.This work was supported in part by the National Research Council of Canada, Grant No. A-3552, Canada Council Grant No. S74-0418, and a research grant from the School of Organization and Management, Yale University. The author wishes to thank D. Himmelblau, T. Jefferson, M. Rijckaert, X. M. Martens, A. Templeman, J. J. Dinkel, G. Kochenberger, M. Ratner, L. Lasdon, and A. Jain for their cooperation in making the comparative study possible.     

KKT conditions for weak compact convex sets,theorems of the alternative,and optimality conditions

We present several equivalent conditions for the Karush–Kuhn–Tucker conditions for weak^? compact convex sets. Using them, we extend several existing theorems of the alternative in terms of weak^? compact convex sets. Such extensions allow us to express the KKT conditions and hence necessary optimality conditions for more general nonsmooth optimization problems with inequality and equality constraints. Furthermore, several new equivalent optimality conditions for optimization problems with inequality constraints are obtained.     

Theorems of the alternative and optimality conditions

A theorem of the alternative is stated for generalized systems. It is shown how to deduce, from such a theorem, known optimality conditions like saddle-point conditions, regularity conditions, known theorems of the alternative, and new ones. Exterior and interior penalty approaches, weak and strong duality are viewed as weak and strong alternative, respectively.     

Reductions of interval nonlinear programming problem

A general nonlinear programming problem with interval functions is considered. Two reductions of this problem to the deterministic nonlinear programming problem are proposed, and illustrative examples are discussed.     

Optimality conditions using sum-convex approximations

The purpose of this paper is to give necessary and sufficient conditions of optimality for a general mathematical programming problem, using not a linear approximation to the constraint function but an approximation possessing certain convexity properties. Such approximations are called sum-convex. Theorems of the alternative involving sum-convex functions are also presented as part of the proof.This work is part of the author's PhD Thesis under the supervision of Professor S. Zlobec at McGill University.     

An exact duality theory for semidefinite programming and its complexity implications

In this paper, an exact dual is derived for Semidefinite Programming (SDP), for which strong duality properties hold without any regularity assumptions. Its main features are: (i) The new dual is an explicit semidefinite program with polynomially many variables and polynomial size coefficient bitlengths. (ii) If the primal is feasible, then it is bounded if and only if the dual is feasible. (iii) When the primal is feasible and bounded, then its optimum value equals that of the dual, or in other words, there is no duality gap. Further, the dual attains this common optimum value. (iv) It yields a precise theorem of the alternative for semidefinite inequality systems, i.e. a characterization of theinfeasibility of a semidefinite inequality in terms of thefeasibility of another polynomial size semidefinite inequality. The standard duality for linear programming satisfies all of the above features, but no such explicit gap-free dual program of polynomial size was previously known for SDP, without Slater-like conditions being assumed. The dual is then applied to derive certain complexity results for SDP. The decision problem of Semidefinite Feasibility (SDFP), which asks to determine if a given semidefinite inequality system is feasible, is the central problem of interest, he complexity of SDFP is unknown, but we show the following: (i) In the Turing machine model, the membership or nonmembership of SDFP in NP and Co-NP is simultaneous; hence SDFP is not NP-Complete unless NP=Co-NP. (ii) In the real number model of Blum, Shub and Smale, SDFP is in NP∩CoNP.