A new global optimization method for a symmetric Lipschitz continuous function and the application to searching for a globally optimal partition of a one-dimensional set

In this paper, we consider a global optimization problem for a symmetric Lipschitz continuous function \(g:[a,b]^k\rightarrow {\mathbb {R}}\), whose domain \([a,b]^k\subset {\mathbb {R}}^k\) consists of k! hypertetrahedrons of the same size and shape, in which function g attains equal values. A global minimum can therefore be searched for in one hypertetrahedron only, but then this becomes a global optimization problem with linear constraints. Apart from that, some known global optimization algorithms in standard form cannot be applied to solving the problem. In this paper, it is shown how this global optimization problem with linear constraints can easily be transformed into a global optimization problem on hypercube \([0,1]^k\), for the solving of which an applied DIRECT algorithm in standard form is possible. This approach has a somewhat lower efficiency than known global optimization methods for symmetric Lipschitz continuous functions (such as SymDIRECT or DISIMPL), but, on the other hand, this method allows for the use of publicly available and well developed computer codes for solving a global optimization problem on hypercube \([0,1]^k\) (e.g. the DIRECT algorithm). The method is illustrated and tested on standard symmetric functions and very demanding center-based clustering problems for the data that have only one feature. An application to the image segmentation problem is also shown.     

Solution of symmetric linear complementarity problems by iterative methods

A unified treatment is given for iterative algorithms for the solution of the symmetric linear complementarity problem: $$Mx + q \geqslant 0, x \geqslant 0, x^T (Mx + q) = 0$$ , whereM is a givenn×n symmetric real matrix andq is a givenn×1 vector. A general algorithm is proposed in which relaxation may be performed both before and after projection on the nonnegative orthant. The algorithm includes, as special cases, extensions of the Jacobi, Gauss-Seidel, and nonsymmetric and symmetric successive over-relaxation methods for solving the symmetric linear complementarity problem. It is shown first that any accumulation point of the iterates generated by the general algorithm solves the linear complementarity problem. It is then shown that a class of matrices, for which the existence of an accumulation point that solves the linear complementarity problem is guaranteed, includes symmetric copositive plus matrices which satisfy a qualification of the type: $$Mx + q > 0 for some x in R^n $$ . Also included are symmetric positive-semidefinite matrices satisfying this qualification, symmetric, strictly copositive matrices, and symmetric positive matrices. Furthermore, whenM is symmetric, copositive plus, and has nonzero principal subdeterminants, it is shown that the entire sequence of iterates converges to a solution of the linear complementarity problem.     

Duality in Truncated Steady-State Erlang Distribution-Based Queueing Processes

In this paper, the notion of duality and a generalized methodology to identify the dual for an Erlang distribution-based truncated steady-state queueing process is suggested. This procedure provides insight into truncated queueing processes. At first glance, the relationship between the primal problem and the dual problem may not be intuitive. Several such relationships are identified. For example, the dual of the M/E_s/C/C queueing process is shown to be the M/M/1 machine interference problem with C machines and the solution to one of these provides the solution to the other. An example is presented.     

An accelerated augmented Lagrangian method for linearly constrained convex programming with the rate of convergence <Emphasis Type="Italic">O</Emphasis>(1/<Emphasis Type="Italic">k</Emphasis><Superscript>2</Superscript>)

In this paper, we propose and analyze an accelerated augmented Lagrangian method (denoted by AALM) for solving the linearly constrained convex programming. We show that the convergence rate of AALM is O(1/k ²) while the convergence rate of the classical augmented Lagrangian method (ALM) is O(1/k). Numerical experiments on the linearly constrained l ₁?l ₂ minimization problem are presented to demonstrate the effectiveness of AALM.     

On a class of solutions of KdV

Practically every book on the Inverse Scattering Transform method for solving the Cauchy problem for KdV and other integrable systems refers to this method as nonlinear Fourier transform. If this is indeed so, the method should lead to a nonlinear analogue of the Fourier expansion formula . In this paper a special class of solutions of KdV whose role is similar to that of e^i(kx-ω(k)t) is discussed. The theory of these solutions, referred to here as harmonic breathers, is developed and it is shown that these solutions may be used to construct more general solutions of KdV similarly to how the functions e^i(kx-ω(t)) are used to perform the same task in the theory of Fourier transform. A nonlinear superposition formula for general solutions of KdV similar to the Fourier expansion formula is conjectured.     

The class of solenoidal planar-helical vector fields

