# Questions tagged [convex-optimization]

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

648
questions

**2**

votes

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**4**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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