A new proof of the strong duality theorem for semidefinite programming

Semidefinite programs are convex optimization problems arising in a wide variety of applications and are the extension of linear programming. Most methods for linear programming have been generalized to semidefinite programs. Just as in linear programming, duality theorem plays a basic and an important role in theory as well as in algorithmics. Based on the discretization method and convergence property, this paper proposes a new proof of the strong duality theorem for semidefinite programming, which is different from other common proofs and is more simple.     

On duality theory of convex semi-infinite programming

In this article we discuss weak and strong duality properties of convex semi-infinite programming problems. We use a unified framework by writing the corresponding constraints in a form of cone inclusions. The consequent analysis is based on the conjugate duality approach of embedding the problem into a parametric family of problems parameterized by a finite-dimensional vector.     

A study of mixed discrete bilevel programs using semidefinite and semi-infinite programming

In this paper, we study the bilevel programming problem with discrete polynomial lower level problem. We start by transforming the problem into a bilevel problem comprising a semidefinite program (SDP for short) in the lower level problem. Then, we are able to deduce some conditions of existence of solutions for the original problem. After that, we again change the bilevel problem with SDP in the lower level problem into a semi-infinite program. With the aid of the exchange technique, for simple bilevel programs, an algorithm for computing a global optimal solution is suggested, the convergence is shown, and a numerical example is given.     

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.     

Duality for semi-definite and semi-infinite programming

In this article, we study semi-definite and semi-infinite programming problems (SDSIP), which includes semi-infinite linear programs and semi-definite programs as special cases. We establish that a uniform duality between the homogeneous (SDSIP) and its Lagrangian-type dual problem is equivalent to the closedness condition of certain cone. Moreover, this closedness condition was assured by a generalized canonically closedness condition and a Slater condition. Corresponding results for the nonhomogeneous (SDSIP) problem were obtained by transforming it into an equivalent homogeneous (SDSIP) problem.     

Lower level duality and the global solution of generalized semi-infinite programs

The reformulation of generalized semi-infinite programs (GSIP) to simpler problems is considered. These reformulations are achieved under the assumption that a duality property holds for the lower level program (LLP). Lagrangian duality is used in the general case to establish the relationship between the GSIP and a related semi-infinite program (SIP). Practical aspects of this reformulation, including how to bound the duality multipliers, are also considered. This SIP reformulation result is then combined with recent advances for the global, feasible solution of SIP to develop a global, feasible point method for the solution of GSIP. Reformulations to finite nonlinear programs, and the practical aspects of solving these reformulations globally, are also discussed. When the LLP is a linear program or second-order cone program, specific duality results can be used that lead to stronger results. Numerical examples demonstrate that the global solution of GSIP is computationally practical via the solution of these duality-based reformulations.     

A note on perfect duality and limiting lagrangeans

In this note we derive and extend the substance of recent results on Perfect Duality and Limiting Lagrangeans by using standard convex analysis and convex duality theory.Research partially supported by NRC A4493.     

Linear fractional programming and duality

This paper presents a dual of a general linear fractional functionals programming problem. Dual is shown to be a linear programming problem. Along with other duality theorems, complementary slackness theorem is also proved. A simple numerical example illustrates the result.     

Initialization in semidefinite programming via a self-dual skew-symmetric embedding

The formulation of interior point algorithms for semidefinite programming has become an active research area, following the success of the methods for large-scale linear programming. Many interior point methods for linear programming have now been extended to the more general semidefinite case, but the initialization problem remained unsolved.In this paper we show that the initialization strategy of embedding the problem in a self-dual skew-symmetric problem can also be extended to the semidefinite case. This method also provides a solution for the initialization of quadratic programs and it is applicable to more general convex problems with conic formulation.     

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.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

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.     

A note on strong duality in convex semidefinite optimization: necessary and sufficient conditions

