MathOverflow

Questions tagged [convex-optimization]

Ask Question

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

648 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
2
votes
1answer
38 views

Convexity of a positive definite objective with min(x,y)-nonlinearity

I have derived an optimization objective of the form $$ f(x) = \sum_{i,j} C_{ij}\min(x_i, x_j), s.t. g(x) \geq 0 $$ where $C \in \mathcal{R}^{N \times N}$ is a positive definite matrix, and $x \in \...
1
vote
0answers
37 views

When does the metric projection operator have a closed form?

I have a simple question. Often times in optimization, the following function is used: Let $H$ be a real Hilbert space and $C$ a nonempty closed convex subset of $H$, then the metric projection is ...
0
votes
0answers
66 views

Maximum mutual information of random unitary transformation

Let $\mathbf{U}$ and $\mathbf{V}$ be random unitary matrices independent of random input vector $\mathbf{x}$. Moreover, $\mathbf{z}$ be random iid complex Gaussian vector with zero mean and identity ...
0
votes
0answers
9 views

Proof of lower complexity bound for non-smooth convex optimization in small dimensions

I am looking for a reference which contains a proof that the lower first-order complexity bound for non-smooth convex optimization in dimension $n$ is $\Omega(n\log{1/\epsilon})$. In the book Nesterov,...
0
votes
0answers
21 views

Loss function for matrix with fixed trace

I have a matrix $P \in \mathbb{R}^{n \times m}$ where $n \gg m$ and each row of $P$ has norm $1$. It is not hard to see that the $P^T P$ has a fixed trace $n$. I am try to find a loss function to push ...
1
vote
0answers
39 views

Analytic lower-bound for minimal value of $\|x\|^2$ such that $\|Cx-b\|^2 \le c^2$ (a hyperellipsoid)

Let $C$ be an $n \times p$ matrix and $b$ be a column vector of length $n$, and $c>0$. Let $E := \{x \in \mathbb R^p \mid \|Cx-b\| \le c\}$, a hyperellipsoid in nonstandard position. Question 1. ...
0
votes
0answers
35 views

maximize quadratic form with respect to cov matrix of multinomial and linear constraint

Given $x_{m,1}, T$, how to solve $\max_{y} x^T(\mathop{\mathrm{diag}}(p)-pp^T)x$, s.t. $p = Ty, \textbf{1}^Ty=1$ The dimensions are $p_{m,1}, y_{n,1}, T_{m,n}$ and $T$ is a transition matrix ...
1
vote
0answers
62 views

Applications of 1st order oracle in stochastic convex optimization

Due to the rise of machine learning, in many stochastic convex optimization papers the first-order methods now mainly focus on the finite-sum objective function setting. This ends up significantly ...
1
vote
0answers
19 views

Are such assumptions of functions similar to strong convexity reasonable in convex optimization?

For $\mu$-strongly convex function $f:\mathbb{R}^d\to\mathbb{R}$, the following property holds: for any given $x,y\in\mathbb{R}^d$, we have $$ (\nabla f(x) - \nabla f(y))^\top(x-y) \ge \mu \|x-y\|^2.$$...
2
votes
1answer
224 views

Is this geometrically-defined minimum an algebraic number?

I'm trying to find the maximum value $c$ so that there is a probability distribution with support in $R_c:=[-2,2]\times[-2,2]\cap\{x+y\geq c\}$ so that $32$ expectational equations hold. In ...
4
votes
1answer
103 views

Example of empty projection in strictly convex Banach space

Let $X$ be a strictly convex Banach space, let $C\subseteq X$ be a nonempty closed convex set, and let $P_C$ be the set-valued metric projection $$P_C(x) = \{y\in C : \|x-y\| = d(x,C)\} . $$ We know ...
1
vote
1answer
122 views

Matrix reconstruction puzzle

Say a reconstruction of matrix $A$ is $A'$ and it's defined as $$ A' = PDP^TA $$ where $P$ is an orthogonal matrix, $D$ is a diagonal binary (1 or 0) matrix. In a trivial case, when all diagonal ...
2
votes
0answers
56 views

Lagrangian multipliers and a variant of Newton's method

A variant of Newton's method for solving the equality constrained problem \begin{equation} \begin{array}{ll} \min &f(x) \\ \text{s.t.} & h(x) = 0 \end{array} \end{equation} is as follows: \...
2
votes
1answer
105 views

When is a function a convex conjugate?

Let $X$ be a Banach space; $X^*$ be its dual; and $g:X^*\to\mathbb R\cup\{\infty\}$ be a proper, convex, weak${}^*$-lower semicontinuous function with weak${}^*$-compact effective domain. Question: Is ...
1
vote
0answers
148 views

continuity of linear programming

I have the following conjecture: Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
0
votes
0answers
35 views

Minimum of the positive semidefinite quadratic function

