Calculating a minimal sphere containing a polytope defined by a system of linear inequalities

We will propose an algorithm for calculating a minimal sphere containing a polytope defined by a system of linear inequalities in low dimensional Euclidean space. This algorithm is a straightforward application of the algorithm for maximizing a convex quadratic function over a polytope. It will be shown that this algorithm successfully generates a minimal sphere when the dimensions of the underlying space is up to five.International Digital Communication Inc.     

An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem

This paper proposes a new tabu search algorithm for multi-objective combinatorial problems with the goal of obtaining a good approximation of the Pareto-optimal or efficient solutions. The algorithm works with several paths of solutions in parallel, each with its own tabu list, and the Pareto dominance concept is used to select solutions from the neighborhoods. In this way we obtain at each step a set of local nondominated points. The dispersion of points is achieved by a clustering procedure that groups together close points of this set and then selects the centroids of the clusters as search directions. A nice feature of this multi-objective algorithm is that it introduces only one additional parameter, namely, the number of paths. The algorithm is applied to the permutation flowshop scheduling problem in order to minimize the criteria of makespan and maximum tardiness. For instances involving two machines, the performance of the algorithm is tested against a Branch-and-Bound algorithm proposed in the literature, and for more than two machines it is compared with that of a tabu search algorithm and a genetic local search algorithm, both from the literature. Computational results show that the heuristic yields a better approximation than these algorithms.     

Multiplication of a Schubert polynomial by a Schur polynomial

Schur polynomials are a special case of Schubert polynomials. In this paper, we give an algorithm to compute the product of a Schubert polynomial with a Schur polynomial on the basis of Schubert polynomials. This is a special case of the general problem of the multiplication of two Schubert polynomials, where the corresponding algorithm is still missing. The main tools for the given algorithm is a factorization property of a special class of Schubert polynomials and the transition formula for Schubert polynomials.     

Global minimization of a generalized linear multiplicative programming

This article presents a simplicial branch and bound algorithm for globally solving generalized linear multiplicative programming problem (GLMP). Since this problem does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving such problem. In this algorithm, a well known simplicial subdivision is used in the branching procedure and the bound estimation is performed by solving certain linear programs. Convergence of this algorithm is established, and some experiments are reported to show the feasibility of the proposed algorithm.     

一种新的双模式盲均衡算法研究

针对恒模算法(CMA)收敛速度较慢、收敛后均方误差较大的缺点,提出一种新的双模式盲均衡算法.在算法初期,利用能快速收敛的归一化恒模算法(NCMA)进行冷启动,在算法收敛后切换到判决引导(DD-LMS)算法,减少误码率.计算机仿真表明,提出的新算法有较快的收敛速度和较低的误码率.     

Iterative algorithm for minimizing a convex function at the intersection of a spherical surface and a convex compact set

A numerical algorithm for minimizing a convex function on the set-theoretic intersection of a spherical surface and a convex compact set is proposed. The idea behind the algorithm is to reduce the original minimization problem to a sequence of convex programming problems. Necessary extremum conditions are examined, and the convergence of the algorithm is analyzed.     

Convergence to a second-order point of a trust-region algorithm with a nonmonotonic penalty parameter for constrained optimization

In a recent paper (Ref. 1), the author proposed a trust-region algorithm for solving the problem of minimizing a nonlinear function subject to a set of equality constraints. The main feature of the algorithm is that the penalty parameter in the merit function can be decreased whenever it is warranted. He studied the behavior of the penalty parameter and proved several global and local convergence results. One of these results is that there exists a subsequence of the iterates generated by the algorithm that converges to a point that satisfies the first-order necessary conditions.In the current paper, we show that, for this algorithm, there exists a subsequence of iterates that converges to a point that satisfies both the first-order and the second-order necessary conditions.This research was supported by the Rice University Center for Research on Parallel Computation, Grant R31853, and the REDI Foundation.     

A residual algorithm for finding a fixed point of a nonexpansive mapping

This paper presents a weak convergence residual algorithm for finding a fixed point of a nonexpansive mapping in a real Hilbert space. To study the numerical behavior of the algorithm it is included an extensive series of numerical experiments. Our computational experiments show that the new algorithm is computationally efficient.     

Analysis of a shellsort algorithm

D. L. Shell published in 1959, [4], a fast algorithm for internal sorting. R. M. Frank and R. B. Lazarus pointed out in 1960, [3], a disadvantage in the original design of the algorithm and changes were proposed based on heuristic arguments. J. Boothroyd took care of Frank and Lazarus objections in an elegant algorithm published 1963, [1]. If we change Boothroyds algorithm slightly we get an algorithm which, in the general case with the arguments of Frank and Lazarus, is even worse than the original one. On the other hand this algorithm has the advantage that it is easy to analyse theoretically. To the author's knowledge such an analysis has not yet been given for any of the other Shellsort algorithms.     

Global Maximization of a Generalized Concave Multiplicative Function

This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence of the algorithm is shown; computational considerations and benefits for users of the algorithm are given. A sample problem is also solved.     

Complexity analysis of a linear complementarity algorithm based on a Lyapunov function

