Convex analysis is the study of properties of convex sets and convex functions. For questions about optimization of convex functions over convex sets, please use the (convex-optimization) tag.

learn more… | top users | synonyms (1)

1
vote
0answers
12 views

Sum of a convex set and a complement of a convex set

In $\mathbb R^n$ equipped with the Euclidean norm, let $B$ be a convex set and $A$ be a subset such that $\mathbb R^n\setminus A$ is a convex set. Is it true that $A+B$ is a complement of a convex ...
0
votes
1answer
367 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
0
votes
1answer
36 views

Can we claim that $f(x)$ is an increasing function and its stationary point is $x = \infty$ (in this specific case)?

If $f(x)$ is concave and its first derivative $f'(x) \rightarrow 0$ when $x\rightarrow \infty$, can we claim that $f(x)$ is an increasing function and its (only) stationary point is $x = \infty$ ? ( ...
0
votes
0answers
5 views

Does analytical solution exist for this convex euclidean affine projection problem with non-negativity constraints?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely, $X \in ...
1
vote
1answer
24 views

Why is $J(u) := \int_\Omega |\nabla u|^2$ convex?

Define $J(u) := \int_\Omega |\nabla u|^2$ over $\{ u \in H^1(\Omega) : tr(u) = g\}$. Why is $J$ convex? I keep getting $J(tu + (1-t)v) \leq 2t^2J(u) + 2(1-t)^2J(v)$ by using the triangle inequality ...
1
vote
2answers
20 views

Is this set of matrices convex?

