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 (3)

1
vote
0answers
19 views

Why is this set a subset of its polyhedral approximation - contradicting the gradient inequality?

Say we have a set $C:= \{y\in \mathbb{R}^n : g_i(y) \leq 0, \space i=1,...,m\}$ where $g_i : \mathbb{R}^n \to \mathbb{R}$ are convex and differentiable functions, then we have $\tilde C : = \{y: ...
1
vote
0answers
17 views

Convexity Proof with constraints on the gradient

Consider a minimization problem $(P)$ : minimize $f(x)$ subject to $\delta_C(x) \leq 0$ Now assume that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and let $f: \mathbb{R}^n \to \mathbb{R}$ be ...
1
vote
1answer
17 views

Show the following statements are equivalent - convexity

Let $C \subset \mathbb{R}^n$ be a set. Show the following are equivalent: (a) The set $C$ is convex. (b) The function $\delta_C : \mathbb{R}^n \to \mathbb{R} \cup \infty$ defined as: ...
0
votes
0answers
16 views

About the alternating optimization

The problem is defined as follows: $$ min_{A,B,C} f(A,B,C) $$ and the problem couldn't solve by gradient descent or close-form solution. Thus, the usual way is to use the alternating optimization: ...
2
votes
2answers
68 views

Minimum volume covering ellipse

Given a convex polygon in the plane, consider the smallest-area ellipse which contains this polygon. This is the "minimal volume covering ellipsoid" or "minimal volume enclosing ellipsoid" or in short ...
1
vote
1answer
34 views

Convexity proof - can I get some pointers?

Prove that $C \subset \mathbb{R}^n$ is convex iff $\forall m \in \mathbb{N}$ and every set of $m$ points $\{x_1,...,x_m\} \subset C$ we have that $\sum_{i=1}^m \lambda_i x_i \in C$ Where ...
0
votes
1answer
27 views

Steepest Descent Sequence

How can I compute the first three iterates for the steepest descent sequence $f(x_1,x_2) = \frac{(x_1^2+3x_2^2)}{2}$ beginning at $x_0 = (\frac{\sqrt{3}}{2}, \frac{1}{2 \sqrt{3}})^T$ $\nabla ...
2
votes
1answer
32 views

Constructing a newton sequence

How may I construct the newton sequence for the following: $(1) f(x_1,x_2) = x_1^4 + 2x_1^2x_2^2 + x_2^4$ with $x_0 = (1,1)$ and $x_0 = (1,0)$ $(2) f(t) = t^4 - 32t^2$ and $t_0 = 1$ To find ...
1
vote
1answer
28 views

Different ways to prove convexity of quadratic form associated to rank 1 matrix

Let $v \in \Bbb R^n$, and $f:\Bbb R^n \to \Bbb R^n$ with $f(x)=\langle x,(vv^T)x\rangle$. Show that $f$ is convex. I'm looking for different approaches to solve this (rather simple) problem. ...
0
votes
0answers
39 views

A property similar to the convexity, but actually different?

If we know there exists a point $x_0$, such that $f(x_0)$ lies below the tangent line at $0$ of $f(x)$, which means below the line $y=f(0)+f'(0)x$. My question is how to prove this violate $f(0)\le ...
1
vote
0answers
48 views

Is the function $f(A)=-\log(tr(A^{-1}))-\log(\det(A))$ convex?

I am trying to show the following function is convex or not $$f(A)=-\log(\text{trace}(A^{-1}))-\log(\det(A)),$$ where $ A$ is positive definite. I know $\text{trace}(A^{-1}), -\log(\cdot)$ and ...
0
votes
0answers
16 views

Property of probability density function (pdf)

If $X$ is a random variable with a log-concave pdf. And suppose $Z = h(X)$ If $h(X)$ is convex, can we say $Z$ has a log-concave pdf? If $h(X)$ is affine, can we say $Z$ has a log-concave pdf? ...
1
vote
0answers
32 views

Legendre Transform of this function

Is the Legendre-Fenchel transform of $$f(x)=1-\sqrt{1-|x|^2}, x\in B(0,1)\subset\mathbb{R}^n$$ just $$f^*(x^*)=-1+\sqrt{1+|x^*|^2}?$$ I calculated this using the table here ...
1
vote
1answer
70 views

Chebyshev sets in finite dimension are closed and convex

Prove a finite-dimensional converse to the “best approximation theorem”: Let $K$ be a subset of a finite-dimensional Hilbert space $H$ which satisfies the following property: for each $x \in H$ there ...
0
votes
0answers
40 views

Proximal Mapping of Composition with Linear Operator

I've posted this question on math overflow but got no answer, so I think it might not be a research level question so I decided to post it here too. Let $A$ be an orthogonal matrix. It is well known ...
0
votes
0answers
21 views

Dot product - geometrical interpretation in convex analysis

I am studying a theorem on the characterization of solutions in nondifferentiable convex problems. Say that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and $f: \mathbb{R}^n \to ...
0
votes
1answer
23 views

Normal cone to the tangent cone of $\mathbb{R}_+$

These are the definitions I'm using (cf Rockaffeller): normal cone to a convex set $C$: $$\mathcal{N}_C(x)=\{d\ | <d,y-x>\leq 0,\ \forall y\in C\}$$ tangent cone to a convex set $C$: ...
5
votes
1answer
73 views

References for hemicontinuity?

Let $X$ be a real vector space, $K\subset X$ be a nonempty and convex set. The mapping $f:X\rightarrow\mathbb{R}$ is said to be hemicontinuous if for every $u,v\in K$, the mapping ...
0
votes
1answer
31 views

How to show that SVM is convex problem

It's well-known fact that SVM is convex problem $min \frac{1}{2} \left \| w \right \|^2$ s.t. $(wx_i+b)y_i \geq 1$ I don't understand how given the LP formulation of SVM I can coclude that it's ...
0
votes
0answers
37 views

$Ax = b$ & $Ax + b$

Ask a dumb question but confuse me long time. The following is what I know: 1st case $Ax = b$ is an affine set in $x$,i.e. $\{x | Ax = b\}$, and it is linear in $x$. 2nd case $ f(x) = Ax + b$ ...
0
votes
0answers
23 views

convex function divided by convave function is quasiconvex

$p(x) \geq 0$ is convex, and $q(x) > 0$ is concave. How to prove $f(x) = \frac{p(x)}{q(x)}$ is quasiconvex? My proof is using t-sublevel set: $\{x | \frac{p(x)}{q(x)} \leq t\}$ is ...
0
votes
1answer
45 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
1answer
38 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
28 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 ...
0
votes
0answers
21 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, ...
1
vote
2answers
30 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
20 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\gt x2,\ ...
2
votes
1answer
22 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
vote
0answers
25 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, ...
1
vote
0answers
23 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
3answers
111 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 ...
0
votes
0answers
28 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
1answer
21 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 - ...
2
votes
0answers
30 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 ...
1
vote
0answers
18 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 ...
1
vote
0answers
30 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
1answer
52 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
0answers
33 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 ...
0
votes
1answer
11 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
0answers
16 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
41 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
0answers
28 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
3answers
38 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? ...
2
votes
1answer
46 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] ...
0
votes
2answers
21 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
33 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
33 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
33 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
1answer
44 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
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 ...