Farkas’ lemma for separable sublinear inequalities without qualifications

We show that the celebrated Farkas lemma for linear inequality systems continues to hold for separable sublinear inequality systems. As a consequence, we establish a qualification-free characterization of optimality for separable sublinear programming problems which include classes of robust linear programming problems. We also deduce that the Lagrangian duality always holds for these programming problems without qualifications.     

Dual Semidefinite Programs Without Duality Gaps for a Class of Convex Minimax Programs

In this paper, we introduce a new dual program, which is representable as a semidefinite linear programming problem, for a primal convex minimax programming problem, and we show that there is no duality gap between the primal and the dual whenever the functions involved are sum-of-squares convex polynomials. Under a suitable constraint qualification, we derive strong duality results for this class of minimax problems. Consequently, we present applications of our results to robust sum-of-squares convex programming problems under data uncertainty and to minimax fractional programming problems with sum-of-squares convex polynomials. We obtain these results by first establishing sum-of-squares polynomial representations of non-negativity of a convex max function over a system of sum-of-squares convex constraints. The new class of sum-of-squares convex polynomials is an important subclass of convex polynomials and it includes convex quadratic functions and separable convex polynomials. The sum-of-squares convexity of polynomials can numerically be checked by solving semidefinite programming problems whereas numerically verifying convexity of polynomials is generally very hard.     

Linear Programming with Special Ordered Sets

Concave objective functions which are both piecewise linear and separable are often encountered in a wide variety of management science problems. Provided the constraints are linear, problems of this kind are normally forced into a linear programming mould and solved using the simplex method. This paper takes another look at the associated linear programs and shows that they have special structural features which are not exploited by the simplex algorithm. It suggests that their variables can be divided into special ordered sets which can then be used to guide the pivoting strategies of the simplex algorithm with a resultant reduction in basis changes.     

A group of knowledge-incorporated multiple criteria linear programming classifiers

Classification is a main data mining task, which aims at predicting the class label of new input data on the basis of a set of pre-classified samples. Multiple criteria linear programming (MCLP) is used as a classification method in the data mining area, which can separate two or more classes by finding a discriminate hyperplane. Although MCLP shows good performance in dealing with linear separable data, it is no longer applicable when facing with nonlinear separable problems. A kernel-based multiple criteria linear programming (KMCLP) model is developed to solve nonlinear separable problems. In this method, a kernel function is introduced to project the data into a higher-dimensional space in which the data will have more chance to be linear separable. KMCLP performs well in some real applications. However, just as other prevalent data mining classifiers, MCLP and KMCLP learn only from training examples. In the traditional machine learning area, there are also classification tasks in which data sets are classified only by prior knowledge, i.e. expert systems. Some works combine the above two classification principles to overcome the faults of each approach. In this paper, we provide our recent works which combine the prior knowledge and the MCLP or KMCLP model to solve the problem when the input consists of not only training examples, but also prior knowledge. Specifically, how to deal with linear and nonlinear knowledge in MCLP and KMCLP models is the main concern of this paper. Numerical tests on the above models indicate that these models are effective in classifying data with prior knowledge.     

A comparative analysis of linear fitting for non-linear functions on optimization: A case study: Air pollution problems

A very frequent problem in advanced mathematical programming models is the linear approximation of convex and non-convex non-linear functions in either the constraints or the objective function of an otherwise linear programming problem. In this paper, based on a model that has been developed for the evaluation and selection of pollutant emission control policies and standards, we shall study several ways of representing non-linear functions of a single argument in mixed integer, separable and related programming terms. Thus we shall study the approximations based on piecewise constant, piecewise adjacent, piecewise non-adjacent additional and piecewise non-adjacent segmented functions. In each type of modelization we show the problem size and optimization results of using the following techniques: separable programming, mixed integer programming with Special Ordered Sets of type 1, linear programming with Special Ordered Sets of type 2 and mixed integer programming using strategies based on the quasi-integrality of the binary variables.     

A global optimization method for nonconvex separable programming problems

Conventional methods of solving nonconvex separable programming (NSP) problems by mixed integer programming methods requires adding numerous 0–1 variables. In this work, we present a new method of deriving the global optimum of a NSP program using less number of 0–1 variables. A separable function is initially expressed by a piecewise linear function with summation of absolute terms. Linearizing these absolute terms allows us to convert a NSP problem into a linearly mixed 0–1 program solvable for reaching a solution which is extremely close to the global optimum.     

Reformulation of mathematical programming problems as linear complementarity problems and investigation of their solution methods

A family of complementarity problems is defined as extensions of the well-known linear complementarity problem (LCP). These are:

The Evolution of Mathematical Programming Systems

Computer programs to solve linear programming problems by the simplex method have existed since the early 1950s. They remain the central feature of today's mathematical programming systems. There has been a steady increase in the size of problem that can be solved: this has been due as much to a better understanding of how to exploit sparseness as to larger and faster computers. There has been a steady increase in the type of problem that can be solved: this has been due as much to new concepts, such as separable programming, integer variables and special ordered sets, as to new algorithms. There has been a steady increase in the extent to which the application of mathematical programming has become more automatic. This applies both to the use of computerized matrix generators and report writers and to the mathematical formulation itself, in that we rely less on the user producing a well-scaled linear programming problem and are starting on the process of automatically sharpening the formulation of integer programming problems.Important new work is being done on all these aspects of computational mathematical programming.     

Dual multilevel optimization