The set of positive definite matrices is convex. But what about this set? $$\Omega = \left\{ (\mathbf{A}, \mathbf{b}) \in \mathbb{R}^{n \times n} \times \mathbb{R}^n : (\mathbf{A} - ...
0
votes
0answers
6 views

convex region with 7 vertices

Let, $X$ be a convex region in the plane bounded by straight lines. Let, $X$ have $7$ vertices. Suppose $f(x,y)=ax+by+c$ has maximum value $M$ & minimum value $N$ on $X$ & $N<M$. Let, ...
0
votes
0answers
10 views

Need to prove a property using super modularity and convexity

I have a function f(x,y) that is convex on both x and y separately (but maybe not a joint convex function). It is also super modular. Assume that we have ordered sets of x and y as (x1>x2,x3>x4) and ...
1
vote
0answers
16 views

Is product of 2 positive concave function with different domain concave? [on hold]

Suppose f(x) and g(y) are two positive concave functions. h(x,y) = f(x)g(y) Is h(x,y) concave as well?
2
votes
1answer
18 views

Proof: number of intersection points of borders of a convex polygon and its translate never greater than 2

How can I prove the observation that the borders of a convex polygon $P$ with no parallel sides in $\mathbb{R}^2$ and a translate of $P$ by any vector $t\neq 0 \in \mathbb{R}^2$ that is not parallel ...
-1
votes
0answers
30 views

Is following matrix sets convex? [on hold]

Given $A\in\{0,1\}^{n\times n}$. Denote $\mathcal{A_{n,n}}$ to be collection of rank $1$ matrices from $\{0,1\}^{n\times n}$. Denote $\mathcal{A_{n,n}}[A,c,S\subseteq\Bbb R,T\subseteq\Bbb ...
2
votes
0answers
53 views

Isometric isomorphism maps extreme points to extreme points

I am trying to prove that $\mathcal{c}$ and $\mathcal{c_0}$ are isomorphic but not isometrically isomorphic. I've read on this forum that isometric isomorphism preserves extreme points, but I don't ...
1
vote
0answers
10 views

Fenchel Conjugate of a norm squared

I was wondering if the fenchel conjugate of the $\frac{1}{2}||u||^2$, is the $\frac{1}{2}||u||_*^2$, where $||.||_*$ is the dual norm of $||.||$. This seems to be true for the $\ell_2$ norm. However, ...
2
votes
1answer
39 views

Using inequalities to find vertices of a polytope

Consider a set $C$ of vectors of integers $x\in\mathbb N^d$ satisfying $$ \begin{align} \forall\ i=1..d & \ \ [0 \leq \ell_i \leq x_i \leq u_i]\\ \forall\ i=1..d-1 & \ \ [x_{i+1} \leq x_i] ...
5
votes
2answers
135 views

For what $X$ do we have $\|XA\|_{1} \leq 1$ for a given $\|A\|_{1} \leq 1$.

All matrices are real. By $\| \cdot \|_1$ I mean a matrix norm induced by the vector norm $L_1$, i.e. the max of the column sums of absolute values. The matrix $A$ is given and we have $\|A\|_{1} ...
1
vote
0answers
19 views

Mean width of an ellipsoid

Let $E$ be an ellipsoid in $\mathbb{R}^d$ defined by the equation $\sum \frac{x_i^2}{a_i^2}=1$. Is there a formula to express the mean width (or an approximation of the mean width) of $E$ in term of ...
8
votes
0answers
265 views

Theorem about convex sets

I want to prove a theorem (the link is after the whole text here) and in order to do that I need to prove three preliminary statements. I tried to prove them all but I'm already stuck in the first, ...
2
votes
0answers
22 views

Log concavity/convexity of a determinant

I was wondering if anyone would be able to help me determine whether the following quantity is log concave or not with respect to $\alpha$? $$\left[\det(\textbf Y^\top \textbf P \textbf G \textbf ...
6
votes
3answers
76 views

Exposed point of a compact convex set

I'm trying to show that given a compact convex set $K$ in $R^d$, there must be at least one exposed point (where $v$ is exposed if there exists a hyperplane H such that $H \cap K = \{v\}$ . This is a ...
1
vote
1answer
16 views

A proof of property of log-concave

How to prove the $f$ is NOT log-concave? (or equivalently, log$f(x)$ is not concave) log$f(d)+$log$f(a) < $log$f(b) + $log$f(c)$ where $a = x_2 - y_2$, $b = x_2 - y_1$, $c = x_1 - y_2$, $d = x_1 - ...
0
votes
0answers
12 views

log-concavity with PDF and CDF

Assume the following: pdf: $f_X(x)$ cdf: $F_X(x)=P(X \leq x)$ $X$ is a random variable with log-concave pdf $f_X(x)$. $Y = h(X)$ $X \in R^n$ $h: R^n \rightarrow R$ Through the ...
1
vote
0answers
30 views

Dimension of Polyhedra [closed]

Can someone explain the question below? I'm pretty new in this area, and I did not understand anything. Question; Let $P$ be defined by the following $$\begin{align}x_1+x_2+x_3&\le ...
1
vote
0answers
25 views

Convexity of matrix inverse

If $$f\colon\mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}$$ where $$f(x,y)=y^T x^{-1}y$$ and dom$(f)=\{(x,y)\ |\ x+x^T\gt 0\}$, then is $f$ convex?
0
votes
0answers
27 views

Logarithmically Convex Function

By definition a logarithmically convex function is a positive real-valued function $f(x)$ defined on a convex set such that $\log f(x)$ is convex i.e. $$\forall\alpha\in[0,1]\hspace{0.5cm}\log ...
1
vote
0answers
12 views

Property of log-concave function

In S.Boyd's lecture: And in his vedio, he said: You are allowed one positive eigenvalue in the Hessian of log-concave function. http://web.stanford.edu/class/ee364a/videos/video04.html (at ...
12
votes
1answer
367 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 & ...
1
vote
0answers
21 views
0
votes
0answers
20 views

Proof - extreme point of a convex set

everybody! I am wondering how to prove the following theorem: Let $S \subset \mathbf{R}^{n}$ be a non-empty closed convex set. Then $S$ has at least one extreme point iff $S$ does not contain any ...
1
vote
2answers
54 views

Convexity of mutual information $I(X;Y)$ in conditional $p(y \mid x)$

I'm trying to understand the proof that $I(X;Y)$ is convex in conditional distribution $p(y \mid x)$ - from Elements of Information Theory by Cover & Thomas, theorem 2.7.4. In the proof we fix ...
1
vote
3answers
29 views

Questions about coerciveness and convexity

I just have a few yes/no questions, and would really appreciate if you could correct me where I am wrong, and for what fundamental flaw I have. 1. Would the set of coercive functions a linear space? ...
0
votes
0answers
5 views

Variation of linear matrix inequality

When reading "Convex optimization, S. Boyd" p.76, Example 3.4, it says The last condition is a linear matrix inequality (LMI) in $(x,Y,t)$. Therefore, epi($f$) is convex. I am confused about ...
0
votes
1answer
184 views

directional derivative of convex function sublinear proving that fact

How can we show that the directional derivative of a proper convex function on $\mathbb{R}^n$ is sublinear? Thank you!
0
votes
0answers
12 views

Proof of the direction of directional derivative is convex

Consider the directional derivative: http://en.wikipedia.org/wiki/Directional_derivative How to prove the following is cvx in $v$ (the direction of directional derivative): $h(v) = $inf ...
1
vote
1answer
32 views

Is $f(x,y)=-xy$ neither concave nor convex?

Is $f(x,y)=-xy$ neither concave nor convex? I used the definition for first differentiable functions and determined it depends on the choice of points, hence it is neither.
1
vote
2answers
19 views

How to find ellipsoid bounding the intersection of an ellipsoid and half-space?

How does one prove that the bounding ellipsoid $E(A', a')$ of the intersection of an ellipsoid $E(A,a) = [ x | (x-a)^TA^{-1}(x-a) ]$ and half-space $H = [x | c^Tx \le c^Ta ]$ is given by the ...
1
vote
0answers
21 views

Books on convex sets?

I'm looking for good books on convex sets. Idealy I'd like an introductory text AND a more advanced one. Appart from basic definitions and the like I have no background on the topic.
1
vote
1answer
35 views

the relation between positive definite matrix and its ellipsoid

Define $S^n_{++}$ to be the set that contains all the positive definite matrices. That is, if $A \in S^n_{++}$, then $A$ is a positive definite matrix. Then, we associate with each $A \in S^n_{++}$ ...
0
votes
2answers
15 views

Coerciveness and Positive definiteness relation?

Let $A ∈ \mathbb{R}^{n×n}$ be a symmetric matrix. How can I demonstrate that A is positive definite iff the function $q(x) := x^TAx$ is coercive . I know the eigenvalues of A have to be positive for ...
1
vote
1answer
28 views

Why does the Weierstrass theorem fail if a set is not compact?

By Weierstrass theorem I mean that if $f:\mathbb{R}^n \to \mathbb{R}$ is continuous and $C \subset \mathbb{R}^n$ is compact, then the theorem asserts that a solution $x^*$ of $$ \text{min} _{x\in ...
0
votes
2answers
26 views

Union of 2 convex sets

Let $f : \mathbb{R}^n→ \mathbb{R}_∞$ be convex over the sets A, B which are also convex. $A ∩ B = ∅$ and $A ∪ B$ is convex. Then is $f$ is convex on $A ∪ B$? Why or why not? I am confused ...
1
vote
1answer
26 views

Proving convexity using the Hessian

Suppose I have $f: \mathbb{R}^n \to \mathbb{R}_\infty$ which is twice continuously differentiable, on some convex set C, which is open. How can I prove that $f$ is convex over C, iff the hessian ...
0
votes
0answers
24 views

Coerciveness of a function - help

I'm trying to show that $$f(x_1,x_2,x_3) = e^{x_1^2 + x_2^2} + (x_1^2 + x_2^2 + 3x_2)^{500}$$ is not coercive, but am struggling to see anything. Any help is appreciated!
-1
votes
0answers
19 views

Which one(are) true?

My Effort: a,b are true. As f convex means for any 2 points in the curve , curve lies below the line. Thinking geometrically I think c is incorrect as if f negative |f| is positive. I' ll be glad if ...
1
vote
0answers
46 views

Showing convexity of a function with the restriction over an arbitrary line proof

Let $f : \mathbb{R}^n → \mathbb{R}_∞$ be a function and let $C ⊂ dom f$ be a convex set. $$**Part I**$$ Prove that $f$ is a convex function if and only if $f$ is convex over every line $L_{v,x_0}$ ...
1
vote
0answers
23 views

Convexity over a line given a convex interval [duplicate]

Let $f : \mathbb{R}^n \to \mathbb{R}_∞$ be a function. I want to prove that $f$ is convex over the line $L_{v,x_0}$ iff $\psi : \mathbb{R} \to \mathbb{R}_∞$ $\psi(t) := f (x_0 + tv)$, is convex ...
0
votes
0answers
11 views

Subsets being cones

I am trying to self-study convex optimization and still trying to get into the gist of it. There is a question in my text as follows: Let $V$ be the set of sequences whose terms are contained in ...
0
votes
1answer
15 views

Subdifferential is closed, convex and bounded

If $f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ is convex, how can I show that $\partial f(x_0)$ (sub differential) is closed and convex, and also bounded (bounded when f over the entire domain)
1
vote
2answers
28 views

Is the support function always unique for a convex set?

Given an arbitrary set $A ⊂ \mathbb{R}^n$ , the support function associated with the set $A$ $ σ_A : \mathbb{R}^n \to \mathbb{R} ∪ \{+\infty\}$ is defined as $\sigma_A(x):= \sup_{z \in A} \langle ...
1
vote
0answers
30 views

How to find a hyperplane

Let $A, B ⊂ \mathbb{R}^n$ be two nonempty sets such that $A ∩ B = ∅$. $H(A, B) := \{(w, d) ∈ \mathbb{R}^{n+1} : \sup_{x\in A} \langle w,x\rangle ≤ d ≤ \inf_{y \in B} \langle w, y\rangle \}$ How do I ...
0
votes
0answers
17 views

The conditions on marginals that guarantees a certain class of measures

$x$ and $y$ are $m\times n$ matrices. $a, B,C$ are $m\times 1$ matrices. $b, A$ are $n\times 1$ matrices. $$\sum a_i=1, 0\leq a_i\leq 1, \forall i$$ $$\sum b_j=1, 0\leq b_j\leq 1, \forall j$$ ...