Meta-control of an interacting-particle algorithm for global optimization

A common issue for stochastic global optimization algorithms is how to set the parameters of the sampling distribution (e.g. temperature, mutation/cross-over rates, selection rate, etc.) so that the samplings converge to the optimum effectively and efficiently. We consider an interacting-particle algorithm and develop a meta-control methodology which analytically guides the inverse temperature parameter of the algorithm to achieve desired performance characteristics (e.g. quality of the final outcome, algorithm running time, etc.). The main aspect of our meta-control methodology is to formulate an optimal control problem where the fractional change in the inverse temperature parameter is the control variable. The objectives of the optimal control problem are set according to the desired behavior of the interacting-particle algorithm. The control problem considers particles’ average behavior, rather than treating the behavior of individual particles. The solution to the control problem provides feedback on the inverse temperature parameter of the algorithm.     

Solving the Inverse Generalized Problem of Vertical Seismic Profiling

The dynamic inverse seismics problem is considered in a generalized setting. We investigate whether the wave propagation problem in a vertically nonhomogeneous medium is well-posed. We show that the regular part of the solution is an L ₂ function and the inverse problem, i.e., the determination of the reflection coefficient, is thus reducible to minimizing the error functional. The gradient of the functional is obtained in explicit form from the conjugate problem, and approximate formulas for its evaluation are derived. A regularization algorithm for the solution of the inverse problem is considered; simulation results using various excitation sources are reported.     

Numerical solution of the inverse electrocardiography problem with the use of the Tikhonov regularization method

The inverse electrocardiography problem related to medical diagnostics is considered in terms of potentials. Within the framework of the quasi-stationary model of the electric field of the heart, the solution of the problem is reduced to the solution of the Cauchy problem for the Laplace equation in R ³. A numerical algorithm based on the Tikhonov regularization method is proposed for the solution of this problem. The Cauchy problem for the Laplace equation is reduced to an operator equation of the first kind, which is solved via minimization of the Tikhonov functional with the regularization parameter chosen according to the discrepancy principle. In addition, an algorithm based on numerical solution of the corresponding Euler equation is proposed for minimization of the Tikhonov functional. The Euler equation is solved using an iteration method that involves solution of mixed boundary value problems for the Laplace equation. An individual mixed problem is solved by means of the method of boundary integral equations of the potential theory. In the study, the inverse electrocardiography problem is solved in region Ω close to the real geometry of the torso and heart.     

Inverse Problem for Quasi-Periodic Differential Pencils with Jump Conditions Inside the Interval

Non-self-adjoint second-order differential pencils on a finite interval with non-separated quasi-periodic boundary conditions and jump conditions are studied. We establish properties of spectral characteristics and investigate the inverse spectral problem of recovering the operator from its spectral data. For this inverse problem we prove the corresponding uniqueness theorem and provide an algorithm for constructing its solution.     

Heuristic algorithms for the inverse mixed integer linear programming problem

The recent development in inverse optimization, in particular the extension from the inverse linear programming problem to the inverse mixed integer linear programming problem (InvMILP), provides more powerful modeling tools but also presents more challenges to the design of efficient solution techniques. The only reported InvMILP algorithm, referred to as Alg^InvMILP, although finitely converging to global optimality, suffers two limitations that greatly restrict its applicability: it is time consuming and does not generate a feasible solution except for the optimal one. This paper presents heuristic algorithms that are designed to be implemented and executed in parallel with Alg^InvMILP in order to alleviate and overcome its two limitations. Computational experiments show that implementing the heuristic algorithm on one auxiliary processor in parallel with Alg^InvMILP on the main processor significantly improves its computational efficiency, in addition to providing a series of improving feasible upper bound solutions. The additional speedup of parallel implementation on two or more auxiliary processors appears to be incremental, but the upper bound can be improved much faster.     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

Solution method for the inverse boundary-value problem for the wave equation

