Tagged Questions
3
votes
1answer
50 views
Does convex and radially open imply open?
I want to show that a convex set $A$ is radially open iff $A\cap W$ is open in W, for every finite dimensional linear subspace.
Here the 'openness' we are talking about is from any normed space.
...
1
vote
0answers
37 views
Prove that for every $f$ in $H$, the sequence $u_n$ which is the projection of $f$ on $K_n$ converges to a limit
$K_n$ is non-increasing sequence of closed convex sets in Hilbert space $H$ such that the intersection of $K_n$ is different from emptiness. Prove that for every $f \in H$, the sequence $u_n$ which is ...
1
vote
1answer
19 views
Does the Border (Boundary) Points of a convex shape in the positive quadrant make a convex function?
Let $\mathbb{S}$ be a convex body in 2-D with some non-zero intersection with positive quadrant and let it also contain origin. Let $c>0$ be the right-most point on the x-axis such that $(c,y)\in ...
0
votes
0answers
18 views
Solution of a Quadratic Optimization Problem
Let $\mathbf{A_1}$ and $\mathbf{A_2}$ be two given $N\times N$ hermitian matrices. Then how do I solve the problem,
\begin{align}
...
1
vote
1answer
34 views
Robust feasibility with halfspace?
Consider a convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$, such that for all $x \in \mathbb{R}^n$ we have
$$ a_1^\top x + b_1 \leq f(x) \leq a_2^\top x + b_2 $$
for some given $a_1, a_2 ...
1
vote
1answer
40 views
About Balanced-Convex Hull of a Set
Definition. $\newcommand{\bco}{\operatorname{bco}}$Let $X$ be a real vector space and let $A\subseteq X$. The balanced-convex hull of $A$, deonoted $\bco A$, is the intersection of all balanced-convex ...
1
vote
2answers
80 views
Does $\inf_{(a,b)\in A} ax+by=\inf_{(a,b)\in B} ax+by$ imply $A=B$?
Let $A,B\subseteq\Bbb [0,1]\times [0,1]$, and for all $(x,y)\in \Bbb R^2$ with $x^2+y^2=1$,
$$\inf_{(a,b)\in A} ax+by=\inf_{(a,b)\in B} ax+by$$
Can we deduce $\overline A=\overline B$.
1
vote
1answer
43 views
Trace Constraints and rank-one positive semi-definite matrices.
Let $C_1$,$C_2$...$C_N$ be $M\times M$ hermitian matrices and $c$ be a given positive constant. Let $W$ be a positive (possibly semi) definite matrix such that
\begin{align}
\text{trace}\{WC_1\}\geq ...
1
vote
1answer
40 views
Convexity of product of elements from two convex set
Given two convex set $X\subseteq \mathbb{R}^N$,$Y\subseteq \mathbb{R}^{N\times N}$
Given a $x\in X$, is the set $\{z|z=yx,\forall y \in Y\}$ convex?
If no, by adding what can force it to be convex?
...
1
vote
1answer
50 views
Hessian of a function that takes matrix arguments
I have a function that that takes a matrix and returns a scalar, $f : \mathbb{R}^{m\times n} \rightarrow \mathbb{R}$. I know how to calculate the derivative of this function with respect to the matrix ...
4
votes
1answer
82 views
Is this matrix function convex or non-convex?
Given, $g(Z)=Tr(Z^Tf(Z)Z)$ , where $f(Z)=h(Z)-ZZ^T$ is a p.s.d matrix formed using entries in $Z$, where again $h(Z)$ is a diagonal matrix with its $i$'th diagonal entry being ...
0
votes
0answers
41 views
Is this function concave on X? $\log \det(I+(P-\text{tr}(X))\cdot X)$
where P-tr(X)>0 and X is a diagonal matrix with elements of (x1,x2,...xm) where xi>0 and xi<1
For this question,I have apply Mathematica8.0 to find the Hessian matrix of -1*Logdet(I+(P-tr(x)X)) ...
0
votes
2answers
83 views
Convexity of $\log \det(I+(P-\text{tr}(X))\cdot X)$
where $P-\text{tr}(X)>0$ and $X$ is a diagonal matrix with diagonal elements are $(x_1,x_2,\dots x_m)$
0
votes
2answers
71 views
An eigen problem
$K$ is a symmetric positive semidefefinit matrix.
$K1 = 0$ (i.e. The sum of elements in each row is $0$. Or in other words matrix $K$ is centered. From this we conclude the smallest eigenvalue of $K$ ...
3
votes
1answer
89 views
Convexity of a Given Function
Is the following function convex or concave?
$$f(\mathbf{x}) = \frac{1}{N}\sum_{i=1}^N\sqrt{1+\frac{x_i^2}{\left(\frac{1}{N}\sum_{i=1}^{N}x_i\right)^2}},$$
$\mathbf{x} = [x_1,x_2,...,x_N]^T, x_i \ge ...
0
votes
1answer
26 views
affine set definition equivalence
How to show the following definitions are identical for an affine space:
$C = p + W$ where $W$ is a subspace $p$ is a vector in $\mathbb{R}^n$, and
$\lambda a + (1-\lambda) b$ is in $C$ for any $a$ ...
2
votes
0answers
62 views
Is the polar set of convex Polytope also Polytope
Let $P$ be a convex polytope.
How can I prove that the polar set of $P$ (lets call it $P^*$) is polytope?
where $P^*=\{x\in\mathcal R^n:\forall v\in P, |\langle x,v\rangle|\le1\}$ .
$Thanks$
2
votes
1answer
50 views
Possibility of Unboundedness in Least Squares Minimization
Suppose we have the quadratic minimization problem
\begin{equation}
\min_x \frac{1}{2} x^TPx + q^Tx +r
\end{equation}
We know that when $P$ is symmetric positive semi-definite, but the optimality ...
3
votes
1answer
35 views
If a vector in a convex set can be extended infinitely to a certain direction, can any vector in that set be extended infinitely to that direction
Assume we have a convex set $U$. Given $x \in U$, assume there exists a vector $y$ such that $\forall t>0, \ \ x+ty \in U$. I wish to prove that $\forall z \in U,\ \ \forall t>0,\ \ z+t y \in U$ ...
3
votes
1answer
55 views
A particular ILP where the existence of a relaxed solution implies the existence of an integer solution
This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately.
I am ...
2
votes
0answers
73 views
Numerical Methods for minimizing a Non-Differentiable Convex Function of Several Variables
I have a multi-variable convex continuous function which is not differentiable. I am interested to know about different numerical techniques, possibly also references to them, used for this.
Read ...
3
votes
1answer
80 views
Edges of the convex hull of a finite point set
I'm looking for a formal proof of a statement that seems obvious (and yet may be wrong) to make sure one of my algorithms is correct.
Given a set S of N points in $\mathbb{R}^3$, suppose we have a ...
0
votes
1answer
25 views
Intersection of a 2-Dimensional body and a Line given west-most point and south-most point
I have a 2-Dimensional Closed Convex Compact Body $\mathbb{S}$(a set, for eg, a circular disc)). Assume, it has a non-zero intersection with the all-negative quadrant. Consider the following 2-D point ...
2
votes
1answer
237 views
Prove every local minimum is a global minimum
Let $Q\in\mathbb{R^{dxd}}$ and $A\in\mathbb{R^{d'xd}}$ be two matrixes and $b\in\mathbb{R^d}$, $c\in\mathbb{R^{d'}}$. Suppose $d'\lt d $. For $x\in\mathbb{R^d}$.
Minimize
$$f(x)= ...
3
votes
2answers
86 views
A standard quadratic minimization problem
Consider the "Complex" Quadratic minimization problem
\begin{align}
\min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~\mathbf{{x}}^H\mathbf{Q}\mathbf{x}-2~\Re{(\mathbf{x}^H\mathbf{b})}+1
\end{align}
...
4
votes
2answers
108 views
How should I prove a set is convex?
Given a set $$ \mathbf{S} = \{ \mathbf{x}\:|\: \mathbf{x}^T\mathbf{V}\mathbf{x}=1 \} $$ where $\mathbf{V}$ is a positive semidefinite matrix. How to prove this set is convex?
I tried in the ...
2
votes
1answer
97 views
Why a closed bounded convex set in $\mathbb{R}^{n}$ always has an extreme point?
Let $X\subseteq \mathbb{R}^{n}$ is closed, bounded convex set. How to prove that $X$ contains such point $x$ that we can't represent as $x=\frac{1}{2}x_{1}+\frac{1}{2}x_{2}$ where $x_1\in X$ and ...
1
vote
0answers
41 views
Minimize a complex quadratic subject to two convex quadratic constraints
I have the following the optimization problem
\begin{align}
\min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~&||\mathbb{x}^H\mathbb{u}||_2^2-2*Real\{ \mathbb{x^Hu}\}
\\\ ...
1
vote
1answer
91 views
Separation Theorem in Euclidean Space.
I want to show the following:
Let $A,B \subseteq \mathbb{R}^n$ disjoint, nonempty, closed and convex sets. Then there exists a $h \in \mathbb{R}^n$, such that $A$ and $B$ gets separated in the ...
0
votes
1answer
135 views
a convex function on a 2 dimensional closed convex set
Let us say I have a closed compact convex set $\mathbb{S}$ on the 2-D plane (eg: a circle). Let any point $p$ in the 2-D plane be represented by $p=(x,y)$. I define the max function over 2-D plane
...
0
votes
2answers
56 views
Proof that this set is convex
I need a help with prooving that a given set is a convex set:
$\{ x \in R^n | Ax \leq b, Cx = d \}$
I know the definition of convexity: $X \in R^n$ is a convex set if $\forall \alpha \in R, 0 ...
1
vote
0answers
39 views
Concave lower bound on inner product of two distributions.
Given two discrete distributions $p, q$ which lie in an $m$-dimensional simplex, is it possible to provide a concave lower bound on the inner product between these distributions. That is we wish to ...
4
votes
5answers
149 views
Find a convex combination of scalars given a point within them.
I've been banging my head on this one all day! I'm going to do my best to explain the problem, but bear with me.
Given a set of numbers $S = \{X_1, X_2, \dots, X_n\}$ and a scalar $T$, where it is ...
1
vote
1answer
139 views
Second order approximation of log det X
I'm trying to follow the derivation of second order approximation of log det X from Boyd's "Convex Optimization", p.658 in http://www.stanford.edu/~boyd/cvxbook/
How is the last step derived? IE, ...
2
votes
2answers
75 views
A Quadratic Problem (which looks very simple)
This arises as a part of my work.
\begin{align}
\min_{x^{H}x=1}~&x^{H}A_1x \\
subject~to~&x^{H}A_2x=0
\end{align}
$A_1$ and $A_2$ are $N\times N$ hermitian matrices and $x$ is a unit norm ...
2
votes
3answers
75 views
Proof of Convexity
Is the function $Trace(AX^TBX)$ a convex function in $X$ or not ? Here, $X$ is a rectangular matrix and $A,B$ are square, symmetric, p.s.d matrices. The entries in $X,A,B$ are real valued.
0
votes
0answers
42 views
Hyperplane with convex / affine combination
I have a $(d-1)$-simplex with the $n$ vertices
$x_1,...,x_n$
and look at points described by the convex combination
$$\sum_{i=1}^n a_i x_i, \qquad \sum a_i = 1.$$
Now can I describe the slice ...
0
votes
1answer
68 views
How do you describe a convex hull for the set of points in $y = \sin x$
More specifically in, the set notation for the original set is:
$$
S = \begin{Bmatrix} \begin{bmatrix} x\\ y\\ \end{bmatrix} : y = \sin x \end{Bmatrix}
$$
So, how would you find the convex ...
0
votes
0answers
68 views
Does every convex-linear map have an affine extension?
There is one step in a proof which I don't manage to show, although it seems to be very easy.
Let $A, B$ be real vector spaces, let $S \subset A$ be a convex set and let $\text{aff}(S)$ be its affine ...
0
votes
0answers
90 views
When do the minimal and the maximal tensor product coincide?
The structures in question are known in the (physics) literature, so the reader familiar with it can skip the definitions and read the question below.
For the other, let's make the following ...
6
votes
1answer
391 views
Farkas Lemma proof
I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm.
From Wikipedia:
Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the ...
1
vote
1answer
87 views
Convex Combination of Hermitian Matrices
Assume all the matrices I discuss about are $N \times N$. Consider any two hermitian matrices $A_1$ and $A_2$ which are indefinite. The question is, In general, for any $A_1$ and $A_2$, does there ...
1
vote
1answer
304 views
Relation between Positive definite matrix and strictly convex function
I have a problem.
From wikipedia http://en.wikipedia.org/wiki/Positive-definite_matrix
any function can be written as $$z^TMz$$
where z is a column vector and M is a symmetric real matrix.
However ...
0
votes
1answer
62 views
Question about piecewise linear paths
I'm having trouble with a concept about piecewise linear paths. I've been looking on the net but I haven't found a definition of it.
Consider a finite family of hyperplanes in a finite-dimension real ...
1
vote
0answers
109 views
How to compute the image of a polyhedron under a linear transformation
Suppose $P$ is a polyhedron whose representation as a system of linear inequalities is given to us: $$ P = \{ x ~|~ Ax \leq b\}$$ Define $P'$ be the image of $P$ under the linear transformation which ...
1
vote
1answer
85 views
Is concave quadratic + linear a concave function?
Basic question about convexity/concavity:
Is the difference of a concave quadratic function of a matrix $X$ given by f(X) and a linear function l(X), a concave function?
i.e, is f(X)-l(X) concave?
...
2
votes
0answers
62 views
Find a vector such that its matrix product is positive in every element
Given a matrix $A$ I want to find a vector $\vec{x}$ such that every element of $A\vec{x}$ is strictly positive. Also, the columns of $A$ do not span the full space, so if I were to just naively pick ...
0
votes
0answers
92 views
The bipolar theorem from functional analysis
I am referring to this source: http://www.math.unl.edu/~s-bbockel1/929/node6.html.
How can I show the other bipolar theorem where the polar of a prepolar is the closed convex balanced hull? Is it ...
4
votes
3answers
159 views
Prove one set is a convex hull of another set
Define two sets:
$A = \{x \in \{0,1\}^n : \lVert x \rVert_1 \leq k\}$ is a finite set of binary vectors;
$B = \{x \in [0,1]^n : \lVert x \rVert_1 \leq k\}$ is an infinite set of real-valued vectors, ...
4
votes
1answer
85 views
Is this function convex when the input vector is positive?
I am wondering if $f(\mathbf{x})$ is convex on the input of a vector of $n$ positive reals $\mathbf{x}$:
$$f(\mathbf{x})=\operatorname{Tr}[(\mathbf{A}+\operatorname{diag}(\mathbf{x}))^{-1}]$$
where ...
