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
2answers
1k 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
21 views

Why does $f$ being convex and twice continuously differentiable imply that the domain of $f$ is open?

On the slide here: It says: $f: \mathbb{R}^n \to \mathbb{R}$ is convex and twice continuously differentiable imply that the domain of $f$ is open What is the reason behind the implication? Is it ...
1
vote
1answer
40 views

Equivalent formulation of linear discrimination problem on Boyd convex optimization slides

In Boyd's CVX slides on pg 189 he has the linear discrimination problem http://stanford.edu/class/ee364a/lectures.html Given data $\{x_1, \ldots, x_n\}$, $\{y_1, \ldots, y_n\}$ The problem of ...
2
votes
1answer
51 views

Geometric interpretation of monotone operators on a Hilbert space

Recall that a monotone operator is defined by the relationship as follows: $$\langle y - x, F(y) - F(x)\rangle \geq 0, \quad \forall x,y \in X$$ ($X$ is a Hilbert space) What is a good geometric ...
0
votes
0answers
42 views

Recall that in the context of Fenchel–Rockafellar duality, the primal problem is defined by

Let X and Y be two Hilbert spaces. Let $f : X \rightarrow ]-\infty, +\infty]$ be convex and lower semicontinuous, let $A : X \rightarrow Y$ be linear, and let $g: Y \rightarrow ]-\infty,+\infty]$ be ...
0
votes
1answer
34 views

Let $a_1,\ldots,a_m$ be elements of $\mathbb{R}^n.$ Then the convex cone $K_{\Omega}$

I am having a problem with one aspect of the following proof I came across in "An Easy Path to Convex Analysis and Applications" by Mordukhovich and Nam. It is Proposition 3.9 and it is the line ...
0
votes
0answers
32 views

Find the distance between two convex sets

Let's say that ||.|| is an Euclidian norm in $R^3$ and we have two sets in $R^3$ defined by inequalities: $Y = \{y| f(y)<a\}, Z = \{ z| g(z)<b \} $ Let's say that $f$ and $g$ are convex and ...
0
votes
0answers
61 views

Explain why the function $f(x)=\frac{1}{2}(x-d)^2+\alpha|x|$ is strictly convex.

Let $d\in\mathbb{R}$ and $\alpha>0$ be given. (i) Explain why the function $f(x)=\dfrac{1}{2}(x-d)^2+\alpha|x|$ is strictly convex. (ii) verify that \begin{equation} ...
0
votes
0answers
12 views

bounding the hausdorff distance between a convex set and a template polytope.

How can we find an upper bound on the hausdorff distance between a convex set and its enclosing template polytope whose facets directions are given in advance?? Note that the bound should tend to zero ...
3
votes
0answers
52 views

How to prove the matrix fractional function is convex by definition

It is well known that the matrix fractional function $f(\mathbf{w},\boldsymbol{\Omega})=\mathbf{w}^T\boldsymbol{\Omega}^{-1}\mathbf{w}$ is jointly convex with respect to $\mathbf{w}$ and ...
0
votes
0answers
48 views

Show that $f + g$ is still strictly convex.

Let $d \in X$ and set $$f: X \to \mathbb{R}: x \mapsto \left(\frac{1}{2}\right) \parallel x-d \parallel^2.$$ Use (*) to show that $f$ is strictly convex. Now let $g$ be any convex function. Show that ...
19
votes
1answer
761 views

How many points of intersection between an ellipse and an $L_p$-circle?

Consider an ellipse $E$ in the plane, centered at the origin. (In my case, the minor axis points into the nonnegative quadrant.) Let S be an "$L_p$-circle": $S = \{(x,y) : |x|^p + |y|^p = 1\}$, ...
0
votes
2answers
39 views

Given $\min\limits_x \|x\|_2^2 \quad \text{s.t.} \quad Ax = b$ show $x^* = A^T(AA^T)^{-1}b$

