Decision Problems in Quadratic Function Fields of High Genus

This paper provides verification procedures for a number of decision problems in quadratic function fields of odd characteristic, thereby establishing membership of these problems in both NP and co-NP. The problems include determining the ideal and divisor class numbers of the field, the regulator of the field (in the real case), a generating system of the ideal class group, a basis of the ideal class group, the pricipality of an ideal, the equivalence of two ideals, the discrete logarithm of an ideal class with respect to another ideal class, and the order of a class in the ideal class group. While several of these problems belong to the aforementioned complexity classes unconditionally, others require a certain assumption to ensure that the verification procedures can be done in polynomial time; so far, this assumption has only been verified for fields of high genus.     

An Interior Proximal Method for a Class of Quasimonotone Variational Inequalities

The Bregman-function-based Proximal Point Algorithm for variational inequalities is studied. Classical papers on this method deal with the assumption that the operator of the variational inequality is monotone. Motivated by the fact that this assumption can be considered to be restrictive, e.g., in the discussion of Nash equilibrium problems, the main objective of the present paper is to provide a convergence analysis only using a weaker assumption called quasimonotonicity. To the best of our knowledge, this is the first algorithm established for this general and frequently studied class of problems.     

Regularization method with two parameters for nonlinear ill-posed problems

This paper is devoted to the regularization of a class of nonlinear ill-posed problems in Banach spaces. The operators involved are multi-valued and the data are assumed to be known approximately. Under the assumption that the original problem is solvable, a strongly convergent approximation procedure is designed by means of the Tikhonov regularization method with two pa- rameters.     

On the maximum principle for time-optimal controls for a class of distributed-boundary control problems

In this note, we present the necessary conditions of optimality for time-optimal controls for a class of distributed-boundary control problems in general Banach spaces using the semigroup theory. Theorem 3.1 is based on a recent general maximum principle due to Barbu (Ref. 1), which was proved for strictly convex reflexive Banach spaces. Theorem 3.2 generalizes this result (for time-optimal control problems) by lifting the assumption.This work was supported by the National Science and Engineering Council of Canada under Grant No. 7109.     

E-凸多目标规划的最优性及Wolfe型对偶

先引入了一类带不等式和等式约束的E-凸多目标优化问题(MP),给出了该类问题的一个最优性充分条件;其次,建立了该类规划问题(MP)的一类Wolfe型对偶模型(WD),并在E-凸条件下,获得了弱对偶定理,强对偶定理和逆对偶定理.     

Mathematical Problems of Tomography and Hyperbolic Mappings

We consider a new class of mathematical problems related to interpretation of tomography data. The main assumption is that the sought distribution of absorption is an identically one function in the domain to be determined. These problems are connected with three known directions of mathematical physics: the Dirichlet problems for hyperbolic equations, the problems of small oscillations of a rotating fluid, and the problems of supersonic flows of an ideal gas.     

Relative Convergence Estimates for the Spectral Asymptotic in the Large Coupling Limit

We prove optimal convergence estimates for eigenvalues and eigenvectors of a class of singular/stiff perturbed problems. Our profs are constructive in nature and use (elementary) techniques which are of current interest in computational Linear Algebra to obtain estimates even for eigenvalues which are in gaps of the essential spectrum. Further, we also identify a class of “regular” stiff perturbations with (provably) good asymptotic properties. The Arch Model from the theory of elasticity is presented as a prototype for this class of perturbations. We also show that we are able to study model problems which do not satisfy this regularity assumption by presenting a study of a Schroedinger operator with singular obstacle potential.     

Combined Relaxation Method for Mixed Equilibrium Problems

We consider a general class of equilibrium problems which involve a single-valued mapping and a nonsmooth bifunction. Such mixed equilibrium problems are solved with a combined relaxation method using an auxiliary iteration of a splitting-type method for constructing a separating hyperplane. We prove the convergence of the method under the assumption that the dual of the mixed equilibrium problem is solvable. Convergence rates are also derived.S. Schaible - This author gratefully acknowledges partial support from the National Science Council of Taiwan.J.C. Yao - His research was partially supported by Grant NSC 93-2115-M-110-011     

On minkowski metric and weighted tchebyshev norm in vector optimization ∗

The typical approach in solving vector optimization problems is to scalarize the vector cost function into a single cost function by means of some utility or value function. A very large class of utility function is given by the Minkowski’s metric proposed by Charnes and Cooper in the context of goal programming. This includes the special case of linear scalarization and the weighted Tchebyshev norm. We shall furnish a rigorous justification that there is no equivalent relationship between the general vector optimization problem and scalarized optimization problems using any Minkowski’s metric utility function. Furthermore, we also show that the weighted Tchebyshev norm is, in some sense, the best amongst the class of Minkowski’s metric utility functions since it is the only scalarization method which yields an equivalence relation between the weak vector optimization problem and a set of scalar optimization problems, without any convexity assumption     

A monotone finite element scheme for convection-diffusion equations

A simple technique is given in this paper for the construction and analysis of a class of finite element discretizations for convection-diffusion problems in any spatial dimension by properly averaging the PDE coefficients on element edges. The resulting finite element stiffness matrix is an -matrix under some mild assumption for the underlying (generally unstructured) finite element grids. As a consequence the proposed edge-averaged finite element scheme is particularly interesting for the discretization of convection dominated problems. This scheme admits a simple variational formulation, it is easy to analyze, and it is also suitable for problems with a relatively smooth flux variable. Some simple numerical examples are given to demonstrate its effectiveness for convection dominated problems.

     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

