A constructive algorithm for folding large-scale systems of linear inequalities

The conventional procedure for folding a system of linear inequalities based on the Fourier-Chernikov algorithm is supplemented with techniques for eliminating redundant inequalities, which considerably counteracts the increase in the system dimension. Exact and approximate methods are proposed, which are brought to algorithmic form and software implementation. Numerical results are discussed.     

AN ALGORITHM FOR SOLVING SYSTEM OF LINEAR INEQUALITIES

A new algorithm is presented for solving a system of linear inequalities. Starting at any point by solving a least squares problem we can either obtain a feasible point or determine that no solution exists.     

Weighted Variational Inequalities

In this paper, we introduce weighted variational inequalities over product of sets and system of weighted variational inequalities. It is noted that the weighted variational inequality problem over product of sets and the problem of system of weighted variational inequalities are equivalent. We give a relationship between system of weighted variational inequalities and systems of vector variational inequalities. We define several kinds of weighted monotonicities and establish several existence results for the solution of the above-mentioned problems under these weighted monotonicities. We introduce also the weighted generalized variational inequalities over product of sets, that is, weighted variational inequalities for multivalued maps and systems of weighted generalized variational inequalities. Extensions of weighted monotonicities for multivalued maps are also considered. The existence of a solution of weighted generalized variational inequalities over product of sets is also studied. The existence results for a solution of weighted generalized variational inequality problem give also the existence of solutions of systems of generalized vector variational inequalities. The first and third author express their thanks to the Department of Mathematical Sciences, King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia for providing excellent research facilities. The authors are also grateful to the referees for comments and suggestions improving the final draft of this paper.     

Existence of Solutions and an Algorithm for Mixed Variational-Like Inequalities in Banach Spaces

In this paper, we study the class of mixed variational-like inequalities in reflexive Banach spaces. By applying a minimax inequality due to the author, some existence and uniqueness theorems for solutions of mixed variational-like inequalities are proved. Next, by applying the auxiliary problem technique, we suggest an innovative iterative algorithm to compute approximate solutions of the mixed variational-like inequality. Finally, convergence criteria are also discussed. This research was supported by NSF, Sichman Education Department of China, Projects 2003A081 and SZD0406. The author expresses his sincere thanks to Professor H.P. Benson and the anonymous referees for careful comments leading to the present version of this paper.     

General criteria for redundant and nonredundant linear inequalities

A system of linear inequalities subject to nonnegativity restrictions is considered. General criteria which are necessary and sufficient for a linear inequality to be redundant are derived. This general characterization provides a basis for unifying some of the existing techniques. After taking into consideration the existence of redundant linear inequalities, general necessary and sufficient criteria for a linear inequality to be nonredundant are also obtained. An example is given to illustrate the application of these new criteria.The author wishes to thank the referee for his comments.     

A smoothing-type algorithm for solving system of inequalities

In this paper we consider system of inequalities. By constructing a new smoothing function, the problem is approximated via a family of parameterized smooth equations. A Newton-type algorithm is applied to solve iteratively the smooth equations so that a solution of the problem concerned is found. We show that the algorithm is globally and locally quadratically convergent under suitable assumptions. Preliminary numerical results are reported.     

一个关于混合变分不等式问题的投影算法

作者提出了混合变分不等式的一个新的投影算法. 混合变分不等式在弹性塑料学领域有实际应用, 而且形式上比经典的变分不等式更一般. 假设映射具有某种伪单调性, 作者证明了所提出的新算法是全局收敛的. 如果某种误差届成立, 算法的收敛率也被分析.     

求解线性不等式组的方法

本提出了一个新的求解线性不等式组可行解的方法－－无约束极值方法。通过在线性不等式组的非空可行域的相对内域上建立一个非线性极值问题，根据对偶关系，得到了一个对偶空间的无约束极值及原始，对偶变量之间的简单线性映射关系，这样将原来线性不等式组问题的求解转化为一个无约束极值问题。中主要讨论了求解无约束极值问题的共轭梯度算法。同时，在寻找不等式组可行解的过程中，定义了穿越方向，这样大大减少计算量。中最后数值实验结果表明此算法是有效的。     

基于动力系统的线性不等式组的解法

本文提出了一种新的求解线性不等式组可行解的方法-基于动力系统的方法．假设线性不等式组的可行域为非空,在可行域的相对内域上建立一个非线性关系表达式,进而得到一个结构简单的动力系统模型．同时,定义了穿越方向。文章最后的数值实验结果表明此算法是有效的．     

A NEW SMOOTHING APPROXIMATION METHOD FOR SOLVING BOX CONSTRAINED VARIATIONAL INEQUALITIES

In this paper, we first give a smoothing approximation function of nonsmooth system based on box constrained variational inequalities and then present a new smoothing approximation algorithm. Under suitable conditions,we show that the method is globally and superlinearly convergent. A few numerical results are also reported in the paper.     

Hilbert空间中关于松弛协强制映射的一类新的广义变分不等式组

在本文中,我们首先引入了一类新的关于松弛协强制映射的广义变分不等式组,通过用度量投影的方法,我们证明了这类广义变分不等式组解的存在性和唯一性.我们也建立了一类新的算法来逼近这一不等式组的解,本文的结果使得近期相关结果成为本文的特殊情况.     

Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research.     

广义混合隐拟h变分不等式的解的存在性与算法

本文在Hilbert空间中,引入了一类广义混合隐拟h变分不等式.运用变分原理,给出了广义混合隐拟h变分不等式逼近解的迭代算法,证明了这类变分不等式解的存在性定理,同时,得到迭代序列的收敛性.并改进和推广了[6~8]一些已知结果.     

