All Questions
1,594 questions
3
votes
1
answer
123
views
How to maximize the variance of a subset of integers?
$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
- 41
1
vote
0
answers
29
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_+...
- 21
-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....
1
vote
1
answer
82
views
Solution to a quadratically constrained quadratic program with unit ball constraint
I am working on a quadratically constrained quadratic program (QCQP) of the form:$$ \min_{x} \quad \frac{1}{2} x^T P x + q^T x + r$$
$$ \text{subject to} \qquad x^{T}x \leq 1 $$
where $P \in S^{++}_{...
- 13
5
votes
0
answers
90
views
Rational maps from the circle to the unitary group (energy-preserving convolutive mixtures)
Consider a rational map $A : S^1 \to U(n)$, i.e. a matrix of rational functions such that evaluation at any $z \in S^1 \subset \mathbf C$ is unitary. These objects show up in digital signal processing ...
- 151
2
votes
0
answers
174
views
Eigenvalues of Laplace operator and Schrödinger operator
When reading the paper Control for Schrödinger operators on tori by N.Burq and M.Zworski (Math. Res. Lett., 19(2):309–324, 2012), an inequality confused me:
Define the flat torus $\mathbb{T}^2=\mathbb{...
- 21
0
votes
0
answers
35
views
Describing the boundary of the feasible direction cone to a convex open subset of $\mathbb{R}^n$ at a boundary point: connection via subdifferential?
Let $U\subset \mathbb{R}^n$ be a convex, open set with nonempty boundary. Let $x_0\in \partial{U}.$ We can describe $U$ locally near $x_0$ as a super level set of a suitable continuous concave ...
- 1,465
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 ...
- 4,049
1
vote
0
answers
29
views
Change in active constraints when perturbing the objective of a QP
Suppose I have a quadratic program (with positive semidefinite cost matrix) with affine (polytopic) constraints. It is known that the solution to this is piecewise affine, with the ``pieces'' defined ...
- 11
1
vote
0
answers
91
views
How to optimize parametric information-theoretic bounds?
I am faced with an information-theoretic upper bound, such as
\begin{align}
\sqrt{\alpha'}2^{I_\alpha(X;Y)},
\end{align}
where $I_\alpha(X;Y)$ is the Rényi mutual information with parameter $\alpha>...
- 287
0
votes
0
answers
22
views
Alignment of unit vectors under graph-neighbor constraints with a global vector
Statement
Let $G = (V, E)$ be a connected, unweighted, and undirected graph with $n$ nodes, represented by its adjacency matrix $A$. Suppose each node $i$ is associated with a unit vector $ \mathbf{v}...
1
vote
1
answer
41
views
Lower spectral radius of matrices with an invariant subspace
Let $\mathcal{A} = \{ A_1, \ldots, A_J, : A_j \in \mathbb{R}^{s\times s}\}$, and define the lower spectral radius (LSR) (aka joint subradius) by
$LSR(\mathcal{A}) = \lim_{n\rightarrow\infty} \inf_{A_{...
- 131
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 &...
0
votes
1
answer
57
views
Self-concordant barrier for the epigraph of $f(x,y) = x^p y^{1-p}$?
The problem
Assume $p > 1$. Consider the function
$$f(x,y) = x^p y^{1-p}, \qquad x,y > 0.$$
Note that
$$
f'' = p(p-1)x^{p-2}y^{-1-p}
\begin{bmatrix}
y \\ & x
\end{bmatrix}
\begin{bmatrix}
1 &...
- 981
0
votes
2
answers
97
views
Optimization algorithms for Kronecker approximation of high-dimensional covariance matrices
I'm working with a high-dimensional covariance matrix and exploring Kronecker product approximations to make it computationally manageable.
Here's the setup:
I have a graph $G$ represented by a $D\...
- 1
2
votes
1
answer
104
views
Minimum time required by a curve to reenter a closed ball with radius equal to the reciprocal of its maximum curvature
I have a continuously differentiable curve $r : \mathbb{R} \to \mathbb{R}^{n}$, $n \ge 2$, with the properties
\begin{align}
\lvert r'(t) \rvert = 1 \text{ for all } t \in \mathbb{R}, \\
\lvert r'(t) -...
- 351
0
votes
1
answer
236
views
Solving a 0-1 quadratic matrix inequality
I am working on a binary optimization problem. So far I have derived the following constraint functions.
\begin{align}
\begin{bmatrix} \left( P + \sum_{i=1}^n (\sum_{j=1}^n x_{i, j} \alpha_j) e_i e_i^...
- 11
8
votes
1
answer
582
views
One flip coin game
Nate has $n \geq 2$ coins $\{C_i\}_{0 \leq i \leq n-1}$ that each turn up heads with probability $\frac{i}{n-1}$ each, but he is not sure which ones are which.
He has \$1 with which to bet with. On ...
- 6,155
5
votes
2
answers
527
views
Which coupling of uniform random variables maximises the essential infimum of the sum?
Recall that a coupling of probability measures $\mu_i$ is a set of random variables $X_i$ defined on the same probability space $\Omega$ such that $X_i \sim \mu_i$.
Question: Let $\mu_1, \dots, \mu_n$ ...
- 6,155
3
votes
0
answers
107
views
Stability of a nonlinear dynamical system with non-elementary dynamics
I am trying to prove stability and get a non-asymptotic upper bound on the convergence rate of a nonlinear discrete-time dynamical system, whose dynamics are stated in terms of the (non-elementary) ...
- 31
9
votes
1
answer
257
views
Higher or lower? (#2)
$N \geq 2$ players play a game - at the start of the game, they are each given independently and uniformly a number from $[0, 1]$. On each round, they are to guess whether their number is higher or ...
- 6,155
0
votes
0
answers
27
views
Projection onto polytopes as tropical polynomial
Let $C$ be a convex polytope in $\mathbb{R}^n$ with $m$ extremal points. Let $p\in \{1,2\}$.
Can the $\ell^p$-projection $\Pi_C:\mathbb{R}^n\to C$
$$
\Pi_C(x) \in \operatorname{argmin}_{z\in C}\, \|x-...
- 364
1
vote
0
answers
46
views
Intuition for proximal point method using L2 regularization
To minimize a function $f$, the proximal point method is defined as
$$x_{k+1} := \operatorname*{argmin}_x f(x) + \frac{1}{2\eta}\|x - x_k\|^2.$$
What's the intuition for why we want to use L2 ...
4
votes
1
answer
286
views
The gacha stamp collector’s problem
Let $N \gg n \geq 2$ be fixed natural numbers. In the Gacha stamp game, players are given an $N \times N$ square grid, with each point occupied by a unique stamp.
On every turn, they may choose a ...
- 6,155
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 ...
- 157
1
vote
0
answers
45
views
Conditions on LR in Gradient Descent
In Introductory Lectures in Convex Optimization by Yurii Nesterov, Section 1.2.3 shows that gradient descent is guaranteed to converge if the step size is chosen either with a fixed step size or ...
- 51
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$ ...
- 13
0
votes
0
answers
63
views
Convergence of the trajectory of ODE
Consider a $C^\infty$ smooth nonconvex function $f$, and ODE
$$
\begin{cases}
\dot{x}=-x\circ\nabla f(x),\\
x(0)\in\mathbb{R}^d_{++}.
\end{cases}
$$
Here $\circ$ is elementwise product, $\mathbb{R}^d_{...
- 43
1
vote
1
answer
105
views
Constrained optimization over a set of functions
How to approach the following optimization problem:
$$\text{minimize }\int_0^1 f(x) \, dx$$
over all (integrable) real-valued functions $f$ on $[0,1]$ satisfying
$$1-x_1 x_2 \leq f(x_1)f(x_2)\text{ ...
1
vote
0
answers
68
views
Uniqueness of a canonical homography decomposition
Consider a multi-camera system with $n \geq 3$ calibrated cameras, each represented by a projection matrix $P_i \in \mathbb{R}^{3 \times 4}$ for $i=1, \dots, n$. We first want to detect and track ...
-1
votes
1
answer
61
views
Asking for some references on correlations of joint optimization problems
Here are two problems that I am trying to understand, and it would be nice if someone could provide references on whether there is some structure theorem for these problems that have been studied in ...
0
votes
0
answers
49
views
Haraux's article request
I'm trying to find the article "Haraux, A., Séries lacunaires et contrôle semi-interne des vibrations d'une plaque rectangulaire., J. Math. Pures Appl. (9)68(1989), no.4, 457–465."
I could ...
- 21
2
votes
1
answer
141
views
(Sub)Optimality of random transport
Problem Setup: Consider the intervals $I_R = [a_R, b_R]$ and $I_B = [a_B,b_B]$. Let $F_R$ and $F_B$ denote the CDF of distributions with support on the intervals $I_R$ and $I_B$. I draw $k$ red and ...
- 25
0
votes
0
answers
112
views
Vector field connecting two points
I'm now working on somehow an inverse problem of an ODE:
Suppose we have a ODE on $\mathbb{R}^{n}$: $\dot{x} = f(x)$, denote the solution to the ODE starting at $a$ as $x_{f,a}$(t).
Now there is a ...
- 1
1
vote
0
answers
66
views
Sum of k vectors with largest possible norm
Suppose I have a family of $n$ vectors in $\mathbb{R}^d$:
$v_1,\dots,v_n.$ Is there a poly-time algorithm that computes a subset $S\subset [n]:=\{1,\dots,n\}$ of size $1\leq k\leq n$ for which the (...
0
votes
1
answer
164
views
Which coupling minimises the following cyclic sum?
We recall that a coupling of probability distributions $\mu_1, \dots, \mu_n$ on $\mathbb R$ is a set of random variables $X_1, \dots, X_n$ defined on the same probability space such that $X_i$ is ...
- 6,155
1
vote
0
answers
63
views
The rank of a matrix expression
I'm studying discrete-time LTI systems and state estimators for them. Recently, I studied this paper. I am facing a matrix rank calculation problem and having trouble solving it. I will provide more ...
- 4,484
0
votes
0
answers
53
views
Relations between the optimal solutions of two related SDPs
In system theory, we often encounter Semi-Definite Programs (SDPs) with Linear Matrix Inequality (LMI) constraints, such as those presented in this paper. I have introduced new variables based on the ...
- 4,484
2
votes
0
answers
48
views
Characterization of multifunctions with globally asymptotically stable minimal invariant sets
Let $(X, d)$ be a compact connected metric space. Consider a compact-valued upper semicontinuous multifunction $F: X \rightrightarrows X$. The reachable set $R[x]$ of $F$ from $x\in X$ is defined as:
...
- 111
8
votes
1
answer
449
views
What do smooth signatures give you?
My background is in rough paths theory.
In short, if you have an irregular function $f:[0,T]\to\mathbb R^d$ and you want to make sense of integrals $\int_s^t \cdot \ df(r)$, the right objects that are ...
- 1,904
2
votes
0
answers
57
views
Mappings that preserve local or global minimum
In the most general form, I'm interested in any non-trivial results of the following question.
Consider metric space $X$ and $Y$, denote all real valued functions on $X$ and $Y$ as $\mathbb{R}^{X}$ ...
- 275
19
votes
2
answers
2k
views
Higher or lower?
Consider the following game - I draw a number from $[0, 1]$ uniformly, and show it to you. I tell you I am going to draw another $1000$ numbers in sequence, independently and uniformly. Your task is ...
- 6,155
8
votes
1
answer
522
views
One step forward, one step back
$N \geq 2$ players play a cooperative game on the integers $\mathbb Z$. All of them start from $0$. At each turn, they are simultanously given the same yes or no question to answer.
The questions ...
- 6,155
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}=\...
- 6,214
5
votes
2
answers
364
views
Euler-Lagrange equations for minimizer of energy with indicator function
I'm looking for a modern explanation/proof of the derivation of Euler-Lagrange (or first-order or the "first variation") conditions for
$$\min_{u \in H^1_0(\Omega), u \geq 0} \int_\Omega |\...
- 93
5
votes
1
answer
355
views
How do you traverse a rectangular grid of points while turning as little as possible?
Suppose I have a lattice grid of $m \times n$ points in the plane, with $m\leq n$. I want to traverse this grid in such a way as to minimize the total amount of turning that occurs. I am pretty sure ...
- 4,049
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 ...
- 990
0
votes
0
answers
39
views
Comonotone solution for Optimal Transport problems with supermodular surplus
In Alfred Galichon's book Optimal Transport Methods in Economics the foollowing result is stated for OT problems on the real line.
Theorem 4.3.(i) Assume that $\Phi$ is supermodular. Then the primal ...
8
votes
2
answers
270
views
Equal segmentation of a series of numbers
How can a series of real numbers be split into subsets in a way that the sum of the real numbers within each subset is as equal as possible?
Coming across from StackOverflow this is the first time, I'...
- 83
2
votes
1
answer
177
views
Optimization over Poisson-binomial distributions
I am studying the problem of how an expected utility maximizer should optimally form a portfolio of uncorrelated Bernoullis.
Fix an increasing sequence of $n$ numbers in $(0,1)$, $0<p_1<\dots<...