Understanding linear semi-infinite programming via linear programming over cones

In this article, the standard primal and dual linear semi-infinite programming (DLSIP) problems are reformulated as linear programming (LP) problems over cones. Therefore, the dual formulation via the minimal cone approach, which results in zero duality gap for the primal–dual pair for LP problems over cones, can be applied to linear semi-infinite programming (LSIP) problems. Results on the geometry of the set of the feasible solutions for the primal LSIP problem and the optimality criteria for the DLSIP problem are also discussed.     

Generalized corner optimal solution for LSIP: existence and numerical computation

In this paper, we consider general linear semi-infinite programming (LSIP) problems and study the existence and computation of optimal solutions at special generalized corner points called generalized ladder points (glp). We develop conditions, including an equivalent condition, under which glp optimal solutions exist. These results are fundamentally important to the ladder method for LSIP, which finds an optimal solution at a glp in the feasible region. For problems that do not have glp optimal solutions, we propose the addition of special artificial constraints to the constraint system of the problem to create a glp optimal solution. We present a ladder algorithm based on the maximum violation rule and an artificial ladder technique. Convergence results are provided with the support of some numerical tests.     

Stability of the primal-dual partition in linear semi-infinite programming

We analyse the primal-dual states in linear semi-infinite programming (LSIP), where we consider the primal problem and the so called Haar's dual problem. Any linear programming problem and its dual can be classified as bounded, unbounded or inconsistent, giving rise to nine possible primal-dual states, which are reduced to six by the weak duality property. Recently, Goberna and Todorov have studied this partition and its stability in continuous LSIP in a series of papers [M.A. Goberna and M.I. Todorov, Primal, dual and primal-dual partitions in continuous linear semi-infinite programming, Optimization 56 (2007), pp. 617–628; M.A. Goberna and M.I. Todorov, Generic primal-dual solvability in continuous linear semi-infinite programming, Optimization 57 (2008), pp. 239–248]. In this article we consider the general case, with no continuity assumptions, discussing the maintenance of the primal-dual state of the problem by allowing small perturbations of the data. We characterize the stability of all of the six possible primal-dual states through necessary and sufficient conditions which depend on the data, and can be easily checked, showing some differences with the continuous case. These conditions involve the strong Slater constraint qualification, and some distinguished convex sets associated to the data.     

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     

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.     

Linear programming approaches for multicategory support vector machines

We consider linear programming approaches for support vector machines (SVM). The linear programming problems are introduced as an approximation of the quadratic programming problems commonly used in SVM. When we consider the kernel based nonlinear discriminators, the approximation can be viewed as kernel principle component analysis which generates an important subspace from the feature space characterized the kernel function. We show that any data points nonlinearly, and implicitly, projected into the feature space by kernel functions can be approximately expressed as points lying a low dimensional Euclidean space explicitly, which enables us to develop linear programming formulations for nonlinear discriminators. We also introduce linear programming formulations for multicategory classification problems. We show that the same maximal margin principle exploited in SVM can be involved into the linear programming formulations. Moreover, considering the low dimensional feature subspace extraction, we can generate nonlinear multicategory discriminators by solving linear programming problems.Numerical experiments on real world datasets are presented. We show that the fairly low dimensional feature subspace can achieve a reasonable accuracy, and that the linear programming formulations calculate discriminators efficiently. We also discuss a sampling strategy which might be crucial for huge datasets.     

The dual simplex method and sensitivity analysis for fuzzy linear programming with symmetric trapezoidal numbers

In this paper, we first extend the dual simplex method to a type of fuzzy linear programming problem involving symmetric trapezoidal fuzzy numbers. The results obtained lead to a solution for fuzzy linear programming problems that does not require their conversion into crisp linear programming problems. We then study the ranges of values we can achieve so that when changes to the data of the problem are introduced, the fuzzy optimal solution remains invariant. Finally, we obtain the optimal value function with fuzzy coefficients in each case, and the results are described by means of numerical examples.     

Checking weak optimality of the solution to linear programming with interval right-hand side

The interval linear programming (IvLP) is a method for decision making under uncertainty. A weak feasible solution to IvLP is called weakly optimal if it is optimal for some scenario of the IvLP. One of the basic and difficult tasks in IvLP is to check whether a given point is weak optimal. In this paper, we investigate linear programming problems with interval right-hand side. Some necessary and sufficient conditions for checking weak optimality of given feasible solutions are established, based on the KKT conditions of linear programming. The proposed methods are simple, easy to implement yet very effective, since they run in polynomial time.     

