On solving the second four-element Riemann-type boundary-value problem on a disk

The paper is devoted to solving one of the main four-element Riemann-type boundary-value problems in classes of piecewise-bianalytic functions with unit circumference as jump line. We prove a theorem on reduction of solving the stated problem to solving two vector-matrix Riemann problems with respect to piecewise-analytic vector-functions. Using it, we obtain an algorithm for solving the problem and conditions under which one can get a constructive and explicit solution in terms of Cauchy-type integrals. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 46, No. 3, pp. 377–385, July–September, 2006.     

A comparison of two methods for solving 0–1 integer programs using a general purpose simulated annealing algorithm

0–1 problems are often difficult to solve. Although special purpose algorithms (exact as well as heuristic) exist for solving particular problem classes or problem instances, there are few general purpose algorithms for solving practical-sized instances of 0–1 problems. This paper deals with a general purpose heuristic algorithm for 0–1 problems. In this paper, we compare two methods based on simulated annealing for solving general 0–1 integer programming problems. The two methods differe in the scheme used for neighbourhood transitions in the simulated annealing framework. We compare the performance of the two methods on the set partitioning problem.     

The Cauchy Problem for Second-Order Elliptic Systems on the Plane

Regular solutions to second-order elliptic systems on the plane are representable in terms of A-analytic functions satisfying an operator equation of the Beltrami type. We prove Carleman-type formulas for reconstruction of solutions from data on a part of the boundary of the domain. We use these formulas for solving the Cauchy problems for the system of Lame equations, the Navier–Stokes system, and the system of equations of elasticity with resilience.     

The Gibbs Cloner for Combinatorial Optimization, Counting and Sampling

We present a randomized algorithm, called the cloning algorithm, for approximating the solutions of quite general NP-hard combinatorial optimization problems, counting, rare-event estimation and uniform sampling on complex regions. Similar to the algorithms of Diaconis–Holmes–Ross and Botev–Kroese the cloning algorithm is based on the MCMC (Gibbs) sampler equipped with an importance sampling pdf and, as usual for randomized algorithms, it uses a sequential sampling plan to decompose a “difficult” problem into a sequence of “easy” ones. The cloning algorithm combines the best features of the Diaconis–Holmes–Ross and the Botev–Kroese. In addition to some other enhancements, it has a special mechanism, called the “cloning” device, which makes the cloning algorithm, also called the Gibbs cloner fast and accurate. We believe that it is the fastest and the most accurate randomized algorithm for counting known so far. In addition it is well suited for solving problems associated with the Boltzmann distribution, like estimating the partition functions in an Ising model. We also present a combined version of the cloning and cross-entropy (CE) algorithms. We prove the polynomial complexity of a particular version of the Gibbs cloner for counting. We finally present efficient numerical results with the Gibbs cloner and the combined version, while solving quite general integer and combinatorial optimization problems as well as counting ones, like SAT.     

A new class of complementarity functions for symmetric cone complementarity problems

A popular approach to solving the complementarity problem is to reformulate it as an equivalent equation system via a complementarity function. In this paper, we propose a new class of functions, which contains the penalized natural residual function and the penalized Fischer–Burmeister function for symmetric cone complementarity problems. We show that this class of functions is indeed a class of complementarity functions. We finally prove that the merit function of this new class of complementarity functions is coercive.     

Continuous Reformulations for Zero–One Programming Problems

In this work, we study continuous reformulations of zero–one programming problems. We prove that, under suitable conditions, the optimal solutions of a zero–one programming problem can be obtained by solving a specific continuous problem.     

Non-Interior continuation methods for solving semidefinite complementarity problems

 There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported. Received: October 1999 / Accepted: April 2002 Published online: December 19, 2002 RID="⋆" ID="⋆" This research is supported by National Science Foundation Grant CCR-9731273. Key words. semidefinite complementarity problem – smoothing function – non-interior continuation – global convergence – local superlinear convergence     

A new complexity result on multiobjective linear integer programming using short rational generating functions

