0
votes
0answers
5 views

Case of affine hull and linear hull possibly being euqal

Let C be a set in $\mathbb{R}^n$. Let $aff(X)$ denote the affine hull of $X$, and $lin(X)$ denote the linear hull of $X$. Suppose $x \in aff(C)$. Then, is it true that $aff(C-x)=lin(C-x)$? The ...
0
votes
0answers
16 views

What is the proof/show that the post of linear transformation generated by LDA is at most k-1

What is the proof/show that the post of linear transformation generated by LDA is at most k-1, where ...
1
vote
0answers
12 views

Find relationships between events

I have a set of Events $(E_i)_i$ which have a probability $(P_i)_i$. I am able to write each event as a sum of distinct events that form a partition of the space. My goal is to find all the ...
0
votes
1answer
42 views

Solving LP with two $L_1$ inequality constraints

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le ...
0
votes
0answers
9 views

How to prove that the solution in every next iteration of Simplex algorithm is a BFS

Let Ax = b x >= 0 be the feasible region. Let A be mxn matrix with m <= n and rank(A) = m. Simplex algorithm starts with a Basic Feasible solution. In each step it moves to a new solution. How do ...
0
votes
1answer
28 views

what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
0
votes
0answers
26 views

Linear Algebra - find basis without reduced echelon

For the start of a simplex solver I'm building in Python, I need to find a basic feasible solution. To do that, I need to find a basic solution/find the basis of the constraint matrix. Here's my ...
0
votes
1answer
22 views

Maximum cardinality affinely independent subset of $\mathbb{R}^n$

Let $S \subset \mathbb{R}^n$ such that $S$ is affinely independent. Then $$|S| \le n + 1.$$ Why? (e.g. does anybody know some place where this is proven?)
0
votes
0answers
19 views

Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces.

Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?) Every polyhedron $P \ne ...
0
votes
1answer
29 views

Can there be a unique natural number vector solution to $Ax =b$ where $A$ is not a specific type of square matrix?

