Gap duality in convex programming

Gap duality in convex programming

0.00 Avg rating0 Votes
Article ID: iaor20072062
Country: Cuba
Volume: 26
Issue: 3
Start Page Number: 219
End Page Number: 224
Publication Date: Sep 2005
Journal: Revista de Investigacin Operacional
Authors: , ,
Keywords: duality
Abstract:

Whenever an optimization problem is planned it is necessary to wonder if there exists another associated problem to the previous one, that allows, among other things, to solve the former in a simpler way, taking advantage from the properties of the second as the concavity of the function objective, its smallest dimension, and/or the simplicity of the constraints, etc. They are the primal and dual problems. If in addition we consider that the primal problem is a convex program, the dual problem that characterizes it is such that by solving the other it is also solved as well as allows to analyse its sensibility. We structure this work in the following way: In section 1 the basic concepts on duality are developed, among them that of duality gap, the theorem of the weak duality is enunciated. Section 2 is dedicated to the conditions under which a coincidence between the solutions of the primal and dual problem coincide, (duality gap zero). These conditions are based on the properties of convexity of the original problem and the qualification of Slater, being justified by the strong duality theorem (necessary but not sufficient condition). In section 3 a more general condition is given the qualification of Slater, called property D, which is a characterization of the absence of the duality gap in certain sense.

Reviews

Required fields are marked *. Your email address will not be published.