Questions tagged [convex-optimization]

Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes

334 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
898 views

Existence of barycenter

Let $(X,d)$ be a metric space. A barycenter of a Borel probability measure $\mu$ on $X$ is a minimizer of the function \begin{equation} \begin{split} f \colon X & \to \mathbb{R}\\ x &\mapsto \...
seub's user avatar
  • 1,337
8 votes
0 answers
192 views

Concavity of product and ratio of sums

Apologies if this question is not appropriate for MathOverflow. I have asked at Math.StackExchange without success. Consider the function $f:\mathbb{R}^n\rightarrow \mathbb{R}$ defined as $$ f(x)=\...
user_lambda's user avatar
8 votes
0 answers
247 views

Quantum coupon collection: positivity of an alternating sum of matrices

It is well-known that in the classic coupon collecting problem (CCP), the expected waiting time is \begin{equation*} T_n(x_1,\ldots,x_n) = \sum_{k=1}^n (-1)^{k+1}\sum_{1\le i_1 < \cdots < i_k \...
Suvrit's user avatar
  • 28.4k
7 votes
0 answers
400 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
7 votes
0 answers
1k views

Closed-form solution of a linear programming question

Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & \...
Jerry Jiannan Lu's user avatar
7 votes
0 answers
215 views

Characterizing matrices with rank constraint

Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times ...
Turbo's user avatar
  • 13.7k
7 votes
0 answers
208 views

Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi, my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$. The matrix $C$ is huge ($n$ up to a ...
Manuel Schmidt's user avatar
6 votes
0 answers
116 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
6 votes
0 answers
251 views

Concavity of a function implicitly defined by a polynomial

Consider the following system of $n$ equations: \begin{equation}f_j^2 = x_j^2\sum_{i=1}^n A_{ij} f_i \tag{$\star$} \end{equation} where $A_{ij}\geq 0$ are known constants and where $x_j>0$ for ...
user_lambda's user avatar
6 votes
0 answers
92 views

Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...
Robert Lowell's user avatar
5 votes
0 answers
78 views

Differentiability/continuity of stabilizing solution to algebraic Riccati equation with respect to matrix parameters

When solving the LQR problem to find the optimal feedback matrix $K^*$, i.e. solving \begin{align*} \min_K &\int_0^\infty \left(x^TQx + u^TRu\right)dt,\\ \text{s.t. }&\dot{x} = Ax+Bu,\\ &u=...
VGD's user avatar
  • 151
5 votes
0 answers
251 views

Generalized convexity

Let $X$ be a vector space. The positive-homogeneous function $\|\cdot\|$ is said to be a quasinorm if $\|x+y\|\le K(\|x\|+\|y\|)$, for some $K\ge1$; it is a norm if $K=1$. Question: 1. (terminology) ...
Aryeh Kontorovich's user avatar
5 votes
0 answers
133 views

Conv A = Dual B

I have two cones $A$ and $B$ in a Euclidean space. I want to show that $\mathrm{Conv}\,A=\mathrm{Dual}\,B$; that is, $a\in\mathrm{Conv}\,A$ if and only if $\langle a,b\rangle\ge 0$ for any $b\in B$. ...
Anton Petrunin's user avatar
5 votes
0 answers
121 views

Projection of a function $f\in L^1(\Omega)$ onto a finite dimensional subspace

Suppose $\Omega \subset \Bbb R^n$ be a domain such that $|\Omega|<\infty$, $f\in L^1(\Omega)$. Let $Y= \text{span}\{g_1,\dots, g_k\}$. Is there a characterization of the set of projections of $f$...
BigbearZzz's user avatar
  • 1,245
5 votes
0 answers
263 views

Fenchel conjugate on a Hadamard manifold

Let $M$ be a Hadamard manifold and let $F:M\to\mathbb{R}$ be a real-valued convex function on $M$. What would be the Fenchel-Young conjugate of $F$? In general for a real locally convex vector space $...
Arian's user avatar
  • 364
5 votes
0 answers
150 views

Dimensions of faces of convex hull of convex bodies

Let $K_1,\ldots,K_m\subset\mathbb{R}^n$ with $m\geq n$ some convex bodies (i.e. compact with nonempty interior). I am interested in sufficient criteria for the convex hull $K=\textrm{conv}(K_1,\ldots,...
Hans's user avatar
  • 2,863
5 votes
0 answers
96 views

Non-convex optimization problem involving minimum spanning trees

Suppose I am given $n$ points $p_1,\dots,p_n\in \mathbb{R}^2$, as well as two positive coefficients $a_1$ and $a_2$, and I am trying to select $n$ points $x_1,\dots,x_n$ to solve the following ...
Tom Solberg's user avatar
  • 3,929
5 votes
0 answers
167 views

A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...
user109711's user avatar
5 votes
0 answers
1k views

Coordinate mirror descent

Let $f$ be a jointly convex function of 2 variables say $x,y$. I am interested in solving the optimization problem $$\min_{x,y\in\Delta} f(x,y)$$ where $\Delta$ is a $d$ dimensional simplex. An ...
gmravi2003's user avatar
4 votes
0 answers
210 views

Economic equilibrium and tropical geometry

There is a famous saying in economics: When everyone pursues his or her own interests, there is an invisible hand that brings the market to equilibrium. However, this is not always the case. Here is ...
Surpass2019's user avatar
4 votes
0 answers
551 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 ...
dodo's user avatar
  • 589
4 votes
0 answers
205 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\\ ...
Abumze978's user avatar
4 votes
0 answers
124 views

A convex function is "usually" subdifferentiable

Let $X$ be a locally convex topological vector space, and let $f:X\to\mathbb R\cup\{\infty\}$ be a proper, convex, lower semicontinuous function, whose effective domain $D:=f^{-1}(\mathbb R)$ is ...
e.lipnowski's user avatar
4 votes
0 answers
204 views

Fréchet subdifferentiation on riemannian manifolds

Context. I'm looking for a "natural" definition of subdifferentials on riemannian manifolds. Given a function $F:\mathbb R^m \to \mathbb R$, its Fréchet-subdifferential at a point $w \in \...
dohmatob's user avatar
  • 6,716
4 votes
0 answers
197 views

How to find the dimension of the polar cone of a convex cone generated by some given vectors

Suppose we have access to a generating set $\{v_1, ..., v_k\}\subseteq\mathbb{R}^n$ of the convex cone $C=cone(v_1, ..., v_k)$, where $cone(\cdot)$ is the conical hull (i.e. nonnegative span) of ...
Min Wu's user avatar
  • 461
4 votes
0 answers
252 views

Can this function be minimized?

Let $X$ be a locally convex TVS, and let $A$ and $B$ be convex and compact subsets of $X$ with $A \subset B$. Let $f: A \times B \to [0,\infty]$ have the following properties: (1) For all $b \in B$, $...
aduh's user avatar
  • 839
4 votes
0 answers
479 views

analytic approximations of the min and max operators

Question: What is the state of the art on analytic approximations of $\min$ and $\max$? My hunch is that numerical analysts probably have a better solution than the one I propose here. For any $\...
Aidan Rocke's user avatar
  • 3,827
4 votes
0 answers
223 views

Minimization over a convex function of equal vs unequal success probabilities of Bernoulli random variables

Let $U_1,U_2,\ldots,U_n$ be $n\geq 2$ mutually independent Bernoulli random variables. There are two cases of interest: $1.$ The random variables $U_1,U_2,\ldots,U_n$ are identically distributed; $...
Seyhmus Güngören's user avatar
4 votes
0 answers
500 views

Using Linear Programming as an iterative procedure

Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
D. Rusin's user avatar
  • 381
4 votes
0 answers
139 views

Asymptotic behavior of gradient descent on a smooth, convex, non-negative function with no finite minimum - part II

Let $f: \mathbb{R}^d\rightarrow\mathbb{R}_{\geq 0}$ be a function which is convex and smooth (i.e., in $C^{\infty}$). If $x^* \in \mathbb{R}^d$ is the (global) minimum of $f$, it is well known that ...
Daniel Soudry's user avatar
4 votes
0 answers
296 views

Best Approximation in Operator/non-Frobenius Norm

Since the Frobenius norm on matrices is generated by an inner product, solving the optimization/approximation problem of approximating an operator $X$ with a scalar multiple of another operator $Y$ $$\...
Conner DiPaolo's user avatar
4 votes
0 answers
294 views

Derivative of rank $r$ approximation of matrix

Let $Y \in \mathbb R^{n \times c}$ and $r$ be an integer with $1 \le r \le \operatorname{rank}(Y)$. Consider the problem $$\text{minimize} \|Y-X\|_{\text{Fro}}^2\text{ over }X \in \mathbb R^{n \times ...
dohmatob's user avatar
  • 6,716
4 votes
0 answers
237 views

Stochastic subgradient descent almost sure convergence

I was reading up on stochastic subgradient descent, and most sources i could find via google search give quick proofs on convergence in expectation and probability, and say that proofs of almost sure ...
user1539279's user avatar
4 votes
0 answers
76 views

How well does an estimator perform on another dataset?

Suppose $X \sim N(0, \Sigma)$ is a $d$-dimensional Gaussian random vector. And we have $2n$ $i.i.d$ sample $X_1, \ldots, X_{n}, \ldots, X_{2n}$. Let $\hat{\Sigma}_1 = \frac{1}{n}\sum_{i=1}^nX_i X_i^\...
Wuchen's user avatar
  • 505
4 votes
0 answers
129 views

Covering Number of a Positive Semidefinite Cone (Approximate the Objective of a SDP)

I was wondering what the covering number of a positive semidefinite cone is. Consider the semidefinite optimization program \begin{align} \max\langle \mathbf{C}, \mathbf{X} \rangle~~\text{subject to}~...
Steve's user avatar
  • 1,117
4 votes
0 answers
106 views

Designing Character Other Than Temperature for Simulated Annealing on Combinatorial Optimization

Many research on designing temperature for simulated annealing is carried out. We wonder if there is any research on designing general feature of the Hamiltonian used in Simulated Annealing. For ...
Jiayi Liu's user avatar
  • 909
4 votes
0 answers
195 views

Basin of Attraction

I have a function $F$ which is defined as follows: $$ F(x) = \sum_{i=1}^N f(z_i^T x) $$ where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = \...
Mkl's user avatar
  • 291
4 votes
0 answers
124 views

An inequality from the "Interlacing-1" paper

This question is in reference to this paper, http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf (or its arxiv version, http://arxiv.org/abs/1304.4132) For the argument to ...
InterlacingStudent's user avatar
4 votes
0 answers
182 views

This function looks quasiconvex, can't understand why

Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by $$g(\mathbf{y}):=\max_{\mathbf{x}\in\...
Richard Senn's user avatar
4 votes
0 answers
292 views

When is the sum of a weak-$*$ closed convex cone and a subspace also weak-$*$ closed?

Let $X$ be a Banach space. Suppose $C \subset X^*$ is a convex cone and $V \subset X^*$ is a subspace, and suppose both $C$ and $V$ are closed in the weak-$*$ topology. Are there any general ...
Evan DeCorte's user avatar
3 votes
0 answers
98 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
  • 688
3 votes
0 answers
497 views

Proving an optimization problem from continuous input to binary is optimal

Suppose we have a function $f(x,y,z)$ where the inputs are uniform from 0 to 1. The output is either $+1$ or $-1$. And there is a partial symmetry $f(x,y,z) = f(z,y,x)$. Tell me what the minimum of ...
Kunal Marwaha's user avatar
3 votes
0 answers
87 views

What is the name for this type of optimization problem?

As we all know, a classic optimization problem can be represented in the following way: Given a function $f: A \to \mathbb{R}$, find an element $x_0 \in A$ such that $f(x_0) \le f(x)$ for all $x \in ...
Shaun Han's user avatar
  • 141
3 votes
0 answers
87 views

Projection onto level set of convex functional

Fix a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and let $F:L^2_{\mathbb{P}}(\mathcal{F})\rightarrow (-\infty,\infty]$ be bounded-blow, convex, lower semi-continuous, and not identically ...
ABIM's user avatar
  • 5,019
3 votes
0 answers
252 views

Continuum of Lagrange multipliers, duality gap, and minimax theorem

Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
Bogdan's user avatar
  • 781
3 votes
0 answers
202 views

$L^2$-projection onto monotone functions

Let $f:{\mathbb R}\rightarrow{\mathbb R}$ be measurable and such that $$\int_{-\infty}^0(f(x)-a)^2dx+\int_0^{+\infty}(f(x)-b)^2dx<+\infty.$$ This, denoted as $E(a,b)$, is an affine space: $E(a,b):=...
Denis Serre's user avatar
  • 51.5k
3 votes
0 answers
116 views

Convex optimization upper bound for a non-linear optimization

Is there any good convex optimization problem based upper-bound for the following non-linear optimization problem? \begin{align} \max_{x_1,\ldots,x_N}&\quad \sum_{n=1}^{N} \log(1+\frac{x_n}{1+\...
Math_Y's user avatar
  • 311
3 votes
0 answers
135 views

What is the convergence rate of the iterative optimization method?

For the following optimization problem: $$ \mathrm{min}_{A,B} \|I-A^{T}XB\|^2 + \lambda\|B\|^2, $$ where $A$ and $B$ are the two variables ($\|A\|^2 \le \rho$ where $\rho$ is a constant, e.g. 1), the ...
Shijie Pan's user avatar
3 votes
0 answers
120 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 ...
VS.'s user avatar
  • 1,816
3 votes
0 answers
68 views

Convergence of iteration of a convex program

Let $\mathbf{V} \in \mathbb{R}_{+}^{n \times m}, \ \ \mathbf{E} \in \mathbb{R}_{+}^{n \times m}$, with $\mathbf{V} \mathbf{1}_{m} = \mathbf{1}_{n}$ and $\mathbf{E}^{T} \mathbf{1}_{n} = \mathbf{1}_{m}$...
Ded's user avatar
  • 53

1
2 3 4 5
7