On the stability of inner and outer approximations of a convex compact set by a ball

The finite-dimensional problems of outer and inner estimation of a convex compact set by a ball of some norm (circumscribed and inscribed ball problems) are considered. The stability of the solution with respect to the error in the specification of the estimated compact set is generally characterized. A new solution criterion for the outer estimation problem is obtained that relates the latter to the inner estimation problem for the lower Lebesgue set of the distance function to the most distant point of the estimated compact set. A quantitative estimate for the stability of the center of an inscribed ball is given under the additional assumption that the compact set is strongly convex. Assuming that the used norm is strongly quasi-convex, a quantitative stability estimate is obtained for the center of a circumscribed ball.     

Method for finding an approximate solution of the asphericity problem for a convex body

Given a convex body, the finite-dimensional problem is considered of minimizing the ratio of its circumradius to its inradius (in an arbitrary norm) by choosing a common center of the circumscribed and inscribed balls. An approach is described for obtaining an approximate solution of the problem, whose accuracy depends on the error of a preliminary polyhedral approximation of the convex body and the unit ball of the used norm. The main result consists of developing and justifying a method for finding an approximate solution with every step involving the construction of supporting hyperplanes of the convex body and the unit ball of the used norm at some marginal points and the solution of a linear programming problem.     

Efficiency of the estimate refinement method for polyhedral approximation of multidimensional balls

The estimate refinement method for the polyhedral approximation of convex compact bodies is analyzed. When applied to convex bodies with a smooth boundary, this method is known to generate polytopes with an optimal order of growth of the number of vertices and facets depending on the approximation error. In previous studies, for the approximation of a multidimensional ball, the convergence rates of the method were estimated in terms of the number of faces of all dimensions and the cardinality of the facial structure (the norm of the f-vector) of the constructed polytope was shown to have an optimal rate of growth. In this paper, the asymptotic convergence rate of the method with respect to faces of all dimensions is compared with the convergence rate of best approximation polytopes. Explicit expressions are obtained for the asymptotic efficiency, including the case of low dimensions. Theoretical estimates are compared with numerical results.     

Best Approximation in Numerical Radius

Let X be a reflexive Banach space. In this article, we give a necessary and sufficient condition for an operator T ∈ 𝒦(X) to have the best approximation in numerical radius from the convex subset 𝒰 ? 𝒦(X), where 𝒦(X) denotes the set of all linear, compact operators from X into X. We also present an application to minimal extensions with respect to the numerical radius. In particular, some results on best approximation in norm are generalized to the case of the numerical radius.     

Approximation of continuous set-valued maps by constant set-valued maps with image balls

It is shown that the problem of the best uniform approximation in the Hausdorff metric of a continuous set-valued map with finite-dimensional compact convex images by constant set-valued maps whose images are balls in some norm can be reduced to a visual geometric problem. The latter consists in constructing a spherical layer of minimal thickness which contains the complement of a compact convex set to a larger compact convex set.     

Regularized parametric Kuhn-Tucker theorem in a Hilbert space

For a parametric convex programming problem in a Hilbert space with a strongly convex objective functional, a regularized Kuhn-Tucker theorem in nondifferential form is proved by the dual regularization method. The theorem states (in terms of minimizing sequences) that the solution to the convex programming problem can be approximated by minimizers of its regular Lagrangian (which means that the Lagrange multiplier for the objective functional is unity) with no assumptions made about the regularity of the optimization problem. Points approximating the solution are constructively specified. They are stable with respect to the errors in the initial data, which makes it possible to effectively use the regularized Kuhn-Tucker theorem for solving a broad class of inverse, optimization, and optimal control problems. The relation between this assertion and the differential properties of the value function (S-function) is established. The classical Kuhn-Tucker theorem in nondifferential form is contained in the above theorem as a particular case. A version of the regularized Kuhn-Tucker theorem for convex objective functionals is also considered.     

On the Continuity of Best Approximations by Constants on Balls in Metric Measure Spaces

Mathematical Notes - Conditions for the constants of best approximation in the metric of the spaces Lp(B) to be continuous or semicontinuous as functions of the center of a ball B of fixed radius...     

Inscribed ball and enclosing box methods for the convex maximization problem

