1
vote
2answers
22 views

an interior point of a convex set

How can we prove a point is an interior point of a convex set, considering we don't have all of the extreme points of the given convex set ? or How can we find an interior point of a convex set, ...
0
votes
0answers
19 views

relative interior and the affine map

In the convex analysis book by Hiriart-Urruty &Lemarechal, Proposition 2.1.12 states $ri [A(C)] = A(ri C)$. Where $ri$ is the relative interior and $A: \mathbb{R}^n \to \mathbb{R}^m $ is an ...
4
votes
0answers
68 views

Convexity of $S=\left\{ \frac{\underline{x}^HA\underline{x}}{\underline{x}^H\underline{x}} , \underline{x} \in \mathbb C ^{n}\right\}$

i've to prove that the following set is convex: Let $A \in \mathbb{C}^{n \times n}$ $$S=\left\{ \frac{\underline{x}^HA\underline{x}}{\underline{x}^H\underline{x}} , \underline{x} \in \mathbb C ...
0
votes
1answer
36 views

Question about the structure of a convex optimization problem

I am reading a tutorial about Convex Optimization and it defines the general Convex Optimization problem as: $$ minimize_x f(x)$$ where $g_1(x) \leq 0, ... , g_m(x) \leq 0$ and $Ax=b$ and $x \in ...
10
votes
0answers
258 views

Convexity of Matrix Exponential