We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilevel implementation of the Dual Active Set algorithm is compared with CPLEX Simplex and Barrier codes using Netlib linear programming test problems.      

Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations

In this paper we present necessary conditions for global optimality for polynomial problems with box or bivalent constraints using separable polynomial relaxations. We achieve this by first deriving a numerically checkable characterization of global optimality for separable polynomial problems with box as well as bivalent constraints. Our necessary optimality conditions can be numerically checked by solving semi-definite programming problems. Then, by employing separable polynomial under-estimators, we establish sufficient conditions for global optimality for classes of polynomial optimization problems with box or bivalent constraints. We construct underestimators using the sum of squares convex (SOS-convex) polynomials of real algebraic geometry. An important feature of SOS-convexity that is generally not shared by the standard convexity is that whether a polynomial is SOS-convex or not can be checked by solving a semidefinite programming problem. We illustrate the versatility of our optimality conditions by simple numerical examples.     

A Finite Algorithm for Global Minimization of Separable Concave Programs

Researchers first examined the problem of separable concave programming more than thirty years ago, making it one of the earliest branches of nonlinear programming to be explored. This paper proposes a new algorithm that finds the exact global minimum of this problem in a finite number of iterations. In addition to proving that our algorithm terminates finitely, the paper extends a guarantee of finiteness to all branch-and-bound algorithms for concave programming that (1) partition exhaustively using rectangular subdivisions and (2) branch on the incumbent solution when possible. The algorithm uses domain reduction techniques to accelerate convergence; it solves problems with as many as 100 nonlinear variables, 400 linear variables and 50 constraints in about five minutes on an IBM RS/6000 Power PC. An industrial application with 152 nonlinear variables, 593 linear variables, and 417 constraints is also solved in about ten minutes.     

Using separable programming to solve the multi-product multiple ex-ante constraint newsvendor problem and extensions

This paper provides an approximating programming technique to solve the multi-product newsvendor model in which product demands are independent and stocking quantities are subject to two or more ex-ante linear contraints, such as budget or volume constraints. Previous research has attempted to solve this problem with Lagrange relaxation techniques or by limiting the distribution of demand. However, by taking advantage of the separable nature of the problem, a close approximation of the optimal solution can be found using convex separable programming for any demand distribution in the traditional newsvendor model and extensions. Sensitivity analysis of the linear program provides managerial insight into the effects of parameters of the problem on the optimal solution and future decisions.     

Linear,Integer, Separable and Fuzzy Programming Problems: A Unified Approach towards Reformulation

For mathematical programming (MP) to have greater impact as a decision tool, MP software systems must offer suitable support in terms of model communication and modelling techniques. In this paper, modelling techniques that allow logical restrictions to be modelled in integer programming terms are described, and their implications discussed. In addition, it is illustrated that many classes of non-linearities which are not variable separable may be, after suitable algebraic manipulation, put in a variable separable form. The methods of reformulating the fuzzy linear programming problem as a max-min problem is also introduced. It is shown that analysis of bounds plays a key role in the following four important contexts: model reduction, reformulation of logical restrictions as 0-1 mixed integer programmes, reformulation of non-linear programmes as variable separable programmes and reformulation of fuzzy linear programmes. It is observed that, as well as incorporating an interface between the modeller and the optimizer, there is a need to make available to the modeller software facilities which support the model reformulation techniques described here.     

A numerical method for a class of continuous concave programming problems

The problem under consideration consists in maximizing a separable concave objective functional on a class of non-negative Lebesgue integrable functions satisfying a system of linear constraints. The problem is approximated by two sequences of concave separable programming problems with linear constraints. The convergence of the sequences of optimum values of these problems is investigated in the general case and the convergence of the sequences of optimum solutions in a special case. A numerical example is given.     

AN EXTENSION OF PREDICTOR-CORRECTOR ALGORITHM TO A CLASS OF CONVEX SEPARABLE PROGRAM

1.IntroductionIn[1]Mizuno,ToddandYepresentedapredictor-correctoralgorithmforlinearpramgrammingwhichpossessesaquadraticconvergencerateofthedualgaptozero.GuoandWul6]gaveamodificationofthisalgorithmforsolvingconvexquadraticprogramwithupperbounds.Itisshownthatthemodifiedmethodnotonlypreservesalltheoriginalmerits,butalsoreducesthedualgapbyaconstantfactorineachcorrectorstep,incontrasttotheMizuno,TOddandYe'soriginalpredictor--correctormethodwherethedualgapremainsunchanged.Thealgorithmdiscussedint…     

A simple SLP algorithm for solving a class of nonlinear programs

Successive linear programming (SLP) algorithms solve nonlinear optimization problems via a sequence of linear programs. We present an approach for a special class of nonlinear programming problems, which arise in multiperiod coal blending. The class of nonlinear programming problems and the solution approach considered in this paper are quite different from previous work. The algorithm is very simple, easy to apply and can be applied to as large a problem as the linear programming code can handle. The quality of solution, produced by the proposed algorithm, is discussed and the results of some test problems, in the real world environment, are provided.     

Survey of linear programming for standard and nonstandard Markovian control problems. Part II: Applications

This paper deals with some applications of Markov decision models for which the linear programming method is efficient. These models are replacement models (with the optimal stopping problem as special case), separable models (including the inventory model as special case) and the multi-armed bandit model. In the companion paper Survey of linear programming for standard and nonstandard Markovian control problems. Part I: Theory, general linear programming methods are discussed. These linear programming formulations are the starting point for the efficient methods that will be derived for the special models.     

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.     

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.