Let $A$ be $(n-1) \times n$ matrix that is of the following form: $$\left( \begin{array}{ccc} n-1 & 1 & 0 &.... & ....\\ 0 & n-2 & 2 & .... & ....\\ 0 & 0 & n-3 ...
2
votes
1answer
52 views

Prove vertices of a simplex are affinely independent

I'm given that the definition of a simplex $T$ is $x \in\mathbb R^n$ such that $x$ satisfies $n+1$ linear inequalities: $(u_k, x) \lt c_k$ for $k = 1,\ldots,n+1$ (i.e. $T$ is the intersection of $n+1$ ...
1
vote
0answers
57 views

Proving boundedness of a function .

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
0
votes
1answer
50 views

Proving boundedness of a function (part 1).

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
1
vote
0answers
35 views

Proof of Strong Duality via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
0
votes
1answer
26 views

shortest point on a line segment from point out side the line

from the above pic I found the value x from line (p1,p2) and point a using y=mx+b and imaginary red line which is perpendicular to black line having slope -1/m and the intersecting point x. the ...
0
votes
0answers
15 views

Variable bounds of under-determined linear system

If I have a non-negative, under-determined linear system $\mathbf{Ax}=\mathbf{b}$ $\mathbf{x}\geq\mathbf{0}$ is there a fast way to compute the upper and lower bounds on values of each element of ...
0
votes
1answer
34 views

Minimze min max (A*x)

has this example matrix A some special propertries, which might be useful? $$ \left[\begin{array}{rrrrrr} 3 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ 4 & 3 & 0 & ...
1
vote
0answers
12 views

How to import matrix from sif document

I want to make some computation (with scilab, scipy or other) over the matrix A of linear problems (in inequational form). Those problems are in .sif format (from the netlib library in fact) and I ...
0
votes
1answer
26 views

Under-determined linear problem

To compute all solution of following under-determined linear problem in matrix form $ Ax = y $ we can use Pseudo inverse of A and the solution would be : $ x = A^{PI}y + [I - A^{PI}A]w $ I couldn't ...
0
votes
1answer
26 views

Linear Constraints Solution Existence

how can one decide if $$A*t\ge b$$ $A$ is a Matrix with integer Entries and $t$ is a Vector with integer Entries, $b$ is a fixed Vector with integer Entries exists?
2
votes
0answers
28 views

Finding optimal hyperplane

I have a set of vectors $\{V_i\}$ in $n$-dimensional space. There is a number corresponded to each vector $\alpha_i = f(V_i)$ ($\alpha_i$ can be negative). I want to find a hyperplane which would ...
0
votes
1answer
34 views

Pseudoinverse system of linear equation

$Ax = b$ describes a convex polyhedron, where $A$ is a real matrix and $b$ is a real vector. Now assume $A$ has less rows than columns. If you take a look here: ...
0
votes
1answer
38 views

Simplying linear equation to get quartic in q using Maple and then using Descarte’s rule of sign

Using the maple I am trying to get quardic in q from this big linear equation. Then use Descarte’s rule of signs to determine the number of positive roots. \begin{equation} ...
2
votes
1answer
38 views

Does the Duality Theorem of Linear Programming hold only in closed convex cones

I've just read the the Duality Theorem of Linear Programming. Here is the proof from my book (and my questions after it): Duality Theorem of Linear Programming: If the primal or dual linear ...
2
votes
0answers
29 views

Rayleigh Quotient variant?

If $A$ is a covariance matrix and I want to get $\max X^TAX$ where each value of $x$ is between -1 and 1. Is there a closed-form solution for this? I understand when $X^TX = 1$ this becomes the ...
1
vote
0answers
24 views

Check feasibility of a system of integer linear equations

I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time. The initial set of linear equations S={Ax<=b) is feasible. I want to add more ...
1
vote
1answer
35 views

Why $(1,\textbf{0}) \not\in \{(r,\textbf{w}): r=tz_0-\textbf{c}^T\textbf{x}, \textbf{w}=t\textbf{b}-\textbf{Ax}, \;\textbf{x}\geq\textbf{0}, t\geq0\}$

I'm learning about linear and nonlinear programming and on the chapter about duality I have the following statement and proof I can't understand: minimize $\textbf{c}^T\textbf{x}$ subject to ...
0
votes
0answers
31 views

Approximation of optimum for two linear programs

Suppose you got two linear programs. They are the same except that one has a shifted objective by a positive constant (1) $$\min c^Tx$$ (2) $$\min c^Tx + d$$ For (2) there exists a ...
0
votes
0answers
20 views

Name search for special Linear Mixed Integer Programm

I am looking for a name for the following question in literature! (and if you know it, then it would be great) I couldn't find it and due to wide audience here, presumably you know more. Thank you ...
0
votes
0answers
37 views

Prove solution does not exist for inequalities system

I have an inequalities sytem like the following: Example > x+y+z <= A > x+y <= B > x+z > C > y+z > D > x >= E Let A,B,C,D,E be any ...
0
votes
1answer
39 views

Projection onto Polyeder

I know how to projects onto a linear subspace of $\mathbb R^3$, but how to project a point $x$ onto an polyhedron given as the intersection of three halfspaces $$ \langle y_1, x \rangle \ge c_1 ...
0
votes
1answer
46 views

Can someone explain the effects of degenerate basic feasible solutions in the simplex algorithm?

I was given this on an assignment sheet, and am now using it to revise from...I cannot remember the issues that arise from degeneracy of basic feasible solutions... Let $P$ =$\{x\in \mathbb{R}^n ...
1
vote
1answer
32 views

Why is this simplex procedure not working? $\min z = y - x + 1$

I have read of two ways to solve this program with the Simplex algorithm. One worked and the other didn't. The only difference is that, in the one that didn't work, I rewrote the function. I will ...
0
votes
1answer
10 views

Is there relations between earth mover's distance and vector norms?

Say I have two vectors $a$ and $b$. Can I estimate $\mbox{EMD}(a,b)$ via some combination of things like $\|a-b\|_p$ and such?
2
votes
1answer
81 views

Linear Algebra 101 - Optimizing inequalities

I am considering the region contained in $\mathbb{R}^2$ consisting of all the points that satisfy all the following inequality: $-4 \leq y < 4 \\ -9 \leq 2x + y \leq 9 \\ -9 \leq x + 2y \leq 9 \\ ...
0
votes
0answers
33 views

Union of all sets of optimal solutions to a perturbed linear programming problem

Please let me know if you have some ideas on how to approach this proof? I got stuck part-way through. The following linear program is a function of $\theta$, $ \begin{array}{ll} \min & c^\top x ...
1
vote
1answer
14 views

the differences and relationship between linear independent and affinely independent

When learning optimization, I heard the two related concepts on linear algebra: linearly independent and affinely independent. ...
1
vote
1answer
23 views

Linear Optimization Study Material

I've recently enrolled in a linear optimization course, and it's been a while since I've taken linear algebra. I do not yet have access to the book for the course or I would skim it to see what I need ...
0
votes
1answer
24 views

What's wrong with this linear program formulation?

You have two item factories, $A$ and $B$, and there are two clients that buy such item. Each client has a demand - the first one needs $400$, and the second $300$. Each factory has a ...
0
votes
0answers
15 views

Total Least Squares problem when some columns of data matrix have no error

I'm reading through Golub and Van Loan and they mention that to solve the total least-squares problem $(A + E)x = b + r$, where the first $s$ columns of E are zero, then we can solve the problem by ...
1
vote
2answers
41 views

What is wrong with this linear program $\max z = 3x_1+2x_2$?

I solved a linear program. It is wrong. The answer is that $(x_1,x_2) = (50,75)$ and the maximum value is $300$, but instead I am getting $(x_1,x_2) = (50,100)$ and the maximum being $350$. Why is ...
0
votes
0answers
14 views

Solving $\max z (3x_1 - x_2)$ linear program

I am trying to solve this linear programming exercise using the Simplex method. First of all, I detail every step, so it is pretty long, but the real question (the part where I'm stuck at) is at the ...
0
votes
0answers
20 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
0
votes
0answers
18 views

Why do I have to solve a minimisation for an expanded maximisation linear program?

I'm learning about artifical variables with the Simplex method. There is an example where I'm getting a bit stuck at some point: Solving $$\max z = -2x_1 +x_2+1$$ subject to $$\begin{cases} ...
0
votes
1answer
39 views

How can I verify my linear program solutions?

I started solving linear programs with the Simplex algorithm, however it is unclear to me how can I verify my solutions. I have heard about geometrical solutions easy to check visually, but I'd ...
1
vote
1answer
18 views

What to do if the righthand of a constraint is a variable when solving Linear programs?

I'm starting to solve linear program exercises with the Simplex method. $$max \ (3x_1-x_2)$$ $$\begin{cases} x_1-x_2 \le 3\\ 2x_1\le x_2\\ x_1+x_2\ge 12\\ x_2 \le 10\\ x_1,x_2 \ge 0 \end{cases}$$ I ...
1
vote
1answer
46 views

Explicit solution of linear program: minimize $c^T x$ subject to $Ax = b$

This is the given question in a textbook I am following. I will paste the solution below which I do not understand: I am a little hazy on linear algebra theory, so I don't fully understand how the ...
2
votes
2answers
47 views

Which mathematical programming method is good for solving the described problem?

I need to solve the following problem. Let's say that there are 3 clients with different time windows. For simplicity let's say that travel distance is always 10 minutes and service time is 30 ...
0
votes
1answer
12 views

Finding the corresponding constrained subspace under a over determined mapping Ax=b, where b is constrained

Suppose that $A$ is a $m\times n$ matrix with m>n, $Ax=b$, and $b$ is constrained in every component, $b_\min^i<b_i<b_\max^i$ for $i=1,\dots,m$. There should be a similar set of constraints for ...
1
vote
0answers
36 views

How to use the simplex method for linear programs?

I believe to be missing something important in the Simplex algorithm, because I can't get it to work. From what I gather, there are three steps per iteration, given a matrix for a linear program in ...