Misclassification minimization

The problem of minimizing the number of misclassified points by a plane, attempting to separate two point sets with intersecting convex hulls inn-dimensional real space, is formulated as a linear program with equilibrium constraints (LPEC). This general LPEC can be converted to an exact penalty problem with a quadratic objective and linear constraints. A Frank-Wolfe-type algorithm is proposed for the penalty problem that terminates at a stationary point or a global solution. Novel aspects of the approach include: (i) A linear complementarity formulation of the step function that counts misclassifications, (ii) Exact penalty formulation without boundedness, nondegeneracy or constraint qualification assumptions, (iii) An exact solution extraction from the sequence of minimizers of the penalty function for a finite value of the penalty parameter for the general LPEC and an explicitly exact solution for the LPEC with uncoupled constraints, and (iv) A parametric quadratic programming formulation of the LPEC associated with the misclassification minimization problem.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9101801 and CDA-9024618.     

A global optimization approach for the linear two-level program

Linear two-level programming deals with optimization problems in which the constraint region is implicity determined by another optimization problem. Mathematical programs of this type arise in connection with policy problems to which the Stackelberg leader-follower game is applicable. In this paper, the linear two-level programming problem is restated as a global optimization problem and a new solution method based on this approach is developed. The most important feature of this new method is that it attempts to take full advantage of the structure in the constraints using some recent global optimization techniques. A small example is solved in order to illustrate the approach.The paper was completed while this author was visiting the Department of Mathematics of Linköping University.     

求线性比试和问题的确定性全局优化算法

为求线性比试和问题的全局最优解,本文给出了一个分支定界算法.通过一个等价问题和一个新的线性化松弛技巧,初始的非凸规划问题归结为一系列线性规划问题的求解.借助于这一系列线性规划问题的解,算法可收敛于初始非凸规划问题的最优解.算法的计算量主要是一些线性规划问题的求解.数值算例表明算法是切实可行的.     

模糊线性规划问题的一种新的单纯形算法

提出求解模糊线性规划问题的一种新的思路 ,就是应用单纯形法先求解与 (FLP)相应的普通线性规划问题 ,通过模糊约束集与模糊目标集的隶属度的比较 ,获得两个集合交集的最优隶属度 ,将此最优隶属度代入最优单纯形表中 ,即可求得 (FLP)的解。本算法只需在一张适当的迭代表台上执行单纯形迭代过程 ,简捷方便适用     

下层以最优值反应上层的两层线性规则

本文证明了下层以最优值反应上层的两层线性规划可转化为一线性Max-min问题，进而得出其与一双线性规划问题等价。基于此结论可以讨论这种特殊两层问题的几何性质，最优性条件及算法设计。     

An applicable method for solving the shortest path problems

A theorem of Hardy, Littlewood, and Polya, first time is used to find the variational form of the well known shortest path problem, and as a consequence of that theorem, one can find the shortest path problem via quadratic programming. In this paper, we use measure theory to solve this problem. The shortest path problem can be written as an optimal control problem. Then the resulting distributed control problem is expressed in measure theoretical form, in fact an infinite dimensional linear programming problem. The optimal measure representing the shortest path problem is approximated by the solution of a finite dimensional linear programming problem.     

A practicable branch-and-bound algorithm for globally solving linear multiplicative programming

To globally solve linear multiplicative programming problem (LMP), this paper presents a practicable branch-and-bound method based on the framework of branch-and-bound algorithm. In this method, a new linear relaxation technique is proposed firstly. Then, the branch-and-bound algorithm is developed for solving problem LMP. The proposed algorithm is proven that it is convergent to the global minimum by means of the subsequent solutions of a series of linear programming problems. Some experiments are reported to show the feasibility and efficiency of this algorithm.     

A trust region algorithm for solving bilevel programming problems

In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem.     

修正的模糊最小一乘线性回归

