**0**

votes

**0**answers

44 views

### Bounding the off-diagonal entries of a hermitian matrix [on hold]

I asked this question on stackexchange and didnt receive any answers, am therefore posting it here.
The Pauli matrices are $I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$, $X = ...

**0**

votes

**0**answers

35 views

### How to solve this nonlinear optimization problem?

I have a nonlinear optimization problem with linear constraints. How to solve this? $\sigma_i$ and $\rho_i$ are the optimization variables.
...

**-1**

votes

**0**answers

15 views

### stochastic dual coordinate ascent VS [closed]

I am using vl_feat library to train an SVM. The function I am using (vl_svmtrain http://www.vlfeat.org/matlab/vl_svmtrain.html) uses stochastic dual coordinate ascent to minimize the HINGE LOSS as I ...

**0**

votes

**0**answers

34 views

### Limit of argmin of sum

Suppose that I know $f_n\rightarrow f$ and $g_n\rightarrow g$ are both continuous maps from a Complete Riemmanian Manifold $X$ to $\mathbb{R}$ which converge pointwise almost everywhere. Then is it ...

**0**

votes

**0**answers

35 views

### Separation on discrete set

Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ ...

**0**

votes

**0**answers

18 views

### A possible condition on a set of vectors to be uniquely determined by their gramian?

Suppose you are given a gramian matrix $G=W^TW\in R^{k\times k}$, $W\in R^{d\times k},\;d>k$.
The given gramian $G$ determines, up to a unitary transformation, the columns of $W$, i.e. an ...

**1**

vote

**0**answers

27 views

### Optimizing sum of approximate and exact functions

This is a research question that I had asked in Math.SE about a month ago, but even after putting a bounty on it, I did not get any answers.
I have two real values functions, where one ...

**0**

votes

**0**answers

14 views

### Finding orthogonal basis with constraint

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$
with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$.
And is there any condition on $V_i,i\leq ...

**0**

votes

**0**answers

52 views

### Unsupervised classification [migrated]

In a typical supervised learning problem, one observe $(X,Y)$ where $Y$ is a categorical variable. We confront the such a problem that $Y$ is hidden and instead $(X,Z)$ is observed where both ...

**0**

votes

**0**answers

22 views

### Dennis More' Superlinear Convergence_refrences request

Why in the proof of superlinear convergence of restricted broyden class (for the unconstrained optimization) we need the bounded deterioration condition for the approximation of all the true hessian ...

**1**

vote

**0**answers

27 views

### Which algorithm is most efficient for a specific QP problem

I have a QP problem of the following kind:
$\min_{\alpha\in\mathbb{R}^n}\frac{1}{2}\alpha^T M \alpha - p^T\alpha$
s.t. $l\leq \alpha \leq u$
The matrix $M$ is symmetric and positive definite and of ...

**1**

vote

**0**answers

18 views

### Concavity of maxima [closed]

Suppose we have the following optimization problem : $\min\limits_x kf(x) + g(x)$ where $f$ is a decreasing convex function in $x$ and $g$ is an increasing convex function. Can we say that $x^*$ is ...

**4**

votes

**0**answers

77 views

### Designing Character Other Than Temperature for Simulated Annealing on Combinatorial Optimization

Many research on designing temperature for simulated annealing is carried out. We wonder if there is any research on designing general feature of the Hamiltonian used in Simulated Annealing.
For ...

**4**

votes

**2**answers

69 views

### About optimization with Renyi divergence

Can someone link me to some pedagogic example of computing the Renyi divergence between two discrete/continuous distributions? Like examples where someone has been able to obtain a neat closed form ...

**4**

votes

**0**answers

132 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 & ...

**1**

vote

**0**answers

32 views

### Minimum of sum of modulus [closed]

How can I evaluate the minimum of
$$
\left|7x-1\right|+\left|7y-5\right|+\left|7z-1\right|
$$
if $x,y,z$ are non negative reals such that $
x+y+z=1$ and $y^2 \le xz$?
Is there a standard way to ...

**3**

votes

**1**answer

111 views

### Global minimum of nonlinear least square

We have a continuous and differentiable function $f(\cdot)$ that maps from $R^n$ to $R^n$. We are trying to solve a nonlinear least square problem:
Minimize $J(x)=\Vert f(x)-z\Vert^2$
subject to box ...

**1**

vote

**1**answer

43 views

### On optimizing a function whose projection and projected vector go through a linear transformation

Assume the two sets of vectors $\{\mathbf{a}_1,\ldots,\mathbf{a}_N\}$ and $\{\mathbf{b}_1,\ldots,\mathbf{b}_N\}$ of equal length. My goal is to find the optimum matrix $\mathbf{C}$ to the following ...

**0**

votes

**0**answers

36 views

### Bounds on the curvature of a sequence of convex functions

Let $\{f_n\}$ be a sequence of (real-valued) smooth convex functions on $[0,1]$, with $f_n(0) = f_n(1) = 0$ for all $n$.
Let $t_n \in [0,1]$ be the minimizer of $f_n$ and assume that $M_n:= f_n(t_n) ...

**-1**

votes

**1**answer

51 views

### Does element-wise concavity guarantee joint concavity?

I have a function of two variables, and I have checked that along one direction (fixing another variable), it is a monotonically increasing and concave function. Whereas in another direction (fixing ...

**10**

votes

**2**answers

284 views

### More general than semidefinite program?

I was TAing 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. My question ...

**0**

votes

**1**answer

100 views

### Is the linear production game a convex game?

In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem.
Does anyone know if the LPG is a convex ...

**0**

votes

**0**answers

45 views

### Find optimal value for a regularization parameter in generalized eigenvalue problem

Consider the generalized eigenvalue problem :
$ \Sigma_{XY} \Sigma_{YX} {W} = \lambda \Sigma_{XX} {W} $
where $\Sigma_{XX} $ and $\Sigma_{XY}$ are sample covariance matrices are of the matrices ...

**0**

votes

**0**answers

42 views

### Nuclear norm maximization

I am trying to solve a nuclear norm maximization problem:
$$\arg \max_{Q \in O(n)} \|WQV^T\|_*$$
where $Q$ is an $n \times n$ orthogonal matrix and $W$ and $V$ are real $d \times n$ matrices. I've ...

**2**

votes

**1**answer

249 views

### Is this a log-concave function?

Let $(a_k)$ be a log-concave positive decreasing sequence. Is $\sum\limits_{k=1}^n a_k(1-e^x)^{k-1}$ log-concave in $x<0$, for each natural $n$?

**1**

vote

**1**answer

90 views

### A bound on the number of bilinear functions needed in order to obtain the minmax

For $n\in\mathbb N$, let $\Delta(n)=\{x\in\mathbb R^n:x_i\geq 0, \sum_ix_i=1\}$ be the set of probability vectors in $\mathbb R^n$.
Is there a function $m:\mathbb N\to\mathbb N$ such that for any ...

**0**

votes

**0**answers

20 views

### Bounding the error of the optimal solution from an approximated objective

Let $f$ be a smooth convex function defined in a bounded region $X$ and its Hessian is bounded $m I \le |\frac{\partial^2 f(x)}{\partial x^2}| \le M I$ for some $M>m>0$. Let $x^*=argmin_{x\in X} ...

**0**

votes

**0**answers

46 views

### Question on solving an optimization problem using Variable splitting and ADMM

Tell me if I have found the right approach to the following optimization problem:
$$
min_{x} \frac{1}{2}\left \| Ax-b \right \|_2^2
\\
s.t. \ \ \Phi v=x \ , \ {x^T(1-x)}=0
$$
$A$ and $\Phi$ ...

**1**

vote

**1**answer

73 views

### Envelope theorem for second derivative

I am maximizing a function $f(x,z)$ on $x$ ($z$ is treated a parameter in the maximization). The function $f$ is strictly concave on both variables.
I know how to use the envelope theorem for the ...

**1**

vote

**0**answers

34 views

### Is this QCQP convex or nonconvex

\begin{equation}
\begin{split}
\min_{x\in \mathbb{R}^n}\:f(x)=(1/2)x^{T}Q_0x+c_0^T x
\end{split}
\end{equation}
s.t.
$$
g_i(x)=\frac{1}{2}x^T Q_ix-lmax_i\leq0,i\in\{1,...,m/2\}
$$
$$
...

**1**

vote

**0**answers

72 views

### Projecting on a a special polyhedron

Let $X$ be an $n$-by-$p$ matrix and consider the closed convex polyhedron
$$\mathcal P_X := \{y \in \mathbb R^n | \|X^Ty\|_\infty \le 1\}.$$
Notice that $\mathcal P_X$ is symmetric about the origin.
...

**1**

vote

**0**answers

41 views

### Projecting on a convex compact polytope with special form

Let $E$ be a large sparse $l$-by-$n$ matrix ($l$ and $n$ can be in the billions...) with coefficients in $\{-1, 0, 1\}$: the first row of $E$ is the vector $(1,0,0,\ldots,0) \in \mathbb R^n$, and ...

**5**

votes

**1**answer

265 views

### Minimize Frobenius norm

My question is the following:
Suppose $M$ is an $n \times n$ symmetric real matrix. I want to find an $n \times n$ symmetric real matrix X such that $|| X -M||_F$ is minimized with the constraint ...

**1**

vote

**0**answers

36 views

### convergence of unconstrained convex optimization

I encounter an optimization problem. The simplified version is like following:
Denote function $F(x):\mathbf{R}^n\rightarrow\mathbf{R}$, where $F(x)$ is a smooth lower bounded convex function (i.e. ...

**1**

vote

**2**answers

63 views

### Sensitivity analysis in minimum norm problems under a linear constraint

Suppose $\Delta$ is some nice topological space, say compact, and Hausdorff.
Let $A:\Delta \rightarrow \mathbb{R}^{m\times n}$ be a continuous $m\times n$ matrix valued map. Let $b\in \mathbb{R}^{m}$ ...

**1**

vote

**0**answers

46 views

### Derivatives of Minkowski function?

Let $A\subset \mathbb R^n$ and $M$ be the convex hull of the set $A$, e.g., $M:=Conv(A)$. The Minkowski function on $M$ is defined as follows
\begin{align*}
&f: \mathbb R^n \to \mathbb R\\
...

**0**

votes

**0**answers

60 views

### Well-posedness of gradient flows

For a convex lower-semicontinuous functional on a Hilbert space $I\colon H\rightarrow\mathbb{R}$, it is shown in Evans' PDE that the Hilbert-space-valued ODE
$$\begin{cases}\mathbf{u}'(t)\in-\partial ...

**11**

votes

**1**answer

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

**-1**

votes

**1**answer

58 views

### Convex Optimization in an Ellipsoid

Suppose we want to minimize a linear objective inside an ellipsoid that is,
$\min _x l^Tx$
such that $(x - \mu)^TA(x - \mu) \leq \beta ^2$.
Here, A is PSD and $\mu$ is a fixed vector. Can this be ...

**0**

votes

**0**answers

22 views

### Maximizing modular function subject to supermodular constaint

I'm trying to solve a constrained optimization problem with submodular functions and get some nice properties of the solution. Unfortunately, I think I am in a setting where Topkis' theorem does not ...

**3**

votes

**1**answer

104 views

### Finding a semigroup that maximizes the trace of a sum of matrices

Let $H$ be a finite semigroup containing $n$ elements from a compact group $G$. I am trying to solve
$$\max_{h_i,\ h_j\ \in\ H} \operatorname{tr} \sum_{i,\ j\ \leq\ n} \rho(h_i^{-1} h_j)(A_j ...

**0**

votes

**0**answers

47 views

### How to use the property of Frobenius norm in this proof?

Let $A \in \mathcal{S}^{n}$($\mathcal{S}^{n}$ is the $n \times n$ symmetric matrix space), $P,Q \in\mathbb R^{n \times n}$, and $\rho \geq 0$ be given. Show that:
$$A \succeq P^{T}ZQ+Q^{T}Z^{T}P$$
for ...

**3**

votes

**1**answer

132 views

### Computational complexity of low rank SDP

Suppose we are given a general SDP of the form with an additinal rank requirement
\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\ \text{subject ...

**0**

votes

**1**answer

232 views

### L-infinity-norm regularized proximity problem

I have a question:
$$\min_x {1\over 2} \|x-t\|^2 + \lambda \|x\|_\infty$$
where $t, \lambda$ are given constant.
I think this may be a classic problem? However, I didn't find closed form of its ...

**1**

vote

**0**answers

55 views

### Log convexity for the norm of a vector-valued function

Log convexity of various functions defined on the space of Hermitian matrices plays an important role in matrix analysis and probability theory.
Given $v \in \mathbb{C}^n$, $D$ a diagonal matrix with ...

**4**

votes

**2**answers

94 views

### Questions concerning convergence rate of Iterated Projections

Assume for simplicity $C_1,C_2,...,C_n\subset \mathbb{R}^m$ to be closed and convex subsets with $\underset{i=1}{\overset{n}{\bigcap{}}}C_i\neq\emptyset$.
Let $x^0\in\mathbb{R}^n$ and define the ...

**2**

votes

**0**answers

34 views

### Constrained absolute orientation of 3D point sets

Let us assume we have two 3D point sets, $P=\{p_i\}$ and $Q=\{q_i\}$, and that we need to recover the transformation that takes $P$ as close to $Q$ as possible. In particular, I am interested in ...

**0**

votes

**1**answer

56 views

### How to compute the direction of slowest ascent from the minimum of a strongly convex function?

Consider a twice differentiable strongly convex function $f:\mathbb{R}^n \rightarrow \mathbb{R^+}$ that attains its minimum value at the point $x^*$. I am wondering if one can compute a direction of ...

**2**

votes

**0**answers

79 views

### About optimizing a convex function on a hypercube

Given a real valued convex function $g$ on $[-1,1]^n$, let $f$ be the restriction of it on the hypercube $\{-1,1\}^n$. I want to find a vertex on the hypercube $\{-1,1\}^n$ on which either (1) $f$ ...

**5**

votes

**0**answers

72 views

### Basin of Attraction

I have a function $F$ which is defined as follows:
$$
F(x) = \sum_{i=1}^N f(z_i^T x)
$$
where ${z_i}$ are known $m \times 1$ vectors, $x$ is an $m \times 1$ vector, and for $t\in \mathbb{R}$, $f(t) = ...