Sigma-subdifferential and its application to minimization problem

Positivity - In this paper, we study $$\sigma $$ -subdifferentials of $$\sigma $$ -convex functions. Two equivalent conditions for $$\sigma $$ -convexity are given. The formula for the $$\sigma $$...     

An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers

This article presents an exact algorithm for the precedence-constrained traveling salesman problem, which is also known as the sequential ordering problem. This NP-hard problem has applications in various domains, including operational research and compilers. In this article, the problem is presented and solved in the context of minimizing switching energy in compilers. Most previous work on minimizing switching energy in the compiler domain has been limited to simple heuristics that are not guaranteed to give an optimal solution. In this work, we present an exact algorithm for solving the switching energy minimization problem using a branch-and-bound approach. The proposed algorithm is simple and intuitive, yet powerful. It is the first exact algorithm for the switching energy problem that is shown to solve real instances of the problem within a few seconds per instance. Compared to previous work in the operational research domain, the proposed algorithm is believed to be the most powerful exact algorithm that does not require a linear programming formulation. The proposed algorithm is experimentally evaluated using instances taken from a production compiler. The results show that with a time limit of 10 ms per node, the proposed algorithm optimally solves 99.8 % of the instances. It optimally solves instances with up to 598 nodes within a few seconds. The resulting switching cost is 16 % less than that produced without energy awareness and 5 % less than that produced by a commonly used heuristic.     

A decomposition method for convex minimization problems and its application

1. IntroductionConsider the following special convex programming problem(P) adn{f(~) g(z); Ax = z},where f: Re - (--co, co] and g: Re - (--co, co] are closed proper convex functions andA is an m x n matrix. The Lagrangian for problem (P) is defined by L: Rad x Re x Re -- (~co, co] as follows:L(x, z, y) = f(x) g(z) (y, Ax ~ z), (1.1)where (., .) denotes the inner product in the general sense and 'y is the Lagrangian multiplierassociated with the constraint Ax = z. The augmented L…     

On a semi-smooth Newton method and its globalization

This paper addresses the globalization of the semi-smooth Newton method for non-smooth equations F(x)  =  0 in with applications to complementarity and discretized ℓ¹-regularization problems. Assuming semi-smoothness it is shown that super-linearly convergent Newton methods can be globalized, if appropriate descent directions are used for the merit function |F(x)|². Special attention is paid to directions obtained from the primal-dual active set strategy. K. Ito’s research was partially supported by the Army Research Office under DAAD19-02-1-039.     

Application of Newton’s method to a homogenization problem

The homogenization of a family (P _ε) of uniformly elliptic semilinear partial differential equations of second order is studied. The main result is that any non-singular solutionu of the homogenized problem (P) is the limit of non-singular solutions of (P _ε). The method consists of specifying a functionw _ε starting from which the Newton iterates converge to a solutionu _ε ofP _ε. These solutionsu _ε converge to the given solutionu of (P).     

Split Newton iterative algorithm and its application

Inspired by some implicit-explicit linear multistep schemes and additive Runge-Kutta methods, we develop a novel split Newton iterative algorithm for the numerical solution of nonlinear equations. The proposed method improves computational efficiency by reducing the computational cost of the Jacobian matrix. Consistency and global convergence of the new method are also maintained. To test its effectiveness, we apply the method to nonlinear reaction-diffusion equations, such as Burger’s-Huxley equation and fisher’s equation. Numerical examples suggest that the involved iterative method is much faster than the classical Newton’s method on a given time interval.     

The convergence of the perturbed Newton method and its application for ill-conditioned problems

Iterative methods, such as Newton’s, behave poorly when solving ill-conditioned problems: they become slow (first order), and decrease their accuracy. In this paper we analyze deeply and widely the convergence of a modified Newton method, which we call perturbed Newton, in order to overcome the usual disadvantages Newton’s one presents. The basic point of this method is the dependence of a parameter affording a degree of freedom that introduces regularization. Choices for that parameter are proposed. The theoretical analysis will be illustrated through examples.     

A constrained minimization problem and its application to guided cylindrical TM-modes in an anisotropic self-focusing dielectric

The first part of this paper establishes the existence of a minimizer of problem: where The essential features of the integrand are that where We show that the minimizer satisfies an Euler- Lagrange equation and estimates are given for the Lagrange multiplier as a function of d. In the second part of the paper, we use this result to establish the existence of guided TM-modes propagating through a self-focusing anisotropic dielectric. These are special solutions of Maxwell's equations with a nonlinear constitutive relation of a type commonly used in nonlinear optics when treating the propagation of waves in a cylindrical wave-guide. In TM-modes, the magnetic field has the form \[ {\bf B}=w(r)\cos (kz-\omega t)i_{\theta } \] when expressed in cylindrical polar co-ordinates The amplitude w is given by where is a minimizer of the problem (0.1) for a function which is determined by the constitutive relation through a Legendre transformation. Received: 4 April 2001 / Accepted: 29 November 2001 / Published online: 28 February 2002     

An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem

