**0**

votes

**0**answers

14 views

### Are there examples of functions with Nesterov's convergence bound between convex quadratic and strongly convex cases?

Are there examples of simple and strongly convex functions for which the convergence bound of Nesterov’s Accelerated Gradient Method is better than Nesterov’s bound for strongly convex case ($\sqrt{1 -...

**-1**

votes

**1**answer

46 views

### About the critical points of quasi-convex functions

What do we know about the structure of critical points of quasi-convex functions?
I am looking for statements like "the critical points of a quasi-convex function are always either a global minima ...

**-1**

votes

**0**answers

24 views

### Multi-objective optimization for large matrices

I have a large matrix 102400 x 600 to optimize for two different criteria (maximum likelihood over a large dataset and another more complicated one). In practice, it represents a factors loading ...

**0**

votes

**0**answers

14 views

### Under which conditions discretization of convex\concave function is submodular?

Say, I have $f(x)$ with $x \in [0,1]$, then by discretization I mean $f(x_h)$ with $x_h \in \{0, h, 2h, \dots, 1\}$.
I know about Lovasz extension, but it works in other way: given discrete function ...

**1**

vote

**0**answers

27 views

### About a particular definition of a Hessian of a function of tuples of matrices

Say I have a function $L : (W_1,..,W_{H+1}) \rightarrow \mathbb{R}$ i.e it takes a tuple of $n$ matrices of different dimensions and computes a number from them.
Then I see being defined a ...

**5**

votes

**1**answer

79 views

### Complexity for solving linear equations?

What is the best known complexity for finding a vector $x \in \mathbb{R}^n$ to minimize $||Ax - b||^2$ and/or to solve (when possible) the system of linear equations $Ax=b$?
I am interested in ...

**1**

vote

**0**answers

39 views

### Nesterov's Methods for minimizing composite functions

There are some methods originally from Nesterov, which accelerates optimization methods, e.g. Nesterov 1983, Nesterov 2003, Nesterov 2005 ( smooth minimization of non-smooth functions), Nesterov 2013 (...

**0**

votes

**0**answers

38 views

### optimize a Quadratic Matrix Programming with multi-spherical constraints

I have got the following quadratic problem restricted on the Cartesian product of Euclidean spheres.
$\underset{X \in \mathbb{R}^{n\times 3}}{\text{min}}$ $Q(X) = \frac{1}{2} Tr(X^TA X) + Tr(B^T X)$
...

**1**

vote

**0**answers

31 views

### Practical application of envelope theorem for linear programs

Assume that we have solved a (standard) linear program
$$
\text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0,
$$
and would like to know how sensitive is the optimal ...

**0**

votes

**1**answer

29 views

### Limits of argmin ratios and sums

In my research on convergence properties of certain Bayesian methods I have encountered $\mathop{\mathrm{arg\,min}}$ limits of the forms
\begin{equation}
\lim_{n\to\infty} \mathop{\mathrm{arg\,min}}_{\...

**1**

vote

**0**answers

38 views

### Minimization over function space [closed]

This is the first time I encounter a problem where I need to minimize a function defined in a function space. Define the function space $A=\{\theta:\mathbb{R}^3 \rightarrow\mathbb{R}|\ \theta\ \text{...

**1**

vote

**0**answers

27 views

### Can the extragradient method be computed only based on proximal steps?

As we know, for solving saddle point problems, the forward-backward algorithm is generally not guaranteed to converge. But the extragradient method converges Structured Prediction via the ...

**0**

votes

**0**answers

65 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.
$\min\hspace{1mm}\max\hspace{1mm}\left\{\frac{\sigma_1}{c_1-...

**0**

votes

**0**answers

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

**1**

vote

**0**answers

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

**0**

votes

**0**answers

33 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 ($g(w;x):\...

**0**

votes

**0**answers

17 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

25 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

30 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

79 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

78 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 or ...

**4**

votes

**0**answers

137 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

33 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

136 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

45 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

37 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

291 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

101 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

46 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 $X$...

**0**

votes

**0**answers

45 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

252 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

104 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

21 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

50 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

86 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

41 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\}
$$
$$
g_i(x)=\frac{...

**1**

vote

**0**answers

73 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

45 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

305 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

39 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

66 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

51 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\\
&f(...

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

**14**

votes

**1**answer

377 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

65 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

23 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 A_i^T)$$...