共查询到20条相似文献,搜索用时 15 毫秒
1.
Sung-Pil Hong 《Discrete Applied Mathematics》2008,156(1):25-41
We present a unifying framework to establish a lower bound on the number of semidefinite-programming-based lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by Lovász and Schrijver and have been used usually implicitly in the previous lower-bound analyses. In this paper, we formalize the lift-and-project commutative maps and propose a general framework for lower-bound analysis, in which we can recapture many of the previous lower-bound results on the lift-and-project ranks. 相似文献
2.
Renaud Sirdey 《4OR: A Quarterly Journal of Operations Research》2007,5(4):319-333
The purpose of this paper is to illustrate the diversity of combinatorial problems encountered in the design of wireless switching
systems. This is done via a representative selection of examples of real problems along with their associated solution methods. It should be emphasized that all the solution methods presented in
this paper are successfully operating in the field at the time of writing.
To the memory of my beloved father, French Navy Admiral Christian Sirdey, whose life was cut short by cancer on November the
13th, 2006. 相似文献
3.
This paper is devoted to the continuity of solution maps for perturbation semi-infinite vector optimization problems without compact constraint sets. The sufficient conditions for lower semicontinuity and upper semicontinuity of solution maps under functional perturbations of both objective functions and constraint sets are established. Some examples are given to analyze the assumptions in the main result. 相似文献
4.
This is a review of the literature on parallel computers and algorithms that is relevant for combinatorial optimization. We start by describing theoretical as well as realistic machine models for parallel computations. Next, we deal with the complexity theory for parallel computations and illustrate the resulting concepts by presenting a number of polylog parallel algorithms andP-completeness results. Finally, we discuss the use of parallelism in enumerative methods. 相似文献
5.
Alfredo N. Iusem 《Acta Appl Math》1995,38(2):163-184
We analyze an algorithm for the problem minf(x) s.t.x 0 suggested, without convergence proof, by Eggermont. The iterative step is given by x
j
k+1
=x
j
k
(1-kf(x
k)j) with k > 0 determined through a line search. This method can be seen as a natural extension of the steepest descent method for unconstrained optimization, and we establish convergence properties similar to those known for steepest descent, namely weak convergence to a KKT point for a generalf, weak convergence to a solution for convexf and full convergence to the solution for strictly convexf. Applying this method to a maximum likelihood estimation problem, we obtain an additively overrelaxed version of the EM Algorithm. We extend the full convergence results known for EM to this overrelaxed version by establishing local Fejér monotonicity to the solution set.Research for this paper was partially supported by CNPq grant No 301280/86. 相似文献
6.
A numerical approach to optimization problems with variational inequality constraints 总被引:7,自引:0,他引:7
Optimization problems with variational inequality constraints are converted to constrained minimization of a local Lipschitz function. To this minimization a non-differentiable optimization method is used; the required subgradients of the objective are computed by means of a special adjoint equation. Besides tests with some academic examples, the approach is applied to the computation of the Stackelberg—Cournot—Nash equilibria and to the numerical solution of a class of quasi-variational inequalities.Corresponding author. 相似文献
7.
P.Q. KhanhN.D. Tuan 《Nonlinear Analysis: Theory, Methods & Applications》2011,74(13):4338-4351
Second-order necessary conditions and sufficient conditions for optimality in nonsmooth vector optimization problems with inclusion constraints are established. We use approximations as generalized derivatives and avoid even continuity assumptions. Convexity conditions are not imposed explicitly. Not all approximations in use are required to be bounded. The results improve or include several recent existing ones. Examples are provided to show that our theorems are easily applied in situations where several known results do not work. 相似文献
8.
L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method
is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method
also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in
perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for
the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields
a proof that weighted fractional chromatic number is NP-hard.
Research by the third author was supported by the Netherlands Organisation for the Advancement of Pure Research (Z.W.O.). 相似文献
9.
Truong Xuan Duc Ha 《Nonlinear Analysis: Theory, Methods & Applications》2012,75(3):1305-1323
We present a new approach to the study of a set-valued equilibrium problem (for short, SEP) through the study of a set-valued optimization problem with a geometric constraint (for short, SOP) based on an equivalence between solutions of these problems. As illustrations, we adapt to SEP enhanced notions of relative Pareto efficient solutions introduced in set optimization by Bao and Mordukhovich and derive from known or new optimality conditions for various efficient solutions of SOP similar results for solutions of SEP as well as for solutions of a vector equilibrium problem and a vector variational inequality.We also introduce the concept of quasi weakly efficient solutions for the above problems and divide all efficient solutions under consideration into the Pareto-type group containing Pareto efficient, primary relative efficient, intrinsic relative efficient, quasi relative efficient solutions and the weak Pareto-type group containing quasi weakly efficient, weakly efficient, strongly efficient, positive properly efficient, Henig global properly efficient, Henig properly efficient, super efficient and Benson properly efficient solutions. The necessary conditions for Pareto-type efficient solutions and necessary/sufficient conditions for weak Pareto-type efficient solutions formulated here are expressed in terms of the Ioffe approximate coderivative and normal cone in the Banach space setting and in terms of the Mordukhovich coderivative and normal cone in the Asplund space setting. 相似文献
10.
11.
The max-bisection problem is an NP-hard combinatorial optimization problem. In this paper, a new Lagrangian net algorithm is proposed to solve max-bisection problems. First, we relax the bisection constraints to the objective function by introducing the penalty function method. Second, a bisection solution is calculated by a discrete Hopfield neural network (DHNN). The increasing penalty factor can help the DHNN to escape from the local minimum and to get a satisfying bisection. The convergence analysis of the proposed algorithm is also presented. Finally, numerical results of large-scale G-set problems show that the proposed method can find a better optimal solutions. 相似文献
12.
Bernard Fortz 《Operations Research Letters》2010,38(6):545-549
We show how we can linearize individual probabilistic linear constraints with binary variables when all coefficients are independently distributed according to either N(μi,λμi), for some λ>0 and μi>0, or Γ(ki,θ) for some θ>0 and ki>0. The constraint can also be linearized when the coefficients are independent and identically distributed and either positive or strictly stable random variables. 相似文献
13.
We examine a notion of generalized convex set-valued mapping, extending the notions of a convex relation and a convex process. Under general conditions, we establish duality results for composite set-valued mappings and for convex programming problems involving convex set-valued mappings. We also present applications to the study of economic dynamical systems, by obtaining the characteristics of optimal paths generated by convex processes, and to optimization problems of a certain class of positively homogeneous increasing functions. 相似文献
14.
In this paper we study divisible load scheduling in systems with limited memory. Divisible loads are parallel computations which can be divided into independent parts processed in parallel on remote computers, and the part sizes may be arbitrary. The distributed system is a heterogeneous single level tree. The total size of processor memories is too small to accommodate the whole load at any moment of time. Therefore, the load is distributed in many rounds. Memory reservations have block nature. The problem consists in distributing the load taking into account communication time, computation time, and limited memory buffers so that the whole processing finishes as early as possible. This problem is both combinatorial and algebraic in nature. Therefore, hybrid algorithms are given to solve it. Two algorithms are proposed to solve the combinatorial component. A branch-and-bound algorithm is nearly unusable due to its complexity. Then, a genetic algorithm is proposed with more tractable execution times. For a given solution of the combinatorial part we formulate the solution of the algebraic part as a linear programming problem. An extensive computational study is performed to analyze the impact of various system parameters on the quality of the solutions. From this we were able to infer on the nature of the scheduling problem. 相似文献
15.
Expressions for subdifferential and optimization problems defined by nonsmooth homogeneous functions
In this paper, we prove a theoretical expression for subdifferentials of lower semicontinuous and homogeneous functions. The theoretical expression is a generalization of the Euler formula for differentiable homogeneous functions. As applications of the generalized Euler formula, we consider constrained optimization problems defined by nonsmooth positively homogeneous functions in smooth Banach spaces. Some results concerning Karush–Kuhn–Tucker points and necessary optimality conditions for the optimization problems are obtained. 相似文献
16.
In this paper we study mathematical programming problems with mixed constraints in a Banach space and show that most of the problems (in the Baire category sense) are well-posed. Our result is a generalization of a result of Ioffe et al. [SIAM J. Optim. 12 (2001) 461–478] obtained for finite-dimensional Banach spaces. 相似文献
17.
Fuzzy optimization conditions in terms of the Fréchet subdifferential for reflexive spaces were investigated by Borwein, Treiman and Zhu (1998) in [1]. To achieve the nondegenerate form, it is well known that some qualification conditions should be assumed. In this paper, we are going to prove that the nondegenerate fuzzy optimality condition even holds with no qualification conditions in Asplund spaces (in particular, reflexive spaces) for optimization problems with semi-continuous and continuous data. The results are even new in finite-dimensional frameworks. 相似文献
18.
Yigui Ou Author Vitae Qian Zhou Haichan Lin 《Journal of Computational and Applied Mathematics》2009,232(2):318-326
In this paper, a new trust region algorithm is proposed for solving unconstrained optimization problems. This method can be regarded as a combination of trust region technique, fixed step-length and ODE-based methods. A feature of this proposed method is that at each iteration, only a system of linear equations is solved to obtain a trial step. Another is that when a trial step is not accepted, the method generates an iterative point whose step-length is defined by a formula. Under some standard assumptions, it is proven that the algorithm is globally convergent and locally superlinear convergent. Preliminary numerical results are reported. 相似文献
19.
An implementable augmented Lagrange method for solving fixed point problems with coupled constraints
Li Wang Feng ShanLiwei Zhang 《Nonlinear Analysis: Theory, Methods & Applications》2011,74(5):1761-1768
An augmented Lagrange function method for solving fixed point problems with coupled constraints is studied, and a theorem of its global convergence is demonstrated. The semismooth Newton method is used to solve the inner problems for obtaining approximate solutions, and numerical results are reported to verify the effectiveness of the augmented Lagrange function method for solving three examples with more than 1000 variables. 相似文献
20.
An error in the proof, and in the statement of a generalization, of the result that submodular setfunctions can be minimized
over the subsets with odd cardinality is corrected. 相似文献