The convex-optimization tag has no wiki summary.

**0**

votes

**0**answers

13 views

### Proximal operator of modified L1 matrix norm

In literature proximal operator $prox_{\lambda f} : R^n \rightarrow R^n$ of $f$ is defined as:
$prox_{\lambda f}(V) = argmin(X) (f(X) + (1/2 \lambda)||X-V||^2_2)$
Consider now $g(X) = ...

**2**

votes

**1**answer

84 views

### Projection onto $\ell^{2,1}$ ball

Does anyone have an idea how to project onto the $\ell^{2,1}$ ball efficiently, i.e. how to solve
$$ u = \arg \min_u \|u-f \|^2 \text{such that } \left(\sum_i \big(\sum_j |u_{i,j}|\big)^2 ...

**0**

votes

**0**answers

24 views

### mixed semi definite and second order programming complexity order

Consider the following mixed semi definite and second order programming:
$\begin{array}{l}
\mathop {{\rm{min}}}\limits_{\bf{X}} \,{\rm{Tr}}\left( {{\bf{XA}}} \right)\\
{\rm{s}}{\rm{.t:}}\, & ...

**1**

vote

**1**answer

35 views

### Convergence rate of stochastic gradient decent with projections

Given a strong (not only strict) convex function $f: \mathbb{R}^n\to\mathbb{R}$. On such problems, stochastic gradient decent (SGD) has a convergence rate of $O(1/T)$, where $T$ is the number of ...

**3**

votes

**2**answers

55 views

### Is the prox-residual monotone?

$\newcommand{\scp}[2]{\langle #1,#2\rangle}\newcommand{\id}{\mathrm{Id}}$
Let $f$ and $g$ be two proper, convex and lower semi-continuous functions (on a Hilbert space $X$ or $X=\mathbb{R}^n$) and let ...

**1**

vote

**0**answers

48 views

### dual problem of SDP [closed]

suppose we have the following optimization problem:
\begin{array}{l}
\mathop {\min }\limits_{{\bf{X}},{\bf{x}}} \,\,Tr\left( {{\bf{XA}}} \right) + 2{{\bf{a}}^H}{\bf{x}} + b\\
s.t:\,\,\,\,\left[ ...

**2**

votes

**0**answers

59 views

### proving quasi convexity of multivariable function

Given
an arbitrary $(N \times N)$ square matrix ${\bf X}$
a positive definite $(M\times M)$ matrix ${\bf T}$
a $(Q\times MN), Q< MN$ matrix ${\bf Z}$ consisting of only 1s and 0s where there is
...

**1**

vote

**0**answers

111 views

### Continuity of minimizers to distance function from point to convex set

Suppose I am minimizing the Euclidean distance in $\mathbb{R}^{n}$ between a point $y$ and compact convex set $U$ (where $y\notin U$):
$\min_{x\in U}\|x-y\|$.
I believe the minimizer $x_{U}^{*}$ is ...

**4**

votes

**0**answers

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

**2**

votes

**0**answers

50 views

### Optimality condition for non-differentiable constrained convex optimization problem

(EDIT: see proof at the end) Consider the problem
$$
\min f(x) \; \text{s.t.} \; x\in D
$$
where $f(x)$ is convex but not differentiable, and $D$ is convex.
For differentiable $f$, we know that $x$ ...

**7**

votes

**3**answers

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

**2**

votes

**2**answers

97 views

### sensitivity analysis in conic optimization

I have a conic optimization of the form:
$\min_x \langle c, x \rangle$, s.t. $Ax = b$, $x \in K$.
Where $x \in \mathbb{R}^{n}$, $A$ is an $m \times n$ matrix, $b \in \mathbb{R}^m$, $K$ is a self ...

**0**

votes

**0**answers

40 views

### Sufficient optimality condition for a non-smooth quasiconvex problem

The result of relaxing to an integer program is the following optimization problem:
$$\min_{\textbf{x}} \sum_{i=1}^n \alpha_i h(x_i)\quad subject \; to \quad A\textbf{x} = \textbf{0}$$
where ...

**5**

votes

**1**answer

237 views

### What it is the volume of the unit ball section of the cone of positive definite matrices?

Let $PD_{n}$ be the cone of positive definite $n \times n$ real matrices and let $B$ be the unit sphere in $n \times n$ dimensions. What is the volume of $PD_{n} \cap B$?
EDIT: Let's assume that $B$ ...

**1**

vote

**0**answers

61 views

### Constrained optimization problem with system of differential equations [closed]

Thanks in advance for any help. My question relates to a homework problem. I have been given a system of generalized differential equations with the goal of creating an algorithm that will solve ...

**2**

votes

**1**answer

80 views

### Convex interaction energy

Does anybody know examples of absolutely continuous probability measures $\mu_0,\mu_1$ on $\mathbb{R}^n$ with finite 2nd moments such that
$$
\frac{d^2}{dt^2}\left(\int_{\mathbb{R}^n\times ...

**1**

vote

**1**answer

80 views

### Minimize a strictly convex quadratic function subject to linearly equality and nonnegativity constraints in finite time?

I am wondering if we can minimize a strictly convex quadratic function in finite time, subject to linearly equality and nonnegativity constraints.
Thanks!

**0**

votes

**0**answers

28 views

### Maximizing the product of projections of a vector on another vectors

I want to get the $N\times1$ complex vector $\mathbf{x}$ which maximizes this real valued function
$f=\mathbf{x}^{H}\left (\mathbf{a}_{1} \mathbf{a}_{1}^{H}\mathbf{x}\mathbf{x}^{H}\mathbf{a}_{2} ...

**2**

votes

**5**answers

208 views

### Distance between two sets

Let $A, B$ be two convex and closed subsets of $\mathbb{R}^n$. We would like to the minimum distance between these two sets. i.e., we want to find a solution for the following problem.
$$ \min ...

**1**

vote

**1**answer

53 views

### optimization of inverse matrix with constraint on matrix elements

everyone! I have this optimization problem with constraint.
D and T are symmetric matrice, where T is known and D is the unknown parameter.
x and v are two known p-dimensional vectors.
The objective ...

**2**

votes

**2**answers

90 views

### How to minimize the Bregman divergence on a convex hull spanned from a set of vectors?

everyone.
It has been well known that the following minimization problem of a Bregman divergence with linear inequality
can be solved by successively projecting the current point to each constraint ...

**22**

votes

**2**answers

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

**1**

vote

**0**answers

26 views

### Searching for the maximum of a (strictly convex) two-dimensional distribution via maximization over a series of arbitrarily specified 1D intervals

Let $f$ be a strictly convex two-dimensional distribution with a maximum $M$ at some unknown position $(x_m,y_m)$. Starting from the origin, $(x_0,y_0) = (0,0)$, we need to find $(x_m,y_m)$, however ...

**0**

votes

**1**answer

73 views

### Homotopy with non piece-wise linear boundary

in the middle of a long proof I encounter the following problem.
Let $E$ be a closed and convex set in $\mathbb R^n$ such that for all $\vec x\in E$ it holds that $\sum_ix_i=1$. (We can understand ...

**4**

votes

**2**answers

210 views

### Gradient descent-like optimization on a convex landscape with noisy sampling

This is a rewrite of the original positing (below), and is crossposted to ...

**2**

votes

**1**answer

109 views

### Block Covariance Matrix - Positive Definite? (Quadratic Optimization) [closed]

I have a covariance matrix C. I have then formulated an quadratic optimization problem that involves the following matrix in the quadratic form:
[ C C ]
[ C C ]
However, the quadratic solver ...

**1**

vote

**0**answers

99 views

### Extreme points of a set related to semidefinite cone

Let $X \in \mathbb{R}^{n \times n}$ be symmetric matrix. Consider the following set
$$
\mathcal{C} = \{ X: X \succeq 0, \quad 0 \le X_{ij} \le 1, \forall i,j\}
$$
What are the extreme points of this ...

**3**

votes

**1**answer

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

**0**

votes

**0**answers

67 views

### An attempt to solve “Maximization of a total variation distance subject to another total variation distance in Markov chain”

I have been trying to solve Maximization of a total variation distance subject to another total variation distance in Markov chain. As a recall, suppose we have a pair of correlated random variables ...

**0**

votes

**0**answers

55 views

### No Strong Duality In Spite of Slater's Condition

I was reading some course notes here.
On Page 8, it says:
Note that strong duality holds here (Slater's condition), but the
optimal value of the last problem is not necessarily the optimal
...

**0**

votes

**1**answer

159 views

### Find the following transformation $G$

I asked this question 6 days ago on math.stackexchange.com (http://math.stackexchange.com/questions/656585/find-the-following-transformation-g). I didn't get any answers yet, so I'm posting here.
I'm ...

**0**

votes

**1**answer

102 views

### Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).
The cost to send $x$ unit of flow through edge $e_i$ is defined ...

**4**

votes

**2**answers

129 views

### Minimax theorem on a non convex domain

A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in ...

**-1**

votes

**1**answer

77 views

### Uniqueness of the solution to a quadratic problem [closed]

Consider a positive definite matrix $\boldsymbol H$, the known vectors ${\boldsymbol b}$ and ${\boldsymbol a}_i$. Now the minimization problem is casted with respect to the vector ${\boldsymbol x} $ ...

**0**

votes

**1**answer

103 views

### Eigenvalues of a given parametrized matrix.

Let $\mathbf{A}$ and $\mathbf{B}$ be two complex rank-one $N\times N$ positive semi-definite matrices. Let the matrix $\mathbf{C}$ be defined as
\begin{align}
...

**1**

vote

**1**answer

181 views

### Interior of a dual cone

Let $K$ be a closed convex cone in $\mathbb{R}^n$. Its dual cone (which is also closed and convex) is defined by $K' = \{ \phi\ |\ \phi(x) \geq 0,\ \ \forall x \in K\}$.
I know that the interior of ...

**1**

vote

**1**answer

116 views

### Lagrange multiplier and semidefinite programming

suppose we have a primal semidefinite programming. for finding its dual we use Lagrange multiplier $w_i$ for each semidefinite constraint. If the Lagrange multiplier be zero for one constraint what we ...

**1**

vote

**0**answers

133 views

### How to solve such an optimization problem efficiently？

Given a symmetric positive semi-definite matrix $\mathbf Y$ and a convex set $\mathcal M$ which is a subset of all symmetric positive semi-definite matrices (consider a simple case of $\mathcal M$： a ...

**2**

votes

**2**answers

94 views

### Projection onto rotated box

Does anyone know if there is an efficient way to find the projection of an arbitrary point $z$ onto a rotated box, i.e. onto the set $\Omega=\{x \mid a \leq Ux \leq b\}$ where $U$ is a unitary matrix?
...

**3**

votes

**1**answer

139 views

### Equivalent method for maximum likelihood estimation of covariance parameters

My goal is to estimate the parameters of a covariance matrix $\Omega$, by maximizing the following log-likelihood function:
$$\log L(\vec\tau, \rho, \sigma \mid W, X) = -m\ln(\left | \Omega \right |) ...

**0**

votes

**0**answers

75 views

### minimizing the sum of euclidean norms with box constraints

minimizing the sum of euclidean norms with box constraints
I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...

**1**

vote

**0**answers

93 views

### Maximizing an integral over a convex region

Let $C$ denote a compact, convex region in the plane containing the origin with unit area, and let $f$ be a probability distribution on $C$. Let $f^\ast$ denote the distribution that maximizes the ...

**1**

vote

**0**answers

107 views

### Lipschitz continuity of solution set mapping of a parametric convex optimization problem

I have a parametric convex optimization problem:
\begin{array}{cl}
\underset{x}{\text{minimize}} & f\left(x,z\right)\\
\text{subject to} & g\left(x\right)\leq0
\end{array}
where $x$ is the ...

**2**

votes

**1**answer

114 views

### Circumscribed ellipsoid of minimum Hilbert-Schmidt norm

Let $K\subseteq \mathbb{R}^n$ be a full-dumensional convex body. The Löwner ellipsoid of $K$ is the unique ellipsoid of smallest volume containing $K$. My question is about a related object: the ...

**-1**

votes

**1**answer

44 views

### Determining the sign of each element of the optimal of a strict convex function

The problem is:
Let $\vec{x}\in\mathbb{R}^d$ be the variable and $f(\vec{x})$ be a scalar function that is globally strictly convex in $\mathbb{R}^d$. We assume the unique optimum of $f$ to be ...

**2**

votes

**1**answer

166 views

### quadratic programming on hypercube

I want to maximize a quadratic form $\mathbf x^T\mathbf Q\mathbf x$ and also want to find out which vector $\mathbf x$ maximizes the quadratic form when
$\mathbf Q$ is an $n\times n$ positive ...

**1**

vote

**1**answer

178 views

### Question on convex optimization and dual norms [closed]

I have the following questions about dual norms :
How do you prove that the dual of the dual norm is in fact the original norm?
This is what I have so far:
If I have $||y||_* $ as the norm dual of ...

**2**

votes

**2**answers

111 views

### Survey on Compared Running Time: Ellipsoid Method vs. Simplex Method

If you look through papers on the Ellipsoid Method, there is a large agreement, that the Ellipsoid Method, although theoretically polynomial, is in practice way slower than the Simplex Method. ...

**2**

votes

**1**answer

126 views

### maximizing convex quadratic form over the intersection of unit sphere and positive orthant

For a positive semi-definite matrix $C$, I want to find the solution to the following problem:
$\arg\max_{h\geq 0} h^T C h\quad$ s.t. $\quad h^T h\leq 1$
Any pointers are welcome.

**3**

votes

**1**answer

172 views

### Fast algorithm for maximizing smallest eigenvalue of linear combination of hermitian matrices

I have an engineering back ground. Due to work, I came across this problem
\begin{align}
&\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\
...