The long-step method of analytic centers for fractional problems

We develop a long-step surface-following version of the method of analytic centers for the fractional-linear problem min{t ₀ |t ₀ B(x) −A(x) εH, B(x) εK, x εG}, whereH is a closed convex domain,K is a convex cone contained in the recessive cone ofH, G is a convex domain andB(·),A(·) are affine mappings. Tracing a two-dimensional surface of analytic centers rather than the usual path of centers allows to skip the initial “centering” phase of the path-following scheme. The proposed long-step policy of tracing the surface fits the best known overall polynomial-time complexity bounds for the method and, at the same time, seems to be more attractive computationally than the short-step policy, which was previously the only one giving good complexity bounds. The research was partly supported by the Israeli-American Binational Science Foundation (BSF).     

Using the analytic center in the feasibility pump

The feasibility pump (FP) has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems. Briefly, FP alternates between two sequences of points: one of feasible solutions for the relaxed problem, and another of integer points. This short paper extends FP, such that the integer point is obtained by rounding a point on the (feasible) segment between the computed feasible point and the analytic center for the relaxed linear problem.     

On polynomiality of the method of analytic centers for fractional problems

We establish polynomial time convergence of the method of analytic centers for the fractional programming problemt→min |x∈G, tB(x)−A(x)∈K, whereG ⊂ ℝ ⁿ is a closed and bounded convex domain,K ⊂ ℝ ^m is a closed convex cone andA(x):G → ℝ ⁿ ,B(x):G→K are regular enough (say, affine) mappings. This research was partly supported by grant #93-012-499 of the Fundamental Studies Foundation of Russian Academy of Sciences     

Complexity analysis of the analytic center cutting plane method that uses multiple cuts

We analyze the complexity of the analytic center cutting plane or column generation algorithm for solving general convex problems defined by a separation oracle. The oracle is called at the analytic center of a polytope, which contains a solution set and is given by the intersection of the linear inequalities previously generated from the oracle. If the center is not in the solution set, separating hyperplanes will be placed through the center to shrink the containing polytope. While the complexity result has been recently established for the algorithm when one cutting plane is placed in each iteration, the result remains open when multiple cuts are added. Moreover, adding multiple cuts actually is a key to practical effectiveness in solving many problems and it presents theoretical difficulties in analyzing cutting plane methods. In this paper, we show that the analytic center cutting plane algorithm, with multiple cuts added in each iteration, still is a fully polynomial approximation algorithm. The research of the author is supported by NSF grant DDM-9207347, an Iowa Business School Summer Grant, and a University of Iowa Obermann Fellowship.     

Maintaining closeness to the analytic center of a polytope by perturbing added hyperplanes

In this work we consider a regionR in ℝ ⁿ given by a finite number of linear inequalities and having nonempty interior. We assume a pointx ^o is given, which is close in certain norm to the analytic center ofR, and that a new linear inequality is added to those definingR. It is constructively shown how to obtain a perturbation of the right-hand side of this inequality such that the pointx ^o is still close, in the same norm, to the analytic center of this perturbed polytope. This fact plays a central role in interior point postoptimality techniques for linear programming involving methods of centers.     

On computing the center of a convex quadratically constrained set

We propose a method for finding analytic center of a convex feasible region whose boundaries are defined by quadratic functions. The algorithm starts from an arbitrary initial point and approaches to the desired center by simultaneously reducing infeasibility or slackness of all constraints. A partial Newton step is taken at each iteration.Research supported in part by the ONR under grant N00014-87-K-0214 and by the NSF under grant CCR-8810107.Research supported in part by the NSF under grant ECS-8721709.     

A note on some analytic center cutting plane methods for convex feasibility and minimization problems

Recently Goffin, Luo and Ye have analyzed the complexity of an analytic center algorithm for convex feasibility problems defined by a separation oracle. The oracle is called at the (possibly approximate) analytic center of the set given by the linear inequalities which are the previous answers of the oracle. We discuss oracles for the problem of minimizing a convex (possibly nondifferentiable) function subject to box constraints, and give corresponding complexity estimates.The research of the first author is supported by the Polish Academy of Sciences; the research of the second author is supported by the State Committee for Scientific Research under Grant 8S50502206.     

Complexity of some cutting plane methods that use analytic centers

We consider cutting plane methods for minimizing a convex (possibly nondifferentiable) function subject to box constraints. At each iteration, accumulated subgradient cuts define a polytope that localizes the minimum. The objective and its subgradient are evaluated at the analytic center of this polytope to produce one or two cuts that improve the localizing set. We give complexity estimates for several variants of such methods. Our analysis is based on the works of Goffin, Luo and Ye. Research supported by the State Committee for Scientific Research under Grant 8S50502206.     

The use of stochastic analytic center for yield maximization of systems with general distributions of component values

This paper presents a new method for maximizing manufacturing yield when the realizations of system components are dependent random variables with general distributions. The method uses a new concept of stochastic analytic center introduced herein to design the unknown parameters of component values. Design specifications define a feasible region which, in the nonlinear case, is linearized using a first-order approximation. The resulting problem becomes a convex optimization problem. Monte Carlo simulation is used to evaluate the actual yield of the optimal designs of a tutorial example.     

