# 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

0
votes

0
answers

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

0
votes

1
answer

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

3
votes

0
answers

135
views

### Interchange limit and supremum of functionals over a bounded convex set

Let $(H, \langle\cdot,\cdot\rangle)$ be a separable real Hilbert space and $B\subset H$ be (nonempty) convex and bounded, and suppose that $(\alpha_k)\subset H$ is a sequence for which the limit $\...

0
votes

1
answer

69
views

### Clarification about this optimisation problem

Good morning everybody. First of all, I apologise to ask here the same question I asked on MSE three days ago, but I am in fact re-asking since I obtained no relevant advice. Perhaps I will hear some ...

1
vote

0
answers

25
views

### When does an optimal input sequence for a discrete-time system exist?

Suppose an LTI discrete-time system is given by the equations
$$
x_{k+1} = Ax_k + Bu_k,\\
y_{k} = Cx_k + Du_k
$$
with $x_k\in\mathbb{R}^{m}$, $y_k\in\mathbb{R}^{n}$ and $u_k\in\mathbb{R}^{p}$ and $\...

1
vote

0
answers

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

0
answers

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

0
votes

0
answers

82
views

### Comparison between the expected values of the inverse of the CDF of binomial-distributed random variables

Let us denote with $F(x;j,\mu)$ the cdf of a Binomial distributed random variable with $j$ trial with success probability $\mu$ considered in $x$, and let $f(x;j,\mu)$ be the pmf. Defining $0\leq \...

0
votes

0
answers

43
views

### Gradient-based optimization of $n$ functions

