A Subdivision Approach to Maximum Parsimony

Determining an optimal phylogenetic tree using maximum parsimony, also referred to as the Steiner tree problem in phylogenetics, is NP hard. Here we provide a new formulation for this problem which leads to an analytical and linear time solution when the dimensionality (sequence length, or number of characters) is at most two. This new formulation of the problem provides a direct link between the maximum parsimony problem and the maximum compatibility problem via the intersection graph. The solution for the “two character case” has numerous practical applications in phylogenetics, some of which are discussed. Received January 16, 2006     

A Note on Fuzzy Relation Programming Problems with Max-Strict-t-Norm Composition

The fuzzy relation programming problem is a minimization problem with a linear objective function subject to fuzzy relation equations using certain algebraic compositions. Previously, Guu and Wu considered a fuzzy relation programming problem with max-product composition and provided a necessary condition for an optimal solution in terms of the maximum solution derived from the fuzzy relation equations. To be more precise, for an optimal solution, each of its components is either 0 or the corresponding component's value of the maximum solution. In this paper, we extend this useful property for fuzzy relation programming problem with max-strict-t-norm composition and present it as a supplemental note of our previous work.     

Canonical dual approach to solving the maximum cut problem

This paper presents a canonical dual approach for finding either an optimal or approximate solution to the maximum cut problem (MAX CUT). We show that, by introducing a linear perturbation term to the objective function, the maximum cut problem is perturbed to have a dual problem which is a concave maximization problem over a convex feasible domain under certain conditions. Consequently, some global optimality conditions are derived for finding an optimal or approximate solution. A gradient decent algorithm is proposed for this purpose and computational examples are provided to illustrate the proposed approach.     

Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams

Two important tasks in probabilistic reasoning are the computation of the maximum posterior probability of a given subset of the variables in a Bayesian network (MAP), and the computation of the maximum expected utility of a strategy in an influence diagram (MEU). Both problems are NP^PP-hard to solve, and NP-hard to approximate when the treewidth of the underlying graph is bounded. Despite the similarities, researches on both problems have largely been conducted independently, with algorithmic solutions and insights designed for one problem not (trivially) transferable to the other one. In this work, we show constructively that these two problems are equivalent in the sense that any algorithm designed for one problem can be used to solve the other with small overhead. Moreover, the reductions preserve the boundedness of treewidth. Building on the known complexity of MAP on networks whose parameters are imprecisely specified, we show how to use the reductions to characterize the complexity of MEU when the parameters are set-valued. These equivalences extend the toolbox of either problem, and shall foster new insights into their solution.     

Proper efficiency in a linear fractional vector maximum problem with generalized convex constraints

In the present paper, a vector maximum problem (VMP) with linear fractional objectives and generalized convex constraints is considered. A necessary and sufficient condition for an efficient solution of (VMP) is derived in Kuhn-Tucker's form. Moreover, it is proved that under a certain boundedness assumption an efficient solution is properly efficient. This extends the results of Choo [3] for a linear fractional vector maximum problem with linear constraints to generalized convex constraints. An example is given to illustrate the results.     

Constructing an artificial basis in the symmetric linear programming problems

The constraint region of a symmetric LP problem is extended to a region with a known corner point constructed on the gradient of a linear form. The solution of the problem by the simplex method starts with the supporting program that corresponds to this corner point. The algorithm is proved, a bound on an approximate solution is obtained, and cases with an exact solution are identified.Khmel'nitskii Technological Institute of Consumer Services. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 67, pp. 106–113, 1989.     

Minimum residual iteration for a dual–dual mixed formulation of exterior transmission problems

We investigate the minimum residual method for symmetric, indefinite linear systems of a so‐called dual–dual structure. These systems arise when using a combined dual‐mixed finite element method with a Dirichlet‐to‐Neumann mapping to solve a class of exterior transmission problems. As a model problem we consider an elliptic equation of divergence form coupled with the Laplace equation in an unbounded region of the plane. We give abstract convergence results for the preconditioned minimum residual method for the solution of linear systems of the special dual–dual structure. For our model problem, we show that this iterative method provides an efficient solution procedure where standard preconditioners can directly be used. Copyright © 2001 John Wiley & Sons, Ltd.     