Given $$\min\limits_x \|x\|_2^2$$ $$\text{s.t.} Ax = b$$ show $x^* = A^T(AA^T)^{-1}b$ where $A \in \mathbb{R}^{m \times n}, m < n$ This is projection $x$ onto the hyperplane $Ax - b = 0$ ...
0
votes
1answer
38 views

Let $f:\mathbb{R}^n\rightarrow ]-\infty,+\infty]$ be proper and strictly convex. [duplicate]

Let $f:\mathbb{R}^n\rightarrow ]-\infty,+\infty]$ be proper and strictly convex. Show that $f$ has at most one minimizer. I am hoping someone can give me some feedback on the proof for this. I feel ...
1
vote
1answer
63 views

Examples of $f$ strictly convex, either with one minimizer or with no minimizer.

Let $f\colon X \to [ -\infty, +\infty]$ be proper and strictly convex. Show that $f$ has at most one minimizer. Give examples where $f$ is strictly convex, and either (i) $f$ has one minimizer; or ...
0
votes
0answers
13 views

Proof that a set is a closed convex cone given feasible directions

I have some problems trying to show the following problem. Could you guys please lend me a hand? Let $d_1$, $d_2$ $\in$ $\bf{R}$$^2$ two linearly independent vectors. Consider the rays that begin ...
1
vote
1answer
45 views

Gradient of the form $(\textbf{x}-\textbf{x}_k)^TA(\textbf{x}-\textbf{x}_k)$

In the context of a convex optimization problem I came across with the following function: $$f_1(\textbf{x})=(\textbf{x}-\textbf{x}_k)^T\textbf{A}(\textbf{x}-\textbf{x}_k) - t^2$$ EDIT $f_1$ is a ...
0
votes
1answer
54 views

Is this function strongly convex? or could I find a value space to make this function strongly convex?

I want to judge if this function $f(x_1,x_2,...,x_n)=(\frac{x_1}{\sum_{i=1}^{n}{x_i}})^2+(\frac{x_2}{\sum_{i=1}^{n}{x_i}})^2+...+(\frac{x_n}{\sum_{i=1}^{n}{x_i}})^2$ strongly convex for each ...
2
votes
1answer
53 views

Prove that a polytope is closed

Let the polytope defined by $$S:=co \left\{ x_1,x_2,...,x_k \right\}$$ where $x_1,x_2,...,x_k \in \mathbb{R^n}$ and $co \left \{... \right \}$ is the convex Hull. Prove that S i closed. I tried the ...
2
votes
1answer
312 views

Any example of strongly convex functions whose gradients are Lipschitz continuous in $\mathbb{R}^N$

Let $f:\mathbb{R}^N\to\mathbb{R}$ be strongly convex and its gradient is Lipschitz continuous, i.e., for some $l>0$ and $L>0$ we have $$f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{l}{2}||y-x||^2,$$ ...
0
votes
1answer
27 views

what's the relation between such a convex set and it's extreme points:

A little silly question: if A is a convex body and A is NOT a convex polytope, does this mean that the number of the extreme points of A is infinite?
0
votes
1answer
21 views

How to transform between two ellipsoid representations

Claim: $\mathcal{E}(x_c, 1) = \{x|(x - x_c)^T P^{-1} (x-x_c) \leq 1\}, P \in S^n_{++}$ has an alternative representation as: $\mathcal{E}(x_c, 1) = \{x|\|Ax+b\|^2 \leq 1\}, A \in S^n_{++}$ What ...
3
votes
0answers
31 views

If $16$ equal isosceles right triangles are combined into convex polygon then rational side of one does not lie along irrational side of another

How can we prove, using algebra, that if $16$ equal isosceles right triangles are combined into a convex polygon, then a rational side of one triangle does not lie along an irrational side of another? ...
0
votes
1answer
28 views

Prove that a function is convex by only using positive semi-definiteness

let $x \in \mathbb{R}^n$ where $f(x) = (1 + ||x||^2)^{1/2}$. Prove that it is convex. As of right now, we define a convex function to be a function with a positive semi definite second derivative. So ...
2
votes
1answer
25 views

nullity of a convex combination of matrices

