共查询到20条相似文献,搜索用时 31 毫秒
1.
UOBYQA: unconstrained optimization by quadratic approximation 总被引:5,自引:0,他引:5
M.J.D. Powell 《Mathematical Programming》2002,92(3):555-582
UOBYQA is a new algorithm for general unconstrained optimization calculations, that takes account of the curvature of the
objective function, F say, by forming quadratic models by interpolation. Therefore, because no first derivatives are required, each model is defined
by ?(n+1)(n+2) values of F, where n is the number of variables, and the interpolation points must have the property that no nonzero quadratic polynomial vanishes
at all of them. A typical iteration of the algorithm generates a new vector of variables,
t
say, either by minimizing the quadratic model subject to a trust region bound, or by a procedure that should improve the
accuracy of the model. Then usually F(
t
) is obtained, and one of the interpolation points is replaced by
t
. Therefore the paper addresses the initial positions of the interpolation points, the adjustment of trust region radii, the
calculation of
t
in the two cases that have been mentioned, and the selection of the point to be replaced. Further, UOBYQA works with the
Lagrange functions of the interpolation equations explicitly, so their coefficients are updated when an interpolation point
is moved. The Lagrange functions assist the procedure that improves the model, and also they provide an estimate of the error
of the quadratic approximation to F, which allows the algorithm to achieve a fast rate of convergence. These features are discussed and a summary of the algorithm
is given. Finally, a Fortran implementation of UOBYQA is applied to several choices of F, in order to investigate accuracy, robustness in the presence of rounding errors, the effects of first derivative discontinuities,
and the amount of work. The numerical results are very promising for n≤20, but larger values are problematical, because the routine work of an iteration is of fourth order in the number of variables.
Received: December 7, 2000 / Accepted: August 31, 2001?Published online April 12, 2002 相似文献
2.
Generalizing a classical idea of Biermann, we study a way of constructing a unisolvent array for Lagrange interpolation in Cn+m out of two suitably ordered unisolvent arrays respectively in Cn and Cm. For this new array, important objects of Lagrange interpolation theory (fundamental Lagrange polynomials, Newton polynomials, divided difference operator, vandermondian, etc.) are computed.
AMS subject classification 41A05, 41A63 相似文献
3.
A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function)
defined on the convex hull of m points in R
n
is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial
cone in R
m
, which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates.
It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating
with the optimal solution. 相似文献
4.
杨松林 《高等学校计算数学学报》2005,27(1):1-6
The matrix valued rational interpolation is very useful in the partial realization problem and model reduction for all the linear system theory. Lagrange basic functions have been used in matrix valued rational interpolation. In this paper, according to the property of cardinal spline interpolation, we constructed a kind of spline type matrix valued rational interpolation, which based on cardinal spline. This spline type interpolation can avoid instability of high order polynomial interpolation and we obtained a useful formula. 相似文献
5.
This paper studies some cases of (0,m)-interpolation on non-uniformly distributed roots of unity that were not covered before. The interpolation problem uses as nodes the zeros of (z
k
+1)(z
3–1) with k=3n+1, 3n+2. Proof of the regularity is more intricate than when k is divisible by 3, the case included in a previous paper by the authors. The interpolation problem appears to be regular for mk+3, a result that is in tune with the case k=3n mentioned before. However, it is necessary to treat the full general 18×18 linear system. For small values of m the determinant is calculated explicitly using MAPLE V, Release 5. 相似文献
6.
Eng-Wee Chionh 《Advances in Computational Mathematics》2003,19(4):373-383
It is known that the Dixon matrix can be constructed in parallel either by entry or by diagonal. This paper presents another parallel matrix construction, this time by bracket. The parallel by bracket algorithm is the fastest among the three, but not surprisingly it requires the highest number of processors. The method also shows analytically that the Dixon matrix has a total of m(m+1)2(m+2)n(n+1)2(n+2)/36 brackets but only mn(m+1)(n+1)(mn+2m+2n+1)/6 of them are distinct. 相似文献
7.
Lagrange基函数的复矩阵有理插值及连分式插值 总被引:1,自引:0,他引:1
顾传青 《高等学校计算数学学报》1998,20(4):306-314
1引言 矩阵有理插值问题与系统线性理论中的模型简化问题和部分实现问题有着紧密的联系~[1][2],在矩阵外推方法中也常常涉及线性或有理矩阵插值问题~[3]。按照文~[1]的阐述。目前已经研究的矩阵有理插值问题包括矩阵幂级数和Newton-Pade逼近。Hade逼近,联立Pade逼近,M-Pade逼近,多点Pade逼近等。显然,上述各种形式的矩阵Pade逼上梁山近是矩 相似文献
8.
Carl Bracken Eimear Byrne Gary McGuire Gabriele Nebe 《Designs, Codes and Cryptography》2011,61(3):261-272
Establishing the CCZ-equivalence of a pair of APN functions is generally quite difficult. In some cases, when seeking to show
that a putative new infinite family of APN functions is CCZ inequivalent to an already known family, we rely on computer calculation
for small values of n. In this paper we present a method to prove the inequivalence of quadratic APN functions with the Gold functions. Our main
result is that a quadratic function is CCZ-equivalent to the APN Gold function x2r+1{x^{2^r+1}} if and only if it is EA-equivalent to that Gold function. As an application of this result, we prove that a trinomial family
of APN functions that exist on finite fields of order 2
n
where n ≡ 2 mod 4 are CCZ inequivalent to the Gold functions. The proof relies on some knowledge of the automorphism group of a code
associated with such a function. 相似文献
9.
Interpolation-based trust-region methods are an important class of algorithms for Derivative-Free Optimization which rely on locally approximating an objective function by quadratic polynomial interpolation models, frequently built from less points than there are basis components. Often, in practical applications, the contribution of the problem variables to the objective function is such that many pairwise correlations between variables are negligible, implying, in the smooth case, a sparse structure in the Hessian matrix. To be able to exploit Hessian sparsity, existing optimization approaches require the knowledge of the sparsity structure. The goal of this paper is to develop and analyze a method where the sparse models are constructed automatically. The sparse recovery theory developed recently in the field of compressed sensing characterizes conditions under which a sparse vector can be accurately recovered from few random measurements. Such a recovery is achieved by minimizing the ℓ 1-norm of a vector subject to the measurements constraints. We suggest an approach for building sparse quadratic polynomial interpolation models by minimizing the ℓ 1-norm of the entries of the model Hessian subject to the interpolation conditions. We show that this procedure recovers accurate models when the function Hessian is sparse, using relatively few randomly selected sample points. Motivated by this result, we developed a practical interpolation-based trust-region method using deterministic sample sets and minimum ℓ 1-norm quadratic models. Our computational results show that the new approach exhibits a promising numerical performance both in the general case and in the sparse one. 相似文献
10.
《European Journal of Operational Research》2001,130(2):276-304
We develop a model for constructing quadratic objective functions in n target variables. At the input, a decision maker is asked a few simple questions about his ordinal preferences (comparing two-dimensional alternatives in terms `better', `worse', `indifferent'). At the output, the model mathematically derives a quadratic objective function used to evaluate n-dimensional alternatives.Thus the model deals with some imaginary decisions (criteria aggregates) at the input, and disaggregates the decision maker's preference into partial criteria and their cross-correlations (=a quadratic objective function). Therefore, the model provides an approximation step which is next to the disaggregation of a preference into additively separable linear criteria with weight coefficients.The model is based on least squares fitting a quadratic indifference hypersurface (if n=2, indifference curve) to several alternatives which are supposed to be equivalent in preference. The resulting ordinal preference is independent of the cardinal utility scale used in intermediate computations which implies that the model is ordinal. The monotonicity of the quadratic objective function is implemented by means of a finite number of linear constraints, so that the computational model is reduced to restricted least squares.In illustration, we construct a quadratic objective function of German economic policy in four target variables: inflation, unemployment, GNP growth, and increase in public debt. This objective function is used to evaluate the German economic development in 1980–1994.In another application, we construct a quadratic objective function of ski station customers. Then it is used to adjust prices of 10 ski stations to the South of Stuttgart.In Appendix A we provide an original fast algorithm for restricted least squares and quadratic programming used in the main model. 相似文献
11.
S. S. Oren 《Journal of Optimization Theory and Applications》1984,43(2):167-204
A new class of quasi-Newton methods is introduced that can locate a unique stationary point of ann-dimensional quadratic function in at mostn steps. When applied to positive-definite or negative-definite quadratic functions, the new class is identical to Huang's symmetric family of quasi-Newton methods (Ref. 1). Unlike the latter, however, the new family can handle indefinite quadratic forms and therefore is capable of solving saddlepoint problems that arise, for instance, in constrained optimization. The novel feature of the new class is a planar iteration that is activated whenever the algorithm encounters a near-singular direction of search, along which the objective function approaches zero curvature. In such iterations, the next point is selected as the stationary point of the objective function over a plane containing the problematic search direction, and the inverse Hessian approximation is updated with respect to that plane via a new four-parameter family of rank-three updates. It is shown that the new class possesses properties which are similar to or which generalize the properties of Huang's family. Furthermore, the new method is equivalent to Fletcher's (Ref. 2) modified version of Luenberger's (Ref. 3) hyperbolic pairs method, with respect to the metric defined by the initial inverse Hessian approximation. Several issues related to implementing the proposed method in nonquadratic cases are discussed.An earlier version of this paper was presented at the 10th Mathematical Programing Symposium, Montreal, Canada, 1979. 相似文献
12.
M.J.D. Powell 《Mathematical Programming》2003,97(3):605-623
We consider some algorithms for unconstrained minimization without derivatives that form linear or quadratic models by interpolation to values of the objective function. Then a new vector of variables is calculated by minimizing the current model within a trust region. Techniques are described for adjusting the trust region radius, and for choosing positions of the interpolation points that maintain not only nonsingularity of the interpolation equations but also the adequacy of the model. Particular attention is given to quadratic models with diagonal second derivative matrices, because numerical experiments show that they are often more efficient than full quadratic models for general objective functions. Finally, some recent research on the updating of full quadratic models is described briefly, using fewer interpolation equations than before. The resultant freedom is taken up by minimizing the Frobenius norm of the change to the second derivative matrix of the model. A preliminary version of this method provides some very promising numerical results.
Presented at NTOC 2001, Kyoto, Japan. 相似文献
13.
Josef Dalík 《Applications of Mathematics》2008,53(6):547-560
We study the problem of Lagrange interpolation of functions of two variables by quadratic polynomials under the condition
that nodes of interpolation are vertices of a triangulation. For an extensive class of triangulations we prove that every
inner vertex belongs to a local six-tuple of vertices which, used as nodes of interpolation, have the following property:
For every smooth function there exists a unique quadratic Lagrange interpolation polynomial and the related local interpolation
error is of optimal order. The existence of such six-tuples of vertices is a precondition for a successful application of
certain post-processing procedures to the finite-element approximations of the solutions of differential problems.
This work was supported by the grant GA ČR 103/05/0292. 相似文献
14.
Gerlind Plonka 《Advances in Computational Mathematics》1995,3(1):1-22
The Fourier transforms of B-splines with multiple integer knots are shown to satisfy a simple recursion relation. This recursion
formula is applied to derive a generalized two-scale relation for B-splines with multiple knots. Furthermore, the structure
of the corresponding autocorrelation symbol is investigated.
In particular, it can be observed that the solvability of the cardinal Hermite spline interpolation problem for spline functions
of degree 2m+1 and defectr, first considered by Lipow and Schoenberg [9], is equivalent to the Riesz basis property of our B-splines with degreem and defectr. In this way we obtain a new, simple proof for the assertion that the cardinal Hermite spline interpolation problem in [9]
has a unique solution. 相似文献
15.
We consider the construction of a C
(1,1) interpolation parabolic spline function of two variables on a uniform rectangular grid, i.e., a function continuous in a
given region together with its first partial derivatives which on every partial grid rectangle is a polynomial of second degree
in x and second degree in y. The spline function is constructed as a minimum-derivative one-dimensional quadratic spline in one of the variables, and
the spline coefficients themselves are minimum-derivative quadratic spline functions of the other variable. 相似文献
16.
Robert M. Yamaleev 《Journal of Mathematical Analysis and Applications》2006,322(2):815-824
Generator of the complex algebra within the framework of general formulation obeys the quadratic equation. In this paper we explore multicomplex algebra with the generator obeying n-order polynomial equation with real coefficients. This algebra induces generalized trigonometry ((n+1)-gonometry), underlies of the nth order oscillator model and nth order Hamilton equations. The solution of an evolution equation generated by (n×n) matrix is represented via the set of (n+1)-gonometric functions. The general form of the first constant of motion of the evolution equation is established. 相似文献
17.
It is obvious that between any two rows (columns) of an m-by-n totally nonnegative matrix a new row (column) may be inserted to form an (m+1)-by-n (m-by-(n+1)) totally nonnegative matrix. The analogous question, in which “totally nonnegative” is replaced by “totally positive” arises, for example, in completion problems and in extension of collocation matrices, and its answer is not obvious. Here, the totally positive case is answered affirmatively, and in the process an analysis of totally positive linear systems, that may be of independent interest, is used. 相似文献
18.
Rational approximation of vertical segments 总被引:1,自引:0,他引:1
In many applications, observations are prone to imprecise measurements. When constructing a model based on such data, an approximation rather than an interpolation approach is needed. Very often a least squares approximation is used. Here we follow a different approach. A natural way for dealing with uncertainty in the data is by means of an uncertainty interval. We assume that the uncertainty in the independent variables is negligible and that for each observation an uncertainty interval can be given which contains the (unknown) exact value. To approximate such data we look for functions which intersect all uncertainty intervals. In the past this problem has been studied for polynomials, or more generally for functions which are linear in the unknown coefficients. Here we study the problem for a particular class of functions which are nonlinear in the unknown coefficients, namely rational functions. We show how to reduce the problem to a quadratic programming problem with a strictly convex objective function, yielding a unique rational function which intersects all uncertainty intervals and satisfies some additional properties. Compared to rational least squares approximation which reduces to a nonlinear optimization problem where the objective function may have many local minima, this makes the new approach attractive. 相似文献
19.
Bruno Iannazzo 《Linear algebra and its applications》2011,434(1):174-184
We study the properties of palindromic quadratic matrix polynomials φ(z)=P+Qz+Pz2, i.e., quadratic polynomials where the coefficients P and Q are square matrices, and where the constant and the leading coefficients are equal. We show that, for suitable choices of the matrix coefficients P and Q, it is possible to characterize by means of φ(z) well known matrix functions, namely the matrix square root, the matrix polar factor, the matrix sign and the geometric mean of two matrices. Finally we provide some integral representations of these matrix functions. 相似文献
20.
M. A. Komarov 《Journal of Mathematical Sciences》2012,181(5):600-612
We study a generalized interpolation of a rational function at n nodes by a simple partial fraction of degree n and reduce
the consideration to the solvability question for a special difference equation. We construct explicit interpolation formulas
in the case where the equation order is equal to 1. We show that for functions A(x − a)
m
,
m ? \mathbbN m \in \mathbb{N} , it is possible to reduce the consideration to a system of m + 1 independent first order equations and construct explicit interpolation formulas. Bibliography: 6 titles. 相似文献