On the sufficiency of finite support duals in semi-infinite linear programming

We consider semi-infinite linear programs with countably many constraints indexed by the natural numbers. When the constraint space is the vector space of all real valued sequences, we show that the finite support (Haar) dual is equivalent to the algebraic Lagrangian dual of the linear program. This settles a question left open by Anderson and Nash (1987). This result implies that if there is a duality gap between the primal linear program and its finite support dual, then this duality gap cannot be closed by considering the larger space of dual variables that define the algebraic Lagrangian dual. However, if the constraint space corresponds to certain subspaces of all real-valued sequences, there may be a strictly positive duality gap with the finite support dual, but a zero duality gap with the algebraic Lagrangian dual.     

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.     

Convex analysis treated by linear programming

The theme of this paper is the application of linear analysis to simplify and extend convex analysis. The central problem treated is the standard convex program — minimize a convex function subject to inequality constraints on other convex functions. The present approach uses the support planes of the constraint region to transform the convex program into an equivalent linear program. Then the duality theory of infinite linear programming shows how to construct a new dual program of bilinear type. When this dual program is transformed back into the convex function formulation it concerns the minimax of an unconstrained Lagrange function. This result is somewhat similar to the Kuhn—Tucker theorem. However, no constraint qualifications are needed and yet perfect duality maintains between the primal and dual programs.Work prepared under Research Grant DA-AROD-31-124-71-G17, Army Research Office (Durham).     

Controlled perturbations for quadratically constrained quadratic programs

Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains that are essentially linear. However, the objective function is not differentiable over the constraint region. In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this controlled perturbation scheme.     

On fractional programming containing support functions

Optimality conditions are derived for a nonlinear fractional program in which a support function appears in the numerator and denominator of the objective function as well as in each constraint function. As an application of these optimality conditions, a dual to this program is formulated and various duality results are established under generalized convexity. Several known results are deduced as special cases.     

Geometric programming problems with negative degrees of difficulty

This paper proposes two methods to solve posynomial geometric programs with negative degrees of difficulty of lower integral values. Such a case arises when a primal program has a number of variables equal or slightly greater than the number of terms. In this specific case the normality and the orthogonality conditions of the dual geometric program give a system of linear equations, where the number of linear equations is greater than the number of dual variables. No general solution vector exists for this system of linear equations. Either the least square or linear programming method can be applied to get an approximate solution vector for this system. Then the optimum value of the dual objective function can be obtained from the approximate solution vector.     

Strong duality for robust minimax fractional programming problems

We develop a duality theory for minimax fractional programming problems in the face of data uncertainty both in the objective and constraints. Following the framework of robust optimization, we establish strong duality between the robust counterpart of an uncertain minimax convex–concave fractional program, termed as robust minimax fractional program, and the optimistic counterpart of its uncertain conventional dual program, called optimistic dual. In the case of a robust minimax linear fractional program with scenario uncertainty in the numerator of the objective function, we show that the optimistic dual is a simple linear program when the constraint uncertainty is expressed as bounded intervals. We also show that the dual can be reformulated as a second-order cone programming problem when the constraint uncertainty is given by ellipsoids. In these cases, the optimistic dual problems are computationally tractable and their solutions can be validated in polynomial time. We further show that, for robust minimax linear fractional programs with interval uncertainty, the conventional dual of its robust counterpart and the optimistic dual are equivalent.     

The continuity of the optimum in parametric programming and applications to stochastic programming

It is proved a sufficient condition that the optimal value of a linear program be a continuous function of the coefficients. The condition isessential, in the sense that, if it is not imposed, then examples with discontinuous optimal-value function may be found. It is shown that certain classes of linear programs important in applications satisfy this condition. Using the relation between parametric linear programming and the distribution problem in stochastic programming, a necessary and sufficient condition is given that such a program has optimal value. Stable stochastic linear programs are introduced, and a sufficient condition of such stability, important in computation problems, is established.This note is a slightly modified version of a paper presented at the Institute of Econometrics and Operations Research of the University of Bonn, Bonn, Germany, 1972.The author is grateful to G. B. Dantzig and S. Karamardian for useful comments on an earlier draft of this paper. In particular, S. Karamardian proposed modifications which made clearer the proof of Lemma 2.1.     

Mixed-integer quadratic programming

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a suitable approach for solving such programs. However, the program does not become more tractable if this method is used, since Benders' cuts are quadratic in the integer variables. A new equivalent formulation that renders the program tractable is developed, under which the dual objective function is linear in the integer variables and the dual constraint set is independent of these variables. Benders' cuts that are derived from the new formulation are linear in the integer variables, and the original problem is decomposed into a series of integer linear master problems and standard quadratic subproblems. The new formulation does not introduce new primary variables or new constraints into the computational steps of the decomposition algorithm.The author wishes to thank two anonymous referees for their helpful comments and suggestions for revising the paper.     

Deriving an unconstrained convex program for linear programming

Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.This work was partially supported by the North Carolina Supercomputing Center and a 1990 Cray Research Grant. The authors are indebted to Professors E. L. Peterson and R. Saigal for stimulating discussions.     

A new approach to fuzzy programming

