22

Is the following any clearer? (Read the subscripts carefully!) $$\begin{array}{ll} f_1(y_1) + f_2(y_2) + f_3(y_3) + \cdots + f_n(y_n) &\leq \\ f_1(y_2) + f_2(y_2) + f_3(y_3) + \cdots + f_n(y_n) & \leq \\ f_1(y_3) + f_2(y_3) + f_3(y_3) + \cdots + f_n(y_n) & \leq \\ \qquad \qquad \qquad \vdots & \leq \\ f_1(y_n) + f_2(y_n) + f_3(y_n) + \...


19

Many classically important probability distributions are maximum entropy distributions for suitable constraints, including the normal distribution, exponential distribution, and Poisson distribution. Viewing them as maximum entropy distributions gives a unified viewpoint for why such distributions occur often in practice.


17

This won't be a complete answer to Q2, but something of a starting point, at least for all two-dimensional convex $P$. Assuming for simplicity that the area of $P$ is 1, $P$ contains a parallelogram of area at least $1/2$ (triangular $P$-s are extreme in this respect). This is quite easy to prove, and for polygonal $P$, an algorithm can be produced to find ...


15

Using the operator norm, as you have defined it, the fraction of the unit ball in real symmetric $n$-by-$n$ matrices that consists of positive definite matrices is $2^{-n(n+1)/2}$. Thus, this fraction shrinks very quickly as $n$ increases. Added comment 1: Actually, I just realized that you don't need to do the calculation below; the ratio is obvious ...


14

There is the concept of hyperbolic programming, introduced in the 90's by Osman Güler: O. Güler, Hyperbolic Polynomials and Interior Point Methods for Convex Programming, Math. Oper. Res. 22 (1997) 350-377. See also H.H. Bauschke, O. Güler, A.S. Lewis, H.S. Sendov, Hyperbolic Polynomials and Convex Analysis, Canad. J. Math. 53 (2001) 470-488; J. ...


13

[Edit: I had originally posted a proof that finding the minimum value was NP-hard; in the comments below, Brendan McKay pointed out how to convert that into a proof that finding the maximum value is NP-hard, which was the question asked by the original poster. I have edited this to include a complete answer to the original question.] Let's refer to the ...


12

As far as I know, the state of the art is that one can actually achieve $K=K(n)=O(\log^{\frac{1}{2}} n)$ independent of the dimension $d$. Moreover, one can actually find the weights $w_i$ via an efficient randomized algorithm. This matches the best non-constructive bound due to Banaszczyk. See this paper of Bansal, Dadush and Garg.


11

I think Carlo Beenakker digged up the right reference for the notation of the set, but I think more can be said. First, there is some meaning for the subscript $0$ which can be found in the same paper of Moreau a little later: So $\Gamma(H)$ are all functions that are pointwise suprema of continuous affine functions. This is a neat space since it's ...


10

Restricting to the case where $P$ is triangular, if the angles of the triangle are $A$, $B$, $C$ and you fold the triangle along the bisector to the angle $C$, then assuming wlog that $A<B$, you obtain an overlapping area whose ratio to that of the full triangle is: $$r(A,B)=\frac{\sin A}{\sin A + \sin B}$$ Choosing to fold along the bisector of the ...


10

Anyway, If you know a 5 line proof for the first inequality please share it with us OK, here goes. Assume that $\inf_P f=-1$ and that it is (nearly) attained at the origin. Let $K=\{x\in P: f(x)\le -\frac 12\}$. Then $E=\{x\in P: f(x)<1\}\subset 4K$ by convexity. Also, $|E|\ge |P|/2$ because otherwise $\int_P f=\int_{P\setminus E}f+\int_E f\ge |P\...


10

Yes, they are connected. The first problem is a special case of the second when $\lambda=0$, if the first problem has a unique solution (i.e., $\ker A = 0$), or if the second is also formulated as a double minimization "$\min \|x\|$ such that $x$ minimizes $\|Ax-b\|^2+\lambda \|x\|^2$". But there is also a reduction in the other direction: The ...


9

In finance, finding risk neutral probabilities can be done via max-entropy methods. In short, you observe prices $p_i$ of a finite number of instruments $\phi_i$, and you seek a probability measure $P$ such that $p_i = \int\phi_i\,\mathrm{d}P$. There is in general no uniqueness of $P$, and finding such a $P$ can be challenging. Finding $P$ by a max-entropy ...


9

I would try to approach your original problem a bit differently. Note that $|x-a|\le \frac 12(r|x-a|^2+r^{-1})$ and the equality is attained for $r=|x-a|^{-1}$. Thus, $$ \min_x[|x-a|+\langle b,x\rangle]=\frac 12\min_r\min_x[r|x-a+r^{-1}b|^2+r^{-1}(1-|b|^2)]+\langle a,b\rangle $$ However, the inner minimum can be now found rather quickly and finding the ...


9

Take $\mathcal X = L^1(\Omega,\mu)$ where $\Omega = \{1,2,3,\dots\}$ and measure $\mu(\{k\}) = p_k$ with $p_k > 0$, $\sum p_k = 1$. The norm in $\mathcal X$ is $$ \|f\|_{\mathcal X} = \sum_k |f(k)|p_k . $$ Let $\mathcal Y = \mathbb R^2$ with norm $$ \|(x,y)\|_{\mathcal Y} = \frac{1}{2}|x|+\frac{1}{2}|y|. $$ Thus $\mathcal Y$ is also $L^1$ of a ...


9

