共查询到20条相似文献,搜索用时 31 毫秒
1.
This contribution is concerned with goal–oriented r-adaptivity based on energy minimization principles for the primal and the dual problem. We obtain a material residual of the primal and of the dual problem, which are indicators for non–optimal finite element meshes. For goal–oriented r-adaptivity we have to optimize the mesh with respect to the dual solution, because the error of a local quantity of interest depends on the error in the corresponding dual solution. We use the material residual of the primal and dual problem in order to obtain a procedure for mesh optimization with respect to a local quantity of interest. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
2.
Efficient algorithms for buffer space allocation 总被引:1,自引:0,他引:1
This paper describes efficient algorithms for determining how buffer space should be allocated in a flow line. We analyze two problems: a primal problem, which minimizes total buffer space subject to a production rate constraint; and a dual problem, which maximizes production rate subject to a total buffer space constraint. The dual problem is solved by means of a gradient method, and the primal problem is solved using the dual solution. Numerical results are presented. Profit optimization problems are natural generalizations of the primal and dual problems, and we show how they can be solved using essentially the same algorithms. 相似文献
3.
Pham Huu Sach 《Numerical Functional Analysis & Optimization》2013,34(3-4):371-392
In this paper, we consider some dual problems of a primal multiobjective problem involving nonconvex set-valued maps. For each dual problem, we give conditions under which strong duality between the primal and dual problems holds in the sense that, starting from a Benson properly efficient solution of the primal problem, we can construct a Benson properly efficient solution of the dual problem such that the corresponding objective values of both problems are equal. The notion of generalized convexity of set-valued maps we use in this paper is that of near-subconvexlikeness. 相似文献
4.
Edward L. Hannan 《The Journal of the Operational Research Society》1978,29(7):643-649
The dual of the multiple objective linear programming problem is defined as a multiparametric LP problem for the right-hand sides. The resulting dual variables are multidimensional and are related to the indifference regions in the primal problem. The formulation of the dual is shown to be preferable to the vector minimization formulation in terms of (a) identifying primal efficient points and indifference regions, and (b) sensitivity analysis. 相似文献
5.
本文提出了一种整数规划中的指数一对数对偶.证明了此指数-对数对偶方法具有的渐近强对偶性质,并提出了不需要进行对偶搜索来解原整数规划问题的方法.特别地,当选取合适的参数和对偶变量时,原整数规划问题的解可以通过解一个非线性松弛问题来得到.对具有整系数目标函数及约束函数的多项式整规划问题,给出了参数及对偶变量的取法. 相似文献
6.
N. Mahdavi-Amiri F. Salehi Sadaghiani 《4OR: A Quarterly Journal of Operations Research》2017,15(3):303-326
Recently, Luc defined a dual program for a multiple objective linear program. The dual problem is also a multiple objective linear problem and the weak duality and strong duality theorems for these primal and dual problems have been established. Here, we use these results to prove some relationships between multiple objective linear primal and dual problems. We extend the available results on single objective linear primal and dual problems to multiple objective linear primal and dual problems. Complementary slackness conditions for efficient solutions, and conditions for the existence of weakly efficient solution sets and existence of strictly primal and dual feasible points are established. We show that primal-dual (weakly) efficient solutions satisfying strictly complementary conditions exist. Furthermore, we consider Isermann’s and Kolumban’s dual problems and establish conditions for the existence of strictly primal and dual feasible points. We show the existence of primal-dual feasible points satisfying strictly complementary conditions for Isermann’s dual problem. Also, we give an alternative proof to establish necessary conditions for weakly efficient solutions of multiple objective programs, assuming the Kuhn–Tucker (KT) constraint qualification. We also provide a new condition to ensure the KT constraint qualification. 相似文献
7.
《European Journal of Operational Research》1999,117(1):183-196
Duality formulations can be derived from a nonlinear primal optimization problem in several ways. One abstract theoretical concept presented by Johri is the framework of general dual problems. They provide the tightest of specific bounds on the primal optimum generated by dual subproblems which relax the primal problem with respect to the objective function or to the feasible set or even to both. The well-known Lagrangian dual and surrogate dual are shown to be special cases. Dominating functions and including sets which are the two relaxation devices of Johri's general dual turn out to be the most general formulations of augmented Lagrangian functions and augmented surrogate regions. 相似文献
8.
韩乔明 《高等学校计算数学学报(英文版)》1997,(2)
It is well known that for symmetric linear programming there exists a strictly complementary solution if the primal and the dual problems are both feasible. However, this is not necessary true for symmetric or general semide finite programming even if both the primal problem and its dual problem are strictly feasible. Some other properties are also concerned. 相似文献
9.
Magnus Önnheim Emil Gustavsson Ann-Brith Strömberg Michael Patriksson Torbjörn Larsson 《Mathematical Programming》2017,163(1-2):57-84
Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal–dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which—in the inconsistent case—the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional \(\varepsilon \)-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal–dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved. 相似文献
10.
《Optimization》2012,61(4):717-738
Augmented Lagrangian duality provides zero duality gap and saddle point properties for nonconvex optimization. On the basis of this duality, subgradient-like methods can be applied to the (convex) dual of the original problem. These methods usually recover the optimal value of the problem, but may fail to provide a primal solution. We prove that the recovery of a primal solution by such methods can be characterized in terms of (i) the differentiability properties of the dual function and (ii) the exact penalty properties of the primal-dual pair. We also connect the property of finite termination with exact penalty properties of the dual pair. In order to establish these facts, we associate the primal-dual pair to a penalty map. This map, which we introduce here, is a convex and globally Lipschitz function and its epigraph encapsulates information on both primal and dual solution sets. 相似文献
11.
《European Journal of Operational Research》2003,144(3):598-612
This research focuses on scheduling jobs with varying processing times and distinct due dates on a single machine subject to earliness and tardiness penalties. Hence, this work will find application in a just-in-time (JIT) production environment. The scheduling problem is formulated as a 0–1 linear integer program with three sets of constraints, where the objective is to minimize the sum of the absolute deviations between job completion times and their respective due dates. The first two sets of constraints are equivalent to the supply and demand constraints of an assignment problem. The third set, which represents the process time non-overlap constraints, is relaxed to form the Lagrangian dual problem. The dual problem is then solved using the subgradient algorithm. Efficient heuristics have also been developed in this work to yield initial primal feasible solutions and to convert primal infeasible solutions to feasibility. The computational results show that the relative deviation from optimality obtained by the subgradient algorithm is less than 3% for problem sizes varying from 10 to 100 jobs. 相似文献
12.
The convergence of primal and dual central paths associated to entropy and exponential functions, respectively, for semidefinite
programming problem are studied in this paper. It is proved that the primal path converges to the analytic center of the primal
optimal set with respect to the entropy function, the dual path converges to a point in the dual optimal set and the primal-dual
path associated to this paths converges to a point in the primal-dual optimal set. As an application, the generalized proximal
point method with the Kullback-Leibler distance applied to semidefinite programming problems is considered. The convergence
of the primal proximal sequence to the analytic center of the primal optimal set with respect to the entropy function is established
and the convergence of a particular weighted dual proximal sequence to a point in the dual optimal set is obtained. 相似文献
13.
This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual. 相似文献
14.
Hsien-Chung Wu 《Fuzzy Optimization and Decision Making》2007,6(3):179-198
The weak and strong duality theorems in fuzzy optimization problem based on the formulation of Wolfe’s primal and dual pair
problems are derived in this paper. The solution concepts of primal and dual problems are inspired by the nondominated solution
concept employed in multiobjective programming problems, since the ordering among the fuzzy numbers introduced in this paper
is a partial ordering. In order to consider the differentiation of a fuzzy-valued function, we invoke the Hausdorff metric
to define the distance between two fuzzy numbers and the Hukuhara difference to define the difference of two fuzzy numbers.
Under these settings, the Wolfe’s dual problem can be formulated by considering the gradients of differentiable fuzzy- valued
functions. The concept of having no duality gap in weak and strong sense are also introduced, and the strong duality theorems
in weak and strong sense are then derived naturally. 相似文献
15.
Solutions and optimality criteria for nonconvex quadratic-exponential minimization problem 总被引:1,自引:0,他引:1
This paper presents a set of complete solutions and optimality conditions for a nonconvex quadratic-exponential optimization
problem. By using the canonical duality theory developed by the first author, the nonconvex primal problem in n-dimensional space can be converted into an one-dimensional
canonical dual problem with zero duality gap, which can be solved easily to obtain all dual solutions. Each dual solution
leads to a primal solution. Both global and local extremality conditions of these primal solutions can be identified by the
triality theory associated with the canonical duality theory. Several examples are illustrated. 相似文献
16.
Many theoretical and algorithmic results in semidefinite programming are based on the assumption that Slater's constraint qualification is satisfied for the primal and the associated dual problem. We consider semidefinite problems with zero duality gap for which Slater's condition fails for at least one of the primal and dual problem. We propose a numerically reasonable way of dealing with such semidefinite programs. The new method is based on a standard search direction with damped Newton steps towards primal and dual feasibility. 相似文献
17.
18.
We develop a duality theory for problems of minimization of a convex functional on a convex set and apply this theory to optimal control problems with non-differentiable functional and state as well as control constraints. The dual problem is sometimes found to be simpler than the primal problem. The equivalence of the primal and the dual problem is established for problems in which the functional is strongly convex. A posteriori error are also given for such problems. 相似文献
19.
Regina S. Burachik Alfredo N. Iusem Jefferson G. Melo 《Journal of Optimization Theory and Applications》2013,157(1):108-131
We consider a primal optimization problem in a reflexive Banach space and a duality scheme via generalized augmented Lagrangians. For solving the dual problem (in a Hilbert space), we introduce and analyze a new parameterized Inexact Modified Subgradient (IMSg) algorithm. The IMSg generates a primal-dual sequence, and we focus on two simple new choices of the stepsize. We prove that every weak accumulation point of the primal sequence is a primal solution and the dual sequence converges weakly to a dual solution, as long as the dual optimal set is nonempty. Moreover, we establish primal convergence even when the dual optimal set is empty. Our second choice of the stepsize gives rise to a variant of IMSg which has finite termination. 相似文献
20.
For the minimization knapsack problem with Boolean variables, primal and dual greedy algorithms are formally described. Their relations to the corresponding algorithms for the maximization knapsack problem are shown. The average behavior of primal and dual algorithms for the minimization problem is analyzed. It is assumed that the coefficients of the objective function and the constraint are independent identically distributed random variables on [0, 1] with an arbitrary distribution having a density and that the right-hand side d is deterministic and proportional to the number of variables (i.e., d = μn). A condition on μ is found under which the primal and dual greedy algorithms have an asymptotic error of t. 相似文献