All Questions
685 questions
4
votes
0
answers
202
views
$\ell^1$-norm minimization duality
I am looking for an explicit description and discussion of the dual of the $\ell^1$-norm minimization problem $\lVert A x\rVert_1\to\min$, where $A$ is a matrix, and $x$ belongs to the $n$-simplex $\...
- 17k
4
votes
0
answers
539
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
- 391
4
votes
0
answers
405
views
maximize non-convex composite function
I want to maximize a composite function over a convex set
\begin{equation}
\begin{aligned}
& \underset{\mathbf{p}}{\text{maximize}}
& & f(\mathbf{p})-g(\mathbf{p})\\
& \text{subject to}...
- 61
4
votes
0
answers
205
views
Basin of Attraction
I have a function $F$ which is defined as follows:
$$
F(x) = \sum_{i=1}^N f(z_i^T x)
$$
where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = \...
- 291
4
votes
0
answers
522
views
Solution of a linearly constrained quadratic programming problem [closed]
What is the solution of the following optimization problem:
\begin{align}
&\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\
&\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}.
\...
- 51
4
votes
0
answers
790
views
Is it possible to use linear programming to solve this problem?
I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group.
Could someone comment on whether this is ...
- 41
3
votes
1
answer
233
views
Min problem on integers
Let $n$ be any integer greater than $2^{10^6}$. Given any $s\le (\log_2 n)/1000$ integers $1=q_1\le q_2\le \cdots q_{s-1}\le q_s=n$. Prove that
$$\min_\ell\left(\sum_{i=1}^\ell q_i\right)\left(\sum_{i=...
3
votes
4
answers
4k
views
Existence of nonnegative solutions to an underdetermined system of linear equations
Similar questions have been asked elsewhere, but I think this is sufficiently different to warrant a new post. I have a particular matrix $A$ and would like to know when the system $Ax = 0$ has at ...
- 491
3
votes
2
answers
437
views
convex polytope integer points
is there a simple proof for the following lemma:
An unbounded convex polytope (defined by linear constraints) has either zero integer points or infinite many integer points.
- 39
3
votes
1
answer
553
views
Calculate the discrete set of points B which are in the convex hull of the set of points A
This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
- 151
3
votes
2
answers
791
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 ...
- 13.2k
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
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 ...
- 221
3
votes
1
answer
184
views
Does there exist energy-minimizing immersions?
This is a cross-post.
Let $M,N$ be $d$-dimensional oriented Riemannian manifolds, possibly with boundary, $M$ compact. Let $E_d:C^{\infty}(M,N) \to \mathbb{R}$ be the $d$-energy, i.e.
$$ E_d(f)=\...
- 6,741
3
votes
2
answers
5k
views
Linear program to maximize the minimum absolute value of linear functions ?
I'd like to compute
$\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$.
where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$.
Can this be solved with a linear ...
- 500
3
votes
1
answer
252
views
Measurable selection for argmin to distance
Let $Y$ be a Banach space and equip $Y$ with the weak topology. Now, let $X$ be a closed, bounded, and convex subset of $Y$ and suppose that the relative (weak) topology on $X$ is metrizable with ...
- 5,405
3
votes
1
answer
152
views
A question about polytopes related to linear programming
Given linear functions $f_1({\bf x}),\dots,f_n({\bf x})$ on ${\bf R}^m$, let $K = \{(a_1,\dots,a_n) \in {\bf R}^n:$ the $n$ halfspaces $\{{\bf x}: f_i({\bf x}) \leq a_i\} $ have nonempty intersection$\...
- 19.7k
3
votes
1
answer
266
views
Strong polynomial algorithm for linear programming
What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?
- 781
3
votes
1
answer
73
views
Maximizing the $\alpha$-moment of a distributution
Given $\alpha$ and constant $\mu$,
$$\begin{array}{ll} \text{maximize} & \displaystyle\int_0^\infty p(x)x^\alpha \,\mathrm d x\\ \text{subject to} & \displaystyle\int_0^\infty p(x)\,\mathrm d ...
- 1,129
3
votes
3
answers
349
views
Sensitivity analysis in conic optimization
I have a conic optimization of the form:
$$\min_x \langle c, x \rangle,\ \text{s.t.}\ Ax = b,\ x \in K.$$
where $x \in \mathbb{R}^{n}$, $A$ is an $m \times n$ matrix, $b \in \mathbb{R}^m$, $K$ is a ...
- 143
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 ...
- 31
3
votes
2
answers
2k
views
Sherali-Adams relaxation
I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...
- 113
3
votes
1
answer
275
views
Uniqueness of l1 minimization
Let $A \in \mathbb{R}^{m \times n}$.
Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to
$\...
- 33
3
votes
1
answer
260
views
Better alternative to solve quadratic programming for large matrices
I have the following problem. Let's say we have $x_{jk}$ it is an expression value of gene $j$ in a sample $k$. It is the average of expression levels across the cell types $s_{ij}$, weighted by ...
- 135
3
votes
1
answer
336
views
Bounding the difference in the value of a strongly convex function at its integer minimum and other integer points
I am currently working on a problem where I have to minimize a $m$-strongly convex function
$$f ~: ~\mathbb{R}^n \rightarrow \mathbb{R}^+$$
over a bounded integer lattice,
$$L = \mathbb{Z}^n \cap [-...
- 379
3
votes
2
answers
792
views
Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed]
I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ...
- 131
3
votes
2
answers
313
views
Uniqueness of fixed points for rational transformations
Background
Let $a,b,c,d$ be nonnegative constants and consider the map $T\colon [0,1]\times[0,1] \rightarrow [0,1]\times[0,1]$ defined by
$$
T(x,y) := \left( \frac{1}{1 + ax + by}, \frac{1}{1 + cx + ...
- 123
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
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 (...
- 31
3
votes
1
answer
261
views
When is the optimum of an optimization problem affine in the constraint parameter?
While working on a variational problem I have reached to the following question:
Let $f:(0,\infty) \to [0,\infty)$ be a $C^1$ function satisfying $f(1)=0$. Suppose that $f(x)$ is strictly increasing ...
- 6,741
3
votes
1
answer
244
views
What importance does the Hirsch conjecture have to Simplex Complexity?
The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...
- 1,826
3
votes
2
answers
331
views
Program to solve Optimization Problem
I have an optimization problem, this problem has linear constraints and nonlinear constraints. I solved the linear part by MATLAB but the nonlinear constraints I could not solve it. I downloaded ...
- 31
3
votes
1
answer
328
views
LP Constraints for Connected Subgraphs of Fixed Size
Question:
how can the connectedness-constraint for a subgraph, that is induced by a proper subset $W\subset V$ of the vertices of $G(V,E),\ |V|=n,\ |W|=m$, be formulated in a $LP$ or $ILP$?
...
- 13.2k
3
votes
1
answer
634
views
Properties of one dimensional null space
Let $\mathcal{G}$ be denote the set of all $3 \times 3$ real symmetric matrices and let $\mathcal{G}^+$ denote the set of all $3 \times 3$ positive semidefinite matrices (see definition).
Let $S: \...
- 31
3
votes
1
answer
397
views
Partially optimal solutions in integer linear programming
Linear programs with a totally unimodular system matrix are known to have an optimal integer point. They are therefore solvable via relaxing the integer constraints to intervals.
An other interesting ...
- 567
3
votes
1
answer
1k
views
Java library for SDP [closed]
People who frequently code semi definite programs, is there any java library for solving sdps? I have tried my luck but all I can find is C/C++ libraries or matlab toolboxes. I can write wrappers to ...
- 263
3
votes
1
answer
357
views
Mathematical Programming with other Algebras than Linear
Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization.
What analogies are there for ...
- 2,383
3
votes
1
answer
138
views
Handling absolute value and other discontinuities in numerical optimization methods that use gradients
Suppose we have difficult peak fitting problems where the the users wish to fit asymmetric peaks to their experimental data by the least squares method. One such function is illustrated below:
Here
$...
- 879
3
votes
1
answer
188
views
Minimize total area bounded by $N$ lines in general position
Suppose we have $N$ lines in general position (any two lines, but no three lines, meet at a point) ($N\geq 3$). Let the smallest bounded region have area $1$. Determine the minimum (or possibly ...
- 141
3
votes
2
answers
262
views
Optimal Kelly criterion for process with N discrete outcomes
I am trying to come up with a generalisation of the Kelly formula for optimal fractional betting but and have hit a roadblock. The Kelly criterion is usually explained via a game that ends in 1 of 2 ...
3
votes
1
answer
296
views
Trying to prove an inequality
I am working on a problem and for that purpose, I need to prove the following inequality. Let $t\in [0,1]$ and set
$$
z_0=1-4t(1-t)\sin^2(4x)\\
z_1=1-4z_0(1-z_0)\sin^2(3x)
$$
I need to show that for ...
- 697
3
votes
2
answers
1k
views
Equality constraints in mixed-integer optimization
Suppose I have a linear mixed-integer optimization problem of the form
$$MIP: min_{(x,y) \in \mathbb{R}^n \times \mathbb{Z}^m} c^\top x + d^\top y \hspace{0.2cm} \text{s.t.} \hspace{0.1cm} Ax+By \leq ...
3
votes
1
answer
2k
views
Maximize a sum of log of sum
For a matrix $c (m\times n)$ of non-negative constants, find values of $\lambda_1, \lambda_2, \ldots, \lambda_n$ that satisfy $\sum_{k=1}^n \lambda_k = 1$, $\lambda_k \ge 0 \, \forall k$ and maximize ...
- 41
3
votes
1
answer
1k
views
Constrained vs Unconstrained Optimization
I'm currently working on an optimization problem with a linear objective with linear and nonlinear constraints, i'm facing difficulties reaching a good solution, so i was advised to move the nonlinear ...
- 31
3
votes
1
answer
956
views
Maximum of a mollified/convolution function
I have a function $f:{\mathbb R}\rightarrow {\mathbb R}_+$ which has a unique maximum at $x=0$. $f$ can be symmetric or asymmetric. I am interested on the mollified-f function
$$\tilde{f}(x)=\int_{-\...
- 39
3
votes
2
answers
2k
views
ILP for minimum edge coloring problem
We know that for a graph $G=(V,E)$, minimum edge coloring is a coloring of
$E$, i.e., a partition of $E$ into disjoint sets $E_1, E_2, \dots, E_k$ such
that, for $1 \leq i \leq k$, no two edges in $...
- 45
3
votes
1
answer
340
views
Name search for special Linear Integer Program
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
$...
- 31
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
1
answer
1k
views
maximization of a quadratic function with a quadratic constraint
I have the following quadratic maximization problem
$\max_{\mathbf X} \quad tr(\mathbf A\mathbf X\mathbf B\mathbf X^H)+tr(\mathbf C\mathbf X)+tr(\mathbf C^H\mathbf X^H)$
subject to the quadratic ...
- 31
3
votes
0
answers
105
views
Techniques for solving linear inequalities
For $n$ real variables $x_1, \ldots, x_n$, I have a bunch of inequalities of form $2 x_i > x_j + x_k$ or $2 x_i < x_j + x_k$, where $i,j,k$ are distinct. My goal is to determine whether this set ...
- 231