Using the Dinkelbach-type algorithm to solve the continuous-time linear fractional programming problems

A Dinkelbach-type algorithm is proposed in this paper to solve a class of continuous-time linear fractional programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.     

On the treatment of free boundary problems with the heat equation via optimal control

In this paper we consider a free boundary problem of general type for the heat equation in one space dimension. We formulate this problem as an optimal control problem and derive necessary conditions for a solution of it. In order to compute a solution of the control problem, we apply the projection-gradient-method. Simple numerical examples illustrate the results.     

Some remarks on the dynamics of cell membranes

Motivated by the desire to model the entry of 1,25D into a cell by receptor mediated endocytosis, we have formulated the problem as the dynamics of a bilayer membrane. We have discussed setting the problem as a variational problem using the Helfrich modeling of the bilayer in terms of the free energy. Using a Lagrangian formulation we arrive at the Euler–Lagrange equations for the system. The model we have used depends on the amount of reagent in the neighborhood of the upper membrane. The problem thereby reduces to a moving boundary problem, which is dependent on a diffusion equation for a region changing with time. In order to solve this problem we seek the correct Neumann function for this altered. This is accomplished by deriving a Hadamard variational formula for the diffusion equation. We also offer an iterative procedure for solving this non-linear problem.     

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.     

Inverse problems for the Sturm-Liouville equation with the discontinuous coefficient

In this study we derive the Gelfand-Levitan-Marchenko type main integral equation of the inverse problem for the boundary value problem $L$ and prove the uniquely solvability of the main integral equation. Further, we give the solution of the inverse problem by the spectral data and by two spectrum.     

Simultaneous Subgradient Algorithms for the Generalized Split Variational Inclusion Problem in Hilbert Spaces

In this article, we study the generalized split variational inclusion problem. For this purpose, motivated by the projected Landweber algorithm for the split equality problem, we first present a simultaneous subgradient extragradient algorithm and give related convergence theorems for the proposed algorithm. Next, motivated by the alternating CQ-algorithm for the split equality problem, we propose another simultaneous subgradient extragradient algorithm to study the general split variational inclusion problem. As applications, we consider the split equality problem, split feasibility problem, split variational inclusion problem, and variational inclusion problem in Hilbert spaces.     

Multiple Order Pick Sequencing in a Carousel System: A Solvable Case of the Rural Postman Problem

We consider the problem of sequencing picks in a set of orders on a single carousel. First we consider the situation in which the sequence of the orders is given. For this problem we present an efficient dynamic programming algorithm. Second, we consider the problem without a given order sequence. We simplify this problem to a Rural Postman Problem on a circle and solve this problem to optimality. Finally, we show that the solution of the Rural Postman Problem requires at most 1.5 revolutions more than a lower bound of an optimum solution to the original problem.     

Bin covering algorithms in the second stage of the lot to order matching problem

We formulate the problem of effectively assigning semiconductor fabrication wafer lots to customer orders of various sizes, or the lot-to-order matching problem, as an integer programming problem. Our goal in this paper is to develop an efficient, practical method for solving this problem for various performance measures. Because of its complexity we decompose the problem into a knapsack problem coupled with a generalized bin-covering problem, and solve these subproblems sequentially using heuristic methods. We restrict our attention to solution methods for the less-common second subproblem, and analyze the performance of several heuristics using a data set representative of real situations in a semiconductor back-end. Based on this analysis, we show that these heuristics perform significantly better than current industrial practice in the context of the overall problem.     

On the Main Aspects of the Inverse Conductivity Problem

We consider a nonlinear inverse problem for an elliptic partial differential equation known as the Calder{\''o}n problem or the inverse conductivity problem. Based on several results, we briefly summarize them to motivate this research field. We give a general view of the problem by reviewing the available results for $C^2$ conductivities. After reducing the original problem to the inverse problem for a Schr\"odinger equation, we apply complex geometrical optics solutions to show its uniqueness. After extending the ideas of the uniqueness proof result, we establish a stable dependence between the conductivity and the boundary measurements. By using the Carleman estimate, we discuss the partial data problem, which deals with measurements that are taken only in a part of the boundary.     

About the Power Law of the PageRank Vector Component Distribution. Part 1. Numerical Methods for Finding the PageRank Vector

In Part 1 of this paper we consider the web-page ranking problem, also known as the problem of finding the PageRank vector, or the Google problem. We discuss the link between this problem and the ergodic theorem and describe different numerical methods to solve this problem together with their theoretical background, such asMarkov chain Monte Carlo and equilibrium in a macrosystem.     

Properties and methods for finding the best rank-one approximation to higher-order tensors

The problem of finding the best rank-one approximation to higher-order tensors has extensive engineering and statistical applications. It is well-known that this problem is equivalent to a homogeneous polynomial optimization problem. In this paper, we study theoretical results and numerical methods of this problem, particularly focusing on the 4-th order symmetric tensor case. First, we reformulate the polynomial optimization problem to a matrix programming, and show the equivalence between these two problems. Then, we prove that there is no duality gap between the reformulation and its Lagrangian dual problem. Concerning the approaches to deal with the problem, we propose two relaxed models. The first one is a convex quadratic matrix optimization problem regularized by the nuclear norm, while the second one is a quadratic matrix programming regularized by a truncated nuclear norm, which is a D.C. function and therefore is nonconvex. To overcome the difficulty of solving this nonconvex problem, we approximate the nonconvex penalty by a convex term. We propose to use the proximal augmented Lagrangian method to solve these two relaxed models. In order to obtain a global solution, we propose an alternating least eigenvalue method after solving the relaxed models and prove its convergence. Numerical results presented in the last demonstrate, especially for nonpositive tensors, the effectiveness and efficiency of our proposed methods.     

