On zero duality gap in nonconvex quadratic programming problems

We present in this paper new sufficient conditions for verifying zero duality gap in nonconvex quadratically/linearly constrained quadratic programs (QP). Based on saddle point condition and conic duality theorem, we first derive a sufficient condition for the zero duality gap between a quadratically constrained QP and its Lagrangian dual or SDP relaxation. We then use a distance measure to characterize the duality gap for nonconvex QP with linear constraints. We show that this distance can be computed via cell enumeration technique in discrete geometry. Finally, we revisit two sufficient optimality conditions in the literature for two classes of nonconvex QPs and show that these conditions actually imply zero duality gap.     

Improved estimation of duality gap in binary quadratic programming using a weighted distance measure

We present in this paper an improved estimation of duality gap between binary quadratic program and its Lagrangian dual. More specifically, we obtain this improved estimation using a weighted distance measure between the binary set and certain affine subspace. We show that the optimal weights can be computed by solving a semidefinite programming problem. We further establish a necessary and sufficient condition under which the weighted distance measure gives a strictly tighter estimation of the duality gap than the existing estimations.     

On reduction of duality gap in quadratic knapsack problems

We investigate in this paper the duality gap between quadratic knapsack problem and its Lagrangian dual or semidefinite programming relaxation. We characterize the duality gap by a distance measure from set {0, 1} ⁿ to certain polyhedral set and demonstrate that the duality gap can be reduced by an amount proportional to the square of the distance. We further discuss how to compute the distance measure via cell enumeration method and to derive the corresponding improved upper bound of the problem.     

Unit integer quadratic binary programming

This paper presents an efficient method of computing $\text{?′}{}_{\mathrm{<mtext>max</mtext>}}\text{=}\text{max}\text{Y}\text{Y}{}^{\mathrm{<mtext>T</mtext>}}\text{AY}$, where Y is an N-dimensional vector of ±1 entries and A is a real symmetric matrix. The ratio of number of computations required by this method to that by the direct method is approximately ($\text{3}\text{2N}$), where the direct method corresponds to computing Y^TAY for all possible Y and then finding the maximum from these. This problem has important applications in operations research, matrix theory, signal processing, communication theory, control theory, and others. Some of these are discussed in this paper.     

A duality theorem for complex quadratic programming

A duality theory for complex quadratic programming over polyhedral cones is developed, following Dorn, by using linear duality theory.This research was partly supported by the National Science Foundation, Project No. GP-7550, and by the US Army Research Office, Durham, North Carolina, Contract No. DA-31-124-ARO-D-322. The authors are indebted to the referee for his helpful suggestions.     

On products and duality of binary, quadratic, regular operads

Since its introduction by Loday in 1995, with motivation from algebraic K-theory, dendriform dialgebras have been studied quite extensively with connections to several areas in Mathematics and Physics. A few more similar structures have been found recently, such as the tri-, quadri-, ennea- and octo-algebras, with increasing complexity in their constructions and properties. We consider these constructions as operads and their products and duals, in terms of generators and relations, with the goal to clarify and simplify the process of obtaining new algebra structures from known structures and from linear operators.     

Generalized S-Lemma and strong duality in nonconvex quadratic programming

On the basis of a new topological minimax theorem, a simple and unified approach is developed to Lagrange duality in nonconvex quadratic programming. Diverse generalizations as well as equivalent forms of the S-Lemma, providing a thorough study of duality for single constrained quadratic optimization, are derived along with new strong duality conditions for multiple constrained quadratic optimization. The results allow many quadratic programs to be solved by solving one or just a few SDP’s (semidefinite programs) of about the same size, rather than solving a sequence, often infinite, of SDP’s or linear programs of a very large size as in most existing methods.     

Path relinking for unconstrained binary quadratic programming

This paper presents two path relinking algorithms to solve the unconstrained binary quadratic programming (UBQP) problem. One is based on a greedy strategy to generate the relinking path from the initial solution to the guiding solution and the other operates in a random way. We show extensive computational results on five sets of benchmarks, including 31 large random UBQP instances and 103 structured instances derived from the MaxCut problem. Comparisons with several state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that both algorithms are able to improve the previous best known results for almost 40 percent of the 103 MaxCut instances.     

On duality concepts in fractional programming

The paper (Part I) describes an approach to duality in fractional programming on the basis of another kind of conjugate functions. The connections to some duality concepts (the Lagrange-duality and duality concepts of Craven and Schaible) are investigated and some new proofs of strong duality theorems are given.     

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.     

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.     

On abstract duality in mathematical programming

It is shown that duality in mathematical programming can be treated as a purely order theoretic concept which leads to some applications in economics. Conditions for strong duality results are given. Furthermore the underlying sets are endowed with (semi-)linear structures, and the perturbation function of arising linear and integer problems, which include bottleneck problems and extremal problems (in the sense of K. Zimmermann), is investigated.