Here's one way to see this directly. I will assume that $A$ is $m \times n$. Let $$ A = U \Sigma V^T$$ be the SVD for A. Recall that the regularized solution to the least squares problem $Ax = b$ is given by $$\hat{x} = (A^TA + \lambda I)^{-1}A^Tb.$$ Now substitute the SVD of $A$ in place of $A$. Simplifying algebra, we get that $$\hat{x} = V(\Sigma^T \...


8

The Frobenius norm does not cause a problem. Remember, the Frobenius norm of a matrix $X$ is actually nothing more than the 2-norm of the vector formed by stacking the columns of $X$ on top of each other. And for vectors, the vector 2-norm and the matrix 2-norm coincide. So if $\mathcal{Q}$ implements this "stacking" isomorphism, we have $$\|\mathcal{P}_\...


8

The most general form of such algorithms are named Mirror-Descent. This algorithm is an extension of gradient descent for non-Euclidean geometries. For a formal explanation on how multiplicative weights (or exponentiated gradient descent) is a particular setup for Mirror-Descent see Appendix A.2 from http://arxiv.org/abs/1407.1537


8

TL;DR : Yes, the two problems are equivalent in the limit $\lambda \rightarrow 0$ ! One freely available reference is the following (excellent in my opinion) review paper : https://arxiv.org/abs/1110.6882 Specifically, your question is addressed on Theorem 4.3 of this paper on Tikhonov’s Regularization.


8

By Carathéodory's theorem, if the origin in $\mathbb{R}^{32}$ is contained in the convex hull of the set $$ X_c = \{\,(x, y, x^2 - 1, \ldots, y^8 - 14) \mid -2 \le x, y \le 2, x + y \ge c\,\} $$ then there exist some 33 points in $X_c$ whose convex hull contains the origin. Thus, your question is equivalent to: Find the maximum value of $c$ such that: ($*$) ...


7

Symmetry groups are certainly an issue in integer programming. Orbital branching is one way of dealing with it. Core points are another relevant concept.


7

A nonempty set $S$ in a normed linear space $X$ is called a Chebyshev set if for each $u \in X$ there is exactly one nearest point in $S$ to $u$ (i.e., for a Chebyshev set, nearest points always exist, and they are unique). For finite dimensional spaces it is known that: Theorem. A nonempty set in the Euclidean space $R^n$ is Chebyshev if and only if it ...


7

I have found this book a useful reference: Maximum-entropy Models in Science and Engineering It may contain some pointers to applied work that you will find convincing (I don't have it on me right now) if you can get a copy.


7

Every monic integer polynomial $f(x) \in \mathbb{Z}[x]$ of degree $n$ is the characteristic polynomial of an $n \times n$ matrix, namely its companion matrix. The companion matrix is invertible iff the constant term of $f(x)$ is $\pm 1$. Conversely, every characteristic polynomial of an element of $GL_n(\mathbb{Z})$ has this form. So the question reduces to ...


7

Yes, the same approach can be used for complex matrices, with the constraint becoming $\left[ \begin{array}{rr} W_{1} & X \\ X^{H} & W_{2} \\ \end{array} \right] \succeq 0 $ Here, the constraint says that the matrix must be Hermitian (rather than symmetric) and positive definite. However, not all SDP solvers directly support complex matrices. ...


7

The set of $n \times n$ symmetric Toeplitz matrices is $$\left\{ x_1 \mathrm M_1 + x_2 \mathrm M_2 + \cdots + x_n \mathrm M_n \mid x_1, x_2, \dots, x_n \in \mathbb R \right\}$$ where $\mathrm M_1, \mathrm M_2, \dots, \mathrm M_n$ are $n \times n$ symmetric Toeplitz basis matrices. Let $\mathrm M_1 = \mathrm I_n$ correspond to the main diagonal, whereas the ...


7

It seems the notation $\Gamma_0$ was introduced by Jean-Jacques Moreau in Proximité et dualité dans un espace Hilbertien (1965), as a generalisation of the notion of projection onto a convex domain (see screenshot). No explanation is given for the subscript $0$, but the connotation with a projection seems natural.


7

For fixed $d$, one can actually achieve a bound independent of $n$. More precisely, $K=K(d)=O(\sqrt{d})$ is fine, uniformly in $n$. Proof : the unit ball of $\mathbb{R}^d$ can be covered by $2C^d$ balls of radius $\frac{1}{2}$, for some absolute constant $C$. Let $v_1,\dots,v_n$ be $n$ vectors in $\mathbb{R}^d$ of norm at most $1$. If $n>2C^d$, then one ...


7

Jensen's inequality $\int c(f)\,d\mu \ge c(\int f\,d\mu)$ is always equality when $f$ is constant, so you know that taking $dz/dt$ constant would saturate it. That means $z(t)$ has to be linear, and since you know the endpoints, $z$ is determined. Also useful to know is that when $c$ is strictly convex, a constant (almost everywhere) is the only way to ...


7

Let $x$ be the smallest nonzero eigenvalue of $A$. It is the reciprocal of the largest root of $$f(t)=-\det(t(D-aa^\top)-I),$$ where $D$ is the diagonal matrix. By the matrix determinant lemma, \begin{align} f(t)&=-\det(tD-I)(1-ta^\top(tD-I)^{-1}a)\\ &=-\det(tD-I)\left(1-\sum_{i=1}^d \frac{ta_i^2}{ta_i-1}\right)\\ &=-\det(tD-I)\left(1-\sum_{i=1}^...


7

The answer is no. See Rockafellar's Convex Analysis, part V. First, let $D$ be the set of points where $F$ is differentiable. Theorem 25.5 proves that $D$ is dense in the interior of the domain of $F$, with measure zero complement. And that $\nabla F$ is a continuous mapping on $D$. Next, if the domain of $F$ has non-empty interior, then at every interior ...


Only top voted, non community-wiki answers of a minimum length are eligible