**0**

votes

**0**answers

18 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

23 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

17 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

62 views

### Designing Better “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

**1**answer

63 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

129 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

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

**2**

votes

**1**answer

104 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

35 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

48 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

280 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

43 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

36 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

246 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

85 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

45 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

61 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

33 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

39 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

221 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

35 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

45 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

59 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

304 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

57 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

46 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

128 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

199 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

54 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

93 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

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

**2**

votes

**1**answer

120 views

### Minimizing a convex integral function

Consider the following constrained optimization with the integral objective function
$$
\min_{x_i\in D} \int_{t_1}^{t_2} \frac 1 {t - \sum\limits_{i = 1}^N x_i f_i (t)} \, dt
$$
where $t - ...

**4**

votes

**0**answers

45 views

### How does one go from convexity to submodularity?

If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular?
It would be helpful is someone can share some specific ...

**2**

votes

**1**answer

56 views

### Bounding the difference in the value of a strongly convex function at its integer minimum and other integer points

I am currently working on a problem where I have to minimize a $m$-strongly convex function
$$f ~: ~\mathbb{R}^n \rightarrow \mathbb{R}^+$$
over a bounded integer lattice,
$$L = \mathbb{Z}^n \cap ...

**5**

votes

**2**answers

111 views

### convert a special case of nonlinear fractional programming into a convex problem

Is it possible to convert a fractional problem (maximization) with objective function equal to the ratio of a concave function and convex function ? This question sound impossible but I have read this ...

**0**

votes

**2**answers

131 views

### Estimating the shift in the $\lambda_{max}$ of a matrix under a diagonal perturbation

Given a matrix $A$ and a diagonal matrix $D$, what ways do we have to estimate, $\lambda_{max}(A+D) - \lambda_{max}(A)$? (Feel free to make other assumptions about the matrices that they are all ...

**4**

votes

**0**answers

104 views

### An inequality from the “Interlacing-1” paper

This question is in reference to this paper, http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf (or its arxiv version, http://arxiv.org/abs/1304.4132)
For the argument to ...

**2**

votes

**0**answers

34 views

### About the partial expectation polynomials in the Interlacing-I paper and perfect matchings

I am thinking of the polynomials $f_{s_1,s_2,..,s_k}$ as in the definition 4.3 in this paper http://annals.math.princeton.edu/wp-content/uploads/annals-v182-n1-p07-p.pdf
In the use of these ...

**0**

votes

**1**answer

119 views

### sum of fractional functions optimization problem

Consider the following sum of fractional functions optimization problem
$$
\begin{array}{l}
\mathop {\min }\limits_{\bf{x}} \,\,\,\sum\limits_{i = 1}^p {\frac{1}{{{\bf{a}}_i^T{\bf{x}} + {b_i}}}} \\
...

**3**

votes

**2**answers

119 views

### Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed]

I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ...