The convex-optimization tag has no wiki summary.

**2**

votes

**1**answer

69 views

### Linearly constrained eigenvalue problem

Suppose I'd like to:
\begin{align}
\mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\
\text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\
&& ...

**4**

votes

**2**answers

221 views

### Convex Sets and Nearest Neighbors

For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is uniquely determined. It is known that ...

**3**

votes

**1**answer

61 views

### Can one always find sparse solutions to an $\ell^1$-minimization problem?

Consider $A\in\mathbb{R}^{m \times N}$ and $b \in \mathbb{R}^m$, with $m<N$. Is it true that the optimization problem
$$\min \|x\|_1 \quad s.t. \;\; A x = b,$$
admits an $m$-sparse solution in ...

**7**

votes

**3**answers

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

**1**

vote

**2**answers

118 views

### investigating positivity/negativity of a function [closed]

I'm investigating if and how the positivity or negativity of a multivariable function can be proved. Consider $y_{1},y_{2},y_{3}\in\mathbb{R}$ and the following function
...

**2**

votes

**1**answer

52 views

### A difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$.
(Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...

**1**

vote

**2**answers

105 views

### The set of matrices with same spectral radius

I am working on an optimization problem over the set of positive matrices (that is, matrices where all entries are positive numbers) that have the same spectral radius. My main problem is how to ...

**2**

votes

**1**answer

99 views

### Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$?
I know ...

**0**

votes

**0**answers

22 views

### Optimize the distribution if it is left unsmoothed

I have a question about distribution. Let see my problem
The paper said that the distributions p and q are left unsmoothed, so we can ignore Kernel density. But I don't understand what is left ...

**0**

votes

**0**answers

23 views

### Convergence of Coordinate Descent / Alternating directions

My question regards this method
http://en.wikipedia.org/wiki/Coordinate_descent,
where at each step a function $f$ is minimized along one coordinate axis (or block of coordinates).
Assume that $f: ...

**0**

votes

**0**answers

58 views

### numerical and functional mixed optimization problem $\max f - \min f +\int_{-1}^1 (f'(x)-x)^2dx$

Given a function $g(x)$ and its domain, we want to get another function $f(x)$ whose derivative is approximately $g(x)$, but so that $f(x)$ itself has small variation. For example, for ...

**3**

votes

**1**answer

157 views

### Linear dependency of real numbers with integer coefficients adding up to zero [closed]

Let $x = (x_1, \dots, x_n)$ be a vector of real number. I was asking myself if there was an efficient way of telling whether there exists a non-zero vector of integers $z \in \mathbb Z$ such that both
...

**1**

vote

**0**answers

71 views

### Convex Optimization related problem

Suppose two non-negative convex functions $f$ and $g$ be given.
We want to solve the following optimization
$$\max_{g\leq\epsilon}f.$$
Now suppose that both $f$ and $g$ can be upper-bounded by a ...

**1**

vote

**0**answers

276 views

### On increasing the penalty term in convex optimization with regularization

Given the two strictly convex (unique solution) optimization problems as:
$$Problem\:1:\min_{X} f(X)+\|X\|_{F}^2 \hspace{2cm}Problem \:2:\min_{X}f(X)+n\|X\|_2^2$$
where $X\in\mathbf{S}_{++}^{n}$ ...

**2**

votes

**0**answers

35 views

### Reference request: Edmond's Algorithm for integer hull

I'm looking for a good reference for the algorithm (supposedly by Edmonds) to compute the integer hull of a polytope, not by cutting plane methods but by starting with a set of integer points and then ...

**1**

vote

**0**answers

22 views

### Changing a nonlinear equality constraint into some conic inequality plus rank constraint

If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...

**2**

votes

**1**answer

69 views

### Is first term of my cost function convex?

I have an optimization problem in the form of
[\begin{array}{l}
\mathop {{\rm{Minimize}}}\limits_{\bf{X}} \,\,\,2\left| \delta \right|\sqrt {{\rm{Tr}}\left( {{\bf{A}}{{\bf{X}}^2}} \right)} {\rm{ - ...

**0**

votes

**0**answers

46 views

### Finding gradient of an optimization

I am trying to find the gradient of the following optimization problem and then add to objective, but I got some trouble in computing. Could you please help me?
Assume that we have an optimization ...

**1**

vote

**0**answers

27 views

### Characterization of the optimal solution in relative entropy minimization

The following optimization problem is related to relative entropy and to the limit of the iterative proportional fitting procedure.
For $1 \leq i,j \leq n$ and fixed $w_{ij} \geq 0$, and fixed $a_i, ...

**4**

votes

**1**answer

171 views

### optimization problem, any solution?

The objective is as follows:
$\min_{\mathbf{F}} a Tr(\mathbf{F} \mathbf{F}^H) - Re\{\mathbf{b}\mathbf{F}^H \mathbf{C} \mathbf{F} \mathbf{d}\}$
$s.t.\ \ \ Tr(\Sigma \mathbf{F} \mathbf{F}^H)<p$
...

**5**

votes

**1**answer

107 views

### Reference request: Continuity of unique maximizer of linear functional on convex set

Does anyone know reference for a theorem of the following sort:
Proposition: Let $K \subset\mathbb {R}^n$ be a compact convex set, and assume that
$$f(w):=\operatorname{argmax}_{x\in K}w(x) $$ is ...

**0**

votes

**0**answers

30 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

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

**1**

vote

**1**answer

61 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

40 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

72 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

61 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

75 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

130 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

153 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

68 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$ ...

**8**

votes

**3**answers

644 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

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

**1**

vote

**0**answers

86 views

### Diagonal entries of a Cholesky factorization

Let $I$ denote an identity matrix, $E$ denote the all-one matrix of dimension $k\times k$ and $c$ some positive real number. Define $X=B(I-cE)B^T$ where $B$ is given by
$B:=\begin{pmatrix}
1 ...

**0**

votes

**0**answers

50 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

246 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

65 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

85 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

100 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

29 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

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

**2**

votes

**1**answer

82 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

110 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

817 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

101 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

266 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

128 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

110 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

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