Tagged Questions
1
vote
1answer
30 views
Compute $v,W,k$ such that the following is true
$$
\left\{ x \in \mathbb{Z}^4 |
\begin{pmatrix}
5 & 3 & 7 & 0 \\
2 & -4 & 6 & 5
\end{pmatrix}
x =
\begin{pmatrix}
5 \\0
\end{pmatrix}
\right\} = \left\{ v + Wy \ | \ y \in ...
0
votes
0answers
32 views
Basic Solutions in Linear System
I am studying Linear programming and we have just learnt about Basic solutions. I know that a basic solution (x) should have 2 properties:
should indeed be a solution. $Ax = b$ should hold.
for some ...
2
votes
2answers
35 views
Exploring underdetermined linear system with non-negative solution
I haven't had much luck searching for this specific problems. Any pointers would be greatly appreciated.
I have an underdetermined system where $ A $ and $ b $ are known. $ x $ is a real vector with ...
0
votes
0answers
20 views
Proof by Farkas theorem
2) Show using duality that exactly one of the following systems has a solution:
I) Ax=b, 0 ≤ x ≥ e
II) A^T u + v ≥ 0, b^T u + e^T v=-1,v ≥ 0
Solution:
(P) ...
1
vote
1answer
42 views
How tell if a polyhedron contains a lattice point
So given a polyhedron
$Ax \le b$
Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point)
I was thinking a couple things:
brute force ...
3
votes
1answer
70 views
Is the inverse of an invertible totally unimodular matrix also totally unimodular?
My question is learned from here. Let me restate it as follows:
A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix ...
0
votes
0answers
38 views
Transportation Problem - Linear Algebra
Say we have a standard transportation problem with supply and demand vectors S = [50, 60] and d = [20, 50, 40] and the cost matrix
C =
R1) 4 3 5
R2) 3 6 2
The minimum cost method provides a way ...
0
votes
0answers
14 views
Graphical solution of LOP with three variables and a parameter
For what values of $\lambda$ does the following linear optimization problem has no solution?
$$
x_2 - \lambda x_3 \to \operatorname{min}
$$
subject to
\begin{align*}
-x_1 + 3x_2 + x_3 & ~=~ 3 \\
...
1
vote
0answers
46 views
Linear Programming: Modifying Coefficients of the Objective Function
Consider a final tableau with entries:
Row 1: 0,(-1/2),1,1,2,0,-1
Row 2: 1,(1/2),0,2,-1,0,-2
Row 3: 0,2,0,-1,(-1/2),1,3
Basic variable values (4,2,1)
and objective function coefficients ...
0
votes
0answers
79 views
Transportation Problem: Least-Cost Method
I am trying to get a grasp on the standard transportation problem. Apparently the number of linearly independent constraints is m+n-1. How can I show that the minimum cost method creates at most ...
1
vote
1answer
68 views
Linear Programming for Integer Solutions
Connsider the linear programming problem Max $z = 5x_1 + 6x_2$ st. $10x_1 + 3x_2 \leq 52,2x_1 + 3x_2 \leq 18$ and $x_1, x_2 \geq 0$ and integer.
How would one manipulate the resources so that the ...
0
votes
0answers
29 views
How to prove this? The existence of solutions to linear inequalities
A system of real homogeneous linear inequalities $\lambda_i>0$, $i=1,2,\ldots,m$, has a solution if and only if there is no nontrivial linear dependence with nonnegative coefficients among the ...
1
vote
2answers
80 views
Max and min value of $7x+8y$ in a given half-plane limited by straight lines?
So, there are four inequalities:
$$\begin{eqnarray*}
y &\geq &-3x+15; \\
y &\leq &-11/3x+56/3; \\
x &\geq &0; \\
y &\geq &0.
\end{eqnarray*}$$
If we draw all those ...
0
votes
0answers
80 views
Formula for distance travelled?
Given the coordinates of source of a missile, and those of the target both of which are on the surface of the Earth $(z=0)$ , I need to determine the total distance that the missile will need to ...
0
votes
0answers
49 views
Solving an overdetermined system of inequalities using null-space arguments
The solutions to a linear system of equations:
$$A\cdot x = b$$
(where $x$ is a $(n\times 1)$ column vector, $b$ is a $(m\times 1)$ column vector and $A$ is $(m\times n)$ matrix)
can all be ...
2
votes
2answers
54 views
What are the relations between these two minimizations
What are the relations between the minimization problems $\arg\min_{\mathbf{y}=A\mathbf{x}}\left\Vert \mathbf{x}\right\Vert _{2}$
and $\arg\min_{\mathbf{x}}\left\Vert A\mathbf{x-y}\right\Vert _{2}$
?
0
votes
1answer
54 views
Is the product of two totally unimodular matrices again totally unimodular?
For unimodular matrices this is the case. It seems reasonable that this is also the case for totally unimodular matrices, but I couldn't find a reference for this.
Does someone know why it is true ...
1
vote
1answer
45 views
Are there 0-1-matrices that are not unimodular?
I am just wondering if there are matrices that only consists of $0$s and a few $1$s that are not totally unimodular (TU)? I cannot come up with an example but I am not very experienced with this ...
6
votes
1answer
35 views
Bounding the number of nonzero coefficients in a conic combination
I'm looking for a proof for the following statement in order to understand a proof about integer programming I'm reading.
Given vectors $x_1, \ldots, x_s \in \mathbb R^n$, nonnegative coefficients ...
1
vote
1answer
258 views
Armijo's rule line search
I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13.
The variable is $\beta$ ...
3
votes
2answers
106 views
Find the point in a sub-space defined by linear constraints closer to an external point
I have the following
$P \in \mathbb R^d$
A set of $k$ linear constraints $c_i \in \mathbb R^d,d_i \in \mathbb R$
I need to find the point $P_0$ that satisfies all the $k$ constraints (i.e. ...
2
votes
1answer
76 views
Optimality Criterion and the Simplex Method
The optimality criterion states:
If the objective row of a tableau has zero
entries in the columns labeled by basic variables and no
negative entries in the columns labeled by nonbasic variables,
...
0
votes
1answer
122 views
Matlab question: Converting a permutation matrix into a vector showing row exchanges
Let me preface that I am an absolute beginner with Matlab. I am trying to perform $PA=LU$ factorization on a matrix, however I am having difficulty with the permutation matrix. When I execute ...
1
vote
1answer
81 views
How to determine maximum angles between vectors?
I'm attempting to distribute vectors with the same origin with a maximum angle of separation. Then if given a set of vectors, I want to determine how far from maximum separation they are. For ...
3
votes
1answer
63 views
Find the vertices of the polytope
Let $x,n$ be 2 integers with $x<n$.
I need to find the vertices of the polytope $P$ of $2 \times n$ nonnegative matrices $A$ such that:
The first row in $A$ is summed to $x$.
$$\sum_{j=1}^n ...
3
votes
1answer
55 views
A particular ILP where the existence of a relaxed solution implies the existence of an integer solution
This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately.
I am ...
4
votes
1answer
140 views
How to solve system of equations with multiple constraints?
I have a system of equations that looks like this:
$$\begin{array}{rl}
a_1 b_1 c_1+a_2 b_2 c_2+a_3 b_3 c_3&=1000\\
a_1+a_2+a_3&=1\\
a_2&=0.6 \,a_1\\
b_1+b_2+b_3&=500
\end{array}$$
...
1
vote
1answer
73 views
positive solution of a system of linear equations
Consider the following system of linear equations over $x_{ij}$ for $1\leq i\leq m$ and $1\leq j\leq n$:
$\sum_{j}x_{ij}=a_i$ for $i=1, \cdots, m$ and $\sum_{i}x_{ij}=b_j$ for $j=1, \cdots, n$ where ...
3
votes
1answer
75 views
Solving ill posed linear equations
Given a set of linear equations $AX=B$, say $A$ is an ill posed matrix (has a few singular values equal or very close to zero), which numerical algorithm (conjugate gradient, least squares or steepest ...
1
vote
2answers
88 views
Invertability of submatrix?
If I have a matrix $A \in R^{(m \times n)}$ with $m \leq n$. All rows in matrix a are linearly independent and therefore $A$ has a full row rank. I can decompose matrix $A$ such that $A = [B|N]$ with ...
1
vote
0answers
123 views
Linear programming: writing a problem with artificial variables?
Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
3
votes
0answers
43 views
finding the largest $p$ components of $x$
Given an $n \times n$ matrix $A$, and an $n \times 1$ vector $b$, the conventional way of computing an $n \times 1$ vector $x$ such that $x=Ax+b$ is to use the following iterations:
...
2
votes
1answer
161 views
A variation of the Assignment Problem
In the following Wikipedia article about the Assignment Problem in the Example section, it says:
Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
0
votes
0answers
27 views
If a number can play the same as a vector in LP
I have a simple linear program as below:
$min L(x)=\sum_i w_i x_i$
subject to
EDIT:
$a\leq f(x_i) \leq b$
where $w_i$ are constants and known calculated by $w_i=(v1_i).*(v2_i)\ \forall i$, where ...
4
votes
5answers
149 views
Find a convex combination of scalars given a point within them.
I've been banging my head on this one all day! I'm going to do my best to explain the problem, but bear with me.
Given a set of numbers $S = \{X_1, X_2, \dots, X_n\}$ and a scalar $T$, where it is ...
2
votes
3answers
80 views
Dual of a Linear Program
\begin{align}
\min_{x} c^Tx \\
s.t.~Ax=b
\end{align}
Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by
\begin{align}
\max_{\lambda} \lambda^Tb \\
...
3
votes
1answer
93 views
Generating random linear programming problems
I've just finished writing a a linear programming problem solver which uses the simplex method. Now I would like to start optimizing my solver but before I can do this, I need a way of reliably ...
2
votes
2answers
190 views
What are the advantages of dual of a problem
I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable ...
0
votes
0answers
62 views
Proving that a nonlinear system has a unique solution
Let $x^*$, $y^*$, $w^*$ and $z^*$ be initial values for $x, y, w$ and $z$. Let $t$ be a parameter between $0$ and $1$. $X, Y, W,$ and $Z$ are diagonal matrices of the vectors $x, y, w,$ and $z$. ...
1
vote
2answers
126 views
Removing linear redundant constraints using Gauss Elimination
I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set.
Here I found a similar ...
1
vote
1answer
65 views
Question on Linear Algebra
NOTE: I tried hard and came up with a lose proof, I have posted it as a answer. Do comment/correct if you can.
Let
$$P=\{x|Ax\geq b\}, A\in \mathbb{R}^{m\times n}$$
$$Q=\{y|Gy\geq h\},G\in ...
3
votes
3answers
187 views
0-1 knapsack like - the set of all non-contained affordable binary selections
This is my first question here, so please go easy on me :)
The following problem is – I think - similar to the 0-1 knapsack problem. It's simplified somehow in that each item has only a cost ...
3
votes
1answer
120 views
Dimension of solution space for system of linear inequalities
Let's say I have a system of inequalities: $Ax \leq g$ for some $A \in \mathbb{R}^{4\times4}$, $x \in \mathbb{R}^4$, $g \in \mathbb{R}^4$, and $A$ is full rank. Here, the $\leq$ denotes element-wise ...
6
votes
1answer
391 views
Farkas Lemma proof
I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm.
From Wikipedia:
Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the ...
0
votes
1answer
24 views
intuitive explanation of sparsity / references
I know it is a vague question, but I am confused by why/when we actually want sparsity of a matrix. For example, interior-point methods work better when constraint matrix is sparse. Similarly, it is ...
1
vote
1answer
105 views
Linear combination question in Linear Programming Problem
I have two constraints in a linear programming model:
x1 + x2 <= 5
x1 >= 2
Note that there are no nonnegativity constraints so the problem is unbounded from below.
The point (2,3) is the only ...
0
votes
1answer
49 views
Solving equation of the form $Axb^Tx = y$
I have a square, invertible $n\times n$ matrix $A$, and column vectors $b$ and $y$. I'd like to find a column vector $x$ such that $Axb^Tx=y$. I suspect there's some way to get it into a QP form, but ...
1
vote
0answers
148 views
Linear programming: basic solutions?
http://www.math.toronto.edu/kergin/236_t1_2.pdf
For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 ...
-5
votes
1answer
94 views
What approach can be used to solve this? [closed]
The problem can be found here.
The game is simple. You initially have ‘H’ amount of health and ‘A’ amount of armor. At any instant you can live in any of the three places - fire, water and air. ...
2
votes
0answers
148 views
Reconstructing an optimal Simplex tableau from an optimal solution
I have here a bounded LP with infinite optimal solutions:
...