The class of solenoidal vector fields whose lines lie in planes parallel to R ² is constructed by the method of mappings. This class exhausts the set of all smooth planarhelical solutions of Gromeka’s problem in some domain D ? R ³. In the case of domains D with cylindrical boundaries whose generators are orthogonal to R ², it is shown that the choice of a specific solution from the constructed class is reduced to the Dirichlet problem with respect to two functions that are harmonic conjugates in D ² = D∩R ²; i.e., Gromeka’s nonlinear problem is reduced to linear boundary value problems. As an example, a specific solution of the problem for an axisymmetric layer is presented. The solution is based on solving Dirichlet problems in the form of series uniformly convergent in \(\bar D^2\) in terms of wavelet systems that form bases of various spaces of functions harmonic in D ².     

Generalized symmetric ADMM for separable convex optimization

The alternating direction method of multipliers (ADMM) has been proved to be effective for solving separable convex optimization subject to linear constraints. In this paper, we propose a generalized symmetric ADMM (GS-ADMM), which updates the Lagrange multiplier twice with suitable stepsizes, to solve the multi-block separable convex programming. This GS-ADMM partitions the data into two group variables so that one group consists of p block variables while the other has q block variables, where \(p \ge 1\) and \(q \ge 1\) are two integers. The two grouped variables are updated in a Gauss–Seidel scheme, while the variables within each group are updated in a Jacobi scheme, which would make it very attractive for a big data setting. By adding proper proximal terms to the subproblems, we specify the domain of the stepsizes to guarantee that GS-ADMM is globally convergent with a worst-case \({\mathcal {O}}(1/t)\) ergodic convergence rate. It turns out that our convergence domain of the stepsizes is significantly larger than other convergence domains in the literature. Hence, the GS-ADMM is more flexible and attractive on choosing and using larger stepsizes of the dual variable. Besides, two special cases of GS-ADMM, which allows using zero penalty terms, are also discussed and analyzed. Compared with several state-of-the-art methods, preliminary numerical experiments on solving a sparse matrix minimization problem in the statistical learning show that our proposed method is effective and promising.     

The FFTRR-based fast direct algorithms for complex inhomogeneous biharmonic problems with applications to incompressible flows

We develop analysis-based fast and accurate direct algorithms for several biharmonic problems in a unit disk derived directly from the Green’s functions of these problems and compare the numerical results with the “decomposition” algorithms (see Ghosh and Daripa, IMA J. Numer. Anal. 36(2), 824–850 [17]) in which the biharmonic problems are first decomposed into lower order problems, most often either into two Poisson problems or into two Poisson problems and a homogeneous biharmonic problem. One of the steps in the “decomposition algorithm” as discussed in Ghosh and Daripa (IMA J. Numer. Anal. 36(2), 824–850 [17]) for solving certain biharmonic problems uses the “direct algorithm” without which the problem can not be solved. Using classical Green’s function approach for these biharmonic problems, solutions of these problems are represented in terms of singular integrals in the complex z?plane (the physical plane) involving explicitly the boundary conditions. Analysis of these singular integrals using FFT and recursive relations (RR) in Fourier space leads to the development of these fast algorithms which are called FFTRR based algorithms. These algorithms do not need to do anything special to overcome coordinate singularity at the origin as often the case when solving these problems using finite difference methods in polar coordinates. These algorithms have some other desirable properties such as the ease of implementation and parallel in nature by construction. Moreover, these algorithms have O(logN) complexity per grid point where N ² is the total number of grid points and have very low constant behind this order estimate of the complexity. Performance of these algorithms is shown on several test problems. These algorithms are applied to solving viscous flow problems at low and moderate Reynolds numbers and numerical results are presented.     

On the convergence rate of grad-div stabilized Taylor-Hood to Scott-Vogelius solutions for incompressible flow problems

It was recently proven in Case et al. (2010) [2] that, under mild restrictions, grad-div stabilized Taylor-Hood solutions of Navier-Stokes problems converge to the Scott-Vogelius solution of that same problem. However, even though the analytical rate was only shown to be (where γ is the stabilization parameter), the computational results suggest the rate may be improvable to γ−1. We prove herein the analytical rate is indeed γ−1, and extend the result to other incompressible flow problems including Leray-α and MHD. Numerical results are given that verify the theory.     

Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

Quadratic Unconstrained Binary Optimization (QUBO) problems concern the minimization of quadratic polynomials in n{0,1}-valued variables. These problems are NP-complete, but prior work has identified a sequence of polynomial-time computable lower bounds on the minimum value, denoted by C₂,C₃,C₄,…. It is known that C₂ can be computed by solving a maximum flow problem, whereas the only previously known algorithms for computing require solving a linear program. In this paper we prove that C₃ can be computed by solving a maximum multicommodity flow problem in a graph constructed from the quadratic function. In addition to providing a lower bound on the minimum value of the quadratic function on {0,1}ⁿ, this multicommodity flow problem also provides some information about the coordinates of the point where this minimum is achieved. By looking at the edges that are never saturated in any maximum multicommodity flow, we can identify relational persistencies: pairs of variables that must have the same or different values in any minimizing assignment. We furthermore show that all of these persistencies can be detected by solving single-commodity flow problems in the same network.     

