Questions on linear programming, the optimization of a linear function subject to linear constraints.

learn more… | top users | synonyms

1
vote
0answers
47 views

Some problems with a proof of the Farkas Lemma

The following is a proof of the Farkas Lemma that is creating me quite some problems. [I presented the all proof simply to point out the notation used by the author.] My problem is with the last part ...
1
vote
1answer
47 views

Does the identity matrix adapt to any other matrix?

So I have a matrix of the form $X=AX+B$ Where $X$ is a 3 by 1 column matrix, $A$ is a 3 by 3 matrix and $B$ is a 3 by 1 column matrix. (Notice that I am talking about Leontief input-output). So I ...
2
votes
1answer
53 views

Iterative update of pseudo inverse solution

I have an overdetermined linear problem of the form $A x = b$, which is solved in least squares sense using the Moore–Penrose pseudo invers. The issue now is, that over time additional constraints and ...
0
votes
1answer
39 views

Regression with equally spaced set

I'm working on an algorithm (written in Python/Cython, but it reads like pseudo-code) that estimates the gradient of each point in noisy data, using a variable window size. It's working very well, but ...
1
vote
0answers
40 views

Understanding the beginning, while, sum, and end of an algorithm

My problem is as follows: \1brace procedure sum (n: positive number) sum:=0 while i < 10 begin sum :=sum + i end output(sum) \rbrace Then, I have the following choices to select from as ...
1
vote
0answers
132 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
0
votes
1answer
24 views

Sufficient conditions for relaxed integer programs to have integer solutions.

