China
Africa
Explore chapters and articles related to this topic
Mixed Type Duality and Saddle Point Criteria for Multiobjective Programming Problems with Nonsmooth Generalized Invexity
Published in Anurag Jayswal, Tadeusz Antczak, Continuous Optimization and Variational Inequalities, 2023
In multiobjective programming problems, when the necessary optimality conditions are established, the conditions for searching an optimal solution will be employed. That is, extra reasonable assumptions for the necessary optimality conditions are needed in order to prove the sufficient optimality conditions. Moreover, these reasonable assumptions are various (e.g. generalized convexity, generalized invexity, set-valued functions and complex functions etc). When the existence of optimality solution is approved in the sufficient optimality theorems, the optimality conditions to investigate the duality models could be employed. Then the duality theorems could be proved. The better condition is that there is no duality gap between primal problems and duality problems. Hence, the duality theorems will be various due to different extra assumptions.
Asset and Liability Management: Recent Advances
Published in George Anastassiou, Handbook of Analytic-Computational Methods in Applied Mathematics, 2019
Interior point method was first proposed by Karmarkar in 1984. The primal-dual interior point method is based on approximation of primal dual trajectories in the interior of the feasible region. The primal and dual problems are solved simultaneously with a progressive reduction of the duality gap at each iteration. The convergence for this algorithm is in general seen to be independent of the problem size. Lustig et al. [58] demonstrated that unlike simplex based methods, the interior point algorithms can significantly benefit from partial variable splitting formulations that yield a staircase structure. See also Berger et al. [4] and Gausmann [36] on this method.
Unconstrained and Constrained Optimization Problems
Published in Erchin Serpedin, Thomas Chen, Dinesh Rajan, Mathematical Foundations for SIGNAL PROCESSING, COMMUNICATIONS, AND NETWORKING, 2012
Shuguang Cui, Anthony Man-Cho So, Rui Zhang
Given the primal–dual pair of problems (P) and (D), the duality gap between them is defined as Δ=υp*−υd*. By Theorem 14.2.6, we always have Δ ≥ 0. It would be nice to have Δ = 0 (i.e., zero duality gap). However, as the following example shows, this is not true in general.
An efficient model for locating solid waste collection sites in urban residential areas
Published in International Journal of Production Research, 2021
Olawale J. Adeleke, M. Montaz Ali
The Lagrangian procedure described in Algorithm 1 calls the subgradient method to solve (19) by initialising with suitable values such that is large enough to move the solution towards the extreme points (Carter and Price 2001). Next, is minimised with fixed values of by solving individual sub-problem and the obtained solutions are then used in the primal problem to find a new set of values for (Balci and Valenzuela 2004). This iterative process continues until a stopping criterion, usually the duality gap, is satisfied. The duality gap measures the difference between the values of the primal problem and the dual problem. At each of the iterations, the values of the multipliers are updated using appropriate techniques. The subgradient optimisation has often been the method of choice among LR researchers in achieving this purpose largely because the generated lower bound is often close enough to the optimal value of the primal problem (Beasley 1993). The method is described as follows: a vector is a sub-gradient of at if .
Strategic bidding for a price-maker hydroelectric producer: Stochastic dual dynamic programming and Lagrangian relaxation
Published in IISE Transactions, 2018
Gregory Steeger, Timo Lohmann, Steffen Rebennack
Recently, advances from the integer L-shaped method have been incorporated and refined for multi-stage stochastic integer programming problems (Angulo et al., 2016; Zou et al., 2018). The proposed method in Zou et al. (2018) presents the so-called Stochastic Dual Dynamic integer Programming (SDDiP) approach, which is an exact SDDP-type decomposition method for integer-programming problems. To mitigate the non-convex value functions in the state variables for integer programming problems, the proposed algorithm is restricted to binary state variables. This way, the value functions can be represented exactly. The key ingredient is a Lagrangian dual problem that possesses a zero duality gap. If the problem contains integer and/or continuous state variables, then these state variables need to be encoded by binary expansion. For problems with a large number of continuous state variables in high dimensions, like ours, SDDiP might not be practical, due to the requirement of binary expansion. In addition, the SDDP algorithm with Lagrangian relaxation proposed in this article can be applied towards general non-convex subproblems and is not restricted to mixed-integer linear programming problems.
On duality gap with polynomial multipliers for polynomial optimization problems
Published in Optimization, 2023
Duality in optimization, in particular the Lagrange duality in convex analysis, plays a crucial role in designing efficient methods or conceptual schemes for finding solutions of an optimization problem; see, e.g. [1–3]. In the duality of convex optimization, zero-duality gap is often studied, which decribes the difference between the optimal value of the primal optimization problem and the optimal value of its dual program. However, verifying such zero-duality gaps may tend to a difficult task when the dual problem is not numerically tractable, see e.g. [4,5] and the references therein.