共查询到20条相似文献,搜索用时 31 毫秒
1.
With this note we bring again into attention a vector dual problem neglected by the contributions who have recently announced
the successful healing of the trouble encountered by the classical duals to the classical linear vector optimization problem. This vector dual problem has, different
to the mentioned works which are of set-valued nature, a vector objective function. Weak, strong and converse duality for
this “new-old” vector dual problem are proven and we also investigate its connections to other vector duals considered in
the same framework in the literature. We also show that the efficient solutions of the classical linear vector optimization
problem coincide with its properly efficient solutions (in any sense) when the image space is partially ordered by a nontrivial
pointed closed convex cone, too. 相似文献
2.
Marco A. López Andrea B. Ridolfi Virginia N. Vera de Serio 《Nonlinear Analysis: Theory, Methods & Applications》2012,75(3):1461-1482
In this paper, we apply the concept of coderivative and other tools from the generalized differentiation theory for set-valued mappings to study the stability of the feasible sets of both the primal and the dual problem in infinite-dimensional linear optimization with infinitely many explicit constraints and an additional conic constraint. After providing some specific duality results for our dual pair, we study the Lipschitz-like property of both mappings and also give bounds for the associated Lipschitz moduli. The situation for the dual shows much more involved than the case of the primal problem. 相似文献
3.
A. Y. Azimov 《Journal of Optimization Theory and Applications》2008,137(1):61-74
The duality of multiobjective problems is studied with the help of the apparatus of conjugate set-valued mappings introduced
by the author. In this paper (Part 1), a duality theory is developed for set-valued mappings, which is then used to derive
dual relations for some general multiobjective optimization problems which include convex programming and optimal control
problems. Using this result, in the companion paper (Part 2), duality theorems are proved for multiobjective quasilinear and
linear optimal control problems. The theory is applied to get dual relations for some multiobjective optimal control problem. 相似文献
4.
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. 相似文献
5.
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. 相似文献
6.
É. Komáromi 《Journal of Optimization Theory and Applications》1992,75(3):587-602
We present two pairs of dually related probabilistic constrained problems as extensions of the linear programming duality concept. In the first pair, a bilinear function appears in the objectives and each objective directly depends on the feasibility set of the other problem, as in the game theoretical formulation of dual linear programs. In the second pair, we reformulate the objectives and eliminate their direct dependence on the feasibility set of the other problem. We develop conditions under which the dually related problems have no duality gap and conditions under which the two pairs of problems are equivalent as far as their optimality sets are concerned. 相似文献
7.
Based on the complete-lattice approach, a new Lagrangian type duality theory for set-valued optimization problems is presented. In contrast to previous approaches, set-valued versions for the known scalar formulas involving infimum and supremum are obtained. In particular, a strong duality theorem, which includes the existence of the dual solution, is given under very weak assumptions: The ordering cone may have an empty interior or may not be pointed. “Saddle sets” replace the usual notion of saddle points for the Lagrangian, and this concept is proven to be sufficient to show the equivalence between the existence of primal/dual solutions and strong duality on the one hand, and the existence of a saddle set for the Lagrangian on the other hand. Applications to set-valued risk measures are indicated. 相似文献
8.
Robust conjugate duality for convex optimization under uncertainty with application to data classification 总被引:1,自引:0,他引:1
In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences. 相似文献
9.
Elisa Pagani 《Optimization Letters》2012,6(5):901-914
We recall a general scheme for vector problems based on separation arguments and alternative theorems, and then, this approach is exploited to study Lagrangian duality in vector optimization. We show that the vector linear duality theory due to Isermann can be embedded in this separation approach. The theoretical part of this paper serves the purpose of introducing two possible applications. Some well-known classical applications in economics are the minimization of costs and the maximization of profit for a firm. We extend these two examples to the multiobjective framework in the linear case, exploiting the duality theory of Isermann. For the former, we consider the minimization of costs and of pollution as two different and conflicting goals; for the latter, we introduce as second objective function the profit for a competitor firm. This allows us to study the relationships between the shadow prices referred to the two different goals and to introduce a new representation of the feasible region of the dual problem. 相似文献
10.
Universal duality in conic convex optimization 总被引:1,自引:0,他引:1
Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended
real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +∞ and
−∞. In contrast, for optimization problems over nonpolyhedral convex cones, a nonzero duality gap can exist when either the
primal or the dual is feasible.
For a pair of dual conic convex programs, we provide simple conditions on the ``constraint matrices' and cone under which
the duality gap is zero for every choice of linear objective function and constraint right-hand side. We refer to this property as ``universal duality'. Our
conditions possess the following properties: (i) they are necessary and sufficient, in the sense that if (and only if) they
do not hold, the duality gap is nonzero for some linear objective function and constraint right-hand side; (ii) they are metrically
and topologically generic; and (iii) they can be verified by solving a single conic convex program. We relate to universal
duality the fact that the feasible sets of a primal convex program and its dual cannot both be bounded, unless they are both
empty. Finally we illustrate our theory on a class of semidefinite programs that appear in control theory applications.
This work was supported by a fellowship at the University of Maryland, in addition to NSF grants DEMO-9813057, DMI0422931,
CUR0204084, and DoE grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper
are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department
of Energy. 相似文献
11.
In this paper we present two approaches to duality in multiple objective linear programming. The first approach is based on a duality relation between maximal elements of a set and minimal elements of its complement. It offers a general duality scheme which unifies a number of known dual constructions and improves several existing duality relations. The second approach utilizes polarity between a convex polyhedral set and the epigraph of its support function. It leads to a parametric dual problem and yields strong duality relations, including those of geometric duality. 相似文献
12.
This paper is devoted to developing augmented Lagrangian duality theory in vector optimization. By using the concepts of the supremum and infimum of a set and conjugate duality of a set-valued map on the basic of weak efficiency, we establish the interchange rules for a set-valued map, and propose an augmented Lagrangian function for a vector optimization problem with set-valued data. Under this augmented Lagrangian, weak and strong duality results are given. Then we derive sufficient conditions for penalty representations of the primal problem. The obtained results extend the corresponding theorems existing in scalar optimization. 相似文献
13.
Gauge duality theory was originated by Freund (1987), and was recently further investigated by Friedlander et al. (2014). When solving some matrix optimization problems via gauge dual, one is usually able to avoid full matrix decompositions such as singular value and/or eigenvalue decompositions. In such an approach, a gauge dual problem is solved in the first stage, and then an optimal solution to the primal problem can be recovered from the dual optimal solution obtained in the first stage. Recently, this theory has been applied to a class of semidefinite programming (SDP) problems with promising numerical results by Friedlander and Macêdo (2016). We establish some theoretical results on applying the gauge duality theory to robust principal component analysis (PCA) and general SDP. For each problem, we present its gauge dual problem, characterize the optimality conditions for the primal-dual gauge pair, and validate a way to recover a primal optimal solution from a dual one. These results are extensions of Friedlander and Macêdo (2016) from nuclear norm regularization to robust PCA and from a special class of SDP which requires the coefficient matrix in the linear objective to be positive definite to SDP problems without this restriction. Our results provide further understanding in the potential advantages and disadvantages of the gauge duality theory. 相似文献
14.
The geometric duality theory of Heyde and Löhne (2006) defines a dual to a multiple objective linear programme (MOLP). In objective space, the primal problem can be solved by Benson’s outer approximation method (Benson 1998a,b) while the dual problem can be solved by a dual variant of Benson’s algorithm (Ehrgott et al. 2007). Duality theory then assures that it is possible to find the (weakly) nondominated set of the primal MOLP by solving its dual. In this paper, we propose an algorithm to solve the dual MOLP approximately but within specified tolerance. This approximate solution set can be used to calculate an approximation of the weakly nondominated set of the primal. We show that this set is a weakly ε-nondominated set of the original primal MOLP and provide numerical evidence that this approach can be faster than solving the primal MOLP approximately. 相似文献
15.
16.
A dual variant of Benson’s “outer approximation algorithm” for multiple objective linear programming
Outcome space methods construct the set of nondominated points in the objective (outcome) space of a multiple objective linear
programme. In this paper, we employ results from geometric duality theory for multiple objective linear programmes to derive
a dual variant of Benson’s “outer approximation algorithm” to solve multiobjective linear programmes in objective space. We
also suggest some improvements of the original version of the algorithm and prove that solving the dual provides a weight
set decomposition. We compare both algorithms on small illustrative and on practically relevant examples. 相似文献
17.
Guoyin Li Alfred Ka Chun Ma Ting Kei Pong 《Computational Optimization and Applications》2014,58(2):347-379
In this paper, we consider a least square semidefinite programming problem under ellipsoidal data uncertainty. We show that the robustification of this uncertain problem can be reformulated as a semidefinite linear programming problem with an additional second-order cone constraint. We then provide an explicit quantitative sensitivity analysis on how the solution under the robustification depends on the size/shape of the ellipsoidal data uncertainty set. Next, we prove that, under suitable constraint qualifications, the reformulation has zero duality gap with its dual problem, even when the primal problem itself is infeasible. The dual problem is equivalent to minimizing a smooth objective function over the Cartesian product of second-order cones and the Euclidean space, which is easy to project onto. Thus, we propose a simple variant of the spectral projected gradient method (Birgin et al. in SIAM J. Optim. 10:1196–1211, 2000) to solve the dual problem. While it is well-known that any accumulation point of the sequence generated from the algorithm is a dual optimal solution, we show in addition that the dual objective value along the sequence generated converges to a finite value if and only if the primal problem is feasible, again under suitable constraint qualifications. This latter fact leads to a simple certificate for primal infeasibility in situations when the primal feasible set lies in a known compact set. As an application, we consider robust correlation stress testing where data uncertainty arises due to untimely recording of portfolio holdings. In our computational experiments on this particular application, our algorithm performs reasonably well on medium-sized problems for real data when finding the optimal solution (if exists) or identifying primal infeasibility, and usually outperforms the standard interior-point solver SDPT3 in terms of CPU time. 相似文献
18.
We consider a multiobjective optimization problem with a feasible set defined by inequality and equality constraints and a set constraint, where the objective and constraint functions are locally Lipschitz. Several constraint qualifications are given in such a way that they generalize the classical ones, when the functions are differentiable. The relationships between them are analyzed. Then, we establish strong Kuhn–Tucker necessary optimality conditions in terms of the Clarke subdifferentials such that the multipliers of the objective function are all positive. Furthermore, sufficient optimality conditions under generalized convexity assumptions are derived. Moreover, the concept of efficiency is used to formulate duality for nonsmooth multiobjective problems. Wolf and Mond–Weir type dual problems are formulated. We also establish the weak and strong duality theorems. 相似文献
19.
We survey some recent developments in duality theory with the idea of explaining and unifying certain basic duality results in both nonlinear and integer programming. The idea of replacing dual variables (prices) by price functions, suggested by Everett and developed by Gould, is coupled with an appropriate dual problem with the consequence that many of the results resemble those used in linear programming. The dual problem adopted has a (traditional) economic interpretation and dual feasibility then provides a simple alternative to concepts such as conjugate functions or subdifferentials used in the study of optimality. In addition we attempt to make precise the relationship between primal, dual and saddlepoint results in both the traditional Lagrangean and the more general duality theories and to see the implications of passing from prices to price functions. Finally, and perhaps surprisingly, it appears that all the standard algorithms terminate by constructing primal and dual feasible solutions of equal value, i.e., by satisfying generalised optimality conditions. 相似文献
20.
J. Brinkhuis 《Journal of Optimization Theory and Applications》1996,91(3):523-542
A systematic exposition of duality theory is given on what appears to be the optimal level of generality. A condition is offered which implies that the ideal of duality theory is achieved. For the case of linear programming, our approach leads to two novel features. In the first place, primal and dual LP-problems and complementarity conditions are defined canonically, without choosing a matrix form. In the second place, without deriving the explicit form of the dual problem, we show that the following well-known fact implies that the condition mentioned above holds: the polyhedral set property is invariant under linear maps. We give a new quick algorithmic proof of this fact.The author would like to thank Jan Boone for his helpful comments on a preliminary version of this paper. 相似文献