Projection with a Minimal System of Inequalities

Projection of a polyhedron involves the use of a cone whose extreme rays induce the inequalities defining the projection. These inequalities need not be facet defining. We introduce a transformation that produces a cone whose extreme rays induce facets of the projection.     

On the sum of distances along a circle

The arc distance between two points on a circle is their geodesic distance along the circle. We study the sum of the arc distances determined by n points on a circle, which is a useful measure of the evenness of scales and rhythms in music theory. We characterize the configurations with the maximum sum of arc distances by a balanced condition: for each line that goes through the circle center and touches no point, the numbers of points on each side of the line differ by at most one. When the points are restricted to lattice positions on a circle, we show that Toussaint's snap heuristic finds an optimal configuration. We derive closed-form formulas for the maximum sum of arc distances when the points are either allowed to move continuously on the circle or restricted to lattice positions. We also present a linear-time algorithm for computing the sum of arc distances when the points are presorted by the polar coordinates.     

Solving molecular distance geometry problems by global optimization algorithms

In this paper we consider global optimization algorithms based on multiple local searches for the Molecular Distance Geometry Problem (MDGP). Three distinct approaches (Multistart, Monotonic Basin Hopping, Population Basin Hopping) are presented and for each of them a computational analysis is performed. The results are also compared with those of two other approaches in the literature, the DGSOL approach (Moré, Wu in J. Glob. Optim. 15:219–234, 1999) and a SDP based approach (Biswas et al. in An SDP based approach for anchor-free 3D graph realization, Technical Report, Operations Research, Stanford University, 2005).     

n元椭球面的判定及所围椭球体的体积

给出n元二次曲面是椭球面的充要条件和所对应的n维椭球体的体积计算公式,并且条件和体积的计算中只用到曲面中的系数行列式,使判定和体积计算较为方便.     

Optimization of Molecular Similarity Index with Applications to Biomolecules

Molecular similarity index measures the similarity between two molecules. Computing the optimal similarity index is a hard global optimization problem. Since the objective function value is very hard to compute and its gradient vector is usually not available, previous research has been based on non-gradient algorithms such as random search and the simplex method. In a recent paper, McMahon and King introduced a Gaussian approximation so that both the function value and the gradient vector can be computed analytically. They then proposed a steepest descent algorithm for computing the optimal similarity index of small molecules. In this paper, we consider a similar problem. Instead of computing atom-based derivatives, we directly compute the derivatives with respect to the six free variables describing the relative positions of the two molecules.. We show that both the function value and gradient vector can be computed analytically and apply the more advanced BFGS method in addition to the steepest descent algorithm. The algorithms are applied to compute the similarities among the 20 amino acids and biomolecules like proteins. Our computational results show that our algorithm can achieve more accuracy than previous methods and has a 6-fold speedup over the steepest descent method.     

On Projections of Semi-Algebraic Sets Defined by Few Quadratic Inequalities

Let S⊂ℝ ^k+m be a compact semi-algebraic set defined by P ₁≥0,…,P _ℓ ≥0, where P _i ∈ℝ[X ₁,…,X _k ,Y ₁,…,Y _m ], and deg (P _i )≤2, 1≤i≤ℓ. Let π denote the standard projection from ℝ ^k+m onto ℝ ^m . We prove that for any q>0, the sum of the first q Betti numbers of π(S) is bounded by (k+m) ^{O(q ℓ)}. We also present an algorithm for computing the first q Betti numbers of π(S), whose complexity is . For fixed q and ℓ, both the bounds are polynomial in k+m. The author was supported in part by an NSF Career Award 0133597 and a Sloan Foundation Fellowship.     

The complexity of optimizing over a simplex,hypercube or sphere: a short survey

We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere. These relatively simple optimization problems arise naturally from diverse applications. We review known approximation results as well as negative (inapproximability) results from the recent literature.      

Enumerating Solutions of a System of Linear Inequalities Related to Magic Squares

We enumerate the solutions of a system of a simple homogeneous linear inequalities, motivated by magic squares and their generalizations. We also compute the generating function of these numbers, and prove that it is a rational function. Received March 1, 2005     

由算子定义的一类p叶解析函数性质

