A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes

In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC representation. This subgradient information is gathered from some neighborhood of the current iteration point and it is used to build separately an approximation for each component in the DC representation. By combining these approximations we obtain a new nonconvex cutting plane model of the original objective function, which takes into account explicitly both the convex and the concave behavior of the objective function. We design the proximal bundle method for DC programming based on this new approach and prove the convergence of the method to an \(\varepsilon \)-critical point. The algorithm is tested using some academic test problems and the preliminary numerical results have shown the good performance of the new bundle method. An interesting fact is that the new algorithm finds nearly always the global solution in our test problems.     

Generalized Quasilinearization for Quasilinear Parabolic Equations with Nonlinearities of DC Type

In this paper, we consider an initial boundary-value problem for a class of quasilinear parabolic equations whose lower-order nonlinearity is of d.c. function type with respecxt to the dependent variable. Assuming the existence of an ordered pair of weak upper and lower solutions, we establish a generalized quasilinearization method for the problem under consideration. A characteristic feature of this generalized quasilinearization method consists in the construction of monotone sequences converging to the unique solution within the interval of upper and lower solutions, and whose convergence rate is quadratic.     

The Resurgence Properties of the Incomplete Gamma Function II

In this paper, we derive a new representation for the incomplete gamma function, exploiting the reformulation of the method of steepest descents by Howls 1992. Using this representation, we obtain numerically computable bounds for the remainder term of the asymptotic expansion of the incomplete gamma function with large a and fixed positive λ, and an asymptotic expansion for its late coefficients. We also give a rigorous proof of Dingle's formal result regarding the exponentially improved version of the asymptotic series of .     

On a robust version of the integral representation formula of nonlinear filtering

The paper is concerned with completing “unfinished business” on a robust representation formula for the conditional expectation operator of nonlinear filtering. Such a formula, robust in the sense that its dependence on the process of observations is continuous, was stated in [2] without proof. The main purpose of this paper is to repair this deficiency.The formula is “almost obvious” as it can be derived at a formal level by a process of integration-by-parts applied to the stochastic integrals that appear in the integral representation formula. However, the rigorous justification of the formula is quite subtle, as it hinges on a measurability argument the necessity of which is easy to miss at first glance. The continuity of the representation (but not its validity) was proved by Kushner [9] for a class of diffusions.Here we follow the definition given in [11].     

Ultradifferential operators in the study of Gevrey solvability and regularity

In this work we present a new representation formula for ultradistributions using the so‐called ultradifferential operators. The main difference between our representation result and other works is that here we do not break the duality of Gevrey functions of other s and their ultradistributions, i.e., we locally represent an element of by an infinite order operator acting on a function of class . Our main application was in the local solvability of the differential complex associated to a locally integrable structure in a Gevrey environment.     

A Method for Converting a Class of Univariate Functions into d.c. Functions

D.c. functions are functions that can be expressed as the sum of a concave function and a convex function (or as the difference of two convex functions). In this paper, we extend the class of univariate functions that can be represented as d.c. functions. This expanded class is very broad including a large number of nonlinear and/or nonsmooth univariate functions. In addition, the procedure specifies explicitly the functional and numerical forms of the concave and convex functions that comprise the d.c. representation of the univariate functions. The procedure is illustrated using two numerical examples. Extensions of the conversion procedure for discontinuous univariate functions is also discussed.     

基于结构元的模糊值函数的一般表示方法

文[1]提出了模糊结构元的概念,并给出了模糊数与模糊值函数的模糊结构元表示,以及一类由模糊结构元线性生成的模糊值函数的微分和积分(黎曼意义下的)的表达形式。本文在文[1]的基础上进一步给出了由模糊结构元生成的模糊值函数的一般表达形式,并得到了一般表达形式下的模糊值函数的连续性和微分、黎曼积分的定义,它们与传统模糊分析中相应定义是等价的。     

RELU DEEP NEURAL NETWORKS AND LINEAR FINITE ELEMENTS

In this paper, we investigate the relationship between deep neural networks (DNN) with rectified linear unit (ReLU) function as the activation function and continuous piecewise linear (CPWL) functions, especially CPWL functions from the simplicial linear finite element method (FEM). We first consider the special case of FEM. By exploring the DNN representation of its nodal basis functions, we present a ReLU DNN representation of CPWL in FEM. We theoretically establish that at least $2$ hidden layers are needed in a ReLU DNN to represent any linear finite element functions in $\Omega \subseteq \mathbb{R}^d$ when $d\ge2$. Consequently, for $d=2,3$ which are often encountered in scientific and engineering computing, the minimal number of two hidden layers are necessary and sufficient for any CPWL function to be represented by a ReLU DNN. Then we include a detailed account on how a general CPWL in $\mathbb R^d$ can be represented by a ReLU DNN with at most $\lceil\log_2(d+1)\rceil$ hidden layers and we also give an estimation of the number of neurons in DNN that are needed in such a representation. Furthermore, using the relationship between DNN and FEM, we theoretically argue that a special class of DNN models with low bit-width are still expected to have an adequate representation power in applications. Finally, as a proof of concept, we present some numerical results for using ReLU DNNs to solve a two-point boundary problem to demonstrate the potential of applying DNN for numerical solution of partial differential equations.     

Second-Order Global Optimality Conditions for Optimization Problems

Second-order optimality conditions are studied for the constrained optimization problem where the objective function and the constraints are compositions of convex functions and twice strictly differentiable functions. A second-order sufficient condition of a global minimizer is obtained by introducing a generalized representation condition. Second-order minimizer characterizations for a convex program and a linear fractional program are derived using the generalized representation condition     

Optimization of the Norm of a Vector-Valued DC Function and Applications

