Distributed modelling of propagation of computer viruses/worms by partial differential equations

Two distributed Partial Differential Equations-based (PDES-based) mathematical models of propagation of computer viruses are derived for the first time. It is shown that experimental studies and inverse problems should be two main topics of further research of these models. The recently developed so-called globally convergent convexification numerical method of the author and Timonov is a good candidate to be a base of corresponding inverse algorithms.     

Global solution of optimization problems with signomial parts

In this paper a new approach for the global solution of nonconvex MINLP (Mixed Integer NonLinear Programming) problems that contain signomial (generalized geometric) expressions is proposed and illustrated. By applying different variable transformation techniques and a discretization scheme a lower bounding convex MINLP problem can be derived. The convexified MINLP problem can be solved with standard methods. The key element in this approach is that all transformations are applied termwise. In this way all convex parts of the problem are left unaffected by the transformations. The method is illustrated by four example problems.     

The Law of Large Numbers in a Metric Space with a Convex Combination Operation

We consider a separable complete metric space equipped with a convex combination operation. For such spaces, we identify the corresponding convexification operator and show that the invariant elements for this operator appear naturally as limits in the strong law of large numbers. It is shown how to uplift the suggested construction to work with subsets of the basic space in order to develop a systematic way of proving laws of large numbers for such operations with random sets.     

The Erdős–Nagy theorem and its ramifications

Given a simple polygon in the plane, a flip is defined as follows: consider the convex hull of the polygon. If there are no pockets do not perform a flip. If there are pockets then reflect one pocket across its line of support of the polygon to obtain a new simple polygon. In 1934 Paul Erdős introduced the problem of repeatedly flipping all the pockets of a simple polygon simultaneously and he conjectured that the polygon would become convex after a finite number of flips. In 1939 Béla Nagy proved that if at each step only one pocket is flipped the polygon will become convex after a finite number of flips. The history of this problem is reviewed, and a simple elementary proof is given of a stronger version of the theorem. Variants, generalizations, and applications of the theorem of interest in computational knot theory, polymer physics and molecular biology are discussed. Several results in the literature are improved with the application of the theorem. For example, Grünbaum and Zaks recently showed that even non-simple (self-crossing) polygons may be convexified in a finite number of suitable flips. Their flips each take Θ(n²) time to determine. A simpler proof of this result is given that yields an algorithm that takes O(n) time to determine each flip. In the context of knot theory Millet proposed an algorithm for convexifying equilateral polygons in 3-dimensions with a generalization of a flip called a pivot. Here Millet's algorithm is generalized so that it works also in dimensions higher than three and for polygons containing edges with arbitrary lengths. A list of open problems is included.     

The Cauchy problem for the homogeneous Monge–Ampère equation, II. Legendre transform

We continue our study of the Cauchy problem for the homogeneous (real and complex) Monge–Ampère equation (HRMA/HCMA). In the prequel (Y.A. Rubinstein and S. Zelditch [27]) a quantum mechanical approach for solving the HCMA was developed, and was shown to coincide with the well-known Legendre transform approach in the case of the HRMA. In this article—that uses tools of convex analysis and can be read independently—we prove that the candidate solution produced by these methods ceases to solve the HRMA, even in a weak sense, as soon as it ceases to be differentiable. At the same time, we show that it does solve the equation on its dense regular locus, and we derive an explicit a priori upper bound on its Monge–Ampère mass. The technique involves studying regularity of Legendre transforms of families of non-convex functions.     

Local saddle point and a class of convexification methods for nonconvex optimization problems

A class of general transformation methods are proposed to convert a nonconvex optimization problem to another equivalent problem. It is shown that under certain assumptions the existence of a local saddle point or local convexity of the Lagrangian function of the equivalent problem (EP) can be guaranteed. Numerical experiments are given to demonstrate the main results geometrically.     

Convexity of Products of Univariate Functions and Convexification Transformations for Geometric Programming

We investigate the characteristics that have to be possessed by a functional mapping f:ℝ↦ℝ so that it is suitable to be employed in a variable transformation of the type x→f(y) in the convexification of posynomials. We study first the bilinear product of univariate functions f ₁(y ₁), f ₂(y ₂) and, based on convexity analysis, we derive sufficient conditions for these two functions so that ℱ₂(y ₁,y ₂)=f ₁(y ₁)f ₂(y ₂) is convex for all (y ₁,y ₂) in some box domain. We then prove that these conditions suffice for the general case of products of univariate functions; that is, they are sufficient conditions for every f _i (y _i ), i=1,2,…,n, so as ℱ _n (y ₁,y ₂,…,y _n )=∏ _i=1 ⁿ f _i (y _i ) to be convex. In order to address the transformation of variables that are exponentiated to some power κ≠1, we investigate under which further conditions would the function (f) ^κ be also suitable. The results provide rigorous reasoning on why transformations that have already appeared in the literature, like the exponential or reciprocal, work properly in convexifying posynomial programs. Furthermore, a useful contribution is in devising other transformation schemes that have the potential to work better with a particular formulation. Finally, the results can be used to infer the convexity of multivariate functions that can be expressed as products of univariate factors, through conditions on these factors on an individual basis. The authors gratefully acknowledge support from the National Science Foundation.     

Comparative studies of the globally convergent convexification algorithm with application to imaging of antipersonnel land mines

A comparative study of various aspects on the globally convergent convexification algorithm for coefficient inverse problems is described. Numerical results of the algorithm with application to detection of antipersonnel land mines are presented. The aspects studied include initial guess and layer size for the layer stripping approach, dimensions of the basis for spatial and pseudo-frequency approximations, the lower limit of the integrals with respect to pseudo-frequency κ, the stopping criteria of steepest descent method in the least squares minimization, the tails to compensate the truncated integration with respect to κ, the parameter λ associated with the Carleman weight function, and adding different noise levels to the input data for the coefficient inverse problems. With our new implementation, the convexification algorithm is very efficient and feasible to be applied in real time to detect antipersonnel land mines in the field.     

Successive Optimization Method via Parametric Monotone Composition Formulation*

In this paper a successive optimization method for solving inequality constrained optimization problems is introduced via a parametric monotone composition reformulation. The global optimal value of the original constrained optimization problem is shown to be the least root of the optimal value function of an auxiliary parametric optimization problem, thus can be found via a bisection method. The parametric optimization subproblem is formulated in such a way that it is a one-parameter problem and its value function is a monotone composition function with respect to the original objective function and the constraints. Various forms can be taken in the parametric optimization problem in accordance with a special structure of the original optimization problem, and in some cases, the parametric optimization problems are convex composite ones. Finally, the parametric monotone composite reformulation is applied to study local optimality.