通过Hadarnard卷积定义算子I<,n+p-1>,并利用其引进了新的解析函数类H(p,n,δ,A,B),研究了函数f(z)(f(z)∈A<,p>)属于函数类H(p,n,δ,A,B)的充分条件和部分和性质,同时还考虑了类H(p,n,δ,A,B)的卷积性质.     

Computing a Minimum Weight Triangulation of a Sparse Point Set*

Investigating the minimum weight triangulation of a point set with constraint is an important approach for seeking the ultimate solution of the minimum weight triangulation problem. In this paper, we consider the minimum weight triangulation of a sparse point set, and present an O(n ⁴) algorithm to compute a triangulation of such a set. The property of sparse point set can be converted into a new sufficient condition for finding subgraphs of the minimum weight triangulation. A special point set is exhibited to show that our new subgraph of minimum weight triangulation cannot be found by any currently known methods.     

Minimization of the Ratio of Functions Defined as Sums of the Absolute Values

This paper addresses a new class of linearly constrained fractional programming problems where the objective function is defined as the ratio of two functions which are the sums of the absolute values of affine functions. This problem has an important application in financial optimization. This problem is a convex-convex type of fractional program which cannot be solved by standard algorithms. We propose a branch-and-bound algorithm and an integer programming algorithm. We demonstrate that a fairly large scale problem can be solved within a practical amount of time. The research of the first author was supported in part by the Grant-in-Aid for Scientific Research of the Ministry of Education, Science, Culture and Sports of the Government of Japan, B(2) 15310122 and 15656025.     

On the Solution of a Locally Finite System of Linear Inequalities with Graph Structure

We propose a method for the solution of a locally finite system of linear inequalities that arises in the course of solution of problems of control over resource in networks with generalized Kirchhoff law. We present a criterion for a system of inequalities to have the graph structure.     

极大代数上线性系统的3维最小实现的研究

研究了极大代数上线性系统的3维最小实现问题,给出了特征方程为λ<'3> c<,0>λ<'0>=c<,2>λ<'2> c<,1>λ,当c<,1>=c<'2><,2>,c<,0>=C<,1>C<,2>时,无穷序列{g<,2>}<,0><'∞>存在3维最小实现的充要条件.     

A Sharper Estimate on the Betti Numbers of Sets Defined by Quadratic Inequalities

In this paper we consider the problem of bounding the Betti numbers, b _i (S), of a semi-algebraic set S⊂ℝ ^k defined by polynomial inequalities P ₁≥0,…,P _s ≥0, where P _i ∈ℝ[X ₁,…,X _k ], s<k, and deg (P _i )≤2, for 1≤i≤s. We prove that for 0≤i≤k−1,

Robust Stability and Performance Analysis of Uncertain Systems Using Linear Matrix Inequalities

A wide variety of problems in system and control theory can be formulated or reformulated as convex optimization problems involving linear matrix inequalities (LMIs), that is, constraints requiring an affine combination of symmetric matrices to be positive semidefinite. For a few very special cases, there are analytical solutions to these problems, but in general LMI problems can be solved numerically in a very efficient way. Thus, the reduction of a control problem to an optimization problem based on LMIs constitutes, in a sense, a solution to the original problem. The objective of this article is to provide a tutorial on the application of optimization based on LMIs to robust control problems. In the first part of the article, we provide a brief introduction to optimization based on LMIs. In the second part, we describe a specific example, that of the robust stability and performance analysis of uncertain systems, using LMI optimization.     

A Revision of the Trapezoidal Branch-and-Bound Algorithm for Linear Sum-of-Ratios Problems

In this paper, we point out a theoretical flaw in Kuno [(2002)Journal of Global Optimization 22, 155–174] which deals with the linear sum-of-ratios problem, and show that the proposed branch-and-bound algorithm works correctly despite the flaw. We also note a relationship between a single ratio and the overestimator used in the bounding operation, and develop a procedure for tightening the upper bound on the optimal value. The procedure is not expensive, but the revised algorithms incorporating it improve significantly in efficiency. This is confirmed by numerical comparisons between the original and revised algorithms. The author was partially supported by the Grand-in-Aid for Scientific Research (C)(2) 15560048 from the Japan Society for the Promotion of Science.