Crossposted on Math SE Given quadratic function $$ f(x) = \sum_{i \in L^-} \frac{\lambda_i}{v_i^T v_i}(v_i^Tx + \frac{1}{2\lambda_i}v_i^T c)^2 + \sum_{i \in L^0} \frac{1}{v_i^T v_i}(v_i^Tc \cdot v_i^...
3
votes
0answers
98 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 ...
7
votes
1answer
124 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 ...
1
vote
2answers
79 views

Convexity of inverse quadratic form

Let $\alpha_i\in[0,1]^k$, $x_i\in\mathbb{R}^d$ for all $i\in[k]$, with $k \geq d$. Define $X: \operatorname{col}(X) = \{x_i\}_{i\in[k]}$, $\Lambda(\alpha) = \operatorname{diag}(\alpha)$, $y\in\mathbb{...
2
votes
1answer
136 views

Generalizing Pythagorean Theorem: equations defining edges of a (convex) $n$-gon with $n-2$ prescribed angles?

Let $n\geq 3$ be an integer and $0<\alpha_1, \dots ,\alpha_{n-2}<1$. Let's say a tuple of positive numbers $(e_1,\dots, e_n)$ is nice if there is a convex $n$-gon $A_1\dots A_n$ such that $\hat ...
3
votes
0answers
83 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):=...
3
votes
0answers
146 views

Sufficient condition for geodesic convexity/connectedness

Let $(\Sigma,g)$ be a connected smooth Riemannian manifold without boundary. By a minimizing geodesic I mean a geodesic whose length equals the distance between its endpoints. Let us consider the ...
0
votes
0answers
113 views

Maximizing a piecewise-linear convex function

Crossposted on Operations Research SE. I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables: ...
3
votes
0answers
46 views

Conjugate of composition in Bochner spaces

Let $H$ be a separable Hilbert space (of non-zero dimension), let $(\Omega,\Sigma,\mu)$ be a finite measure space, and let $L^2(\mu;H)$ be the Bochner-space $\mu$-integrable $H$-valued functions. ...
1
vote
0answers
40 views

Conjugate gradient and the eigenvectors corresponding to the large eigenvalues [closed]

I am working on an optimization problem (for example, conjugate gradient) to solve $Ax=b$, where $A$ is a symmetric positive definite matrix. I can understand that the CG (conjugate gradient) has ...
0
votes
2answers
102 views

Matrix norm minimization and matrix inner product

One of the famous problem in SDP is the matrix norm minimization (see S. Boyd, Convex Optimization, p. 170). Consider: \begin{equation}\label{eq:Lasse} \begin{aligned} &\min_{\mathbf{x}} & &...
0
votes
0answers
23 views

Analytic formula for $D(x,y) := \sup_{z \in B_p} \|z-x\|_1 - \alpha\|z-y\|_1$, where $\alpha \ge 0$ and $B_p$ is the unit $L_p$-ball

Let $\alpha \in [0,\infty)$ and $p \in [1,\infty]$, and consider the function $D_\alpha:B_p \times B_p\to \mathbb R$ defined by $$ D_{\alpha,p}(x,y) := \sup_{z \in B_p} \|z-x\|_1 - \alpha\|z-y\|_1, $$...
0
votes
0answers
37 views

Let $A,B,C$ be centrally-symmetric convex bodies. What is this function $G(x,y) := \sup_{b \in B}\inf_{a \in A} a^T x - b^T y + \|a-b\|_C$?

Let $A$, $B$, and $C$ be centrally-symmeric convex bodies in $\mathbb R^n$. Note that any such set can such set induces a norm $\|\cdot\|_C$ on $\mathbb R^n$ defined by $\|x\|_C := \sup_{c \in C}c^\...
19
votes
4answers
963 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)$. ...
0
votes
0answers
23 views

Techniques to bound a regularized loss involving a maximum?

I am studying the following optimization problem $DROT(a,b) = \max \int f(x)\,dP(x) + \int g(y)\,dQ(y) - \frac{1}{\gamma}(\phi(f)+\varphi(g))$ subject to $f(x)+g(y)\leq c(x,y)$ where $\phi$ and $\...
1
vote
0answers
52 views

Proximity operator of lower semi-continuous and convex functions pre-composed with norm

Let $\phi:(-\infty,\infty) \rightarrow (-\infty,\infty]$ be a some-where finite, lower semi-continuous, increasing, and convex function. It is easy to verify that the function $\Phi:\mathbb{R}^n\...
0
votes
0answers
34 views

References for matrix variational problems on the unitary group

