Recognizing polygonal parts from width measurements

Automatic recognition of parts is an important problem in many industrial applications. One model of the problem is: given a finite set of polygonal parts, use a set of “width” measurements taken by a parallel-jaw gripper to determine which part is present. We study the problem of computing efficient strategies (“grasp plans”), with the goal to minimize the number of measurements necessary in the worst case. We show that finding a minimum length grasp plan is -hard, and give a polynomial time approximation algorithm that is simple and produces a solution that is within a log factor from optimal.     

A general model for the undesirable single facility location problem

In this paper, a finite set in which an optimal solution for a general Euclidean problem of locating an undesirable facility in a polygonal region, is determined and can be found in polynomial time. The general problem we propose leads us, among others, to several well-known problems such as the maxisum, maximin, anticentdian or r-anticentrum problem.     

n-sided polygonal hybrid finite elements with unified fundamental solution kernels for topology optimization

In topology optimization, the optimized design can be obtained based on spatial discretization of design domain using natural polygonal finite elements to reduce the influence of mesh geometry on topology optimization solutions. However, the natural polygonal finite elements require separate interpolants for each type of elements and involve troublesome domain integrals. In this study, an alternative n-sided polygonal hybrid finite element possessing multiple-node connection is formulated in a unified form to compress the checkerboard patterns caused by numerical instability in topology optimization. Different from the natural polygonal finite elements, the present polygonal hybrid finite elements involve two sets of independent displacement fields. The intra-element displacement field defined inside the element is approximated by the linear combination of the fundamental solution of the problem to achieve the purpose of the local satisfaction of the governing equations of the problem, but not the specific boundary conditions and the inter-element continuity conditions. To overcome such drawback, the inter-element displacement field defined over the entire element boundary is independently approximated by means of the conventional shape function interpolation. As a result, only line integrals along the element boundary are involved in the computation, whose dimension is reduced by one compared to the domain integrals in the natural polygonal finite elements, and more importantly, allowing us to flexibly construct any polygons from Voronoi tessellations in discretizing complex design domains using same fundamental solution kernels. Numerical results obtained indicate that the present n-sided polygonal hybrid finite elements can produce more accurate displacement solutions and smaller mean compliance, compared to the standard finite elements and the natural polygonal finite elements.     

An all-linear programming relaxation algorithm for optimizing over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. In this paper a relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.Research supported by a grant from the College of Business Administration, University of Florida, Gainesville, Florida, U.S.A.     

On finite convergence of proximal point algorithms for variational inequalities

In this paper, we first characterize finite convergence of an arbitrary iterative algorithm for solving the variational inequality problem (VIP), where the finite convergence means that the algorithm can find an exact solution of the problem in a finite number of iterations. By using this result, we obtain that the well-known proximal point algorithm possesses finite convergence if the solution set of VIP is weakly sharp. As an extension, we show finite convergence of the inertial proximal method for solving the general variational inequality problem under the condition of weak g-sharpness.     

Solvability of the vector problem by the linear criteria convolution algorithm

Conditions are found under which a multicriteria problem with a finite set of vector estimates is solvable by means of the linear criteria convolution (LCC) algorithm, that is, any Pareto optimum for the problem can be obtained as an optimum solution to a one-criterion problem with an aggregated criterion defined as an LCC. Also, an algorithm is suggested that is polynomial in dimension and reduces any problem with minimax and minimin criteria to an equivalent vector problem with the same Pareto set solvable by the LCC algorithm. Translated fromMatematicheskie Zametki, Vol. 62, No. 4, pp. 502–509, October, 1997. Translated by V. N. Dubrovsky     

Finite-element analysis of contact problems in thermoelasticity. The semi-coercive case

Numerical analysis of the Signorini problem with friction in two-dimensional quasi coupled linear thermoelasticity is investigated. Piecewise linear finite elements on the triangulation of the given domain Ω ² with polygonal boundary ∂Ω are used. In this contribution we establish the rate of convergence of the finite-element approximate solution u_h, provided the exact solution is smooth enough. In general the problem represents the model problem of a great number of branches, such as the model problem of a high-level radioactive waste disposal system as well as the model problem of geodynamcis and biomechanics, etc.     

