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)

0
votes
0answers
18 views

Is the sum of logarithms of l1-normed positive vectors concave?

Consider the following function, $f(x) = \sum_{i} \log \frac{x_i}{\sum_k x_K}$ defined on the set of all real vectors with strictly positive entries, $x_i > 0$. The problem $\max f(x)$ has the ...
6
votes
1answer
328 views

Cones of positive semidefinite matrices generated by matrices of rank $1$

Let $S_n$ be the space of real $n \times n$ symmetric matrices and let $S_n^+$ be the convex cone of positive semidefinite matrices in $S_n$. The extremal rays of this cone correspond to the positive ...
0
votes
3answers
65 views

Is the norm of a convex function convex?

I know that the norm of $x\in R^n$, $(\sum\limits_{i=1}^n|x_i|^2)^{0.5}$ is a convex function. Also, not any composition of two convex functions is convex. So my question is: Lets say we have a real ...
0
votes
0answers
13 views

Proving disjoint sets and finding separating hyperplane

Consider \begin{equation} \mathbf{h}=\begin{bmatrix} h_0 & h_1 & \cdots & h_p \end{bmatrix} \end{equation} where $h_i \in \mathbb{R}\forall i=1:p$ and is known. \begin{equation} ...
0
votes
0answers
13 views

Is there a proof for this result (about the inclusion $y \in [\partial h + T](x)$, with $T$ maximal monotone)?

I am trying to find a place (book, paper) which has a proof of this result: "Let $T: \mathbb{R}^n \mapsto 2^{\mathbb{R}^n}$ be maximal monotone, $\Omega \subset \mathbb{R}^n$ a closed convex set ...
3
votes
1answer
2k 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
20 views

Why is a local min also a global min for convex functions?

As the title states, for an unconstrained minimizaton problem, of a convex function, why is it that the local minimum is also the global solution?
1
vote
2answers
58 views

Lotka-Volterra First Integral and Fixed Point

I have the following problem that I am dealing with, quite a long time, I must say. Let us assume that we have a predator-prey, Lotka-Volterra system given to us by: \begin{align} & ...
2
votes
0answers
31 views

the continuity of argmin on convex funtion

Define $$x'=\text{argmin}_{x_1}f(x_1,\lambda),$$ where $f$ is a strictly convex function on $x_1$ and $\lambda$. I would like to ask if there is any theorem about the continuity of $x'$ w.r.t ...
0
votes
0answers
22 views

Non-differentiable regions of convex functions of more than one variable

I've heard that a convex function of a single variable is continuous in the interior of its domain, and is differentiable everywhere with the possible exception of a countable number of points. (I ...
1
vote
1answer
40 views

intuitive meaning of sphericity

i interested in the following definition but i don't understand it because i don't understand what mean by "flat space generated by C" . the same definition is given by i have also the same ...
7
votes
1answer
3k views

Is the trace of inverse matrix convex?

Hi I would like to know whether the trace of the inverse of a symmetric positive definite matrix $\mathrm{trace}(S^{-1})$ is convex. Actually I know that the trace of a symmetric positive definite ...
0
votes
0answers
28 views

How to prove that convex function has an increasing slope?

A function $f(x)$ in some domain $a\leq x \leq b$ is convex if and only if for any $x_1 < x_2 < x_3$ from domain $[a,b]$, $$\frac{(f(x_2)-f(x_1))}{(x_2-x_1)} \leq ...
0
votes
0answers
14 views

Prove subdifferentiable of convex lower semicotinuous function

I have read the following statement from Page 53 of Villani's book "Topics in Optimal Transportation": If $f$ is convex, lower semicontinuous, then $\partial f(x)\not=\emptyset$ for all $x\in ...
1
vote
1answer
422 views

proximal operator of infinity norm

What is the proximal operator of $||x||_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
0
votes
0answers
11 views

Question composition rules in standard deviation

Standard deviation is defined as following: $f(x) = (\frac{1}{n} \sum_{i=1}^nx_i^2-(\frac{1}{n} \sum_{i=1}^nx_i)^2)^{1/2}$ Obviously, $(.)^{1/2}$ is not convex, so can I say $f(x)$ is not ...
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} - ...
4
votes
1answer
830 views

Strictly convex sets

If $S\subseteq \mathbb{R} ^2$ is closed and convex, we say $S$ is strictly convex if for any $x,y\in Bd(S)$ we have that the segment $\overline{xy} \not\subseteq Bd(S)$. Show that if $S$ is compact, ...
0
votes
0answers
24 views

convex function - global minimum

Suppose that $f(x):R^p \rightarrow R$ is a convex function with global minimum, say 0. Let $C=(x: f(x)=0)$, i.e. the set of the global minimum. Suppose that there exist at least one point $y$ such ...
2
votes
1answer
26 views

Does $\log(f(X))$ concave implies $\log(f(X^{-1}))$ convex?

One of my professor claims that $\log f(X)$ concave implies that $\log(f(X^{-1}))$ convex where $X$ is symmetric positive definite matrix. $\log(f(X))$ is a function defined on symmetric positive ...
1
vote
0answers
21 views

Subspace of tangent feasible directions

If $h: \mathbb{R}^3 \to \mathbb{R}^3$ defined by $h(x_1,x_2,x_3) = (x_1^3 - x_2 + x_3^2, x_2,x_1+x_2+x_3)$ I define $V(x)$ as a subspace formed by all directions tangent to some constrained set at ...
0
votes
1answer
36 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!
2
votes
2answers
52 views

Minimum volume covering ellipse

Given a 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 the ...
0
votes
0answers
25 views

Subdifferential of a convex function

How would I find a convex function $f: \mathbb{R} \to \mathbb{R}$ such that $\partial f(0) = [0,1]$ A subdifferential is just the collection of vectors $w \in \mathbb{R}^n$ such that $f(y) \geq ...
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: ...
0
votes
1answer
15 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$: ...
0
votes
0answers
15 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
1answer
31 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
65 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 ...
1
vote
0answers
28 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 ...
0
votes
0answers
38 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 ...
0
votes
1answer
24 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. ...
1
vote
0answers
37 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
12 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? ...
0
votes
0answers
22 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
19 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 ...
1
vote
1answer
678 views

Convex conjugate of $\ell_1$ and $\ell_2$ norm

Given a function $f$, we can define a function $f^{*}$, called the convex conjugate (also known as the Fenchel conjugate) of $f$ as follows: $$ f^*(\vec{z})= \sup_{\vec x \in \mathbb ...
2
votes
2answers
318 views

Applications of Helly's theorem to problem solving

Helly's Theorem states the following: Suppose that $X_1,X_2,...,X_n$ are convex sets in $\mathbb{R}^d$, such that for any $|I|\leq d+1$, $\cap_{i\in I}X_i \neq \emptyset$. Then $\cap_{i=1}^{n}X_i ...
5
votes
1answer
68 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
23 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
33 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
19 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
36 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 ...
2
votes
1answer
151 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$
0
votes
1answer
390 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
44 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$ ? ( ...
1
vote
1answer
27 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
14 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
13 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 ...
2
votes
1answer
21 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 ...