---

Zusammenfassung In dieser Arbeit wird aufgezeigt, daß Dualitätskonzepte der mathematischen Optimierung in ordnungstheoretischem Rahmen beschrieben werden können. Dies führt u.a. auf neue Anwendungen in der Ökonomie. Ferner werden Bedingungen hergeleitet, unter denen starke Dualitätsaussagen gelten. Sodann werden die zugrundeliegenden Mengen mit algebraischen Strukturen versehen und es werden Dualitätssätze für lineare und ganzzahlige Programme über diesen Mengen bewiesen. Darunter fallen nicht nur die klassischen linearen und ganzzahligen Programme, sondern auch Probleme mit Engpaßzielfunktion und extremale Probleme im Sinne von K. Zimmermann.

---

---

This paper was partially supported by the NATO Research Grants Programme under SRG 8.     

A geometric characterization of strong duality in nonconvex quadratic programming with linear and nonconvex quadratic constraints

We first establish a relaxed version of Dines theorem associated to quadratic minimization problems with finitely many linear equality and a single (nonconvex) quadratic inequality constraints. The case of unbounded optimal valued is also discussed. Then, we characterize geometrically the strong duality, and some relationships with the conditions employed in Finsler theorem are established. Furthermore, necessary and sufficient optimality conditions with or without the Slater assumption are derived. Our results can be used to situations where none of the results appearing elsewhere are applicable. In addition, a revisited theorem due to Frank and Wolfe along with that due to Eaves is established for asymptotically linear sets.     

On the gap between the quadratic integer programming problem and its semidefinite relaxation

Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap We establish the uniqueness of the SDR solution and prove that if and only if γ_r:=n⁻¹max{x^TVV^Tx:x ∈ {-1, 1}ⁿ}=1 where V is an orthogonal matrix whose columns span the (r–dimensional) null space of D−Q and where D is the unique SDR solution. We also give a test for establishing whether that involves 2^r−1 function evaluations. In the case that γ_r<1 we derive an upper bound on γ which is tighter than Thus we show that `breaching' the SDR gap for the QIP problem is as difficult as the solution of a QIP with the rank of the cost function matrix equal to the dimension of the null space of D−Q. This reduced rank QIP problem has been recently shown to be solvable in polynomial time for fixed r.     

On duality gap in linear conic problems

In their paper “Duality of linear conic problems” Shapiro and Nemirovski considered two possible properties (A) and (B) for dual linear conic problems (P) and (D). The property (A) is “If either (P) or (D) is feasible, then there is no duality gap between (P) and (D)”, while property (B) is “If both (P) and (D) are feasible, then there is no duality gap between (P) and (D) and the optimal values val(P) and val(D) are finite”. They showed that (A) holds if and only if the cone K is polyhedral, and gave some partial results related to (B). Later Shapiro conjectured that (B) holds if and only if all the nontrivial faces of the cone K are polyhedral. In this note we mainly prove that both the “if” and “only if” parts of this conjecture are not true by providing examples of closed convex cone in \mathbbR⁴{\mathbb{R}^{4}} for which the corresponding implications are not valid. Moreover, we give alternative proofs for the results related to (B) established by Shapiro and Nemirovski.     

On strong duality in linear copositive programming

Journal of Global Optimization - The paper is dedicated to the study of strong duality for a problem of linear copositive programming. Based on the recently introduced concept of the set of...     

On duality in stochastic programming with recourse

This short paper compares dual programs of stochastic programs with recourse. It explains why the discrepancy exists between two such dual programs recently appearing in the literature. An example is presented which illustrates the difference.     

On duality in linear fractional functionals programming

Summary The paper formulates a dual program for a given linear fractional functionals program (L.F.F.P.) and proves the duality theorem and its converse for the same. Special feature of the paper is that both the primal and the dual programs are L. F. F. Ps. and can easily be solved by the existing standard techniques.

---

Zusammenfassung Für ein lineares Optimierungsproblem, dessen Zielfunktion als Quotient zweier linearer Funktionen gegeben ist (LP-Problem mit gebrochener Zielfunktion), wird ein duales Problem formuliert und das Dualitätstheorem bewiesen. Es wird gezeigt, daß sowohl das primale als auch das duale Problem lineare Probleme mit gebrochener Zielfunktion sind und leicht mit den bekannten Standardtechniken gelöst werden können.

     

On duality in multiple objective linear programming

In this paper we present two approaches to duality in multiple objective linear programming. The first approach is based on a duality relation between maximal elements of a set and minimal elements of its complement. It offers a general duality scheme which unifies a number of known dual constructions and improves several existing duality relations. The second approach utilizes polarity between a convex polyhedral set and the epigraph of its support function. It leads to a parametric dual problem and yields strong duality relations, including those of geometric duality.