All Questions
Tagged with linear-optimization or linear-programming
493 questions
3
votes
1
answer
1k
views
For interior point methods of linear programming, what is the "L" in the computational complexity $\mathcal{O}(n^3 L)$?
My question is about interior point methods of linear programming. Suppose the constraint matrix $A$ has $m$ rows and $n$ columns, and $m<n$. The state-of-the-art methods, like primal dual interior ...
- 6,694
1
vote
0
answers
196
views
Interior point optimisation using big M for L1 norm on linear system using Dikin's Affine method
I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set ...
- 111
5
votes
0
answers
581
views
When is polytope compatible with network flow?
A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
- 747
1
vote
1
answer
240
views
Conditions for differentiability of minima and minimizers of linear functionals?
Let $B$ be a (real) Banach space and $C$ be a compact convex subset of $B$.
For every continuous linear functional $F$ on $B$, define
$V(F)=min_{c\epsilon C} F(c)$ and
$S(F)= { \lbrace c \epsilon C :...
- 60.5k
1
vote
0
answers
1k
views
Robust optimization in matlab using fmincon [closed]
I am trying to implement the following optimization (from this paper) in Matlab using fmincon:
$\min_\omega\omega'\Sigma\omega$ subject to $\min_Ur_p \geq r_0$
where $\Sigma$ is a positive definite ...
CommunityBot
- 1
4
votes
4
answers
703
views
efficient way to compute the inversion of the following matrix
Hi, there
I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special ...
- 2,205
2
votes
1
answer
1k
views
Finding integer points inside of a parallelogram
Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...
- 12.3k
1
vote
0
answers
256
views
Equal maximum and minimum in a large-scale linear programming
For a linear optimization of an integral (with integral constraints), I perform a linear programming for the equivalent series. Maximum and minimum of the LP problem tend to be equal as I increase the ...
CommunityBot
- 1
2
votes
0
answers
39
views
In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?
I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
- 6,210
2
votes
1
answer
689
views
Why does the LP Formulation of the MST Problem need Topology Constraints?
I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST
In the internet I only could find the LP ...
- 46
2
votes
0
answers
163
views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
- 501
1
vote
2
answers
306
views
Name of operations on two vectors
Suppose we have two vectors $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$.
I could define the mapping
$$
T: \mathbb{R}^n\times \mathbb{R}^m \rightarrow \mathbb{R}^{n\times m}
$$
as follows
$$
T(x,y) = ( ...
CommunityBot
- 1
0
votes
2
answers
244
views
Rewrite optimization objective
Hi,
I wanted to ask, under which conditions can one rewrite the optimization objective
$\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$
as
$\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$
I have particular ...
- 3,934
1
vote
1
answer
296
views
Deducing Linear Inequalities
Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form
$X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$
with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...
- 185
2
votes
1
answer
227
views
Arrangements of hyperplanes
Fix $n>0$ and $X\subseteq\mathbb{R}^n$. A function $f:X\longrightarrow\mathbb{R}$ is linear if it is of the form
$$
f(\bar{x})=a_1x_1+\ldots+a_nx_n+b
$$
for some $a_i,b\in\mathbb{R}$.
Suppose we ...
- 73.1k
1
vote
1
answer
4k
views
What does "Vertex Solution" mean?
Hello!
I come across the word "vertex solution" in the context
" We can also assume that x and y are vertex solutions,so that the sequence {x,y} remains in a finite set."
Could anybody know any ...
- 3,934
0
votes
0
answers
104
views
Big eigenvalues of a special stochastic matrix
Given a matrix $M$ of size $n\times n,$ we write its different eigenvalues by $x_1,x_2,\ldots,x_m$ with $m\leq n$ such that $|x_1|>|x_2|>|x_3|>\cdots|x_m|,$ and call $x_2\doteq |\lambda_2|(M)....
- 105
5
votes
1
answer
3k
views
Maximizing supermodular functions
I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k .
I am wondering if anyone can give me more information about a ...
2
votes
0
answers
63
views
Put positive polynomial in finite intersection of half-spaces
This is a cross-posting of a MSE question (which did not attract any attention there so far).
Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, ...
CommunityBot
- 1
3
votes
2
answers
792
views
complexity of finding optimal matchings of given fixed size
It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...
- 286
4
votes
1
answer
8k
views
Detection of Redundant Constraints
Suppose I pose the following query to a constraint logic programming
system:
?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3.
Are there systems that would recognize the last inequality as
...
CommunityBot
- 1
1
vote
2
answers
1k
views
Efficient algorithm finding 'a' solution of system of linear inequalities
I'm working on rational number field $\mathbb{Q}$.
Is there an efficient algorithm finding a solution of system of linear inequalities?
In many computer algebra systems like Sage or Maple,
there ...
- 11
0
votes
1
answer
2k
views
Find edge weights that fit given node weights
Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes.
Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...
- 1,083
3
votes
1
answer
4k
views
Schur complement and negative definite matrices
Hello,
My question regards to the Schur complement lemma. Consider the matrix $M=\left( \begin{array}{cc}
A & B\\\
B^T & C \end{array}\right)
$.
According to the lemma $M\geq0$ iff $C>0$ ...
- 155
1
vote
0
answers
126
views
Matrix Minimax problem
I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The $M_k$...
- 4,829
4
votes
2
answers
1k
views
Set Cover:Greedy vs LP
Hi
Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches?
thanks
- 183
1
vote
1
answer
640
views
Approximate Set Cover Problem by Rounding
Here is the simple algorithm for approximating set cover problem using rounding:
Algorithm 14.1 (Set cover via LP-rounding)
Find an optimal solution to the LP-relaxation.
Pick all sets $S$ for ...
CommunityBot
- 1
0
votes
1
answer
2k
views
Finding linearly independent columns of a large sparse rectangular matrix
I have a problem that necessitates solving a large non-negative least-squares
problem. My matrix A is large, sparse, highly rectangular (num rows >> num cols)
and nearly binary. However, A is not ...
- 30.1k
1
vote
2
answers
444
views
Levenberg-Marquadt near the minima for non-zero-residual problems
I'm using the LM algorithm to do gradient descent in a model fitting context. I'm minimizing:
$$
c(x) = \sum ( f_i(x) - y_i )^2
$$
I'm noticing that after a few steps when I'm close to the minima, I ...
- 561
0
votes
0
answers
103
views
Gauss-Newton for quotient functions
I'm optimizing a function of the form
$$
\sum \frac{ \|\mathbf{f_i}(x)\|^2 }{ g_i(x)^2 + h_i(x)^2 }
$$
where $x$ is a real vector, $\mathbf{f}(x)$ is a real vector, and $g(x)$ is a scalar. My first ...
- 561
1
vote
1
answer
769
views
Results for minimizing the norm w.r.t a unitary matrix
Suppose $x \in \mathbb{R}^n$, $B,U \in \mathbb{R}^n\times\mathbb{R}^n$ and $U$ a unitary matrix. Define $g_{U}(x) = || BUx||$ where $||.||$ is some norm or norm-ish function on $\mathbb{R}^n$ (not ...
- 3,059
0
votes
0
answers
194
views
A linear program related question
Dear all, recently, I encountered the following problem. It is closely related to the order of growth for UMD constants of all $n$-dimensional Banach lattice.
Let $\alpha^k \in (\alpha_1^k, \alpha_2^...
- 769
0
votes
0
answers
79
views
Computing maximum point for minimal function of a family of linear functions
Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such that:...
- 11
0
votes
1
answer
130
views
Cascading minimization problems
Hi all. Suppose I have a linear programming problem on the vector variable $x$ that has many solutions and let $U$ be the set of these solutions. Suppose I have a second LP problem on $y \in U$. ...
- 3,934
3
votes
2
answers
10k
views
linear programming with OR restrictions
Hi all. I have a linear program with the restriction that every variable can be zero or greater than or equal to a positive constant. That is:
minimize: $w^Tx$
subject to: $Ax=b$, $Cx \le d$ and for ...
- 57
0
votes
2
answers
891
views
Find both maximum and minimum values in linear programming problem
Hi all. I have a linear programming problem where I need to find both maximum and minimum values of the objective function. The optimal points are not relevant.
Is there an efficient way to do so?
- 96.4k
1
vote
2
answers
242
views
what method can I employ to solve this optimization problem which involves \min?
The optimization problem is:
maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N \log\left(a_{2,i}+\frac{b_{2,i}}{c_{2,i}+d_{2,i}x_i}\...
- 101
0
votes
1
answer
205
views
SDP Algorithms/ maximally complementary solutions
Hello,
I was wondering if there are algorithms for (linear) Semidefinite Programs (SDP) out there, that converge towards a maximally complementary solution, even if strict complementary does not hold.
...
CommunityBot
- 1
1
vote
2
answers
134
views
LP/QP with not-so-constant linear constaints
I have an otherwise standard LP or PSD QP problem as below:
$\min\limits_x {c}' x$ subject to $Ax\leq b$
or
$\min\limits_x \frac{1}{2}{x}' Qx + {c}' x$ subject to $Ax\leq b$
the only exception ...
- 54.2k
0
votes
0
answers
783
views
LP relaxation for ILP\IP (integer linear programming)
I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
3
votes
1
answer
533
views
Solving a system of linear inequalities
Consider the following system of inequalities:
$Ax=b$;
$x\geq 0$;
A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. How this system can be solved without ...
- 276
2
votes
1
answer
6k
views
sum of maxima vs the maximum of the sum
Consider the following integer program
$$
\begin{align}
\max &\sum\nolimits_{i}\sum\nolimits_{j} U_i(j)\cdot x_{i,j}\\
\text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant c_j,&...
- 1,253
4
votes
2
answers
4k
views
Dual Norm For Sum of 2-Norms
What is the dual of a norm that is the sum of two-norms? Specifically, say we have the following norm for $\mathbf{x}\in \mathbb{R}^n$ and $\mathbf{A}_i \in \mathbb{R}^{m \times n}$
$\|\mathbf{x}\| = ...
- 9,486
1
vote
2
answers
660
views
constructing a curve dividing two sets of points
Lets assume I have two sets of points, each characterized as being "A" or "B", respectively, that are in a Euclidean plane. Theoretically these two sets are samplings from a space that has ...
CommunityBot
- 1
2
votes
3
answers
2k
views
Efficient Algorithm For Projection Onto A Convex Set
Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem:
$\underset{\mathbf{p}}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2
\;\;
\...
- 3,934
2
votes
0
answers
230
views
Consistency of a system of linear equations
I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
- 221
0
votes
1
answer
226
views
Continuity of Lexicographic Minimum Solution of a parametrized LP problem
Given a parametrized LP problem
find x, that minimizes F*x
such that Ax <=Bt+D
where t is a parameter.
And suppose C(t) is a set of all optimal solutions of LP with parameter t.
Let x_L(t) be ...
CommunityBot
- 1
3
votes
1
answer
347
views
Grading a non-graded poset as squeezed as possible
Here is a curiosity question (motivated by the recent revamp of ranked-poset routines in Sage).
Let $P$ be a finite poset. We look for a family $\left(a_p\right)_{p\in P}$ of real numbers summing up ...
- 33.8k
3
votes
2
answers
3k
views
how to model a linear program with step-like cost function in the objective
I have a large linear program with the following details.
d1 to di are the variables, where di is an integer. The constraints are a series of inequalities of the form
d1 < d3 < d7 < d23 (...
CommunityBot
- 1
10
votes
1
answer
411
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...
- 37.7k