I have the following question. Given two matrices of the same dimension $A, B\in \mathcal R ^{m\times n}$ , and consider a third one given by a convex combination of them $$ C = c_1 A + c_2 B $$ $c_1 ...
0
votes
1answer
27 views

How to extract the positive semidefinite part of a matrix

Motivation: We wish to make an second order approximation of a nonconvex function $f(x), x \in \mathbb{R}^n$ such that it is convex, however we do not have guarantee that $\nabla^2 f(x)$ is convex ...
0
votes
1answer
25 views

Problem with showing convexity of a function

I want to show that $f_n(\zeta) = \frac{1}{n} \log \sum_{w \in W_n} e^{\zeta K_n(w)} P_n (w)$ , with $\zeta \in \mathbb{R}$ is convex. I will not explain what $W_n, K_n$ and $P_n$ are, because this is ...
0
votes
1answer
31 views

Direct sum of convex sets is convex

Let $S_1 \subseteq \mathbb{R}^n$ be a compact convex set and let $S_2 \subseteq \mathbb{R}^n$ be a closed convex set. Prove that then $A=S_1 \oplus S_2$ is convex. Here is my attempt, where I havent ...
0
votes
0answers
35 views

The dual norm of a operator matrix norm

Let as look at matrices $B$ in $\mathbb{R}^{p\times q}$ together with the following operator norm: $$||B||_{op}:=\max_{\beta}\frac{|B\cdot \beta|_{p}}{|\beta|_{q}}.$$ Here $|\cdot|_{p}$ is any norm on ...
2
votes
0answers
33 views

Optimizing a convex combination

Assume that functions $f_i:X\to\mathbb{R}$ are fixed among weights $\alpha_1,...,\alpha_n$ with $\sum_i \alpha_i=1$, and assume that each function $f_i$ is maximized at a point $x_i\in X$, i.e. ...
0
votes
1answer
28 views

Closed convex set as the intersection of (tangent) half spaces

Theorem 18.8 in the book by Rockafellar establishes that any $n$-dimensional closed convex set $C$ in $R^n$ can be expressed as the intersection of the closed half spaces tangent to $C$. See here for ...
2
votes
1answer
29 views

Hahn-Banach separation theorem with a countable subset of functionals

For a separable Banach space $X$, the unit sphere of $X^*$ always contains a countable set $D$ such that $$ \left\Vert x \right\Vert = \sup_{f \in D} \left\vert f(x) \right\vert \qquad \mbox{ for ...
1
vote
0answers
87 views

Equidistant sets and extremal points

Let $\lVert\cdot \rVert$ be any norm on $\mathbb{R}^n$ and let $x\in \mathbb{R}^n$ be a point. Let $\textrm{ext}(B_{\lVert x\rVert})$ denote the set of all extremal points of $B_{\lVert x ...
0
votes
1answer
19 views

Convex conjugate of l1 norm function with weight

The conjugate of $f(x)=\|y\|_1$ is, by definition, $$ f^*(z) = \sup_y \{y^Tz - \|y\|_1\} $$ Also we can write $$f(y)=\|y\|_1 = \max_{\|p\|_\infty\leq 1} y^Tp $$ By using this, we can get the ...
0
votes
1answer
37 views

The distance is attained by a unique point

Theorem: Let $K$ be a convex and closed subset of a Hilbert space $X$ and $x \in X$. Then there is a unique $y_x \in K$ such that $$\|x-y_x\|=d(x,K):=\inf \{\|x-y\|: y \in K \}$$ Remarks: if $K$ ...
2
votes
1answer
65 views

Minkowski functional of a convex set is a convex function.

Let $X$ be a real vector space, and $K$ be a convex set with $2$ properties: $0\in K$ and $\forall x\in X, \exists t >0$ s.t. $x/t\in K$. Define the Minkowski functional of the set $K$ to be ...
0
votes
1answer
34 views

Let $f:X\rightarrow ]-\infty,+\infty]$, let $b\in x$ and let $c\in X$. Find Fenchel conjugates of the functions:

