All Questions
686 questions
1
vote
0
answers
62
views
LP Constraints for Bridgeless Cactus Graphs
When trying to determine the optimal bridgeless spanning cactus graph of a weighted, symmetric graph, I got stuck.
What I do not know how to capture, is
the variable number and sizes of the cycles
...
CommunityBot
- 1
0
votes
0
answers
369
views
Finding a point in the relative interior of the convex hull of a set of integer-valued vectors
Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
- 136
1
vote
0
answers
60
views
On the defect of a flow network
This problem in graph theory was actually motivated by some problems in Theory of Fractals.
To formulate the problem I need to recall some definitions related to flow network.
A flow network is a ...
CommunityBot
- 1
1
vote
0
answers
86
views
Infinite system of equations with finitely many constraints
During my research I have stumbled upon the following issue concerning infinite systems of linear equations. I do not have much practice in such settings, so I am asking you whether the following ...
5
votes
0
answers
162
views
Homogeneous linear and quadratic inequalities
I have a bunch of vectors $b_i \in R^n$ for $i = 1,\ldots,N$ and a bunch of (indefinite) matrices $A_j$ for $j = 1,\ldots,M$. Let's consider the set $S \subset R^n$ of $x \in R^n$ vectors such that
$$...
12
votes
2
answers
350
views
A (reverse)-Minkowski type inequality for symmetric sums
Let $(u_1, u_2, u_3, u_4)$ and $(v_1, v_2, v_3, v_4)$ be vectors in $\mathbb R_+^4$. Is the following inequality true?
\begin{align*}
\left(\sum_{{[4] \choose 3}} \sqrt{u_i u_j u_k}\right)^{2/3} + \...
- 28.6k
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)=\...
- 28k
17
votes
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
1
vote
0
answers
246
views
How to solve a large linear programming problem? [closed]
I have the linear programming problem in $\mathbf x \in\mathbb R^n$
$$\begin{array}{ll} \text{minimize} & \mathbf c^T\mathbf x\\ \text{subject to} & \mathbf A\mathbf x \leq \mathbf b\end{...
1
vote
1
answer
126
views
a linear programming problem
Recently I have a conjecture on decomposing a linear program into smaller ones. I have tested it in Mathmatica by a lot of examples. However, I cannot prove it. I will appreciate if someone can give ...
CommunityBot
- 1
0
votes
1
answer
351
views
QUBO formulation of a discrete-variable Genetic Algorithm optimization problem
I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic real-valued function $f$ depending on a set of parameters $ \theta\...
CommunityBot
- 1
2
votes
1
answer
1k
views
What does the basis of the null space of the constraint matrix of a flow problem look like?
Consider a directed graph $G=(V,\mathbb{A})$ and a set of flow constraints of the following form:
$$ \sum_{(u,v)\in\mathbb{A}}x_{u,v} - \sum_{(v,u)\in \mathbb{A}}x_{v,u} = 0 \forall v \in V$$
...
- 6,051
5
votes
1
answer
394
views
Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$
The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...
- 297
1
vote
0
answers
44
views
In convex optimization we know that the optimum solution is on which hyper plane
We have a standard linear program, I mean a set of inequalities $c_i^Tx\leq b_i$ where $i\in \{1,\ldots ,k\}$ and we want to find $max\{c^Ty| y\in \{\cap \{x|c_i^Tx\leq b_i\}\}$. I put some condition ...
- 19
-1
votes
1
answer
137
views
Does a half plane contain intersection of some other half planes? [closed]
I'm doing research in Optimization and I have found this obstacle in the way.
If we have set of half planes like $c_ix\leq b_i$ where $i\in \{1,\ldots ,k\}$ there is an algorithm(it would be better ...
- 361
35
votes
4
answers
5k
views
Why are optimization problems often called "programs"?
Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...
2
votes
0
answers
283
views
Derivative with multiple summation operators
I have a defined utility function as Eq.(1), and I am seeking the minimized utility subjects to some constraints. The notation used is as following:
\linebreak
$V$ is the set of nodes, $v_i\in V$; $O$...
- 21
0
votes
1
answer
212
views
Is an exact violated inequality constraint met as equal constraint in optimal solution?
We have a solution which does not satisfied exactly one inequality constraint in linear program. The corresponding dual solution is also feasible. Is it correct this constraint is in equal form in the ...
- 54.2k
9
votes
1
answer
295
views
Definition of packing property
Definition 1:
A clutter $C$ is said to have the packing property if $C$ and all of its minors satisfy the König property.
where,
vertex cover of $C$ is a set of vertices that have non-empty ...
- 30.5k
4
votes
0
answers
203
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 $\...
- 4,746
1
vote
0
answers
261
views
Prove that the following set of triples forms a convex polytope
Take $a,\,b,\,c,\,d \in \mathbb R_+$ such that $a+b+c+d=1$. Define:
\begin{equation}
x_1 = \min(a+b,\,c+d)\,,\qquad x_2 = \min(a+c,\,b+d)\,,\qquad x_3 = \min(a+d,\,b+c)\;.
\end{equation}
I would like ...
- 6,406
4
votes
1
answer
4k
views
Can you give me good examples of non-convex functions that are problematic for optimization?
I want to test my extended gradient descent algorithm, whose aim is to handle non-convex problems better. Can you give me some examples of non-convex functions that are hard to minimize via gradient ...
- 3,486
9
votes
1
answer
2k
views
Uniform sampling from general simplex with a twist
This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange.
Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
CommunityBot
- 1
3
votes
0
answers
3k
views
0,1 solution to system of linear integer equations
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
CommunityBot
- 1
2
votes
0
answers
43
views
Partitioning $n$-space based on linear combinations
I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ ...
- 21
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 ...
- 128k
2
votes
1
answer
2k
views
Finding a point farthest away from $k$ points in a polygon
There are $k$ points placed inside a polygon and I am interested in finding a point inside the polygon (not necessarily on its boundary) who's minimum distance to any of the $k$ points is maximized.
...
- 1,228
25
votes
2
answers
2k
views
An Interesting Optimization Problem
You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
- 2,821
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
1
answer
2k
views
Under what conditions does an Integer Programming problem run in polynomial time?
Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...
CommunityBot
- 1
1
vote
1
answer
185
views
Complexity Measures for Mathematical Programming
Question:
Are there any complexity measures in use, that allow one to compare mathematical programming formulations of optimization problems on basis of the number of variables that must be subjected ...
CommunityBot
- 1
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$?
...
- 2,966
1
vote
0
answers
42
views
Computation of sub-gradient for a concave envelope
Let $x_1<\cdots<x_n$ be $n$ points on real line and $g=(g_1,\cdots, g_n)\in\mathbb R^n$ be the scattered data. Let $u_g: [x_1,x_n]\to\mathbb R$ be the linear interpolation of $g_1,\cdots, g_n$, ...
- 345
1
vote
0
answers
81
views
Maximizing sum of homogeneous functions of order one over a polytope
Let $f_i: \mathbb{R}^n\rightarrow \mathbb{R}$ be
concave, increasing (i.e., if $x\geq y$ where the inequality is entry wise, we have $f_i(x)\geq f_i(y)$), and a
homogeneous function of order one for ...
- 393
13
votes
2
answers
664
views
Complexity of a weirdo two-dimensional sorting problem
Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
- 1,083
7
votes
3
answers
278
views
Solve $\inf_{ X: |X| \le a \text{ a.s.}} E \left[ \frac{1}{1+(X-X^\prime)^2} \right] $
I want to solve the following optimization problem
\begin{align}
\inf_{ X: |X| \le a \text{ a.s.}} E \left[ \frac{1}{1+(X-X^\prime)^2} \right]
\end{align}
where $X^\prime$ is an independent copy ...
- 4,361
0
votes
0
answers
64
views
Dense set of functions on manifold with no local optima
Given a smooth manifold $M$ and another $S$, consider a smooth function $\psi: S \times M \rightarrow \mathbb{R}$, and use this to define $\psi_s:M\rightarrow \mathbb{R}$ by $\phi_s(p):= \psi(s,p)$.
...
- 2,099
3
votes
0
answers
105
views
Are there scenarios under which feasibility bilinear programming is easy?
Given $c\in\Bbb R^{n_1},d\in\Bbb R^{n_2}$, $E\in\Bbb R^{n_1\times n_2}$, $A\in\Bbb R^{m_1\times n_1}$, $B\in\Bbb R^{m_2\times n_2}$ $a\in\Bbb R^{m_1}$, $b\in\Bbb R^{m_2}$ and $t\in\Bbb R$ we know ...
- 13.9k
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 4,713
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 ...
CommunityBot
- 1
2
votes
0
answers
80
views
Making a polyhedron integral by selecting value for a specific co-ordinate of constraint vector
I am currently trying to solve a binary integer programming(maximization) problem, where the first row of the constraint matrix corresponds to the constraints on the total number of 1's in the vector ...
- 123
1
vote
0
answers
20
views
Calculating Cost-Optimal 1-Factors in Digraphs
I need to find a cost-optimal 1-factor in a positively weighted, directed, regular graph $G(V,A)$ without antiparallel arcs, i.e. given $$\text{deg}_{\text{in}}(u)=\text{deg}_{\text{in}}(v)=\text{deg}...
CommunityBot
- 1
2
votes
0
answers
105
views
Optimization over a convex cone generated by a set is equal to optimization over the set
Within my research I found an important doubt and that prevents me from advancing, the context of my doubt is as follows:
We considerer the following optimization problem
$$
\left\{\begin{array}{cl} \...
- 159
1
vote
1
answer
111
views
Optimal "Generalization" of Polylines
This question is inspired by a lossy compression technique for polylines, namely to identify a subset of the points of polyline $\mathcal{P}$, whose removal yields a polyline $\mathcal{Q}$ within a ...
- 151k
0
votes
1
answer
203
views
Maximizing sum of a product of logs
I came across the following note in a paper I'm reading and don't understand how it was derived.
$\max_{\alpha_\ell}\sum_\ell^L\beta_\ell\log\alpha_\ell$ such that $\sum_\ell^L\alpha_\ell=1$ and $\...
- 24.8k
10
votes
0
answers
722
views
Fractional Matching version of Hall's Marriage theorem
Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...
- 109k
2
votes
0
answers
344
views
Linear programming with an infinite matrix
I would like to solve the following infinite linear system subject to $x_i \ge 0$ that minimizes $x_3$.
The third column contains no additional nonzero values beyond what is shown. Though the first ...
4
votes
3
answers
200
views
Maximizing a pseudoconcave function in a box
I am trying to solve the problem:
$\max_{\boldsymbol{s}\in\mathbb{R}^{n}} \frac{\sqrt{\boldsymbol{a}^{T}\boldsymbol{s}+\alpha}}{\boldsymbol{b}^{T}\boldsymbol{s}+\beta}\\
\text{s.t} \;\;0\leq s_{i}\...
- 1,517
1
vote
1
answer
2k
views
minimum of convex function in different variables [closed]
Let $g_1,g_2$ be convex functions defined over $[0,1]$, and let $f:[0,1]^2 \rightarrow\mathbb R$ such that
$$f(x,y)=\min(g_1(x),g_2(y)). $$
I wish to know whether $f$ is convex. I do suspect that $f$ ...
- 53.3k
1
vote
0
answers
40
views
Linear cost traveling salesman heuristic
I have a sequence of points $y_1,\ldots,y_n\in \mathbb{R}^3$ and want to approximately minimise
$$
\sum_{i=1}^{n-1}|y_{\pi(i)}-y_{\pi(i+1)}|
$$
by choosing a permutation $\pi$ of $\{1,\ldots,n\}$.
I ...
- 435