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)

0
votes
0answers
7 views

Logarithmic algorithm performance

If I have an algorithm that on $T$ iterations gets me within $O(\log(T)/T)$ accuracy, what is a (preferably concise, closed form) lower bound on $T$ that gets me within $\epsilon$ accuracy? In other ...
0
votes
0answers
10 views

strong convex implies exp-concave

Prove that if f is strong convex (for some m>0) $\mbox(\nabla f(\mathbf{x})-\nabla f(\mathbf{y}))^{T}(\mathbf{x}-\mathbf{y})\geq m||\mathbf{x}-\mathbf{y}||_{2}^{2} $ then f is also ...
0
votes
0answers
18 views

Are these two definitions of an affine subspace equivalent?

I've seen the notion of an affine subspace defined differently as follows: $S \subset \mathbb R^3$, non-empty, is an affine subspace if $(1-t)u + tv \in S$ whenever $u,v \in S$. $S$ is an affine ...
0
votes
2answers
19 views

compute the smallest affine subspace containing $S$, where $S=\{(1,1,1),(2,3,4),(1,2,3),(2,1,0)\}$ is a set of vectors in $\mathbb R^3$

I've started to study convexity to enchance my optimization skills. Given a set $S=\{(1,1,1),(2,3,4),(1,2,3),(2,1,0)\}$ of vectors in $\mathbb R^3$ an exercise asks to compute the smallest affine ...
-1
votes
0answers
9 views

converting a equation to convex form which can be given to cvx solver to solve it. [on hold]

