**6**

votes

**0**answers

118 views

### A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...

**6**

votes

**0**answers

162 views

### Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently

Hi,
my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$.
The matrix $C$ is huge ($n$ up to a ...

**5**

votes

**0**answers

76 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) = \...

**5**

votes

**0**answers

68 views

### Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...

**5**

votes

**0**answers

178 views

### Characterizing matrices with rank constraint

Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times ...

**5**

votes

**0**answers

450 views

### An intuition for three different types of subgradients (proximal, regular, limiting)

I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking.
These subgradients are (assume $x \in$ ...

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

**0**answers

136 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 & \...

**4**

votes

**0**answers

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

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

**4**

votes

**0**answers

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

286 views

### Maximizing sum of matrices

Over the last few months, I've been trying to find the solution to a research-related problem I'm having. However, my research is not in mathematics, and my progress toward reaching a solution has ...

**3**

votes

**0**answers

118 views

### This function looks quasiconvex, can't understand why

Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by $$g(\mathbf{y}):=\max_{\mathbf{x}\in\...

**3**

votes

**0**answers

520 views

### Coordinate mirror descent

Let $f$ be a jointly convex function of 2 variables say $x,y$. I am interested in solving the optimization problem $$\min_{x,y\in\Delta} f(x,y)$$ where $\Delta$ is a $d$ dimensional simplex. An ...

**2**

votes

**0**answers

35 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 roto-...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

212 views

### Reference request: functional analysis results used in Taubes paper (1980)

I am studying Taubes paper 'Arbitrary N-vortex solutions to the first order Ginzburg-Landau equations'. I am looking for a reference of three following theorems:
Let $f(x)$ be a convex funtional ...

**2**

votes

**0**answers

339 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

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

174 views

### Quadratic optimization with parameter in constraint

Disclaimer: I posted the same question on math.stackexchange. However, the FAQ suggests to post research-level questions in this forum.
Question: Given a function $q: \mathbb R^{N\times N}\mapsto \...

**1**

vote

**0**answers

23 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 (...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

39 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+ \...

**1**

vote

**0**answers

29 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

40 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

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

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

**0**answers

50 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(...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

68 views

### Finding all feasible solutions

Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...

**1**

vote

**0**answers

60 views

### Finding optimal linear transformation for intersection of convex polytopes

I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue)...

**1**

vote

**0**answers

37 views

### Condition for maximizer of convex combination to be expansion mapping

I have $\Pi_n:\mathbb R^{n+1}\rightarrow \mathbb R$ and $F_n:\mathbb R^2\rightarrow \mathbb R$ with $$F_n(x,a)=\Pi_n(x,...,x,a)$$
$$f_n(x)=\operatorname{ArgMax}_{a\in\mathbb R}\{F_n(x,a)\} $$
such ...

**1**

vote

**0**answers

59 views

### Characterization of the maximizer of a function based on a parameter's value

Consider a smooth, continuously differentiable, and jointly concave function $f(x,y,z;a)$, where $x,y$ and $z$ are decision variables and $a$ is a problem parameter.
I have two optimization problems. ...

**1**

vote

**0**answers

96 views

### On compactness in Sion's minimax theorem

Sions minimax theorem (wiki, paper) can be stated as follows:
Let $X$ be a compact convex subset of a linear topological space and $Y$ a convex
subset of a linear topological space. Let $f$ be a ...

**1**

vote

**0**answers

74 views

### A version of isotone projection cones

We write $a \succeq b$, where both $a, b \in \mathbb{R}^n$, as a shorthand for $a_i \ge b_i$ for all $1 \le i \le n$. Let $C$ be a closed convex cone in the first orthant of $\mathbb{R}^n$ and denote ...

**1**

vote

**0**answers

116 views

### Likelihood convexification

I am doing constrained vector optimization using a non-convex non-linear likelihood function. My problem is of the following form:
$$\begin{align*}\hat Q &= \underset{\vec Q}{\arg\min} -\log \...

**1**

vote

**0**answers

124 views

### Proximal mapping of composition with linear operator

Let $A$ be an orthogonal matrix. Then the proximal mapping $prox_{f \circ A}(x)$ can be evaluated efficiently by
$$
(I + \partial (f \circ A))^{-1}(x) = prox_{f \circ A}(x) = A^T prox_{f}(A x),
$$
as ...

**1**

vote

**0**answers

173 views

### Restricted strong convexity for biconvex functions

Recently, it has been shown (arxiv paper) that non-convex functions with the restricted strong convexity (RSC) property has the interesting property that their local minima lie within a small ball of ...

**1**

vote

**0**answers

139 views

### What is the purpose of the definition of “metric regularity”/“regularity modulus”?

A set mapping $F:X \rightrightarrows Y$ is said to be metrically regular for $\overline{x}\in X$ and $\overline{y} \in Y$ if there exists a $\kappa\in(0,\infty)$ for which
$$
d(x,F^{-1}(y))\leq \...

**1**

vote

**0**answers

50 views

### Is there a unique tilted measure with specified marginals?

Suppose $\mathcal{A},\mathcal{B}$ are finite sets and $\mu_{A,B}(a,b)$ is a probability measure on the product set $\mathcal{A}\times \mathcal{B}$ so that $\mu_{A,B}(a,b)>0$ for each $a\in \mathcal{...

**1**

vote

**0**answers

96 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

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

**1**

vote

**0**answers

57 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, ...

**1**

vote

**0**answers

131 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 &\...