Interior-point methods: An old and new approach to nonlinear programming

In this paper we discuss the main concepts of structural optimization, a field of nonlinear programming, which was formed by the intensive development of modern interior-point schemes.     

Heuristic fuzzy-neuro network and its application to reactive navigation of a mobile robot

A novel pattern recognition approach to reactive navigation of a mobile robot is presented in this paper. A heuristic fuzzy-neuro network is developed for pattern-mapping between quantized ultrasonic sensory data and velocity commands to the robot. The design goal was to enable an autonomous mobile robot to navigate safely and efficiently to a target position in a previously unknown environment. Useful heuristic rules were combined with the fuzzy Kohonen clustering network (FKCN) to build the desired mapping between perception and motion. This method provides much faster response to unexpected events and is less sensitive to sensor misreading than conventional approaches. It allows continuous, fast motion of the mobile robot without any need to stop for obstacles. The effectiveness of the proposed method is demonstrated in a series of practical tests on our experimental mobile robot.     

Functional-differential equations in a class of analytic functions and its application to elastic composites

According to Muskhelishvili’s approach, two-dimensional elastic problems for media with non-overlapping inclusions are reduced to boundary value problems for analytic functions in multiply connected domains. Using a method of functional equations developed by Mityushev, we reduce such a problem for a circular multiply connected domain to functional-differential equations. It is proved that the operator corresponding to the functional-differential equations is compact in the Hardy–Sobolev space. Moreover, these equations can be solved by the method of successive approximation under some natural conditions.     

Chapter 7 DEA multiplier analytic center sensitivity with an illustrative application to independent oil companies

The setE of extreme points which are also efficient are of basic importance in defining the efficiency frontier, from which the observations for all other DMUs are evaluated in DEA. A significant question which we address is “What variations in the data can be tolerated before the membership inE is changed?” This topic is explored using (1) a simple illustrative example, and (2) production data for 30 independent oil companies during the period 1983–1985. Data were allowed to vary simultaneously for all observations and in different subsets determined by random drawings of data for points both inE and not inE. The results were found to be robust in this study, thereby lending further support to earlier studies which also found these classifications into efficient and inefficient performers to be robust in DEA. Technical developments for these new methods of sensitivity analysis are supplied. These developments feature an application of analytic center (interior point) algorithms which ensure that the Strong Complementary Slackness Condition (SCSC) is fulfilled. The solutions satisfy a mathematical condition called “centrality”. Generally, the solutions are at interior points calledanalytic centers. At these interior points, continuity of the input-output ratios ensures that DMUs inE remain inE for at least small relative variations in the data, while empirically these properties have been found to extend to much larger variations in the data sets.     

Existence and uniqueness of analytic solution for unsteady crystals with zero surface tension

We study the initial value problem for two-dimensional dendritic crystal growth with zero surface tension. If the initial data is analytic and close to Ivantsov steady solution, it is proved that unique analytic solution exists locally in time. The analysis is based on a Nirenberg Theorem on abstract Cauchy-Kovalevsky problem in properly chosen Banach spaces.     

A note on a nonlinear functional equation and its application

This paper treats the following type of nonlinear functional equations

     

An adaptation of the dual-affine interior point method for the surface flatness problem

This paper presents an adaptation of the dual-affine interior point method for the surface flatness problem. In order to determine how flat a surface is, one should find two parallel planes so that the surface is between them and they are as close together as possible. This problem is equivalent to the problem of solving inconsistent linear systems in terms of Tchebyshev’s norm. An algorithm is proposed and results are presented and compared with others published in the literature.     

Analytic solutions of a nonlinear iterative equation near neutral fixed points and poles

In this paper existence of analytic solutions of a nonlinear iterative equations is studied when given functions are all analytic and when given functions have poles. As well as in many previous works, we reduce this problem to finding analytic solutions of a functional equation without iteration of the unknown function f. For technical reasons, in previous works an indeterminate constant related to the eigenvalue of the linearized f at its fixed point O is required to fulfill the Diophantine condition that O is an irrationally neutral fixed point of f. In this paper the case of rationally neutral fixed points is also discussed, where the Diophantine condition is not required.     

Integrability and generalized center problem of resonant singular point

In this paper, integrability and generalized center condition of resonant singular point for a broad class of complex autonomous polynomial differential system are studied. A new method—integrating factor method of determining integrability of resonant singular point is obtained for any rational resonance ratio. At the same time, the relations of the first integral method and the integrating factor method with the normal form method are obtained.     

The fuzzy entropy concept and its application

The fuzzy entropy is applied to the seal impression problem to measure the subjective value of information under the condition of uncertainty.Two methods, successive and direct segmentation, are introduced in recognizing the pattern to find out which method is more cost-effective. For the equal entropy, the comparative elements sought in association with the cost information on the successive and direct segmentation methods are 441 and 1024, respectively. Thus, the effectiveness of the former method is 2.32 times higher than that of the latter method, provided that the cost of information is equal.A parametric analysis among the membership function, fuzzy entropy, and threshold level is made and a summary graph shown.