Questions tagged [convex-optimization]

Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes

Filter by
Sorted by
Tagged with
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)...
user avatar
  • 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{...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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{...
user avatar
  • 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 ...
user avatar
  • 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 =...
user avatar
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}...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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)$...
user avatar
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\\ ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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} ...
user avatar
  • 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 ...
user avatar
  • 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 + ...
user avatar
  • 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 ...
user avatar
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[\...
user avatar
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{...
user avatar
  • 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 $\...
user avatar
  • 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 ...
user avatar
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$ ...
user avatar
  • 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, ...
user avatar
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 \...
user avatar
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 $$ ...
user avatar
  • 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} & \...
user avatar
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 ...
user avatar
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, \...
user avatar
  • 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(...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
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>...
user avatar
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*} &\...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}^{...
user avatar
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|\...
user avatar
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 ...
user avatar
  • 621

1
2 3 4 5
15