In this paper we consider low-rank semidefinite programming (LRSDP) relaxations of combinatorial quadratic problems that are equivalent to the maxcut problem. Using the Gramian representation of a positive semidefinite matrix, the LRSDP problem can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function with quadratic equality constraints. For the solution of this problem we propose a continuously differentiable exact merit function that exploits the special structure of the constraints and we use this function to define an efficient and globally convergent algorithm. Finally, we test our code on an extended set of instances of the maxcut problem and we report comparisons with other existing codes.     

An approximation theory of matrix rank minimization and its application to quadratic equations

Matrix rank minimization problems are gaining plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization problem can be approximated to any level of accuracy via continuous optimization (especially, linear and nonlinear semidefinite programming) problems. One of the main results in this paper shows that if the feasible set of the problem has a minimum rank element with the least Frobenius norm, then any accumulation point of solutions to the approximation problem, as the approximation parameter tends to zero, is a minimum rank solution of the original problem. The tractability under certain conditions and convex relaxation of the approximation problem are also discussed. An immediate application of this theory to the system of quadratic equations is presented in this paper. It turns out that the condition for such a system without a nonzero solution can be characterized by a rank minimization problem, and thus the proposed approximation theory can be used to establish some sufficient conditions for the system to possess only zero solution.     

K-page crossing number minimization problem: An evaluation of heuristics and its solution using GESAKP

The $K$ -page crossing number minimization problem (KPMP) is to determine the minimum number of edge crossings over all $K$ -page book drawings of a graph $G$ with the vertices placed in a sequence along the spine and the edges on the $K$ -pages of the book. In this paper we have (a) statistically evaluated five heuristics for ordering vertices on the spine for minimum number of edge crossings with all the edges placed on a single page, (b) statistically evaluated five heuristics for distributing edges on $K$ -pages with minimum number of crossings for a fixed ordering of vertices on the spine and (c) implemented and experimentally evaluated an instance of guided evolutionary simulated annealing (GESA) called GESAKP here for solving the KPMP. In accordance with the results of (a) and (b) above, in GESAKP, placement of vertices on the spine is decided using a random depth first search of the graph and an edge embedding heuristic is used to distribute the edges on $K$ -pages of a book. Extensive experiments have been carried out on a suite of benchmark, standard and random graphs to compare the performance of GESAKP with variants of the simple genetic algorithm and other existing approaches. In order to improve the results for some graphs, simple extensions to GESAKP were made. Experiments show that in almost all cases, zero or low cost could be achieved for $K\le 5$ . Also, for $K \le $ ‘known upper bound’ i.e. upper bound for minimum number of pages necessary to draw or embed the edges of a graph without crossings, zero crossings were obtained. In general, GESAKP outperformed the other techniques. From our experimental results we also present the conjectures for the $K$ -page crossing number of some complete tripartite graphs and pagenumber of toroidal meshes and a class of complete bipartite and tripartite graphs.     

Nonlinear support functionals and a minimization problem

Translated from Issledovaniya po Prikladnoi Matematike, No. 3, pp. 60–67, 1975.     

Spectral Galerkin method and its application to a Cauchy problem of Helmholtz equation

Based on a mathematical model of laser beams, we present a spectral Galerkin method for solving a Cauchy problem of the Helmholtz equation in a rectangle, where the Cauchy data pairs are given at y?=?0 and boundary data are for x?=?0 and x?=?π. The solution is sought in the interval 0?<?y?<?1. The spectral Galerkin method is considered as a regularization method. We then perform an analysis on the error bound for this method. For illustration, several numerical experiments are constructed to demonstrate the feasibility and efficiency of the proposed method.     

An operator Newton method for the Stefan problem based on smoothing: A local perspective

The initial/Neumann boundary-value enthalpy formulation for the two-phase Stefan problem is regularized by smoothing. Known estimates predict a convergence rate of ^1/2, and this result is extended in this paper to include the case of a (nonzero) residual in the regularized problem. A modified Newton Kantorovich framework is established, whereby the exact solution of the regularized problem is replaced by one Newton iteration. It is shown that a consistent theory requires measure-theoretic hypotheses on the starting guess and the Newton iterate, otherwise residual decrease is not expected. The circle closes in one spatial dimension, where it is shown that the residual decrease of Newton's method correlates precisely with the ^1/2 convergence theory.     

A semi-smooth Newton method for an inverse problem in option pricing

We present an optimal control approach using a Lagrangian framework to identify local volatility functions from given option prices. We employ a globalized sequential quadratic programming (SQP) algorithm and implement a line search strategy. The linear-quadratic optimal control problems in each iteration are solved by a primal-dual active set strategy which leads to a semi-smooth Newton method. We present first- and second-order analysis as well as numerical results. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

One-step smoothing Newton method for solving the mixed complementarity problem with a function

The mixed complementarity problem (denote by MCP(F)) can be reformulated as the solution of a smooth system of equations. In the paper, based on a perturbed mid function, we propose a new smoothing function, which has an important property, not satisfied by many other smoothing function. The existence and continuity of a smooth path for solving the mixed complementarity problem with a P₀ function are discussed. Then we presented a one-step smoothing Newton algorithm to solve the MCP with a P₀ function. The global convergence of the proposed algorithm is verified under mild conditions. And by using the smooth and semismooth technique, the rate of convergence of the method is proved under some suitable assumptions.