Structure of entropy solutions to the eikonal equation

In this paper, we establish rectifiability of the jump set of an S ¹–valued conservation law in two space–dimensions. This conservation law is a reformulation of the eikonal equation and is motivated by the singular limit of a class of variational problems. The only assumption on the weak solutions is that the entropy productions are (signed) Radon measures, an assumption which is justified by the variational origin. The methods are a combination of Geometric Measure Theory and elementary geometric arguments used to classify blow–ups.?The merit of our approach is that we obtain the structure as if the solutions were in BV, without using the BV–control, which is not available in these variationally motivated problems. Received June 24, 2002 / final version received November 12, 2002?Published online February 7, 2003     

Idealized program packages and problems of positional control with incomplete information

The paper is devoted to developing the method of program packages as a tool for investigating problems of positional control with incomplete information. The method is embedded in the field of guaranteed control theory and was stipulated by a number of constructions from this theory. Under the assumption that an a priori given set of initial positions of a controlled system is finite, it is established that the solvability of a guaranteed guidance problem in the class of program packages (or, which is the same, in the class of positional strategies) is equivalent to the solvability of this problem in the class of considerably simpler program operators, namely, in the class of idealized program packages.     

Specially Structured Precedence Constraints in Three-Dimensional Bottleneck Assignment Problems

A three-dimensional, time-minimizing (bottleneck) assignment problem consists of assigning n jobs to n workers to be performed on n machines under different forms of feasibility conditions so that the different functions of the individual times taken by a worker to finish a job on a given machine are minimized. The usual assumption made in such a problem is that all the jobs can be commenced simultaneously. In this paper, two specially structured precedence constraints on jobs are considered, which necessitate modifications in this assumption. Further, the main purpose here is to develop branch-and-bound-type algorithms for solving the corresponding problems and to illustrate them by a numerical example.     

Global entropy solutions to a class of quasi-linear wave equations with large time-oscillating sources

This research explores the Cauchy problem for a class of quasi-linear wave equations with time dependent sources. It can be transformed into the Cauchy problem of hyperbolic integro-differential systems of nonlinear balance laws. We introduce the generalized Glimm scheme in new version and study its stability which is proved by Glimm-type interaction estimates in a dissipativity assumption. The generalized solutions to the perturbed Riemann problems, the building blocks of generalized Glimm scheme, are constructed by Riemann problem method modeled on the source free equations. The global existence for the Lipschitz continuous solutions and weak solutions to the systems is established by the consistency of scheme and the weak convergence of source. Finally, the weak solutions are also the entropy solutions which satisfy the entropy inequality.     

Regularized extragradient method in multicriteria control problems with inaccurate data

The class of Hilbert space multicriteria optimization problems considered in the paper includes control problems for various dynamical systems with lumped as well as distributed parameters. An equilibrium point is sought under the assumption that the criteria and their derivatives are known approximately. We use a regularized extragradient method and prove its convergence. As a sample application of the general theory, we consider a control problem for a parabolic equation with two criteria.     

An adaptive finite element method with asymptotic saturation for eigenvalue problems

This paper discusses adaptive finite element methods for the solution of elliptic eigenvalue problems associated with partial differential operators. An adaptive method based on nodal-patch refinement leads to an asymptotic error reduction property for the computed sequence of simple eigenvalues and eigenfunctions. This justifies the use of the proven saturation property for a class of reliable and efficient hierarchical a posteriori error estimators. Numerical experiments confirm that the saturation property is present even for very coarse meshes for many examples; in other cases the smallness assumption on the initial mesh may be severe.     

The Lipschitzianity of convex vector and set-valued functions

It is well known that every scalar convex function is locally Lipschitz on the interior of its domain in finite dimensional spaces. The aim of this paper is to extend this result for both vector functions and set-valued mappings acting between infinite dimensional spaces with an order generated by a proper convex cone C. Under the additional assumption that the ordering cone C is normal, we prove that a locally C-bounded C-convex vector function is Lipschitz on the interior of its domain by two different ways. Moreover, we derive necessary conditions for Pareto minimal points of vector-valued optimization problems where the objective function is C-convex and C-bounded. Corresponding results are derived for set-valued optimization problems.     

Refinements of existence results for relaxed quasimonotone equilibrium problems

We consider a general equilibrium problem in a normed vector space setting and we establish sufficient conditions for the existence of solutions in compact and non compact cases. Our approach is based on the concept of upper sign property for bifunctions, which turns out to be a very weak assumption for equilibrium problems. In the framework of variational inequalities, this notion coincides with the upper sign continuity for a set-valued operator introduced by Hadjisavvas. More in general, it allows to strengthen a number of existence results for the class of relaxed $\mu $ -quasimonotone equilibrium problems.     

小批量随机块坐标下降算法

针对机器学习中广泛存在的一类问题：结构化随机优化问题（其中“结构化”是指问题的可行域具有块状结构,且目标函数的非光滑正则化部分在变量块之间是可分离的）,我们研究了小批量随机块坐标下降算法（mSBD）。按照求解非复合问题和复合问题分别给出了基本的mSBD和它的变体,对于非复合问题,分析了算法在没有一致有界梯度方差假设情况下的收敛性质。而对于复合问题,在不需要通常的Lipschitz梯度连续性假设条件下得到了算法的收敛性。最后通过数值实验验证了mSBD的有效性。