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
38 votes
2 answers
2k views

How to make a sandwich from just one piece of bread?

I don't know how to go about such questions. It's not exactly my area, so maybe it is stupid, but curiosity is winning. So I have a piece of bread $P$ of a really non-regular shape (let's make it ...
erz's user avatar
  • 5,385
30 votes
5 answers
13k views

Can all convex optimization problems be solved in polynomial time using interior-point algorithms?

Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
Optimizationguy's user avatar
25 votes
2 answers
2k views

An Interesting Optimization Problem

You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
Praveen Dhinwa's user avatar
20 votes
4 answers
4k views

Is the pseudoinverse the same as least squares with regularization?

Given a linear system $Ax=b$, the pseudoinverse of $A$ is found as the matrix $A^+$ such that $x=A^+ b$ where $x$ solves the least squares problem $\min \| Ax - b \|^2 $ and $x \perp \mathcal{N}(A)$. ...
Herman Jaramillo's user avatar
18 votes
8 answers
3k views

When do people actually use the maximum entropy distribution?

One of the standard problems in convex optimization is the calculation of the maximum entropy distribution that satisfies some set of criteria. For example, if $\mathbf{x} \in \mathbb R^n$ is an ...
Ed Davis's user avatar
  • 183
18 votes
3 answers
2k views

Current state of the Komlos conjecture on vector balancing

Komlos Conjecture: the exists an absolute constant $K>0$ such that for all $d$ and any collection of vectors $v_1,\ldots, v_n\in \mathbb{R}^d$ with $\left\lVert v_i\right\rVert _2=1$ we can find ...
TOM's user avatar
  • 2,218
14 votes
1 answer
4k views

Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension

By KL divergence I mean $D(P||Q) = \int dP \log(\frac{dP}{dQ})$. I am looking for the conditions under which this strong convexity is true and possible references. I could not find an answer for ...
Maziar Sanjabi's user avatar
13 votes
2 answers
715 views

Is there a class of optimization problems more general than semidefinite programming?

I was TA-ing my convex optimization class and explaining that linear programs are a special case of second-order cone programs, which are themselves special cases of semidefinite programs. Is there ...
Anthony Esparza's user avatar
13 votes
4 answers
2k views

Is group theory useful in any way to optimization?

For what I have seen, optimization uses a lot of linear algebra and convex analysis, but I have not seen any group theory being used, so I was curious about it. Is group theory useful in any way to ...
13 votes
3 answers
814 views

Famous theorems that are special cases of linear programming (or convex) duality

The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...
13 votes
1 answer
1k views

Minimize sum of $\ell_2$ norm and linear combination, on simplex

Let $\Delta_n := \{x \in \mathbb{R}^n | x \ge 0, \sum_{1 \le i \le n}x_i = 1\}$ be the $n$-simplex. For $a, b \in \mathbb R^n$, with $\Delta_n \not \ni a$, consider the problem of computing the ...
dohmatob's user avatar
  • 6,716
13 votes
1 answer
2k views

An intuition for three different types of subgradients (proximal, regular, limiting)

I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking. These subgradients are (assume $x \in$ ...
Ben Stott's user avatar
  • 239
11 votes
2 answers
521 views

Convex hull of the Stiefel manifold with non-negativity constraints

Consider the Stiefel manifold $$\mathrm{St}(n,k) :=\{X \in \mathbb{R}^{n\times k} : X^TX = I_k\},$$ where $I_k$ is the $k$-dimensional identity matrix. It is well known that $$\mathrm{conv} \left( ...
Mahdi's user avatar
  • 1,991
11 votes
2 answers
376 views

Sum of squared nearest-neighbor distances between points in a square

Let $\square_2=\{(x,y): 0\leq x, y\leq1\}$ be the unit square in $\mathbb{R}^2$. Take $n>1$ points $P_1, \dots, P_n\in\square_2$. Denote the distances $d_j=\min\{\Vert P_k-P_j\Vert: k\neq j\}$, ...
T. Amdeberhan's user avatar
10 votes
4 answers
897 views

The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small? More ...
Will Schaefer's user avatar
9 votes
1 answer
2k views

Is There an Induction-Free Proof of the 'Be The Leader' Lemma?

This lemma is used in the context of online convex optimisation. It is sometimes called the 'Be the Leader Lemma'. Lemma: Suppose $f_1,f_2,\ldots,f_N$ are real valued functions with the same ...
Daron's user avatar
  • 1,761
9 votes
1 answer
301 views

Closedness of linear image of positive L1 functions

Let $\mathcal X$ be the Banach space of $L^1$ functions on some probability space, $\mathcal Y$ be some other Banach space, $T:\mathcal X\to \mathcal Y$ be some surjective continuous linear map, $\...
e.lipnowski's user avatar
9 votes
1 answer
713 views

property of convex functions

I am able to give a proof to the following inequality for convex functions. Most likely this is well known, but I am unable to find a reference. I would appreciate if someone more knowledgeable in the ...
Hammerhead's user avatar
  • 1,171
9 votes
2 answers
1k views

Orthogonal representations of graphs

A faithful orthonormal representation of a graph $G=(V,E)$ on $n$ vertices $\{1,2,\dotsc,n\}$ is an assignment of unit vectors $v_1,v_2,...,v_n \in \mathbb{R}^d$ to the vertices of $G$ such that $\...
pizzazz's user avatar
  • 201
9 votes
2 answers
916 views

Removing constraints in convex optimization

Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and ...
Jeff Kenney's user avatar
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
3 answers
514 views

Lower bound for spectral radius on $\operatorname{GL}(n,\mathbb{Z})$

Consider the group of matrices $G =\operatorname{GL}(n,\mathbb{Z})$ with integer entries and determinant $\pm 1$. For each matrix $D \in G$, the product of the eigenvalues of $D$ is equal to $\det D =\...
Liam Baker's user avatar
8 votes
4 answers
500 views

Abstract treatment of multivariate calculus relevant for optimization

After studying the basics of (convex) optimization, I've become convinced there's sometimes a conceptual benefit in thinking of quantities like gradients etc. in a coordinate-free way, and keeping ...
amakelov's user avatar
  • 987
8 votes
2 answers
684 views

Bounding the spectral gap of a simple symmetric matrix

I have a seemingly innocent linear algebra problem that I cannot solve, and which I hope that you would kindly offer some insight into. Here is the description: Let $\mathbf{a} = (a_1, a_2, \dots, a_d)...
Yi Huang's user avatar
  • 333
8 votes
2 answers
700 views

On the convexity of element-wise norm 1 of the inverse

Question first asked on math.stackexchange here: https://math.stackexchange.com/questions/317209/on-the-convexity-of-element-wise-norm-1-of-the-inverse On the convexity of element-wise norm 1 of the ...
Ferpect's user avatar
  • 83
8 votes
3 answers
2k views

Optimization problem with determinant as objective

Let $A$ be a given symmetric positive definite $N\times N$ matrix. I need to find a symmetric positive semi-definite matrix $S$ which is the solution to the following optimization problem \begin{align}...
dineshdileep's user avatar
  • 1,371
8 votes
1 answer
1k views

Finding Toeplitz matrix nearest to a given matrix

For an arbitrary $N\times N$ Hermitian matrix $A$, I want to derive a Toeplitz matrix from $A$ such that the eigenvectors of both matrices have minimal change. Specifically I want find the Toeplitz ...
Creator's user avatar
  • 435
8 votes
1 answer
1k views

Uniqueness of a Solution for a Convex Optimization Problem

I have the following convex optimization problem: $$\begin{array}{ll} \text{maximize}_{{f,g}} & \displaystyle\int_{\Omega} g^u{f}^{1-u}\mathrm{d}\mu\\ \text{subject to} & \displaystyle\int_{\...
Seyhmus Güngören's user avatar
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
2 answers
441 views

Proving the set $\left\lbrace \frac{(x + y)^2}{\sqrt{y}} \leq x - y + 5, y > 0 \right\rbrace$ is convex

I have recently picked up a course on Convex Analysis in my spare time, but feel I'm not quite up to speed with the 'tricks' for proving a set is convex. I have managed to prove this by moving all ...
AlwaysLost123's user avatar
7 votes
1 answer
377 views

Nondifferentiable convex function whose subdifferential admits a continuous selection

Is there a convex function $F$ that is not differentiable, but whose subdifferential admits a continuous selection, i.e. a continuous $g$ with $g(x) \in \partial F(x)$ for all $x$ in the domain? In ...
usul's user avatar
  • 4,429
7 votes
2 answers
432 views

Gaussian Surface Area of Positive Semidefinite Cone

Let $\mathbb{R}^n$ be the Euclidean space and $A \subseteq \mathbb{R}^n$ be a sufficiently regular set, e.g., one that has smooth boundary or is convex. We define the $\epsilon$-neighbor of $A$ in the ...
Minkov's user avatar
  • 1,117
7 votes
1 answer
350 views

Is the solution of this optimization problem always positive semidefinite?

We are given a set of unit vectors $U \subset \mathbb{C}^n$ which spans the space $\mathbb{C}^n$. Given another unit vector $x$, consider then the following optimization problem: $$ \sup_H \left\{ x^*...
F.G.'s user avatar
  • 73
7 votes
2 answers
251 views

What methods do we have to understand the spectrum of matrices with restricted entries?

Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"), What is the largest possible spectral radius of a $...
user6818's user avatar
  • 1,883
7 votes
1 answer
396 views

Does the plane clustered to minimize sum distances^2 to clusters centers ( inertia / "K-means") produce hexagonal clusters / hexagonal lattice?

"K-means" is the most simple and famous clustering algorithm, which has numerous applications. For a given as an input number of clusters it segments set of points in R^n to that given number of ...
Alexander Chervov's user avatar
7 votes
1 answer
196 views

How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?

This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...
student's user avatar
  • 1,320
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
2 answers
516 views

Why are $\Gamma_0$ functions called this

It is very common to indicate with $\Gamma_0(A)$ the set of lower semicontinuous convex functions from $A$ to $(-\infty,+\infty]$ with nonempty domain. An example of usage of this notation can be ...
MMFF's user avatar
  • 71
6 votes
2 answers
458 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
6 votes
2 answers
2k views

Computational complexity of unconstrained convex optimisation

What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...
Alex Flint's user avatar
6 votes
2 answers
307 views

Convex optimization with full subdifferential information

Can anyone direct me to any algorithms or theorems that describe the difficulty of solving a non-smooth convex optimization problem for the special case where the full subdifferential is available? ...
Tom Solberg's user avatar
  • 3,929
6 votes
1 answer
2k views

SDP formulation of noisy low-rank matrix completion

Exact low rank matrix completion using nuclear norm minimization can be formulated as a semidefinite program (SDP). Following the notation in the paper, a convex problem for noisy matrix completion ...
tngo's user avatar
  • 63
6 votes
2 answers
2k views

Wasserstein distance and the Kantorovich-Rubinstein duality

The only few references I could find on this topic are either amateur blog posts (http://n.ethz.ch/~gbasso/download/A%20Hitchhikers%20guide%20to%20Wasserstein/A%20Hitchhikers%20guide%20to%...
gradstudent's user avatar
  • 2,136
6 votes
1 answer
165 views

Subsets of a ball/sphere with the largest sum of distances

$\newcommand\R{\mathbb R}\newcommand\S{\mathbb S}$Let $B_d$ and $S_{d-1}$ denote, respectively, the closed unit ball and the unit sphere in $\R^d$. Let us say that a finite subset $F$ of $B_d$ is ...
Iosif Pinelis's user avatar
6 votes
1 answer
659 views

If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?

I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...
ArtificiallyIntelligent's user avatar
6 votes
5 answers
712 views

Convex optimization over vector space of varying dimension

In all instances of convex optimization I know of, the dimension of the vector space is defined beforehand. Is there any work on convex optimization over a vector space of varying dimension? For ...
LowerBounds's user avatar

1
2 3 4 5
16