An algorithm for calculating one subgradient of a convex function of two variables

Summary We present an algorithm which enables us to calculate one particular subgradient of a convex functionf: ² at a given point. Such a calculation is required in many existing numerical methods for convex nondifferentiable optimization. The novelty of our approach lies in the assumption that only the values off are computable and no analytical formula for the subdifferential is known. We include some numerical examples.     

Canonical Dual Transformation Method and Generalized Triality Theory in Nonsmooth Global Optimization*

This paper presents, within a unified framework, a potentially powerful canonical dual transformation method and associated generalized duality theory in nonsmooth global optimization. It is shown that by the use of this method, many nonsmooth/nonconvex constrained primal problems in ⁿ can be reformulated into certain smooth/convex unconstrained dual problems in ^m with m n and without duality gap, and some NP-hard concave minimization problems can be transformed into unconstrained convex minimization dual problems. The extended Lagrange duality principles proposed recently in finite deformation theory are generalized suitable for solving a large class of nonconvex and nonsmooth problems. The very interesting generalized triality theory can be used to establish nice theoretical results and to develop efficient alternative algorithms for robust computations.     

The Newton Bracketing Method for Convex Minimization

An iterative method for the minimization of convex functions f :ⁿ , called a Newton Bracketing (NB) method, is presented. The NB method proceeds by using Newton iterations to improve upper and lower bounds on the minimum value. The NB method is valid for n = 1, and in some cases for n > 1 (sufficient conditions given here). The NB method is applied to large scale Fermat–Weber location problems.     

Parametrization via secant length and application to path following

Summary A possible way for parametrizing the solution path of the nonlinear systemH(u)=0, H: ^{n+1 n} consists of using the secant length as parameter. This idea leads to a quadratic constraint by which the parameter is introduced. A Newton-like method for computing the solution for a given parameter is proposed where the nonlinear system is linearized at each iterate, but the quadratic parametrizing equation is exactly satisfied. The localQ-quadratic convergence of the method is proved and some hints for implementing the algorithm are givenDedicated to Professor Lothar Collatz on the occasion of his 75th birthday     

Convergence of an upstream finite volume scheme for a nonlinear hyperbolic equation on a triangular mesh

Summary We study here the discretisation of the nonlinear hyperbolic equationu _t +div(vf(u))=0 in ³ × ₊, with given initial conditionu(.,0)=u ₀(.) in ², wherev is a function from ² × ₊ to ² such that divv=0 andf is a given nondecreasing function from to . An explicit Euler scheme is used for the time discretisation of the equation, and a triangular mesh for the spatial discretisation. Under a usual stability condition, we prove the convergence of the solution given by an upstream finite volume scheme towards the unique entropy weak solution to the equation.     

On the semiboundedness ofδ-perturbations of the laplacian supported by curves with angle points

Elementary self-adjoint perturbations of the Laplacian supported by curves with singular angle points in ³ and ⁴ are studied. The perturbations are shown to be semibounded in ³ and not semibounded in ⁴. In the latter case semiboundedness may take place in subspaces with a given symmetry, as simple examples illustrate.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 105, No. 1, pp. 3–17, October, 1995.     

Extremal types for certainL p minimization problems and associated large scale nonlinear programs

Extremals for constrained minimization problems, min F, are classified according to the growth properties of the linear functionalF() restricted to . Various singular and nonsingular extremal types are investigated in detail for the special case where = {measurableu(·): [0, 1] U},U = a bounded polyhedral convex set in ^m , andF is understood in Fréchet's sense relative to anL ^p norm withp [1, ). The analysis yields newL ^p minimization corollaries of recently developed general convergence rate theories for conditional and projected gradient methods, and a Newton method for constrained minimization. These results help to explain trends in the behavior of computational procedures for certain large scale structured nonlinear programs in ^k ask increases to , with particular application to a large class of optimal control problems with linearly constrained inputs; control problems with bang-bang solutions are considered at some length.Investigation supported by NSF Research Grants ECS-8005958 and ENG 78-03385.     

Heuristic solutions to polynomial moment problems with some convex entropic objectives

We are asking to estimate a nonnegative density on ^m , given some of its algebraic or trigonometric moments. The maximum entropy method is to introduce an entropy-like objective function and then solve a convex minimization programming with some linear constraints. In the existing literature, Newton's method or some other iteration methods are used to solve its dual problem. In this paper, special structures of the problem have been discovered when we use some particular entropies, which include Boltzmann-Shannon entropy and Burg's entropy. Useful linear relationships among the moments help us to set up very fast and effective algorithms. Numerical computations and comparison are also presented.     

On Non-Negative Elliptic-Type Differential Inequalities in ℝ n , Vanishing Almost Everywhere on Some Open Subset in ℝ n

It is proved in this article that any generalized solution of a sufficiently general class of elliptic-type differential inequalities in  ⁿ that is non-negative almost everywhere in  ⁿ and vanishes almost everywhere on an open set ⁿ is trivial in  ⁿ .     

Distributionen mit Werten in topologischen Vektorräumen I

In this article, distributions with values in a (not necessarily locally convex) topological vector space E are defined to be the elements of. Operations on such distributions can be introduced as usual. In general, not every continuous E-valued function defines a distribution, but the elements of do. A large part of the theory is reduced to the locally convex case by use of the so-called locally convex subspaces of E (cf. [2]). We prove that the presheaf of E-valued distributions on open subsets of ^N is a topological sheaf. We give integral representation theorems for bounded mappings in and, and we show that, on bounded subsets of ^N, each distribution defined on ^N with values in a (p)-space is a derivative of a function in.

---

---

Während der Fertigstellung eines Teils dieser Arbeit Research Associate der University of Maryland, Md. 20742, USA.     