A fast interface solver for the biharmonic Dirichlet problem on polygonal domains

Summary. In this paper we propose and analyze an efficient discretization scheme for the boundary reduction of the biharmonic Dirichlet problem on convex polygonal domains. We show that the biharmonic Dirichlet problem can be reduced to the solution of a harmonic Dirichlet problem and of an equation with a Poincaré-Steklov operator acting between subspaces of the trace spaces. We then propose a mixed FE discretization (by linear elements) of this equation which admits efficient preconditioning and matrix compression resulting in the complexity . Here is the number of degrees of freedom on the underlying boundary, is an error reduction factor, or for rectangular or polygonal boundaries, respectively. As a consequence an asymptotically optimal iterative interface solver for boundary reductions of the biharmonic Dirichlet problem on convex polygonal domains is derived. A numerical example confirms the theory. Received September 1, 1995 / Revised version received February 12, 1996     

Nonlinear programming without differentiability in banach spaces: necessary and sufficient constraint qualification

The problem under consideration is a maximization problem over a constraint set defined by a finite number of inequality and equality constraints over an arbitrary set in a reflexive Banach space. A generalization of the Kuhn-Tucker necessary conditions is developed where neither the objective function nor the constraint functions are required to be differentiable. A new constraint qualification is imposed in order to validate the optimality criteria. It is shown that this qualification is the weakest possible in the sense that it is necessary for the optimality criteria to hold at the point under investigation for all families of objective functions having a constrained local maximum at this point     

Weak sharp solutions for variational inequalities in Banach spaces

In this paper, we introduce the notion of a weak sharp set of solutions to a variational inequality problem (VIP) in a reflexive, strictly convex and smooth Banach space, and present its several equivalent conditions. We also prove, under some continuity and monotonicity assumptions, that if any sequence generated by an algorithm for solving (VIP) converges to a weak sharp solution, then we can obtain solutions for (VIP) by solving a finite number of convex optimization subproblems with linear objective. Moreover, in order to characterize finite convergence of an iterative algorithm, we introduce the notion of a weak subsharp set of solutions to a variational inequality problem (VIP), which is more general than that of weak sharp solutions in Hilbert spaces. We establish a sufficient and necessary condition for the finite convergence of an algorithm for solving (VIP) which satisfies that the sequence generated by which converges to a weak subsharp solution of (VIP), and show that the proximal point algorithm satisfies this condition. As a consequence, we prove that the proximal point algorithm possesses finite convergence whenever the sequence generated by which converges to a weak subsharp solution of (VIP).     

Ersatz function method for minimizing a finite-valued function on a compact set

A method is proposed for solving optimization problems with continuous variables and a function taking a large finite set of values. Problems of this type arise in the multicriteria construction of a control rule for a discrete-time dynamical system whose performance criteria coincide with the number of violations of requirements imposed on the system. The rule depends on a finite set of parameters whose set of admissible values defines a collection of admissible control rules. An example is the problem of choosing a control rule for a cascade of reservoirs. The optimization method is based on solving a modified problem in which the original function is replaced by a continuous ersatz function. A theorem on the relation between the average-minimal values of the original and ersatz functions is proved. Optimization problems are solved with power-law ersatz functions, and the influence exerted by the exponent on the quality of the solution is determined. It is experimentally shown that the solutions produced by the method are of fairly high quality.     

Parabolic finite element equations in nonconvex polygonal domains

Let Ω be a bounded nonconvex polygonal domain in the plane. Consider the initial boundary value problem for the heat equation with homogeneous Dirichlet boundary conditions and semidiscrete and fully discrete approximations of its solution by piecewise linear finite elements in space. The purpose of this paper is to show that known results for the stationary, elliptic, case may be carried over to the time dependent parabolic case. A special feature in a polygonal domain is the presence of singularities in the solutions generated by the corners even when the forcing term is smooth. These cause a reduction of the convergence rate in the finite element method unless refinements are employed.     

Error Analysis of Galerkin Methods for Dirichlet Problems Containing Boundary Singularities