Existence and uniqueness issues are considered for the inverse boundary-value problem of determining the variable coefficient of the one-dimensional wave equation on a half-line. A Tikhonov-regularizing algorithm is constructed to find an approximate solution using input data that are specified with an error.Translated from Metody Matematicheskogo Modelirovaniya, Avtomatizatsiya Obrabotki Nablyudenii i Ikh Primeneniya, pp. 80–88, 1986.     

An inverse problem for the acoustics equations: A multilevel adaptive algorithm

A numerical solution to an inverse problem for the acoustic equations using an optimization method for a stratified medium is presented. With the distribution of an acoustic wave field on the medium’s surface, the 1D distributions of medium’s density, as well as the velocity and absorption coefficient of the acoustic wave, are determined. Absorption in a Voigt body model is considered. The conjugate gradients and the Newton method are used for minimization. To increase the efficiency of the numerical method, a multilevel adaptive algorithm is proposed. The algorithm is based on a division of the whole procedure of solving the inverse problem into a series of consecutive levels. Each level is characterized by the number of parameters to be determined at the level. In moving from one level to another, the number of parameters changes adaptively according to the functional minimized and the convergence rate. The minimization parameters are chosen as illustrated by results of solving the inverse problem in a spectral domain, where the desired quantities are presented as Chebyshev polynomial series and minimization is carried out with respect to the coefficients of these series. The method is compared in efficiency with a nonadaptive method. The optimal parameters of the multilevel method are chosen. It is shown that the multilevel algorithm offers several advantages over the one without partitioning into levels. The algorithm produces primarily a more accurate solution to the inverse problem.     

Numerical methods for some inverse problems of heart electrophysiology

We consider numerical methods for solving inverse problems that arise in heart electrophysiology. The first inverse problem is the Cauchy problem for the Laplace equation. Its solution algorithm is based on the Tikhonov regularization method and the method of boundary integral equations. The second inverse problem is the problem of finding the discontinuity surface of the coefficient of conductivity of a medium on the basis of the potential and its normal derivative given on the exterior surface. For its numerical solution, we suggest a method based on the method of boundary integral equations and the assumption on a special representation of the unknown surface.     

Numerical solution of the inverse problem for the polarized-radiation transfer equation

An inverse problem for the steady vector transfer equation for polarized radiation in an isotropic medium is studied. For this problem, an attenuation factor is found from a given solution of the equation at a medium boundary. An approach is propounded to solve the inverse problem by using special external radiative sources. A formula is derived which relates the Radon transform of an attenuation factor to a radiation-flux density at the boundary. Numerical experiments show that the algorithm for the polarized-radiation transfer equation has an advantage over the method used in the scalar case.     

Inversion of electroencephalography data for a 2‐D current distribution

It is known from the fundamental work of Albanese and Monk that, the recovery of the support of a three dimensional current, within a conducting medium, from measurements of the generated exterior electric potential, is not possible. However, it is possible to recover the support of any other current, which is supported on a set of dimension lower than three. Nevertheless, no algorithm for such an inversion is known. Here, we propose such an algorithm for a two dimensional current distribution, and in particular, we apply this algorithm to the inverse problem of electroencephalography in the case where the neuronal current is restricted to a small disk of arbitrary location and orientation within the brain. The solution of this inverse problem is reduced to the solution of a nonlinear algebraic system, and numerical tests show that the there exists a unique real solution to this system.Copyright © 2014 John Wiley & Sons, Ltd.     

逆热传导方程的一个正则化方法

考虑了标准的一维逆热传导方程.问题是不适定的,即解不连续地依赖于数据.通过Fourier逼近的方法进行正则化处理,提出了一个新的算法,理论分析和数值实验均表明该算法是稳定的;该算法不仅保留了测量数据的部分高频成份,同时还具有相同的精度和计算复杂性.     

A unified framework for constructing globally convergent algorithms for multidimensional coefficient inverse problems

