Finding squares and rectangles in sets of points

A number of problems concerning sets of points in the plane are studied, e.g. establishing whether it contains a subset of size 4, which are the vertices of a square or rectangle. Both the problems of finding axis-parallel squares and rectangles, and arbitrarily oriented squares and rectangles are studied. Efficient algorithms are obtained for all of them. Furthermore, we investigate the generalizations tod-dimensional space, where the problem is to find hyperrectangles and hypercubes. Also, upper and lower bounds are given for combinatorial problems on the maxium number of subsets of size 4, of which the points are the vertices of a square or rectangle. Then we state an equivalence between the problem of finding rectangles, and the problem of findingK _{2, 2} subgraphs in bipartite graphs. Thus we immediately have an efficient algorithm for this graph problem.This work was partially supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). Work of the second author was also supported by the Dutch Organisation for Scientific Research (N.W.O.).     

规范变换与有限维可积系统间的变换

本文表明，利用两个特征值问题的规范变换，不仅可以建立和它们相联系的势的约束之间以及相应的有限维Ｈａｍｉｌｔｏｎ系统间的变换关系式，而且可以由一个可积系统的对合守恒积分导出另一个系统的守恒积分     

Scanline algorithms on a grid

A number of important problems in computational geometry are solved efficiently on 2- or 3-dimensional grids by means of scanline techniques. In the time complexity of solutions to the maximal elements and closure problems, a factor logn is substituted by loglogn, wheren is the number of elements. Next, by using a data structure introduced in the paper, the interval trie, previous solutions to the rectangle intersection and connected component problems are improved upon. Finally, a fast intersection finding algorithm for arbitrarily oriented line segments is presented.     

A Relaxation of a Min-Cut Problem in an Anisotropic Continuous Network

Strang [18] introduced optimization problems on a Euclidean domain which are closely related with problems in mechanics and noted that the problems are regarded as continuous versions of famous max-flow and min-cut problems. In [15] we generalized the problems and called the generalized problems max-flow and min-cut problems of Strang's type. In this paper we formulate a relaxed version of the min-cut problem of Strang's type and prove the existence of optimal solutions under some suitable conditions. The conditions are essential. In fact, there is an example of the relaxed version which has no optimal solutions if the conditions are not fulfilled. We give such an example in the final section. Accepted 8 October 1998     

Existence of Optimal Controls for Semilinear Parabolic Equations without Cesari-Type Conditions

Abstract. Optimal control problems governed by semilinear parabolic partial differential equations are considered. No Cesari-type conditions are assumed. By proving the existence theorem and the Pontryagin maximum principle of optimal ``state-control" pairs for the corresponding relaxed problems, an existence theorem of optimal pairs for the original problem is established.     

A branch and reduce approach for solving a class of low rank d.c. programs

Various classes of d.c. programs have been studied in the recent literature due to their importance in applicative problems. In this paper we consider a branch and reduce approach for solving a class of d.c. problems. Seven partitioning rules are analyzed and some techniques aimed at improving the overall performance of the algorithm are proposed. The results of a computational experience are provided in order to point out the performance effectiveness of the proposed techniques.     

A Modified Alternating Direction Method for Variational Inequality Problems

The alternating direction method is an attractive method for solving large-scale variational inequality problems whenever the subproblems can be solved efficiently. However, the subproblems are still variational inequality problems, which are as structurally difficult to solve as the original one. To overcome this disadvantage, in this paper we propose a new alternating direction method for solving a class of nonlinear monotone variational inequality problems. In each iteration the method just makes an orthogonal projection to a simple set and some function evaluations. We report some preliminary computational results to illustrate the efficiency of the method. Accepted 4 May 2001. Online publication 19 October, 2001.     

Regularization by Functions of Bounded Variation and Applications to Image Enhancement

Optimization problems regularized by bounded variation seminorms are analyzed. The optimality system is obtained and finite-dimensional approximations of bounded variation function spaces as well as of the optimization problems are studied. It is demonstrated that the choice of the vector norm in the definition of the bounded variation seminorm is of special importance for approximating subspaces consisting of piecewise constant functions. Algorithms based on a primal—dual framework that exploit the structure of these nondifferentiable optimization problems are proposed. Numerical examples are given for denoising of blocky images with very high noise. Accepted 29 March 1998     

二阶系统边值问题的正解

以关于非线性全连续算子的锥不动点定为工具,研究二阶系统边值问题,在不假定ｆ,ｇ单调的情况下,得出了上述问题存在正解的若干充分条件。     

