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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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*}
&\...

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

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

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

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

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

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

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