对文献[1]提出的基于对称三角模糊数的模糊最小一乘线性回归进行修正和扩展,给出模糊最小一乘线性回归模型的三种不同形式,并将其转化为线性规划或非线性规划问题进行求解。最后,给出几个数值实例,通过计算和比较,结果表明三种模糊最小一乘线性回归模型都具有非常好的拟合性。     

A procedure for one-parametric linear programming

A procedure is proposed for the parametric linear programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The solution vector and the optimum value are determined explicitly as rational functions of the parameter. In addition to standard linear programming technique, only the determination of eigenvalues is required. The procedure is compared to those by Dinkelbach and Zsigmond, and a numerical example is given.     

Disjunctive cuts for continuous linear bilevel programming

This work shows how disjunctive cuts can be generated for a bilevel linear programming problem (BLP) with continuous variables. First, a brief summary on disjunctive programming and bilevel programming is presented. Then duality theory is used to reformulate BLP as a disjunctive program and, from there, disjunctive programming results are applied to derive valid cuts. These cuts tighten the domain of the linear relaxation of BLP. An example is given to illustrate this idea, and a discussion follows on how these cuts may be incorporated in an algorithm for solving BLP.     

On an optimal shape design problem to control a thermoelastic deformation under a prescribed thermal treatment

A shape optimization problem concerned with thermal deformation of elastic bodies is considered. In this article, measure theory approach in function space is derived, resulting in an effective algorithm for the discretized optimization problem. First the problem is expressed as an optimal control problem governed by variational forms on a fixed domain. Then by using an embedding method, the class of admissible shapes is replaced by a class of positive Borel measures. The optimization problem in measure space is then approximated by a linear programming problem. The optimal measure representing optimal shape is approximated by the solution of this finite-dimensional linear programming problem. Numerical examples are also given.     

Linear programming in measure spaces

This paper studies a linear programming problem in measure spaces (LPM). Several results are obtained. First, the optimal value of LPM can be equal to the optimal value of the dual problem (DLPM), but the solution of DLPM may be not exist in its feasible region. Sccond, :he relations between the optimal solution of LPM and the extreme point of the feasible region of LPM are discussed. In order to investigate the conditions under which a feasible solution becomes an extremal point, the inequality constraint of LPM is transformed to an equality constraint. Third, the LPM can be reformulated to be a general capacity problem (GCAP) or a linear semi-infinite programming problem (LSIP = SIP), and under appropriate restrictioiis, the algorithm developed by the authors in [7] and [8] are applicable for developing an approximation scheme for the optimal solution of LPM     

The simplex method as a global optimizer: A c-programming perspective

In this paper we give a brief account of the important role that the conventional simplex method of linear programming can play in global optimization, focusing on its collaboration with composite concave programming techniques. In particular, we demonstrate how rich and powerful the c-programming format is in cases where its parametric problem is a standard linear programming problem.     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

On Linear Fractional Programming Problem and its Computation Using a Neural Network Model

In this paper we consider linear fractional programming problem and look at its linear complementarity formulation. In the literature, uniqueness of solution of a linear fractional programming problem is characterized through strong quasiconvexity. We present another characterization of uniqueness through complementarity approach and show that the solution set of a fractional programming problem is convex. Finally we formulate the complementarity condition as a set of dynamical equations and prove certain results involving the neural network model. A computational experience is also reported.      

求一类非凸规划问题全局解的确定性算法

本文对一类非凸规划问题(NP)给出一确定性全局优化算法.这类问题包括:在非凸的可行域上极小化有限个带指数的线性函数乘积的和与差,广义线性多乘积规划,多项式规划等.通过利用等价问题和线性化技巧提出的算法收敛到问题(NP)的全局极小.     

Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

Symmetrized-lexicographic order and the method of points

A variant of lexicographic order called symmetrized-lexicographic order is defined. The symmetrized-lexicographic order finds its application in the goal programming procedure called the method of points. The symmetrized-lexicographic order is shown to be representable using linear algebra and, thus, the method of points can be implemented as a linear programming problem.