Estudo Geralhttps://estudogeral.sib.uc.ptThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Thu, 06 Aug 2020 07:34:29 GMT2020-08-06T07:34:29Z5051Geometry of sample sets in derivative free optimization. Part II: polynomial regression and underdetermined interpolationhttp://hdl.handle.net/10316/11386Title: Geometry of sample sets in derivative free optimization. Part II: polynomial regression and underdetermined interpolation
Authors: Conn, Andrew R.; Scheinberg, Katya; Vicente, Luís Nunes
Abstract: In the recent years, there has been a considerable amount of work in
the development of numerical methods for derivative free optimization problems.
Some of this work relies on the management of the geometry of sets of sampling
points for function evaluation and model building.
In this paper, we continue the work developed in [7] for complete or determined
interpolation models (when the number of interpolation points equals the number
of basis elements), considering now the cases where the number of points is higher
(regression models) and lower (underdetermined models) than the number of basis
components.
We show how the notion of A-poisedness introduced in [7] to quantify the quality
of the sample sets can be extended to the nondetermined cases, by extending first
the underlying notion of bases of Lagrange polynomials. We also show that Apoisedness
is equivalent to a bound on the condition number of the matrix arising
from the sampling conditions. We derive bounds for the errors between the function
and the (regression and underdetermined) models and between their derivatives.
Sat, 01 Jan 2005 00:00:00 GMThttp://hdl.handle.net/10316/113862005-01-01T00:00:00ZError estimates and poisedness in multivariate polynomial interpolationhttp://hdl.handle.net/10316/11438Title: Error estimates and poisedness in multivariate polynomial interpolation
Authors: Conn, Andrew R.; Scheinberg, Katya; Vicente, Luís Nunes
Abstract: We show how to derive error estimates between a function and its interpolating
polynomial and between their corresponding derivatives. The derivation
is based on a new de nition of well-poisedness for the interpolation set, directly
connecting the accuracy of the error estimates with the geometry of the points in
the set. This de nition is equivalent to the boundedness of Lagrange polynomials,
but it provides new geometric intuition. Our approach extracts the error bounds
for all of the derivatives using the same analysis; the error bound for the function
values is then derived a posteriori.
We also develop an algorithm to build a set of well-poised interpolation points or
to modify an existing set to ensure its well-poisedness. We comment on the optimal
geometries corresponding to the best possible well-poised sets in the case of linear
interpolation.
Wed, 01 Jan 2003 00:00:00 GMThttp://hdl.handle.net/10316/114382003-01-01T00:00:00ZGlobal convergence of general derivative-free trust-region algorithms to first and second order critical pointshttp://hdl.handle.net/10316/11325Title: Global convergence of general derivative-free trust-region algorithms to first and second order critical points
Authors: Conn, Andrew R.; Scheinberg, Katya; Vicente, Luís Nunes
Abstract: In this paper we prove global convergence for first and second-order stationarity
points of a class of derivative-free trust-region methods for unconstrained
optimization. These methods are based on the sequential minimization of linear or
quadratic models built from evaluating the objective function at sample sets. The
derivative-free models are required to satisfy Taylor-type bounds but, apart from
that, the analysis is independent of the sampling techniques.
A number of new issues are addressed, including global convergence when acceptance
of iterates is based on simple decrease of the objective function, trust-region
radius maintenance at the criticality step, and global convergence for second-order
critical points.
Sun, 01 Jan 2006 00:00:00 GMThttp://hdl.handle.net/10316/113252006-01-01T00:00:00ZBilevel derivative-free optimization and its application to robust optimizationhttp://hdl.handle.net/10316/13700Title: Bilevel derivative-free optimization and its application to robust optimization
Authors: Conn, Andrew R.; Vicente, L. N.
Abstract: We address bilevel programming problems when the derivatives of both
the upper and the lower level objective functions are unavailable.
The core algorithms used for both levels are trust-region interpolation-based
methods, using minimum Frobenius norm quadratic models when the number of
points is smaller than the number of basis components. We take advantage of the
problem structure to derive conditions (related to the global convergence theory of
the underlying trust-region methods, as far as possible) under which the lower level
can be solved inexactly and sample points can be reused for model building. In addition,
we indicate numerically how effective these expedients can be. A number of
other issues are also discussed, from the extension to linearly constrained problems
to the use of surrogate models for the lower level response.
One important application of our work appears in the robust optimization of
simulation-based functions, which may arise due to implementation variables or
uncertain parameters. The robust counterpart of an optimization problem without
derivatives falls in the category of the bilevel problems under consideration here.
We provide numerical illustrations of the application of our algorithmic framework
to such robust optimization examples
Fri, 01 Jan 2010 00:00:00 GMThttp://hdl.handle.net/10316/137002010-01-01T00:00:00ZGeometry of interpolation sets in derivative free optimizationhttp://hdl.handle.net/10316/7727Title: Geometry of interpolation sets in derivative free optimization
Authors: Conn, A.; Scheinberg, K.; Vicente, Luís
Abstract: Abstract We consider derivative free methods based on sampling approaches for nonlinear optimization problems where derivatives of the objective function are not available and cannot be directly approximated. We show how the bounds on the error between an interpolating polynomial and the true function can be used in the convergence theory of derivative free sampling methods. These bounds involve a constant that reflects the quality of the interpolation set. The main task of such a derivative free algorithm is to maintain an interpolation sampling set so that this constant remains small, and at least uniformly bounded. This constant is often described through the basis of Lagrange polynomials associated with the interpolation set. We provide an alternative, more intuitive, definition for this concept and show how this constant is related to the condition number of a certain matrix. This relation enables us to provide a range of algorithms whilst maintaining the interpolation set so that this condition number or the geometry constant remain uniformly bounded. We also derive bounds on the error between the model and the function and between their derivatives, directly in terms of this condition number and of this geometry constant.
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/10316/77272008-01-01T00:00:00Z