A Dynamic Programming Algorithm for the κ-Haplotyping Problem

The Minimum Fragments Removal （MFR） problem is one of the haplotyping problems： given a set of fragments, remove the minimum number of fragments so that the resulting fragments can be partitioned into k classes of non-conflicting subsets. In this paper, we formulate the κ-MFR problem as an integer linear programming problem, and develop a dynamic programming approach to solve the κ-MFR problem for both the gapless and gap eases.     

求解$P_*(\kappa)$阵线性互补问题的宽邻域Dikin型高阶内点算法

Based on the idea of Dikin-type primal-dual affine scaling method for linear programming, we describe a high-order Dikin-type algorithm for P. （κ）-matrix linear complementarity problem in a wide neighborhood of the central path, and its polynomial-time complexity bound is given. Finally, two numerical experiments are provided to show the effectiveness of the proposed algorithms.     

MULTI-PARAMETER TIKHONOV REGULARIZATION FOR LINEAR ILL-POSED OPERATOR EQUATIONS

We consider solving linear ill-posed operator equations. Based on a multi-scale decomposition for the solution space, we propose a multi-parameter regularization for solving the equations. We establish weak and strong convergence theorems for the multi-parameter regularization solution. In particular, based on the eigenfunction decomposition, we develop a posteriori choice strategy for multi-parameters which gives a regularization solution with the optimal error bound. Several practical choices of multi-parameters are proposed. We also present numerical experiments to demonstrate the outperformance of the multiparameter regularization over the single parameter regularization.     

ALTERNATING PROJECTION BASED PREDICTION-CORRECTION METHODS FOR STRUCTURED VARIATIONAL INEQUALITIES

The monotone variational inequalities Ⅵ(Ω,F)have vast applications, including opti-mal controls and convex programming.In this paper we focus on the Ⅵ problems thathave a particular splitting structure and in which the mapping F does not have an explicitform,therefore only its function values can be employed in the numerical methods for solv-ing such problems.We study a set of numerical methods that are easily implementable.Each iteration of the proposed methods consists of two procedures.The first(prediction)procedure utilizes alternating projections to produce a predictor.The second(correction)procedure generates the new iterate via some minor computations.Convergence of theproposed methods is proved under mild conditions.Preliminary numerical experiments forsome traffic equilibrium problems illustrate the effectiveness of the proposed methods.     

解线约束凸规划的势下降算法

A potential reduction algorithm is proposed for optimization of a convex function subject to linear constraints. At each step of the algorithm,a system of linear equations is solved toget a search direction and the Armijo‘s rule is used to determine a stepsize. It is proved that thealgorithm is globally convergent. Computational results are reported.     

A SUPERLINEARLY CONVERGENT TRUST REGION ALGORITHM FOR LC^1 CONSTRAINED OPTIMIZATION PROBLEMS

In this paper, a new trust region algorithm for nonlinear equality constrained LC^1 optimization problems is given. It obtains a search direction at each iteration not by solving a quadratic programming subproblem with a trust region bound, but by solving a system of linear equations. Since the computational complexity of a QP-Problem is in general much larger than that of a system of linear equations, this method proposed in this paper may reduce the computational complexity and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and super-linearly convergent to a solution of the original problem. Some numerical examples are reported, showing the proposed algorithm can be beneficial from a computational point of view.     

Generalized K-T conditions and penalty functions for quasidifferentiable programming

In this paper,a quasidifferentiable programming problem with inequality constraintsis considered. First,a general form of optimality conditions for this problem is glven,which contains the results of Luderer,Kuntz and Scholtes. Next,a new generalized K-T condition is derived. The new optimality condition doesn‘t use Luderer‘s regularity assumption and ita Lagrangian multipliers don‘t depend on the particular elements in the superdifferentials of the object function and constraint functions, Finally,a penalty function for the prohlem is studied. Sufficient conditions of the penalty function attaining a global minimum are obtained.     

一类非单调线性互补问题的高阶仿射尺度算法

In this paper, a new interior point algorithm-high-order atone scaling for a class of nonmonotonic linear complementary problems is developed. On the basis of idea of primal-dual affine scaling method for linear programming , the search direction of our algorithm is obtained by a linear system of equation at each step . We show that, by appropriately choosing the step size, the algorithm has polynomial time complexity. We also give the numberical results of the algorithm for two test problems.     

DATA PREORDERING IN GENERALIZED PAV ALGORITHM FOR MONOTONIC REGRESSION

Monotonic regression （MR） is a least distance problem with monotonicity constraints induced by a partiaily ordered data set of observations. In our recent publication [In Ser. Nonconvex Optimization and Its Applications, Springer-Verlag, （2006） 83, pp. 25-33], the Pool-Adjazent-Violators algorithm （PAV） was generalized from completely to partially ordered data sets （posets）. The new algorithm, called CPAV, is characterized by the very low computational complexity, which is of second order in the number of observations. It treats the observations in a consecutive order, and it can follow any arbitrarily chosen topological order of the poset of observations. The CPAV algorithm produces a sufficiently accurate solution to the MR problem, but the accuracy depends on the chosen topological order. Here we prove that there exists a topological order for which the resulted CPAV solution is optimal. Furthermore, we present results of extensive numerical experiments, from which we draw conclusions about the most and the least preferable topological orders.     