The bilevel linear/linear fractional programming problem

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. In this paper we consider the bilevel linear/linear fractional programming problem in which the objective function of the first level is linear, the objective function of the second level is linear fractional and the feasible region is a polyhedron. For this problem we prove that an optimal solution can be found which is an extreme point of the polyhedron. Moreover, taking into account the relationship between feasible solutions to the problem and bases of the technological coefficient submatrix associated to variables of the second level, an enumerative algorithm is proposed that finds a global optimum to the problem.     

A General Alternative Procedure for Solving Negative Degree of Difficulty Problems in Geometric Programming

The degree of difficulty is an important concept in classical geometric programming theory. The dual problem is often infeasible when the degree of difficulty is negative and little has been published on this topic. In this paper, an alternative procedure is developed to find the optimal solution for the posynomial geometric programming problem with a negative degree of difficulty. First an equivalent problem was constructed with a positive degree of difficulty and the general posynomial geometric programming problem was solved using an original method previously developed by the authors. This method avoids the difficulty of non-differentiability of the dual objective function in the classical methods classified as dual. It also avoids the problem that appears when the feasible region for the dual problem is formed by an inconsistent system of linear equations.     

The tolerance approach in multiobjective linear fractional programming

When solving a multiobjective programming problem by the weighted sum approach, weights represent the relative importance associated to the objectives. As these values are usually imprecise, it is important to analyze the sensitivity of the solution under possible deviations on the estimated values. In this sense, the tolerance approach provides a direct measure of how weights may vary simultaneously and independently from their estimated values while still retaining the same efficient solution. This paper provides an explicit expression to the maximum tolerance on weights in a multiobjective linear fractional programming problem when all the denominators are equal. An application is also presented to illustrate how the results may help the decision maker to choose a most satisfactory solution in a production problem.     

An Algorithm for Solving Optimization Problems with One Linear Objective Function and Finitely Many Constraints of Fuzzy Relation Inequalities

An optimization model with one linear objective function and fuzzy relation equation constraints was presented by Fang and Li (1999) as well as an efficient solution procedure was designed by them for solving such a problem. A more general case of the problem, an optimization model with one linear objective function and finitely many constraints of fuzzy relation inequalities, is investigated in this paper. A new approach for solving this problem is proposed based on a necessary condition of optimality given in the paper. Compared with the known methods, the proposed algorithm shrinks the searching region and hence obtains an optimal solution fast. For some special cases, the proposed algorithm reaches an optimal solution very fast since there is only one minimum solution in the shrunk searching region. At the end of the paper, two numerical examples are given to illustrate this difference between the proposed algorithm and the known ones.     

Controlled perturbations for quadratically constrained quadratic programs

Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains that are essentially linear. However, the objective function is not differentiable over the constraint region. In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this controlled perturbation scheme.     

Placing a finite size facility with a center objective on a rectangular plane with barriers

This paper addresses the finite size 1-center placement problem on a rectangular plane in the presence of barriers. Barriers are regions in which both facility location and travel through are prohibited. The feasible region for facility placement is subdivided into cells along the lines of Larson and Sadiq [R.C. Larson, G. Sadiq, Facility locations with the Manhattan metric in the presence of barriers to travel, Operations Research 31 (4) (1983) 652–669]. To overcome complications induced by the center (minimax) objective, we analyze the resultant cells based on the cell corners. We study the problem when the facility orientation is known a priori. We obtain domination results when the facility is fully contained inside 1, 2 and 3-cornered cells. For full containment in a 4-cornered cell, we formulate the problem as a linear program. However, when the facility intersects gridlines, analytical representation of the distance functions becomes challenging. We study the difficulties of this case and formulate our problem as a linear or nonlinear program, depending on whether the feasible region is convex or nonconvex. An analysis of the solution complexity is presented along with an illustrative numerical example.     

