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

learn more… | top users | synonyms

0
votes
1answer
46 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$.
2
votes
0answers
38 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
43 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
66 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
199 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} $$ ...
2
votes
1answer
291 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 ...
1
vote
1answer
29 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
34 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
76 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
38 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
29 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
171 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
64 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 ...
2
votes
0answers
54 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
64 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
20 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 ...
1
vote
1answer
155 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 ...
1
vote
1answer
55 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
1answer
590 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
26 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
327 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
190 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 ...
2
votes
1answer
966 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
114 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
83 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
35 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
29 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
1answer
61 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
148 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
59 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
81 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
346 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
101 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 ...
1
vote
0answers
54 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 ...
1
vote
1answer
239 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 ...
1
vote
1answer
45 views

Reduction to LP

What will be the primal and dual of the following problem/ Given an undirected graph $G = (V,E)$, we want to assign non-negative weights to all the edges of $G$, denoted $\{ x_e \mid e\in E \}$ , such ...
1
vote
2answers
104 views

Optimal production for factories

A firm produces two different models of heavy machines; say (A) and (B). The market demand implies that the final profit of each model is 1200 and 2500, respectively. The production of each car (of both ...
1
vote
0answers
121 views

Linear Programming Problem About Inventory and Cost Minimizing

http://www.endustri.anadolu.edu.tr/zkamisli/ENM%20203/duyuru/ENM203%20Assignment%202.pdf In that link, you can find my question. I'm having trouble about defining decision variables. The objective ...
0
votes
0answers
51 views

Formulating an optimization problem

I am having difficulty formulating a schedule/pay statement in to an maximization problem. Problem: If you are AT work for ${\leq }40$ hours/week your pay/hour is $r$, if $>40$ your pay/hour is ...
1
vote
0answers
16 views

Equivalent System of equations

Let system $$\left\{ \begin{array}{l} {A_1}X = {b_1}\\ a_1^TX = {b_2} \end{array} \right.$$ where the last constraint is dependent to others. Prove that if this system be a feasible system then it is ...
2
votes
0answers
41 views

Calculating second derivative of $g(\alpha) = f(\textbf{y}(\alpha))$

I'm having problems with the second derivative of the function $g(\alpha) = f(\textbf{y}(\alpha))$ (which I will define more precisely below). I tried calculating it myself, could anyone just simply ...
1
vote
2answers
26 views

Linear program dual

We are trying to find the dual of the following linear program. $$ \max_x \ 2x_1 \ + x_2 \ \ \ \ -- (1) $$ such that, $$ x_1 + x_2 \leq 2 \ \ \ \ -- (2)\\ -x_1 - x_2 \leq -4 \ \ \ ...
1
vote
2answers
66 views

Duals of Linear Programs

We are trying to find the dual of the following linear program. $$ \max_x \ ax_1 \ + x_2 $$ such that: $$ v_1x_1 - v_2x_2 \geq b_1 \\ v_1x_1 - v_2x_2 \geq b_2 \\ x_1 \geq 0 \\ x_2 \geq 0$$ ...
1
vote
1answer
4k views

Finding dual of linear programming problem

I have to find the dual to this linear programming problem: Maximize $-15z-\frac{11}{20}w-3a-3b=-132+p$ subject to $y+9z+\frac{13}{10}w+3a-2b=12$ $x-2z-\frac{7}{20}-a+b=4$ ...
1
vote
0answers
58 views

Linear Programming- are my equations correct?

A dairy produces cheese, milk, sour cream, and yogurt. Suppose: Every 100 lbs of cheese requires 2 units of plant capacity, 3 workers, and 7 gallons of culturing additive, and gives $1,500 in ...
1
vote
0answers
34 views

Is the coefficient uniquely determined by the sign function?

Suppose $a\in R^p$, $b\in R^p$, and $||a||=||b||=1$, is it true that if $sign(a'x)=sign(b'x)$ for any $x\in R^p$, then $a=b$, where $sign(t)=1$ if $t\geq 0$ and $sign(t)=-1$ if $t<0$?
1
vote
0answers
52 views

How to solve linear system of equations in 1 and inf-norm?

I have the problem to find a linear program that is equivalent to solving the problem that finds a minimum for $||Ax-b||_1$ and $||Ax-b||_{\infty}$. We defined a linear program as follows: $min_{x} ...
0
votes
1answer
148 views

Maximize two-variable linear function

How would you maximize the following function (with integer domain) $$f(x,y) = a * x + b * y$$ subject to $$c * x + d * y \leq N$$ $$x \geq 0, y \geq 0$$ the constants $a, b, c, d, N$ are known ...
1
vote
1answer
51 views

Having trouble understanding this proposition from my textbook.

I'm seeing this perplexing proposition in my optimization textbook: Suppose an LP $$\max\{z(x)=\vec{c}^{T}x+\bar{z}:A\vec{x}=\vec{b},\vec{x}\geq\vec{0}\}$$ and a basis $B$ of $A$ are given. Then, ...