This paper presents a new complexity result for solving multiobjective integer programming problems. We prove that encoding the entire set of nondominated solutions of the problem in a short sum of rational functions is polynomially doable, when the dimension of the decision space is fixed. This result extends a previous result presented in De Loera et al. (INFORMS J. Comput. 21(1):39–48, 2009) in that there the number of the objective functions is assumed to be fixed whereas ours allows this number to vary.     

Carleman estimates for second-order hyperbolic systems in anisotropic cases and applications. Part II: an inverse source problem

In this paper, we consider Carleman-type estimate and consider an inverse problem for second order hyperbolic systems in an anisotropic case. In the previous Part I paper, we established a Carleman-type estimate for hyperbolic systems in which the coefficient matrices satisfy suitable conditions. We apply a Carleman estimate in the previous Part I paper to an inverse source problem for second-order hyperbolic systems in an anisotropic case and prove an estimate of the Hölder type.     

Duality and optimality conditions for generalized equilibrium problems involving DC functions

We consider a generalized equilibrium problem involving DC functions which is called (GEP). For this problem we establish two new dual formulations based on Toland-Fenchel-Lagrange duality for DC programming problems. The first one allows us to obtain a unified dual analysis for many interesting problems. So, this dual coincides with the dual problem proposed by Martinez-Legaz and Sosa (J Glob Optim 25:311–319, 2006) for equilibrium problems in the sense of Blum and Oettli. Furthermore it is equivalent to Mosco’s dual problem (Mosco in J Math Anal Appl 40:202–206, 1972) when applied to a variational inequality problem. The second dual problem generalizes to our problem another dual scheme that has been recently introduced by Jacinto and Scheimberg (Optimization 57:795–805, 2008) for convex equilibrium problems. Through these schemes, as by products, we obtain new optimality conditions for (GEP) and also, gap functions for (GEP), which cover the ones in Antangerel et al. (J Oper Res 24:353–371, 2007, Pac J Optim 2:667–678, 2006) for variational inequalities and standard convex equilibrium problems. These results, in turn, when applied to DC and convex optimization problems with convex constraints (considered as special cases of (GEP)) lead to Toland-Fenchel-Lagrange duality for DC problems in Dinh et al. (Optimization 1–20, 2008, J Convex Anal 15:235–262, 2008), Fenchel-Lagrange and Lagrange dualities for convex problems as in Antangerel et al. (Pac J Optim 2:667–678, 2006), Bot and Wanka (Nonlinear Anal to appear), Jeyakumar et al. (Applied Mathematics research report AMR04/8, 2004). Besides, as consequences of the main results, we obtain some new optimality conditions for DC and convex problems.     

Two-time temperature Green's functions in kinetic theory and molecular hydrodynamics: I. The chain of equations for the irreducible functions

We develop a scheme for constructing chains of equations for the irreducible Green's functions. The structure of the equations allows going beyond the usual perturbation theory in solving specific problems. We obtain general relations that allow any correlation function to be expressed through solutions of an infinite chain of equations for the irreducible functions. Translated from Teoreticheskaya i Matematischeskaya Fizika, Vol. 118, No. 1, pp. 105–125, January, 1999.     

Globally Convergent Cutting Plane Method for Nonconvex Nonsmooth Minimization

Nowadays, solving nonsmooth (not necessarily differentiable) optimization problems plays a very important role in many areas of industrial applications. Most of the algorithms developed so far deal only with nonsmooth convex functions. In this paper, we propose a new algorithm for solving nonsmooth optimization problems that are not assumed to be convex. The algorithm combines the traditional cutting plane method with some features of bundle methods, and the search direction calculation of feasible direction interior point algorithm (Herskovits, J. Optim. Theory Appl. 99(1):121–146, 1998). The algorithm to be presented generates a sequence of interior points to the epigraph of the objective function. The accumulation points of this sequence are solutions to the original problem. We prove the global convergence of the method for locally Lipschitz continuous functions and give some preliminary results from numerical experiments.     

Solution of systems of nonlinear equations using a Chebyshev series