We present a unified framework for constructing the globally convergent algorithms for a broad class of multidimensional coefficient inverse problems arising in natural science and industry. Based on the convexification approach, the unified framework substantiates the numerical solution of the corresponding problem of nonconvex optimization. A globally convergent iterative algorithm for an inverse problem of diffuse optical mammography is constructed. It utilizes the contraction property of a nonlinear operator resulting from applying the convexification approach. The effectiveness of this algorithm is demonstrated in computational experiments.     

Numerical identification of the leading coefficient of a parabolic equation

For a multidimensional parabolic equation, we study the problem of finding the leading coefficient, which is assumed to depend only on time, on the basis of additional information about the solution at an interior point of the computational domain. For the approximate solution of the nonlinear inverse problem, we construct linearized approximations in time with the use of ordinary finite-element approximations with respect to space. The numerical algorithm is based on a special decomposition of the approximate solution for which the transition to the next time level is carried out by solving two standard elliptic problems. The capabilities of the suggested numerical algorithm are illustrated by the results of numerical solution of a model inverse two-dimensional problem.     

The Sinc‐Galerkin method for solving an inverse parabolic problem with unknown source term

The inverse problem of determining an unknown source term depending on space variable in a parabolic equation is considered. A numerical algorithm is presented for recovering the unknown function and obtaining a solution of the problem. As this inverse problem is ill‐posed, Tikhonov regularization is used for finding a stable solution. For solving the direct problem, a Galerkin method with the Sinc basis functions in both the space and time domains is presented. This approximate solution displays an exponential convergence rate and is valid on the infinite time interval. Finally, some examples are presented to illustrate the ability and efficiency of this numerical method. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013     

Reconstruction for a class of the inverse transmission eigenvalue problem

The authors present a constructive algorithm for the numerical solution to a class of the inverse transmission eigenvalue problem. The numerical experiments are provided to demonstrate the efficiency of our algorithms by a numerical example.     

Identification of a dissipation coefficient by a variational method

A generalized inverse problem for the identification of the absorption coefficient for a hyperbolic system is considered. The well-posedness of the problem is examined. It is proved that the regular part of the solution is an L ₂ function, which reduces the inverse problem to minimizing the error functional. The gradient of the functional is determined in explicit form from the adjoint problem, and approximate formulas for its calculation are derived. A regularization algorithm for the solution of the inverse problem is considered. Numerical results obtained for various excitation sources are displayed.     

Shape inverse problem for the two‐dimensional unsteady Stokes flow

In this article, the shape inverse problem for the two‐dimensional unsteady Stokes flow has been presented. We employ Piola transformation to bypass the divergence free condition for the flow and prove the differentiability of the solution to the initial boundary value problem. For the approximate solution of the ill‐posed and nonlinear problem, we propose a regularized Gauss‐Newton method. The numerical examples show that our theory is useful for practical purpose and the proposed algorithm is feasible. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

Note on an improved branch-and-bound algorithm to solve n/m/P/Fmax problems

The LOMNICKI algorithm for n/m/P/F_max flow-shop problems is unsuitable for large values ofn andm because of the time and size of storage required to attain an optimal solution. The form of presentation of the problem to the algorithm can influence its performance. The algorithm performance can be improved applying the algorithm to the problem and to its inverse at the same time, sharing both applications the best value and the best bound found. Further exploitation of proprieties of the inverse problem are useful also for solve hard instances of the problem.     

A numerical method for solving an inverse thermoacoustic problem

In this paper, we consider an inverse problem of determining the initial condition of an initial boundary value problem for the wave equation with some additional information about solving a direct initial boundary value problem. The information is obtained from measurements at the boundary of the solution domain. The purpose of our paper is to construct a numerical algorithm for solving the inverse problem by an iterative method called a method of simple iteration (MSI) and to study the resolution quality of the inverse problem as a function of the number and location of measurement points. Three two-dimensional inverse problem formulations are considered. The results of our numerical calculations are presented. It is shown that the MSI decreases the objective functional at each iteration step. However, due to the ill-posedness of the inverse problem the difference between the exact and approximate solutions decreases up to some fixed number k _min, and then monotonically increases. This shows the regularizing properties of the MSI, and the iteration number can be considered a regularization parameter.