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.     

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.      

求解弱线性双层规划问题的一种全局优化方法

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.     

二次半定规划问题及其投影收缩算法

In this paper,we discuss the relations among the quadratic semi-definite programming problem,the linear semi-definite porgramming and the linearquadratic semi-definite programming problem.The duality theories are presented.After proving the equivalence of its optimality conditions and monotonous linear variational inequalities,we use the projection and contraction algorithms to solve(QSDP),We present the algorithms and its convergence analysis.     

带惩罚的容错设施布局问题的近似算法

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.     

The theory of linear programming:skew symmetric self-dual problems and the central path *

The literature in the field of interior point methods for linear programming has been almost exclusively algorithm oriented. Recently Güler, Roos, Terlaky and Vial presented a complete duality theory for linear programming based on the interior point approach. In this paper we present a more simple approach which is based on an embedding of the primal problem and its dual into a skew symmetric self-dual problem. This embedding is essentially due Ye, Todd and Mizuno

First we consider a skew symmetric self-dual linear program. We show that the strong duality theorem trivally holds in this case. Then, using the logarithmic barrier problem and the central path, the existence of a strictly complementary optimal solution is proved. Using the embedding just described, we easily obtain the strong duality theorem and the existence of strictly complementary optimal solutions for general linear programming problems     

On robust duality for fractional programming with uncertainty data

In this paper, we present a duality theory for fractional programming problems in the face of data uncertainty via robust optimization. By employing conjugate analysis, we establish robust strong duality for an uncertain fractional programming problem and its uncertain Wolfe dual programming problem by showing strong duality between the deterministic counterparts: robust counterpart of the primal model and the optimistic counterpart of its dual problem. We show that our results encompass as special cases some programming problems considered in the recent literature. Moreover, we also show that robust strong duality always holds for linear fractional programming problems under scenario data uncertainty or constraint-wise interval uncertainty, and that the optimistic counterpart of the dual is tractable computationally.     

Bounds for codes by semidefinite programming

Delsarte’s method and its extensions allow one to consider the upper bound problem for codes in two-point homogeneous spaces as a linear programming problem with perhaps infinitely many variables, which are the distance distribution. We show that using as variables power sums of distances, this problem can be considered as a finite semidefinite programming problem. This method allows one to improve some linear programming upper bounds. In particular, we obtain new bounds of one-sided kissing numbers.     

Using the Dinkelbach-type algorithm to solve the continuous-time linear fractional programming problems

A Dinkelbach-type algorithm is proposed in this paper to solve a class of continuous-time linear fractional programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.     

Using the parametric approach to solve the continuous-time linear fractional max–min problems

A numerical algorithm based on parametric approach is proposed in this paper to solve a class of continuous-time linear fractional max-min programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as a parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this algorithm.     

Fuzzy Multi-fractional Programming for Land Use Planning in Agricultural Production System

In this paper, we present a multi-objective linear fractional programming (MOLFP) approach for multi-objective linear fuzzy goal programming (MOLFGP) problem. Here, we consider a problem in which a set of pair of goals are optimized in ratio rather than optimizing them individually. In particular, we consider the optimization of profit to cash expenditure and crop production in various seasons to land utilization as a fractional objectives and used remaining goals in its original form. Further, the goals set in agricultural production planning are conflicting in nature; thus we use the concept of conflict and nonconflict between goals for computation of appropriate aspiration level. The method is illustrated on a problem of agricultural production system for comparison with Biswas and Pal [1] method to show its suitability.     

Direct newton method for a linear problem of semidefinite programming

We consider a linear problem of semidefinite programming. To solve this problem, we propose a direct Newton method, which is a generalization of the direct barrier-Newton method for problems of linear programming. We study properties of the method and prove its local convergence.     

An approach for solving nonlinear programming problems

In this paper we use measure theory to solve a wide range of the nonlinear programming problems. First, we transform a nonlinear programming problem to a classical optimal control problem with no restriction on states and controls. The new problem is modified into one consisting of the minimization of a special linear functional over a set of Radon measures; then we obtain an optimal measure corresponding to functional problem which is then approximated by a finite combination of atomic measures and the problem converted approximately to a finite-dimensional linear programming. Then by the solution of the linear programming problem we obtain the approximate optimal control and then, by the solution of the latter problem we obtain an approximate solution for the original problem. Furthermore, we obtain the path from the initial point to the admissible solution.     