Many important classes of decision models give rise to the problem of finding a global maximum of a convex function over a convex set. This problem is known also as concave minimization, concave programming or convex maximization. Such problems can have many local maxima, therefore finding the global maximum is a computationally difficult problem, since standard nonlinear programming procedures fail. In this article, we provide a very simple and practical approach to find the global solution of quadratic convex maximization problems over a polytope. A convex function achieves its global maximum at extreme points of the feasible domain. Since an inscribed ball does not contain any extreme points of the domain, we use the largest inscribed ball for an inner approximation while a minimal enclosing box is exploited for an outer approximation of the domain. The approach is based on the use of these approximations along with the standard local search algorithm and cutting plane techniques.     

On measuring the inefficiency with the inner-product norm in data envelopment analysis

A technique for assessing the sensitivity of efficiency classifications in Data Envelopment Analysis (DEA) is presented. It extends the technique proposed by Charnes et al. (A. Charnes, J.J. Rousseau, J.H. Semple, Journal of Productivity Analysis 7 (1996) 5–18). An organization's input–output vector serves as the center for a cell within which the organization's classification remains unchanged under perturbations of the data. The maximal radius among such cells can be interpreted as a stability measure of the classification. Our approach adopts the inner-product norm for the radius, while the previous work does the polyhedral norms. For an efficient organization, the maximal-radius problem is a convex program. On the other hand, for an inefficient organization, it is reduced to a nonconvex program whose feasible region is the complement of a convex polyhedral set. We show that the latter nonconvex problem can be transformed into a linear reverse convex program. Our formulations and algorithms are valid not only in the CCR model but in its variants.     

Error estimates for the approximation of semicoercive variational inequalities

Summary. An abstract error estimate for the approximation of semicoercive variational inequalities is obtained provided a certain condition holds for the exact solution. This condition turns out to be necessary as is demonstrated analytically and numerically. The results are applied to the finite element approximation of Poisson's equation with Signorini boundary conditions and to the obstacle problem for the beam with no fixed boundary conditions. For second order variational inequalities the condition is always satisfied, whereas for the beam problem the condition holds if the center of forces belongs to the interior of the convex hull of the contact set. Applying the error estimate yields optimal order of convergence in terms of the mesh size . The numerical convergence rates observed are in good agreement with the predicted ones. Received August 16, 1993 / Revised version received March 21, 1994     

非线性sine-Gordon方程的双线性元分析及外推

研究双线性元对一类非线性sine-Gordon方程的有限元逼近.利用该元的高精度结果和对时间t的导数转移技巧,得到了H~1模意义下的超逼近性.进一步地,通过运用插值后处理技术,给出了H~1模意义下的超收敛结果.与此同时,通过构造一个新的外推格式,导出了与线性问题情形相同的三阶外推解.最后给出了一种全离散逼近格式下的最优误差估计.     

Positive definite matrix approximation with condition number constraint

Positive definite matrix approximation with a condition number constraint is an optimization problem to find the nearest positive definite matrix whose condition number is smaller than a given constant. We demonstrate that this problem can be converted to a simpler one when we use a unitary similarity invariant norm as a metric. We can especially convert it to a univariate piecewise convex optimization problem when we use the Ky Fan p-k norm. We also present an analytical solution to the problem whose metric is the spectral norm and the trace norm.     

Explicit H1-Estimate for the Solution of the Lamé System with Mixed Boundary Conditions

In this paper we consider the Lamé system on a polygonal convex domain with mixed boundary conditions of Dirichlet-Neumann type. An explicit L² norm estimate for the gradient of the solution of this problem is established. This leads to an explicit bound of the H¹ norm of this solution. Note that the obtained upper-bound is not optimal.     

Zeroth order H ∞ norm approximation of multivariable systems

In this paper the H _∞ norm approximation of a given stable, proper, rational transfer function by a constant matrix is considered (Zeroth order H _∞ norm approximation problem). The solution method is based on the observation that the H _∞ norm approximation problem can be put into an allpass imbedding problem.     

Extreme values for characteristic radii of a Poisson-Voronoi Tessellation

