Questions tagged [convex-optimization]
Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
756
questions
1
vote
1
answer
76
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 ...
- 277
1
vote
1
answer
43
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
-3
votes
0
answers
47
views
problem：Conditions for including cones [duplicate]
I have considered a very interesting question myself, and I think it is very difficult to answer it.
Consider N n-dimensional vectors, where the angle between any two vectors is acute and their ...
- 55
2
votes
1
answer
97
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,...
- 133
2
votes
1
answer
90
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,\...
- 391
0
votes
0
answers
25
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
77
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
115
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^*)$ ...
- 309
0
votes
0
answers
28
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
46
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
101
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
80
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
68
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
1
vote
0
answers
29
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
62
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 \...
- 115
0
votes
0
answers
38
views
Minimizing a certain trace-product involving orthonormal vectors
Let $C$ be an $n \times n$ positive-semidefinite matrix. Fix and integer $1 \le m \le n$, and for orthonormal vectors $v_1,\ldots,v_m$ in $\mathbb R^n$, and set $V := (v_1,\ldots,v_m) \in \mathbb R^{m ...
- 6,338
0
votes
0
answers
77
views
Decomposing convex functions as (simple, useful, convex) + (convex)
Let $f$ be a nice convex function, let $X = \{ x_i : i \in [N] \}$ be a collection of points in the domain of $f$, and define the 'bundle approximation'
$$
f(x; X) = \max \{ f(x_i) + \langle \nabla f (...
- 551
3
votes
1
answer
64
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
0
votes
1
answer
40
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
0
votes
0
answers
35
views
Solving constrained convex minimization problems by reduction to a scalar equation
Let $f,g:\mathbb R^d \to \mathbb R$ be functions such that
$g$ is convex and there exists $x_0 \in \mathbb R^n$ such that $f(x_0) \le 0$.
$f$ is strictly convex.
Consider the problem
$$
\tag{*}
\...
- 6,338
1
vote
0
answers
75
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
2
votes
0
answers
51
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,338
6
votes
0
answers
96
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 ...
- 371
1
vote
2
answers
49
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 ...
- 551
1
vote
0
answers
44
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)$ ...
- 75
0
votes
0
answers
83
views
How to find a specific clique cover set?
Let $G(\mathcal{V},\mathcal{E})$ be a graph with vertex set $\mathcal{V}$ and edge set $\mathcal{E}$. Also, non-negative weights $w_i$ are assigned to each vertex $i\in\{1,\ldots,n\}$. Suppose the ...
- 129
6
votes
2
answers
375
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
122
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,338
3
votes
0
answers
71
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), \...
- 551
2
votes
1
answer
119
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
68
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
170
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
1
vote
1
answer
123
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}^...
- 133
0
votes
1
answer
95
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, ...
0
votes
0
answers
42
views
On the convex inequality $x^2\leq u$
Suppose $x$ is in $[0,M]$ where $M^2$ is known and treated as constant in a convex program.
Consider the convex inequality $x^2\leq u$. The reverse inequality $u\leq x^2$ is non-convex. On the other ...
- 13.2k
1
vote
1
answer
118
views
Optimal transport: the existence of an optimal pair of $c$-conjugate functions
$\newcommand{\diff}{ \, \mathrm d}$
Let
$X,Y$ be Polish spaces,
$\mathcal C_b(X)$ the space of all real-valued bounded continuous functions on $X$,
$\mathcal P(X)$ the space of Borel probability ...
- 713
1
vote
0
answers
47
views
Comparison of solutions of Hamilton-Jacobi equations with different initial conditions
Consider a Hamilton-Jacobi equation:
$$u_{t} + f(u_{x}) = 0 \quad (x,t) \in \mathbb{R}\times [0,+\infty)$$
with two possible initial conditions $u(x,0) = g_{i}(x)$ for $x \in \mathbb{R}$ and $i=1,2$. ...
- 2,961
1
vote
0
answers
55
views
John and Lowner ellipsoid
I am looking at a proof to show that Lowner ellipsoids are unique for centrally symmetric convex body $K$. I want to show basically that $$Low(K)=John(K^{\circ})^{\circ},$$ where the $\circ$ means ...
- 11
3
votes
3
answers
201
views
Eigenvectors that are tensor products?
Consider a fixed $N\times N$ positive definite symmetric matrix $A$.
Assume $N=d^r$ for some $d,r\geq 1$.
I wonder if one can find a closed formula for the maximizer/maximum of the function $$f(x):=\...
- 2,045
7
votes
0
answers
323
views
Are there any characterizations of $C^2$ convex functions?
There are several characterizations of convex functions with the Lipschitz continuous gradient. If we already know that the function is of class $C^1$, then we have the following equivalent conditions:...
- 24.5k
0
votes
1
answer
60
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., $\|\...
- 129
0
votes
0
answers
20
views
Inverting laplacian for leverage scores $w_{s,t}({\bf e}_s-{\bf e}_t)^TL^{+}({\bf e}_s-{\bf e}_t)$
Given a graph $G(V,E)$ with edge weights $w_e>0$ and edge-vertex incidence matrix $U$, consider the laplacian $L=U^TWU$, and its Moore-Penrose psuedoinverse $L^{+}$. Here, $W$ is a diagonal matrix ...
- 452
1
vote
1
answer
64
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(...
- 437
0
votes
0
answers
59
views
A little question about the derivation of the generalized alternating projection (GAP) algorithm
This question is actually just a question about Euclidean projection.
I've been studying some articles on the generalized alternate projection (GAP) algorithm recently, but have a little question ...
- 131
0
votes
1
answer
57
views
Strict inclusion for recession cone of closure of a convex set
Let $C$ be a nonempty closed convex subset of $\mathbb{R}^n$. The recession cone of $C$ is given by
$$R_C=\left\lbrace d\in\mathbb{R}^n:x+td\in C, \forall t>0, \forall x\in C\right\rbrace.$$
It is ...
- 29
1
vote
0
answers
25
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
0
votes
0
answers
32
views
Linear transformation of intersection of SDP cone and polyhedral cone
Let $A$ be a linear transformation, let $\mathcal{S}^n_+$ be the cone of positive semidefinite matrices. Suppose $P$ is a polyhedral cone. We consider the image of the intersection of the two cones, i....
- 263
2
votes
0
answers
91
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\...
- 690
0
votes
1
answer
60
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 ...
- 6,338
2
votes
1
answer
106
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. ...
- 6,338