Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
28 views

Integral hull of a polyhedron Q is polyhedron

Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
Sowbarnika R's user avatar
-1 votes
0 answers
41 views

Is it possible to backtrack an optimization solver? [closed]

I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
Bamboozle's user avatar
2 votes
1 answer
128 views

Reference request for elementary convex geometry property

I need to use the following lemma for a proof. It is an elementary result, which I am sure is well known, just I am not familiar enough with the relative literature to find a direct reference. Is ...
ECL's user avatar
  • 345
2 votes
1 answer
91 views

Does approximately null gradient imply approximately global minimum for convex functions?

Let $f: \mathbb{R}^{n} \rightarrow \mathbb{R}_{+}$ be a non-negative and differentiable convex function which vanishes in a non-empty convex set $\Omega$ - possibly unbounded. Usually, when one ...
R. W. Prado's user avatar
0 votes
0 answers
21 views

Easy instance of set cover

I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
Tom Solberg's user avatar
  • 4,049
2 votes
0 answers
67 views

Two-terms Euler-Maclaurin formula for concave functions over polytopes

Let $P\subset\mathbb{R}^{n}$ be a lattice polytope (vertices are in $\mathbb{Z}^{n}$). Set $P_{k}=P\cap k^{-1}\mathbb{Z}^{n}$ for $k\geq1$. Given a concave function $\phi:P\rightarrow\mathbb{R}$ (...
Yee Yao's user avatar
  • 73
7 votes
2 answers
242 views

Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$

Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds: $$ \langle x_k, \theta_k \rangle &...
Alireza Bakhtiari's user avatar
1 vote
0 answers
60 views

Behaviour of the solutions of parametrized multivariable non-linear (non polynomial) system of equations

The following problem arose out of a research problem. Let us consider the $n \times n$ matrix valued function $[x_{i,j}(p)]$ (of $p$), satisfying $$ \sum_j x_{i,j}(p) x_{k,j}(p)|x_{k,j}(p)|^{p}= \...
Arun 's user avatar
  • 745
2 votes
4 answers
212 views

Efficient algorithm for graph problem

Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
Martin Clever's user avatar
1 vote
1 answer
40 views

Envelopes of functions with respect to some convex cone $\mathcal{F}$

Let's say we are given a function $f:\mathbb R ^d\to \mathbb R$ continuous. Assume that $\mathcal F$ is a convex cone of continuous functions ($\mathbb R^d$ to $\mathbb R$) closed under maxima. I am ...
J.R.'s user avatar
  • 291
1 vote
1 answer
106 views

Iterated optimal transport

Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
tex.support's user avatar
2 votes
1 answer
132 views

Points of differentiability of convex functions

Let $U$ be an open neighbourhood of $0 \in \mathbb{R}^2$ and $f\colon U \to \mathbb{R}$ a convex (and bounded) function. Denote by $D \subset U$ the set of points on which $f$ is totally ...
AlexE's user avatar
  • 2,998
7 votes
0 answers
248 views

Proving this function is convex

Let $C$ be a symmetric positive definite matrix such that $0\leq c_{ij} \leq 1$, $c_{ii}=1$, and define $f$ as $$f(x)=\sum_{i}x_{i}\log(\sum_{j}c_{ij}x_{j})$$ for positive vectors $x$ (in fact let's ...
Tom Solberg's user avatar
  • 4,049
11 votes
2 answers
430 views

On the convex cone of convex functions

$\newcommand\R{\Bbb R}$Let $F$ be the set of all functions of the form $\max(a,b,c)$, where $a,b,c$ are affine functions from $\R^2$ to $\R$ and the maximum is taken pointwise. Let $G$ be the set of ...
Iosif Pinelis's user avatar
2 votes
0 answers
60 views

Test probability distributions increasing in convex order on $\mathbb R^2$?

Two probability distributions $\mu, \nu$ on $\mathbb R^d$ are said to be increasing in convex order if $$\int_{\mathbb R^d} |x|\mu(dx) + \int_{\mathbb R^d} |x|\nu(dx)<\infty$$ and $$\int_{\mathbb R^...
GJC20's user avatar
  • 1,334
1 vote
0 answers
41 views

Convex 1-semiconcave functions : extreme points

Let $C$ be the set of functions $f:\mathbb{R}^n \to \mathbb{R}$ such that $x\mapsto f(x)$ and $x\mapsto \lVert x \rVert^2 - f(x)$ are both convex. If $f$ belongs to $C$, then $f$ plus any affine ...
alesia's user avatar
  • 2,772
1 vote
0 answers
73 views

Convexity and subdifferential monotonicity

Do you know any reference where I can find some results in this sense: Consider $W:K\to [0,\infty)$ is a functional defined on a convex cone $K\subset X$, where $X$ is a Banach space. Then the ...
Bogdan's user avatar
  • 1,759
13 votes
2 answers
1k views

Probability vector $p$ majorizes its normalized entropy vector $\small \frac{-p\log p}{H(p)}$

I guess the following inequality $$ \sum_{i=1}^n g \left (\frac{-p_i \log p_i}{H(\boldsymbol{p})} \right ) \le \sum_{i=1}^n g (p_i)$$ holds for any continuous convex function $g$ and any probability ...
Amir's user avatar
  • 303
6 votes
0 answers
304 views

Distribution class closed under convolution counterexample?

Define the class of probability density functions $\mathcal{C}$: $\,p \in \mathcal{C}$ iff $p(x)=p(|x|)$, and $\log p(\!\sqrt{x})$ is convex on $[0,\infty)$. Conjecture: if $p,q \in \mathcal{C}$, then ...
japalmer's user avatar
  • 391
2 votes
0 answers
58 views

An s-convex function lying between two convex functions

Let $f: \mathbb R_{+} \to \mathbb R_{+}$ be an $s$-function in the second sense, i.e., $$ f(\lambda x +(1-\lambda)y) \leq \lambda^s f(x) +(1-\lambda)^s f(y)$$ for every $\lambda \in (0,1)$. Assume ...
MAY's user avatar
  • 55
2 votes
0 answers
123 views

Continuity of entropies, replica trick and Hausdorff moment problem

I could not find a really appropriate title for my question (happy to revise) but let me explain. Suppose $p(x|c)$ is a probability density function over $x \in [0,1]$ which depends continuously on ...
nervxxx's user avatar
  • 231
3 votes
0 answers
110 views

How many Tverberg partition are in cloud of points? [closed]

Tverberg's Theorem: A collection of $(d+1)(r-1) +1$ points in $\mathbb{R}^d$ can always be partitioned into $r$ parts whose convex hulls intersect. For example, $d=2$, $r=3$, 7 points: Let $p_1, p_2,...
Xd00fg's user avatar
  • 214
0 votes
0 answers
48 views

A question on a quantitative form of Farkas' lemma

Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
Keivan Karai's user avatar
  • 6,214
2 votes
0 answers
318 views

What's the number of facets of a $d$-dimensional cyclic polytope?

A face of a convex polytope $P$ is defined as $P$ itself, or a subset of $P$ of the form $P\cap h$, where $h$ is a hyperplane such that $P$ is fully contained in one of the closed half-spaces ...
the_tomato's user avatar
6 votes
1 answer
366 views

An arrangement of hyperplanes [closed]

An arrangement of hyperplanes in $\mathbb{R}^d$ is simple if the hyperplanes are in general position (for every $1\leq k\leq d+1$, the intersection of $k$ hyperplanes is $(d-k)$-dimensional). My ...
Xd00fg's user avatar
  • 214
4 votes
1 answer
416 views

Maximum and concavity of function

Let \begin{align} G(x_1,x_2,x_3)=\int_0^{2\pi}\int_0^{2\pi}\int_0^{2\pi} \frac{d\theta_1 d\theta_2 d\theta_3}{(2\pi)^3} p(\vec{x},\vec{\theta}) \log\left( p(\vec{x}, \vec{\theta})\right) \end{...
nervxxx's user avatar
  • 231
6 votes
1 answer
287 views

Determinantal inequality for difference of substochastic matrices

Let $A=(A_{ij})_{1\le i,j\le n}$ be a square matrix with nonnegative real entries. Recall that $A$ is called a substochastic matrix if $$ \forall i,\ \ \sum_j A_{ij}\le 1\ . $$ In the course of my ...
Abdelmalek Abdesselam's user avatar
2 votes
0 answers
104 views

Reference request: books on convex analysis / geometry

I am interested in convex geometry and analysis, especially in its connections with high dimensional probability theory. I was reading the book by Pisier, The volume of convex bodies and Banach space ...
Drew Brady's user avatar
1 vote
0 answers
99 views

Minimum of the maximum element frequency given the family size and the universe size

[Crossposted at math.stackexchange]. Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$. I have written and solved ...
Fabius Wiesner's user avatar
2 votes
1 answer
308 views

Concavity of hypergeometric function ratio

I would like to show that the function, $$ f(x) = \frac{{}_2\mathrm{F}_1\big(\frac{1}{2},\frac{1}{2};c+1\,;x\big)}{{}_2\mathrm{F}_1\big(\frac{1}{2},\frac{1}{2};c\,;x\big)} $$ is concave for $0 < x &...
japalmer's user avatar
  • 391
1 vote
1 answer
39 views

Does uniform convergence of suitable functions yield pathwise convergence of their convex envelopes?

For each $k\ge 1$, let $f_k:\mathbb R\to\mathbb R_+$ be $1-$Lipschitz, increasing such that $f_k(x)\ge x^+$ for $x\in\mathbb R$, $f_k(-\infty)=0$ and $$\lim_{x\to+\infty} \big(f_k(x)-x\big)=0.$$ ...
GJC20's user avatar
  • 1,334
0 votes
1 answer
150 views

When are infimal convolutions contractions?

Let $X$ be a separable Fréchet space and $\varphi,\psi:X\to \mathbb{R}$ be a lower semi-continuous and convex function with $\psi$ bounded below and coercive. Consider the infimal convolution $$ \...
Math_Newbie's user avatar
0 votes
0 answers
115 views

Software for computing polytopes

As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
AlexiosF's user avatar
5 votes
1 answer
176 views

Efficient counting of integer solutions to linear system

In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
user326210's user avatar
1 vote
1 answer
94 views

Why are symmetric convex bodies with a smooth boundary and non-vanishing Gaussian curvature of particular interest in harmonic analysis?

I don't work in harmonic analysis or convex analysis, but in some literature of harmonic analysis, I often see the assumption that "let $K$ be a symmetric convex body with a smooth boundary and ...
taylor's user avatar
  • 457
1 vote
0 answers
95 views

Distance between two convex sets

Setting If $A$ an $B$ are two symmetric matrices, we denote by $A >B$ when the matrice $A-B$ is definite positive. In $\left(\mathbb{R}^{*}_{+} \right)^4$, consider the convex set $$ \Lambda = \...
Anthony's user avatar
  • 125
5 votes
3 answers
560 views

An inequality in an Euclidean space

For $n\geq 1$, endow $\mathbb{R}^n$ with the usual scalar product. Let $u=(1,1,\dots,1)\in\mathbb{R}^n$, $v\in {]0,+\infty[^n}$ and denote by $p_{u^\perp}$ and $p_{v^\perp}$ the orthographic ...
G. Panel's user avatar
  • 449
2 votes
1 answer
197 views

Prékopa-Leindler style inequality?

Does anyone know a simple proof of the following Prékopa-Leindler style inequality: If we have $f_1,f_2,g_1,g_2$ strictly positive functions on $\mathbb{R}$ such that, for any $x_1,x_2 \in \mathbb{R}$,...
Anthony's user avatar
  • 125
0 votes
1 answer
59 views

Do separable cubic constraint and separable quartic constraint SOCP presentable?

I am an engineer who is doing some network modeling and optimization. During my work, I was running into a case that is quite strange. The problem that I am trying to solve seems to be convex and it ...
Tuong Nguyen Minh's user avatar
3 votes
0 answers
279 views

Interchange limit and supremum of functionals over a bounded convex set

Let $(H, \langle\cdot,\cdot\rangle)$ be a separable real Hilbert space and $B\subset H$ be (nonempty) convex and bounded, and suppose that $(\alpha_k)\subset H$ is a sequence for which the limit $\...
fsp-b's user avatar
  • 463
7 votes
2 answers
345 views

Integral means vs infinite convex combinations

Let $(X,\mathcal A, \mu)$ be a probability space, $\mathbb E$ a Banach space, and $f:X\to\mathbb E$ a Bochner integrable function. Does there exist a sequence $(x_k)_{k\ge 1} $ in $X$, and a ...
Pietro Majer's user avatar
  • 60.5k
4 votes
0 answers
46 views

Implementation of Friedman's algorithm of reconstructing simple polytopes

In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
mashedcarrots's user avatar
0 votes
0 answers
80 views

Verifying the Cauchy behavior of a sequence

Let me consider the iteration $x_{n+1}=Tx_n$ and $T$ is a self-map from a non-empty subset $K$ of a smooth Banach space $X$ to itself, satisfying $W(Tx, Ty) \leq W(x, y)$, where $W(x, y)=\Vert x \Vert^...
PPB's user avatar
  • 85
7 votes
3 answers
703 views

A continuous version of Carathéodory's convex hull theorem

A well-known theorem of Caratheodory states that any point in the convex hull of a set $X\subset R^n$ lies in the convex hull of at most $n+1$ points of $X$. I am wondering about a version of this ...
Mohammad Ghomi's user avatar
0 votes
0 answers
39 views

Max-flow modeling with unified vehicle and commodity variables

I am working on a network flow problem that involves routing through a time-space network. The network consists of: A single source node and a single demand node. A fleet of vehicles with specified ...
graphtheory123's user avatar
0 votes
1 answer
104 views

Optimality condition for strongly convex function under sparsity constraint

Let $f: \mathbb{R}^p \to \mathbb{R}$ be a $2s$-sparse strongly smooth, $2s$-sparse strongly convex and twice differentiable function. In other words, there exists positive constants $\alpha, L >0$ ...
De vinci's user avatar
  • 399
2 votes
1 answer
123 views

Is it true that the set $\{x\colon \partial\phi(x)\subset B_r(0)\}$ is convex when $\phi$ is convex?

Let $\phi\colon \mathbb{R}^n\to \mathbb{R}$ be convex. Is it true that the sets $$ A_r = \{x\in \mathbb{R}^n\;\colon\; \partial \phi(x) \subset B_r(0)\},\quad r>0, $$ are convex? For $n=1$ this ...
user522653's user avatar
0 votes
0 answers
30 views

Application of greedy approach for optimization

I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$ where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
Prakirt Raj's user avatar
1 vote
1 answer
143 views

Projection of an element of the $n$-simplex onto subset

Let $\mathbb{S}^{n}$ denote the $n$-dimensional probability simplex and let $\{e_1,...,e_{n+1}\}$ be the canonical basis of $\mathbb{R}^{n+1}$. Consider the subset $\mathbb{S}^{n}(K) \subset \mathbb{S}...
aureliano_buendia's user avatar
0 votes
1 answer
149 views

Property of $p$-norm in the $n$-simplex

Let $\mathbb{S}^{n}$ be the canonical simplex of $\mathbb{R}^{n}$ and let $u = (1/n,\dotsc,1/n)$. Is it true that $$\lVert x - u \rVert_p \leq \lVert y - u \rVert_p$$ implies that $$\lVert x\rVert_p \...
aureliano_buendia's user avatar

1
2 3 4 5
21