In this paper we study problems involving the application of the Chebyshev series [1]–[4] to solve certain computational problems. The experimental part of the work was carried out using MAPLE. Various functions of the MAPLE program for carrying out analytic transformations, symbolic differentiation, and graphical service make it possible to give a new estimate of the possibilities of the Chebyshev series in solving particular problems. The Chebyshev series gives an exact representation of a zero of an analytic function. Segments of a Chebyshev series generate higher-order recursive processes. In the present paper we discuss the theoretical foundations of this classical approach in the one-dimensional case. We give computational formulas for the coefficients of the Chebyshev series in the multidimensional case. We consider illustrative examples. We present experimental results of solving several optimization problems. Thirteen tables, 8 figures. Bibliography: 14 titles. Translated fromProblemy Matematicheskoi Fiziki, 1998, pp. 5–27.     

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

On the convergence of the Weiszfeld algorithm for continuous single facility location–allocation problems

A general family of single facility continuous location–allocation problems is introduced, which includes the decreasingly weighted ordered median problem, the single facility Weber problem with supply surplus, and Weber problems with alternative fast transportation network. We show in this paper that the extension of the well known Weiszfeld iterative decrease method for solving the corresponding location problems with fixed allocation yields an always convergent scheme for the location allocation problems. In a generic way, from each starting point, the limit point will be a locally minimal solution, whereas for each possible exceptional situation, a possible solution is indicated. Some computational results are presented, comparing this method with an alternating location–allocation approach. The research of the second author was partially supported by the grant of the Algerian Ministry of High Education 001BIS/PNE/ENSEIGNANTS/BELGIQUE.     

Solution of two-dimensional quasistatic problems of thermoelasticity for multilayered bodies

We propose a new method of solving two-dimensional quasistatic problems of thermoelasticity for isotropic multilayered bodies. The method is based on the applicaiton of generalized functions. Translated fromMatematichni Metodi i Fiziko-mekhanichni Polya, Vol. 40, No. 1, 1997, pp. 49–52.     

Multilevel methods for mixed finite elements in three dimensions

In this paper we consider second order scalar elliptic boundary value problems posed over three–dimensional domains and their discretization by means of mixed Raviart–Thomas finite elements [18]. This leads to saddle point problems featuring a discrete flux vector field as additional unknown. Following Ewing and Wang [26], the proposed solution procedure is based on splitting the flux into divergence free components and a remainder. It leads to a variational problem involving solenoidal Raviart–Thomas vector fields. A fast iterative solution method for this problem is presented. It exploits the representation of divergence free vector fields as s of the –conforming finite element functions introduced by Nédélec [43]. We show that a nodal multilevel splitting of these finite element spaces gives rise to an optimal preconditioner for the solenoidal variational problem: Duality techniques in quotient spaces and modern algebraic multigrid theory [50, 10, 31] are the main tools for the proof. Received November 4, 1996 / Revised version received February 2, 1998     

A projected–gradient interior–point algorithm for complementarity problems

Interior–point algorithms are among the most efficient techniques for solving complementarity problems. In this paper, a procedure for globalizing interior–point algorithms by using the maximum stepsize is introduced. The algorithm combines exact or inexact interior–point and projected–gradient search techniques and employs a line–search procedure for the natural merit function associated with the complementarity problem. For linear problems, the maximum stepsize is shown to be acceptable if the Newton interior–point search direction is employed. Complementarity and optimization problems are discussed, for which the algorithm is able to process by either finding a solution or showing that no solution exists. A modification of the algorithm for dealing with infeasible linear complementarity problems is introduced which, in practice, employs only interior–point search directions. Computational experiments on the solution of complementarity problems and convex programming problems by the new algorithm are included.     

A variant of the coboundary element method for studying heat-conduction problems in bodies of complicated shape

We propose a scheme for constructing the solution of boundary-value problems for bodies of complicated shape by applying coboundary or boundary elements and integral transforms. We illustrate the method of applying the finite Fourier cosine transform in solving a mixed boundary-value problem for a body having the shape of a trapezoid. Translated fromMatematichni Metodi i Fiziko-mekhanichni Polya, Vol. 40, No. 1, 1997, pp. 97–103.     

Decomposition-based Method for Sparse Semidefinite Relaxations of Polynomial Optimization Problems

We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim. 17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose is an extension to semidefinite programming of the Benders decomposition for linear programs (Benders, Comput. Manag. Sci. 2(1):3–19, 2005).