21
votes

### Is There an Induction-Free Proof of the 'Be The Leader' Lemma?

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(...

17
votes

### How to make a sandwich from just one piece of bread?

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 ...

14
votes

### More general than semidefinite program?

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) ...

13
votes

### Current state of the Komlos conjecture on vector balancing

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 ...

11
votes

Accepted

### Why are $\Gamma_0$ functions called this

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 ...

10
votes

### How to make a sandwich from just one piece of bread?

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 ...

10
votes

Accepted

### property of convex functions

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 ...

10
votes

Accepted

### Closedness of linear image of positive L1 functions

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)|...

10
votes

### Is the pseudoinverse the same as least squares with regularization?

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 ...

10
votes

Accepted

### Optimal polynomial approximation of rational function $\frac{1}{1-x}$

This problem has an exact solution, written in the book
N. I. Akhiezer, Theory of approximation. Dover Publications, Inc., New York, 1992, Chap II section 37.
The error is
$$\frac{(1-\sqrt{1-\rho^2})^...

9
votes

### Minimize sum of $\ell_2$ norm and linear combination, on simplex

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\...

9
votes

Accepted

### Current state of the Komlos conjecture on vector balancing

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$ ...

9
votes

Accepted

### Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension

$\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\varepsilon}$
Take any probability measures $P_0,P_1$ absolutely continuous with respect (w.r.) to $Q$.
We shall prove the ...

9
votes

Accepted

### Is the pseudoinverse the same as least squares with regularization?

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 ...

8
votes

### Bounding the spectral gap of a simple symmetric matrix

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{...

8
votes

### Is the pseudoinverse the same as least squares with regularization?

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....

8
votes

### Is this geometrically-defined minimum an algebraic number?

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 ...

7
votes

Accepted

### Nuclear norm (convex) minimization with complex-valued matrices?

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 ...

7
votes

### An intuition for three different types of subgradients (proximal, regular, limiting)

This might not be a satisfying answer, but this is how I personally deal with this issue (at least in the topic of optimization).
I think these concepts are not made for actually computing them but ...

7
votes

Accepted

### Finding Toeplitz matrix nearest to a given matrix

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, \...

7
votes

### Why are $\Gamma_0$ functions called this

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 (...

7
votes

Accepted

### Optimization problem with determinant as objective

One can verify that $U_{A}=U_{S}$ as follows. Note that $$\det(U_{A}\Sigma_{A}V_{A}^{T}+U_{S}\Sigma_{S}V_{S}^{T})=\det(\Sigma_{A}+U_{A}^{-1}U_{S}\Sigma_{S}V_{S}^{T}V_{A}^{-T})$$
Let $Y=U_{A}^{-1}U_{S}...

7
votes

Accepted

### Inf of Jensen's inequality

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 ...

7
votes

Accepted

### How to apply Hahn-Banach to the convex hull?

To solve the problem you mention at the end you can argue in this way:
$$
\min_{m \in \mathrm{conv} (M)} \|m\|_{2}=\min_{m \in \mathrm{conv} (M)} \max_{\|\alpha\|_{2}\leq 1} \langle \alpha, m\rangle = ...

7
votes

Accepted

### Nondifferentiable convex function whose subdifferential admits a continuous selection

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$,...

7
votes

Accepted

### Reference request: importance of Lipschitz continuity

In Mathematical/High Dimensional Statistics:
One fairly amazing result is for $X=(X_1,\dots,X_n)$ where the coordinates are i.i.d. standard Gaussians, and $f:R^n \to R$ a $L$-Lipschitz function (w.r.t....

6
votes

### Complexity of convex quadratically constrained quadratic programming (QCQP)

Convex quadratically constrained quadratic programming (QCQP) can be reduced to semidefinite programming (SDP). Suppose that we are given the following convex QCQP in $\mathrm x \in \mathbb R^n$
$$\...

6
votes

Accepted

### L-infinity-norm regularized proximity problem

This is indeed a classic problem. Recall the more general problem of computing the prox operator of an lsc convex function $f$, i.e.,
\begin{equation*}
\text{prox}_f(y) := \operatorname{argmin}\quad \...

6
votes

### algorithm for finding the minimizer of a almost convex function

How abou trying to apply the Golden Search algorithm?

6
votes

Accepted

### Is the solution of this optimization problem always positive semidefinite?

No, it is not always attained at a positive semidefinite matrix. The simplest example I have been able to find to demonstrate this is as follows:
\begin{align*}
U = \{ (1,0), (0,1), \tfrac{1}{\...

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

#### Related Tags

convex-optimization × 770oc.optimization-and-control × 201

nonlinear-optimization × 176

convex-analysis × 146

linear-algebra × 110

linear-programming × 89

fa.functional-analysis × 83

convexity × 68

real-analysis × 62

global-optimization × 57

convex-geometry × 56

reference-request × 43

pr.probability × 42

matrices × 40

convex-polytopes × 36

semidefinite-programming × 35

na.numerical-analysis × 28

inequalities × 24

ca.classical-analysis-and-odes × 22

combinatorial-optimization × 20

st.statistics × 19

mg.metric-geometry × 18

probability-distributions × 18

duality × 18

quadratic-programming × 18