A cutting plane method for bilevel linear programming with interval coefficients

This article considers the bilevel linear programming problem with interval coefficients in both objective functions. We propose a cutting plane method to solve such a problem. In order to obtain the best and worst optimal solutions, two types of cutting plane methods are developed based on the fact that the best and worst optimal solutions of this kind of problem occur at extreme points of its constraint region. The main idea of the proposed methods is to solve a sequence of linear programming problems with cutting planes that are successively introduced until the best and worst optimal solutions are found. Finally, we extend the two algorithms proposed to compute the best and worst optimal solutions of the general bilevel linear programming problem with interval coefficients in the objective functions as well as in the constraints.     

Using convex envelopes to solve the interactive fixed-charge linear programming problem

In the well-known fixed-charge linear programming problem, it is assumed, for each activity, that the value of the fixed charge incurred when the level of the activity is positive does not depend upon which other activities, if any, are also undertaken at a positive level. However, we have encountered several practical problems where this assumption does not hold. In an earlier paper, we developed a new problem, called the interactive fixed-charge linear programming problem (IFCLP), to model these problems. In this paper, we show how to construct the convex envelopes and other convex underestimating functions for the objective function for problem (IFCLP) over various rectangular subsets of its domain. Using these results, we develop a specialized branch-and-bound algorithm for problem (IFCLP) which finds an exact optimal solution for the problem in a finite number of steps. We also discuss the main properties of this algorithm.The authors would like to thank an anonymous referee for his helpful suggestions.     

一个新的解线性规划的神经网络

本文提出一个新的解线性规划的Hopfields-型网络。该网络基于线性规划的对偶理论,并使用了Sigmoid函数,但不需要预先给定的罚参数和乘法模拟器,我们证明该网络不仅全局收敛到线性规划的精确解,而且能同时解原规划和对偶规划。由于在该网络中没有使用乘法模拟器而利用了Sigmoid函数,因此该模型是很容易用硬件实现的。     

On computational methods for solutions of multiobjective linear production programming games

In this paper we consider a production model in which multiple decision makers pool resources to produce finished goods. Such a production model, which is assumed to be linear, can be formulated as a multiobjective linear programming problem. It is shown that a multi-commodity game arises from the multiobjective linear production programming problem with multiple decision makers and such a game is referred to as a multiobjective linear production programming game. The characteristic sets in the game can be obtained by finding the set of all the Pareto extreme points of the multiobjective programming problem. It is proven that the core of the game is not empty, and points in the core are computed by using the duality theory of multiobjective linear programming problems. Moreover, the least core and the nucleolus of the game are examined. Finally, we consider a situation that decision makers first optimize their multiobjective linear production programming problem and then they examine allocation of profits and/or costs. Computational methods are developed and illustrative numerical examples are given.     

线性半向量二层规划问题的全局优化方法

研究了线性半向量二层规划问题的全局优化方法. 利用下层问题的对偶间隙构造了线性半向量二层规划问题的罚问题, 通过分析原问题的最优解与罚问题可行域顶点之间的关系, 将线性半向量二层规划问题转化为有限个线性规划问题, 从而得到线性半向量二层规划问题的全局最优解. 数值结果表明所设计的全局优化方法对线性半向量二层规划问题是可行的.     

Robust Duality for Fractional Programming Problems with Constraint-Wise Data Uncertainty

In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex–concave fractional program and the optimistic counterpart of its conventional Wolfe dual program with uncertain parameters. For linear fractional programming problems with constraint-wise interval uncertainty, we show that the dual of the robust counterpart is the optimistic counterpart in the sense that they are equivalent. Our results show that a worst-case solution of an uncertain fractional program (i.e., a solution of its robust counterpart) can be obtained by solving a single deterministic dual program. In the case of a linear fractional programming problem with interval uncertainty, such solutions can be found by solving a simple linear program.     

On strong optimality of interval linear programming

We consider a linear programming problem with interval data. We discuss the problem of checking whether a given solution is optimal for each realization of interval data. This problem was studied for particular forms of linear programming problems. Herein, we extend the results to a general model and simplify the overall approach. Moreover, we inspect computational complexity, too. Eventually, we investigate a related optimality concept of semi-strong optimality, showing its characterization and complexity.