Existence of Optimal Controls for Semilinear Parabolic Equations without Cesari-Type Conditions

   Abstract. Optimal control problems governed by semilinear parabolic partial differential equations are considered. No Cesari-type conditions are assumed. By proving the existence theorem and the Pontryagin maximum principle of optimal ``state-control" pairs for the corresponding relaxed problems, an existence theorem of optimal pairs for the original problem is established.     

A PENALTY TECHNIQUE FOR NONLINEAR COMPLEMENTARITY PROBLEMS

1.IntroductionConsiderthefollowingnonlinearcomplementarityproblemsNCP(F)offindinganxER",suchthatwhereFisamappingfromR"intoitself.ItisanimportantformofthefollowingvariationalinequalityVI(F,X)offindinganxEX,suchthatwhereXCReisaclosedconvexset.WhenX=R7,(1.1)…     

Relaxation and existence of optimal controls for systems governed by evolution inclusions in separable Banach spaces

In this paper, we examine relaxed control systems governed by evolution inclusions in a separable Banach space. First, we establish the existence of admissible trajectories, correcting an earlier result of Ahmed. Then, we obtain a compactness result for the set of admissible trajectories. Using this compactness result, we prove the existence of optimal solutions for optimal control problems; furthermore, we show that the values of the original and relaxed problems are equal. Finally, we show that the original trajectories are dense in the set of relaxed trajectories. An example is worked out.This research was supported by NSF Grant No. DMS-86-02313.     

A differentiation formula for integrals overseas given by inclusion

Formulae for differentiation with respect to the parameter of an integral over the set given by an inclusion are proposed. The case with bounded and unbounded set is discussed. Such formulae can be used for differentiation of probability functions. An algorithm for solving chance constrainted optimization problems is considered.     

Time considered irrelevant for real-time systems

Various manifestations of the time-as-a-proxy phenomenon in specification of computing problems are considered. It is argued that unless the time-related considerations constitute an essential part of natural (physical) problems, safer specifications are obtained from avoiding short-cuts offered by introduction of time-related notions. This methodological principle is illustrated by examples from several fields: digital control and simulation, design of operator's interface and communication protocols.Dedicated to Peter Naur on the occasion of his 60th birthday     

Minimization of Energy Functionals Applied to Some Inverse Problems

We consider a general class of problems of the minimization of convex integral functionals subject to linear constraints. Using Fenchel duality, we prove the equality of the values of the minimization problem and its associated dual problem. This equality is a variational criterion for the existence of a solution to a large class of inverse problems entering the class of generalized Fredholm integral equations. In particular, our abstract results are applied to marginal problems for stochastic processes. Such problems naturally arise from the probabilistic approaches to quantum mechanics. Accepted 26 March 2001. Online publication 19 July 2001.     

非线性反应扩散方程奇摄动问题

研究了具有非线性反应扩散方程奇摄动问题。在适当的条件下，利用微分不等式理论，讨论了当退化问题具有两个相交解时，原初始边值问题解的渐近性态。      

Solving a Class of Linearly Constrained Indefinite Quadratic Problems by D.C. Algorithms

Linearly constrained indefinite quadratic problems play an important role in global optimization. In this paper we study d.c. theory and its local approachto such problems. The new algorithm, CDA, efficiently produces local optima and sometimes produces global optima. We also propose a decomposition branch andbound method for globally solving these problems. Finally many numericalsimulations are reported.     

几类考虑有限理性平衡问题解的稳定性

对Ky Fan点问题定义了理性函数,证明了大多数的KyFan点问题(在Baire分类意义上)都是结构稳定的,对$\varepsilon$-平衡也都是鲁棒的.作为应用,还给出了Nash平衡问题和变分不等式问题的稳定性结论.     

The lagrange-newton method for infinite-dimensional optimization problems

This paper investigates local convergence properties of the Lagrange-Newton method for optimization problems in reflexive Banach spaces. Sufficient conditions for quadratic convergence of optimal solutions and Lagrange multipliers are given. The results are applied to optimal control problems.     

反中心对称矩阵反问题解存在的条件

讨论了反中心对称矩阵反问题及其最佳逼近。研究了矩阵反问题有解的充分和必要条件,利用这类矩阵的结构和特征性质得到了矩阵反问题解的通式;证明了最佳逼近问题存在唯一解,并给出了求最佳逼近解的算法和数值算例。