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
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 ...
HarrisFatehein's user avatar
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 ...
Tuong Nguyen Minh's user avatar
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 $\...
fsp-b's user avatar
  • 451
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 ...
Red Bordeaux's user avatar
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 $\...
Benjamin Tennyson's user avatar
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 ...
zhamao dra's user avatar
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 ...
MMH's user avatar
  • 139
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 \...
Marco Max Fiandri's user avatar
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 \...
raian's user avatar
  • 1
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 ...
xingye zhan's user avatar
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$ ...
De vinci's user avatar
  • 329
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$ ...
Azmy Rajab's user avatar
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 ...
Prakirt Raj's user avatar
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 ...
CWC's user avatar
  • 389
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 ...
AChem's user avatar
  • 803
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: $\...
Marco Max Fiandri's user avatar
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 \...
Brendan Mallery's user avatar
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 $$\...
wsz_fantasy's user avatar
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 ...
Aaron Bergman's user avatar
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 ...
Surpass2019's user avatar
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}$ (...
Diego Fonseca's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 ...
Titouan Vayer's user avatar
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 ...
user8469759's user avatar
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^{\...
Mojtaba's user avatar
  • 31
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(...
wsz_fantasy's user avatar
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 ...
Erel Segal-Halevi's user avatar
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)...
Fergns Qian's user avatar
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$ ...
Thomas's user avatar
  • 511
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 ...
SequenceGuy's user avatar
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. ...
Pipnap's user avatar
  • 129
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+\...
Polylemma's user avatar
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 ...
wsz_fantasy's user avatar
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 ...
one-day-at-a-time's user avatar
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}\...
Fawen90's user avatar
  • 975
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 ...
Neill Clift's user avatar
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} \...
good bandit's user avatar
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 ...
Hao Yu's user avatar
  • 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 \begin{equation} x_k = x_{k-...
Hao Yu's user avatar
  • 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 ...
Sanae Kochiya's user avatar
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 ...
Jeff 's user avatar
  • 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.
zak.Ryd's user avatar
  • 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 ...
Honglian's user avatar
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\...
Sanae Kochiya's user avatar
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 ...
T. W.'s user avatar
  • 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]}$ ...
Ben Carter Jr.'s user avatar
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}^...
lzzz's user avatar
  • 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 ...
user_lambda's user avatar
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}^{*} \\ \...
Titouan Vayer's user avatar
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,...
Ham's user avatar
  • 11

1
2 3 4 5
16