A strong duality which states that the optimal values of the primal convex problem and its Lagrangian dual problem are equal (i.e. zero duality gap) and the dual problem attains its maximum is a corner stone in convex optimization. In particular it plays a major role in the numerical solution as well as the application of convex semidefinite optimization. The strong duality requires a technical condition known as a constraint qualification (CQ). Several CQs which are sufficient for strong duality have been given in the literature. In this note we present new necessary and sufficient CQs for the strong duality in convex semidefinite optimization. These CQs are shown to be sharper forms of the strong conical hull intersection property (CHIP) of the intersecting sets of constraints which has played a critical role in other areas of convex optimization such as constrained approximation and error bounds. Research was partially supported by the Australian Research Council. The author is grateful to the referees for their helpful comments     

On duality in multiobjective semi-infinite optimization

Abstract

In this paper, we consider multiobjective semi-infinite optimization problems which are defined in a finite-dimensional space by finitely many objective functions and infinitely many inequality constraints. We present duality results both for the convex and nonconvex case. In particular, we show weak, strong and converse duality with respect to both efficiency and weak efficiency. Moreover, the property of being a locally properly efficient point plays a crucial role in the nonconvex case.     

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.     

LP relaxations for a class of linear semi-infinite programming problems

In this paper, we consider a subclass of linear semi-infinite programming problems whose constraint functions are polynomials in parameters and index sets are polyhedra. Based on Handelman’s representation of positive polynomials on a polyhedron, we propose two hierarchies of LP relaxations of the considered problem which respectively provide two sequences of upper and lower bounds of the optimum. These bounds converge to the optimum under some mild assumptions. Sparsity in the LP relaxations is explored for saving computational time and avoiding numerical ill behaviors.     

Optimal value function in semi-infinite programming

In this paper, we provide a systematic approach to the main topics in linear semi-infinite programming by means of a new methodology based on the many properties of the sub-differential mapping and the closure of a given convex function. In particular, we deal with the duality gap problem and its relation to the discrete approximation of the semi-infinite program. Moreover, we have made precise the conditions that allow us to eliminate the duality gap by introducing a perturbation in the primal objective function. As a by-product, we supply different extensions of well-known results concerning the subdifferential mapping.     

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.     

Interior-point algorithms for semi-infinite programming

In order to study the behavior of interior-point methods on very large-scale linear programming problems, we consider the application of such methods to continuous semi-infinite linear programming problems in both primal and dual form. By considering different discretizations of such problems we are led to a certain invariance property for (finite-dimensional) interior-point methods. We find that while many methods are invariant, several, including all those with the currently best complexity bound, are not. We then devise natural extensions of invariant methods to the semi-infinite case. Our motivation comes from our belief that for a method to work well on large-scale linear programming problems, it should be effective on fine discretizations of a semi-infinite problem and it should have a natural extension to the limiting semi-infinite case.Research supported in part by NSF, AFORS and ONR through NSF grant DMS-8920550.     

An improved semidefinite programming relaxation for the satisfiability problem

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial time. Semidefinite programming (SDP) refers to the class of optimization problems where a linear function of a matrix variable X is maximized (or minimized) subject to linear constraints on the elements of X and the additional constraint that X be positive semidefinite. We are interested in the application of SDP to satisfiability problems, and in particular in how SDP can be used to detect unsatisfiability. In this paper we introduce a new SDP relaxation for the satisfiability problem. This SDP relaxation arises from the recently introduced paradigm of higher liftings for constructing semidefinite programming relaxations of discrete optimization problems. To derive the SDP relaxation, we first formulate SAT as an optimization problem involving matrices. Relaxing this formulation yields an SDP which significantly improves on the previous relaxations in the literature. The important characteristics of the SDP relaxation are its ability to prove that a given SAT formula is unsatisfiable independently of the lengths of the clauses in the formula, its potential to yield truth assignments satisfying the SAT instance if a feasible matrix of sufficiently low rank is computed, and the fact that it is more amenable to practical computation than previous SDPs arising from higher liftings. We present theoretical and computational results that support these claims.Mathematics Subject Classification (2000): 20E28, 20G40, 20C20