Vektorwertige Distributionen als Randverteilungen holomorpher Funktionen

This paper is concerned with the problem, for which locally convex spaces E every E-valued distribution on is representable by the boundary values of an E-valued holomorphic function on /, resp. for which spaces is solvable in C(²,E). This is known in the case of (F)-spaces. A complete solution is given in the case of (DF)-spaces. The class of (DF)-spaces, we obtain, turns out to be interesting in a much wider context. This will be contained in a forthcoming paper.     

Implicit elliptic boundary-value problems with discontinuous nonlinearities

Let be a bounded domain in ⁿ (n3) having a smooth boundary, let be an essentially bounded real-valued function defined on × ^h, and let be a continuous real-valued function defined on a given subset Y of Y ^h. In this paper, the existence of strong solutions u W ^2,p (, ^h) W _o ^1,p (n/2<p<+) to the implicit elliptic equation (–u)=(x,u), with u=(u₁, u₂, ..., u_h) and u=(u ₁, u ₂, ..., u _h), is established. The abstract framework where the problem is placed is that of set-valued analysis.     

Minimizing and Stationary Sequences of Convex Constrained Minimization Problems

In the asymptotic analysis of the minimization problem for a nonsmooth convex function on a closed convex set X in ⁿ, one can consider the corresponding problem of minimizing a smooth convex function F on ⁿ, where F denotes the Moreau–Yosida regularization of f. We study the interrelationship between the minimizing/stationary sequence for f and that for F. An algorithm is given to generate iteratively a possibly unbounded sequence, which is shown to be a minimizing sequence of f under certain regularity and uniform continuity assumptions.     

Planar point-objective location problems with nonconvex constraints: A geometrical construction

The planar point-objective location problem has attracted considerable interest among Location Theory researchers. The result has been a number of papers giving properties or algorithms for particular instances of the problem. However, most of these results are only valid when the feasible region where the facility is to be located is the whole space ², which is a rather inaccurate approximation in many real world location problems.In this paper, the feasible region is allowed to be any closed, not necessarily convex, setS in ². The special structure of this nonconvex vector-optimization problem is exploited, leading to a geometrical resolution procedure when the feasible regionS can be decomposed into a finite number of (not necessarily disjoint) polyhedra.     

Complete controllability

A linear autonomous control system in ⁿ is said to be completely controllable iff there existsT>0 such that eachx ⁿ can be steered to anyy ⁿ in timeT. This paper presents a geometric characterization of this property in the case in which there are constraints on the values which the control maps can assume. A necessary and sufficient condition to get instant controllability (i.e., complete controllability for anyT>0) is also derived. This condition generalizes the well-known Kalman condition to the constrained case.     

Constraint decomposition algorithms in global optimization

Many global optimization problems can be formulated in the form min{c(x, y): x X, y Y, (x, y) Z, y G} where X, Y are polytopes in ^p , ⁿ , respectively, Z is a closed convex set in ^p+n, while G is the complement of an open convex set in ⁿ . The function c: ^p+n is assumed to be linear. Using the fact that the nonconvex constraints depend only upon they-variables, we modify and combine basic global optimization techniques such that some new decomposition methods result which involve global optimization procedures only in ⁿ . Computational experiments show that the resulting algorithms work well for problems with smalln.     

On a Class of Convex Sets and Functions

Given a convex subset C of ⁿ, the set-valued mapping C (where 0C is, by convention, the recession cone of C) is increasing on ₊ if and only if C contains the origin, and decreasing on ₊ if and only if C is contained in its recession cone. This simple fact enables us to define a binary operation which combines a concave or convex function on ^m with a convex subset of ⁿ to produce a convex subset of ^n+m. This binary operation is the set theoretic counterpart of a functional operation introduced by the author. In this paper, we present a detailed study of the class of convex subsets which are contained in their recession cones, and we establish some remarkable properties of our binary operation.Mathematics Subject Classifications (2000) 26A51, 26B25, 26E25.     

Monotonically convergent iterative methods for nonlinear systems of equations

Summary This paper deals with discrete analogues of nonlinear elliptic boundary value problems and with monotonically convergent iterative methods for their numerical solution. The discrete analogues can be written asM(u)u+H(u)=0, whereM(u) is ann%n M-matrix for eachu ⁿ andH: ^{n n} . The numerical methods considered are the natural undeerrelaxation method, the successive underrelaxation method, and the Jacobi underrelaxation method. In the linear case and without underrelaxation these methods correspond to the direct, the Gauss-Seidel, and the Jacobi method for solving the underlying system of equations, resp. For suitable starting vectors and sufficiently strong underrelaxation, the sequence of iterates generated by any of these methods is shown to converge monotonically to a solution of the underlying system.     

The fundamentality of sets of ridge functions

Summary We investigate the fundamentality of the set of all continuous ridge functions in the spaceC( ⁿ ) as well as inC(X) for a general Banach space,X. Both positive and negative results are obtained. Necessary and sufficient conditions for the fundamentality are given for certain sets of ridge functions inC( ⁿ ).     

The interactive fixed charge inhomogeneous flows optimization problem

An optimization problem of interactive inhomogenous flows (Steiner multicommodity network flow problem) is formulated. The problem's main characteristic is a fixed charge change when combining multicommodity communications. In this paper we propose a method for solving this problem which, in order to restrict the search on the feasible domain, reduces the original problem to a concave programming problem in the form: min {f(x)|xX} wheref:ⁿ is a concave function, andX ₀ ⁿ is a flow polytope defined by network transportation constraints. For practical large-scale problems arising from planning transportation networks on inhomogeneous surfaces defined by a digital model, a method of local optimization over a flow polytope vertex set is proposed, which is far more effective in comparison with the Gallo and Sodini method under polytope strong degeneracy conditions.