**2**

votes

**1**answer

87 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\{ ...

**2**

votes

**1**answer

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

**2**

votes

**0**answers

76 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

89 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

**0**answers

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

**3**

votes

**1**answer

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

**3**

votes

**2**answers

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

**1**

vote

**1**answer

55 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

115 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

61 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

**1**answer

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

**1**

vote

**0**answers

73 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

62 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

88 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

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

**5**

votes

**0**answers

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

**1**

vote

**0**answers

67 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

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

**8**

votes

**3**answers

308 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

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

**0**

votes

**0**answers

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

**1**

vote

**1**answer

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

**0**

votes

**1**answer

70 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

90 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

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

**0**

votes

**2**answers

126 views

### Does removing some constraints in convex program change the optimal solution? [closed]

Suppose I have a convex program which has only two variables, the objective function is strictly convex, and the constraints are linear functions.
I think removing all non-tight constraints doesn't ...

**1**

vote

**1**answer

95 views

### An optimization problem in complex space

Consider the following optimization problem
$$
\min \| \textbf{Ax-B}\|
$$
$$
s.t.|x_i|=1,i=1,...,n
$$
where $\textbf{x}\in \mathbb{C}^{n}$ is the optimization varaible, $x_i$ is the $i$-th ...

**5**

votes

**1**answer

284 views

### Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...

**1**

vote

**0**answers

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

**0**

votes

**1**answer

62 views

### Finding maximum of a function with unfixed number of variables

Can anybody solve this:
For a constant positive integer $n\geq6$
find $k$ and positive integers $a_{1},a_{2},...,a_{k}$
that maximize the expression
...

**17**

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

**0**

votes

**1**answer

171 views

### Matrix equation

Let $A$ be $k\times n$ matrix i.e., $A=(a_{1},\ldots, a_{n})$ where $a_{j} \in \mathbb{R}^{k}$, $rank(A)=k$ and $1\leq k \leq n$. Let $q=(q_{1},\ldots, q_{n})\in\mathbb{R}^{n}$ be such that ...

**2**

votes

**1**answer

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

**8**

votes

**2**answers

251 views

### Removing constraints in convex optimization

Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and ...

**1**

vote

**0**answers

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

**3**

votes

**0**answers

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

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

**-3**

votes

**1**answer

85 views

### Convert constraint to do convex optimization or use Lagrange multiplier method [closed]

$w_1, w_2, w_3 ... w_n$ are the weights I need to find
I have the following constraint:
$|w_1| + |w_2| + .. |w_n| <= 5$
That is the sum of the absolute values of the weights has to be less than ...

**3**

votes

**1**answer

435 views

### Linearly constrained eigenvalue problem

Suppose I'd like to:
\begin{align}
\mathop{\text{min}}_\mathbf{x} && \mathbf{x}^T\mathbf{A}\mathbf{x} \\
\text{subject to:} && \mathbf{x}^T \mathbf{M} \mathbf{x} = 1\\
&& ...

**4**

votes

**2**answers

315 views

### Convex Sets and Nearest Neighbors

For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is uniquely determined. It is known that ...

**3**

votes

**1**answer

106 views

### Can one always find sparse solutions to an $\ell^1$-minimization problem?

Consider $A\in\mathbb{R}^{m \times N}$ and $b \in \mathbb{R}^m$, with $m<N$. Is it true that the optimization problem
$$\min \|x\|_1 \quad s.t. \;\; A x = b,$$
admits an $m$-sparse solution in ...

**7**

votes

**3**answers

387 views

### The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?
More ...

**1**

vote

**2**answers

127 views

### investigating positivity/negativity of a function [closed]

I'm investigating if and how the positivity or negativity of a multivariable function can be proved. Consider $y_{1},y_{2},y_{3}\in\mathbb{R}$ and the following function
...

**3**

votes

**1**answer

128 views

### A difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$.
(Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...

**1**

vote

**2**answers

139 views

### The set of matrices with same spectral radius

I am working on an optimization problem over the set of positive matrices (that is, matrices where all entries are positive numbers) that have the same spectral radius. My main problem is how to ...

**3**

votes

**1**answer

295 views

### Multiplicative gradient descent?

The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$?
I know ...

**3**

votes

**1**answer

182 views

### Linear dependency of real numbers with integer coefficients adding up to zero [closed]

Let $x = (x_1, \dots, x_n)$ be a vector of real number. I was asking myself if there was an efficient way of telling whether there exists a non-zero vector of integers $z \in \mathbb Z$ such that both
...

**1**

vote

**0**answers

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

**2**

votes

**0**answers

337 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

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