共查询到20条相似文献,搜索用时 15 毫秒
1.
《Journal of Complexity》2001,17(2):306-344
In this paper we describe an adaptive algorithm for approximating the global minimum of a continuous function on the unit interval, motivated by viewing the function as a sample path of a Wiener process. It operates by choosing the next observation point to maximize the probability that the objective function has a value at that point lower than an adaptively chosen threshold. The error converges to zero for any continuous function. Under the Wiener measure, the error converges to zero at rate e−nδn, where {δn} (a parameter of the algorithm) is a positive sequence converging to zero at an arbitrarily slow rate. 相似文献
2.
B. S. Goh 《Journal of Optimization Theory and Applications》2011,148(3):505-527
In an optimization problem with equality constraints the optimal value function divides the state space into two parts. At
a point where the objective function is less than the optimal value, a good iteration must increase the value of the objective function. Thus, a good iteration must be a balance between increasing or decreasing the objective
function and decreasing a constraint violation function. This implies that at a point where the constraint violation function
is large, we should construct noninferior solutions relative to points in a local search region. By definition, an accessory
function is a linear combination of the objective function and a constraint violation function. We show that a way to construct
an acceptable iteration, at a point where the constraint violation function is large, is to minimize an accessory function.
We develop a two-phases method. In Phase I some constraints may not be approximately satisfied or the current point is not
close to the solution. Iterations are generated by minimizing an accessory function. Once all the constraints are approximately
satisfied, the initial values of the Lagrange multipliers are defined. A test with a merit function is used to determine whether
or not the current point and the Lagrange multipliers are both close to the optimal solution. If not, Phase I is continued.
If otherwise, Phase II is activated and the Newton method is used to compute the optimal solution and fast convergence is
achieved. 相似文献
3.
The Fermat—Weber location problem is to find a point in
n
that minimizes the sum of the weighted Euclidean distances fromm given points in
n
. A popular iterative solution method for this problem was first introduced by Weiszfeld in 1937. In 1973 Kuhn claimed that if them given points are not collinear then for all but a denumerable number of starting points the sequence of iterates generated by Weiszfeld's scheme converges to the unique optimal solution. We demonstrate that Kuhn's convergence theorem is not always correct. We then conjecture that if this algorithm is initiated at the affine subspace spanned by them given points, the convergence is ensured for all but a denumerable number of starting points. 相似文献
4.
Sh. A. Alimov 《Differential Equations》2010,46(6):827-839
We consider the expansion of a piecewise smooth function depending on the geodesic distance to some point in the eigenfunctions
of the Beltrami-Laplace operator on an n-dimensional symmetric space of rank 1. We show that if the expansion converges at this point, then the function must have
continuous derivatives up to and including the order (n − 3)/2. 相似文献
5.
Elisabeth Gassner 《Annals of Operations Research》2009,172(1):393-404
This paper deals with downgrading the 1-median, i.e., changing values of parameters within certain bounds such that the optimal
objective value of the location problem with respect to the new values is maximized. We suggest a game-theoretic view at this
problem which leads to a characterization of an optimal solution. This approach is demonstrated by means of the Downgrading
1-median problem in the plane with Manhattan metric and implies an O(nlog2n)\mathcal {O}(n\log^{2}n) time algorithm for this problem. 相似文献
6.
U. Helmke K. Hüper J.B. Moore Th. Schulte-Herbrüggen 《Journal of Global Optimization》2002,23(3-4):283-308
In this paper gradient flows on unitary matrices are studied that maximize the real part of the C-numerical range of an arbitrary complex n×n-matrix A. The geometry of the C-numerical range can be quite complicated and is only partially understood. A numerical discretization scheme of the gradient flow is presented that converges to the set of critical points of the cost function. Special emphasis is taken on a situation arising in NMR spectroscopy where the matrices C,A are nilpotent and the C-numerical range is a circular disk in the complex plane around the origin. 相似文献
7.
Zi-Luan Wei 《计算数学(英文版)》1987,5(4):342-351
In this paper we present an interior point method which solves a linear programming problem by using an affine transformation. We prove under certain assumptions that the algorithm converges to an optimal solution even if the dual problem is degenerate as long as the prime is bounded, or to a ray direction if the optimal value of the objective function is unbounded. 相似文献
8.
魏紫銮 《应用数学学报(英文版)》2001,17(3):366-374
1. IntroductionThe quadratic programming (QP) problem is the most simple one in nonlinear pro-gramming and plays a very important role in optimization theory and applications.It is well known that matriX splitting teChniques are widely used for solving large-scalelinear system of equations very successfully. These algorithms generate an infinite sequence,in contrast to the direct algorithms which terminate in a finite number of steps. However,iterative algorithms are considerable simpler tha… 相似文献
9.
Zvi Drezner 《Annals of Operations Research》2009,167(1):327-336
In this paper we consider Weber-like location problems. The objective function is a sum of terms, each a function of the Euclidean
distance from a demand point. We prove that a Weiszfeld-like iterative procedure for the solution of such problems converges
to a local minimum (or a saddle point) when three conditions are met. Many location problems can be solved by the generalized
Weiszfeld algorithm. There are many problem instances for which convergence is observed empirically. The proof in this paper
shows that many of these algorithms indeed converge. 相似文献
10.
We study the existence and structure of extremals for one-dimensional variational problems on a torus and the properties of the minimal average action as a function of the rotation number. We show that, for a generic integrand f, the minimum of the minimal average action is attained at a rational point mn
–1 where n1 and m are integers; also, for each initial value, there exists an (f)-weakly optimal solution over an infinite horizon. 相似文献
11.
Charles Audet Pierre Hansen Frédéric Messine 《Discrete and Computational Geometry》2009,41(2):208-215
A polygon is said to be simple if the only points of the plane belonging to two of its edges are its vertices. We answer the question of finding, for a
given integer n, a simple n-sided polygon contained in a disk of radius 1 that has the longest perimeter. When n is even, the optimal solution is arbitrarily close to a line segment of length 2n. When n is odd, the optimal solution is arbitrarily close to an isosceles triangle.
Work of the first author was supported by NSERC grant 239436-05, AFOSR FA9550-07-1-0302, and ExxonMobil. Work of the second
author was supported by NSERC grant 105574-02. 相似文献
12.
Fern Sassower Sisser 《Mathematical Programming》1981,20(1):110-121
The problem of minimizing a nonlinear objective function ofn variables, with continuous first and second partial derivatives, subject to nonnegativity constraints or upper and lower bounds on the variables is studied. The advisability of solving such a constrained optimization problem by making a suitable transformation of its variables in order to change the problem into one of unconstrained minimization is considered. A set of conditions which guarantees that every local minimum of the new unconstrained problem also satisfies the first-order necessary (Kuhn—Tucker) conditions for a local minimum of the original constrained problem is developed. It is shown that there are certain conditions under which the transformed objective function will maintain the convexity of the original objective function in a neighborhood of the solution. A modification of the method of transformations which moves away from extraneous stationary points is introduced and conditions under which the method generates a sequence of points which converges to the solution at a superlinear rate are given. 相似文献
13.
Paul Tseng 《Journal of Global Optimization》2004,30(2):285-300
We study convergence properties of Dikins affine scaling algorithm applied to nonconvex quadratic minimization. First, we show that the objective function value either diverges or converges Q-linearly to a limit. Using this result, we show that, in the case of box constraints, the iterates converge to a unique point satisfying first-order and weak second-order optimality conditions, assuming the objective function Hessian Q is rank dominant with respect to the principal submatrices that are maximally positive semidefinite. Such Q include matrices that are positive semidefinite or negative semidefinite or nondegenerate or have negative diagonals. Preliminary numerical experience is reported. 相似文献
14.
Paulo Barcia 《Operations Research Letters》1985,4(1):27-30
The purpose of this paper is to report on a new tool to help solve 0–1 LP's. It consists of a sequence of bounds that, under proper conditions, bridge the duality gap, i.e., converges in a finite number of steps to the optimal value of the objective function of the problem studied. As a by-product an optimal solution for that problem is produced. Computational experience is reported. 相似文献
15.
A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities. 相似文献
16.
Earl R. Barnes 《Mathematical Programming》1986,36(2):174-182
The algorithm described here is a variation on Karmarkar’s algorithm for linear programming. It has several advantages over
Karmarkar’s original algorithm. In the first place, it applies to the standard form of a linear programming problem and produces
a monotone decreasing sequence of values of the objective function. The minimum value of the objective function does not have
to be known in advance. Secondly, in the absence of degeneracy, the algorithm converges to an optimal basic feasible solution
with the nonbasic variables converging monotonically to zero. This makes it possible to identify an optimal basis before the
algorithm converges. 相似文献
17.
We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{p, n − p}n3m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network. 相似文献
18.
Lisa Lorentzen 《The Ramanujan Journal》2007,13(1-3):253-263
We consider linear fractional transformations T
n which map the unit disk U into itself with the property that
for all n. Clearly, the closed sets
form a nested sequence of circular disks, and thus has a non-empty limit set
. If this limit set is a single point, then {T
n(w)} converges uniformly in $\overline U$ to this point. In this paper we study what happens if the limit set has a positive
radius. In particular we prove that under specific conditions, the derivatives satisfy
for w∈ U and {T
n(w)} still converges locally uniformly in U to a constant function. Results of this type are useful in the theories of dynamical systems and continued fractions.
Dedicated to Richard Askey on the occasion of his 70th birthday.
2000 Mathematics Subject Classification Primary—20H15, 30D05, 37F10; Secondary—30B70, 39B12, 40A15 相似文献
19.
In this paper we propose an extension of proximal methods to solve minimization problems with quasiconvex objective functions on the nonnegative orthant. Assuming that the function is bounded from below and lower semicontinuous and using a general proximal distance, it is proved that the iterations given by our algorithm are well defined and stay in the positive orthant. If the objective function is quasiconvex we obtain the convergence of the iterates to a certain set which contains the set of optimal solutions and convergence to a KKT point if the function is continuously differentiable and the proximal parameters are bounded. Furthermore, we introduce a sufficient condition on the proximal distance such that the sequence converges to an optimal solution of the problem. 相似文献
20.
In this paper, we consider a Lipschitz optimization problem (LOP) constrained by linear functions in Rn. In general, since it is hard to solve (LOP) directly, (LOP) is transformed into a certain problem (MP) constrained by a ball in Rn+1. Despite there is no guarantee that the objective function of (MP) is quasi-convex, by using the idea of the quasi-conjugate function defined by Thach (1991) [1], we can construct its dual problem (DP) as a quasi-convex maximization problem. We show that the optimal value of (DP) coincides with the multiplication of the optimal value of (MP) by −1, and that each optimal solution of the primal and dual problems can be easily obtained by the other. Moreover, we formulate a bidual problem (BDP) for (MP) (that is, a dual problem for (DP)). We show that the objective function of (BDP) is a quasi-convex function majorized by the objective function of (MP) and that both optimal solution sets of (MP) and (BDP) coincide. Furthermore, we propose an outer approximation method for solving (DP). 相似文献