Dual semidefinite programs without duality gaps for a class of convex minimax programs

DOI10.1007/S10957-013-0496-0zbMATH Open1312.90087arXiv1307.5151OpenAlexW1993400404MaRDI QIDQ462995FDOQ462995

V. Jeyakumar, José Vicente-Pérez

Publication date: 23 October 2014

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Abstract: In this paper we introduce a new dual program, which is representable as a semi-definite linear programming problem, for a primal convex minimax programming model problem and show that there is no duality gap between the primal and the dual whenever the functions involved are SOS-convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust SOS-convex programming problems under data uncertainty and to minimax fractional programming problems with SOS-convex polynomials. We obtain these results by first establishing sum of squares polynomial representations of non-negativity of a convex max function over a system of SOS-convex constraints. The new class of SOS-convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The SOS-convexity of polynomials can numerically be checked by solving semi-definite programming problems whereas numerically verifying convexity of polynomials is generally very hard.

Full work available at URL: https://arxiv.org/abs/1307.5151

Recommendations

• New dual constraint qualifications characterizing zero duality gaps of convex programs and semidefinite programs
• Strong duality for standard convex programs
• Duality formulations in semidefinite programming
• Generalized SOS-convexity and strong duality with SDP dual programs in polynomial optimization
• Some convex programs without a duality gap

zbMATH Keywords

semidefinite programmingdualityzero duality gapminimax programmingsum-of-squares convex polynomials

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Semidefinite programming (90C22) Minimax problems in mathematical programming (90C47)

Cites Work

• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Title not available (Why is that?)
• Semidefinite Programming
• Theory and Applications of Robust Optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strong Duality in Robust Convex Programming: Complete Characterizations
• Title not available (Why is that?)
• Sums of squares, moment matrices and optimization over polynomials
• Fractional programming
• A convex polynomial that is not sos-convex
• A Frank--Wolfe type theorem for convex polynomial programs
• Title not available (Why is that?)
• Exact SDP relaxations for classes of nonlinear semidefinite programming problems
• Min-max optimization of several classical discrete optimization problems
• An algorithm for generalized fractional programs
• Semidefinite representation of convex sets
• Duality without a constraint qualification for minimax fractional programming
• A complete characterization of the gap between convexity and sos-convexity
• Farkas-type results for max-functions and applications

Cited In (21)

• Characterizing robust solution sets of convex programs under data uncertainty
• Sum-of-squares relaxations in robust DC optimization and feature selection
• Characterization of Positive Definite and Semide Finite Matrices via Quadratic Programming Duality
• Generalized Farkas lemma with adjustable variables and two-stage robust linear programs
• Generalized Farkas' lemma and gap-free duality for minimax DC optimization with polynomials and robust quadratic optimization
• SOS-convex semialgebraic programs and its applications to robust optimization: a tractable class of nonsmooth convex optimization
• Convergent conic linear programming relaxations for cone convex polynomial programs
• Farkas' lemma: three decades of generalizations for mathematical optimization
• Solving fractional multicriteria optimization problems with sum of squares convex polynomial data
• On minimizing difference of a SOS-convex polynomial and a support function over a SOS-concave matrix polynomial constraint
• On duality gap with polynomial multipliers for polynomial optimization problems
• Some convex programs without a duality gap
• A new proof of the strong duality theorem for semidefinite programming
• Conic linear programming duals for classes of quadratic semi-infinite programs with applications
• Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers
• Finding robust global optimal values of bilevel polynomial programs with uncertain linear constraints
• On semidefinite programming relaxations for a class of robust SOS-convex polynomial optimization problems
• Stable zero duality gaps in convex programming: complete dual characterisations with applications to semidefinite programs
• Conic relaxations with stable exactness conditions for parametric robust convex polynomial problems
• Title not available (Why is that?)
• Linear Matrix Inequality Conditions and Duality for a Class of Robust Multiobjective Convex Polynomial Programs

This page was built for publication: Dual semidefinite programs without duality gaps for a class of convex minimax programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q462995)