双层线性规划的一个全局优化方法

用线性规划对偶理论分析了双层线性规划的最优解与下层问题的对偶问题可行域上极点之间的关系，通过求得下层问题的对偶问题可行域上的极点，将双层线性规划转化为有限个线性规划问题，从而用线性规划方法求得问题的全局最优解．由于下层对偶问题可行域上只有有限个极点，所以方法具有全局收敛性．     

BSDEs driven by time-changed Lévy noises and optimal control

We study backward stochastic differential equations (BSDEs) for time-changed Lévy noises when the time-change is independent of the Lévy process. We prove existence and uniqueness of the solution and we obtain an explicit formula for linear BSDEs and a comparison principle. BSDEs naturally appear in control problems. Here we prove a sufficient maximum principle for a general optimal control problem of a system driven by a time-changed Lévy noise. As an illustration we solve the mean–variance portfolio selection problem.     

The stability of parametrically forced coupled oscillators in sum resonance

For a system of two damped parametrically forced oscillators in sum resonance the planar stability diagram of amplitude versus frequency of the forcing shows a discontinuity at damping zero. This is a well known phenomenon, for which we give a geometrical explanation. A linear stability analysis suffices. We show that a versal (i.e. a structurally stable) matrix unfolding for this problem needs four parameters, indicating that the stability diagram is actually four dimensional. The boundary of the stability region in parameter space is singular, this provides a geometric explanation of the discontinuity in the planar stability diagram.     

Optimal discrete-valued control computation

In this paper, we consider an optimal control problem in which the control takes values from a discrete set and the state and control are subject to continuous inequality constraints. By introducing auxiliary controls and applying a time-scaling transformation, we transform this optimal control problem into an equivalent problem subject to additional linear and quadratic constraints. The feasible region defined by these additional constraints is disconnected, and thus standard optimization methods struggle to handle these constraints. We introduce a novel exact penalty function to penalize constraint violations, and then append this penalty function to the objective. This leads to an approximate optimal control problem that can be solved using standard software packages such as MISER. Convergence results show that when the penalty parameter is sufficiently large, any local solution of the approximate problem is also a local solution of the original problem. We conclude the paper with some numerical results for two difficult train control problems.     

On the Motion of Agents across Terrain with Obstacles

The paper is devoted to finding the time optimal route of an agent travelling across a region from a given source point to a given target point. At each point of this region, a maximum allowed speed is specified. This speed limit may vary in time. The continuous statement of this problem and the case when the agent travels on a grid with square cells are considered. In the latter case, the time is also discrete, and the number of admissible directions of motion at each point in time is eight. The existence of an optimal solution of this problem is proved, and estimates of the approximate solution obtained on the grid are obtained. It is found that decreasing the size of cells below a certain limit does not further improve the approximation. These results can be used to estimate the quasi-optimal trajectory of the agent motion across the rugged terrain produced by an algorithm based on a cellular automaton that was earlier developed by the author.     

Trust region subproblem with an additional linear inequality constraint

This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with a single linear inequality constraint. We present an efficient algorithm to solve the problem using a diagonalization scheme that requires solving a simple convex minimization problem. Attainment of the global optimality conditions is discussed. Our preliminary numerical experiments on several randomly generated test problems show that, the new approach is much faster in finding the global optimal solution than the known semidefinite relaxation approach, especially when solving large scale problems.     

优化方法解决无上层约束的线性双层规划问题

In this paper we propose an optimal method for solving the linear bilevel programming problem with no upper-level constraint. The main idea of this method is that the initial point which is in the feasible region goes forward along the optimal direction firstly. When the iterative point reaches the boundary of the feasible region, it can continue to go forward along the suboptimal direction. The iteration is terminated until the iterative point cannot go forward along the suboptimal direction and effective direction, and the new iterative point is the solution of the lower-level programming. An algorithm which bases on the main idea above is presented and the solution obtained via this algorithm is proved to be optimal solution to the bilevel programming problem. This optimal method is effective for solving the linear bilevel programming problem.