共查询到20条相似文献,搜索用时 15 毫秒
1.
We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron. 相似文献
2.
R. Enhbat 《Journal of Global Optimization》1996,8(4):379-391
The problem of maximizing a convex function on a so-called simple set is considered. Based on the optimality conditions [19],
an algorithm for solving the problem is proposed. This numerical algorithm is shown to be convergent. The proposed algorithm
has been implemented and tested on a variety of test problems. 相似文献
3.
A new algorithm is given for finding the convex hull of a finite set of distinct points in three-dimensional space. The algorithm finds the faces of the hull one by one, thus gradually building the polyhedron that constitutes the hull. The algorithm is described as developed through stepwise refinement. 相似文献
4.
An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints 总被引:12,自引:0,他引:12
Le Thi Hoai An 《Mathematical Programming》2000,87(3):401-426
In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids.
The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the
proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound
scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham
Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting
point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order
to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the
ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can
be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting
procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems.
Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA
and the combined DCA-branch-and-bound algorithm.
Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000 相似文献
5.
《European Journal of Operational Research》1997,101(1):155-163
In this paper, we develop an exterior point algorithm for convex quadratic programming using a penalty function approach. Each iteration in the algorithm consists of a single Newton step followed by a reduction in the value of the penalty parameter. The points generated by the algorithm follow an exterior path that we define. Convergence of the algorithm is established. The proposed algorithm was motivated by the work of Al-Sultan and Murty on nearest point problems, a special quadratic program. A preliminary implementation of the algorithm produced encouraging results. In particular, the algorithm requires a small and almost constant number of iterations to solve the small to medium size problems tested. 相似文献
6.
Neyman-Pearson classification has been studied in several articles before.But they all proceeded in the classes of indicator functions with indicator function as the loss function,which make the calculation to be difficult.This paper investigates NeymanPearson classification with convex loss function in the arbitrary class of real measurable functions.A general condition is given under which Neyman-Pearson classification with convex loss function has the same classifier as that with indicator loss function.We give analysis to NP-ERM with convex loss function and prove it's performance guarantees.An example of complexity penalty pair about convex loss function risk in terms of Rademacher averages is studied,which produces a tight PAC bound of the NP-ERM with convex loss function. 相似文献
7.
A stochastic quasigradient algorithm is suggested for solving the quantile optimization problem with a convex loss function. The algorithm is based on stochastic finite-difference approximations of gradients of the quantile function by using the order statistics. The algorithm convergence almost surely is proved. 相似文献
8.
9.
Summary Suppose each member of a team observes aBernoulli random variable,x, and the team outcome is the inner product, a,x, of the observation vectorx and the decision vectora. This paper considers the case when the loss function is convex. Two numerical examples are given.
A Marketing Team
Research supported in part by Deutsche Forschungsgemeinschaft while the first author was a guest professor at the Institut für Angewandte Mathematik, Universität Heidelberg. Additional support came from Studiengruppe für Systemforschung, Heidelberg. 相似文献
Zusammenfassung Angenommen, jedes Mitglied eines Teams beobachtet eineBernoulli-verteilte Zufallsvariablex und das Team-Ergebnis besteht aus dem skalaren Produkt a,x des Beobachtungsvektorsx und des Entscheidungsvektorsa. Die vorliegende Arbeit behandelt den Fall, bei dem die Nutzenfunktion konvex ist. Zwei numerische Beispiele werden vorgeführt.
A Marketing Team
Research supported in part by Deutsche Forschungsgemeinschaft while the first author was a guest professor at the Institut für Angewandte Mathematik, Universität Heidelberg. Additional support came from Studiengruppe für Systemforschung, Heidelberg. 相似文献
10.
Pravin M. Vaidya 《Mathematical Programming》1996,73(3):291-341
Let
be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ
n
the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid
of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global
convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts
to the convex optimization problem. 相似文献
11.
This paper presents an algorithm for the solution of a simpleconvex optimization problem. This problem is a generalizationof several other optimization problems which have applicationsto resource allocation, optimal capacity expansion, and vehiclescheduling. The algorithm is based on a constraint-relaxationapproach. It is easily implemented and transparent, and canbe used to solve even fairly large problems by hand calculator. 相似文献
12.
An efficient and numerically correct program called FastHull for computing the convex hulls of finite point sets in the plane is presented. It is based on the Akl-Toussaint algorithm and the MergeHull algorithm. Numerical correctness of the FastHull procedure is ensured by using special routines for interval arithmetic and multiple precision arithmetic. The FastHull algorithm guaranteesO(N logN) running time in the worst case and has linear time performance for many kinds of input patterns. It appears that the FastHull algorithm runs faster than any currently known 2D convex hull algorithm for many input point patterns. 相似文献
13.
Yu. I. Ingster 《Journal of Mathematical Sciences》1999,93(3):354-371
We study a wide class of minimax problems of signal detection under nonparametric alternatives and a modification of these
problems for a special class of loss functions. Under rather general assumptions, we obtain the exact asymptotics (of Gaussian
type) for the minimax error probabilities and the structure of asymptotically minimax tests. The methods are based on a reduction
of the problems under consideration to extremal problems of minimization of a certain Hilbert norm on a convex set of sequences
of probability measures on the real line. These extremal problems are investigated in a paper by I. A. Suslina for alternatives
having the type of lq-ellipsoids with lp-balls removed. Bibliography: 16 titles.
Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 228, 1996, pp. 162–188. 相似文献
14.
Zhongyi Liu Yue Chen Wenyu Sun Zhihui Wei 《Computational Optimization and Applications》2012,52(2):373-391
Recently an infeasible interior-point algorithm for linear programming (LP) was presented by Liu and Sun. By using similar predictor steps, we give a (feasible) predictor-corrector algorithm for convex quadratic programming (QP). We introduce a (scaled) proximity measure and a dynamical forcing factor (centering parameter). The latter is used to force the duality gap to decrease. The algorithm can decrease the duality gap monotonically. Polynomial complexity can be proved and the result coincides with the best one for LP, namely, $O(\sqrt{n}\log n\mu^{0}/\varepsilon)$ . 相似文献
15.
Masao Fukushima Mounir Haddou Hien Van Nguyen Jean-Jacques Strodiot Takanobu Sugimoto Eiki Yamakawa 《Computational Optimization and Applications》1996,5(1):5-37
In this paper, we propose a parallel decomposition algorithm for solving a class of convex optimization problems, which is broad enough to contain ordinary convex programming problems with a strongly convex objective function. The algorithm is a variant of the trust region method applied to the Fenchel dual of the given problem. We prove global convergence of the algorithm and report some computational experience with the proposed algorithm on the Connection Machine Model CM-5. 相似文献
16.
A descent algorithm for nonsmooth convex optimization 总被引:1,自引:0,他引:1
Masao Fukushima 《Mathematical Programming》1984,30(2):163-175
This paper presents a new descent algorithm for minimizing a convex function which is not necessarily differentiable. The
algorithm can be implemented and may be considered a modification of the ε-subgradient algorithm and Lemarechal's descent
algorithm. Also our algorithm is seen to be closely related to the proximal point algorithm applied to convex minimization
problems. A convergence theorem for the algorithm is established under the assumption that the objective function is bounded
from below. Limited computational experience with the algorithm is also reported. 相似文献
17.
We present an efficient algorithm for planning the motion of a convex polygonal bodyB in two-dimensional space bounded by a collection of polygonal obstacles. Our algorithm extends and combines the techniques of Leven and Sharir and of Sifrony and Sharir used for the case in whichB is a line segment (a ladder). It also makes use of the results of Kedem and Sharir on the planning of translational motion ofB amidst polygonal obstacles, and of a recent result of Leven and Sharir on the number of free critical contacts ofB with such polygonal obstacles. The algorithm runs in timeO(kn
6(kn) logkn), wherek is the number of sides ofB, n is the number of obstacle edges, and ,(q) is an almost linear function ofq yielding the maximal number of connected portions ofq continuous functions which compose the graph of their lower envelope, where it is assumed that each pair of these functions intersect in at mosts points.Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. 相似文献
18.
Manuel J. Carrillo 《Mathematical Programming》1977,13(1):69-80
A study was made of the global minimization of a general quasiconcave function on a convex polyhedron. This nonconvex problem arises in economies of scale environments and in alternative formulations of other well-known problems, as in the case of bilinear programming.Although not very important in our final results, a local minimum can be easily obtained. However, a major aspect is the existence of two families of lower bounds on the optimal functional value: one is provided by non-linear programming duality, the other is derived from a lexicographic ordering of basic solutions which allows the use of relaxation concepts. These results were exploited in a finite algorithm for obtaining the global minimum whose initial implementation has had encouraging performance. 相似文献
19.
Willem K. Klein Haneveld Leen Stougie Maarten H. van der Vlerk 《Annals of Operations Research》1996,64(1):67-81
We consider the objective function of a simple integer recourse problem with fixed technology matrix and discretely distributed right-hand sides. Exploiting the special structure of this problem, we devise an algorithm that determines the convex hull of this function efficiently. The results are improvements over those in a previous paper. In the first place, the convex hull of many objective functions in the class is covered, instead of only one-dimensional versions. In the second place, the algorithm is faster than the one in the previous paper. Moreover, some new results on the structure of the objective function are presented. 相似文献
20.
A customized proximal point algorithm for convex minimization with linear constraints 总被引:1,自引:0,他引:1
Bingsheng He Xiaoming Yuan Wenxing Zhang 《Computational Optimization and Applications》2013,56(3):559-572
This paper demonstrates a customized application of the classical proximal point algorithm (PPA) to the convex minimization problem with linear constraints. We show that if the proximal parameter in metric form is chosen appropriately, the application of PPA could be effective to exploit the simplicity of the objective function. The resulting subproblems could be easier than those of the augmented Lagrangian method (ALM), a benchmark method for the model under our consideration. The efficiency of the customized application of PPA is demonstrated by some image processing problems. 相似文献