Suppose we are given an integer program and we remove the integrality constraints to get a relaxed linear program. Are there a set of sufficient conditions on the form of the linear program, (e.g. ...
0
votes
0answers
18 views

How to check if steepest gradient method will converge?

So I have this function $ f(x,y) = x^4 - 2x^2 +x + 4y^2 $ and I want to know if the steepest gradient method will converge if I pick an arbitrary point and apply said method. My initial thought ...
0
votes
1answer
32 views

How to check linear independence

How can I check the linear independence of my variables? I have this system $Ax=b$ where $A$ is a $N \times 4$ matrix. I want to check the linear independence between the 4 variables in matrix $A$.
1
vote
0answers
27 views

Showing a Hermitian preserving map is not necessarily positivity preserving?

Say I have a linear map, which is not positivity preserving $$\phi: \mathscr H \to \mathscr H$$where $\mathscr H$ is the set of $n \times n$ Hermitian matrices. Then does there exist a positive ...
1
vote
0answers
29 views

KKT conditions and feasibility of problems (P) and (D)

Let following linear problems: Primal Problem: \begin{eqnarray*} \textrm{Min}\quad c^T x & & \\ \textrm{s.t.}\quad Ax & \geq & b \end{eqnarray*} and its dual problem: ...
2
votes
1answer
31 views

Finding subgradients

How would I find the subgradients of this : $$ f(x) = \max_{i=1,\ldots,n} a_i^Tx + b_i$$ I'm new to subgradients and any hint on how to start this would be useful for me.
0
votes
0answers
22 views

Dual of Linear Program

I was wondering what a $symmetric $ dual is. For example, the following is supposed to be a symmetric primal and dual form of LP. Primal : $$ \max c^Tx$$ subject to $$ Ax \le b $$ $$x \ge 0 $$ Dual: ...
0
votes
0answers
73 views

Application of Farkas' Lemma

Suppose matrices $A_{p\times n}$ and $B_{q\times n}$. Use Farkas' Lemma to prove that one and only one of below systems has solution: $$(1)\qquad AX<0,\quad BX = 0, \quad X\in\mathbb{R}^{n} $$ ...
0
votes
0answers
29 views

Finding dual LP of a graph optimization problem

This is homework, so please no full solutions. I really am stuck at only one small place. So, this is a graph thingy with a bipartite graph with bipartition $L,R$. Each vertex has a "requirement" ...
2
votes
1answer
69 views

Converting if else constraints into linear ones

I have the following two constraints: $$ x_1 \leq x_2 \leq x_3 \qquad \mbox{if } x_1 \leq x_3 \\ x_1 > x_2 > x_3 \qquad \mbox{otherwise} $$ Is there a way to get rid of the two conditions and ...
0
votes
1answer
26 views

Set up for matrix solutions

I've haven't touched linear algebra in a while so I'm sorry if this seems simple but I did a google search and I am still confused. I have to find a solution to the following set of equations: ...
1
vote
0answers
32 views

Modeling 4 people going to same place over 3 different places for at least 5 days

I'm trying to model a linear programming task with the condition 4 people going to the same place among 3 different places for at least 5 days. I have the variables for the time spend each person in ...
0
votes
1answer
58 views

Transform OR clause to algebraic equations (linear programming)

So basically my question is: does it exist a way to transform the clausure (a or b or c) into one or more algebraic equations giving as a result 0 or 1 AND that can be included in a linear programming ...
0
votes
1answer
28 views

Definition of an active hyperplane

We are learning about the Geometry of Duality in Linear Programming, and my prof uses the terminology active hyperplane. I'm wondering what the formal definition of this is. I can't seem to find any ...
0
votes
0answers
24 views

Finding dual of incredibly complex LP; any trick?

This is homework, so only hints please. This is about a LP relaxation of the minimum cost perfect matching problem, with another constraint that shrinks the solution space in a way that a lot of ...
0
votes
1answer
65 views

Weak form for Linear Dynamic Wave Equation of Dirichlet/Neumann's boundaries?

I have a linear problem with double derivate of space and time, which has Dirichlet boundary condition in $(1)_{2}$ and Neumann's boundary condition in $(1)_{3}$: \begin{equation} \frac{\delta^{2} ...
1
vote
0answers
41 views

Fitting a sine using linear regression

If I have two functions $s_1 = A_1 \sin(\theta+\phi)$ and $s_2 = A_2 \cos(\theta+\phi)$ is it possible to fit a sine or a cosine using linear regression? I usually have much less that a period ...
0
votes
0answers
37 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
1
vote
0answers
53 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
1
vote
0answers
17 views

elements of oriented matroids belonging either to positive circuits or positive cocircuits

I need to prove the following, which seems trivial because it follows from the Farkas lemma (you may know this as the 3 or 4 painting lemma). Can someone show me how to prove this, please? I'm a bit ...
0
votes
1answer
59 views

Solve linear programming given access to an oracle

This question is about designing a polynomial time algorithm for linear programming given access to an oracle outputs YES if and only if $\{\vec{x}\ |\ A\vec{x} = \vec{b}, \vec{x}\geqslant ...
0
votes
0answers
22 views

Converting an LP to a standard form

I have an LP that is : $ max_{x,y,z} 3x -y +z $ subject to $-1\leq x \leq 1 $ $-1 \leq y\leq 1 $ $x+y+z =1 $ The answer seems to be : Substitute $x:=a-1 $ $ y:= b-1 $ $ z:= c-d $ where $ ...
1
vote
1answer
37 views

Linear Programming Convexity Proof

Suppose a linear programming problem in standard form has as constraints $A \underline{X} = b$ and $\underline{X} \geq \underline{0}$, where $\underline{A}$ is an $m \times n$ matrix and ...
0
votes
0answers
42 views

Integer programming with pairwise relaxations: optimality?

In David Sontag's thesis [1] (page 11, 3rd paragraph from the end), it is mentioned that "Most previous linear programming approaches to approximate inference optimize over the pairwise LP ...
0
votes
1answer
101 views

Finite optimal value for a linear program with unbounded feasible region.

I read this problem in CLRST : Show that a linear program can have finite optimal objective value even if the feasible region is not bounded. Now all the cases I could think of where such a thing ...
0
votes
0answers
23 views

String satisfying the condition

Given $N$, $A_0$, $B_0$, $L_0$, $A_1$, $B_1$ and $L_1$, find a sequence S consisting only of characters '$0$' and '$1$'(a total of N characters) such that: The number of '$0$'s in any consecutive ...
1
vote
0answers
9 views

Lp optimality proof [duplicate]

i have a general question. if there is a general LP problem $c^Tx$ s.t $A\cdot x \le b$, and $x \ge 0$ and assuming that the components of $c$ are non-zero entries then how can I prove that when $x$ ...
3
votes
1answer
92 views

Largest Circle in a Polygon

My polygon is given by $P=$$\left\{x\geq 0, y\geq 0, 3x-4y\leq 2, 4x+3y\leq 12\right\}$ Now trying to find the largest circle inscribed inside these half-planes. But whenever I formulate it as an LP ...
2
votes
1answer
93 views

Dimension of polyhedron defined by inequalities and rank of implied equalities

I'm looking at "Optimization Over Integers" by Bertsimas and Weismantel and I have a question about one of the examples in the book. I'm getting a conflicting answer and I'm not sure what I'm ...
0
votes
1answer
256 views

Taylor's theorem for vector valued functions

I'm reading about linear and nonlinear programming and on one page I have the following statment (I have highlighted the areas where I have problems and drawn questions for them in the bottom of it): ...
6
votes
1answer
74 views

Why is there n-1 different objects in a n by n matrix game like Bejeweled?

For games that consists of a grid, and is similar to the concept like bejeweled: has an n by n matrix and n-1 different objects. What is the reason for this? Why not have more than n-1 different ...
2
votes
1answer
73 views

What needs to be linear for the problem to be considered linear?

Harry Altman presented an excellent question in a comment here: What needs to be linear for the problem to be considered linear? So is it enough to a have linear objective function or other ...
0
votes
1answer
30 views

Help with a property of a convex function

I'm studying linear and nonlinear programming and on my book I bumped into the following statement: $$\lim_{\alpha \to 0} \displaystyle \frac{f(\textbf{x}+\alpha ...
1
vote
0answers
24 views

Linear programming: can someone explain how the time steps work here?

I'm reading a paper, "A Player Selection Heuristic for a Sports League Draft". In it, the authors have come up with a method to assist you in picking players for a fantasy sports league. I'm having ...
0
votes
0answers
48 views

Simply formulated but hard problem on system of linear equations

When does the below system has a solution? $$AX=B\\ X > 0$$, where $A$ is $n\times n$ symmetric positive definite matrix and $X$ is a $n\times 1 $ column vector. Note: (I'm trying to use Farka's ...
0
votes
1answer
54 views

Integer Programming

I've been having trouble getting started with this problem. Suppose $x_1,x_2,x_3$ are integers $\geq 0$, satisfying $$21.7x_1-18.2x_2-19.4x_3=5.3$$ Then show $$7x_1+8x_2+6x_3=3+10z_1$$. ...
1
vote
1answer
54 views

LP: how to understand Duality and simplex

I am learning about Linear Programming right now.. I learned that we can use simplex to solve linear program and I also learned that every linear problem has a dual problem because of duality.. I am ...
1
vote
1answer
49 views

Help to understand the setting up of this Lagrangian

So..I understand up to step 4..but then there are these things I dont get, to start with , it says on (5) that the utility function depended only on the ratios p1/w p2/w ?? why does it say that? ...
1
vote
0answers
48 views

Strong Duality and Duals of linear programming problem

I have the following problem: $ max_{x,y} \ x + y $ subject to $ 2x + y \leq 1 $ $ x + 3y \leq 3 $ $ x,y \geq 0 $ How to find the dual of this problem using the Lagrangian? I have done the ...
0
votes
1answer
206 views

Prove the dominant strategy of Game Theory

A row $r$ of the payoff matrix is said to dominate a row $s$ if $a_{rj}\geq a_{sj}$ for all $j$ = 1,2,......,$n$. Similarly, a column $r$ of the payoff matrix is said to dominate a column $s$ if ...
0
votes
0answers
62 views

Maximum matching in a non-bipartite graph

The problem is the following; I would like to reach maximum matching in a 2-connected graph, but not in an ordinary way - both of the groups of vertices that we get after the matching should remain ...
0
votes
0answers
175 views

question on linear programming problems in three variables

maximize $3x+4y+2z$,subject to $x+y+z\le12$,$x+2y-z\le5,x-y+z\le2$ where $x,y\ge0$ then which of the following are true 1)the problem has more than one feasible solution. 2)the objective function ...
1
vote
0answers
35 views

Regression/compressive sensing with non-linear constrains where the coefficients are assumed to be integer or binary {0,1}

The following regression problem $$ \mathbf{y} = \mathbf{A}\mathbf{x} $$ where $\mathbf{y}$ is a $N\times 1$ column real vector, $\mathbf{A}$ is a $N\times M$ real matrix where each column ...
0
votes
1answer
127 views

''min $c^tx$ subject to $x^tAx=1$'': is is possible to solve it with Lagrange multiplier or in the scope of KKT?

I find a problem: Minimize $c^tx$ subject to $x^tAx=1$, where $A$ is a positive semidefinite symmetric matrix. But the question obligates to use KKT but I am trying to apply simple Lagrange ...