**3**

votes

**1**answer

76 views

### How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?

This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...

**1**

vote

**1**answer

240 views

### optimization of inverse matrix with constraint on matrix elements

everyone! I have this optimization problem with constraint.
$D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter.
$x$ and $v$ are two known p-dimensional vectors.
The ...

**2**

votes

**1**answer

156 views

### How can I find the maximum value of this function?

For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of:
$$
\max_{x \in [0,1]^n} \|Ax+b \|_1
$$
Or is this problem NP-hard?

**0**

votes

**1**answer

197 views

### Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).
The cost to send $x$ unit of flow through edge $e_i$ is defined ...

**-3**

votes

**0**answers

31 views

### How to find positive-definite matrices $Q$ and $W$ satisfying $x^T Q x \leq \xi^T W \xi<1$? [on hold]

Recently, I encounter a problem, that is,
how to find positive-definite matrices $Q\in R^{n\times n}$ and $W\in R^{n\times n}$ satisfying $x^T Q x \leq \xi^T W \xi<1$? where $x\in R^{n\times 1}$ ...

**3**

votes

**1**answer

54 views

### Convex optimization with full subdifferential information

Can anyone direct me to any algorithms or theorems that describe the difficulty of solving a non-smooth convex optimization problem for the special case where the full subdifferential is available? ...

**0**

votes

**1**answer

300 views

### Find the following transformation $G$

