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

To check whether a function is concave or convex or neither.

Let $\pi$ be a vector such that all its elements sum to 1. i.e, $\sum_1^n \pi(i) = 1$ where $\pi(i)$ denotes the i$^{th}$ component and $n$ is the length of the vector. Let $D$ be a diagonal matrix ...
0
votes
0answers
20 views

N-Functions (Nice Young functions)

A mapping $\Phi:[0,\infty)\to[0,\infty)$ is termed an N-function (nice Young function) if (i) $\Phi$ is continuous on $[0,\infty)$; (ii) $\Phi$ is convex on $[0,\infty)$; (iii) $\lim\limits_{t ...
0
votes
0answers
14 views

Second-order quadratic model with bias term

I have 3 points in the 3-d space and I would like to estimate the parameters of a second-order quadratic model with a bias term $z=f(x,y)=ax^2+bxy+cy^2+dx+ey=\theta^TQ\theta+\eta^T\theta$ where the ...
1
vote
1answer
27 views

does constant convexity assures global minimum

I have the following question: Consider a function $f:R^n \longrightarrow R$, s.t.: there is a point $x_0 \in R^n$ s.t. $\frac{\partial f}{\partial x^k} =0$ $\forall k$. the hessian matrix ...
1
vote
2answers
39 views

Why is the constraint $\|w\| = 1$ non-convex?

Related: Why is this function, related to SVM derivation, non-convex? I am studying notes which cover the derivation of SVM. The intuition is the geometric margin should be maximized in order to ...
0
votes
1answer
17 views

Clustering of vectors via inner product relationship

This might be an odd question, but suppose I have a lot of vectors $a_i\in\mathbb{R}^{3}$ (not necessarily unit) and for some unit vector $u\in\mathbb{R}^{3}$ I find $$ \sum_{i=1}^m ...
1
vote
0answers
12 views

Orthogonal Projection of an arbitrary point on the rectangle and the Lorentz cone

I want to know how to find the orthogonal projection of an arbitrary point on the rectangle and the Lorentz cone. I need to know the derivation or the concept not just the formulae which are available ...
6
votes
3answers
4k views

How $x^4$ is strictly convex function?

I hear that $f(x)=x^4$ is a strictly convex function $\forall x \in \Re$. However, strict convexity condition is that the second derivative should be positive $\forall x \in \Re$. For the mentioned ...
0
votes
2answers
30 views

how to show that$ n<{2n \choose n}$ in sets

what can be some methods to prove and explain $$n<{2n \choose n}$$ is true , Iam having diffuculty is proving and explain it though it seems easy . please can anyone help me with my small problem ...
0
votes
1answer
23 views

Characterize polytopes resulting from cutting a convex polytope by a hyperplane

We have a convex polytope $P$ for which we know its set of vertices. Using this set we characterize the H-representation of $P$ as: $\mathbf{A}\mathbf{x} < \mathbf{b}$. If a hyperplane defined by ...
0
votes
1answer
36 views

Estimation of Quadratic form parameters and convexity/concavity surface

I have 3 points in the 3-d space with their coordinates $(x~y~z)^T$. I would like to find the expression of the $\textbf{concave}$ quadratic surface that form those 3 points, i.e., $z=f(x,y)=ax^2 + ...
0
votes
0answers
59 views

Intersection between a hyperplane and a convex polytope [on hold]

We work over $\mathbb{R}^N_+$, where $N \ge 2$. We are facing a situation in which we need to find the intersection between a hyperplane and a convex polytope. In detail, let $V$ be the set of ...
1
vote
1answer
32 views

Why is this function, related to SVM derivation, non-convex?

I'm working through a support vector machines tutorial. In eventually deriving the solvable objective function, the following objective function (to be maximized) was proposed, but dismissed as ...
0
votes
0answers
12 views

Deriving Dual Averaging from (Sub)gradient Descent

Here the presenter tries to derive a simple Dual Averaging from (sub)gradient descent. I have a little problems understanding the steps. (Sub)gradient descent: Loop through: $$ x_{k+1} = x_k - t_k ...
1
vote
1answer
22 views

Can a compact set of $\mathbb{R}$ have some properties and not being convex

The question is related to this one On a condition when bounded sets in R n is convex ?. Suppose that $n > 1 $ and that $C \subset \mathbb{R}^n$ is a compact (closed and bounded) set having a ...
0
votes
1answer
297 views

Convex function and its epigraph PROOF

Can someone help prove this statement. Consider a function $f:R^{n} \to R$ and epi $f$ = {$(x,t) \in R^{n+1}$: $x \in R^{n}$, $t \geq f(x)$} A function is convex if and only if its epigraph is a ...
4
votes
2answers
35 views

On a condition when bounded sets in $\mathbb R^n$ is convex ?

Is it true that a bounded set in $\mathbb R^n$ , $n>1$ , is convex iff every straight line through an arbitrary interior point of the set intersects the boundary of the set in exactly two points ? ...
1
vote
2answers
61 views

Theorem 6.4.1 Auslender Asymptotic cones and functions in optimization and variational inequalities

In proof of Theorem 6.4.1, the author assumes that $\text{rge}\,A\subset\text{aff}\,C$ and for $\epsilon>0$ claims that $\epsilon^{-1}(C-\text{rge}\,A)\subset\text{aff}\,(C-C)$, that I can't verify ...
0
votes
1answer
26 views

If the boundary of a convex set in $\mathbb R^n$ ($n>1$) is connected , is it necessarily also path-connected ?

If the boundary of a convex set in $\mathbb R^n$ ( where $n>1$) is connected , is it necessarily also path-connected ?
1
vote
1answer
19 views

Connected-ness of the boundary of convex sets in $\mathbb R^n$ , $n>1$ , under additional assumptions of the convex set being compact or bounded

Is the boundary of every compact convex set in $\mathbb R^n$ , ($n>1 $ ) connected ? is it path connected ? What if we assume only that the convex set is bounded , is the boundary connected ( and ...
1
vote
0answers
31 views

Half space representation of a convex polytope

We know that the half space representation of a polytope is given by: $Ax<b$. Consider a convex polytope in $\mathbb{R}^3_+$ with vertices given by the following set of points: ...
0
votes
1answer
160 views
+50

Proving that $\text{ri rge}\,A=\text{ri conv rge}\,A$

"If $A:\mathbb R^n\rightrightarrows\mathbb R^n$ is maximal monotone,then $\text{ri rge}\,A$ is convex". This is a proposition in auslender's book about the asymptotic cones. We can prove that ...
0
votes
0answers
24 views

Dividing given rectangle into regions with certain finite points being given

The problem I am facing is as follows. Suppose we have a unit square and we have been given certain no. of finite points, n (For eg n=5) which are randomly spread in the square. Now, we want to ...
-1
votes
0answers
22 views

Exactly one supporting line for a $C^1$ Jordan curve [on hold]

Let $\gamma :[a,b]\to\mathbb{R}^2$ be a convex Jordan curve (closed, simple, continuous) that has $C^1$ regularity, with $\gamma '(t)\neq 0,\ \forall t\in [a,b]$. Prove that there is exactly one ...
0
votes
1answer
16 views

Let $A$ be a convex set in $\mathbb R^n $ , where $n>1$ ; then is it true that $\bar A \setminus A^{\circ}$ i.e. the boundary of $A$ is connected ?

Let $A$ be a convex set in $\mathbb R^n $ , where $n>1$ ; then is it true that $\bar A \setminus A^{\circ}$ i.e. the boundary of $A$ is connected ? if yes , then is it also path connected ?
1
vote
0answers
28 views

References for the following functional

In many of the types of problems Ive looked at the following quantity keeps arising and I was wondering if anyone knew any references I could look at to learn some its properties. Take any function ...
0
votes
1answer
14 views

$A$ be a non-empty closed convex subset of a Hilbert space $H$ , is the distance from $A$ always attained at a unique point in $A$ ?

Let $A$ be a non-empty closed convex subset of a Hilbert space $H$ , then is it true that for every $b \in H$ , $\exists$ unique $x_b \in A$ such that $||x_b-b||=d(b,A)=\inf \{||b-x||:x \in A\}$ ?
1
vote
0answers
40 views
+50

Characterizing affine subspaces order-theoretically

Let $V$ denote a real vectorspace and $\mathrm{Con}(V)$ denote the poset of convex subsets of $V$. The goal is to identify those elements of $\mathrm{Con}(V)$ that happen to be affine subspaces of $V$ ...
-1
votes
0answers
31 views

How to prove that the following function is convex

I have a following function that I would like to show it is convex in $x$, however the function is not a sum of convex functions so I think I need to specify some conditions. However I don't know how ...
0
votes
0answers
28 views

Is convex or non convex function?$J(u,c)=\int K(x).u.(f(x)-c)^2dx$

I have a function such as $$J(u,c)=\int K(x).u.(f(x)-c)^2dx$$ where $f(x):\Omega \to R$; c is constant; $0 \le u \le 1$; and K(.) is gaussian kernel. My question is that : Is J convex or non-convex ...
1
vote
1answer
59 views

Is there any way to make the following function convex?

I need to find optimal lagrangian multiplier vectors for a quadratic programming problem subject to three quadratic equality constraints and several other linear inequality constraints. I would like ...
1
vote
1answer
34 views

Difference of support functions and its minimum points

Let $A$ and $B$ are convex, compact sets in $\mathbb{R}^n$. We have known that $$\max_{a\in A}\min_{b \in B} \|a-b\|=\sup_{\|g\|\le1}(\sigma_A(g)-\sigma_B(g)),$$ where $\sigma_M(x)=\sup_{u\in ...
1
vote
0answers
29 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in ...
4
votes
1answer
29 views

Visualizing Euclidean Algorithm in $\mathbb{Q}(\sqrt{-7})$ and $\mathbb{Q}(\sqrt{-11})$ with Convex Geometry

In an attempt to answer one of the bounty questions, I have started picturing Euclidean division in quadratic fields. In theory we would like the equation: $$ a = b\,q + r ...
2
votes
1answer
51 views

Calculating the distance function and projection

Let $\Omega=\{x\in\mathbb R^n\mid\langle a,x\rangle=b\}$. We define the distance function and projection as follows $$d(x;\Omega)=\inf\{||x-\omega||\mid\omega\in\Omega\}$$ ...
0
votes
1answer
51 views

Lower semi-continuity of particular function

Let $F : \mathbb{R}^n \rightrightarrows \mathbb{R}^n$ be a set-valued map, locally bounded, upper semi-continuous, and taking nonempty, convex and compact values. Let $f : \mathbb{R}^n \to \mathbb{R}$ ...
0
votes
1answer
21 views

Supporting lines of closed Jordan curve

Given a simple closed Jordan (i.e. continuous) curve $\gamma:[a,b]\to\mathbb{R}^2,\ \gamma([a,b])=C_\gamma$, how can I prove that $D_\gamma$ (the set of all interior points of $\gamma$ toghether with ...
3
votes
1answer
18 views

Volume of Convex Polytope with rational Entries

I have the following question: In this article Polytope volume computation it is stated that when considering a bounded convex polytope $P=\{x \mid Ax\le b\}$ with the matrix $A$ and the vector $b$ ...
1
vote
0answers
67 views

Find the intersection between two convex hulls, in this specific case

We work over $\mathbb{R}^K$. Let $V$ the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$, . Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ ...
2
votes
4answers
92 views

Sufficient condition for convexity

Let f:$ [a,b] \rightarrow \mathbb{R} $ a continous function such that $ \forall (x,y) \in [a,b]^{2}, \exists t \in ]0,1[, f(tx+(1-t)y) \le tf(x) + (1-t)f(y) $ show that f is convex
1
vote
1answer
28 views

Strongly convex, bounded from below by a quadratic function.

A strongly convex function $V: \mathbb{R}^d \rightarrow \mathbb{R}$ with negative parameter is given, i.e. $$ V(tx + (1-t)y) \leq tV(x) + (1-t) V(y) - \lambda t(1-t) | x -y |^2 , $$ with ...
1
vote
1answer
53 views

Convex function inequality for Euclidean norm: $\|(f(x_1),\cdots,f(x_n))\|_2\leq f(\|x\|_2)$

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a positive, convex, continuous function such that $f(0)=0$. (If you wish you can also suppose $f$ to be monotone increasing.) I would like to prove or to ...
0
votes
0answers
55 views

Is $C(B^c)$ an open set?

Assume that $B$ is an open set, if \begin{equation*} C:=\{x=\sum_{i=1}^{n}\lambda_{i}x_{i},\lambda_{i} \geq 0,\sum_{i=1}^{n}\lambda_{i}=1,x_i \in B\} \end{equation*} is a convex that contains $B$, ...
-2
votes
2answers
29 views

Simple question on convexity [closed]

If $\epsilon,\lambda\in(0,1)$, $a,b\in(1-\epsilon,1+\epsilon)$, then is $$\lambda a+(1-\lambda)b\in(1-\epsilon,1+\epsilon)?$$
3
votes
1answer
1k 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 ...
3
votes
2answers
46 views

Proving $x\ln(\frac{x}{a})+y\ln(\frac{y}{b})\geq (x+y)\ln(\frac{x+y}{a+b})$

Let a,b,x,y be positive reals. Prove $x\ln(\frac{x}{a})+y\ln(\frac{y}{b})\geq (x+y)\ln(\frac{x+y}{a+b})$ I don't have any olympic background, so I may be missing some standard trick. The ...
0
votes
1answer
20 views

Interior of difference of two convex sets

Let $A, B$ be two nonempty convex set in normed space $X$. We always have $$ \text{int}(A)\bigcap B\ne\emptyset\;\Longrightarrow\; 0\in\text{int}(A-B). $$ Indeed, suppose that $\text{int}(A)\bigcap ...
1
vote
2answers
46 views

Is it convex function?

I have a function and I don't know it is whether convex or non-convex: $$J(c,\alpha)=\int_\Omega ( \alpha c-I(x))^2u \, dx+ \|\alpha\|^2$$ where $0 \le u \le 1$, $I(x): \Omega \to R$, $c$ is constant ...
2
votes
2answers
60 views

If $A\subset B$, then $\text{ri}\, A\subset\text{ri}\,B$?

Is it true that If $A\subset B$, then $\text{ri}\, A\subset\text{ri}\,B$? Let $u\in\text{ri}\,A$, then there is $\epsilon>0$ such that $$\mathbb B(u;\epsilon)\cap\text{aff}\,A\subset A\subset B$$ ...
4
votes
2answers
38 views

Supporting hyperplane of a convex set

Let $\Omega$ be a bounded convex set in $\mathbb{R}^n$, and let $\partial \Omega$ denote its boundary. Fix a point $p$ in $\Omega$, and let $c$ denote the point on $\partial \Omega$ that is closest ...