Can anybody tell me how to convert this to quadratic programming format so that CVX could solve it...?? I am not asking the whole solution but need only conversion. objective is:- minimize {sum ( ...
1
vote
1answer
15 views

Extending a convex function

Suppose $f:(a,b) \to \mathbb R$ is twice differentiable with the property that $c_1 \leq f''(x) \leq c_2$ for every $x \in (a,b)$, where $c_1, c_2$ are positive constants. Is it possible to extend $f$ ...
2
votes
1answer
33 views

Identity of the Operator Norm applied to the differential $df$ for convex $U \subset \mathbb{R}^n$ and $f \in C^1(U, \mathbb{R}^k)$

In my Analysis II Script they often use 'special' norms such as the Operator norm to make proofs more 'elegant' or just shorter. There is also the following statement (without a proof) which I can't ...
1
vote
0answers
24 views

Tangent plane of a convex set.

Given a convex set $\Omega$ in $\mathbb{R}^n$ with smooth boundary, is $\Omega$ contained completely on one side of it's tangent plane at any point on the boundary? If so, how can we prove this? ...
1
vote
4answers
66 views

Euclidean norm second derivative

I really need Your help. I need to prove that Euclidean norm is strictly convex. I know that a function is strictly convex if $f ''(x)>0$. Can I use it for Euclidean norm and how? ...
0
votes
1answer
33 views

Log-convexity preserved by sum?

I'm currently reading Boyd's book on Convex Optimization (free book which can be found here : http://stanford.edu/~boyd/cvxbook/) , and there is one proof I do not understand : p. 105, the book says ...
2
votes
1answer
29 views

Are the coefficients of a Taylor series bounded when the function is?

Say that I have three real functions $f(x)$, $g(x)$, and $h(x)$ such that $f(x)\le g(x)\le h(x)$ for all real $x$. Additionally, $f(x)$ and $h(x)$ are logarithmically convex. Can I make any definite ...
0
votes
1answer
30 views

Is this function of matrix F convex?

A scalar function $f(F)=vec(F)^{H}\Big(\Omega^{H}\big(M\otimes F(I+F^{H}F)^{-1}F^{H}\big)\Omega\Big)^{-1}vec(F)$ convex? $\Omega$ is arbitrary matrix and $M$ is positive definite. F can be reviewed ...
2
votes
0answers
12 views

Relationships between affine closures and convex closures

Let $V$ denote a vector space. Then the following concepts make sense: affine subset of $V$ affine closure (affine "hull") of a subset of $V$ Suppose $V$ is in fact a real vector space. Then the ...
1
vote
2answers
52 views

Can $\sin (x)$ be represented as difference of two convex functions?

In my optimization homework, I am supposed to prove that every differentiable function with Lipschitz continuous gradients can be represented as difference of two convex functions. I think I have come ...
2
votes
1answer
30 views

Pointwise convergence implies uniform convergence under concavity?

Suppose that $X$ is a subset of a Euclidean space and $f_n:X\to\mathbb{R}$ converges pointwise to $f:X\to\mathbb{R}$. A book I'm reading seems to say that: if $X$ is convex and compact and each ...
0
votes
0answers
36 views

Maximizing xy subject to x+y <= a x>0 and y>0, using Hessian to check concavity of f [on hold]

I wish to maximize $f$ subject to $x>0,\quad y>0,\quad x+y=a$ where $$f(x,y) = xy \quad x,y\in \mathbb{R}^n_+ $$ The Hessian did not help me so I was wondering whether I can make modifications ...
2
votes
1answer
44 views

Hint on how to proof that $x^2$ is convex

Note: I can't differentiate 2 times and prove that $f''(x) > 0$ The exercise requires me to prove that the function $f(x) = x^2$ is convex by using the following Theorem: $f(x) \ge f(x^*) + ...
0
votes
0answers
32 views

Normal Cone of a Convex Set

Is there a proof that shows that if a convex set $C \subset \mathbb{R}^n$ has smooth boundary, then the classical normal vector at a given point at the boundary is an element of the normal cone? That ...
0
votes
1answer
26 views

Convex optimization problem: linear equality and inequality constraints

When linear equality constraints can be converted in an inequality constraints for a strongly convex optimization problem? I mean, I got the same solution for both the following problem: 1) $\min_x ...
1
vote
1answer
19 views

Continuity of subdifferential mapping

I'm reading Cedric Villani's book topics in optimal transportation, and I have a problem on page 53: If $\varphi$ lower semi-continuous, then the subdifferential mapping $\partial\varphi$ is always ...
1
vote
1answer
48 views

Proof of some inquality on convex sets in $\mathbb{R}^n$

Suppose $\Omega$ is a strictly convex bounded set with smooth boundary in $\mathbb{R}^n$. If $y \in \partial\Omega$, how can we show that $$\langle(x-y),\nu_y\rangle < 0$$ for all $x \in ...
0
votes
1answer
24 views

Let S ⊂ R 2 . Show that if cl(S) is convex, then S is convex.

Let $S ⊂ R^2$. Show that if $cl(S)$ is convex, then S is convex. This seems intuitive but, I am having trouble thinking of a proof or counter example.
2
votes
1answer
24 views

How to prove convexity of a given set

I have the set $$ C_c = \{(x,y,z) \epsilon \mathbb{R}^3 : (2x-x^2+y)(2y-3z)(5x-z) > 1, |x| < 1, y > 3, z < 2\} $$ and I need to prove whether it's convex or not. I know that the ...
2
votes
1answer
36 views

Existence of complicated convex functions

In Stochastic Finance: An Introduction In Discrete Time (by Follmer, Schied), page 400, I found the following proposition: Proposition A.4. Let $I\subseteq\mathbb R$ be an open interval and ...
1
vote
1answer
14 views

Set of points at which a function coincides with its convexification is compact?

Let $f:[0,1]\rightarrow\ \mathbb{\bar{R}}$, and let $\tilde{f}$ be the convexification of $f.$ (i.e., $\tilde{f}$ is the pointwise supremum of all affine functions that lie everywhere below $f$.) Let ...
0
votes
0answers
20 views

connections between polar set, polar cone?

Given a set $S$, its polar cone http://en.wikipedia.org/wiki/Dual_cone_and_polar_cone and its polar set http://en.wikipedia.org/wiki/Polar_set are defined. Could some please tell me the ...
1
vote
0answers
24 views

Proximal operator of spectral norm of a matrix

How can I calculate the proximal operator of spectral norm for any general matrix, $X\in R^{m\times n}$ i.e., $X^* = \arg \min_X ||X||_2 + \frac{1}{2\tau} ||X-Y||_F^2$ I understand that the proximal ...
1
vote
0answers
15 views

Hahn Banach theorem and supporting hyperplane theorem

The question is out of Rudin Functional analysis Chapter 3 problem 1. Call a set $H \subset \mathbb{R}$ a hyperplane if there exists real numbers $a_1,\ldots, a_n, c$ (with $a_i \neq 0$ for at least ...
0
votes
0answers
26 views

Krein Milman Property

If a closed bounded (not compact) set $X$ in a Banach space $B$ (like $L^1$) has extreme point(s), must the max of a linear functional defined on $X$ occur at one of them? I suppose it depends on $B$. ...
0
votes
0answers
20 views

Book recommendation for Choquet theory

Assuming a good background in basic functional analysis and operator algebras, what is an appropriate text for self-study in Choquet theory?
0
votes
0answers
15 views

How to solve this entropy optimization problem with gradient projection method?

The problem is defined as $$ \min_{w} = \sum_{i=1}^{n} \sum_{j=1}^{n}\left\{ \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \log \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \right\} + \gamma \|w\|_2^2\\ $$ ...
0
votes
0answers
18 views

How to prove a set is 'norm-closed convex' [closed]

I have to prove that the given set is 'norm-closed convex.' I proved the 'convex' part. But I don't know how to prove a set is 'norm-closed' Can you tell me if there's a general approach to proving ...
-3
votes
0answers
29 views

Convex optimization problem [closed]

Can anybody tell me how to convert this to quadratic programming format...?? objective is:- minimize {sum ( $(x(i)-x(j))^2 + (y(i)-y(j))^2$ ) for $j>i$; constraints:- $x(i)+r(i) \leq (1/2)w$; ...
0
votes
0answers
19 views

Intersection of two convex lattices polygons

A convex lattice polygon is a polygon whose vertices are points on the integer lattice. Let P and Q two convex lattice polygons with n ,(resp. m) vertices. Let R be the convex lattice polygon ...
1
vote
1answer
19 views

Convex hull of set of sparse vectors?

I am trying to understand how one can define the convex hull of sparse vectors. I understand that for k sparse vectors can be described as a union of subspaces (such as in: ...
0
votes
0answers
23 views

regularity of a bivariate function

Consider a bivariate function $f(x,y)$ which is concave in $y$. Moreover, for any given $y$, let $x^*(y)$ be the solution to $f_x(x,y)=0$, and there is $f_x(x,y)>0$ for $x<x^*(y)$ and ...
1
vote
0answers
23 views

Proximal operator for the nuclear norm of Hankel (x)

I have a problem in hand for which I need to compute the proximal operator of the composite function $||Hankel(x)||_{nuc}$ where $x \in R^N$ and $||.||_{nuc}$ denotes the matrix nuclear norm. For a ...
1
vote
1answer
42 views

How to use convexity in this step?

I am trying to fill in the details of a proof about the following statement: If $f:\mathbb{R}^n\to \mathbb{R}$ be a convex function, if subdifferential of $f$ at $x$ is singleton, then $f$ is ...
1
vote
3answers
49 views

Proving that the second derivative of a convex function is nonnegative

My task is as follows: Let $f:\mathbb{R}\to\mathbb{R}$ be a twice-differentiable function, and let $f$'s second derivative be continuous. Let $f$ be convex with the following definition of ...
0
votes
0answers
15 views

Continuity of convex function [duplicate]

Let $f$ be a proper convex lower semi-continuous function on $\mathbb R^n$, how can we prove $f$ is continuous in the interior of $Dom(f)=\{f<\infty\}$ ?
1
vote
2answers
41 views

If $f$ is midpoint convex, continuous, and two times differentiable, then for any $a, b \in \mathbb{R}$, there exists $c$ such that $f''(c) \geq 0$

One of my analysis texts states this as an exercise If $f$ is midpoint convex, continuous, and two times differentiable, then for any $a, b \in \mathbb{R}$, there exists $c \in [a, b]$ such that ...
2
votes
1answer
37 views

Non-trivial lower bound approximation of a convex function using the second derivative at the minimum

Say that I am given an infinitely differentiable convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$. I am wondering if I can construct a meaningful lower bound approximation of $f$ using it's ...
1
vote
0answers
36 views

Expectation of an increasing, bounded concave function of a non-negative random variable

Let $h:[0,\infty)\to [0,1)$ be a strictly increasing and strictly concave function. Let the argument of this function be a random variable $C$ with probability density function (pdf) $f_{C}(c)$ with ...
0
votes
0answers
21 views

Notion of positive third derivative for nondifferentiable functions?

Are there any notions that generalize the idea of a positive third derivative of a univariatve function to those for which the function is not necessarily differentiable? For example, a function ...
1
vote
0answers
16 views

Intersection numbers on blow ups of toric varieties

Suppose we have a smooth, complete toric varietiy $X_{\Sigma}$ of dimension $n$. Let $\sigma_k \in \Sigma(k)$ a smooth $k$-dimensional cone in $\Sigma$ and suppose we make the toric blow up at the ...
2
votes
1answer
34 views

Constructing a quasiconvex function

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called convex if $$ f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, ...
3
votes
1answer
50 views

How can I prove the hypersurface $M$ is neither convex nor concave?

The question is so simple: how can I prove that $M$ (as defined below) is neither convex nor concave (in the real sense)? The point here is to define a new notion of convexity, the complex convexity, ...
1
vote
1answer
37 views

finding discrète coordinate of Intersection of two convex polygon?

I seek for cartésien coordinate of vertex's of the intersection area between two polygons ? We have two convex polygon's P & Q such that : all vertex of P (resp. Q) are in 2D cartésien plane. I ...
2
votes
0answers
161 views

An improvement of Jensen's inequality - help please!

It would nice if someone could help me with this problem. I am looking at an improvement to the classical Jensen's Inequality: $$\int_\limits{}^{} \phi(x) \mu \mathrm{d}x \geq ...
1
vote
2answers
45 views

Is the optimum of this problem unique?

I have a convex optimisation problem: $$\min_{x_i} \sum_{i=1}^N a_i \exp(-x_i/b_i)\quad\text{ s.t. }\sum_{i=1}^N x_i=x\text{ and } x_i\ge 0$$ The KKT conditions are: $$\lambda=\begin{cases} ...