I appreciate the willingness of everyone to assist me in advance.
I am faced with a set of $n$ distinct convex optimization problems, each defined as follows:
\begin{equation}
\max\limits_{x \in \...

0
votes

0
answers

21
views

### The existence of convergent subsequences

Considering an optimization problem on an infinite-dimensional Euclidean space, the sequence of objective functions is $J_{n}(\theta_{n})=||f(X,\theta_{n})-Y||^{2} $, where X and Y are datas.
This can ...

0
votes

1
answer

78
views

### Optimality condition for strongly convex function under sparsity constraint

Let $f: \mathbb{R}^p \to \mathbb{R}$ be a $2s$-sparse strongly smooth, $2s$-sparse strongly convex and twice differentiable function. In other words, there exists positive constants $\alpha, L >0$ ...

1
vote

0
answers

29
views

### How to extract 'top k' multiple solutions from a quadratic optimization problem?

Imagine we are interested in the following problem:
$$
\min_{w} \left( w^T V w + \lambda \|w\| \right) \\
\text{s.t. } w^T R \geq c
$$
Where 𝑤 is an $N \times 1$ vector, $V$ is an $N \times N$ ...

0
votes

0
answers

26
views

### Application of greedy approach for optimization

I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$
where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...

3
votes

2
answers

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

1
vote

1
answer

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

2
votes

1
answer

114
views

### Convexity of a function

Let: $F_{j+1,y}(s)$ be the cumulative distribution function of a binomial distribution with mean $y$, $j+1$ independent trials considered for $s$ successes. Is it possible to show in any way that:
$\...

2
votes

0
answers

50
views

### Instances of c-concavity outside of optimal transport?

Let $X$ and $Y$ be metric spaces, and let $c:X\times Y\rightarrow \mathbb{R}$ be a nonnegative function which we refer to as a cost. For any $\phi:X\rightarrow \mathbb{R}$ and $\psi:Y\rightarrow \...

1
vote

1
answer

80
views

### Norm bound in simultaneous stability to semidefinite program

In the context of robust control, I remember hearing that the two following problems are equivalent.
Find $P \succ 0$, such that $A P + P A^{\top} \prec 0$ for all $A \in \mathscr{A}$ where $$\...

0
votes

0
answers

36
views

### Generalized envelope theorems

I'm looking for references for two generalizations of Danskin/envelope-type theorems for convex optimization. The first is for when the parameters are functions on a space rather than numbers. A ...

4
votes

0
answers

214
views

### Economic equilibrium and tropical geometry

There is a famous saying in economics: When everyone pursues his or her own interests, there is an invisible hand that brings the market to equilibrium. However, this is not always the case. Here is ...

2
votes

0
answers

114
views

### Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$

Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...

0
votes

0
answers

29
views

### Characterization of functions whose epigraph has a self-concordant barrier

Self-concordant barriers, particularly those that can be computed efficiently, are essential ingredients in solving convex optimization problems using interior-point methods. I am particularly ...

2
votes

1
answer

321
views

### Simple proof for convexity of a real valued matrix function

I am looking for a simple and short proof showing that $X \to \|X X^\top\|_F^2$ is a convex function where $\|\cdot\|_F$ is the Frobenius norm. I have one proof by showing that the derivative is ...

2
votes

0
answers

90
views

### Self adjoint operators from energy functionals

It is known that the equation
$$
\Delta f = 0
$$
on some bounded domain $\Omega$ on $\mathbb{R}^n$ subjected to certain boundary conditions can be derived through the minimization of the Dirichlet ...

3
votes

1
answer

240
views

### Is this constraint convex?

I have an optimization problem where the following constraint causes DCP Rule Error.
$$e^{x_n} \leq B \log _2\left(1+\frac{e^{\rho_n} g_n^2}{\sum_{i=1}^{n-1} e^{\...

0
votes

0
answers

92
views

### Primal optimal attained implies dual optimal attained

Given some optimization problem
$$\min_{x \in S \subset \mathbb{R}^n} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0, \quad 1\leq i\leq m$$
we can find the dual problem
$$\max_{\lambda\in\mathbb{R}^m} g(...

3
votes

1
answer

201
views

### Convex optimization without Slater's condition

In nearly all convex optimization methods that I read about, it is assumed that the problem satisfies Slater's condition, that is, there is a point that strictly satisfies all constraints (the ...

1
vote

1
answer

122
views

### On the additive property of the subdifferential of lower semicontinuous functions

Let $f:\mathbb R\to\mathbb R$ be a lower semicontinuous function, we define the Fréchet subdifferential of $f$ at $x\in\mathbb R$ by
$$\partial^F f(x):=\left\{L\in\mathbb R: \liminf_{v\to0}\frac{f(x+v)...

2
votes

0
answers

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

1
vote

1
answer

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

0
votes

0
answers

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

2
votes

0
answers

91
views

### Lower & upper bound on the maximal component given the system of power sums

Given a non-negative vector $x=(x_1,x_2,\dots,x_n)\in\mathbb{R_{>0}^n}$ and $m\in\mathbb{N}$, construct a system of power sum symmetric polynomials (or norms, if you like)
$$
\begin{cases}
x_1+x_2+\...

2
votes

1
answer

148
views

### Conic hull of a rectangle

I have a simple question that appeared in research: For a rectangle $S :=[a_1,b_1] \times[a_2,b_2] \times \dots \times [a_n,b_n] \subset \mathbb{R}^n$. Let $p_0 = (a_1,a_2,\dots,a_n)$, and define $p_i ...

1
vote

1
answer

90
views

### If $|P|<\infty$ and $C=P\cap\partial(\textrm{Conv}(P))$, then $P\subset\textrm{Conv}(C)$?

That is, if $P$ is a finite set, and $C$ is the set of points in $P$ which lie on the boundary of the convex hull of $P$, then is $P$ contained in the convex hull of $C$?
It seems true intuitively. In ...

1
vote

1
answer

61
views

### Boundedness of maximisers of parametric strictly concave functions

Let $L:[0,1]\times \mathbb R^m\times \mathbb R^n\to \mathbb R$ be defined by
$$L(\lambda, x,y):=\sum_{1\le i\le m}\alpha_i x_i + \sum_{1\le j\le n}\beta_j y_j -\sum_{1\le i\le m, 1\le j\le n} p_{i,j}\...

1
vote

0
answers

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

1
answer

126
views

### Bound the distance between two vectors on the probability simplex

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

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

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
\begin{equation}
x_k = x_{k-...

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

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.

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

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

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

0
votes

0
answers

60
views

### An integer optimization problem on the simplex

For $K \geq n$ and some $\sigma_i > 0$, I am looking for a solution to the following optimization problem:
\begin{equation}
\underset{\begin{smallmatrix} t_1, \cdots, t_n \in \mathbb{N}^{*} \\ \...

1
vote

1
answer

137
views

### Exponential optimization problem

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