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
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 ...
Television's user avatar
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 ...
bernard's user avatar
  • 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 ...
dzk's user avatar
  • 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,...
aest's user avatar
  • 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,\...
Medo's user avatar
  • 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|^...
nir's user avatar
  • 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 ...
Justin's user avatar
  • 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^*)$ ...
Jean Legall's user avatar
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 ...
Itimethy's user avatar
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 ...
Naruto's user avatar
  • 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$. ...
user3750444's user avatar
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, ...
oyy's user avatar
  • 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 $$ ...
ximeng fan's user avatar
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 ...
pyridoxal_trigeminus's user avatar
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 \...
Meowdog's user avatar
  • 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 ...
dohmatob's user avatar
  • 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 (...
πr8's user avatar
  • 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 ...
gcy's user avatar
  • 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 ...
seulberg1's user avatar
  • 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{*} \...
dohmatob's user avatar
  • 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 ...
koch's user avatar
  • 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 $...
dohmatob's user avatar
  • 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 ...
user135520's user avatar
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 ...
πr8's user avatar
  • 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)$ ...
ViktorStein's user avatar
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 ...
Math_Y's user avatar
  • 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]$...
Jiayun Li's user avatar
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) :=...
dohmatob's user avatar
  • 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), \...
πr8's user avatar
  • 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 ...
feynman's user avatar
  • 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;\...
Goga's user avatar
  • 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\}...
Drrd's user avatar
  • 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}^...
aest's user avatar
  • 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, ...
Bipolo TheGod's user avatar
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 ...
Turbo's user avatar
  • 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 ...
Akira's user avatar
  • 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$. ...
IamWill's user avatar
  • 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 ...
pasqc's user avatar
  • 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):=\...
Adrien Hardy's user avatar
  • 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:...
Piotr Hajlasz's user avatar
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., $\|\...
Math_Y's user avatar
  • 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 ...
AspiringMat's user avatar
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(...
Fawen90's user avatar
  • 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 ...
anyon's user avatar
  • 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 ...
Chivul's user avatar
  • 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, ...
Kyle Shapiro's user avatar
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....
Pew's user avatar
  • 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\...
AgnostMystic's user avatar
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 ...
dohmatob's user avatar
  • 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. ...
dohmatob's user avatar
  • 6,338

1
2 3 4 5
16