# 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
Filter by
Sorted by
Tagged with
1 vote
11 views

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

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

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

1 vote
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{...
49 views

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 isy=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 functionf$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>...
96 views

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