Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
2
votes
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
2answers
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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;
$...