Qualitative and quantitative data envelopment analysis with interval data

In this paper, we investigate DEA with interval input-output data. First we show various extensions of efficiency and that 25 of them are essential. Second we formulate the efficiency test problems as mixed integer programming problems. We prove that 14 among 25 problems can be reduced to linear programming problems and that the other 11 efficiencies can be tested by solving a finite sequence of linear programming problems. Third, in order to obtain efficiency scores, we extend SBM model to interval input-output data. Fourth, to moderate a possible positive overassessment by DEA, we introduce the inverted DEA model with interval input-output data. Using efficiency and inefficiency scores, we propose a classification of DMUs. Finally, we apply the proposed approach to Japanese Bank Data and demonstrate its advantages.     

Strong duality for inexact linear programming

In this paper, we apply the Dubovitskii-Milyutin approach to derive strong duality theorems for inexact linear programming problems. Inexact linear programming deals with the standard linear problem in which the data is not well known and it is supposed to lie in certain given convex sets. The case of parametric dependence of the data is particularly analyzed and relations with semi-infinite and

semi-definite programming are also commented.     

Some duality results on linear programming problems with symmetric fuzzy numbers

Recently, linear programming problems with symmetric fuzzy numbers (LPSFN) have considered by some authors and have proposed a new method for solving these problems without converting to the classical linear programming problem, where the cost coefficients are symmetric fuzzy numbers (see in [4]). Here we extend their results and first prove the optimality theorem and then define the dual problem of LPSFN problem. Furthermore, we give some duality results as a natural extensions of duality results for linear programming problems with crisp data.     

Possibilistic Linear Programming with Fuzzy If-Then Rule Coefficients

In this paper, we propose a scenario decomposition approach for the treatment of interactive fuzzy numbers. Scenario decomposed fuzzy numbers (SDFNs) reflect a fact that we may have different estimations of possible ranges of uncertain variables depending on scenarios, which are expressed by fuzzy if-then rules. The properties of SDFNs are investigated. Possibilistic linear programming problems with SDFNs are formulated by two different approaches, fractile and modality optimization approaches. It is shown that the problems are reduced to linear programming problems in fractile optimization models with the necessity measures and that the problems can be solved by a linear programming technique and a bisection method in modality optimization models with necessity measures. A simple numerical example is given.     

An inexact interior point method for L 1-regularized sparse covariance selection

Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.     

Sufficient Optimality Criterion for Linearly Constrained,Separable Concave Minimization Problems

A sufficient optimality criterion for linearly-constrained concave minimization problems is given in this paper. Our optimality criterion is based on the sensitivity analysis of the relaxed linear programming problem. The main result is similar to that of Phillips and Rosen (Ref. 1); however, our proofs are simpler and constructive.In the Phillips and Rosen paper (Ref. 1), they derived a sufficient optimality criterion for a slightly different linearly-constrained concave minimization problem using exponentially many linear programming problems. We introduce special test points and, using these for several cases, we are able to show optimality of the current basic solution.The sufficient optimality criterion described in this paper can be used as a stopping criterion for branch-and-bound algorithms developed for linearly-constrained concave minimization problems.This research was supported by a Bolyai János Research Fellowship BO/00334/00 of the Hungarian Academy of Science and by the Hungarian Scientific Research Foundation, Grant OTKA T038027.     

A simplex algorithm for piecewise-linear fractional programming problems

Generalizations of the well-known simplex method for linear programming are available to solve the piecewise linear programming problem and the linear fractional programming problem. In this paper we consider a further generalization of the simplex method to solve piecewise linear fractional programming problems unifying the simplex method for linear programs, piecewise linear programs, and the linear fractional programs. Computational results are presented to obtain further insights into the behavior of the algorithm on random test problems.     

A globally convergent trust region algorithm for optimization with general constraints and simple bounds

1.IntroductionInthispaper,weconsiderthefollowingnonlinearprogr~ngproblemwherec(x)=(c,(x),c2(2),',We(.))',i(x)andci(x)(i=1,2,',m)arerealfunctions*ThisworkissupPOrtedbytheNationalNaturalScienceFOundationofChinaandtheManagement,DecisionandinformationSystemLab,theChineseAcademyofSciences.definedinD={xEReIISx5u}.Weassumethath相似文献   

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

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.     

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.     

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

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