Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
0
votes
0answers
46 views
optimization with eigenvector composition
as the figure shows, I would like to minimize v, and also to solv the corresponding x vector. The solution has shown in the figure. I cannot solve x vector on my own. Help, with thanks...
2
votes
0answers
43 views
Relative interior of subdifferential
$\def\ri{\mathop{\rm ri}}$
Conjecture:
Let $f{:}\ \mathbb{R}^n\to\mathbb{R}$ be convex and let $x,y\in\mathbb{R}^n$.
If $0\in\ri\partial f(x)\cap\ri\partial f(y)$ then
$\partial f(x)=\partial f(y)$. ...
0
votes
1answer
71 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\...
1
vote
0answers
46 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
247 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
58 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
70 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
185 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
138 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
31 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
49 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
99 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
108 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
239 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
36 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
136 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
44 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
51 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
50 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
81 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
43 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
42 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
142 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
37 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
293 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
50 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
98 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
60 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
226 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
202 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;
$...
1
vote
0answers
39 views
In convex optimization we know that the optimum solution is on which hyper plane
We have a standard linear program, I mean a set of inequalities $c_i^Tx\leq b_i$ where $i\in \{1,\ldots ,k\}$ and we want to find $max\{c^Ty| y\in \{\cap \{x|c_i^Tx\leq b_i\}\}$. I put some condition ...
-1
votes
1answer
95 views
Does a half plane contain intersection of some other half planes? [closed]
I'm doing research in Optimization and I have found this obstacle in the way.
If we have set of half planes like $c_ix\leq b_i$ where $i\in \{1,\ldots ,k\}$ there is an algorithm(it would be better ...
2
votes
1answer
223 views
Can the sum of quasiconcave functions always be made quasiconcave?
Let $f_1,f_2$ be two smooth quasiconcave functions defined on a convex subset of $\mathbb{R}^d$.
It is known that $f_1+f_2$ is not necessarily quasiconcave.
Does there always exist monotonically ...
1
vote
0answers
48 views
Complexity of conic optimization problems
I am interested in bounding the computational complexity of the interior points method for solving a generic conic problem of the form
\begin{equation}
\min_x \left\{ c^T x : \mathcal{A}x-B\in\mathbf{...
1
vote
2answers
57 views
Optimization of non-smooth convex function in a polytope
We know that accelerated proximal gradient descent method can be applied to solve the following convex programming problem:
$$\min{f(x)+g(x)}$$
where $f$ is smooth and convex, and $g$ is a non-smooth ...
0
votes
0answers
47 views
Projection onto the “Quadratic Form”
Dear Optimization experts,
I would like to project a vector $\mathbf{z} \in \mathbb{C}^{N\times 1}$ onto a set that can be described by a "quadratic form":
\begin{equation} \label{eqn:...
1
vote
0answers
32 views
How is the minimax oracle used to find the oracle complexity of projected subgradient?
I am going through a set of blog posts on the complexity of projected gradient method.
https://blogs.princeton.edu/imabandit/2013/03/15/orf523-oracle-complexity-large-scale-optimization/ defines the ...
0
votes
0answers
107 views
Are there examples of both strongly convex and smooth functions for $l_p$ norm?
Given an $l_p$ norm $\| x \|_p = (\sum_{i=1}^n |x_i|^p)^{1/p},$ we call a convex differentiable function $f: \mathbb{X} \rightarrow \mathbb{R}$ both strongly convex and smooth if there exists $m, M &...
2
votes
2answers
341 views
Wasserstein distance and the Kantorovich-Rubinstein duality
The only few references I could find on this topic are either amateur blog posts (http://n.ethz.ch/~gbasso/download/A%20Hitchhikers%20guide%20to%20Wasserstein/A%20Hitchhikers%20guide%20to%...
5
votes
0answers
97 views
Dimensions of faces of convex hull of convex bodies
Let $K_1,\ldots,K_m\subset\mathbb{R}^n$ with $m\geq n$ some convex bodies (i.e. compact with nonempty interior). I am interested in sufficient criteria for the convex hull $K=\textrm{conv}(K_1,\ldots,...
2
votes
0answers
95 views
Derivative with multiple summation operators
I have a defined utility function as Eq.(1), and I am seeking the minimized utility subjects to some constraints. The notation used is as following:
\linebreak
$V$ is the set of nodes, $v_i\in V$; $O$...
1
vote
0answers
65 views
Regularized convex relaxation of PCA
One of the ways of formulating the Principal Component Analysis (PCA) problem is the following
$$\begin{array}{ll} \text{minimize} & -\langle C, P \rangle\\ \text{subject to} & P^2 = P\\ &...
3
votes
0answers
115 views
Finding a mixture of 1st and 0'th order Markov models that is closest to an empirical distribution
I am interested in finding the distribution "$p^*$" closest to an empirical distribution $\hat{p}$ where $p^*$ is a mixture of first and zeroth order Markov models. That is, I want to find $$
p^* = \...
1
vote
0answers
37 views
Lipschitz of the minimum curve of a convex function of two variables
Let $f(x,y)$ be a function in two real variables. Assume that $f$ is strictly convex by which I mean $f(x,y) - c(|x|^2 + |y|^2)$ is convex for some $c>0$.
Assume for each $x$ there is a unique $...
1
vote
1answer
75 views
Possible analytical way to solve or approximate a specific optimization problem's solution
In my research on linear algebra and optimization, I have come across the following problem repeatedly:
Given constant matrices $C\in\mathbb{R}^{k \times k}$ and $X\in\mathbb{R}^{n \times n}$, $$\...
1
vote
1answer
67 views
Norm of solution of quadratic program
In a quadratic program (QP), do linear equality constraints always reduce the norm of the minimizer? Specifically, let $P \succ 0$, $A \in \mathsf{M}_{m\times n}$ and $q\in\mathbb{R}^n$. Define
$$x^* ...
4
votes
2answers
241 views
Is this function always bounded below?
Is there any global constant $C$ such that $$C<\frac{\sum_{i=1}^{n}x_{i}\log x_{i}-x_{i}+(1-x_{i})\log(1-x_{i})}{\sum_{i=1}^{n}x_{i}}+\log(\sum_{i=1}^{n}x_{i})-\log(\sum_{i=1}^{n}x_{i}^{2})$$ for ...
1
vote
0answers
170 views
Prove that the following set of triples forms a convex polytope
Take $a,\,b,\,c,\,d \in \mathbb R_+$ such that $a+b+c+d=1$. Define:
\begin{equation}
x_1 = \min(a+b,\,c+d)\,,\qquad x_2 = \min(a+c,\,b+d)\,,\qquad x_3 = \min(a+d,\,b+c)\;.
\end{equation}
I would like ...
