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
10 views

Directions of sublevel sets ofa convex function

Let $f:\mathbb R^n \rightarrow \mathbb R$ be a convex (continuous ) function. Let's assume that some sublevel set $L_a:=\{x\in \mathbb R^n : f(x) \leq a\}$, where $a \in \mathbb R$, contains a ...
6
votes
1answer
290 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
0answers
14 views

Relation between recesion directions of a sublevel set and epigraph

It is known that if a convex set $C\subset \mathbb R^n$ contains a halfline $\{p+tu: t\geq 0 \}$ with initial point $p\in C$ and direction $u\in \mathbb R^n$ then for each $q\in int C$ the set $C$ ...
1
vote
0answers
14 views

Existence criterion for solution in quadratic programming

I have the problem $$ \begin{align*}\min \quad&f(x)= c^Tx + x^TQx \\ &x\in D \end{align*}$$ with $D=\{ x \in \mathbb{R}^n \mid Ax \leq b\}$, $A,Q\in \mathbb{R}^{n\times n}$ and $b,c \in ...
2
votes
2answers
56 views
+50

Distributed Convex Optimization Algorithm

Consider the convex optimization problem $$ \min_{x_1, \cdots, x_N, y} \sum_{i=1}^{N} f_i(x_i,y) $$ $$ \text{subject to: } x_i \in X_i \ \ \forall i, \ \ y \in Y, \ \ y = \sum_{i=1}^{N} x_i $$ ...
0
votes
0answers
29 views

Shrinkage operator for matrices

Here http://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf, on page 188, you can see the derivation of the soft thresholding operator or shrinkage operator for the case of vectors using Moreau ...
0
votes
0answers
7 views

Is quadratic over linear convex for matrices?

