All Questions
1,233 questions
2
votes
1
answer
151
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\...
- 307
0
votes
0
answers
201
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
2
votes
1
answer
240
views
Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard.
However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
- 123
0
votes
0
answers
55
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
0
votes
0
answers
85
views
Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points
Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$
\begin{align}
\max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
- 671
1
vote
1
answer
69
views
$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance
Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
- 111
1
vote
1
answer
209
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
1
vote
1
answer
119
views
Optimization on non-convex set
Let $\Omega$ be an open bounded subset of $\mathbb{R}^2$ and $f\in L^2(\Omega)$ be a given function. Consider the optimization problem
$$\mathrm{min} \int_\Omega u(x) f(x) \,dx\,,$$
where a minimum is ...
- 11
2
votes
1
answer
183
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,...
- 21
0
votes
2
answers
197
views
Convergence of the infima of convex functions on $\mathbb{R}^m$
Any thoughts on proving the following statement, which is a generalization of the result in convergence of the infima of convex functions from domain $\mathbb{R}$ to $\mathbb{R}^m$ and also Theorem 1 ...
1
vote
1
answer
55
views
From relative convexity to modulus of continuity estimates for the dual gradient mapping
Let $F: \mathbf{R}^d \to \mathbf{R}$ be a convex function, let $m > 0$, and define $Q_m: \mathbf{R}^d \to \mathbf{R}$ to be the mapping $x \mapsto \frac{m}{2} \| x \|_2^2$. One says that $F$ is $m$-...
- 801
2
votes
1
answer
181
views
Matrix function as gradient
Let $S_n^{++}(\mathbb{R})$ be the space of $n \times n$ symmetric positive definite matrices. For $M \in S_n^{++}(\mathbb{R})$ consider the function $f: X \in S_n^{++}(\mathbb{R}) \mapsto M X^{-1} M$.
...
- 407
0
votes
2
answers
530
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
- 21
0
votes
2
answers
319
views
Representation of continuous, monotone, concave functions
Is there a characterization of all continuous functions $f:\mathbb{R}\rightarrow \mathbb{R}$ satisfying:
$f(0)=0$
$f$ is monotonically increasing
$f$ is concave
My intuition is that $f$ should admit ...
- 5,405
2
votes
1
answer
106
views
Submodularity of a particular function derived from a convex function?
Consider a convex function $f : \mathbb{R}^d \to \mathbb{R}$. Define now the set-input function $g_f : 2^{[d]} \to \mathbb{R}$ as follows,
\begin{align}
g_f(S) = \min \left\{ f(x) : x \in \mathbb{R}^d ...
- 297
1
vote
1
answer
69
views
Characterization of the behavior of the residuals in conjugate gradient
In conjugate gradient method for solving symmetric positive definite linear system $Ax=b$, which can also be regarded as a convex optimization problem $\dfrac{1}{2} x'Ax - x'b$, the $A$-norm of the ...
- 205
2
votes
1
answer
594
views
Tangent cone of a closed convex cone
Let $K \subset \mathbb{R}^n$ be a closed convex set. Given a point $u \in K$, the tangent cone of $K$ at $u$ is defined as (or characterized by)
$$
T_K(u) := \mathrm{cl}(\left\{ t (v - u) \mid v \in K,...
- 163
2
votes
1
answer
106
views
Is $f^{-a}$ locally integrable if $f\geq 0$ has a unique stationary point ( a minimum) at which the Hessian is positive definite, $0<a<d/2$
Let $0<a<d/2$, let $B$ be the unit ball in $\mathbb{R}^{d}$ centered at the origin, and let $f:B \to [0,\infty[$ be a a smooth function such that
(1) $f(x)\geq f(0).$
(2) $\nabla f(x)\neq 0,\...
- 852
0
votes
0
answers
57
views
optimization of mixed linear and infinity norm
I have the following optimization problem:
Given a complex sequence $H_i$, $1 \leq i\leq N$. Find a complex sequence $G_i$ that minimizes:
$$ \lambda\cdot\max_i { |H_i\cdot G_i - 1|^2 } + \sum_i |G_i|^...
- 101
0
votes
0
answers
176
views
Given optimality of L1 norm, prove that absolute value of sum of a vector with proper sign is less than 1?
Problem:
Given a domain $\mathcal{D}\subset\mathbb{R}^{l}$, we can find $l$
points $\boldsymbol{v}_{i}\in\mathcal{D}$, $i=1,\cdots,l$. Each
point is a column vector with dimension $l\times1$. They ...
- 1
4
votes
2
answers
353
views
An upper bound of gradient norm for convex functions near minimizer
Let $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a convex function. Denote $X^*$ as the set of minimizers of $f$ and assume $X^*$ is unbounded. Is it possible that $\|g_x\|$ is unbounded when $d(x,X^*)$ ...
- 311
0
votes
0
answers
60
views
Trying to transform a minimization problem to a saddle point problem for the primal–dual algorithm
I’m reading about a problem, and the author goes from a classical minimization problem to a saddle point problem in order to perform a primal–dual algorithm on it [1].
However, It’s my first problem ...
- 1
1
vote
1
answer
66
views
Estimate of minimum of the Poisson integrals corresponding to a convergent Hausdorff sequence of smooth bounded domains from below
Let $\{\Omega_{j}\}_{j\in\mathbb{N}}$ be a sequence of smooth bounded domains in $\mathbb{C}^{n}$ such that $\Omega_{j}$ converges to a smooth bounded domain $\Omega$ in the sense that the defining ...
- 63
1
vote
2
answers
121
views
How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?
I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...
- 175
1
vote
2
answers
125
views
Establishing quasiconcavity
Let $f:\mathbb{R}_+\rightarrow\mathbb{R}_+$ be twice differentiable quasi-concave function satisfying $f(x)>0,\forall x \in \mathbb{R}_+$. Let $g:\mathbb{R}_+\rightarrow\mathbb{R}_+$ be a positive, ...
- 67
2
votes
0
answers
178
views
Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?
Crossposted at Computational Science SE
Consider a quadratic programming problem with the following format:
$$
\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\
$$
$$
\text{s.t.} Ax\leq b, \\
x\geq 0
$$
...
- 21
3
votes
0
answers
105
views
Techniques for solving linear inequalities
For $n$ real variables $x_1, \ldots, x_n$, I have a bunch of inequalities of form $2 x_i > x_j + x_k$ or $2 x_i < x_j + x_k$, where $i,j,k$ are distinct. My goal is to determine whether this set ...
- 231
1
vote
0
answers
61
views
Fitting a convex polytope with 𝑛 facets between two nested spheres
This is related to a research problem that is interested in approximation of spheres by convex polytopes.
Let $C_r$ and $C_R$ be two spheres in $\mathbb R^d$ of radius $r$ and $R$, respectively, where ...
0
votes
1
answer
103
views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
3
votes
1
answer
188
views
Sensitivity of the solution of QP with respect to parameters
Given a quadratic program,
$$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$
Suppose $A \succ 0$, so the program strongly ...
- 33
1
vote
0
answers
36
views
Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?
Suppose that $P$ is a polyhedron represented by
$$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$
and $P$ contains interior points. Moreover, the ...
- 33
0
votes
1
answer
44
views
Identify maxima for 2-Dimensional Function without knowing cross-derivative
I am trying to proof the uniqueness of a maximum for a two-dimensional function (well behaved, twice differentiable, domain $R^2$, etc.), yet cannot compute the exact derivatives or the Hessian.
I ...
- 103
1
vote
0
answers
83
views
Convex optimization with one-point feedback
In an adversarial bandit setting, we want to minimize $\sum_{1}^{T}l_t$(not exactly this but the corresponding regret), where $l_t$ is the loss function in the $t-$th round. Each round we can specify ...
- 21
0
votes
0
answers
145
views
Bound on solutions of $Ax \ge b$
Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$.
One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...
- 439
2
votes
0
answers
56
views
Whether $d_x(t) := \|P_t(x)-x\|_H$ is increasing in $t$ where $P_t:H \to H$ is the proximal operator of a convex function
Let $H$ be a Hilbert space (e.g Euclidean $\mathbb R^n$), and fix a proper convex function $f:H \to (-\infty,+\infty]$. Given any $t \ge 0$, let $P_t:H \to H$ be the proximal operator of $f$ at level $...
- 6,853
0
votes
0
answers
84
views
1-degree SOS proof refutes Linear Programming
I am trying to understand Sums-of-Squares proof systems.
A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as
$\sum_{i=1}^m g_i(...
1
vote
1
answer
119
views
Adding linear constraint to the domain
I don't know if it is a well-known problem, but I have been struggling to come up with an algorithm.
I have a set of linear constraints $Ax\le b$, $b\ge 0$ ($b$ and $A$ are given, $x$ is a variable). ...
6
votes
0
answers
136
views
Minimizing $\det(D)$ for all diagonal matrices $D$ that satisfy $D+B \succeq 0$
Let $A$ be an $n \times n$ real matrix and let $B$ be the block bipartite matrix
$$B = \begin{bmatrix} 0&A \\
A^{T}&0 \end{bmatrix}$$
I came across the following optimization problem, which ...
- 401
1
vote
0
answers
96
views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
1
vote
2
answers
69
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 ...
- 801
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
1
vote
0
answers
335
views
Closed-form solution of a particular linear program
(Note: I asked a similar question at math.stackexchange but the present one is more precise.)
I have a linear program of the form:
$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$
$...
- 988
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]$...
- 63
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) :=...
- 6,853
3
votes
0
answers
109
views
Convex minorants to convex functions, given partial Taylor expansion and smoothness estimate
Let $V$ denote a strictly convex function (in arbitrary dimension) whose Hessian is $L$-Lipschitz. Given only this knowledge, and the values of $\left\{ V \left( x \right), \nabla V \left( x \right), \...
- 801
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 ...
- 159
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;\...
- 47
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
2
votes
1
answer
61
views
Counting the number of pair of d-uplets with upper bounded distance
Consider two d-uplets $u = (u_1,...,u_d)$ and $v = (v_1, ..., v_d)$ both living in $\mathbb{N}^d$ with $d$ a positive integer. They both verify $$(*) \sum_{i=1}^d u_i = \sum_{i=1}^d v_i = k$$ with $k$ ...
- 55
1
vote
1
answer
1k
views
Is a Lipschitz continuous gradient equivalent to this condition?
I know if a function $f: \mathbb{R}^n \to \mathbb{R}$ is $L$-smooth, i.e. its gradient $\nabla f$ is $L$-Lipschitz continuous, then it satisfies the following inequality for any $x, x_0 \in \mathbb{R}^...
- 163