A NEW FILLED FUNCTION METHOD FOR INTEGER PROGRAMMING

The Filled Function Method is a class of effective algorithms for continuous globaloptimization.In this paper,a new filled function method is introduced and used to solveinteger programming.Firstly,some basic definitions of discrete optimization are given.Then an algorithm and the implementation of this algorithm on several test problems areshowed.The computational results show the algorithm is effective.     

GLOBAL WEAK SHARP MINIMA AND COMPLETENESS OF METRIC SPACE

A sufficient condition on the existence of a global weak sharp minima for general function in metric space is established. A characterization for convex function to have global weak sharp minima is also presented, which generalized Burke and Ferris‘ result to infinite dimensional space. A characterization of the completeness of a metric space is given by the existence of global weak sharp minima.     

CONVERGENCE OF A MIXED FINITE ELEMENT FOR THE STOKES PROBLEM ON ANISOTROPIC MESHES

The main aim of this paper is to study the convergence properties of a low order mixed finite element for the Stokes problem under anisotropic meshes. We discuss the anisotropic convergence and superconvergence independent of the aspect ratio. Without the shape regularity assumption and inverse assumption on the meshes, the optimal error estimates and natural superconvergence at central points are obtained. The global superconvergence for the gradient of the velocity and the pressure is derived with the aid of a suitable postprocessing method. Furthermore, we develop a simple method to obtain the superclose properties which improves the results of the previous works .     

Connectedness of Cone-Efficient Solution Set for Cone-Quasiconvex Multiobjective Programming in Locally Convex Spaces

This paper deals with the connectedness of the cone-efficient solution set for vector optimization inlocally convex Hausdorff topological vector spaces.The connectedness of the cone-efficient solution set is provedfor multiobjective programming defined by a continuous cone-quasiconvex mapping on a compact convex set ofalternatives.The generalized saddle theorem plays a key role in the proof.     

无约束全局优化的一个可调参数的填充函数

A filled function with adjustable parameters is suggested in this paper for finding a global minimum point of a general class of nonlinear programming problems with a bounded and closed domain. This function has two adjustable parameters. We will discuss the properties of the proposed filled function. Conditions on this function and on the values of parameters are given so that the constructed function has the desired properties of traditional filled function.     

具有V-不变凸的多目标规划的另一种方法

In this paper, optimality conditions for multiobjective programming problems having V-invex objective and constraint functions are considered. An equivalent multiobjective programming problem is constructed by a modification of the objective function.Furthermore, a (α, η)-Lagrange function is introduced for a constructed multiobjective programming problem, and a new type of saddle point is introduced. Some results for the new type of saddle point are given.     

EXPONENTIAL CONVERGENCE OF SAMPLE AVERAGE APPROXIMATION METHODS FOR A CLASS OF STOCHASTIC MATHEMATICAL PROGRAMS WITH COMPLEMENTARITY CONSTRAINTS

In this paper,we propose a Sample Average Approximation(SAA)method for a class ofStochastic Mathematical Programs with Complementarity Constraints(SMPCC)recentlyconsidered by Birbil,Gürkan and Liste[3].We study the statistical properties of obtainedSAA estimators.In particular we show that under moderate conditions a sequence of weakstationary points of SAA programs converge to a weak stationary point of the true problemwith probability approaching one at exponential rate as the sample size tends to infinity.To implement the SAA method more efficiently,we incorporate the method with sometechniques such as Scholtes' regularization method and the well known smoothing NCPmethod.Some preliminary numerical results are reported.     

A TRANSFORMATION PATH ALGORITHM FOR UNCONSTRAINED SIGNOMIAL GEOMETRIC PROGRAMMING

In this paper we present a transformation path algorithm for UnconstrainedSignomial Geometric Programming (USGP). The algorithm is proposed from a newpoint of view based on exploring the characteristics of USGP problem. Firstly by somestable transformations, a particular subproblem is derived which is very easy to solve.Secondly, a special path is formed conveniently. And then the step of the algorithmconsists in finding a “good” point to the current iterate by choosing it along the specialpath and within a trust region. It is proved that the algorithm is globally convergent.     

A TRUST REGION METHOD WITH A CONIC MODEL FOR NONLINEARLY CONSTRAINED OPTIMIZATION

Trust region methods are powerful and effective optimization methods.The conic model method is a new type of method with more information available at each iteration than standard quadratic-based methods.The advantages of the above two methods can be combined to form a more powerful method for constrained optimization.The trust region subproblem of our method is to minimize a conic function subject to the linearized constraints and trust region bound.At the same time,the new algorithm still possesses robust global properties.The global convergence of the new algorithm under standard conditions is established.     

Approximation Algorithm for MAX DICUT with Given Sizes of Parts

Given a directed graph G and an edge weight function w : A(G)→ R^ , the maximum directed cut problem (MAX DICUT) is that of finding a directed cut δ(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut δ(S) having maximum weight over all cuts δ(S) with |S| -- k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.     

SOME EXTENDED KNAPSACK PROBLEMS INVOLVING JOB PARTITION BETWEEN TWO PARTIES

Some novel applications and pragmatic variations of knapsack problem(KP)are presented and constructed,which are formulated and developed from a model initiated in this paper on profit allocation from partition of jobs in terms of two-person discrete cooperation game.