All Questions
1,019 questions
1
vote
1
answer
1k
views
convert absolute form into linear programming problem [closed]
I would like to convert this problem into a Linear Programming Problem :
$\min |x|+|y|+|z|$
subject to $x+y \leq 1$
$2x+z=3$.
The solution to this problem is given chapter and here. But I still ...
- 113
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 ...
- 221
18
votes
2
answers
1k
views
The Teichmüller space $T_g$ of a closed riemann surface $S_g$ of genus $g \geq 2$ can't be parametrized by $6g−6$ geodesic length functions
I asked this question almost a month ago on Math SE. After waiting three weeks for an answer or a comment, I opened a bounty on the question in hope that it might get an answer this way. The bounty ...
- 385
1
vote
0
answers
64
views
Maximize discrete harmonic function at given point
Let $n>0$, and let $S_n$ denote the discrete square
$S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
- 621
2
votes
0
answers
299
views
Practical application of envelope theorem for linear programs
Assume that we have solved a (standard) linear program
$$
\text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0,
$$
and would like to know how sensitive is the optimal ...
- 7,182
2
votes
1
answer
3k
views
max-flow at max-cost
I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
- 121
9
votes
2
answers
907
views
When is a mapping the proximity operator of some convex function?
Is there a characterization of mappings $p : \mathbb R^n \rightarrow \mathbb R^n$ which are proximity operators (in the sense of Moreau) of l.s.c (extended) real-valued functions ?
That is, given $p : ...
- 6,853
1
vote
0
answers
55
views
Separation on discrete set
Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ \...
- 61
2
votes
0
answers
64
views
Finding orthogonal basis with constraint
Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$
with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$.
And is there any condition on $V_i,i\leq ...
- 909
2
votes
0
answers
71
views
Existence of probability distribution satisfying upper/lower bounds on events
Suppose we have a finite sample space $S$ and some events $A_1, \dots, A_k \subseteq S$. We would like to put a probability distribution on $S$ so that no element has probability greater than a ...
- 21
5
votes
1
answer
266
views
Extremal Lipschitz convex functions
Let $B_d$ the unit ball in $\mathbb{R}^d$, and let $F_d$ be the set of convex functions with Lipschitz constant at most 1 from $B_d$ to $\mathbb{R}$.
When $d=1$ (so the domain is the just the ...
- 708
1
vote
0
answers
35
views
Concavity of maxima [closed]
Suppose we have the following optimization problem : $\min\limits_x kf(x) + g(x)$ where $f$ is a decreasing convex function in $x$ and $g$ is an increasing convex function. Can we say that $x^*$ is ...
- 11
4
votes
1
answer
345
views
Existence of Nonnegative Solutions of Linear Systems of Equations and Inequalities with particular constraints
Suppose we have an $n \times m$ nonnegative matrix $A$, where each row sums to $1$. I wonder whether there exists an $m \times n$ nonnegative matrix $X$ that satisfies the following constraints:
...
- 49
2
votes
1
answer
201
views
Minimum cover for sets in which each element appears in exactly 2 sets?
Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ...
7
votes
0
answers
1k
views
Closed-form solution of a linear programming question
Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & \...
2
votes
2
answers
438
views
Perturbation of Linear Programs
Consider the linear program,
$$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & Ax \leq b\\
& x \geq 0\end{array}$$
I want to study the sensitivity of the optimal $x^*$ ...
- 275
1
vote
1
answer
96
views
Bounds on the curvature of a sequence of convex functions
Let $\{f_n\}$ be a sequence of (real-valued) smooth convex functions on $[0,1]$, with $f_n(0) = f_n(1) = 0$ for all $n$.
Let $t_n \in [0,1]$ be the minimizer of $f_n$ and assume that $M_n:= f_n(t_n) ...
- 1,731
0
votes
1
answer
204
views
Is the linear production game a convex game?
In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem.
Does anyone know if the LPG is a convex ...
- 17
1
vote
1
answer
391
views
Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...
- 2,689
7
votes
2
answers
605
views
Gaussian and the convex hull of moment curves
Let $c_1,\dots, c_d$ be the first $d$ moments of the standard normal distribution. Does the point $(c_1,\dots, c_d)$ lie in the convex hull of the set $\{(t,t^2,\dots,t^d)\colon t\in[-b,b]\}$, for a ...
- 1,127
2
votes
0
answers
177
views
Formulating shortest path as submodular minimization
I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...
- 21
1
vote
0
answers
168
views
Projecting on a a special polyhedron
Let $X$ be an $n$-by-$p$ matrix and consider the closed convex polyhedron
$$\mathcal P_X := \{y \in \mathbb R^n | \|X^Ty\|_\infty \le 1\}.$$
Notice that $\mathcal P_X$ is symmetric about the origin.
...
- 6,853
1
vote
0
answers
77
views
Projecting on a convex compact polytope with special form
Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...
- 6,853
10
votes
2
answers
925
views
Constructing an independent uniform random variable from two independent ones
Does there exist a continuous (differentiable) function $h:[0,1]\times [0,1] \to [0,1]$ such that if $\alpha,\beta\in [0,1]$ are independent and uniformly distributed on $[0,1]$, the random variable $...
- 355
2
votes
0
answers
420
views
Derivatives of Minkowski function?
Let $A\subset \mathbb R^n$ and $M$ be the convex hull of the set $A$, e.g., $M:=Conv(A)$. The Minkowski function on $M$ is defined as follows
\begin{align*}
&f: \mathbb R^n \to \mathbb R\\
&f(...
- 51
6
votes
1
answer
263
views
Algorithm that solves every Mixed Integer Linear Program (to optimality)?
Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically?
I know that you usually ...
- 1,282
13
votes
1
answer
2k
views
Minimize sum of $\ell_2$ norm and linear combination, on simplex
Let $\Delta_n := \{x \in \mathbb{R}^n | x \ge 0, \sum_{1 \le i \le n}x_i = 1\}$ be the $n$-simplex. For $a, b \in \mathbb R^n$, with $\Delta_n \not \ni a$, consider the problem of computing the ...
- 6,853
2
votes
0
answers
112
views
Pcross-like, nonogram-like in near-linear time [closed]
I have a problem with a puzzle game like pcross in which I have a nxn square: At any index of rows and columns I have an integer that say the maximum numbers of points that I can place in that row/col....
7
votes
0
answers
245
views
orthogonal projector onto the set of convex functions
Let $\Omega\subset \mathbb R^d$ be an open, convex domain, and consider the Hilbert space $L^2(\Omega)$. Each sum of convex functions is convex, hence the subset $Conv(\Omega)$ of all convex functions ...
- 3,388
0
votes
1
answer
500
views
Convex Optimization in an Ellipsoid
Suppose we want to minimize a linear objective inside an ellipsoid that is,
$\min _x l^Tx$
such that $(x - \mu)^TA(x - \mu) \leq \beta ^2$.
Here, A is PSD and $\mu$ is a fixed vector. Can this be ...
- 275
2
votes
1
answer
531
views
Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables
I am working out an interesting problem and would like some help with this particular sub problem:
Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\...
- 21
0
votes
1
answer
543
views
Convert general optimization problem to LP problem
I am trying to convert the following problem into a linear programming problem:
There are $M\times N$ matrix $T$ of real numbers between 0 and 1 and $N\times 1$ vector $w$ of real numbers between 0 ...
- 99
7
votes
1
answer
187
views
Two (new?) variants of convex functions
I find that the following two types of functions are useful to my research.
(i) We know that a function $f: \mathbb{R}_+^m\rightarrow \mathbb{R}$ is called convex if for all ${\bf x,y}\in \mathbb{R}...
- 73
0
votes
1
answer
2k
views
When to use non-negative-least square and least-square [closed]
What are the typical case we need to use Non-negative least squares NNLS
$$
||Ax - B||^2
$$
instead of least-square $$ Ax-B$$ (or vice versa)?
And is there any drawback in applying them on large $A$...
- 135
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
206
views
A family of convex bodies in Banach-Mazur position
Let $\{K_i\}$ be a family of smooth, origin-symmetric, strictly convex bodies such that $K_i$ converge in the Hausdorff distance (or you may assume $\partial K_i\to \partial K$ smoothly, in the sense ...
- 41
5
votes
1
answer
220
views
Order between two completely monotone functions?
I am wondering if the following assertion is true:
Let $f,g:\mathbb{R}_+\rightarrow [0,1]$ be completely monotone functions on $\mathbb{R}_+^*$, that is, $(-1)^n f^{(n)}(x)\geq 0$ and $(-1)^n g^{(n)}...
- 266
3
votes
1
answer
280
views
Generalization of standard convex problem
In standard convex programming, the objective function and each of the constraint inequalities are convex. in such case, if the KKT condition hold for a point, and Slater condition is also hold for ...
- 383
3
votes
0
answers
970
views
Testing if a point is inside a convex polytope formed by halfspaces in n-dimension
Assume we have a convex polytope that is formed by the intersection of $k$-halfspaces in $\mathbb{R}^{n}$.
$$
a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0
$$
$$
a_{1,0}x^{n-1} + {a}_{1,...
- 31
2
votes
0
answers
86
views
A question about the approximation of convex cones
I have the following question which maybe is too naive.
Let $K$ be a convex cone on $\mathbf{R}^n$. Can we approximate $K$ by a sequence of polyhedral convex cone $K_i$ such that for any compactly ...
- 379
0
votes
1
answer
141
views
How to compute the direction of slowest ascent from the minimum of a strongly convex function?
Consider a twice differentiable strongly convex function $f:\mathbb{R}^n \rightarrow \mathbb{R^+}$ that attains its minimum value at the point $x^*$. I am wondering if one can compute a direction of ...
- 379
1
vote
0
answers
488
views
concavity of a vector function
I'm given a function $g:\mathbb{R}^n \mapsto \mathbb{R}$, $g(y) = \prod_{i\in[n]} (1+y_i\cdot c_i)$, where $c_i>0$.
Let $e_a,e_b$ be two arbitrary standard vectors. It is easy to show that for any ...
- 341
0
votes
1
answer
82
views
Introducton books for $\frak{E}_p(I)$
Are there any good books different from abstract harmonic analysis by hewitt to study $\frak{E}_p(I)$. where $\frak{E}_p(I)$ is: Let $I$ be an arbitrary index set. For each $i\in I$ let $H_i$ ...
- 209
5
votes
1
answer
146
views
How does one go from convexity to submodularity?
If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular?
It would be helpful is someone can share some specific ...
- 1,893
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
1
vote
1
answer
219
views
approximate diameter of polytopes in high dimensions
I just came across the following problem:
Let us consider the unit corner of the n-cube
$$
\Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 \...
- 75
2
votes
0
answers
154
views
Listing all Lattice Points in a Box
Let $B := [-1,1]^n$ be an $n$-dimensional box. Moreover, let $v_1,\ldots,v_n \in \mathbb{R}^n$ form a basis of $\mathbb{R}^n$, where the entries of the $v_i$ are explicitly irrational. We can assume ...
- 173
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
1
vote
0
answers
171
views
Finding all feasible solutions
Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...
- 175
3
votes
0
answers
229
views
Area defined with $\pm$ closedness
Denote $B_n\subset\Bbb R^n$ to be unit ball at origin.
Denote $S\subset B_n$ to region of type $\mathsf I$ if it satisfies
$$s\in S\iff\forall t\in S, s+t\in S\mbox{ or }s-t\in S$$
I am convinced $\...
- 13.9k