# Questions tagged [convex-optimization]

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

800 questions
Filter by
Sorted by
Tagged with
52 views

### Convexifying a Non-Linear Fractional Function

I am working on a problem that involves a non-convex, non-linear fractional function: $$Y(X_1, X_2) = \frac{X_1 + X_2}{\alpha X_1 + \beta X_2}$$ Where $X_{1}$, $X_{2}$, $Y$ are decision variables ...
36 views

### Do separable cubic constraint and separable quartic constraint SOCP presentable?

I am an engineer who is doing some network modeling and optimization. During my work, I was running into a case that is quite strange. The problem that I am trying to solve seems to be convex and it ...
135 views

1 vote
36 views

### What is the closed form of a polyhedral cone's dual cone?

A polyhedral cone can be defined as $$\mathcal{K} = \{x~|~Ax\preceq 0\},$$ where $A \in \mathbb{R}^{m \times n}$, $x\in \mathbb{R}^n$ and $\preceq$ denotes component-wise less than and equal to. The ...
1 vote
29 views

### Variants of cutting plane method for convex optimization

The cutting plane approach in convex optimization is a general recipe for minimizing a convex function. The argument relies on the fact that using the gradient vector, we can cut the feasible set into ...
• 139
82 views

173 views

### Is there a closed-form solution for $\max_D \operatorname{Tr}(ADBD)$

Is there a closed-form solution for $$\max_D \operatorname{Tr}(ADBD)$$ where $D$ is a $N\times N$ diagonal matrix with $m<N$ number of $1$'s and the rest are $0$'s, and $A$ and $B$ are real ...
• 389
1 vote
278 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 ...
• 803
114 views

1 vote
80 views

• 31
92 views

• 299
114 views

### Max-cut from Laplacian

(This question seems like very standard material for those well-versed in the subject. I thought I would get a quick answer from Math stackexchange, but to no avail.) Given a weighted graph with $n$ ...
• 511
1 vote
163 views

### Maximization of $\ell^2$-norm

Consider for $r,c>0$ the set $$X_{r,c}=\{x \in \ell^1(\mathbb{N}) \mid \|x\|_1=r,\, \forall i \in \mathbb{N}: |x_i|<c\}.$$ Then I can show that $\inf_{x \in X_{r,c}} \|x\|_2 = 0.$ But is it ...
139 views

### Inf-convolution of norm 1 and norm 2 square

The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is $$h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) .$$ We can prove that if $f,g$ are convex functions, then $h$ is convex. ...
• 129
91 views

• 975
1 vote
107 views

### Can the ideas of convex optimization be used to prove a bound?

If we define $\lambda(n)=\lfloor \log_2(n) \rfloor$ and $v(n)$ as the binary digit sum of positive integer $n$ we can make a toy example of what I think is the most important conjecture in addition ...
1 vote
126 views

Let $a,b$ be two vectors with strictly positive elements and $\delta = 1 - \frac{\langle a,b \rangle}{\|a\|\|b\|}$. Bound the following optimization problem as a function of $\delta$ $$\sup_{x>0} \... • 135 0 votes 0 answers 26 views ### Convergence bound for zero-order optimization method I would like to understand the error bound for a particular zero-order optimization method: (stochastic) difference method. To solve an nonsmooth optimization problem min_x G(x) where G is only a ... • 771 0 votes 0 answers 72 views ### Error bound for stochastic gradient descent method To solve an optimization problem \min_x G(x) using standard stochastic gradient descent method, we let x_0 be the initial point and x_k be the k-th point such that x_k = x_{k-... • 771 2 votes 1 answer 222 views ### Boundary points in \overline{\operatorname{conv}\{z_i\}_{i\in I}} Let X be an infinitely-dimensional Banach space and \{z_i\}_{i\in I} be a set of linearly independent points in X_{\leq 1}, the closed unit ball of X. I the index set is not necessarily ... 1 vote 1 answer 82 views ### optimization over moving domains Let A, B be Banach spaces, and for any a\in A, B_a\in B is a measurable subset. Consider the following optimization problem:$$L(a)=\inf_{b\in B_a}\ell(b),$$where \ell(b) is a infinite-times ... • 87 1 vote 0 answers 53 views ### LICQ vs MFCQ who is stronger [closed] I want to ask you which constraint is stronger: MFCQ or LICQ. • 11 2 votes 1 answer 143 views ### Optimization over permutation The Problem This is the problem I am working on: Given a set X = \{x_1, x_2, \cdots , x_n\} in a metric space, find an optimal ordering \pi : X \rightarrow X that maximizes the following objective ... • 43 2 votes 1 answer 141 views ### Distance between convex hulls in a bounded closed convex set Let X be an infinite-dimensional Banach space and C\subseteq X be a bounded closed convex subset. Let \{z_i\}_{i\in\mathbb{N}} be a sequence of linearly independent points in C and for each n\... 0 votes 0 answers 185 views ### How expensive is a proximal operation? In optimization, a proximal step is usually considered as cheap as a gradient step. I'm quite confused by this. Why are people taking this convention at all? A typical proximal step indeed incurs a ... • 31 0 votes 0 answers 128 views ### Convex conjugate of the sum of smallest elements I recently came across this problem to find the conjugate function of the sum of r smallest elements in a vector$$f(x) = \sum_{i=n-r+1}^{n}x_{[i]} \text{ for } x \in \mathbb{R}^n$$where x_{[i]} ... 0 votes 0 answers 54 views ### Relationship of optimal solutions between the total function and the sub function This is an unconstrained convex optimization problem. Let \mathcal{N}=\left\{1,\ldots,n\right\}, 2\leq n<\infty. Suppose there are many strongly convex functions f_i(x), where x\in\mathbb{R}^... • 1 1 vote 1 answer 187 views ### Does the value function of a quadratic program stay convex when adding constraints? I am interested in the value function of a quadratic program of the form$$ v(y)=\min_x \frac{1}{2} x^\top Q(y) x, $$subject to a linear equality constraint$$ E(y)x=d(y),  and a linear inequality ...
• 379
For $K \geq n$ and some $\sigma_i > 0$, I am looking for a solution to the following optimization problem: \underset{\begin{smallmatrix} t_1, \cdots, t_n \in \mathbb{N}^{*} \\ \...
\begin{eqnarray} \arg\max_{k}\sum_{i=1}^{p}\sum_{j=1}^{p}\exp\left(-{\frac{\left(X(i,j)-{U_k}(i,j)\right)^2}{2}}\right),\:\: k=0,\dots,p \end{eqnarray} where $X$ and $U_k$ are the $p\times p$ matrices,...