Questions tagged [convex-optimization]
Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
839 questions
1
vote
2
answers
70
views
Monotonicity of kernel matrices with respect to hyperparameters
Let $\mathcal{X}$ be some nice space, let $\Phi$ be some ordered space, and let $K :\mathcal{X} \times \mathcal{X} \times \Phi \to \mathbf{R}$ be a positive-semidefinite kernel indexed by a ...
- 3,979
1
vote
0
answers
96
views
Dynamical formulation of the 2-Wasserstein distance for *discrete* matrix-valued measures
TL;DR: I want to find a definition generalizing "$t \mapsto \frac{1}{m} \sum_{k = 1}^{m} \delta_{x_k(t)}$ is a Wasserstein gradient flow" to matrix-valued probability measures.
Let $(X, d)$ ...
- 67
6
votes
2
answers
539
views
Optimal polynomial approximation of rational function $\frac{1}{1-x}$
I've been working on the following polynomial approximation problem. I want to find the optimal Chebyshev approximation of the rational function $\frac{1}{1-x}$ on the real interval $x\in[-\rho, \rho]$...
- 91.8k
2
votes
1
answer
101
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 + ...
CommunityBot
- 1
5
votes
3
answers
512
views
Optimisation under constraint of Wasserstein distance
Let $\mathcal P_n = \{P \in \mathbb R^n_{\geq 0}: P^T \mathbb I = 1 \}$, where $\mathbb I = (1,...,1)^T \in \mathbb R^n$ and $f: \mathcal P_n \to \mathbb R$ a convex and differentiable function (or ...
1
vote
1
answer
130
views
Analytic expression for the min value of $g(t):= \sqrt{(t-1)^2 + a^2}+ b|t|$ subject to $|t-1| \le c$
Disclaimer. Not sure this is MO-level but would really appreciate some help with this. Thanks in advance. Moved from SE.
Let $a,b,c \ge 0$, and define a function $g:\mathbb R \to \mathbb R$ by $g(t) :=...
- 128k
2
votes
1
answer
307
views
Gradient descent relaxation dynamics of a Euler-Lagrange equation
I want to minimize the functional
$$
F=\int{L(u)}dx,
$$
where $L= u_x^2-u^2$ is the Lagrangian function of the functional. Even if its Euler-Lagrange equation is easily found and solved, I want to try ...
- 6,367
1
vote
1
answer
169
views
Best projection on non-convex discrete set with two constraints
I want to compute the projection of a vector $\left( x\right) _{1\leq
i,j\leq n}\in \lbrack 0,1]^{n\times n}$ on the following discrete set
$$
S=\left\{ x\in \{0,1\}^{n\times n}:x_{i,j}+x_{j,i}\leq 1;\...
- 128k
1
vote
0
answers
212
views
Question related to Kahn-Kalai conjecture
I am interested whether the statement of Kahn-Kalai conjecture (proved by Jinyoung Park and Huy Tuan Pham in '22) can be strengthened to the question about Boolean functions $f : 2^{[1, n]}\to \{0, 1\}...
- 11
0
votes
1
answer
147
views
Is there a redundant constraint in linear programming? [closed]
From wikipedia:
But... Why do we need the $x\ge 0$ part? We can instead do $-x\le 0$, and thus saving a line in the definition (which is not a big deal but nevertheless nice).
(In order to do that, ...
- 63.9k
4
votes
0
answers
622
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 ...
- 599
5
votes
1
answer
278
views
For $f$ geodesically convex with $L$-Lipschitz-gradient on hyperbolic space, is $f(x)-f(x^*)\leq(\mathrm{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-...
- 45k
4
votes
2
answers
280
views
Can one always find sparse solutions to an $\ell^1$-minimization problem?
Consider $A\in\mathbb{R}^{m \times N}$ and $b \in \mathbb{R}^m$, with $m<N$. Is it true that the optimization problem
$$\min \|x\|_1 \quad \text{s.t.} \quad A x = b,$$
admits an $m$-sparse solution ...
0
votes
1
answer
80
views
Probability of accurate sparse recovery
Suppose $\mathbf{A}_{k\times n}$ ($k<n$) is a matrix whose entries are generated i.i.d. from Gaussian distribution and $\mathbf{s}_{n\times 1}$ is a sparse vector with $m$ sparsity (i.e., $\|\...
- 1,724
1
vote
1
answer
94
views
Differentiability of some function defined as the maximum
Let $d,n\ge 1$ be fixed integers. Given some compact subset $E\subset \mathbb R^d$, consider the function $f: E^n\ni (x_1,\ldots, x_n) \longrightarrow f(x_1,\ldots, x_n)\in \mathbb R$ defined by
$$f(...
- 128k
1
vote
0
answers
28
views
Finding variance-minimizing weights [closed]
I'm trying to solve the following matrix calculus problem:
$\text{argmin}_{v \in R_+^K}(v'\Sigma v) \hspace{0.5pc} \text{subject to} \hspace{0.5pc} 1'v=1$
where $\Sigma$ is a well-behaved (symmetric, ...
- 11
2
votes
0
answers
225
views
Minimisation and maximisation of the modulus of a complex valued function
I am new to complex analysis and I would be grateful to be guided in the following problem. We know that if $f$ is a function from $\Bbb C \to \Bbb R$, then $|f|$ is a function from from $\Bbb R^2 \to\...
- 6,367
0
votes
1
answer
88
views
Is the mapping $F(a):= \arg\min_{x \in \mathbb R^n} \|x-a\|_2 + \|x\|_1$ non-expansive?
Fix $a \in \mathbb R^n$ and let $\|\cdot\|$ be any norm on $\mathbb R$ (e.g $\ell_1$ norm). For any $a \in \mathbb R^n$, it is clear that the function $f_a(x) := \|x-a\|_2 + \|x\|$ is strictly convex ...
- 12.7k
0
votes
2
answers
532
views
Convex integer program with totally unimodular constraints
Suppose I have a convex (nonlinear) integer program with totally unimodular linear constraints. What are sufficient conditions one can impose on the convex objective function such that relaxing the ...
2
votes
1
answer
119
views
Analytic value of $\alpha := \sup_{(x,y) \in C} ax+by$, where $C := \{(x,y) \in \mathbb R^2 \mid x^2 + y^2 \le 1,\,x^2 + c y^2 \le R^2\}$
Let $a,b \in \mathbb R$, $R \ge 0$, and $c > 0$. Define $C := \{(x,y) \in \mathbb R^2 \mid x^2 + y^2 \le 1,\,x^2 + c y^2 \le R^2\}$, and set
$$
\alpha := \sup_{(x,y) \in C} ax + b y.
$$
Question. ...
- 5,429
1
vote
0
answers
97
views
How to solve the following optimization problem?
Let $G=(V,E)$ be a connected network with $|V|=n$. Consider the following optimization problem
I'm trying to know under which conditions the following minimization problem has solution :
$${\sum _{i=1}...
- 47
0
votes
1
answer
67
views
Analytic formula for minimizer of $f(x) := \sqrt{(x-a)^\top S(x-a)}+ r \|x\|_2$
Let $S$ be a positive-definite $n \times n$ matrix and define $\|z\|_S := \sqrt{x^\top S x}$ for any $x \in \mathbb R^n$. Let $a$ be a fixed vector in $\mathbb R^n$ and $r \ge 0$, and consider the ...
- 23.7k
2
votes
0
answers
64
views
Question about (stochastic parallel-gradient descent) SPGD and (simultaneous perturbation stochastic approximation) SPSA [closed]
I wonder if someone could shed some light on this. I'm curious if stochastic parallel-gradient descent and simultaneous perturbation stochastic approximation refer to the same optimization techniques.
- 12.9k
1
vote
0
answers
598
views
Subgradient of a matrix's nuclear norm
I was going through the derivation of subgradient of the nuclear norm of a matrix from an old homework of a Convex Optimization course (CMU Convex Optimization Homework 2 - Problem 2).
Question Image
...
- 11
0
votes
0
answers
63
views
Direct (first-order ?) algorithm to minimize $u(x) := \|x-a\|_C + r\|x\|_p$
Fix $a \in \mathbb R^n$, $r \ge 0$, $p \in \{1,2\}$, and a positive-definite matrix $C$ of order $n$. Define $u:\mathbb R^n \to \mathbb R$ by $u(x) := \|x-a\|_C + r\|x\|_p$, where $\|z\|_C := \sqrt{z^\...
- 6,853
2
votes
0
answers
299
views
Practical application of envelope theorem for linear programs
Assume that we have solved a (standard) linear program
$$
\text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0,
$$
and would like to know how sensitive is the optimal ...
- 1
2
votes
0
answers
73
views
Calculating the minimum distance between points using p norm
I’m trying to gain some insight about a problem I’ve been thinking about recently. I have managed to bring it about to the following form:
Find $\min\limits_{x} \sum\limits_{i=1}^{n} |x-x_{i}|^p$, ...
- 121
2
votes
1
answer
121
views
Can we use the solution to two optimisation problems to solve a third, bigger, one?
Background
Say we have an optimization problem $$\min_x f(x) = g(x) + h(x)$$
where $g$ is differentiable and convex, and $h$ are convex but not necessarily differentiable. If $g$ is the mean squared ...
- 840
1
vote
0
answers
41
views
Fitting a non-periodic sum of periodic time series
The problems is as follows: you have $n$ points $(x_1,y_1),\dots,(x_n,y_n)$ and you want to fit the following equation to the data points:
$$y=\theta_1\cos(\theta_2 x+\theta_3) + \theta_4\cos(\theta_5 ...
- 3,098
0
votes
0
answers
75
views
Maximize entropy under Kulback-Leibler divergence
I posed this question in math.stackexchange.com, but have not received any answer. I would like to try my luck here.
In this question, it is to solve
\begin{align}
\max_p &-\int dy\,p(y)\ln p(y) \\...
- 2,239
0
votes
0
answers
166
views
Literature request: proving or disproving convexity of the optimal value function of semidefinite program (SDP) or convex optimization in general
Suppose I have a function $f:\mathbb{R}\rightarrow \mathbb{R}$ defined as the following parametric optimization problem:
$$f(p) = \inf_xf_0(x) \quad \text{subject to } \quad G(x,p)\leq 0,$$
where ...
1
vote
0
answers
203
views
Matrix relative condition number
I've been working on some distributed optimization problems and faced a bit of a challenge with the following question.
Given $A_1, A_2, .., A_m \in M_n({\mathbb{R})} $ symmetric positive definite ...
- 11
0
votes
2
answers
630
views
Smooth approximation for non differentiable function
Let $f(t) = \min(\frac{1}{\lvert t\rvert}, 1)$. I would like to find a smooth approximating function $g$ such that $f(t) \leq g(t)$ for all real $t$. Is there a nice function $g$ out there? Any ...
- 13.2k
0
votes
0
answers
156
views
Optimal solution of complex optimization problem
Let $Q(x)=a(x)e^{jb(x)}$ be a complex function of $x$. We want to approximate this function with $R(x)=\alpha e^{jx\beta}$ such that
\begin{align}
\text{arg}\min_{\alpha,\beta} \int_{-\frac{A}{2}}^{\...
CommunityBot
- 1
2
votes
2
answers
291
views
Optimizing a multilinear function over the vertices of the cube
Suppose I have $n$ Boolean variables $x_1,\dots,x_n$, and an objective function of the form $f(x_1,\dots,x_n) = \sum_{a_1,\dots,a_n}c_{a_1,\dots,a_n} x_1^{a_1} \cdots x_n^{a_n}$ with $(a_1,\dots,a_n) \...
- 47.3k
1
vote
1
answer
50
views
Point of tangency is an optimal point for a monotone, quasi-concave function
Given $U : \mathbb{R^2} \to \mathbb{R}$ is monotone and quasi-concave, consider the following problem :
$$\max_{(x,y) \ \in \ \mathbb{R}^2}[U(x,y)] \text{ subject to } p_1 x + p_2 y \leq M ; \ (p_1, ...
0
votes
0
answers
44
views
Max and concavity
Let $x,y$ be two probability vectors belonging to the simplex of size $n$ (denote by $\Delta_n$) and $f(x,y) = x^{\top}Ay - \epsilon||x||_2^2-\epsilon ||y||_2^2$ with $\epsilon>0.$ Is it true that $...
0
votes
0
answers
580
views
Convex maximization over the boundary of a convex set
Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be the objective function that is strictly convex. We would to like maximize $f$ over a convex compact set $S \subseteq \mathbb{R}^n$. Assume that $f$ has ...
- 261
4
votes
1
answer
194
views
How to solve this minimax matrix optimization problem?
Recently, I want to know how well can a $\ell_1$ ball be approximated by the image of a $\ell_2$ ball under a linear transform. I formulate this problem as the following optimization problem.
\begin{...
- 4,219
5
votes
1
answer
355
views
Are the polyhedral cones the only examples of cones that remains closed when they are added to vector subspaces?
Let $C \subset \mathbb{R}^{n}$ be a closed convex cone. If one wants to know whether the linear map $T:\mathbb{R}^{n} \to\mathbb{R}^m$ sends the closed set $C$ to another closed one, $T(C)$, it is ...
- 225
3
votes
0
answers
125
views
Does Barvinok's algorithm apply to convex integer program?
Barvinok provided a counting algorithm to count number of integer solutions to integer linear program that runs in polynomial time if the number of integer variables is fixed.
If we have convex ...
CommunityBot
- 1
2
votes
1
answer
509
views
Under what condition does Courant–Fischer–Weyl min-max principle hold in general?
From Wikipedia:
Let $A$ be an $n \times n$ Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient $R_A :
\mathbf C^n \setminus \{0\} \to \...
- 12.9k
0
votes
1
answer
83
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{...
- 128k
2
votes
0
answers
44
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)...
- 6,853
1
vote
2
answers
270
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 ...
- 241
2
votes
0
answers
79
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 ...
- 6,853
1
vote
1
answer
264
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 =...
- 43
1
vote
1
answer
144
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 ...
- 63.9k
1
vote
0
answers
29
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 ...
- 213
5
votes
0
answers
259
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\\ ...
- 51