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

learn more… | top users | synonyms

0
votes
0answers
42 views

extreme points and representing

$$X=\{(x_1,x_2)^T : x_1-x_2\leq3, 2x_1+x_2\leq 4, x_1\geq -3\}$$ Find all extreme points of $X$, and represent $x^*= {0\choose1}$ as a convex combination of those extreme points. I sketched it out ...
0
votes
0answers
39 views

L_1 norm optimization as a sequence of linear optimizations?

Does someone know of numerical methods to approximately solve ${\bf x_0} = \min_{\bf x}\{ \left\|\bf Mx - b\right\|_1\}$ by using some sequence of linear optimizations? Links or ideas are both ...
0
votes
0answers
28 views

Computing a lower bound for the minimal componentwise distance of vertices of polyhedra

Let $A$ be a matrix in $\mathbb{R}^{m \times n}$ and let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a polytope. I want to compute a lower bound on the minimal componentwise distance of two ...
1
vote
0answers
85 views

Linear programming optimization problem formulation

I need help in formulating an optimization problem. I have a system of equations as follows: $c_1x_1+c_2x_2+c_3x_3=1$ $b_1x_1+b_2x_2+b_3x_3=1$ $a_1x_1+a_2x_2+a_3x_3=1$ In my case the ...
0
votes
1answer
23 views

Why is a local min also a global min for convex functions?

As the title states, for an unconstrained minimizaton problem, of a convex function, why is it that the local minimum is also the global solution?
2
votes
1answer
36 views

How does the Simplex method handle test ratios with zeros?

I've been running into an issue choosing a pivot when there are constraints with an RHS of zero. It appears that sometimes you should include zero test ratios when searching for the minimum test ...
2
votes
2answers
53 views

Integer Linear Programming

Without using a computer, I have to solve the following integer linear programming:$$\min \quad x_1+x_2+x_3$$ $$\operatorname{sub} ...
0
votes
2answers
25 views

If $\phi$ is injective linear map $\mathbb{R}^r \rightarrow \mathbb{R}^s$ then $Im \phi$ is closed in $\mathbb{R}^s$

My optimization theory handbook says that If $\phi$ is injective linear map $\mathbb{R}^r \rightarrow \mathbb{R}^s$ then $Im \phi$ is closed in $\mathbb{R}^s$, where $Im \phi$ denotes image of map ...
1
vote
1answer
49 views

Prove a property of primal-dual problems

When I was studying the computation aspects of quantile regression, I consulted some linear programming book and found an interesting property as follows: If the primal problem have unbounded ...
0
votes
1answer
34 views

$ \mathbb{F} = \{x \in \mathbb{R}^n:Ax=b\}= \mathbb{F}_r=\{x \in \mathbb{R}^{n}:A^{(r)}x=b^{(r)}\}$

Show that these two sets are equal. $A$ is an $m\times n$ matrix of rank $r$, $b \in \mathbb{R}^m$. $A^{(r)}$ denotes an $r\times n$ matrix with $r$ linearly independent rows of $A$ and $b^{(r)}$ is ...
0
votes
0answers
43 views

Systematic Gaussian elimination on a binary matrix?

