All Questions
1,019 questions
4
votes
1
answer
357
views
Lipschitz function admits Whitney stratification
I've been reading Topological Aspects of Nonsmooth Optimization by Vladimir Shikhman.
There I have found the following observation that:
Lipschitz functions $f : \mathbb{R}^n \to \mathbb{R}$ admit
...
- 99
1
vote
0
answers
96
views
Infimum of equivalent measures
Suppose I have a functional of the form
$$
F(\mathbb{P})\triangleq \int_{\mathbb{R}^d} \int_{\Omega}f(x,\omega)\mathbb{P}(d\omega)m(dx),
$$
where $m$ is the Lebesgue measure and $\mathbb{P}$ is a ...
- 173
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 163
3
votes
1
answer
472
views
Convex function and weak convergence of measures
Let $X$ be a compact set. Given probability measures $\mu,\mu_n: \mathcal{B}(X)\to R$. Is it possible that $$\langle f,\mu_n\rangle \rightarrow \langle f,\mu\rangle$$
for all convex function $f:X\to R$...
- 185
2
votes
1
answer
509
views
Under what condition does Courant–Fischer–Weyl min-max principle hold in general?
From Wikipedia:
Let $A$ be an $n \times n$ Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient $R_A :
\mathbf C^n \setminus \{0\} \to \...
- 155
3
votes
1
answer
380
views
Finding a smooth convex function with prescribed boundary value and small Monge-Ampère measure
Let $\Omega\subset\mathbb{R}^n$ be a bounded strictly convex domain and $\nu:\partial\Omega\rightarrow\mathbb{R}$ be a lower semi-continuous functions. It is well known that the function $\overline{\...
- 1,804
2
votes
1
answer
376
views
computation of a particular subdifferential
Given a bounded $\Omega\subset R^d$, $N$ functions $F_1,\dots,F_N\in L^\infty(\Omega)$, and a positive integrable $\omega\in L^1_+(\Omega)$, define the following function from $R^N$ to $R$:
$$
f(\...
- 5,380
3
votes
0
answers
142
views
Probability of hitting two vectors
Call an element of $ \{-m,\dots,0,\dots,m\}^{2^n}$ a vector. Assume $m = O(2^{2^n})$.
Let $u_1,u_2$ be vectors.
Let $\{v_1,\dots,v_{2^n}\}$ and $\{w_1,\dots,w_{2^n}\}$ be linearly independent ...
- 13.9k
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
3
votes
0
answers
182
views
Characterization of minimizer of convex functional
I need to check whether the following characterization of the minimizer of a convex functional is valid.
Let $X$ be a reflexive Banach space (think $W^{1,p}(\Omega)$ with $\Omega \subset \mathbb R^n$ ...
- 201
5
votes
2
answers
755
views
Intersecting a convex polytope with the unit sphere
I have a list of $m$ affine inequalities in $n$ variables of the following form
$$a_1 x_1 + \cdots + a_n x_n \leq c_n$$
I would like to know whether there is any point on the unit sphere in $\...
user47305
2
votes
2
answers
3k
views
Linear programming with infinitely many constraints
I wish to study the following linear program
$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0\...
- 283
0
votes
2
answers
120
views
Reference request: dependence on linear constraints
Excuse me if my question is stupid. I'm seeking the references on the dependence of the (linear) optimization problem on (linear) constraints. Namely, consdier the following optimization problem:
$$P(...
- 1,835
0
votes
0
answers
80
views
Comparison of two functions
Given a function $f$ from $R^2$ to $R$ satisfying tha following:
$1)$ $f$ is a convex function which vanishes on $(0,1)$ and on $(1,0).$
$2)$ $f$ is a decreasing function on $x$ and on $y$ and $f$...
- 1,257
3
votes
0
answers
71
views
Dependence of optimization problem on the linear constraints
Let $I=\{x_1,\cdots, x_n\}\subset \mathbb R$ be fixed. Given two probability distributions $\alpha=(\alpha_i)_{1\le i\le n}$ and $\beta=(\beta_i)_{1\le i\le n}$ on $I$, and a matrix $c=(c_{i,j})_{1\le ...
- 1,835
1
vote
1
answer
363
views
Question on Jensen's inequality
Let $(X,Y)$ be a martingale on $\mathbb R$ and $\psi:\mathbb R\to\mathbb R$ be a convex function. Then it follows by Jensen's inequality that
$$\mathbb E[\psi(X)]~~\le~~ \mathbb E[\psi(Y)]$$
and if ...
- 1,835
1
vote
1
answer
114
views
Reference request: regularity of functionals on the space of probability measures
Let $\mathcal M=\mathcal M(\mathbb R^d)$ be the space of finite measures on $\mathbb R^d$, and $\mathcal P=\mathcal P(\mathbb R^d)\subset\mathcal M$ be the space of probability measures. Let $F:\...
- 1,835
2
votes
1
answer
1k
views
Complementary slackness for approximately optimal Dual solution
Given a Primal LP (P) and it Dual LP (D) we know that the optimal solutions to P ($x_{opt}$) and D $(y_{opt})$ satisfy complementary slackness condition, i.e. under optimal solutions either a ...
- 133
4
votes
2
answers
561
views
Reference request: concave/convex envelope
I'm seeking the references concerning on the regularity analysis of concave envelopes, i.e. given some measurable function $f:\mathbb R^d\to\mathbb R$ that is bounded from above ($d=1$ or $d\ge 1$), ...
- 1,835
3
votes
1
answer
193
views
Inequality of a concave function
Let $G:\mathbb R\to\mathbb R$ be a concave function, define $G_{\epsilon}: \mathbb R\to\mathbb R$ by
$$G_{\epsilon}(x)~~:=~~\max_{y\in [x-\epsilon, x+\epsilon]}G(y).$$
My question is the following: ...
- 1,835
0
votes
0
answers
890
views
Maximum shortest path problem
I have the following problem. You have a graph and every edge has a certain set of possible weights. The question is to find the assignment of those weight which will maximize the shortest path.
In ...
- 342
1
vote
0
answers
123
views
Generalization of concave envelope
Let $g:\mathbb R_+\to\mathbb R$ be a measurable function (which could be supposed to be bounded and Lipschitz if required). Let $\mathcal P$ be the collection of probability measures $\mu$ on $\mathbb ...
- 1,835
1
vote
0
answers
71
views
Closeness of the product of closed convex processes
I asked this question to the math.stackexchange but couldn't get an answer.
Let $A$ be a closed convex process from $R^n$ to $R^n$, $I$ be the identity map, $\lambda$ be a real number, and $k$ be a ...
- 183
1
vote
1
answer
130
views
Maximum of gradient of convex functions [closed]
The question comes from the page 472, Elliptic partial differential equations of second order/ David Gilbarg, Neil S. Trudinger. In one dimension it's obviously true, but it seems more involved in ...
- 31
2
votes
0
answers
126
views
Unveiling hidden structures
One way to unveil a hidden structure of a undirected graph - given as an adjacency matrix - is to permute the rows and columns until a pattern with a maximal geometrical symmetry is found. (The ...
- 9,720
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
1
vote
0
answers
1k
views
Number of different combinations in a 0-1 knapsack problem with integer weights [closed]
My question is actually very similar to this other one: Given a vector of positive integers, count the number of combinations which have a sum that produces a different value. But, since this previous ...
- 153
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
1
vote
0
answers
384
views
(Quasi) convexity of separately convex homogeneous functions
Consider a function $f:\mathbb{R}^n_{\geq 0}\rightarrow \mathbb{R}$ that is separately convex, i.e. such that $\frac{d^2f}{dx_i^2}\geq 0$ for all $i\in \{1,\dots n\}$. Assume also that $f$ is ...
- 379
4
votes
2
answers
722
views
Minimum number of rectangles in a polygon
Given a polygon and dimension $d$, find a minimum partition of rectangles that has either of its dimensions equal to $d$.
Example:
Consider the following diagram:
I want to cover maximum shaded ...
- 175
1
vote
0
answers
1k
views
Analytic formula for minimizing the maximum inner product of a set of vectors
Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find
$$
\widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|.
$$
I am also interested in the special case where we further ...
- 710
1
vote
1
answer
184
views
Do doubly infeasible Linear Programming problems always have doubly infeasible bases?
Consider a Linear Programming problem in dictionary form,
$$\max\Big\{f^\pi+\!\!\!\sum_{j\in D(\pi)}\!\! d^\pi_jx_j~\Big|~\forall~i\!\in\!B(\pi)~~~ b^\pi_i+\!\!\!\sum_{j\in D(\pi)}\!\! G^\pi_{ij}x_j\...
- 21
0
votes
1
answer
201
views
Recursive linear programming on a linear subset of a simplex
The problem I am working on is:
Given an $n$ dimensional vector $r \in \mathcal{R}^n$, and a convex set $G=\{\mu \in \mathcal{R}^n | \mu_i \ge 0, ~ \mu^T \mathbf{1}=1, ~ A\mu =0 \}$ where $\mathbf{1}...
1
vote
1
answer
269
views
The definition of the face of a convex set by a nonnegative affine linear polynomial
My question comes from the paper: https://arxiv.org/abs/0911.2750 (p.2~p.3)
For $n\in \mathbf{N}$
Let $X = (X_1,\ldots,X_n)$ be an $n$-tuple of variables.
Let $\mathbf{R}[X]$ denote the ...
- 345
1
vote
0
answers
181
views
Stochastic increasing convex ordering
Consider $n \geq 2$ and the simplex
\begin{equation}
\Delta=\{(p_1,\cdots,p_n) \in \mathbb{R}^{n} \mid \forall i, p_i \geq 0 \text{ and } \sum_{i=1}^{n}{p_i}=1\}
\end{equation}
Suppose that $\Delta$ ...
- 111
4
votes
2
answers
508
views
How to show the two convex bodies are affinely isomorphic?
This problem comes from the response of the author of papers.
Consider two convex bodies $A$ and $B$:
$$A= \{X\in \mathcal{S}^4 : \operatorname{tr}(X) = 1, X\succeq 0 \}$$
$$B = \operatorname{...
- 345
2
votes
1
answer
497
views
Linear map of finite or infinite extreme points. Discuss injectivity and surjectivity
Before entering my problem, let me review some related results:
Suppose $\mathcal{S}$ is a convex hull of finite points: $\mathcal{S}=\operatorname{conv}(x_1,x_2,\ldots,x_m)$, then
By "https://...
- 345
2
votes
3
answers
1k
views
Quadratic Programming With Piecewise Linear Term
The problem I have can be defined as:
$$
\min \frac{1}{2}\mathbf{x}^T\mathbf{Q}\mathbf{x} + \mathbf{c}^T\mathbf{x}
$$
s.t. linear equality constraints:
$$
\mathbf{Ax=b}
$$
and linear inequality ...
- 131
1
vote
0
answers
355
views
Solution to a system of nonlinear equations using convex conjugate of log sum exp
I need to prove the following result:
There exists a unique solution to the system of equations
$$\alpha = \frac{I^T(\gamma e^{I\beta})}{\sum_{i=1}^{n}\gamma_ie^{(I\beta)_i}}$$
if and only if $\...
- 11
0
votes
1
answer
212
views
How to find out if a polytope contains a sphere?
Given a polytope described by linear inequalities $Ax \le b, x \in \mathbb R^n$, how do you find out if there exist a (non degenerate) sphere of dimension $n-1$ contained in the polytope?
Thanks!
- 225
1
vote
0
answers
187
views
Strong Duality of Mixed Integer Linear Program
The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the ...
- 11
3
votes
2
answers
1k
views
SDP relaxation vs LP relaxation
I have a question I hope you might be able to answer.
Let's say we have an integer program for the stable set problem (or clique, not principal).
\begin{equation}
\begin{aligned}
& \text{...
- 342
4
votes
3
answers
2k
views
Zero lambda, zero constraint in the complementary slackness condition of the Kuhn-Tucker problem
Complementary slackness condition in the KKT theorem states that:
$\lambda_i^*\geq0; \lambda_i^*h_i(x^*)=0 $
The usual reasoning goes like this: either constraint is clack $h_i(x^*)>0$ and then ...
- 71
3
votes
1
answer
452
views
How to find extreme points of a set related to Minkowski's Theorem?
Let $S^{n-1}$ be the unit sphere in $\mathbb{R}^n$. For $m>n$, we can define $\Lambda$ to be the set
$$\{(\lambda_1, ..., \lambda_m):\sum_{i=1}^m \lambda_i=1, \lambda_i\ge0, and \mbox{ there exist}...
- 1,350
2
votes
1
answer
171
views
Maximization of Binary Multilinear Fractional Function
Problem: Let $a_{i,j}$, $b_{i,j}\in\mathbb{R}$ for all $(i,j)\in\left[m\right]^2$ such that $a_{i,j}=a_{j,i}$ and $b_{i,j}=b_{j,i}$. Let $z_k\in\{0,1\}$ for $k\in\left[m\right]$. We wish to maximize,
...
2
votes
3
answers
2k
views
Better tactics for removing redundant constraints than Linear Programming?
After reading:
Detection of Redundant Constraints
It appears that linear-programming is the most commonly known way to remove ALL redundant constraints from a system of inequalities of the form
$$ ...
- 2,689
2
votes
1
answer
529
views
Integer programming and Groebner basis
I enjoyed reading different papers about using Groebner basis to solve integer programming.
Is there any literature about the complexity and/or comparison with other (more classical) methods like ...
- 337
1
vote
0
answers
232
views
Semi-convex problem and almost convex problem
I have a target function, I've computed its Hessian to check convexity, it has a positive-definite sub-matrix and small negative-definite sub-matrix and a kernel. Sometimes it is even better -- the ...
- 355
1
vote
1
answer
155
views
Derive a vertex representation of a permutohedron from its linear-inequalities form
Let us define the $n$-permutohedron $P_n$ as the set of all $x\in\mathbb{Q}^n$ such that
$$\sum_{i=1}^n x_i = \binom{n{+}1}{2}\ \ \ \land\ \ \ \forall\,\text{nonempty}\ S\subsetneq\mathbb{N}_n\colon\ ...
user94257
4
votes
2
answers
646
views
Are there examples of functions with Nesterov's convergence bound between convex quadratic and strongly convex cases?
Are there examples of strongly convex functions for which the complexity bound of Nesterov’s Accelerated Gradient Method is better than Nesterov’s complexity bound for strongly convex case $$\sqrt{1 - ...
- 41