Questions tagged [convex-optimization]
Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
702
questions
1
vote
0
answers
11
views
Convergent algorithm for minimizing nonconvex smooth function
Let $\Phi$ be the Gaussian CDF and for $\gamma\ge 0$ and $h>0$, define a loss function $\ell_h:\{\pm 1\} \times \mathbb R$ by
$$
\ell_{\gamma,h}(y,y') := \phi_{\gamma,h}(yy') := \Phi((yy'-\gamma)/h)...
- 5,566
0
votes
1
answer
44
views
Functional relationship between two quantities
Let $\mu \in \mathbb R^n$ and let $\Sigma$ be a positive-definite matrix of order $n \ge 2$. Fix $t \ge 0$ and define $\alpha(\mu,\Sigma,t) > 0$ by
$$
\alpha(\mu,\Sigma,t) := \sup_{\|w\| = 1}\frac{...
- 5,566
0
votes
0
answers
34
views
Some simple conditions on a function $f$ so that $x\mapsto xf(x)$ is convex?
Studying the Braess Paradox for a project at school (with the assiociated Wardrop's equilibria and Nash's game theory result) I came upon one simple question I can not figure out….
If $f$ is a ...
- 1
-1
votes
0
answers
26
views
Calculus of Variations: Uniqueness of a variational problem [closed]
If a Euler Lagrange equation with y(t0) = y0 and y(t1) = y1
for variational problem: max(y) of integral from t0 to t1 of f(t,y,y')dt has a unique solution,
then the variational problem will also has a ...
0
votes
0
answers
60
views
Using the duality theorem for an optimization problem with two variables
I wish to apply the duality theorem to the optimization problem:
$$\text{minimize}~~s$$
$$\text{subject to}~~g_j(x)\leq{s},~~\text{for all}~~j=1,...,r,~~x\in{X},~~s\in{\mathbb{R}},$$
where $X\subseteq{...
- 1
2
votes
0
answers
30
views
Convex optimization over compact sets defined as Aumann set-valued integrals
Let $(X,P)$ be a probability measure space. Let $K$ be a convex compact subset of $\mathbb R^d$ and let $F:X \to 2^{K}$ be a set-valued map. Assume that $F$ is:
closed (i.e $F(x)$ is closed for ...
- 5,566
1
vote
1
answer
93
views
The maximum trace of a covariance can be achieved by a discrete random vector?
Given a random variable $X$, satifying $P(0\leq X \leq 1)=1$, and $\mathsf{E}[X^2] = \alpha$. We know its maximum variance $\text{Var}(X) = \alpha(1-\alpha)$ achived by a binary random variable $P(X =...
- 13
0
votes
0
answers
125
views
Is this function concave? If it is, can we show it in a theoretical way?
Suppose we have a function:
\begin{equation}
\begin{aligned}
f(x_1,x_2,\cdots,x_n)&=\sum\limits_{i=0}^n\frac{(x_i e^{-x_i}-x_{i+1}e^{-x_{i+1}})^2}{e^{-x_i}-e^{-x_{i+1}}}\\
&=\frac{(x_0 e^{-x_0}...
- 81
1
vote
1
answer
44
views
High probability bounds of SGD for general convex functions with suffix averaging
I am interested in finding references that develop high probability suboptimality bounds for stochastic gradient descent (SGD) for general convex functions in the case where we return the average of ...
- 121
3
votes
0
answers
149
views
Simple constructive proof for the hyperplane separating theorem (HST)?
The Hyperplane Separation Theorem (HST) is usually proved through the existence of a unique minimum-norm vector in a nonempty closed convex set. I think this is an existential proof which applies to ...
- 221
1
vote
2
answers
142
views
Can we substitute this KKT condition into this optimization problem to reformulate the optimization problem?
Suppose I have the following optimization problem
$$ \min\limits_{\mathbf{x},\mathbf{y}} f(\mathbf{x},\mathbf{y}) \tag{1} $$
It is already known that the target function $f$ is continuous and ...
- 81
1
vote
0
answers
23
views
Non-differentiability of the set of optima of certain optimization problems
Let $X \subseteq \mathbb{R}^n$ be compact and say the function $f \colon X \to \mathbb{R}$ is locally Lipschitz continuous. Say $\mathcal{X}$ is the set of all solutions of the following optimization ...
- 173
0
votes
0
answers
23
views
Optimization: Minimization when lambda equals infinity
I would like to estimate function g(x) by the following rules:
$$\hat{g}=\arg \min _{g}\left(\sum_{i=1}^{n}\left(y_{i}-g\left(x_{i}\right)\right)^{2}+\lambda \int\left[g^{(m)}(x)\right]^{2} d x\right)$...
4
votes
0
answers
84
views
Does the refined Slater's condition hold also in the infinite-dimensional case?
Let $X$ be an infinite-dimensional Banach space. I have the following optimization problem.
$$\begin{array}{ll} \underset{x \in X}{\text{minimize}} & f(x)\\ \text{subject to} & g_1(x) \leq 0\\ ...
- 41
2
votes
1
answer
58
views
Optimize a function with not-full knowledge of gradient
I want to optimize the following function:
$$
argmin_{x} f(x) = g(x) + h(x)
$$
, where I can get $\nabla_xg(x)$, but cannot calculate $\nabla_xh(x)$.
The derivative-free method, such as the Hill ...
- 31
2
votes
1
answer
179
views
Effect of duplicated row on singular values and vectors
Let $\mathbf{A}$ be a $n\times n$ matrix with Singular Value Decomposition (SVD) $\mathbf{A}=\mathbf{U}\mathbf{S}\mathbf{V}$ and $\mathbf{a}_1$ be the first row of $\mathbf{A}$. What can we say about ...
- 129
0
votes
0
answers
46
views
Minimax problem : uniqueness of a solution
Let $n\geq2$. Is it true that the minimax problem:
$$
\min_{p\in\mathcal{P}}\max_{H\in\mathcal H}p^tH\bar{p},
$$
where
$\mathcal H\subset\mathcal{M}(n)$ is a strictly convex bounded subset of ...
- 3,408
3
votes
0
answers
49
views
For $f$ geodesically convex with $L$-Lipschitz-gradient on hyperbolic space, is $f(x) - f(x^*) \leq (const) \cdot L r$ for all $x \in B(x^*, r)$?
$\DeclareMathOperator\dist{dist}$Setting: Let $M$ be a hyperbolic space of sectional curvature $-1$, and let $f \colon M\to \mathbb{R}$ be a $C^2$, geodesically convex function which has $L$-Lipschitz-...
- 421
0
votes
1
answer
94
views
Estimation via projecting onto a convex body
Assume that $\theta$ is in a convex body $K \in \mathbb{R}^n$ and we observe $y = \theta + z$, where $z$ is a noise term (following, say, the normal distribution). Consider an estimator of $\theta$ by ...
- 623
0
votes
0
answers
39
views
Optimization over algebraic structures other than matrices?
So I've been spending recently going through optimization literature, and to my understanding, much of statistical learning is just solving the following equation:
$$\min_{\theta} f_{\theta}(x) $$
for ...
- 89
0
votes
0
answers
100
views
Is $(K^*)^{**}=(K^{**})^*$ for any cone $K$?
I'm considering the dual cone $K^*$ of a non-convex cone $K$. I came up with a theory that $K^{**}$ is the closure of convex hull of $K$. Then I wonder whether $(K^*)^{**}=(K^{**})^*$ holds for any ...
1
vote
0
answers
62
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} ...
- 1,197
2
votes
2
answers
98
views
Inequality for matrix with rows summing to 1
Let $A$ be real matrix with $M > 1$ rows and $K > 2$ columns, and each entry $a_{m,k} \in (0,1)$, with each row summing to $1$. For all $m$
$$
\sum_{k=1}^{K} a_{m,k} = 1
$$
I want to find out if ...
- 23
0
votes
1
answer
51
views
Maximizing a skew-symmetric 4D cross product
How do I find two orthonormal 4D vectors, $(x_0,x_1,x_2,x_3)$ and $(y_0,y_1,y_2,y_3)$, which maximize this function:
$-19x_1y_0 - 33x_2y_0 + 11x_3y_0 + 19x_0y_1 - 21x_2y_1 - 33x_3y_1 + 33x_0y_2 + ...
- 1,425
0
votes
0
answers
49
views
Weak derivative of projection onto probabilist's simplex
Let $\Delta_n:=\{x\in [0,1]^n:\boldsymbol{1}^{\top}x=1\}$ denote the probabilist's $n$-simplex and let $P:\mathbb{R}^n\rightarrow\Delta_n$ denote the (Euclidean) metric projection onto this simplex ...
- 478
3
votes
1
answer
122
views
On the convexity of certain set of random vectors
Let ${\cal X}$ be the set of pairs of random variables $(X,Y)$ with finite expectations. For constant $c\in[0,1]$, define set
$$
\{(X,Y)\in{\cal X}:\exists a\geq 0, \, b\geq 0 \text{ such that } E[\...
- 2,379
1
vote
0
answers
76
views
Solution of a simple optimization problem
Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...
- 129
0
votes
0
answers
49
views
The best unitary matrices that approximate a matrix product
Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
- 129
4
votes
1
answer
232
views
Which set of functions admits the existence of the minimizer?
Let $a,b \in \mathbb R$ and consider the functional $J$ on $X$:
$$J[u] = \int_0^1 \left( (u'(x))^2 -a)^2 + b \ln (1+ u^2(x))\right) dx$$
Providing reasons specify if the $\inf J$ over $X$ is attained ...
- 223
0
votes
0
answers
51
views
Projection onto a cone followed by a Schur-convex function
Let $Proj_C(x)$ denote the projection of a point $x$ onto a cone $C$. Let $f$ be a Schur-convex function. I'm considering $f(Proj_C(x))$ as a function of $x$.
Are there any conditions on the cone $C$ ...
- 623
1
vote
0
answers
49
views
Optimal bandwidth for a Gaussian filter
I have an $n \times n$ image $A$, and an $m\times m$ image $B$, where $n>m$. As the smaller image looks like a lower-resolution version of the larger one, I'm interested in the relative loss, ...
- 173
1
vote
2
answers
232
views
Optimization of a integral function
I have a function $h(y,x_1,x_2,\ldots,x_n)$. It is known that the minimum value of $h$ for any $y$ is attained when $x_1 = x_n$ and $x_2 = x_3 = \cdots = x_{n-1}$. Now consider the following function
\...
- 167
0
votes
0
answers
54
views
Constrained argmin of a trace
Let $A \in \mathbb{R}^{4 \times 3}$. I am trying to compute
$$\hat{X} = \arg\min_{X \in \mathbb{R}^{3 \times 4}} \frac{\partial\text{Tr}(AX)}{\partial X}$$
with the following equality constraints
$$ ...
- 101
0
votes
0
answers
52
views
Double summation of matrices as constraints in convex optimization in CVX
I want to implement the following optimization problem from the following paper Randomized Gossip Algorithms, Page 10 Eq 53:
\begin{align}
\text{minimize} &\qquad s\\
\text{subject to} & \...
0
votes
0
answers
49
views
sharp $l_{\infty}$-bounds for the LASSO estimator
I have a question regarding sharp $l_{\infty}$-bounds for the LASSO estimator. The linear model is
$$y=X\theta^*+W,$$
where $X\in\mathbb{R}^{n\times p}$ a deterministic matrix (or a probabilistic one ...
- 9
0
votes
0
answers
33
views
Closed form expression for an opt-problem
Consider the following optimization problem
\begin{align}
G(t) = &\max_{x\in R^N} ~~x^\top P x\\
&\mbox{subject to}\\
&\hspace{1cm} x^\top P x \leq t\\
&\hspace{1cm} x^\top x \leq 1,
\...
- 1,126
1
vote
0
answers
24
views
Sufficient condition for an $n$-tuple to be a convex conjugate
We say $(f_1,f_2,\dotsc,f_N)$ is a convex conjugate if for any $i=1,2,\dotsc,N$ and any $x_i\in\Bbb R^d$, we have:
$$f_i(x_i)=\sup\left\{\sum_{k=1}^{N}\sum_{j=k+1}^N x_k x_j - \sum_{j=1,j\neq i}^N f_j(...
- 73
2
votes
1
answer
65
views
Subgradient of a convex integral
I have an integral to minimize that writes like $$F: \mathbb R^d \to \mathbb R: \theta \mapsto \int_{[0,1]^d} f(\langle x,\theta\rangle) dx$$.
The function $f$ is a convex function, which makes $F$ a ...
- 621
2
votes
1
answer
97
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$ ...
- 478
2
votes
0
answers
153
views
Proving an optimization problem from continuous input to binary is optimal
Suppose we have a function $f(x,y,z)$ where the inputs are uniform from 0 to 1. The output is either $+1$ or $-1$. And there is a partial symmetry $f(x,y,z) = f(z,y,x)$.
Tell me what the minimum of ...
1
vote
0
answers
115
views
Is $x\cdot f(x)$ quasiconvex for $x>0$, if $f(x)$ is monotonically decreasing, convex, and positive? [closed]
Original question
Given $f(x):\mathbb{R}^+\to\mathbb{R}^+$, which is monotonically decreasing and convex. Then define a function $g(x) = xf(x)$, I am wondering whether $g(x)$ is quasiconvex for $x>...
- 11
0
votes
0
answers
96
views
Stopping criterion for ADMM
My question is about the stopping criterion for the ADMM algorithm, but some notation needs to be introduced first. The ADMM algorithm solves optimisation problems in the form
\begin{align*}
&\...
- 371
0
votes
0
answers
29
views
Convergence rate for gradient descent approximation algorithms for linear programming
Consider a canonical form for linear programming
$$\max_{x} c^Tx \quad s.t. \quad Ax\leq b $$
where $A\in \mathbb{R}^{m\times n}$.
If a suboptimal solution is acceptable instead of an exact solution, ...
- 101
2
votes
0
answers
60
views
A truncated Frobenius norm of a matrix is convex or not?
Given a positive integer $k$ and a matrix $X\in \mathbb{R}^{m\times n}$. A truncated frobenius norm of a matrix $X$ is defined by
$$\Vert X \Vert_{k,F} = \sqrt{\sum_{i=k+1}^{m} \sigma_i^2(X)},$$
where ...
- 143
2
votes
0
answers
44
views
A variant of the elliptope relaxation
Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...
- 1,931
3
votes
0
answers
74
views
What is the name for this type of optimization problem?
As we all know, a classic optimization problem can be represented in the following way:
Given a function $f: A \to \mathbb{R}$, find an element $x_0 \in A$ such that $f(x_0) \le f(x)$ for all $x \in ...
- 141
3
votes
5
answers
344
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 ...
- 151
0
votes
0
answers
66
views
On least-squares with positive semidefinite constraints
Given real symmetric matrix $\mathbf{R} \in \mathbb{S}^{n\times n}$ and matrices $\mathbf{X}_n, \mathbf{X}_{n-1} \in \mathbb{R}^{n \times m}$,
$$\begin{array}{ll} \underset{\mathbf{A} \in \mathbb{R}^{...
0
votes
0
answers
42
views
How to find a set given its support function
Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function $\delta^*(v|\...
- 53
2
votes
0
answers
28
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 ...
- 621