变分不等式的一类二次投影算法

通过构造的一类严格分离当前点与解集的超平面得到了一类解伪单调变分不等式的修正二次投影算法,该算法对He Yiran的算法进行了修正.从而建立了解伪单调变分不等式二次投影算法的一种框架结构.证明了该算法生成的无穷序列具有的全局收敛性,在具备某种局部误差界和Lipchitz连续条件下给出了收敛率分析.并给出了该算法的数值演算结果.     

求解单调变分不等式的近似邻近点算法的收敛性分析

为了求解单调变分不等式,建立了一个新的误差准则,并且在不需要增加诸如投影,外梯度等步骤的情况下证明了邻近点算法的收敛性.     

A penalty optimization technique for a class of regulator problems,part 3

The frequent encounter in economics, disease epidemics, resource depletion, as well as electromechanical systems of phenomena that cannot be readily modelled unless equations involving time delays are admitted has drawn a great deal of research attention to differentialdelay systems, which have consequently grown at an unprecedented rate. In Refs. 1 and 2, we provided and generalized a function space algorithm, known as the extended conjugate-gradient method (ECGM) algorithm, as a penalty optimization technique for solving a continuous optimal control problem governed by a system of differential-delay equations under the influence of certain inhomogeneous forcing terms; however, numerical results to support our analysis were not presented. To fill the gap, this paper presents the numerical behavior of the ECGM algorithm through the solution of a significant example. There is a noticeable improvement in the accuracy of the solutions obtained via the ECGM algorithm over those obtained via the averaging approximation principles developed by Banks and Burns (Ref. 3). Furthermore, the paper establishes some functional inequalities motivated from practical situations.It is a sincere pleasure to acknowledge the financial support of the University of Ilorin, Ilorin, Nigeria, Senate Research Grant No. UI/REG/SEO/57-1987.The author would like to gratefully thank Dr. J. Schiess of NASA-LRC Analysis and Computation Division and two anonymous referees for their helpful comments which led to a major improvement in the quality of the paper and especially for suggesting the inclusion of Ref. 3.     

Iterative algorithms for systems of extended regularized nonconvex variational inequalities and fixed point problems

This paper points out some fatal errors in the equivalent formulations used in Noor 2011 [Noor MA. Projection iterative methods for solving some systems of general nonconvex variational inequalities. Applied Analysis. 2011;90:777–786] and consequently in Noor 2009 [Noor MA. System of nonconvex variational inequalities. Journal of Advanced Research Optimization. 2009;1:1–10], Noor 2010 [Noor MA, Noor KI. New system of general nonconvex variational inequalities. Applied Mathematics E-Notes. 2010;10:76–85] and Wen 2010 [Wen DJ. Projection methods for a generalized system of nonconvex variational inequalities with different nonlinear operators. Nonlinear Analysis. 2010;73:2292–2297]. Since these equivalent formulations are the main tools to suggest iterative algorithms and to establish the convergence results, the algorithms and results in the aforementioned articles are not valid. It is shown by given some examples. To overcome with the problems in these papers, we consider a new system of extended regularized nonconvex variational inequalities, and establish the existence and uniqueness result for a solution of the aforesaid system. We suggest and analyse a new projection iterative algorithm to compute the unique solution of the system of extended regularized nonconvex variational inequalities which is also a fixed point of a nearly uniformly Lipschitzian mapping. Furthermore, the convergence analysis of the proposed iterative algorithm under some suitable conditions is studied. As a consequence, we point out that one can derive the correct version of the algorithms and results presented in the above mentioned papers.     

On system of generalized vector variational inequalities

In this paper, we introduce a new system of generalized vector variational inequalities with variable preference. This extends the model of system of generalized variational inequalities due to Pang and Konnov independently as well as system of vector equilibrium problems due to Ansari, Schaible and Yao. We establish existence of solutions to the new system under weaker conditions that include a new partial diagonally convexity and a weaker notion than continuity. As applications, we derive existence results for both systems of vector variational-like inequalities and vector optimization problems with variable preference.     

A cutting plane algorithm for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is to locate a set of facilities with capacity constraints, to satisfy at the minimum cost the order-demands of a set of clients. A multi-source version of the problem is considered in which each client can be served by more than one facility. In this paper we present a reformulation of the CFLP based on Mixed Dicut Inequalities, a family of minimum knapsack inequalities of a mixed type, containing both binary and continuous (flow) variables. By aggregating flow variables, any Mixed Dicut Inequality turns into a binary minimum knapsack inequality with a single continuous variable. We will refer to the convex hull of the feasible solutions of this minimum knapsack problem as the Mixed Dicut polytope. We observe that the Mixed Dicut polytope is a rich source of valid inequalities for the CFLP: basic families of valid CFLP inequalities, like Variable Upper Bounds, Cover, Flow Cover and Effective Capacity Inequalities, are valid for the Mixed Dicut polytope. Furthermore we observe that new families of valid inequalities for the CFLP can be derived by the lifting procedures studied for the minimum knapsack problem with a single continuous variable. To deal with large-scale instances, we have developed a Branch-and-Cut-and-Price algorithm, where the separation algorithm consists of the complete enumeration of the facets of the Mixed Dicut polytope for a set of candidate Mixed Dicut Inequalities. We observe that our procedure returns inequalities that dominate most of the known classes of inequalities presented in the literature. We report on computational experience with instances up to 1000 facilities and 1000 clients to validate the approach.