A spectral method for elliptic equations: the Dirichlet problem

Let Ω be an open, simply connected, and bounded region in ? ^d , d?≥?2, and assume its boundary \(\partial\Omega\) is smooth. Consider solving an elliptic partial differential equation Lu?=?f over Ω with zero Dirichlet boundary values. The problem is converted to an equivalent elliptic problem over the unit ball B; and then a spectral Galerkin method is used to create a convergent sequence of multivariate polynomials u _n of degree ≤?n that is convergent to u. The transformation from Ω to B requires a special analytical calculation for its implementation. With sufficiently smooth problem parameters, the method is shown to be rapidly convergent. For \(u\in C^{\infty}( \overline{\Omega})\) and assuming \(\partial\Omega\) is a C ^?∞? boundary, the convergence of \(\left\Vert u-u_{n}\right\Vert _{H^{1}}\) to zero is faster than any power of 1/n. Numerical examples in ?² and ?³ show experimentally an exponential rate of convergence.     

Fredholmness of Toeplitz operators and corona problems

A meromorphic analogue to the corona problem is formulated and studied and its solutions are characterized as being left-invertible in a space of meromorphic functions. The Fredholmness of Toeplitz operators with symbol G∈(L_∞(R))^2×2 is shown to be equivalent to that of a Toeplitz operator with scalar symbol , provided that the Riemann-Hilbert problem admits a solution such that the meromorphic corona problems with data are solvable. The Fredholm properties are characterized in terms of and the corresponding meromorphic left-inverses. Partial index estimates for the symbols and Fredholmness criteria are established for several classes of Toeplitz operators.     

On the comparison of initialisation strategies in differential evolution for large scale optimisation

Differential Evolution (de) has shown to be a promising global optimisation solver for continuous problems, even for those with a large dimensionality. Different previous works have studied the effects that a population initialisation strategy has on the performance of de when solving large scale continuous problems, and several contradictions have appeared with respect to the benefits that a particular initialisation scheme might provide. Some works have claimed that by applying a particular approach to a given problem, the performance of de is going to be better than using others. In other cases however, researchers have stated that the overall performance of de is not going to be affected by the use of a particular initialisation method. In this work, we study a wide range of well-known initialisation techniques for de. Taking into account the best and worst results, statistically significant differences among considered initialisation strategies appeared. Thus, with the aim of increasing the probability of appearance of high-quality results and/or reducing the probability of appearance of low-quality ones, a suitable initialisation strategy, which depends on the large scale problem being solved, should be selected.     

Blow-up of solutions to a degenerate parabolic equation not in divergence form

We study nonglobal positive solutions to the Dirichlet problem for u_t=u^p(Δu+u) in bounded domains, where 0<p<2. It is proved that the set of points at which u blows up has positive measure and the blow-up rate is exactly . If either the space dimension is one or p<1, the ω-limit set of consists of continuous functions solving . In one space dimension it is shown that actually as t→T, where w coincides with an element of a one-parameter family of functions inside each component of its positivity set; furthermore, we study the size of the components of {w>0} with the result that this size is uniquely determined by Ω in the case p<1, while for p>1, the positivity set can have the maximum possible size for certain initial data, but it may also be arbitrarily close to the minimal length π.     

On the Maximum Weight of a Sparse Connected Graph of Given Order and Size

The weight of an edge of a graph is defined to be the sum of degrees of vertices incident to the edge. The weight of a graph G is the minimum of weights of edges of G. Jendrol’ and Schiermeyer (Combinatorica 21:351–359, 2001) determined the maximum weight of a graph having n vertices and m edges, thus solving a problem posed in 1990 by Erd?s. The present paper is concerned with a modification of the mentioned problem, in which involved graphs are connected and of size \(m\le \left( {\begin{array}{c}n\\ 2\end{array}}\right) -\left( {\begin{array}{c}\lceil n/2\rceil \\ 2\end{array}}\right) \).     

On merit functions for <Emphasis Type="Italic">p</Emphasis>-order cone complementarity problem

Merit function approach is a popular method to deal with complementarity problems, in which the complementarity problem is recast as an unconstrained minimization via merit function or complementarity function. In this paper, for the complementarity problem associated with p-order cone, which is a type of nonsymmetric cone complementarity problem, we show the readers how to construct merit functions for solving p-order cone complementarity problem. In addition, we study the conditions under which the level sets of the corresponding merit functions are bounded, and we also assert that these merit functions provide an error bound for the p-order cone complementarity problem. These results build up a theoretical basis for the merit method for solving p-order cone complementarity problem.