This paper deals with a two-dimensional Poisson problem definedin a polygonal domain and having inhomogeneous Dirichlet boundaryconditions. A Galerking method for obtaining approximationsusing triangular finite elements is described. The situationwhen the exact solution contains a singularity at a re-entrantcorner of the boundary is considered, and for this an O(h) boundon the error in the Galerkin approximation is derived.     

Construction of covering maps between orientable surfaces

Consider the following problem. Can a set of numbers be realized as boundary covering indices of a covering map between surfaces? How to realize them? A set of equivalent criteria for this problem are found, which can be checked by a finite algorithm. Furthermore, the algorithm will also construct a solution if such one exists. As an application, a well_known group of necessary conditions are shown to be not sufficient in infinitely many cases, while in most cases, numbers satisfying them are realizable.     

Rigidity of planar tilings

Summary Aperturbation of a tiling of a region inR ⁿ is a set of isometries, one applied to each tile, so that the images of the tiles tile the same region.We show that a locally finite tiling of an open region inR ² with tiles which are closures of their interiors isrigid in the following sense: any sufficiently small perturbation of the tiling must have only earthquake-type discontinuities, that is, the discontinuity set consists of straight lines and arcs of circles, and the perturbation near such a curve shifts points along the direction of that curve.We give an example to show that this type of rigidity does not hold inR ⁿ , forn>2.Using rigidity in the plane we show that any tiling problem with a finite number of tile shapes (which are topological disks) is equivalent to a polygonal tiling problem, i.e. there is a set of polygonal shapes with equivalent tiling combinatorics.Oblatum 19-III-1991     

Construction of the Solvability Set in Differential Games with Simple Motion and Nonconvex Terminal Set

We consider planar zero-sum differential games with simple motion, fixed terminal time, and polygonal terminal set. The geometric constraint on the control of each player is a convex polygonal set or a line segment. In the case of a convex terminal set, an explicit formula is known for the solvability set (a level set of the value function, maximal u-stable bridge, viability set). The algorithm corresponding to this formula is based on the set operations of algebraic sum and geometric difference (the Minkowski difference). We propose an algorithm for the exact construction of the solvability set in the case of a nonconvex polygonal terminal set. The algorithm does not involve the additional partition of the time interval and the recovery of intermediate solvability sets at additional instants. A list of half-spaces in the three-dimensional space of time and state coordinates is formed and processed by a finite recursion. The list is based on the polygonal terminal set with the use of normals to the polygonal constraints on the controls of the players.     

Finite termination of the proximal point algorithm in Banach spaces

In this paper, we show that the convex optimization problem can be solved by the proximal point algorithm in a finite number of steps under the assumption that the solution set is a set of weak sharp minima.     

A Posteriori Error Estimation for the Dual Mixed Finite Element Method of the Stokes Problem

The paper presents an a posteriori error estimator of residual type for the stationary Stokes problem in a possibly multiply-connected polygonal domain of the plane, using the dual mixed finite element method (FEM). We prove lower and upper error bounds with the explicit dependence of the viscosity parameter and without any regularity assumption on the solution.     

Finite convergence analysis and weak sharp solutions for variational inequalities

In this paper, we study the weak sharpness of the solution set of variational inequality problem (in short, VIP) and the finite convergence property of the sequence generated by some algorithm for finding the solutions of VIP. In particular, we give some characterizations of weak sharpness of the solution set of VIP without considering the primal or dual gap function. We establish an abstract result on the finite convergence property for a sequence generated by some iterative methods. We then apply such abstract result to discuss the finite termination property of the sequence generated by proximal point method, exact proximal point method and gradient projection method. We also give an estimate on the number of iterates by which the sequence converges to a solution of the VIP.     

On Generalizations of the Frank-Wolfe Theorem to Convex and Quasi-Convex Programmes

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or a quasi-convex polynomial function over the feasible set defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities, where the faithfully convex functions satisfy some mild assumption. The conditions are provided in the form of an algorithm, terminating after a finite number of iterations, the implementation of which requires the identification of implicit equality constraints in a homogeneous linear system. We prove that the optimal solution set of the considered problem is nonempty, this way extending the attainability result well known as the so-called Frank-Wolfe theorem. Finally we show that our extension of the Frank-Wolfe theorem immediately implies continuity of the solution set defined by the considered system of (quasi)convex inequalities.