A Chance Constrained Approach to Fractional Programming with Random Numerator

This paper presents a chance constrained programming approach to the problem of maximizing the ratio of two linear functions of decision variables which are subject to linear inequality constraints. The coefficient parameters of the numerator of the objective function are assumed to be random variables with a known multivariate normal probability distribution. A deterministic equivalent of the stochastic linear fractional programming formulation has been obtained and a subsidiary convex program is given to solve the deterministic problem.     

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

Interior point algorithms for linear programming with inequality constraints

Interior methods for linear programming were designed mainly for problems formulated with equality constraints and non-negative variables. The formulation with inequality constraints has shown to be very convenient for practical implementations, and the translation of methods designed for one formulation into the other is not trivial. This paper relates the geometric features of both representations, shows how to transport data and procedures between them and shows how cones and conical projections can be associated with inequality constraints.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

交替方向法求解带线性约束的变分不等式

１引言变分不等式是一个有广泛应用的数学问题,它的一般形式是：确定一个向量,使其满足这里ｆ是一个从到自身的一个映射,Ｓ是Ｒ中的一个闭凸集．在许多实际问题中集合Ｓ往往具有如下结构其中ＡｂＫ是中的一个简单闭凸集．例如一个正卦限,一个框形约束结构,或者一个球简言之,Ｓ是Ｒ中的一个超平面与一个简单闭凸集的交．求解问题（１）－（２）,往往是通过对线性约束Ａ引人Ｌａｇｒａｎｇｅ乘子,将原问题化为如下的变分不等式：确定使得我们记问题（３）－（４）为ＶＩ（Ｆ）．熟知［３］,ＶＩ（,Ｆ）等价于投影方程其中凡（·）表…     

A nonlinear interval number programming method for uncertain optimization problems

In this paper, a method is suggested to solve the nonlinear interval number programming problem with uncertain coefficients both in nonlinear objective function and nonlinear constraints. Based on an order relation of interval number, the uncertain objective function is transformed into two deterministic objective functions, in which the robustness of design is considered. Through a modified possibility degree, the uncertain inequality and equality constraints are changed to deterministic inequality constraints. The two objective functions are converted into a single-objective problem through the linear combination method, and the deterministic inequality constraints are treated with the penalty function method. The intergeneration projection genetic algorithm is employed to solve the finally obtained deterministic and non-constraint optimization problem. Two numerical examples are investigated to demonstrate the effectiveness of the present method.     

Reducing quadratic programming problem to regression problem: Stepwise algorithm

Quadratic programming is concerned with minimizing a convex quadratic function subject to linear inequality constraints. The variables are assumed to be nonnegative. The unique solution of quadratic programming (QP) problem (QPP) exists provided that a feasible region is non-empty (the QP has a feasible space).A method for searching for the solution to a QP is provided on the basis of statistical theory. It is shown that QPP can be reduced to an appropriately formulated least squares (LS) problem (LSP) with equality constraints and nonnegative variables. This approach allows us to obtain a simple algorithm to solve QPP. The applicability of the suggested method is illustrated with numerical examples.     

NP-hardness of linear multiplicative programming and related problems

The linear multiplicative programming problem minimizes a product of two (positive) variables subject to linear inequality constraints. In this paper, we show NP-hardness of linear multiplicative programming problems and related problems.     

A unified framework for linear control problems with state-variable inequality constraints

This paper briefly reviews the literature on necessary optimality conditions for optimal control problems with state-variable inequality constraints. Then, it attempts to unify the treatment of linear optimal control problems with state-variable inequality constraints in the framework of continuous linear programming. The duality theory in this framework makes it possible to relate the adjoint variables arising in different formulations of a problem; these relationships are illustrated by the use of a simple example. This framework also allows more general problems and admits a simplex-like algorithm to solve these problems.This research was partially supported by Grant No. A4619 from the National Research Council of Canada to the first author. The first author also acknowledges the support provided by the Brookhaven National Laboratory, where he conducted his research.     

A partitioning and bounded variable algorithm for linear programming

An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex method followed by the dual simplex method for bounded variables. In contrast to the two-phase method and the big M method, the PBVA does not introduce artificial variables. In the PBVA, a reduced linear program is formed by eliminating as many variables as there are equality constraints. A subproblem containing one ‘less than or equal to’ constraint is solved by executing the simplex method modified such that an upper bound is placed on an unbounded entering variable. The remaining constraints of the reduced problem are added to the optimal tableau of the subproblem to form an augmented tableau, which is solved by applying the dual simplex method for bounded variables. Lastly, the variables that were eliminated are restored by substitution. Differences between the PBVA and two other variants of the simplex method are identified. The PBVA is applied to solve an example problem with five decision variables, two equality constraints, and two inequality constraints. In addition, three other types of linear programming problems are solved to justify the advantages of the PBVA.