共查询到20条相似文献,搜索用时 35 毫秒
1.
E. Übi 《Central European Journal of Mathematics》2008,6(1):171-178
The strictly convex quadratic programming problem is transformed to the least distance problem — finding the solution of minimum
norm to the system of linear inequalities. This problem is equivalent to the linear least squares problem on the positive
orthant. It is solved using orthogonal transformations, which are memorized as products. Like in the revised simplex method,
an auxiliary matrix is used for computations. Compared to the modified-simplex type methods, the presented dual algorithm
QPLS requires less storage and solves ill-conditioned problems more precisely. The algorithm is illustrated by some difficult
problems.
相似文献
2.
T. B. Boffey 《TOP》1998,6(2):205-221
In recent years, interest has been shown in the optimal location of ‘extensive’ facilities in a network. Two such problems—the
Maximal Direct and Indirect Covering Tree problems—were introduced by Hutson and ReVelle. Previous solution techniques are
extended to provide an efficient algorithm for the Indirect Covering Tree problem and the generalization in which demand covered
is attenuated by distance. It is also shown that the corresponding problem is NP-hard when the underlying network is not a
tree. 相似文献
3.
Gauss—Seidel type relaxation techniques are applied in the context of strictly convex pure networks with separable cost functions. The algorithm is an extension of the Bertsekas—Tseng approach for solving the linear network problem and its dual as a pair of monotropic programming problems. The method is extended to cover the class of generalized network problems. Alternative internal tactics for the dual problem are examined. Computational experiments — aimed at the improved efficiency of the algorithm — are presented.This research was supported in part by National Science Foundation Grant No. DCR-8401098-A01. 相似文献
4.
E. Mijangos 《Journal of Optimization Theory and Applications》2006,128(1):167-190
The minimization of nonlinearly constrained network flow problems can be performed by using approximate subgradient methods.
The idea is to solve this kind of problem by means of primal-dual methods, given that the minimization of nonlinear network
flow problems can be done efficiently exploiting the network structure. In this work, it is proposed to solve the dual problem
by using ε-subgradient methods, as the dual function is estimated by minimizing approximately a Lagrangian function, which
includes the side constraints (nonnetwork constraints) and is subject only to the network constraints. Some well-known subgradient
methods are modified in order to be used as ε-subgradient methods and the convergence properties of these new methods are
analyzed. Numerical results appear very promising and effective for this kind of problems
This research was partially supported by Grant MCYT DPI 2002-03330. 相似文献
5.
Shiwei He Sohail S. Chaudhry Zhonglin Lei Wang Baohua 《Annals of Operations Research》2009,168(1):169-179
We study a vendor selection problem in which the buyer allocates an order quantity for an item among a set of suppliers such
that the required aggregate quality, service, and lead time requirements are achieved at minimum cost. Some or all of these
characteristics can be stochastic and hence, we treat the aggregate quality and service as uncertain. We develop a class of
special chance-constrained programming models and a genetic algorithm is designed for the vendor selection problem. The solution
procedure is tested on randomly generated problems and our computational experience is reported. The results demonstrate that
the suggested approach could provide managers a promising way for studying the stochastic vendor selection problem.
The authors would like to thank the referees for providing constructive comments that led to an improved version of the paper.
Also, this research was partially supported by grants from National Natural Science Foundation (60776825)—China, 863 Programs
(2007AA11Z208)—China, Doctorate Foundation (20040004012)—China, Villanova University Research Sabbatical Fall 2006, and the
National Science Foundation (0332490)—USA. 相似文献
6.
R. Andreani S. L. C. Castro J. L. Chela A. Friedlander S. A. Santos 《Computational Optimization and Applications》2009,43(3):307-328
We present a new algorithm for solving bilevel programming problems without reformulating them as single-level nonlinear programming
problems. This strategy allows one to take profit of the structure of the lower level optimization problems without using
non-differentiable methods. The algorithm is based on the inexact-restoration technique. Under some assumptions on the problem
we prove global convergence to feasible points that satisfy the approximate gradient projection (AGP) optimality condition. Computational experiments are presented that encourage the use of this method for general bilevel
problems.
This work was supported by PRONEX-Optimization (PRONEX—CNPq/FAPERJ E-26/171.164/2003—APQ1), FAPESP (Grants 06/53768-0 and
05-56773-1) and CNPq. 相似文献
7.
8.
Augusto Eusébio José Rui Figueira Matthias Ehrgott 《4OR: A Quarterly Journal of Operations Research》2009,7(3):255-273
In this paper we develop a primal–dual simplex algorithm for the bi-objective linear minimum cost network flow problem. This
algorithm improves the general primal–dual simplex algorithm for multi-objective linear programs by Ehrgott et al. (J Optim
Theory Appl 134:483–497, 2007). We illustrate the algorithm with an example and provide numerical results. 相似文献
9.
E. Mijangos 《Journal of Optimization Theory and Applications》2012,152(1):51-74
The efficiency of the network flow techniques can be exploited in the solution of nonlinearly constrained network flow problems
by means of approximate subgradient methods. The idea is to solve the dual problem by using ε-subgradient methods, where the dual function is estimated by minimizing approximately a Lagrangian function, which relaxes
the side constraints and is subject only to network constraints. In this paper, convergence results for some kind of ε-subgradient methods are put forward. Moreover, in order to evaluate the quality of the solution and the efficiency of these
methods some of them have been implemented and their performances computationally compared with codes that are able to solve
the proposed test problems. 相似文献
10.
Levent Tunçel 《Foundations of Computational Mathematics》2001,1(3):229-254
We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems
in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov
and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we
allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd
algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual
interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual
algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication
increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better
theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric
primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated
framework.
August 25, 1999. Final version received: March 7, 2001. 相似文献
11.
Jens Vygen 《Mathematical Methods of Operations Research》2002,56(1):101-126
We describe a new dual algorithm for the minimum cost flow problem. It can be regarded as a variation of the best known strongly
polynomial minimum cost flow algorithm, due to Orlin. Indeed we obtain the same running time of O(m log m(m+n log n)), where n and m denote the number of vertices and the number of edges. However, in contrast to Orlin's algorithm we work directly with the
capacitated network (rather than transforming it to a transshipment problem). Thus our algorithm is applicable to more general
problems (like submodular flow) and is likely to be more efficient in practice.
Our algorithm can be interpreted as a cut cancelling algorithm, improving the best known strongly polynomial bound for this
important class of algorithms by a factor of m. On the other hand, our algorithm can be considered as a variant of the dual network simplex algorithm. Although dual network
simplex algorithms are reportedly quite efficient in practice, the best worst-case running time known so far exceeds the running
time of our algorithm by a factor of n. 相似文献
12.
Every convex polytope can be represented as the intersection of a finite set of halfspaces and as the convex hull of its
vertices. Transforming from the halfspace (resp. vertex) to the vertex (resp. halfspace) representation is called vertex enumeration (resp. facet enumeration ). An open question is whether there is an algorithm for these two problems (equivalent by geometric duality) that is polynomial
in the input size and the output size. In this paper we extend the known polynomially solvable classes of polytopes by looking
at the dual problems. The dual problem of a vertex (resp. facet) enumeration problem is the facet (resp. vertex) enumeration problem for the same polytope
where the input and output are simply interchanged. For a particular class of polytopes and a fixed algorithm, one transformation
may be much easier than its dual. In this paper we propose a new class of algorithms that take advantage of this phenomenon.
Loosely speaking, primal—dual algorithms use a solution to the easy direction as an oracle to help solve the seemingly hard direction.
Received July 31, 1997, and in revised form March 8, 1998. 相似文献
13.
We consider a generalized equilibrium problem involving DC functions which is called (GEP). For this problem we establish
two new dual formulations based on Toland-Fenchel-Lagrange duality for DC programming problems. The first one allows us to
obtain a unified dual analysis for many interesting problems. So, this dual coincides with the dual problem proposed by Martinez-Legaz
and Sosa (J Glob Optim 25:311–319, 2006) for equilibrium problems in the sense of Blum and Oettli. Furthermore it is equivalent
to Mosco’s dual problem (Mosco in J Math Anal Appl 40:202–206, 1972) when applied to a variational inequality problem. The
second dual problem generalizes to our problem another dual scheme that has been recently introduced by Jacinto and Scheimberg
(Optimization 57:795–805, 2008) for convex equilibrium problems. Through these schemes, as by products, we obtain new optimality
conditions for (GEP) and also, gap functions for (GEP), which cover the ones in Antangerel et al. (J Oper Res 24:353–371,
2007, Pac J Optim 2:667–678, 2006) for variational inequalities and standard convex equilibrium problems. These results, in
turn, when applied to DC and convex optimization problems with convex constraints (considered as special cases of (GEP)) lead
to Toland-Fenchel-Lagrange duality for DC problems in Dinh et al. (Optimization 1–20, 2008, J Convex Anal 15:235–262, 2008),
Fenchel-Lagrange and Lagrange dualities for convex problems as in Antangerel et al. (Pac J Optim 2:667–678, 2006), Bot and
Wanka (Nonlinear Anal to appear), Jeyakumar et al. (Applied Mathematics research report AMR04/8, 2004). Besides, as consequences
of the main results, we obtain some new optimality conditions for DC and convex problems. 相似文献
14.
Based on the recent theoretical results of Zhao and Li [Math. Oper. Res., 26 (2001), pp. 119—146], we present in this paper
a new path-following method for nonlinear P* complementarity problems. Different from most existing interior-point algorithms
that are based on the central path, this algorithm tracks the “regularized central path” which exists for any continuous P*
problem. It turns out that the algorithm is globally convergent for any P* problem provided that its solution set is nonempty.
By different choices of the parameters in the algorithm, the iterative sequence can approach to different types of points
of the solution set. Moreover, local superlinear convergence of this algorithm can also be achieved under certain conditions.
The research of the first author was supported by The National Natural Science Foundation of China under Grant No. 10201032
and Grant No. 70221001. The research of the second author was supported by Grant CUHK4214/01E, Research Grants Council, Hong
Kong.
An erratum to this article is available at . 相似文献
15.
A new dual problem for convex generalized fractional programs with no duality gap is presented and it is shown how this dual
problem can be efficiently solved using a parametric approach. The resulting algorithm can be seen as “dual” to the Dinkelbach-type
algorithm for generalized fractional programs since it approximates the optimal objective value of the dual (primal) problem
from below. Convergence results for this algorithm are derived and an easy condition to achieve superlinear convergence is
also established. Moreover, under some additional assumptions the algorithm also recovers at the same time an optimal solution
of the primal problem. We also consider a variant of this new algorithm, based on scaling the “dual” parametric function.
The numerical results, in case of quadratic-linear ratios and linear constraints, show that the performance of the new algorithm
and its scaled version is superior to that of the Dinkelbach-type algorithms. From the computational results it also appears
that contrary to the primal approach, the “dual” approach is less influenced by scaling.
This research was carried out at the Econometric Institute, Erasmus University, Rotterdam, the Netherlands and was supported
by J.N.I.C.T. (Portugal) under contract BD/707/90-RM. 相似文献
16.
M. H. Schneider 《Annals of Operations Research》1986,5(1-4):439-462
In this paper, an algorithm is presented for the transshipment problem that is an adaption of the method used by Jones, Saigal,
and Schneider for solving singlecommodity, spatial-equilibrium problems. The approach uses a variable-dimension strategy in
which a sequence of subproblems is formed by solving the problem ‘one-node-at-a-time’. The algorithm is tested on uncapacitated
transportation problems. Although the computational results are not directly comparable to other methods (since the algorithm
is implemented in C under UNIX), the results show that the method is very effective and may be competitive with the best available
algorithms for linear network problems.
This research was supported, in part, by grant number ECS-8504195 from the National Science Foundation. 相似文献
17.
The response time variability problem (RTVP) is a combinatorial scheduling problem that has recently appeared in the literature.
This problem has a wide range of real life applications in fields such as manufacturing, hard real-time systems, operating
systems and network environments. Originally, the RTVP occurs whenever products, clients or jobs need to be sequenced in such
a way that the variability in the time between the instants at which they receive the necessary resources is minimized. Since
the RTVP is hard to solve, heuristic techniques are needed for solving it. Three metaheuristic—multi-start, GRASP and PSO—algorithms
proposed for solving the RTVP in two previous studies have been the most efficient to date in solving non-small instances
of the RTVP. We propose solving the RTVP by means of a psychoclonal algorithm based approach. The psychoclonal algorithm inherits
its attributes from Maslow’s hierarchy of needs theory and the artificial immune system (AIS) approach, specifically the clonal
selection principle. In this paper, we compare the proposed psychoclonal algorithm with the three aforementioned metaheuristic
algorithms and show that, on average, the psychoclonal algorithm strongly improves on the results obtained. 相似文献
18.
Dulce Rosas Jordi Castro Lídia Montero 《Computational Optimization and Applications》2009,44(2):289-313
The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel
demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem
can be formulated as a variational inequality, and several algorithms have been devised for its efficient solution. In this
work we propose a new approach that combines two existing procedures: the master problem of a simplicial decomposition algorithm
is solved through the analytic center cutting plane method. Four variants are considered for solving the master problem. The
third and fourth ones, which heuristically compute an appropriate initial point, provided the best results. The computational
experience reported in the solution of real large-scale diagonal and difficult asymmetric problems—including a subset of the
transportation networks of Madrid and Barcelona—show the effectiveness of the approach. 相似文献
19.
The adaptive algorithm for the obstacle problem presented in this paper relies on the jump residual contributions of a standard
explicit residual-based a posteriori error estimator. Each cycle of the adaptive loop consists of the steps ‘SOLVE’, ‘ESTIMATE’,
‘MARK’, and ‘REFINE’. The techniques from the unrestricted variational problem are modified for the convergence analysis to
overcome the lack of Galerkin orthogonality. We establish R-linear convergence of the part of the energy above its minimal
value, if there is appropriate control of the data oscillations. Surprisingly, the adaptive mesh-refinement algorithm is the
same as in the unconstrained case of a linear PDE—in fact, there is no modification near the discrete free boundary necessary
for R-linear convergence. The arguments are presented for a model obstacle problem with an affine obstacle χ and homogeneous
Dirichlet boundary conditions. The proof of the discrete local efficiency is more involved than in the unconstrained case.
Numerical results are given to illustrate the performance of the error estimator. 相似文献
20.
The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent
problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a
SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the
‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations
are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones.
The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal
solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenx
i=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results
cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the
supermodular ones) is exhibited. 相似文献