China
Africa
Explore chapters and articles related to this topic
A Hierarchical Management Framework for Autonomous Electric Mobility-on-Demand Services
Published in Hussein T. Mouftah, Melike Erol-Kantarci, Sameh Sorour, Connected and Autonomous Vehicles in Smart Cities, 2020
Nuzhat Yamin, Syrine Belakaria, Sameh Sorour, Mohamed Hefeida
Applying Slater’s theorem for duality qualification, and as strong duality holds for the considered optimization problem, then solving the dual problem gives the exact optimal solution for the primal problem. This is described by the equality: g(v*)=−bTv*=cTx*=−R*
Connectivity
Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018
Jonathan L. Gross, Jay Yellen, Mark Anderson
Borrowing from operations research terminology, we consider certain primal-dual pairs of optimization problems that are intimately related. Usually, one of these problems involves the maximization of some objective function, while the other is a minimization problem. A feasible solution to one of the problems provides a bound for the optimal value of the other problem (this is sometimes referred to as weak duality), and the optimal value of one problem is equal to the optimal value of the other (strong duality). Menger’s Theorems and their many variations epitomize this primal-dual relationship. The following terminology is used throughout this section.
Linear Programming and Mixed Integer Programming
Published in Erchin Serpedin, Thomas Chen, Dinesh Rajan, Mathematical Foundations for SIGNAL PROCESSING, COMMUNICATIONS, AND NETWORKING, 2012
Since LP is a convex optimization problem, strong duality holds, i.e., the primal and dual problems have the same optimal value. For LP, unlike for other convex problems, no special assumption (like the Slater condition) is required for strong duality: feasibility is enough.
On Fenchel c-conjugate dual problems for DC optimization: characterizing weak, strong and stable strong duality
Published in Optimization, 2023
In every approach including Fenchel conjugation to derive a dual problem for a primal one, the convexity, together with the properness and lower semicontinuity of the involved functions in the problem, make it possible to apply conjugate duality techniques to epigraphs, which ensure strong duality results. Given a primal problem, (P), and its dual, (D), it is said that the pair verifies weak duality when and strong duality when there is zero duality gap, i.e. , and the dual has an optimal solution. Connected to strong duality, stable strong duality means that there is strong duality when the objective function of the primal problem is perturbed with a linear functional. For more details on the development of regularity conditions for strong and stable strong dualities, we encourage the reader to revise [5,16,17].
Refining the partition for multifold conic optimization problems
Published in Optimization, 2020
Héctor Ramírez C., Vera Roshchina
The complementarity partitions for linear programming and linear complementarity problems are well understood and are utilized heavily in the analysis of optimization problems as well as in numerical methods. In addition to strong duality (i.e. when both primal and dual problems have optimal solutions, and the values of their objective functions coincide), linear programming problems exhibit strict complementarity: in an appropriately formulated pair of primal and dual problems each primal variable has a dual counterpart, and there exists an optimal solution that is also a fully complementary pair, such that exactly one variable in each pair is positive and the other one is zero. The situation is much more complex for general linear conic problems. In a multifold system, where in place of the componentwise inequalities, we have cone inclusions, it may happen that the relevant components of the primal and dual variables lie on the boundary of a corresponding cone. Moreover, there are several different definitions of complementarity that do not coincide and lead to different characterizations.