A homogeneous Poisson-Voronoi tessellation of intensity γ is observed in a convex body W. We associate to each cell of the tessellation two characteristic radii: the inradius, i.e. the radius of the largest ball centered at the nucleus and included in the cell, and the circumscribed radius, i.e. the radius of the smallest ball centered at the nucleus and containing the cell. We investigate the maximum and minimum of these two radii over all cells with nucleus in W. We prove that when \(\gamma \rightarrow \infty \) , these four quantities converge to Gumbel or Weibull distributions up to a rescaling. Moreover, the contribution of boundary cells is shown to be negligible. Such approach is motivated by the analysis of the global regularity of the tessellation. In particular, consequences of our study include the convergence to the simplex shape of the cell with smallest circumscribed radius and an upper-bound for the Hausdorff distance between W and its so-called Poisson-Voronoi approximation.     

The motion of a body with a cavity partly filled with a viscous liquid

Many papers are concerned with the dynamics of a rigid body with a cavity filled with liquid (see the bibliography in [1]). The present paper deals with the motion of a rigid body having a cavity partly filled with a viscous incompressible liquid, and having a free surface. The shape of the cavity is arbitrary. The problem is considered in a linear formulation. The oscillations of the body with respect to its center of inertia and the motion of the liquid in the cavity are assumed small. The viscosity of the liquid is considered low. The solution of the problem of the oscillations of a body with a cavity partly filled with an ideal liquid is used as an initial approximation [1 to 6]. The viscosity is taken into consideration by the boundary layer method used before in similar problems [1 and 7 to 10). General equations are derived for the dynamics of a body filled with a liquid, for an arbitrary form of cavity. The coefficients of those integro-differential equations depend only on the solution of the problem of the oscillations of a body with a cavity of the given form filled with an ideal liquid. Since the corresponding problem has been solved for cavities of many forms [1 to 6, 11 and 12] in the case of an ideal liquid, the determination of the characteristic coefficients is reduced to the evaluation of quadratures. Several particular cases of motion are considered.     

Approximation of convex bodies by polytopes

LetC be a convex body ofE ^d and consider the symmetric difference metric. The distance ofC to its best approximating polytope having at mostn vertices is 0 (1/n ^2/(d?1)) asn→∞. It is shown that this estimate cannot be improved for anyC of differentiability class two. These results complement analogous theorems for the Hausdorff metric. It is also shown that for both metrics the approximation properties of «most» convex bodies are rather irregular and that ford=2 «most» convex bodies have unique best approximating polygons with respect to both metrics.     

Analysis on a Finite Volume Element Method for Stokes Problems

Finite volume element method for the Stokes problem is considered. We use a conforming piecewise linear function on a fine grid for velocity and piecewise constant element on a coarse grid for pressure. For general triangulation we prove the equivalence of the finite volume element method and a saddle-point problem, the inf-sup condition and the uniqueness of the approximation solution. We also give the optimal order H^1 norm error estimate. For two widely used dual meshes we give the L^2 norm error estimates, which is optimal in one case and quasi-optimal in another ease. Finally we give a numerical example.     

Properties and methods for finding the best rank-one approximation to higher-order tensors

The problem of finding the best rank-one approximation to higher-order tensors has extensive engineering and statistical applications. It is well-known that this problem is equivalent to a homogeneous polynomial optimization problem. In this paper, we study theoretical results and numerical methods of this problem, particularly focusing on the 4-th order symmetric tensor case. First, we reformulate the polynomial optimization problem to a matrix programming, and show the equivalence between these two problems. Then, we prove that there is no duality gap between the reformulation and its Lagrangian dual problem. Concerning the approaches to deal with the problem, we propose two relaxed models. The first one is a convex quadratic matrix optimization problem regularized by the nuclear norm, while the second one is a quadratic matrix programming regularized by a truncated nuclear norm, which is a D.C. function and therefore is nonconvex. To overcome the difficulty of solving this nonconvex problem, we approximate the nonconvex penalty by a convex term. We propose to use the proximal augmented Lagrangian method to solve these two relaxed models. In order to obtain a global solution, we propose an alternating least eigenvalue method after solving the relaxed models and prove its convergence. Numerical results presented in the last demonstrate, especially for nonpositive tensors, the effectiveness and efficiency of our proposed methods.