I asked this question 6 days ago on math.stackexchange.com (http://math.stackexchange.com/questions/656585/find-the-following-transformation-g). I didn't get any answers yet, so I'm posting here.
I'm ...

**2**

votes

**1**answer

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

**1**

vote

**0**answers

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

**0**

votes

**0**answers

41 views

### Signs and value of higher order terms in the Taylor expansion of a strongly convex function

Say that I have a function $f: S \rightarrow \mathbb{R}^+$ such that:
$S \subset \mathbb{R}^n$ is a closed convex set such as $S=[-10,10]^n$
$f$ is continuous and infinitely differentiable at all ...

**1**

vote

**1**answer

42 views

### Nonlinear least square with quadratic equality constraint

I am looking for an appropriate method or hint to solve the following constrained nonlinear least square problem:
$\operatorname{argmin}_X \sum_{i\in I} \|\mathbf{X}_i - \mathbf{X}_{i+1}\|_2^2 + ...

**2**

votes

**2**answers

283 views

### Can one estimate the distribution of eigenvalues of a matrix by its Cauchy/Stieltje transform?

Given a real symmetric $n$ dimensional matrix $A$, with eigenvalues $\lambda_i$ I am defining its Cauchy transform as the function, $f_A(z) = \sum_i \frac{1}{z-\lambda_i}\,$
Is there any information ...

**0**

votes

**1**answer

107 views

### Is there any way to compare between diagonals of a resolvent and a Cauchy transform?

Say $A$ is a symmetric matrix of $n$ dimensions. Then let the ``resolvent" of $A$ be the matrix valued function $R_A(z) = \frac{1}{z-A}$ and its Cauchy transform be the real valued function $C_A(z) = ...

**3**

votes

**2**answers

135 views

### Constructing a quasiconvex function [closed]

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called
convex if
$$
f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, ...

**0**

votes

**1**answer

104 views

### polynomial expression for counting number of integral points of a set

Let $v_i=a_ie_i\in\mathbb R^d$ and $w_i=b_ie_i\in\mathbb R^d$ for $i=1,\dots,d$ where $e_i$'s are unit vetcors and $a_i,b_i$ are positive integers. Let $$S=conv\{0,rv_i+sw_i:i=1,\dots,d\}.$$
Can we ...

**3**

votes

**1**answer

115 views

### Condition number after preconditioning

Suppose $A$ and $P$ are symmetric, positive definite matrices and that we factor $P^{-1}=EE^\top.$ Is it true that the condition number of $PA$ is upper-bounded by the condition number of ...

**2**

votes

**1**answer

118 views

### Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?

Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$.
But do we have any quantitative ...

**6**

votes

**2**answers

202 views

### What methods do we have to understand the spectrum of matrices with restricted entries?

Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"),
What is the largest possible spectral radius of a $n \times n$ matrix ...

**5**

votes

**2**answers

256 views

### Minimum of squared sum minus sum of squares

I know that
$$
\min_{\|x\|_2=1=\|y\|_2} \left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2 \geq -1/2
$$
with equality whenever $|x_k|=\frac{1}{\sqrt{2}}=|y_k|$ for two coordinates.
I'm ...

**2**

votes

**1**answer

74 views

### Rate of convergence for cyclic gradient descent

I'm trying to solve the optimization problem
$\min_x \frac{1}{n} \sum_{i=1}^n f_i(x)$
where $f_i$ are (strongly) convex, smooth, lower semi-continuous, etc.
However, I am not able to do conventional ...

**0**

votes

**0**answers

25 views

### Practical bundle methods

What is the most widely applied bundle method currently available? I am trying to solve a large convex optimization as accurate as possible with dimension being roughly 5000+.... Thank you.

**2**

votes

**1**answer

55 views

### smooth minimization of piecewise linear convex function

Is it possible to apply Nesterov's smooth minimization of non smooth function on a problem of the form
$$\mathop {\min }\limits_{\lambda \in {R^m}} \mathop {\max }\limits_{\sigma \in {{\left\{ ...

**5**

votes

**0**answers

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

**2**

votes

**1**answer

51 views

### When is a convex program continuous in its constraint vectors?

Consider $$F(z)=\min ae^{-x}+b e^{-y} s.t. x\ge 0, y\ge 0\text{ and } x+y=z$$
I checked if this function is continuous, but it is not at $z=0$. $F(z)=2\sqrt{ab}e^{-z/2}$ when $z\ne 0$, and ...

**1**

vote

**1**answer

70 views

### Nested convex optimization

Suppose I have a convex optimization problem of the form $$\min_x f(x) ~~s.t.\\x\in X$$. Say that $f(x)$ and its (sub)gradient are not given in a closed form, but are determined by solving a convex ...

**2**

votes

**0**answers

58 views

### l1 Quadratic Programming [closed]

Within a SQP- algorithm it can happen that the constraints of the quadratic sub- problems are infeasible. In order to overcome this infeasibilities, a l1 penalty method can be used according to ...

**2**

votes

**1**answer

84 views

### Functions that are easy to compare to a norm

Let $X$ be a subset of $\mathbb{R}^d$, let $\|\cdot \|_p$ be a norm with $1\leq p\leq\infty$, and let $f:\mathbb{R}^d\to\mathbb{R}$ be a function. I'm trying to find examples of $X$, $p$, and $f$ for ...

**1**

vote

**1**answer

159 views

### No Strong Duality In Spite of Slater's Condition

I was reading some course notes here.
On Page 8, it says:
Note that strong duality holds here (Slater's condition), but the
optimal value of the last problem is not necessarily the optimal
...

**0**

votes

**0**answers

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

**4**

votes

**2**answers

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

**3**

votes

**1**answer

77 views

### generalized mean inequality extension

from generalized inequality, we now that for $p>q$, we have $M_p(\mathbf{x})\ge M_q(\mathbf{x})$. now I am curious to know if we can find a constant $\alpha(p,q)$ which is only function of $p,q$ ...

**1**

vote

**1**answer

46 views

### monotonicity alike functions

assuming we have two smooth function ${f_1},{f_2}:{R^N} \to R$,
under what condition, we have
${f_1}\left( {{{\bf{x}}_1}} \right) \ge {f_1}\left( {{{\bf{x}}_2}} \right) \leftrightarrow ...

**0**

votes

**0**answers

96 views

### Hadamard / matrix product adjoint

First of all I would like to thank everyone over here at mathoverflow for their amazing generosity and help (for both pros and newbies like myself).
I apologize if this question seems dumb; I'm a new ...

**1**

vote

**0**answers

46 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

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

**5**

votes

**0**answers

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

**4**

votes

**1**answer

74 views

### Analysis of first-order methods for constrained convex optimization with approximate oracles

In many first-order optimization methods an oracle is needed whose action enforces the constraint/regularizations. For example, in projected gradient descent, conditional gradient method, and proximal ...

**4**

votes

**1**answer

101 views

### Maximizing Frobenius Norm of Commutator (an opposite Procrustes problem)

I was wondering if anybody has any suggestions on the following problem:
Let $S$ be an $n\times n$ positive definite symmetric matrix. I wish to find an $n\times n$ orthogonal matrix $R$ which ...

**1**

vote

**1**answer

85 views

### What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely,
$X \in ...

**16**

votes

**8**answers

1k views

### When do people actually use the maximum entropy distribution?

One of the standard problems in convex optimization is the calculation of the maximum entropy distribution that satisfies some set of criteria. For example, if $\mathbf{x} \in \mathbb R^n$ is an ...

**1**

vote

**0**answers

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

**2**

votes

**0**answers

68 views

### How to solve the following generalized quadratic programming problem [closed]

I want to solve a generalized form of a quadratic programming problem
$$\min_x \left(\sqrt{x^TPx}+\sqrt{x^TQx}\right)^2+c^Tx$$,
$$\textrm{ s.t. } Ax\le b.$$ Here, $P$ and $Q$ are both positive ...

**0**

votes

**0**answers

38 views

### Least square problems with binary variables

I want to solve the heat equation $T_t(x,t) = - L_x . T(x,t) + F(x,t)$ in an edge-weighted graph where $L_x = \sum_i x_i e_{ij}$ is weighted Laplacian matrix of the graph. Then I conclude to the ...

**8**

votes

**3**answers

291 views

### Lower bound for spectral radius on $\operatorname{GL}(n,\mathbb{Z})$

Consider the group of matrices $G =\operatorname{GL}(n,\mathbb{Z})$ with integer entries and determinant $\pm 1$. For each matrix $D \in G$, the product of the eigenvalues of $D$ is equal to $\det D ...

**6**

votes

**0**answers

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

**2**

votes

**1**answer

95 views

### Fastest 'Oracle' Algorithm for satisfying a single linear constraint on a convex set?

In this paper by Arora, Hazan, and Kale (http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf) a method is given for using the Multiplicative Weights Update algorithm to quickly solve Linear Programs ...

**0**

votes

**1**answer

52 views

### accelerate convex optimization by proximal projection

I am using level method to solve non-smooth convex programming problem (where the objective function is given by an oracle from another program ):
http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf
...

**1**

vote

**0**answers

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

**4**

votes

**0**answers

111 views

### Two quadratic programming problems always same answer? [closed]

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal.
Problem 1:
Minimize $\tfrac{1}{2} \mathbf{x}^T Q\mathbf{x}$
Subject to $ A ...

**2**

votes

**1**answer

168 views

### Necessary conditions for optimality in Banach spaces

Let $X$ denote the non-negative "orthant" of the Banach space $L^2$ (or whatever you call the set of functions in $L^2$ that are non-negative), and let $C$ be a closed, convex subset of $X$. Let $f$ ...