In this paper, we show that a DC representation can be obtained explicitly for the composition of a gauge with a DC mapping, so that the optimization of certain functions involving terms of this kind can be made by using standard DC optimization techniques. Applications to facility location theory and multiple-criteria decision making are presented.     

On the Green Function of the Annulus

Using the Gegenbauer polynomials and the zonal harmonics functions we give some representation formula of the Green function in the annulus. We apply this result to prove some uniqueness results for some nonlinear elliptic problems.     

On the degree and separability of nonconvexity and applications to optimization problems

We study qualitative indications for d.c. representations of closed sets in and functions on Hilbert spaces. The first indication is an index of nonconvexity which can be regarded as a measure for the degree of nonconvexity. We show that a closed set is weakly closed if this indication is finite. Using this result we can prove the solvability of nonconvex minimization problems. By duality a minimization problem on a feasible set in which this indication is low, can be reduced to a quasi-concave minimization over a convex set in a low-dimensional space. The second indication is the separability which can be incorporated in solving dual problems. Both the index of nonconvexity and the separability can be characteristics to “good” d.c. representations. For practical computation we present a notion of clouds which enables us to obtain a good d.c. representation for a class of nonconvex sets. Using a generalized Caratheodory’s theorem we present various applications of clouds.     

Rationality,minimality and uniqueness of representation of matrix formal power series

In some multivariate time-series models a matrix power series is involved. These models can be identified as rational models if these series correspond to a matrix rational function. Moreover, it is necessary to answer some questions about minimality and uniqueness of representation. The main results of this paper fall within the sphere of matrix Padé approximation. On the basis of formal power series, matrix rational functions of arbitrary dimensions are characterized. Furthermore, we study certain minimality types, that are, global minimum degrees and row minimum degrees. In addition, given that the rational representation of the function for the same pair of degrees need not be unique, we have obtained conditions to study the uniqueness of said representation and, also, to find a “canonical” unique representation. Moreover, we consider an application to special series which is associated with time-series models; such series leads to new theoretical results relating to matrix Padé approximation. Finally, we comment on some illustrative examples.     

Gabor frames and directional time–frequency analysis

We introduce a directionally sensitive time–frequency decomposition and representation of functions. The coefficients of this representation allow us to measure the “amount” of frequency a function (signal, image) contains in a certain time interval, and also in a certain direction. This has been previously achieved using a version of wavelets called ridgelets [E.J. Candès, Harmonic analysis of neural networks, Appl. Comput. Harmon. Anal. 6 (1999) 197–218. [2]; E.J. Candès, D.L. Donoho, New tight frames of curvelets and optimal representations of objects with piesewise-C² singularities, Comm. Pure Appl. Math. 57 (2004) 219–266. [3]] but in this work we discuss an approach based on time–frequency or Gabor elements. For such elements, a Parseval formula and a continuous frame-type representation together with boundedness properties of a semi-discrete frame operator are obtained. Spaces of functions tailored to measure quantitative properties of the time–frequency–direction analysis coefficients are introduced and some of their basic properties are discussed. Applications to image processing and medical imaging are presented.     

Exponential Hilbert series and the Stirling numbers of the second kind

We consider the exponential generating function whose coefficients encode the dimensions of irreducible highest weight representations which lie on a given ray in the dominant chamber of the weight lattice. This formal power series can be considered as an exponential version of the Hilbert series of a flag variety. In this context, we compute a simple closed form for the exponential generating function in terms of finitely many differential operators and the Stirling polynomials. We prove that this series converges to a product of a rational polynomial and an exponential, and that, by summing the constant term and linear coefficient of this polynomial, we recover the dimension of the representation.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

Triangular Matrix Representations

In this paper we develop the theory of generalized triangular matrix representation in an abstract setting. This is accomplished by introducing the concept of a set of left triangulating idempotents. These idempotents determine a generalized triangular matrix representation for an algebra. The existence of a set of left triangulating idempotents does not depend on any specific conditions on the algebras; however, if the algebra satisfies a mild finiteness condition, then such a set can be refined to a “complete” set of left triangulating idempotents in which each “diagonal” subalgebra has no nontrivial generalized triangular matrix representation. We then apply our theory to obtain new results on generalized triangular matrix representations, including extensions of several well known results.     

A Hierarchy of Relaxations Leading to the Convex Hull Representation for General Discrete Optimization Problems

We consider linear mixed-integer programs where a subset of the variables are restricted to take on a finite number of general discrete values. For this class of problems, we develop a reformulation-linearization technique (RLT) to generate a hierarchy of linear programming relaxations that spans the spectrum from the continuous relaxation to the convex hull representation. This process involves a reformulation phase in which suitable products using a defined set of Lagrange interpolating polynomials (LIPs) are constructed, accompanied by the application of an identity that generalizes x(1−x) for the special case of a binary variable x. This is followed by a linearization phase that is based on variable substitutions. The constructs and arguments are distinct from those for the mixed 0-1 RLT, yet they encompass these earlier results. We illustrate the approach through some examples, emphasizing the polyhedral structure afforded by the linearized LIPs. We also consider polynomial mixed-integer programs, exploitation of structure, and conditional-logic enhancements, and provide insight into relationships with a special-structure RLT implementation.     

Representing probability measures using probabilistic processes

In the Type-2 Theory of Effectivity, one considers representations of topological spaces in which infinite words are used as “names” for the elements they represent. Given such a representation, we show that probabilistic processes on infinite words, under which each successive symbol is determined by a finite probabilistic choice, generate Borel probability measures on the represented space. Conversely, for several well-behaved types of space, every Borel probability measure is represented by a corresponding probabilistic process. Accordingly, we consider probabilistic processes as providing “probabilistic names” for Borel probability measures. We show that integration is computable with respect to the induced representation of measures.