All Questions
Tagged with convex-optimization reference-request
45 questions
9
votes
4
answers
524
views
Abstract treatment of multivariate calculus relevant for optimization
After studying the basics of (convex) optimization, I've become convinced there's sometimes a conceptual benefit in thinking of quantities like gradients etc. in a coordinate-free way, and keeping ...
- 997
9
votes
1
answer
749
views
property of convex functions
I am able to give a proof to the following inequality for convex functions. Most likely this is well known, but I am unable to find a reference. I would appreciate if someone more knowledgeable in the ...
- 1,211
7
votes
2
answers
251
views
What methods do we have to understand the spectrum of matrices with restricted entries?
Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"),
What is the largest possible spectral radius of a $...
- 1,893
7
votes
1
answer
216
views
How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?
This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...
- 1,350
6
votes
2
answers
2k
views
Wasserstein distance and the Kantorovich-Rubinstein duality
The only few references I could find on this topic are either amateur blog posts (http://n.ethz.ch/~gbasso/download/A%20Hitchhikers%20guide%20to%20Wasserstein/A%20Hitchhikers%20guide%20to%...
- 2,246
5
votes
1
answer
329
views
Reference for the rectifiablity of the boundary hypersurface of convex open set
The boundary of any convex open set $X$ is $\mathbb R^n$ is a rectifiable hypersurface.
To see this, intuitively, simply take a sphere $S_d$ with diameter $d\in(0,+\infty]$ that contains $X$. The ...
- 263
4
votes
5
answers
2k
views
Reference request: importance of Lipschitz continuity
I see that Lipschitz continuity is a common assumption used in optimisation, statistics, machine learning, etc.
Could you point me in the direction of some literature that discusses why Lipschitz ...
- 161
4
votes
1
answer
1k
views
Does the Legendre-Fenchel transform/convex conjugate of strongly convex functions have any desirable properties?
It is well known in convex analysis that when a closed, proper, function $f$ is Legendre-type, that is, essentially strictly convex and essentially smooth, the Legendre transform yields a dual ...
- 205
4
votes
0
answers
260
views
$L^2$-projection onto monotone functions
Let $f:{\mathbb R}\rightarrow{\mathbb R}$ be measurable and such that
$$\int_{-\infty}^0(f(x)-a)^2dx+\int_0^{+\infty}(f(x)-b)^2dx<+\infty.$$
This, denoted as $E(a,b)$, is an affine space: $E(a,b):=...
- 52.3k
4
votes
0
answers
236
views
Fréchet subdifferentiation on riemannian manifolds
Context. I'm looking for a "natural" definition of subdifferentials on riemannian manifolds.
Given a function $F:\mathbb R^m \to \mathbb R$, its Fréchet-subdifferential at a point $w \in \...
- 6,853
4
votes
0
answers
509
views
analytic approximations of the min and max operators
Question:
What is the state of the art on analytic approximations of $\min$ and $\max$? My hunch is that numerical analysts probably have a better solution than the one I propose here.
For any $\...
- 3,871
3
votes
2
answers
2k
views
Strict complementary slackness for semidefinite programs with strong duality
By a theorem of Goldman and Tucker it is known that if a linear program (LP) has a finite valued optimal solution, then there is an optimal primal/dual pair $(x,z)$ satisfying not only complementary ...
- 13.6k
3
votes
2
answers
207
views
Generalizing Pythagorean Theorem: equations defining edges of a (convex) $n$-gon with $n-2$ prescribed angles?
Let $n\geq 3$ be an integer and $0<\alpha_1, \dots ,\alpha_{n-2}<1$. Let's say a tuple of positive numbers $(e_1,\dots, e_n)$ is nice if there is a convex $n$-gon $A_1\dots A_n$ such that $\hat ...
- 30.5k
3
votes
1
answer
266
views
Strong polynomial algorithm for linear programming
What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?
- 781
3
votes
1
answer
189
views
Sensitivity of the solution of QP with respect to parameters
Given a quadratic program,
$$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$
Suppose $A \succ 0$, so the program strongly ...
- 33
3
votes
1
answer
170
views
Reformulation as optimization on probability distributions
This is a "soft" question, in the sense that I'm looking for historical remarks and general commentary rather than a definite answer.
For compact $X \in R^n$ and $f : R^n \to R$ consider the problem
...
2
votes
1
answer
399
views
Smoothness of Minkowski functional is equivalent to smoothness of boundary
Let $C\subseteq \mathbb{R}^n$ be a convex body containing $0$ in its interior. I recently read that Minkowski functional of $C$,
$$
f_C(x):=\inf\Big\{t>0:\frac1{t}\cdot x\in C\Big\},
$$
is $C^1$ ...
- 5,405
2
votes
1
answer
250
views
Circumscribed ellipsoid of minimum Hilbert-Schmidt norm
Let $K\subseteq \mathbb{R}^n$ be a full-dumensional convex body. The Löwner ellipsoid of $K$ is the unique ellipsoid of smallest volume containing $K$. My question is about a related object: the ...
- 757
2
votes
1
answer
345
views
Can the subdifferential become unbounded at interior points?
Consider $f: \mathbb{R}^n \to \overline{\mathbb{R}}$ a lower-semicontinuous, proper, closed and convex. My question is, can the subdifferential of $\partial f$ be unbounded in the interior of $\text{...
- 179
2
votes
1
answer
255
views
Efficient algorithm for solving a convex quadratic program [duplicate]
Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently?
$$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$
- 422
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
2
votes
0
answers
95
views
Self adjoint operators from energy functionals
It is known that the equation
$$
\Delta f = 0
$$
on some bounded domain $\Omega$ on $\mathbb{R}^n$ subjected to certain boundary conditions can be derived through the minimization of the Dirichlet ...
- 115
2
votes
0
answers
37
views
Stochastic gradient descent in 'stronger' settings
I am minimzing a function $F(x) = \mathbb E(f(x,\Xi))$ where $\Xi$ is some random value, by a stochastic gradient descent that generates a random number $\xi$ from the distribution of $\Xi$ at each ...
- 686
2
votes
0
answers
98
views
State-of-the-Art algorithms for bilevel optimization
I want to numerically solve a bilevel optimization problem of the form
$$ \min_y f(y, \hat x(y)), \qquad \hat x(y) = \arg\min_x g(x, y) $$
(for simplicity assume that $\min_x g(x, y)$ exists and is ...
- 121
2
votes
2
answers
323
views
Reference request on computational schemes for $\inf_{x\in\Omega^n}\sup_{y\in\mathbb R^n}F(x,y)$
Let $\Omega\subset \mathbb R^d$ be compact, $\rho$ be a density function on $\Omega$ and $p_1,\ldots, p_n\in (0,1)$ be weights satisfying $\int_{\Omega}\rho(z)dz=1=\sum_{k=1}^n p_k$. We consider the ...
user128095
2
votes
0
answers
282
views
Reference request: functional analysis results used in Taubes paper (1980)
I am studying Taubes paper 'Arbitrary N-vortex solutions to the first order Ginzburg-Landau equations'. I am looking for a reference of three following theorems:
Let $f(x)$ be a convex funtional ...
- 31
2
votes
0
answers
83
views
Reference request: Edmond's Algorithm for integer hull
I'm looking for a good reference for the algorithm (supposedly by Edmonds) to compute the integer hull of a polytope, not by cutting plane methods but by starting with a set of integer points and then ...
- 243
2
votes
0
answers
614
views
Lipschitz continuity of solution set mapping of a parametric convex optimization problem
I have a parametric convex optimization problem:
\begin{array}{cl}
\underset{x}{\text{minimize}} & f\left(x,z\right)\\
\text{subject to} & g\left(x\right)\leq0
\end{array}
where $x$ is the ...
- 21
1
vote
1
answer
113
views
Expected rank - computable approximations
I'm interested in finding the expected rank of some random matrix $A$ (I don't want to specify its distribution right now, since my question makes sense in general).
Computing $\mathbb{E} \ \mathrm{...
- 3,323
1
vote
1
answer
447
views
Nested convex optimization
Suppose I have a convex optimization problem of the form $$\min_x f(x) ~~s.t.\\x\in X$$. Say that $f(x)$ and its (sub)gradient are not given in a closed form, but are determined by solving a convex ...
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 ...
- 1,759
1
vote
1
answer
309
views
Numerical estimation of partial derivatives of convolved functions when closed forms do not exist
Summary: Some peak functions are convolutions which may not have a closed form solution. A classical example can that of a Voigt which is a convolution of a Lorentzian and a Gaussian, followed by ...
- 879
1
vote
0
answers
73
views
Principal component analysis with boundedness constraints
Let $A$ be an $m\times n$ matrix with entries in $F$ ($F=\mathbb{R}$ or $F=\mathbb{C}$).
It is well-known that $A$ has decompositions of the form
$$\displaystyle A = \sum_{k=1}^r\lambda_k\hspace{2mm} ...
- 2,605
1
vote
0
answers
38
views
Solution to dynamic program-type recursion
I have the following dynamic programming principle-type problem.
Suppose that we are given a sequence $\beta_1,\dots,\beta_n\in (0,\infty)$, some target $y\in (0,\infty)$ with $y>\sum_{t=1}^N \...
- 109
1
vote
0
answers
70
views
Solve simple stochastic variational inequality
Let $Z$ be a random variable with finite mean $\mathbb E[Z]$ and let $\phi:(-\infty,\infty) \rightarrow (-\infty,\infty]$ be a convex l.s.c function which is differentiable at $z=1$ with gradient $\...
- 6,853
1
vote
0
answers
267
views
Minimum Preserving Transformations [closed]
If $f:X\rightarrow Y$, $g:Y\rightarrow Y$ are functions and $g$ is monotone increasing function then
$$
\operatorname{argmin}_{x \in X} f(x)
=
\operatorname{argmin}_{x \in X} g\circ f(x) .
$$
X and Y ...
- 5,405
1
vote
0
answers
135
views
Intuition for analysis of basic gradient descent variants
I'm currently learning the basic variants of gradient descent for minimizing convex functions under various assumptions, such as Lipschitz, smooth, strongly-convex, ... .
I've found various sources ...
- 997
1
vote
0
answers
152
views
Well-posedness of gradient flows
For a convex lower-semicontinuous functional on a Hilbert space $I\colon H\rightarrow\mathbb{R}$, it is shown in Evans' PDE that the Hilbert-space-valued ODE
$$\begin{cases}\mathbf{u}'(t)\in-\partial ...
- 123
0
votes
1
answer
172
views
constrained optimization problem/proof
Im trying to maximize the probability of a particular outcome occurring subject to a constraint. In particular
$$\max \prod_{i \leq n} 1 - (1 - x_i)^{y_i} \;\;\; \text{ s.t. } \;\;\; i \in \mathbb{N}...
- 109
0
votes
1
answer
261
views
Non-asymptotic convergence rates for gradient descent
I'd like to know how the number of steps needed for gradient descent depend on properties of the Hessian in non-asymptotic regime.
More specifically, number of gradient descent steps needed to obtain ...
- 2,442
0
votes
1
answer
329
views
Gradient-descent "type" Methods for non-convex and non-smooth functions
Most (stochastic) "gradient descent" type algorithms (such as Nesterov-accelerated gradient-descent or ADAM) seem to be well-defined only for functions which are either:
lower semi-...
- 5,405
0
votes
1
answer
291
views
Quasiconvexity property of quasinorms
Schatten $p$ norm is convex when $p\geq1$ holds and if $p\in(0,1)$ it is quasinorm.
If $p\in(0,1)$ then is Schatten $p$ norm quasi convex? I am interested in definition of quasi convexity here https:...
- 13.9k
0
votes
0
answers
45
views
Generalized envelope theorems
I'm looking for references for two generalizations of Danskin/envelope-type theorems for convex optimization. The first is for when the parameters are functions on a space rather than numbers. A ...
- 4,217
0
votes
0
answers
166
views
Literature request: proving or disproving convexity of the optimal value function of semidefinite program (SDP) or convex optimization in general
Suppose I have a function $f:\mathbb{R}\rightarrow \mathbb{R}$ defined as the following parametric optimization problem:
$$f(p) = \inf_xf_0(x) \quad \text{subject to } \quad G(x,p)\leq 0,$$
where ...
0
votes
1
answer
125
views
Are there search algorithms that are competitive against (gradient based) optimization routines for continuous problems?
Suppose that $f: \mathbb{R}^n \to \mathbb{R}$ is a continuous function for which we want to minimize. We may arbitrarily impose good conditions for $f$, such as Lipschitzness, smoothness, convexity, ...
- 479