共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper, we revisit one of the most important scalarization techniques used in multiobjective programming, the ε-constraint method. We summarize the method and point out some weaknesses, namely the lack of easy-to-check conditions for
properly efficient solutions and the inflexibility of the constraints. We present two modifications that address these weaknesses
by first including slack variables in the formulation and second elasticizing the constraints and including surplus variables.
We prove results on (weakly, properly) efficient solutions. The improved ε-constraint method that we propose combines both modifications.
The research of M. Ehrgott was partially supported by University of Auckland Grant 3602178/9275 and by Deutsche Forschungsgemeinschaft
Grant Ka 477/27-1.
The research of S. Ruzika was partially supported by Deutsche Forschungsgemeinschaft Grant HA 1795/7-2.
The authors thank the anonymous referees, whose comments helped improving the presentation of the paper including a shorter
proof of Theorem 3.1. 相似文献
2.
3.
Convergence of stochastic search algorithms to finite size pareto set approximations 总被引:1,自引:0,他引:1
Oliver Schütze Marco Laumanns Carlos A. Coello Coello Michael Dellnitz El-Ghazali Talbi 《Journal of Global Optimization》2008,41(4):559-577
In this work we investigate the convergence of stochastic search algorithms toward the Pareto set of continuous multi-objective
optimization problems. The focus is on obtaining a finite approximation that should capture the entire solution set in a suitable
sense, which will be defined using the concept of ε-dominance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will
be determined entirely by the archiving strategy. We propose and analyse two different archiving strategies which lead to
a different limit behavior of the algorithms, yielding bounds on the obtained approximation quality as well as on the cardinality
of the resulting Pareto set approximation.
相似文献
4.
A special class of solutions for multiobjective programming problems with set functions is considered. A subset of nondominated solutions, called properD-solution set, with respect to a given domination structure is characterized under two situations, with and without inequality constraints.The authors greatly appreciate valuable comments received from the referees. 相似文献
5.
The Szpilrajn theorem and its strengthening by Dushnik and Miller belong to the most quoted theorems in many fields of pure
and applied mathematics as, for instance, order theory, mathematical logic, computer sciences, mathematical social sciences,
mathematical economics, computability theory and fuzzy mathematics. The Szpilrajn theorem states that every partial order
can be refined or extended to a total (linear) order. The theorem by Dushnik and Miller states, moreover, that every partial
order is the intersection of its total (linear) refinements or extensions. Since in mathematical social sciences or, more
general, in any theory that combines the concepts of topology and order one is mainly interested in continuous total orders
or preorders in this paper some aspects of a possible continuous analogue of the Szpilrajn theorem and its strengthening by
Dushnik and Miller will be discussed. In particular, necessary and sufficient conditions for a topological space to satisfy
a possible continuous analogue of the Dushnik-Miller theorem will be presented. In addition, it will be proved that a continuous
analogue of the Szpilrajn theorem does not hold in general. Further, necessary and in some cases necessary and sufficient
conditions for a topological space to satisfy a possible continuous analogue of the Szpilrajn theorem will be presented.
相似文献
6.
In this paper we examine nonlinear, nonautonomous evolution inclusions defined on a Gelfand triple of spaces. First we show
that the problem with a convex-valued,h*-usc inx orientor fieldF(t, x) has a solution set which is anR
δ-set inC(T, H). Then for the problem with a nonconvex-valuedF(t, x) which ish-Lipschitz inx, we show that the solution set is path-connected inC(T, H). Subsequently we prove a strong invariance result and a continuity result for the solution multifunction. Combining these
two results we establish the existence of periodic solutions. Some examples of parabolic partial differential equations with
multivalued terms are also included.
This work was done while the authors were visiting the Florida Institute of Technology. 相似文献
7.
The numerical approximation of nonlinear partial differential equations requires the computation of large nonlinear systems,
that are typically solved by iterative schemes. At each step of the iterative process, a large and sparse linear system has
to be solved, and the amount of time elapsed per step grows with the dimensions of the problem. As a consequence, the convergence
rate may become very slow, requiring massive cpu-time to compute the solution. In all such cases, it is important to improve
the rate of convergence of the iterative scheme. This can be achieved, for instance, by vector extrapolation methods. In this
work, we apply some vector extrapolation methods to the electronic device simulation to improve the rate of convergence of
the family of Gummel decoupling algorithms. Furthermore, a different approach to the topological ε-algorithm is proposed and preliminary results are presented. 相似文献
8.
Based on the specified grades of satisfaction, we propose two new concepts of (α, β)-acceptable optimal solution and (α, β)-acceptable
optimal value of a fuzzy linear fractional programming problem with fuzzy coefficients, and develop a method to compute them.
An example is provided to demonstrate the method. 相似文献
9.
In this paper, we consider the generalized min-sum set cover problem, introduced by Azar, Gamzu, and Yin (STOC 2009). Bansal, Gupta, and Krishnaswamy (SODA 2010) give a 485-approximation algorithm for the problem. We are able to alter their algorithm and analysis to obtain a 28-approximation algorithm, improving the performance guarantee by an order of magnitude. We use concepts from α-point scheduling to obtain our improvements. 相似文献
10.
The noncommutative Singer-Wermer conjecture states that every linear (possibly unbounded) derivation on a (possibly noncommutative) Banach algebra maps into its Jacobson radical. This conjecture is still an open question for more than thirty years. In this paper we approach this question via linear left θ-derivations. 相似文献
11.
Yury Orlovich Jacek Blazewicz Alexandre Dolgui Gerd Finke Valery Gordon 《Discrete Mathematics》2011,(16):1670
We consider the complexity of the maximum (maximum weight) independent set problem within triangle graphs, i.e., graphs G satisfying the following triangle condition: for every maximal independent set I in G and every edge uv in G−I, there is a vertex w∈I such that {u,v,w} is a triangle in G. We also introduce a new graph parameter (the upper independent neighborhood number) and the corresponding upper independent neighborhood set problem. We show that for triangle graphs the new parameter is equal to the independence number. We prove that the problems under consideration are NP-complete, even for some restricted subclasses of triangle graphs, and provide several polynomially solvable cases for these problems within triangle graphs. Furthermore, we show that, for general triangle graphs, the maximum independent set problem and the upper independent neighborhood set problem cannot be polynomially approximated within any fixed constant factor greater than one unless P=NP. 相似文献
12.
D. Dryanov 《Constructive Approximation》2009,30(1):137-153
Kolmogorov ε-entropy of a compact set in a metric space measures its metric massivity and thus replaces its dimension which is usually infinite. The notion quantifies the compactness property of sets in metric
spaces, and it is widely applied in pure and applied mathematics. The ε-entropy of a compact set is the most economic quantity of information that permits a recovery of elements of this set with
accuracy ε. In the present article we study the problem of asymptotic behavior of the ε-entropy for uniformly bounded classes of convex functions in L
p
-metric proposed by A.I. Shnirelman. The asymptotic of the Kolmogorov ε-entropy for the compact metric space of convex and uniformly bounded functions equipped with L
p
-metric is ε
−1/2, ε→0+.
相似文献
13.
The present paper is devoted to generalizations of the Dieudonné theorem claiming that the convergence of sequences of regular
Borelian measures is preserved under the passage from a system of open subsets of a compact metric space to the class of all
Borelian subsets of this space. The Dieudonné theorem is proved in the case for which the set functions are weakly regular,
nonadditive, defined on an algebra of sets that contains the class of open subsets of an arbitrary σ-topological space, and
take values in a uniform space.
Translated fromMatematicheskie Zametki, Vol. 62, No. 1, pp. 103–110, July, 1997.
Translated by O. V. Sipacheva 相似文献
14.
In this paper, we propose a modification of Benson’s algorithm for solving multiobjective linear programmes in objective space
in order to approximate the true nondominated set. We first summarize Benson’s original algorithm and propose some small changes
to improve computational performance. We then introduce our approximation version of the algorithm, which computes an inner
and an outer approximation of the nondominated set. We prove that the inner approximation provides a set of -nondominated points. This work is motivated by an application, the beam intensity optimization problem of radiotherapy treatment
planning. This problem can be formulated as a multiobjective linear programme with three objectives. The constraint matrix
of the problem relies on the calculation of dose deposited in tissue. Since this calculation is always imprecise solving the
MOLP exactly is not necessary in practice. With our algorithm we solve the problem approximately within a specified accuracy
in objective space. We present results on four clinical cancer cases that clearly illustrate the advantages of our method. 相似文献
15.
In this paper we consider the Lane–Emden problem adapted for the p-Laplacian
where Ω is a bounded domain in , n ≥ 2, λ > 0 and p < q < p* (with if p < n, and p* = ∞ otherwise). After some recalls about the existence of ground state and least energy nodal solutions, we prove that,
when q → p, accumulation points of ground state solutions or of least energy nodal solutions are, up to a “good” scaling, respectively
first or second eigenfunctions of −Δ
p
.
Received: 29 April 2008 相似文献
16.
Dong Hyun Cho 《Czechoslovak Mathematical Journal》2009,59(2):431-452
Let C[0, T] denote the space of real-valued continuous functions on the interval [0, T] with an analogue w
ϕ of Wiener measure and for a partition 0 = t
0 < t
1 < ... < t
n
< t
n+1 = T of [0, T], let X
n
: C[0, T] → ℝ
n+1 and X
n+1: C[0, T] → ℝ
n+2 be given by X
n
(x) = (x(t
0), x(t
1), ..., x(t
n
)) and X
n+1(x) = (x(t
0), x(t
1), ..., x(t
n+1)), respectively.
In this paper, using a simple formula for the conditional w
ϕ-integral of functions on C[0, T] with the conditioning function X
n+1, we derive a simple formula for the conditional w
ϕ-integral of the functions with the conditioning function X
n
. As applications of the formula with the function X
n
, we evaluate the conditional w
ϕ-integral of the functions of the form F
m
(x) = ∫0
T
(x(t))
m
for x ∈ C[0, T] and for any positive integer m. Moreover, with the conditioning X
n
, we evaluate the conditional w
ϕ-integral of the functions in a Banach algebra
which is an analogue of the Cameron and Storvick’s Banach algebra
. Finally, we derive the conditional analytic Feynman w
ϕ-integrals of the functions in
.
相似文献
17.
We consider the semicontinuity of the solution set and the approximate solution set of parametric multivalued quasivariational
inequalities in topological vector spaces. Three kinds of problems arising from the multivalued situation are investigated.
A rather complete picture, which is symmetric for the two kinds of semicontinuity (lower and upper semicontinuity) and for
the three kinds of multivalued quasivariational inequality problems, is supplied. Moreover, we use a simple technique to prove
the results. The results obtained improve several known ones in the literature.
This research was partially supported by the National Basic Research Program in Natural Sciences of Vietnam. The final part
of this work was completed during a stay of the first author at the Department of Mathematics, University of Pau, Pau, France,
and its hospitality is acknowledged. 相似文献
18.
19.
The simplest way to perform a fuzzy risk assessment is to calculate the fuzzy expected value and convert fuzzy risk into non-fuzzy
risk, i.e., a crisp value. In doing so, there is a transition from the fuzzy set to the crisp set. Therefore, the first step
is to define an α level value, and then select the elements x with a subordinate degree A(x)≥α. The higher the value of α, the lower the degree of uncertainty—the probability is closer to its true value. The lower the value of α, the higher the degree of uncertainty—this results in a lower probability serviceability. The possibility level α is dependant on technical conditions and knowledge. A fuzzy expected value of the possibility-probability distribution is
a set with
and
as its boundaries. The fuzzy expected values
and
of a possibility-probability distribution represent the fuzzy risk values being calculated. Therefore, we can obtain a conservative
risk value, a venture risk value and a maximum probability risk value. Under such an α level, three risk values can be calculated. As α adopts all values throughout the set [0,1], it is possible to obtain a series of risk values. Therefore, the fuzzy risk may
be a multi-valued risk or set-valued risk. Calculation of the fuzzy expected value of flood risk in the Jinhua River basin
has been performed based on the interior-outer set model. Selection of an α value depends on the confidence in different groups of people, while selection of a conservative risk value or venture risk
value depends on the risk preference of these people. 相似文献
20.
We study constrained and unconstrained optimization programs for nonconvex maximum eigenvalue functions. We show how second
order techniques may be introduced as soon as it is possible to reliably guess the multiplicity of the maximum eigenvalue
at a limit point. We examine in which way standard and projected Newton steps may be combined with a nonsmooth first-order
method to obtain a globally convergent algorithm with a fair chance to local superlinear or quadratic convergence.
Dedicated to R. T. Rockafellar on the occasion of his 70th anniversary 相似文献