I am trying to understand the mathematics behind the lights out puzzle (http://mathworld.wolfram.com/LightsOutPuzzle.html). There's a very helpful webpage at ...
0
votes
0answers
72 views

Converting nonlinear program into linear program

Consider the following nonlinear optimization problem \begin{align} \min \quad c^Tx &+ f(d^Tx)\\ \text{s.t.} \quad Ax &\geq b\\ x &\geq 0 \end{align} where $$ f(y) = \begin{cases} -y+2 ...
0
votes
0answers
13 views

A basic solution to a linear program

I know that with an objective function of two variables, the basic solutions to a linear programming problem are the points where the constraints intersect in an xy-graph. But, if we are given an ...
2
votes
1answer
32 views

Constructing a newton sequence

How may I construct the newton sequence for the following: $(1) f(x_1,x_2) = x_1^4 + 2x_1^2x_2^2 + x_2^4$ with $x_0 = (1,1)$ and $x_0 = (1,0)$ $(2) f(t) = t^4 - 32t^2$ and $t_0 = 1$ To find ...
0
votes
2answers
39 views

Transpose notation question

In a course I am undertaking, I was exposed to the following notation for Taylor's theorem: Fix $x^∗ , x ∈ \mathbb{R}^n$ and assume that $f : \mathbb{R}^n → \mathbb{R}$ has continuous first and ...
0
votes
1answer
39 views

Convolution Properties

I have a quick question about certain algebraic properties of convolution. If I have 3 functions $f(x)$, $g(x)$ and $h(x)$, is the following true? $\Big[ f(x) . g(x)\Big] \circ h(x) = \Big[f(x) \circ ...
1
vote
1answer
37 views

Lowest upper bound for linear system?

Assume you have an under-determined linear system $AX=B$ where you have more variables than constraints. It is also known that $X>0$ (element-wise). How can you determine the (scalar) lowest ...
0
votes
0answers
37 views

Linear Programming problem - Packing Trucks Objective Function

I'm learning about linear programming and I want to see if it's applicable to a problem I'm trying to solve (one that's probably been solved many times before). I'm having trouble writing a good ...
0
votes
0answers
22 views

Linear System with non zeros count constraint

I trying to solve a simple linear system: $Ax=b$ But with constraints like: $\sum{x_i}=S$, Usually S = 1. $L \le x \le U$, Lower & Upper bounds (usually $0 \le x \le 1$) And "Maximum count of ...
0
votes
1answer
49 views

Prove that optimal solution is an extreme point in LPP.

While proving this I have proved that Optimal solution cannot lie inside the feasible set and that each supporting hyperplane to a set bounded from below (which is the case as in LPP we can always set ...
2
votes
1answer
29 views

What's a basic solution, and how do we find them?

I've just started learning linear programming, and for some reason, have run into a question about something that isn't mentioned in the first chapter (and we're supposed to answer these questions ...
2
votes
2answers
69 views

When change making problem has an optimal greedy solution?

A well-known Change-making problem, which asks how can a given amount of money be made with the least number of coins of given denominations for some sets of coins (50c, 25c, 10c, 5c, 1c) will ...
4
votes
1answer
66 views

Maximum / Minimum Question with 3 Variables?

I seem to be stuck in this problem, would need your help! Question: Assume I have : 147 of x, 174 of y, 238 of z A different amount of x, y ...
0
votes
1answer
24 views

Nonnegative solution to underdetermined linear system

I would like to show that the underdetermined system $Ax=b,\; x\ge 0$, with $b$ being a positive vector and $A$ being a binary matrix, has at least one solution. I've seen several other related ...
1
vote
0answers
89 views

Conversion into linear program

I have an optimisation problem with decision variables that are multiplied with another (a weighted average is calculated). I'd like to convert it into a linear program. I found this link that ...
0
votes
1answer
29 views

Maximizing the number of zero entries in a linear combination of matrices

I was wondering if there exists an algorithmic way of solving the following problem. Let's say you have a bunch of square $N\times N$ matrices (call them $M_i$), and you want to form a linear ...
0
votes
1answer
27 views

Lexicographic Pivoting Rule: Why does that work?

On purpose, I do not write details about it, because I am interested in the intuition and not the details. But if someone asks for it, I can do that. So my question: Could anyone help me with the ...
0
votes
1answer
30 views

Prove that $b_{\perp}^{T}b_{\parallel}=0$

If $A \in \mathbb{R}^{mxn}$ then the unique expansion of every $b \in \mathbb{R^{m}}$ is $b =b_{\perp}+b_{\parallel} $. Prove that $b_{\perp}^{T}b_{\parallel}$. Comment: Saying that they are ...
1
vote
0answers
130 views

Linear program for way optimization with unusual constraints

I've just finished the lecture "Introduction to Optimization", so I know something about linear programming, and came across the following game on lumosity.com: The goal of the game is to pick up ...
1
vote
0answers
16 views

refomulation of an optimization problem

I have written a program for optimizing a set of generators. And I need to reformulate this problem, to include additional generators and constraints. I have hourly price and cost data and need to ...
0
votes
0answers
125 views

Positive/Negative Definite Bordered Hessian?

I understand how to check a function for concavity and convexity using the Hessian matrix and the rules for the determinants of the leading principal minors. I understand if these rules are violated, ...
0
votes
0answers
18 views

maintaining monotonicity in an optimization problem

I have written a program for optimizing a set of generators. I have hourly price and cost data and need to figure out when a generator should run or just stay off. I describe the problem in more ...
1
vote
0answers
25 views

Why does the simplexmethod 'break up' - unbounded, LP program, very basic problem

I've calculated a very, very basic LP problem: with >= "greater or alike" and <= "smaller or alike" max x + 2y 4x + 3y >= 12 x <= 4 ...
0
votes
2answers
60 views

How to find on each face of a polyhedron one point?

We have a polyhedron in $\mathbb R^n$ generated by the intersection of a collection of finete hyperplanes or the convex hull of the set of vertices. My question is: Is there any algorithm for ...
0
votes
1answer
79 views

Show both relaxations of boolean LP give equal lower bounds

Given the boolean LP: $$\text{Minimize}\;\; c^Tx$$ $$\text{Subject to}\;\; Ax \leq b$$ $$\hspace{57mm} x_i(1-x_i)=0\;\; i=1,...,n$$ Show that the LP relaxation: $$\text{Minimize}\;\; c^Tx$$ ...
0
votes
1answer
15 views

Finding the intersection between 2 lines using matrices

My professor uploaded some notes, and there's a step in his explanation of a Linear Programming Problem which I do not understand. He takes 2 lines and converts them into matrices in order to find the ...
1
vote
1answer
28 views

Primal of Dual of LP problem

Given that the following relation holds: $$\begin{align*} &\textbf{Primal problem} \\ &\max Z = c^Tx \\ &s.t. \\ &Ax \leq b \\ & x \geq 0\end{align*}$$ $\Longrightarrow$ ...
0
votes
0answers
21 views

Duality of Linear Program

Formulate the dual of the following linear problem: Min $\sum$ $\sum$ $c_{ij}$ $x_{ij}$ s.to $\sum$ $x_{ij}$ - $\sum$ $x_{ji}$ = 0, $\hspace{5mm}$ $x_{ij}$ >= $l_{ij}$ and $x_{ij}$ $\leq$ $u_{ij}$ ...
0
votes
0answers
12 views

Showing that every extreme point of the set of solutions of the standard form of constraints of any L.p.p. is a basic feasible solution

Let $\vec y$ be an extreme point of the convex set of solutions of $A \vec x=\vec b $ where only the solutions of $\vec x(\in \mathbb R^n)$ with all components non-negative are taken ; then I want ...
1
vote
2answers
53 views

Represent if-else or OR condition in a linear equation (optimisation with simplex algorithm)

I would like to write some linear equations and inequations to state that the sum of all possive x - C is smaller than L. As my ...
3
votes
0answers
68 views

A basic question related with the solutions of linear programming problems

I have to select one option from the problem statement given below. Which of the following statements is true in case of linear programming. $1$: An optimal solution exists at extreme points of a ...
2
votes
0answers
52 views

Lagrange Multipliers for linear functionals

Say I have a Banach-space $X$ and linear (!) functionals $f,g$, and I'm trying to solve the constrained optimization problem $$max~f(x)\quad s.t.~g(x)= 0,~\Vert x\Vert\le 1.$$ Suppose I can show ...
0
votes
1answer
20 views

Does optimal solution always occur at a vertex?

Is it true that if LP $ \text{max} \{c^Tx \ | \ Ax \leq b \}$ has an optimal solution, then $\exists$ a vertex which is simultaneously an optimal solution for LP? I know this works for LP of a ...
0
votes
0answers
35 views

LP in standard form

I don't know how to properly named this question but here it goes: Let $x, c \in \Bbb{R}^n$, $b \in\Bbb{R}^m$, $A \in \Bbb{R}^{m \times n}$. Consider LP in the form: min $\{c^tx : Ax = b, x \ge 0\}$ ...
0
votes
1answer
39 views

Non-negative solution to a underdetermined linear system

I have an underdetermined linear system (more unknown that equations) Ax=b where both b and x represent probabilities. Im currently using ALGLIB (rmatrixsolvels) to find a least square solution but ...
0
votes
0answers
32 views

Find all optimal solutions by Simplex

Let "stable operation" be an operation on a simplex tableau such that the entering variable has a reduced cost of 0. Recall that a pivoting operation will not change the objective value if either the ...
0
votes
0answers
36 views

Simplex minimum ratio test fails on bounded problem

Consider the linear program $\max 3x_1 + x_2 \ @ \\ 3x_1+2x_2 -s_1 = 1 \\ 2x_1+x_2 +s_2 = 2 \\ x_1 \geq 0$ Leting $x_2 = x_2^+ + x_2^-$, introducing slack and solving phase 1 gives $\textbf{x}_b ...
0
votes
1answer
33 views

Linear regression with constrained weights

I have a set of $n$ linear combinations, each with $m$ parameters and desired value $b$. I want to find the set of weights $w$ which minimizes the total equations distances (e.g. the sum of distances ...
0
votes
1answer
15 views

Optimization relaxtion quesiton

I have the following LP relaxation of an integer programme (the programme formed from the set cover problem) minimize $\sum_{j=1}^{m} w_{j}x_{j}$ subject to $\sum_{j:e_{i} \in S_{j}} x_{j} \geq 1$ ...
2
votes
0answers
61 views

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...