Approximation of the Quadratic Set Covering problem

We study in this article the polynomial approximation properties of the Quadratic Set Covering problem. This problem, which arises in many applications, is a natural generalization of the usual Set Covering problem. We show that this problem is very hard to approximate in the general case, and even in classical subcases (when the size of each set or when the frequency of each element is bounded by a constant). Then we focus on the convex case and give both positive and negative approximation results. Finally, we tackle the unweighted version of this problem.     

二阶非线性椭圆型方程带位移的边值问题

In this paper, we consider the boundary value problem with the shift for nonlinear uniformly elliptic equations of second order in a multiply connected domain. For this sake, we propose a modified boundary value problem for nonlinear elliptic systems of first order equations, and give a priori estimates of solutions for the modified boundary value problem. Afterwards we prove by using the Schauder fixedpoint theorem that this boundary value problem with some conditions has a solution. The result obtained is the generlization of the corresponding theorem on the Poincare boundary value problem.     

Contraction of the proximal mapping and applications to the equilibrium problem

In this paper, we introduce a new definition of Lipschitz-type continuity of a bifunction. Using this definition, we prove the contraction of the proximal mapping and apply it to the equilibrium problem over the fixed-point set of a nonexpansive mapping. We present a new algorithm for this problem. Under classical conditions, the convergence of the algorithm is proved. Finally, we present some numerical results for the proposed algorithm.     

On the complexity of the word problem for automaton semigroups and automaton groups

In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and automaton groups, we introduce automaton-inverse semigroups, which are generated by partial, yet invertible automata. We show that there is an automaton-inverse semigroup and, thus, an automaton semigroup with a PSpace-complete word problem. We also show that there is an automaton group for which the word problem with a single rational constraint is PSpace-complete. Additionally, we provide simpler constructions for the uniform word problems of these classes. For the uniform word problem for automaton groups (without rational constraints), we show NL-hardness. Finally, we investigate a question asked by Cain about a better upper bound for the length of a word on which two distinct elements of an automaton semigroup must act differently.A detailed listing of the contributions of this paper can be found at the end of this paper.     

To the Solution of the Hilbert Problem with Infinite Index

In this paper, we obtain a generalization of the method of regularizing multipliers for the solution of the Hilbert boundary-value problem with finite index in the theory of analytic functions to the case of an infinite power-behaved index. This method is used to obtain a general solution of the homogeneous Hilbert problem for the half-plane, a solution that depends on the existence and the number of entire functions possessing mirror symmetry with respect to the real axis and satisfying some additional constraints related to the singularity characteristic of the index. To solve of the inhomogeneous problem, we essentially use a specially constructed solution of the homogeneous problem whereby we reduce the boundary condition of the Hilbert problem to a Dirichlet problem.     

Time optimal sampled-data controls for the heat equation

In this paper, we first design a time optimal control problem for the heat equation with sampled-data controls, and then use it to approximate a time optimal control problem for the heat equation with distributed controls.The study of such a time optimal sampled-data control problem is not easy, because it may have infinitely many optimal controls. We find connections among this problem, a minimal norm sampled-data control problem and a minimization problem, and obtain some properties on these problems. Based on these, we not only build up error estimates for optimal time and optimal controls between the time optimal sampled-data control problem and the time optimal distributed control problem, in terms of the sampling period, but we also prove that such estimates are optimal in some sense.     

On the semicontinuity problem of fibers and global F-regularity

In this article, we discuss the semicontinuity problem of certain properties on fibers for a morphism of schemes. One aspect of this problem is local. Namely, we consider properties of schemes at the level of local rings, in which the main results are established by solving the lifting and localization problems for local rings. In particular, we obtain the localization theorems in the case of seminormal and F-rational rings, respectively. Another aspect of this problem is global, which is often related to the vanishing problem of certain higher direct image sheaves. As a test example, we consider the deformation of the global F-regularity.     

The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect

In this paper, we analyse the single machine maximum lateness minimization scheduling problem with the processing time based aging effect, where the processing time of each job is described by a non-decreasing function dependent on the sum of the normal processing times of preceded jobs. The computational complexity of this problem was not determined. However, we show it is strongly NP-hard by proving the strong NP-hardness of the single machine maximum completion time minimization problem with this aging model and job deadlines. Furthermore, we determine the boundary between polynomially solvable and NP-hard cases.     

A new method for solving the nonlinear second-order boundary value differential equations

In this paper we use measure theory to solve a wide range of second-order boundary value ordinary differential equations. First, we transform the problem to a first order system of ordinary differential equations (ODE’s) and then define an optimization problem related to it. The new problem is modified into one consisting of the minimization of a linear functional over a set of Radon measures; the optimal measure is then approximated by a finite combination of atomic measures and the problem converted approximatly to a finite-dimensional linear programming problem. The solution to this problem is used to construct the approximate solution of the original problem. Finally we get the error functionalE (we define in this paper) for the approximate solution of the ODE’s problems.