Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes

**2**

votes

**1**answer

47 views

### Given the following two assumptions, How to conclude $\lim_{k \rightarrow \infty}|\nabla g_r(y^{k})|=0 \ $?

Please refer attached 6-page short paper for details.
Let $M(y)=y+2r\nabla g_r(y)$.
Given $\ g_r(M(y^k))>g_r(y^k)+r|\nabla g_r(y^k)|^2, \forall k. \ $ (equation 36 in the paper)
and $ \ \lim_{k ...

**0**

votes

**0**answers

18 views

### Projecting a polyhedral cone onto its intersection with the infinity-norm ball

For a point in a convex polyhedral cone, $x\in \mathcal{C} = \{\sum_{i=1}^m \alpha_i r_i \vert \alpha_i \geq 0, r_i \in \mathbb{R}^n \}$, is there an efficient algorithm to project $x$ onto the ...

**1**

vote

**0**answers

53 views

### Solve simple stochastic variational inequality

Let $Z$ be a random variable with finite mean $\mathbb E[Z]$ and let $\phi:(-\infty,\infty) \rightarrow (-\infty,\infty]$ be a convex l.s.c function which is differentiable at $z=1$ with gradient $\...

**0**

votes

**0**answers

19 views

### Dual representation of problems involving $f$-divergences

Studying some problems arising in decision-making under model uncertainty, I'm led to consider the following problems.
Let $\mathbb E_P$ and $\mathbb V_P$ denote the expectation and variance ...

**0**

votes

**0**answers

67 views

### How to understand the span of a matrix? [closed]

https://people.eecs.berkeley.edu/~brecht/cs294docs/week7/12.candes.recht.pdf
In the section 3.3 of the paper above, the author explains the span of matrices:
To apply our results to recovering low-...

**1**

vote

**1**answer

101 views

### How to solve this optimization problem efficiently?

Let, $D\in\mathbb{C}^{1\times M}$ is a row vector with $M$ elements
$V\in\mathbb{C}^{3^M\times M}$ is a given matrix
$T$ is a scalar (real and $>1$)
$\textbf{The problem at hand is as follows:}$
...

**3**

votes

**1**answer

59 views

### Echange of Infimum Integral with Pointwise Infimum

Setup
Suppose that $U$ is a subset of $L^{\infty}_{\mu}(\mathscr{F})\cap L^1_{\mu}(\mathscr{F})$ defined by
$$
f\in U \Leftrightarrow g(f(x))\leq M \mbox{ and } f \in L^{\infty}_{\mu}(\mathscr{F})\...

**2**

votes

**1**answer

99 views

### it's convex sequence inequality

Sequence of real numbers $a_0,a_1,\dots,a_{n}$ are called concave if for each $0<i<n$, $a_i\geq\dfrac{a_{i-1}+a_{i+1}}{2}$.$a_{0}=0$ Find the largest $c(n)$ such that for every concave sequence ...

**2**

votes

**1**answer

112 views

### Advantages of hyperbolic programming over semidefinite programming?

What are the advantages of a hyperbolic program over a semi definite program? SDPs can be used to represent a wide variety of algebraic constraints. Are there constraints that can be represented in a ...

**2**

votes

**0**answers

59 views

### convex approximation for a non convex function

Consider the function
$f\left( {{x_1},...,{x_M},{y_1},...,{y_N}} \right) = \left( {\sum\limits_{j = 1}^M {{\alpha _j}{x_j}} } \right)\left( {{e^{ - \sum\limits_{i = 1}^N {{\beta _i}{y_i}} }}} \right)$...

**2**

votes

**1**answer

86 views

### Convergence of a stochastic sequence?

I am reading this paper related to an algorithm for nonsmooth optimization problems. After many simplifications, I was able to formalize the method as follows: let $\Bbb B $ denote the unit ball in $\...

**0**

votes

**1**answer

52 views

### maximization of a log norm function

Considering the following optimization program:
$$
maximize \ \ \ \log \left( \|x\|_\infty \right)
$$
$$
subject \ to \ \ Ax\leq b, \ x \geq 0
$$
can we rewrite this program as a convex ...

**1**

vote

**1**answer

67 views

### LASSO problem but with a maximization instead of minimization

I have the following optimization problem (like the LASSO problem but with maximization instead of minimization):
$\mathbf{maximize}_{\boldsymbol{\alpha}} \|\mathbf{x} -\mathbf{A}\boldsymbol{\alpha}\|...

**0**

votes

**1**answer

47 views

### Quasiconvexity property of quasinorms

Schatten $p$ norm is convex when $p\geq1$ holds and if $p\in(0,1)$ it is quasinorm.
If $p\in(0,1)$ then is Schatten $p$ norm quasi convex? I am interested in definition of quasi convexity here https:...

**-1**

votes

**0**answers

10 views

### Convex Optimization - Derive Conjugate function [migrated]

I have been trying to solve this question and managed to prove subquestion (a). But I have no idea about proving the other two subquestions. Can anyone help?
Note:
The question is from Stephen Boyd'...

**3**

votes

**0**answers

24 views

### Level sets of strongly convex and smooth functions

Let $f: \mathbb{R}^N \to \mathbb{R}$ be a $\alpha$-strongly convex and $\beta$-strongly smooth function, i.e.,
$$ f(x) + \langle\nabla f(x), y- x\rangle + \frac{\alpha}{2}\|y-x\|^2
\leq f(y) \leq f(x) ...

**0**

votes

**0**answers

38 views

### optimizing convex piecewise linear function

What it the best way to optimize the following objective function?
$$ \min_{x \ge 0} \; c^T x + \sum_{i=1}^n \max(0, a_i^T x + b_i, \eta_i a_i^T x + b_i) $$
with $\eta_i \le 0$.
Since this function ...

**4**

votes

**2**answers

224 views

### Fast projection onto a subspace

Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{...

**1**

vote

**0**answers

34 views

### Minimum Preserving Transformations [closed]

If $f:X\rightarrow Y$, $g:Y\rightarrow Y$ are functions and $g$ is monotone increasing function then
$$
\operatorname{argmin}_{x \in X} f(x)
=
\operatorname{argmin}_{x \in X} g\circ f(x) .
$$
X and Y ...

**2**

votes

**1**answer

76 views

### Why the convexity condition on the definition of a face of a convex set?

A face of a closed convex set $X\subseteq\mathbb{R}^n$ is defined to be a set $F\subseteq X$ such that:
$F$ is convex.
Every line segment from $X$ whose interior meets $F$ is contained in $F$.
Is ...

**1**

vote

**2**answers

136 views

### Maximizing a function that is sum of gaussians

Let $\mathbf{x}_1,\dots,\mathbf{x}_n$ be given $n$ vectors in $\mathbb{R}^d$. Define the function
\begin{align}
\mathcal{K}(\mathbf{x},\mathbf{y})=
\alpha\exp(-\frac{||\mathbf{x}-\mathbf{y}||^2}{2\...

**4**

votes

**2**answers

119 views

### Is there any efficient solution of the matrix equation AXB + (AXB)' + cX = D

I am trying to find the symmetric solution $X\in \mathbb{R}^{p\times p}$ of following matrix equation:
$AXB + (AXB)^T + cX = D$
where $A,B\in \mathbb{R}^{p\times p}$ are symmetric positive ...

**9**

votes

**1**answer

318 views

### Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension

By KL divergence I mean $D(P||Q) = \int dP \log(\frac{dP}{dQ})$. I am looking for the conditions under which this strong convexity is true and possible references. I could not find an answer for ...

**0**

votes

**0**answers

62 views

### Iterative methods for minimizing sequences

Let $\mathbb{X}$ be a Banach space equipped with some norm $||\cdot||_\mathbb{X}$ and $F:\mathbb{X}\to\mathbb{R}$ be some linear functional. Suppose we are given a set $A\subseteq\mathbb{X}$ which is ...

**3**

votes

**0**answers

75 views

### Fenchel conjugate on a Hadamard manifold

Let $M$ be a Hadamard manifold and let $F:M\to\mathbb{R}$ be a real-valued convex function on $M$. What would be the Fenchel-Young conjugate of $F$?
In general for a real locally convex vector space $...

**3**

votes

**1**answer

186 views

### concavity of $\log [ (1+\frac{x_0}{1+x_0+x_1/2+x_2/4}) (1+\frac{x_1}{1+x_0/4+x_1+x_2/2}) (1+\frac{x_2}{1+x_0/2+x_1/4+x_2}) ]$

Let $f:~ [0,1]^3 \rightarrow \mathbb{R}$ be
$$
f(x_0,x_1,x_2)= \log \left[ \left(1+\frac{x_0}{1+x_0+\frac{x_1}{2}+\frac{x_2}{4}}\right) \left(1+\frac{x_1}{1+x_1+\frac{x_2}{2}+\frac{x_0}{4}}\right) \...

**4**

votes

**3**answers

141 views

### Quasi-concavity of $f(x)=\frac{1}{x+1} \int_0^x \log \left(1+\frac{1}{x+1+t} \right)~dt$

I want to prove that function
\begin{equation}
f(x)=\frac{1}{x+1} \int\limits_0^x \log \left(1+\frac{1}{x+1+t} \right)~dt
\end{equation}
is quasi-concave. One approach is to obtain the closed form ...

**1**

vote

**0**answers

36 views

### Lower semicontinuity of proximal gradient descent sequence

I'm using an alternate optimization scheme to minimize a function $F(a,b,c) = G(a,b,c) + H(c)$ where $G$ is continuous and differentiable, $H$ is not differentiable but lower semi-continuous and ...

**0**

votes

**1**answer

88 views

### Strict complementary slackness for semidefinite programs with strong duality

By a theorem of Goldman and Tucker it is known that if a linear program (LP) has a finite valued optimal solution, then there is an optimal primal/dual pair $(x,z)$ satisfying not only complementary ...

**3**

votes

**1**answer

102 views

### Strong polynomial algorithm for linear programming

What is the current state of finding a strong polynomial algorithm for linear programming? Is there any reference?

**2**

votes

**1**answer

110 views

### Quasi-concavity of $f(x)=(1-\frac{x}{1000})\log_2(1+2^x)$ on $[0~1000]$

I want to prove that function $f:[0~1000]\rightarrow R$, $$f(x)=(1-\frac{x}{1000})\log_2(1+2^x)$$ is quasi-concave. Any idea how to do the proof? I already tried to prove that any super-level set is ...

**3**

votes

**1**answer

277 views

### Minimize the variance of a Boltzmann distribution

N.B.: Sorry for cross-posting from https://stats.stackexchange.com/posts/347804/edit (I realized it was the wrong venue for the question, but couldn't find an easy way to transfer the question here).
...

**1**

vote

**0**answers

38 views

### Relative interior of a normal cone at a face of a convex polytope?

Suppose $A$ is a nonempty convex polytope in $\mathbb{R}^n$. Suppose $F$ is a face of $A$.
Consider the normal cone of $A$ at $F$:
$C_A(F)=\{v\in\mathbb{R}^n:v\cdot x\geq v\cdot y\ \forall\ x\in ...

**1**

vote

**1**answer

156 views

### Is this parametrized semidefinite program convex?

I am considering an optimization problem of the form:
\begin{equation}
\begin{split}
f(s) &= \min_{X} \mathrm{tr}(C(s)X) \\
&\;\;\;\;\;\;\;\;\;\;\; X \ge 0, \\
&\;\;\;\;\;\;\;\;\;\;\; \...

**0**

votes

**0**answers

44 views

### Is this set of polynomial constraints convex? Can I optimise it?

Basically I want to optimise a problem with a constraint on the (variable dependant) roots of a polynomial, which I would like to be assigned depending on other constraints.
I reduced the problem to ...

**0**

votes

**1**answer

46 views

### Linearly constrained saddle-point optimization

Let $f(x,y)$ be a smooth (twice differentiable) saddle function (convex in $x$ and concave in $y$), where $f \colon X \times Y \rightarrow \mathbb{R}$, and $X \subset \mathbb R^n$, $Y \subset \mathbb ...

**1**

vote

**1**answer

52 views

### Convex integer programming on totally unimodular polytope?

If
$$\min x'Qx + Rx$$
$$Ax\leq b$$
$$x\in\mathbb Z^n$$
is a quadratic program with $x'Qx$ is convex is there a polynomial time algorithm for this if $A$ is totally unimodular?
In particular if we ask ...

**0**

votes

**0**answers

54 views

### non-convex optimization with constraint

I have a special non-convex optimization problem:
$\min / \max \ f(x) + g(x) + h(x)$,
subject to $| g(x) - h(x)| < \varepsilon$,
where $f(x)$ is non-convex, but both $g(x)$ and $h(x)$ are ...

**1**

vote

**1**answer

98 views

### Maximizing mutual information between two linearly projected random variables

Consider continous random variable $X$ with bounded support $\mathcal{X} \subset \mathbb{R}$, discrete random variable $Y$ with finite support $\mathcal{Y}$ , and constants $c_1 ,c_2 \in \mathbb{R}$. ...

**2**

votes

**1**answer

46 views

### Linear program with one quadratic condition convex in domain of interest polynomial time solvable?

$c\leq xy$ is not a convex condition.
However we know $c\leq xy$ is convex in domain $x,y>0$ in $\mathbb R^2$ for any fixed $c\in\mathbb R$.
Is $c\leq x_1y_1+\dots+x_ny_n$ with $0\leq x_1,\dots,...

**0**

votes

**0**answers

45 views

### Optimization of generalized Fisher information over space of probability measures

Assume we already have $p(\theta)$ apriori desnsity function about unknown parameter $\theta$, and we consider an optimization problem as follows:
\begin{equation} \max_{P \in \mathcal{M}} \int_{\...

**0**

votes

**2**answers

146 views

### Lagrange Multipliers for two constraints, degenerate case

To optimize $f(x,y,z)$ subject to $g(x,y,z)=h(x,y,z)=0$, we use the Lagrange Multiplier method and solve
\begin{equation*}
\nabla f=\lambda \nabla g+\mu\nabla h,\quad g=0,\quad h=0.
\end{equation*}
...

**2**

votes

**1**answer

116 views

### Efficient algorithm for solving a convex quadratic program [duplicate]

Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently?
$$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$

**1**

vote

**0**answers

41 views

### Projecting two convex polyhedra onto their intersection

Suppose we are given two convex polyhedra $\mathcal{C}_1, \mathcal{C}_2 \subset \mathbb{R}^n$ with non-empty intersection $\mathcal{C}_1 \cap \mathcal{C}_2 \neq \emptyset$.
For the orthogonal ...

**11**

votes

**2**answers

310 views

### Convex hull of the Stiefel manifold with non-negativity constraints

Consider the Stiefel manifold
$$\mathrm{St}(n,k) :=\{X \in \mathbb{R}^{n\times k} : X^TX = I_k\},$$
where $I_k$ is the $k$-dimensional identity matrix. It is well known that
$$\mathrm{conv} \left( ...

**0**

votes

**0**answers

51 views

### Suggestions to solve an optimization problem that involves quadratic forms

I am in a crucial part of my research, I have arrived at an optimization problem that I can not solve, I need to solve it to be able to perform simulations and thus complete my research, due to this ...

**2**

votes

**1**answer

101 views

### Constructive version of Hilbert Projection Theorem

I am looking at the Hilbert Projection Theorem, which states that every non-empty closed convex set in a Hilbert space admits a unique element that has the minimum norm in the set.
The proof involves ...

**0**

votes

**0**answers

62 views

### Discrete primal-duality in optimization

I would like to inquire about the existence of something perhaps similar to the duality theorem in the convex analysis or convex programming in the discrete setting. Here is a concrete example.
Let $...

**4**

votes

**1**answer

229 views

### Inf of Jensen's inequality

I'm reading a monograph that considers the following problem:
$$\inf_{z(t) \in C^1} \int_0^1 c\bigg(\frac{dz(t)}{dt}\bigg) dt\\ z(0) = x, z(1) = y$$
Here $c$ is a convex function, $z(t)$ are paths ...

**4**

votes

**0**answers

203 views

### Minimization over a convex function of equal vs unequal success probabilities of Bernoulli random variables

Let $U_1,U_2,\ldots,U_n$ be $n\geq 2$ mutually independent Bernoulli random variables. There are two cases of interest:
$1.$ The random variables $U_1,U_2,\ldots,U_n$ are identically distributed;
$...