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

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

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

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

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

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

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

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^*)$ ...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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) :=...

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

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

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

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

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

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

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

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

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

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):=\...

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

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

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

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

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

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

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

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

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

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

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