We consider a path following algorithm for solving linear complementarity problems with positive semi-definite matrices. This algorithm can start from any interior solution and attain a linear rate of convergence. Moreover, if the starting solution is appropriately chosen, this algorithm achieves a complexity of O( L}) iterations, wherem is the number of variables andL is the size of the problem encoding in binary. We present a simple complexity analysis for this algorithm, which is based on a new Lyapunov function for measuring the nearness to optimality. This Lyapunov function has itself interesting properties that can be used in a line search to accelerate convergence. We also develop an inexact line search procedure in which the line search stepsize is obtainable in a closed form. Finally, we extended this algorithm to handle directly variables which are unconstrained in sign and whose corresponding matrix is positive definite. The rate of convergence of this extended algorithm is shown to be independent of the number of such variables.This research is partially supported by the U.S. Army Research Office, contract DAAL03-86-K-0171 (Center for Intelligent Control Systems), and by the National Science Foundation, grant NSF-ECS-8519058.     

一类MPEC问题的SQP算法

本文研究带线性互补约束规划问题的 SQP算法 .该算法不要求精确计算初值 ,是针对初值非精确计算情形的新算法 ,证明了该算法的收敛性 .     

Deepest point of a polyhedron and linear programming

Abstract

The problem of finding a deepest point (a ball centre) of a polyhedron is studied. A finite combinatorial interior point method is presented for this problem which yields an algorithm for linear programming. We conjecture that this is a strongly polynomial algorithm. Meanwhile developing the algorithm, several auxiliary results were found; among others, Gorokh and Werner’s algorithm for linear inequalities is slightly extended. Our numerical experiments with the problem detected bugs in a linear interior point solver used in MATLAB 6 Optimization Toolbox.     

Discrete allocation of a linear resource according to a sum-of-products objective

The allocation of a linear resource according to the sum of the returns from independent activities is considered. The return from each activity is given by a product of concave and nondecreasing functions of a single allocation variable. The model can be used, for instance, to describe probabilities of success of several serial tasks, into which an activity is subdivided. An incremental algorithm is defined and conditions are given for the algorithm to generate an optimal solution; otherwise, the problem is solved by a two-step procedure involving the incremental maximization of the return corresponding to a single activity and the combination of the activities by dynamic programming. Examples are given of problems solvable and not solvable by the incremental algorithm.     

Optimal detection of a recurring tuple of reference fragments in a quasiperiodic sequence

An a posteriori (off-line) approach to solving the problem of maximum-likelihood detection of a recurring tuple containing reference fragments in a numerical quasiperiodic sequence is studied. The case is analyzed where (1) the total number of fragments in a sequence is unknown; (2) the index of a sequence term corresponding to the beginning of a fragment is a deterministic (not random) value; (3) a sequence distorted by additive uncorrelated Gaussian noise is available for observation. It is shown that the problem under consideration is reduced to testing a set of simple hypotheses about the mean of a random Gaussian vector. The cardinality of this totality grows exponentially as the vector dimension (i.e., the length of the sequence under study) increases. It is established that searching for a maximum-likelihood hypothesis is equivalent to finding arguments that yield a maximum for an auxiliary objective function. It is shown that maximizing the objective function reduces to solving a special optimization problem, which is proved to be solvable in polynomial time. An exact algorithm for solving this problem, which underlies the optimal (maximum-likelihood) detection algorithm for a recurring tuple, is substantiated. The kernel of the exact algorithm is an algorithm for solving a special (basic) optimization problem. Results of numerical simulations are presented.     

Finite iterative algorithms for a common solution to a group of complex matrix equations

An iterative algorithm is constructed to give a common solution to a group of complex matrix equations. By using the proposed algorithm, the existence of a common solution can be determined automatically. When a common solution exists for this group of matrix equations, it is proven by using a real inner product in complex matrix spaces as a tool that a solution can be obtained within finite iteration steps for any initial values in the absence of round-off errors. The algorithm is also generalized to solve a more general case. A numerical example is given to illustrate the effectiveness of the proposed method.     

Theorem of learning for a competition algorithm

This paper is an extension of [1], where a new decisive algorithm was proposed. In its operation, the unit resembles artificial neural networks. However, the functioning of the algorithm proposed is based on different concepts. It does not use the concept of a net or a neuron. The theorem of learning for the new competition algorithm is proved.     

An algorithm for maximizing a convex function over a simple set

The problem of maximizing a convex function on a so-called simple set is considered. Based on the optimality conditions [19], an algorithm for solving the problem is proposed. This numerical algorithm is shown to be convergent. The proposed algorithm has been implemented and tested on a variety of test problems.     

Strong convergence analysis of a hybrid algorithm for nonlinear operators in a Banach space

In this paper, a hybrid algorithm is investigated for an asymptotically quasi-$\phi$-nonexpansive mapping in the intermediate sense and a bifunction. Strong convergence of the algorithm is obtained in a strictly convex, smooth and reflexive Banach space.     

An algorithm for a special case of a generalization of the Richardson extrapolation process

Summary A special case of a generalization of the Richardson extrapolation process is considered, and its complete solution is given in closed form. Using this, an algorithm for implementing the extrapolation is devised. It is shown that this algorithm needs a very small amount of arithmetic operations and very little storage. Convergence and stability properties for some cases are also considered.