Coupled intervals in the discrete calculus of variations: necessity and sufficiency

In this work we study nonnegativity and positivity of a discrete quadratic functional with separately varying endpoints. We introduce a notion of an interval coupled with 0, and hence, extend the notion of conjugate interval to 0 from the case of fixed to variable endpoint(s). We show that the nonnegativity of the discrete quadratic functional is equivalent to each of the following conditions: The nonexistence of intervals coupled with 0, the existence of a solution to Riccati matrix equation and its boundary conditions. Natural strengthening of each of these conditions yields a characterization of the positivity of the discrete quadratic functional. Since the quadratic functional under consideration could be a second variation of a discrete calculus of variations problem with varying endpoints, we apply our results to obtain necessary and sufficient optimality conditions for such problems. This paper generalizes our recent work in [R. Hilscher, V. Zeidan, Comput. Math. Appl., to appear], where the right endpoint is fixed.     

On the complexity of linear programming under finite precision arithmetic

In this paper we study the complexity of solving linear programs in finite precision arithmetic. This is the normal setup in scientific computation, as digital computers work in finite precision. We analyze two aspects of the complexity: one is the number of arithmetic operations required to solve the problem approximately, and the other is the working precision required to carry out some critical computations safely. We show how the conditioning of the problem instance affects the working precision required and the computational requirements of a classical logarithmic barrier algorithm to approximate the optimal value of the problem within a given tolerance. Our results show that these complexity measures depend linearly on the logarithm of a certain condition measure. We carry out the analysis by looking at how well Newton's Method can follow the central trajectory of the feasible set, and computing error bounds in terms of the condition measure. These results can be interpreted as a theoretical indication of good numerical behavior of the logarithmic barrier method, in the sense that a problem instance twice as hard as the other from the numerical point of view, requires only at most twice as much precision to be solved. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This research has been supported through grants from Fundación Andes, under agreement C12021/7, and FONDECYT (project number 1930948).     

A fast $$(2 + \frac{2}{7})$$ ( 2 + 2 7 ) -approximation algorithm for capacitated cycle covering

Mathematical Programming - We consider the capacitated cycle covering problem: given an undirected, complete graph G with metric edge lengths and demands on the vertices, we want to cover the...     

Optimization and data mining in medicine

Mathematical theory of optimization has found many applications in the area of medicine over the last few decades. Several data analysis and decision making problems in medicine can be formulated using optimization and data mining techniques. The significance of the mathematical models is greatly realized in the recent years owing to the growing technological capabilities and the large amounts of data available. In this paper, we attempt to give a brief overview of some of the most interesting applications of mathematical programming and data mining in medicine. In the overview, we include applications like radiation therapy treatment, microarray data analysis, and computational neuroscience.     

Enhanced drainage and coarsening in aqueous foams

Experiments are presented elucidating how the evolution of foam microstructure by gas diffusion from high to low pressure bubbles can significantly speed up the rate of gravitational drainage, and vice versa. This includes detailed data on the liquid-fraction dependence of the coarsening rate, and on the liquid-fraction and the bubble-size profiles across a sample. These results can be described by a "coarsening equation" for the increase of bubble growth rate for drier foams. Spatial variation of the average bubble size and liquid fraction can also affect the growth and drainage rates.