Is there a jointly convex quadratic over linear form, for matrix variables? Something like $f(X,C) =\text{trace}({XC^{-1}X'}$)? Is it convex?
0
votes
1answer
22 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
1answer
57 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 & ...
0
votes
0answers
186 views

Curvature and intersection of convex functions

Take two weakly convex, weakly increasing non-negative functions, $g(x)$ and $h(x)$, domain of $x$ is $[a,d]$, $g(x)=0$ for $x \in [a,b]$, $h(x)=0$ for $x \in [a,c]$, and $g(d)=h(d)$. So $g$ and $h$ ...
-2
votes
3answers
216 views

There is a ray from each point of unbounded convex set that is inside the set.

Let $A$ be a non-empty convex, unbounded set in $\mathbb R^n$. Prove that for each point $a \in A$, there is a non-zero vector $h \in \mathbb R^n$ such that $l = \{x \in \mathbb R^n \mid x=a+th,\ ...
0
votes
0answers
19 views

Fréchet normal cone

Given $x\in \Omega(\subset X)$ (X: Banach space) and $\varepsilon\geq 0$, the set of $\varepsilon-$normals to $\Omega$ at $x$ by \begin{align} \widehat N_\varepsilon(x;\Omega):=\left\{x^*\in X^*\mid ...
1
vote
1answer
29 views

Convex Combination of 3 point in R2 and Triangle

I am new to convex combination, and I am quite amazed by some easy result. I know that convex combination of 2 points($P_1P_2$) in $R^2$ is all points in the line segment $P_1P_2$. And then I see a ...
0
votes
1answer
33 views

Common subdifferentials of convex function

Let $f: \mathbb R^n \rightarrow \mathbb R$ be a convex function. By a subdifference of $f$ in $x\in \mathbb R^n$ we mean an $h\in \mathbb R^n$ such that $f(x) \geq f(p)+<x-p,h>$ for all ...
2
votes
0answers
20 views

Convex interpolation between two points with given derivatives

Let's say I have two real values $x_1$ and $x_2$, to each of which I associate $y_i$ and $y'_i$ satisfying $$ (y_2-y_1)(y'_2 - y'_1) \geq 0. \tag{1} $$ I would like to find a polynomial ...
0
votes
1answer
32 views

Interesting and intuitive affirmation involving convex sets

Let $\Omega_1$ and $\Omega_2$ two open, bounded and convex domains in $R^n$ with $\Omega_1 \supset \overline{\Omega_2}$ and $0 \in \Omega_2.$ Suppose that for each $x_0 \in \partial (\Omega_1 ...
0
votes
0answers
17 views

Firm non-expansiveness in the context of proximal operators

$\newcommand{\prox}{\operatorname{prox}}$ Probably the most remarkable property of the proximal operator is the fixed point property: The point $x^*$ minimizes $f$ if and only if $x^* = \prox_f(x^*) ...
0
votes
0answers
13 views

What is the nature of this one dimensional function?

Let $\mathcal{S}$ be a 2-D convex set whose elements can be represented as $(x,y)\in\mathcal{S}$. Let $p_L$ and $p_U$ be two real constants such that $p_L\leq p_U$. For $p\in[p_L,p_U]$, I define the ...
1
vote
1answer
265 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?
1
vote
0answers
43 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 ...
0
votes
1answer
56 views

$F(x) = f(x) + g(x) + h(x)$, where h(x) is strongly convex , is also strongly convex

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ $\newcommand{\Tr}{\operatorname{Tr}}$ Suppose $g: \mathbb{R}^n \rightarrow \mathbb{R}$ is a continuous convex ...
1
vote
2answers
25 views

Suitable composition of concave and convex functions is convex?

Let $f:[0,1]\to[0,1]$ be a strictly increasing continuous concave function with $f(0)=0$ and $f(1)=1$. Let $g$ be the inverse of $f$. Then $g$ is strictly increasing and convex. It seems that the ...
0
votes
2answers
31 views

Basic question about tangent cone

The following is from Prof. Jahn's book " Intro. to the theory of nonlinear optimization" about tangent cone: After definition, he gave an example: My question is: Does the tangent cone include ...
5
votes
1answer
81 views

Continuous linear image of closed, bounded, and convex set of a Hilbert Space is compact

Is my proof of this proposition correct ? And is this proposition well known? Proposition: Let $C$ be a closed, bounded, and convex set in a separable Hilbert space $H$. Let $L : H \to \mathbb{R}^n$ ...
1
vote
1answer
25 views

Convolution of Strictly Convex Function

Let $f:\mathbb{R}\rightarrow \mathbb{R}$ be a $C^2$, strictly convex function, and $\theta_\epsilon$ the standard approximation to identity ...
0
votes
0answers
29 views

No element in the convex hull of other elements [closed]

Consider a set $A$. If there is no element $a_i \in A$ lies in the convex hull of the other elements $\text{conv}(A\backslash \{a_i\})$.... Could anyone give me an simple example for this ...
2
votes
2answers
38 views

Is the distance between disjoint closed convex subsets of a Hilbert space positive? Is it attained?

Let $H$ be an infinite dimensional and separable Hilbert space. Let $A,B$ be infinite, closed and convex subsets of $H$. If $A$ and $B$ are disjoint and if at least one of them is bounded, is the ...
3
votes
2answers
251 views

How to prove that the following function is convex?

I want to prove convexity of the following function: $$f(x) = log_x \left(1 + \frac{(x^a-1)(x^b - 1)}{x-1}\right)$$ for any fixed $a, b \in (0, 1)$ and: $x\in(0,1)$ $x\in(1, \infty)$ I'm trying ...
0
votes
1answer
27 views

Subtracting a constant from log-concave function preserves log-concavity, if the difference is positive

I am trying to work out a question from 'Convex Optimization - Boyd' . Specifically, exercise 3.48: Show that if $f : \mathbb R^n \to \mathbb R$ is log-concave and $a > 0$, then the function $g ...
2
votes
1answer
35 views

Affine to linear like conversion of a concave function

Is the following true: $$\log \left( \frac{1}{f(x)+K}\right)\mathrm{is\;concave}\Longleftrightarrow \log \left( \frac{1}{f(x)}\right)\mathrm{is\;concave},$$ where $K\in\mathbb{R} $ and ...
2
votes
1answer
61 views

Point-wise converging convex functions on $[0,1]$

Suppose we have a sequence of continuous convex functions $\{f_n\}$ defined on $[0,1]$ which converge point-wise to a limit $f$ on $[0,1]$, i.e. for all $x \in [0,1]$ $$\lim_n f_n(x) = f(x).$$ Let $G ...
0
votes
1answer
565 views

generalized inequalities defined by proper cones

The generalized inequality defined by a proper cone $K$ is that $x \ge_{K} y$ if $x-y \in K$ for $x,y \in K$. Does this means that for any $x \in K$, we have $x \ge_{K} 0$ since $x - 0 = x \in K$ ? ...
0
votes
1answer
212 views

Checking convexity

I know that the function $(\mathbf{a}-\mathbf{b})'(\mathbf{a}-\mathbf{b})$ is convex in $\mathbf{a}$ ($\mathbf{a}$ and $\mathbf{b}$ are vectors, not scalars). Would ...
0
votes
1answer
19 views

Do full-rank linear transformations preserve strong convexity?

Consider a strongly convex function $g$, that is, for all $x,y$ in the domain and $t\in[0,1]$ we have $$ g(t x + (1-t)y) \le tg(x)+(1-t)g(y) - \frac{1}{2}mt(1-t)||x-y||_2^2 $$ for some $m>0$. Also, ...
6
votes
3answers
238 views

Dual norm intuition

The dual of a norm $\|\cdot \|$ is defined as: $$\|z\|_* = \sup \{ z^Tx \text{ } | \text{ } \|x\| \le 1\}$$ Could anybody give me an intuition of this concept? I know the definition, I am using it ...
0
votes
0answers
18 views

Convex Inequality describing Functions inside specific area

Let us assume that we have two functions $f_1$, $f_2:[0,1] \rightarrow \mathbb{R}^{2}$, which describe each a point trajectory on the plane. Let us further assume that we parametrize those functions ...
0
votes
0answers
19 views

Intuitive affirmation on convex sets

Let $D_1, D_2$ two open, bounded and convex domain in $R^n$. Suppose that $D_2 \supset \overline{D_1}$, and the boundaries of these sets are of class $C^1$. Fix $x \in \partial D_1$ and suppose that ...
1
vote
1answer
40 views

Prove that $f(x) > g(x)$ where both functions are convex and have the same value and slope at $0$

Let $f: [-a,a] \to \mathbb{R}$ and $g: [-a,a] \to \mathbb{R}$ be two non-negative, convex and smooth functions. We further know $f(0) = g(0)=0$ and $f'(0) = g'(0)=0$. I'd like to show $$f(x) \ge ...
0
votes
0answers
28 views

Proving concavity for complicated function

I have a rather complicated function, $f$, that I am trying to demonstrate is log-log-concave, i.e., $$\frac{d^2\log f}{(d\log x)^2}\leq 0.$$ The reason I think it is concave is purely heuristic. ...
1
vote
2answers
141 views

The distribution of barycentric coordinates

Let $\mathcal{X} = \{x_1,\dots,x_n\} \subset \mathbb{R}^d$ and let $Z$ be a random variable uniformly distributed over convex hull of $\mathcal{X}$, denoted as $\text{conv}(\mathcal{X})$. Assuming ...
0
votes
1answer
22 views

Is strict convexity necessary and sufficient for non-degeneracy of the Hessian?

A function $f$ is called strictly convex if for $\lambda\in(0,1)$, $x\neq y,$ $$f(\lambda x + (1-\lambda)y) < \lambda f(x) + (1-\lambda)f(y)$$ If $f:\mathbb{R}^n\to\mathbb{R}$ is a twice ...
0
votes
1answer
10 views

How to derive the support function for this set?

I want to ask how to derive the support function of the convex set (in $\mathbb{R}^2$) that is described as the intersection of $x_1\leq \frac{3}{4}$, $x_2\leq \frac{3}{4}$, $x_1+x_2\leq 1$, and ...
0
votes
1answer
419 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 ...
0
votes
1answer
301 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 ...
1
vote
2answers
51 views

Prove that $f(x+h)-f(x) - \langle\nabla f(x), h\rangle\geq 0 \Rightarrow f $ convex

At this link there is a demonstration that for $f$ continuously differentiable on $C \subseteq \mathbb{R}^n$ convex, $f(x+h)-f(x) - \langle\nabla f(x), h\rangle\geq 0 \Rightarrow f $ convex. This ...
3
votes
1answer
38 views

Generalization of log-convexity (log-concavity): log-log-convexity (log-log-concavity)?

$\underline{\mathrm{Background\; on\; function\; Convexity}}$ A function, $f$, is convex if: $$f( x\theta+y(1-\theta) ) \leq \theta f(x) + (1-\theta)f(y).$$ $f$ is concave if $-f$ is convex, [1]. If ...
1
vote
1answer
25 views

Difference quotients are increasing for $f$ convex

Problem 11A.9(c) in Spivak's Calculus (4th edition) asks the following (I'm paraphrasing): Suppose $f$ is convex. Show that $f'(a)$ exists iff $f_+'(x)$ is continuous at $a$. ($f_+'(x)$ is the ...
17
votes
2answers
316 views

Convex surface on which any two points $a,b$ can be joined by a curve of length $(\pi/2-\epsilon)|a-b|$

I am trying to solve an exercise on page 13 of the book Metric structures on Riemannian and non-Riemannian spaces by Gromov. Construct a closed, convex surface $X$ in $\mathbb R^3$ such that any ...
1
vote
1answer
36 views

Prove that a Hilbert space is convex of power type $2$

Let $X$ be a Banach space. For $\epsilon \in (0,2]$, define: $$\delta_X(\epsilon) = \inf_{x,y \in X}\{1 - \|\frac{1}{2}(x + y)\| : \|x\| = \|y\| = 1, \|x-y\| \ge \epsilon\}.$$ Then we say that $X$ ...
2
votes
1answer
44 views

Are strictly convex functions with positive second derivatives on compact domains strongly convex?

Claim: Let $\chi$ be a compact set. If $f''(x)>0$ for all $x\in\chi$, then $f$ is strongly convex. This seems to be true, intuitively, as I can't think of a counterexample. All of the examples ...