A fuzzy program is defined in the usual way as a sequence of statements (instruction) which are considered as functions (possibly fuzzy functions) and fuzzy predicates defined on the given input domain. The essential difference in the approach presented in this paper is the new interpretation of the execution of fuzzy programs, and a new method of evaluating fuzzy predicates. The result of the fuzzy program execution is an appropriate fuzzy subset in the output domain.     

Least-norm linear programming solution as an unconstrained minimization problem

It is shown that the dual of the problem of minimizing the 2-norm of the primal and dual optimal variables and slacks of a linear program can be transformed into an unconstrained minimization of a convex parameter-free globally differentiable piecewise quadratic function with a Lipschitz continuous gradient. If the slacks are not included in the norm minimization, one obtains a minimization problem with a convex parameter-free quadratic objective function subject to nonnegativity constraints only.     

Ergodic,primal convergence in dual subgradient schemes for convex programming,II: the case of inconsistent primal problems

Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal–dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which—in the inconsistent case—the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional \(\varepsilon \)-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal–dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved.     

Duality inequalities as a numerical aid

This note re-examines the problem of estimating the minimum value of a convex program. To obtain a lower bound to this value a dual program is formulated. The dual involves only explicitly given functions and only inequality constraints. No nonlinear equality constraints appear. Thus a numerically feasible algorithm is obtained.     

Characterizations of the Solution Sets of Convex Programs and Variational Inequality Problems

For a convex program in a normed vector space with the objective function admitting the Gateaux derivative at an optimal solution, we show that the solution set consists of the feasible points lying in the hyperplane whose normal vector equals the Gateaux derivative. For a general continuous convex program, a feasible point is an optimal solution iff it lies in a hyperplane with a normal vector belonging to the subdifferential of the objective function at this point. In several cases, the solution set of a variational inequality problem is shown to coincide with the solution set of a convex program with its dual gap function as objective function, while the mapping involved can be used to express the above normal vectors.The research was supported by the National Science Council of the Republic of China. The authors are grateful to the referees for valuable comments and constructive suggestions.     

On duality in linear fractional programming

In this paper, a dual of a given linear fractional program is defined and the weak, direct and converse duality theorems are proved. Both the primal and the dual are linear fractional programs. This duality theory leads to necessary and sufficient conditions for the optimality of a given feasible solution. A unmerical example is presented to illustrate the theory in this connection. The equivalence of Charnes and Cooper dual and Dinkelbach’s parametric dual of a linear fractional program is also established.     

Convex quadratic programming with one constraint and bounded variables

In this paper we propose an iterative algorithm for solving a convex quadratic program with one equality constraint and bounded variables. At each iteration, a separable convex quadratic program with the same constraint set is solved. Two variants are analyzed: one that uses an exact line search, and the other a unit step size. Preliminary testing suggests that this approach is efficient for problems with diagonally dominant matrices. This work was supported by a research grant from the France-Quebec exchange program and also by NSERC Grant No. A8312. The first author was supported by a scholarship from Transport Canada while doing this research.     

Duality in nonlinear fractional programming

Summary The purpose of the present paper is to introduce, on the lines similar to that ofWolfe [1961], a dual program to a nonlinear fractional program in which the objective function, being the ratio of a convex function to a strictly positive linear function, is a special type of pseudo-convex function and the constraint set is a convex set constrained by convex functions in the form of inequalities. The main results proved are, (i) Weak duality theorem, (ii)Wolfe's (Direct) duality theorem and (iii)Mangasarian's Strict Converse duality theorem.Huard's [1963] andHanson's [1961] converse duality theorems for the present problem have just been stated because they can be obtained as a special case ofMangasarian's theorem [1969, p. 157]. The other important discussion included is to show that the dual program introduced in the present paper can also be obtained throughDinkelbach's Parametric Replacement [1967] of a nonlinear fractional program. Lastly, duality in convex programming is shown to be a special case of the present problem.The present research is partially supported by National Research Council of Canada.     

Dual gauge programs,with applications to quadratic programming and the minimum-norm problem

A gauge functionf(·) is a nonnegative convex function that is positively homogeneous and satisfiesf(0)=0. Norms and pseudonorms are specific instances of a gauge function. This paper presents a gauge duality theory for a gauge program, which is the problem of minimizing the value of a gauge functionf(·) over a convex set. The gauge dual program is also a gauge program, unlike the standard Lagrange dual. We present sufficient conditions onf(·) that ensure the existence of optimal solutions to the gauge program and its dual, with no duality gap. These sufficient conditions are relatively weak and are easy to verify, and are independent of any qualifications on the constraints. The theory is applied to a class of convex quadratic programs, and to the minimuml _p norm problem. The gauge dual program is shown to provide a smaller duality than the standard dual, in a certain sense discussed in the text.     

Partial Lagrangian relaxation for general quadratic programming

We give a complete characterization of constant quadratic functions over an affine variety. This result is used to convexify the objective function of a general quadratic programming problem (Pb) which contains linear equality constraints. Thanks to this convexification, we show that one can express as a semidefinite program the dual of the partial Lagrangian relaxation of (Pb) where the linear constraints are not relaxed. We apply these results by comparing two semidefinite relaxations made from two sets of null quadratic functions over an affine variety.