Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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