Let $f:X\rightarrow ]-\infty,+\infty]$, let $b\in x$ and let $c\in X$. Find Fenchel conjugates of the functions: $(i)\;\;\;\; f(x)+\langle c,x\rangle,$ $(ii)\;\;\;\; f(x-c).$ For (i) I'm thinking ...
1
vote
0answers
55 views

Problems with Proof of Jensen's Inequality (Durrett's “Probability Theory and Examples”)

I have some questions concerning the proof of the Jensen's Inequality I found in Durrett's "Probability Theory and Examples" [pp.23-24]. In the following there is the proof, with the questions I have ...
0
votes
2answers
23 views

Examples of $C^1$ differentiable convex functions.

Could you please provide examples of convex functions that are differentiable, but their derivatives are not differentiable.
3
votes
1answer
36 views

Is the function determinant $A \rightarrow \det(A)$ a non-convex fuction?

Is the function $$ \det: A\in \mathbb{M}^{n \times n}(\mathbb{R}) \rightarrow \det (A)$$ a convex function? I think the answer is no, but I cannot prove it directly using the definition of convex ...
1
vote
2answers
88 views

Is the algebraic interior relatively open in a closed convex set?

I am struggling with proving or disproving the following: Let $X$ be a locally convex space and let $C\subset X$ be closed convex with non-empty algebraic interior which we denote by $C^i$ (recall ...
0
votes
0answers
15 views

notions of geometry needed for optimization

Could you tell me the notions of geometry (not topology) that are needed before starting courses on convex analysis and optimization ? Thank you.
0
votes
0answers
15 views

Follow up question for: Convexity of the product of two functions in higher dimensions

The question referred to in the title ( Convexity of the product of two functions in higher dimensions) is already answered. However I have a question regarding the answer and I am not able to post it ...
-1
votes
1answer
44 views

Suppose that $X=\mathbb{R}^n$ and that $K=\mathbb{R}_{+}^{n}$.

Suppose that $X=\mathbb{R}^n$ and that $K=\mathbb{R}_{+}^{n}$. using the definition of the Fenchel conjugate verify that $\iota_{K}^{*}=\iota_{-k}$ where $\iota_{K}$ is the indicator function. my ...
1
vote
0answers
26 views

Proving Convexity for a function $f(x) = \frac1{g(x)}$?

So I have a function $g$ that maps from some subspace, $S$, of $\mathbb{R}^n$ to $\mathbb{R}$. $g$ is concave such that $g(x) > 0$ for all $x$ in this subspace, $S$, of $\mathbb{R}^n$. $f(x)$ is ...
0
votes
1answer
38 views

Formulate the dual problem for primal problem with absolute value constraint

Let $y \in R$, the goal is to find the dual problem to: $$\min y\\ s.t. |y| \leq 0$$ The lagrangian of the problem is: $$L(y, \lambda) = y + \lambda|y|$$ The dual function is: $$g(\lambda) = ...
0
votes
0answers
27 views

Non-binding constraints with positive shadow prices (matlab)

The output of fmincon indicates positive shadow price for linear constraints, although the corresponding constraints are not binding. What could be wrong mathematically? I've checked the code but ...
1
vote
1answer
32 views

Prove that if g,h convex functions and g is positive ,then (goh) is a convex function ,too.

So, I am stuck and I can't think of an answer to the question above. Any help? Note : g is convex and positive and h is just convex.** We want to prove that (goh) is convex** Note2 : We do not know ...
0
votes
2answers
35 views

Convex hull of finite union of closed sets

Suppose $C_1,\cdots,C_n$ are closed, compact, convex subsets of a locally convex topological vector space, then is $\text{Conv}(C_1 \cup \cdots \cup C_n) = \overline{\text{Conv}(C_1 \cup \cdots \cup ...
1
vote
0answers
35 views

Convexity of the log barrier function

Let's consider the following convex optimization problem of minimizing the log barrier function: $$\min_{\textbf{x}\in \Re^n}f(\textbf{x})=\min_{\textbf{x}\in ...