China
Africa
Explore chapters and articles related to this topic
Linear Programming and Mixed Integer Programming
Published in Erchin Serpedin, Thomas Chen, Dinesh Rajan, Mathematical Foundations for SIGNAL PROCESSING, COMMUNICATIONS, AND NETWORKING, 2012
Proof 2. Given a matrix Φ ∈ ℝp×q and a vector f ∈ ℝp, the celebrated Farkas lemma says that exactly one of the following affirmations holds (this type of result is often named a “theorem of alternatives”). ∃u ∈ c such that Φu = f and u ≥ 0.∃v ∈ ℝp such that ΦTv ≥ 0 and fTv ≤ 0.
Optimization Techniques for Circuit Design Applications
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
Clearly, the existence of a such λ serves as a certificate for the incompatibility of the linear inequalities in Equation 6.15. What is interesting (and nontrivial) is the fact that the converse is also true. That is, if the system (Equation 6.15) is infeasible, then there always exists a mathematical certificate λ satisfying Equation 6.16. Results of this kind are called the theorems of alternatives, and are related to the well-known Farkas’ lemma for the linear feasibility problem.
Classical Optimization
Published in Albert G. Holzman, Mathematical Programming, 2020
Kuhn and Tucker's derivation of their conditions [9] is along quite different lines. They assume a constraint qualification and proceed to use Farkas’ lemma to arrive at their result. We have assumed a perhaps stronger condition, in that we have implicitly assumed, just as we did in the previous proofs about the Lagrange multiplier method, that at least one of the Jacobian matrices ∥ αgi/αxj ∥ was nonsingular.
A new approach to strong duality for composite vector optimization problems
Published in Optimization, 2021
María J. Cánovas, Nguyen Dinh, Dang H. Long, Juan Parra
As by-products of the duality approach for problem (CVP) developed in this paper, we obtain extensions of recent Farkas-type results for composite vector functions. From the pioneer work of Farkas [23], different authors have provided generalizations of the initial statement of the celebrated Farkas lemma (see [24] for a survey on this subject). Next we connect the classical statement with our current framework of vector-systems involving composite functions defined on lcHtvs. In this framework, given where represents the space of linear continuous mappings from X to Y, we focus on characterizing the fulfilment of the following functional ‘vectorial inequality’: The following paragraphs are intended to integrate our condition (2) and its characterizations in the existing literature. With this aim, we present a brief summary of different stages in the generalization process from the original version of Farkas lemma until our results. As is well-known, Farkas lemma can be stated as follows: Given any vectors the following conditions, denoted by and are equivalent (here, is the zero vector in ):
Linear Programming from Fibonacci to Farkas
Published in Annals of Science, 2021
In the second half of the nineteenth century the subject we now know as Linear Algebra began to take shape. In 1873, when Paul Gordan proved a ‘Theorem of the Alternative’ about the existence of non-negative solutions of a system of linear homogeneous equations, he used determinants in his paper. Twenty-five years later Gyula Farkas, inspired by Fourier’s work, proved a significant extension of Gordan’s result, about non-homogeneous equations. In the twentieth century Linear Algebra found many new applications, notably as a tool for solving complex problems of organization and planning. Thus there arose the subject of Operations Research. One of its main tools was Linear Programming, where it turned out that the ‘Farkas Lemma’ plays a fundamental role. In fact, the underlying mathematical principle also played a central role in the development of Game Theory and other areas of Mathematical Economics.
Equivariant perturbation in Gomory and Johnson's infinite group problem (V). Software for the continuous and discontinuous 1-row case
Published in Optimization Methods and Software, 2018
Chun Yu Hong, Matthias Köppe, Yuan Zhou
Consider the following question from the theory of linear inequalities over the reals: Given a (finite) system , exactly which linear inequalities are valid, i.e. satisfied for every x that satisfies the given system? The answer is given, of course, by the Farkas Lemma, or, equivalently, by the strong duality theory of linear optimization. As is well known, this duality theory is symmetric: The dual of a linear optimization problem is again a linear optimization problem, and the dual of the dual is the original (primal) optimization problem.