Consider the function $A: \mathbb{R}^n \rightarrow \mathbb{R}^{n \times n}$ defined as $$ A( x ) := \left[ \begin{matrix} x_1 & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & x_2 & ...
0
votes
1answer
17 views

what does full- dimensional means when speaking about covex cones

I want to know the exact definition of full-dimensional. And what does "dimension" refer to, is that in the sense of algebraic variety? I have read several writing announcing that the cone of ...
0
votes
0answers
21 views

A Difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
0
votes
0answers
67 views

weights go to infinity in logistic regression with linearly separable data

I have the loss function of logistic regression $L(W)$ = - $\sum_{i=1}^n {y_i}.log[\sigma(w^Tx)] + {(1-y_i)}.log[1- \sigma(w^Tx)]$ I have derived the Hessian and proven it's positive semi-definite ...
0
votes
1answer
32 views

what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
1
vote
0answers
57 views

Dual norm of the matrix L1 norm is infinity norm (and vice versa)

Recall that for a given norm $\|\cdot\|$ on $\mathbb{R}^n$, the dual norm is defined as a function $\|\cdot\|_*: \mathbb{R}^n \rightarrow \mathbb{R}$ with: $\|y\|_* = \max \limits_x \{x^Ty: \|x\|\le1 ...
1
vote
1answer
71 views

On Stochastic Matrices

Let "stochastic" matrix be the matrix whose rows sum to one and deterministic matrix be a stochastic matrix whose all rows consist of a one and zero. For example $\left [ \begin{array}{ccc} 1 & ...
1
vote
0answers
21 views

How to convexify (relax) this L0 eigenvalue optimization problem?

Let $C_1,\dots,C_L$ be $N\times N$ hermitian matrices. Let $d<0$ be a given negative constant. Then consider the optimization problem \begin{align} \max_{r\in \mathcal{R}^{L\times 1}} &\mid\mid ...
0
votes
0answers
46 views

Strictly Convex Functions

I am trying to show the equivalence of two definitions of strictly convex functions. Let $f:\mathbb{R}^n\to \mathbb{R}$ be a smooth function. The function $f$ is strictly convex if for each ...
2
votes
1answer
57 views

Prove vertices of a simplex are affinely independent

I'm given that the definition of a simplex $T$ is $x \in\mathbb R^n$ such that $x$ satisfies $n+1$ linear inequalities: $(u_k, x) \lt c_k$ for $k = 1,\ldots,n+1$ (i.e. $T$ is the intersection of $n+1$ ...
0
votes
1answer
19 views

Representation of half-space

For any non-zero $\mathbf{y}\in\mathbb{R}^\mathcal{l}$ one half-space through origin is defined by $H_{\mathbf{y}}^{\leq}(\mathbf{0})=\left\{\mathbf{x}\in\mathbb{R}^{\mathcal{l}}:\mathbf{y}\cdot ...
1
vote
1answer
24 views

Prove or disprove a statement about testing the convexity of a set using the vertices

Assume we are working in $\mathbb R^d$. Let $A=\text{Conv}(V)$, the convex hull of $V$. Also $B=\text{Conv}(W)$. I am in a situation where I can prove the following: the line segment joining $v$ and ...
-1
votes
2answers
70 views

How to approximate this large sum of exponential terms

Is there any way to approximate the following sum: $$ \sum\limits_{i_1=1}^N\sum\limits_{i_1=2}^N \cdots \sum\limits_{i_k=1}^N \cdots\sum\limits_{i_N=1}^N \exp(-r_{i_1}-r_{i_{k+1}}-r_{i_{2k+1}}- ...
0
votes
1answer
39 views

Projection onto Polyeder

I know how to projects onto a linear subspace of $\mathbb R^3$, but how to project a point $x$ onto an polyhedron given as the intersection of three halfspaces $$ \langle y_1, x \rangle \ge c_1 ...
0
votes
0answers
34 views

Union of all sets of optimal solutions to a perturbed linear programming problem

Please let me know if you have some ideas on how to approach this proof? I got stuck part-way through. The following linear program is a function of $\theta$, $ \begin{array}{ll} \min & c^\top x ...
0
votes
0answers
22 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
0
votes
0answers
39 views

Extreme points by intersection of extreme rays and hyperplane

I just met one question and have no idea about the proof, hope someone can give me some ideas on how to attack this question. Given a graph $G=(V,E)$ with $|E|=n$. Define a set $S$: ...
0
votes
1answer
26 views

Dual of dual cone of nonconvex closed cone

let $K$ be a nonconvex closed cone, then $K^{**}=conv(K)$ should this hold? I am not quite sure about it. Thanks.
0
votes
0answers
30 views

Hyperplane - soft and hard questions

This would be a rather long question. Apologies for that. Instead of asking three separate questions I've consolidated them in one. I am trying to learn hyperplanes, convex hulls, separations theorems ...
0
votes
2answers
73 views

Solution in general for a seemingly simple problem

Let $\mathbb{S}$ be a closed, bounded, convex set in $\mathbb{R}^N$. Let $\mathbb{x}=[x_1,\dots,x_N]$ be any arbitrary vector in $\mathbb{S}$. Then what can we comment on the problem \begin{align} ...
0
votes
1answer
79 views

Explain the convexity by looking the hessian matrix of a function

The hessian matrix of a function is given by, $$ H = \begin{bmatrix} a & b & c \\[0.3em] b & b & 0\\[0.3em] c & 0 & c \end{bmatrix} $$ where, ...
1
vote
0answers
64 views

Monotonically increasing maximum eigenvalue

Let a matrix $A \in \mathbb{R}^{n \times n}$ be the convex combination of two matrices as $A = qB + (1-q)C$. Define $B$ as unit anti-diagonal. Define $C_{i,j} = \delta_{i,i+1}$. Consider $A$ for ...
0
votes
0answers
41 views

Isomorphisms of Convex Cones

A convex cone $C$ is a subsets $C \subseteq V$ of a vector space which is closed under positive linear combinations, i.e. for $\lambda, \mu > 0$ and $u,v \in C$ it is $\lambda u + \mu v \in C$. An ...
1
vote
0answers
59 views

Properties of matrix functions

Can I say that a certain matrix function is absolutely continuous or monotonically increasing in $\lambda$(assuming that the matrix is a function of $\lambda$)? In other words, are these ...
0
votes
1answer
32 views

Finding the determinant of a $ k \times k$ matrix (Hessian matrix)

Given $H(x_{1}, x_{2}, x_{3}) = \begin{bmatrix} -2 & \frac{1}{2} & 0 \newline \frac{1}{2} & -2 & 0 \newline 0 & 0 & -4 \end{bmatrix}$, I want to find (I think) the leading ...
1
vote
0answers
27 views

Intersection of affine subspace of $\mathbb{R}^n$ with $[0, 1]^n$

Suppose I have an affine subspace $V \subseteq \mathbb{R}^n$, say given by a rank-$r$ system of $m$ equations in $n$ variables. I'm interested in two questions: Is there a straightforward way to ...
2
votes
0answers
119 views

Voronoi-Diagram - split concave polygon

I have a concave polygon c and a set of points p[]. What I need is to have a set of polygons splitted by the voronoi-diagram. My problem is the following: I already found a library to calculate the ...
2
votes
0answers
32 views

Monotononically Increasing Water Filling Solution?

$\mathbf{I}$ is the $K\times K$ identity matrix. $\mathbf{h}_i\in\mathbb{C}^{M\times1}\quad\forall1\leq i\leq K$ are column vectors. Consider the solution of the convex optimisation problem over ...
1
vote
1answer
56 views

Normed space problem

I am currently dealing with the following problem: Imagine you have two points $x,y$ in a normed space $(X,||.||)$ and in a convex set $K \subset X$. Now you know that $B_{\varepsilon}(x) \subset ...
0
votes
1answer
24 views

Converting a Probability constraint to a Norm constraint

Let $\mathbf{z}$ be a $N\times 1$ complex vector. Let $\mathbf{u}$ be a $N\times 1$ random Gaussian vector whose entries are i.i.d with zero mean and $\sigma^2$ variance. Consider the following ...
1
vote
0answers
34 views

What is first edge position in the Minkowski sum of two convex polygons in the plane?

I am trying to understand the informal algorithm of the Minkowski sum of two convex polygons in the plane as described here: ...
1
vote
1answer
33 views

Need an analytic expression to find the index of the first positive element of an array

I have an array of length M. The elements of the array are either zero or positive real numbers. I need to derive a function/analytic expression (preferably linear/convex/concave) that finds the index ...
0
votes
1answer
69 views

alternative definition of Affine map

Let $f:X\longrightarrow Y$ be a function on real vector spaces (note that $X,Y$ have arbitrary dimensions). If $T(x)=f(x)-f(0)$ is linear, $f$ is called an affine map. Prove that $f$ is affine if ...
0
votes
0answers
100 views

Help prove a lemma similar to Fredholm alternative (linear algebra / convex optimization)

I was asked to help with a proof of a lemma similar to Fredholm alternative. It looks too similar so I think it may be wrong - could you please advise whether it is true and hint how to prove it? The ...
2
votes
0answers
50 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
0
votes
1answer
63 views

Is this function convex or concave?

I have a function, $f(x_{0},x_{1},......x_{n})=\sum^{n-1}_{i=0}A_{i}r^{-(x_{i}+x_{i+1})}-B$ $A_{i} >0$ for all $i$ and $B>0$ and $1 \leq r \leq 2$ so above function is convex or concave? ...
1
vote
1answer
45 views

Does a discrete set of points in $\mathbb{R}^{n}$ define a locally finite collection of hyperplanes?

Let $v_{1},v_{2},...$ be a discrete set of non-zero vectors in $\mathbb{R}^{n}$. By discrete, I mean that any $v_{i}$ is surrounded by an $\epsilon$-ball not containing any other point $v_{j}$. ...
0
votes
1answer
35 views

Effect of Moving within the Feasible Region

$f:\mathbb{R}^n\rightarrow\mathbb{R}$ is a concave function with local maximum at $\mathbf{x}^*$ in a convex, closed feasible set $\mathcal{F}\subset\mathbb{R}^n$. Now consider a suboptimal point ...
0
votes
0answers
101 views

Proof of corollary of Farkas' lemma

I tried to prove the following lemma of Farkas' lemma: Given the system $Ax<b$, $A\in \mathbb{R}^{m\times n}$, $b\in \mathbb{R}^m$, the system is infeasible iff there exists $\lambda\in ...
2
votes
0answers
66 views

Maximizing the smallest eigenvalue of a linear combination of matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ ...
0
votes
1answer
44 views

Subtle question concerning intersection of convex sets

I am attempting to convince myself that if $$\{S_{\alpha}: \alpha \in \mathcal{A}\}$$ is any collection of convex sets, then $$\cap_{\alpha \in \mathcal{A}}S_{\alpha}$$ is convex. This is my proof so ...
2
votes
1answer
56 views

Find the real vector $x$ which satisfies all this?

I got this after applying KKT conditions to an optimization problem. Let $\mathbf{h}$ be a given $N\times 1$ real vector. Let $\alpha$ be a real constant. We need to find $\lambda$ and the $N\times ...
0
votes
1answer
635 views

Convexity of sum and intersection of convex sets

Let $A_i$ be a subset of $\Bbb{R}^m$ which is convex for $i=1,...,n$. How can I prove that the sum of $A_i$ is also convex? I know how to prove it with two sets: Let $x = a_1 + b_1$ and $y = a_2 ...
1
vote
0answers
49 views

Convex polyhedron is union of simplices

Given a convex polyhedron $P$, how can we prove that every point $x \in P$ is in some simplex whose vertices are vertices of $P$? One proof is to inductively build a triangulation of $P$. If $P$ is ...
1
vote
1answer
56 views

Interpreting a theorem about convex sets

I'm studying about linear programming and I bumped into following theorem (I have added my questions into the image): So in 1st rectangle how did we obtain the resulting equation when $\alpha ...
1
vote
1answer
88 views

Help with a proof of a theorem about convex sets

I'm studying the following theorem: Theorem 1. Let $C$ be a convex set and let $\textbf{y}$ be a point exterior to the closure of $C$. Then there is a vector $\textbf{a}$ such that ...