Let $U(d)$ denote the group of unitary $d\times d$ matrices. Let $\mathcal C_d$ denote the cone of Hermitian positive semidefinite $d\times d$ matrices. Fix an integer $r\geq 1$ and let $C(U(d),\...
1
vote
0answers
51 views

Decomposition of Polyhedral - An example

There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system $$ \...
1
vote
1answer
107 views

Generalization of Dickson's Lemma

Given $\{v^i\}_{i \in \mathbb{N}} \subseteq \mathbb{N}^n$, and $\cup_{k=1, \ldots, m} C_j = \mathbb{N}^n$ for some $m$, where each $C_k$ is a cone generated by rational vectors. My question is: does ...
0
votes
1answer
70 views

Gradient-descent “type” Methods for non-convex and non-smooth functions

Most (stochastic) "gradient descent" type algorithms (such as Nesterov-accelerated gradient-descent or ADAM) seem to be well-defined only for functions which are either: lower semi-...
2
votes
2answers
125 views

Convex optimization closed-form solution

Consider the standard second order cone programming problem: \begin{equation} \begin{array}{ll} \operatorname{maximize} & \bar{p}^{T} x \\ \text { subject to } & \bar{p}^{T} x+\Phi^{-1}(\beta)\...
0
votes
1answer
61 views

When does strict inclusion holds for the domain of subdifferential?

Recall that, given an extended real-valued function $f: \mathbb{R}^n \to (-\infty, \infty]$ Its effective domain is, $$\text{dom}(f) = \{x \in \mathbb{R}^n : f(x) < +\infty\}$$ The subdifferential ...
1
vote
0answers
53 views

Taut string algorithm and TV-minimization equivalence

Given real numbers $y_i's$, consider the following convex optimization problem: $$ \min_{x_i's} \sum_{i=1}^N(y_i-x_i)^2 + \lambda\sum_{i=1}^{N-1}|x_{i+1}-x_{i}|. $$ The paper A Direct Algorithm for 1D ...
1
vote
1answer
56 views

Prove zero slope point is global maximum for constrained function with binomials. Without restriction, objective function is non-concave

How to prove the zero slope point is a global maximum in this non-concave program for a function with binomials? I need to find the (global) maximum of the following constrained problem: $$\max_{CAP} \...
0
votes
0answers
47 views

Upper bound for the Gradient in terms of rank of a matrix

Assume $f$ is a convex function, for instance: $f(A) = \lVert AX - B \rVert_F^2, A \in \mathbb{R}^{n \times n}, rank(A) = r < n$. Is there any proved relationship between an upper bound on $\lVert \...
0
votes
0answers
101 views

Optimization over the set of all bounded probability measures

Given $X$ finite, fix a continuous function $\theta \in \Delta^+ (X) \to [0,1]$, fix a probability measure $\mu^*$, and a $\varepsilon > 0$. Consider: $$ \max_{\mu \in \Delta^+ (X)} \theta (\mu), \...
0
votes
0answers
92 views

Strongly convex optimization error bounds

Suppose I want to minimize a function $G(f)$ using first order strongly convex methods and I get a solution $f^*$, where we restrict our solution set to strongly convex $f$. Now let $f_0$ be the ...
1
vote
0answers
96 views

Statistical analysis of optimization solution involving Brenier potentials?

I'm reading the paper https://arxiv.org/pdf/1905.10812.pdf where strongly convex approximations to Brenier potentials are approximated. Let $\mathcal{E}$ be a partition of $\mathbb{R}^{d}$ and $ 0\leq ...
0
votes
0answers
37 views

A parametrized saddle point problem with linear constraints

I am struggling to find any potential algorithm for solving a saddle point problem. More precisely let $\mathcal{P}=\{ \mathbf{x}\in \mathbb{R}^{d}; \mathbf{A}\mathbf{x}=\mathbf{b}, \mathbf{x} \geq 0\}...
0
votes
0answers
46 views

Second-order def of strong convexity wrt general norms

A function $f: R^n \rightarrow R$ is said to be C-strongly convex with respect to a norm $\|\cdot\|$ if for all $x,y$ and $\lambda \in [0,1]$ $$f(\lambda x + (1-\lambda)) \le \lambda f(x) + (1-\lambda)...
5
votes
1answer
226 views

Find a combination of convex function so that it is positive

A student in my class asked me the following question, I did know what tools will be needed to attack it. But I found it is an interesting question. Let $f_1,f_2$ be two convex functions on $[0,1]$ ...
0
votes
1answer
62 views

conditions on the boundary of a compact set to ensure the volume of the intersection of a small ball with the set doesn't vanish

Given a compact set $E$ with non-empty interior in $R^d$ and some small positive number $r$, what kind of conditions should we put on the set $E$ so that for all $x\in E$, the volume of the ...
1
vote
1answer
56 views

Decreasing maximizer and concave value function

I am looking for a twice continuously differentiable function $f$ on $\mathbb{R}_+^2$ such that for $$v(k):=\max_{x} \{\lambda x-f(x,k)\},$$ where $\lambda >0$, we have $\frac{\partial{x^*}}{{\...
4
votes
2answers
129 views

Clustering of vertices in an $n$-dimensional cube

Consider the vertices of an $n$-dimensional cube. The distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices. If we ...
0
votes
0answers
29 views

How to derive Lipschitz constant of Moreau envelope of a Lipschitz function

This question is from a lecture note of convex optimization. Q: Prove: If $f$ is $L$-Lipschitz, then its Moreau envelope $f_{\mu}$ is also $L$-Lipschitz. ($L = \mu^{-1}$) [NOT my homework] $$f_{\mu}(x)...

1
2 3 4 5
…
13

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.