Tagged Questions
2
votes
2answers
44 views
Finding convex conjugate of a bounded function
The convex conjugate of a function $f:\mathcal{X}\mapsto \mathbb{R}$ is formally defined as $$f^\star\left(y\right)=\sup_{x\in\mathcal{X}}\ \left\langle x,y\right\rangle-f\left(x\right).$$
In cases ...
1
vote
0answers
33 views
Suggestions for a reference-level text on optimization theory?
I'd be interested in knowing if anybody has suggestions on an advanced but still self-contained reference on optimization theory, centered around linear and convex problems. The key feature of my ...
2
votes
1answer
41 views
Maximum of quasi-convex functions
A function $f$ is quasiconvex if all its sub-level sets are convex (i.e., $\{ x: f(x) \le \alpha\}$ is convex for all $\alpha$.)
For a convex function $f$, it is true that $f$ acheives its maximum ...
4
votes
0answers
67 views
On a version of gradient descent
I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has coordinate-wise Lipschitz constant $M$ (meaning that for all ...
0
votes
0answers
25 views
KKT conditions of this convex optimization problem
Consider a continuous function $f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}$ such that $\forall y \in \mathbb{R}^m$ $f(\cdot,y)$ is convex, and $\forall x \in \mathbb{R}^n$ $f(x,\cdot)$ ...
0
votes
1answer
22 views
Where the gradient of a convex function approaches zero
Does there exists a differentiable convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ with a unique global minimum which we denote by $x^*$ such that there exists a sequence $x_k$, not ...
2
votes
3answers
168 views
A robust convex optimization problem
Consider a function $ f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R} $ such that $\forall x \in \mathbb{R}^n$ the map $f(x,\cdot)$ is convex, and $\forall y\in \mathbb{R}^m$ the map ...
0
votes
0answers
23 views
Convexifying Functions
I have the following question:
Imagine you have a function $F(x,y(x),y'(x)), F:\mathbb{R} \times \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R} $ and this function is not convex.
Then you can ...
1
vote
1answer
49 views
KKT and Slater's condition
I was studying Stephen Boyd's text book and got confused in the KKT part. The book says the following:
"For any convex optimization problem with differentiable objective and constraint function, any ...
3
votes
0answers
40 views
Does convexity of a function guarantee tractability of finding its minimum?
Formulating a problem as a convex optimization problem usually implicitly considered to imply being able to find global minimizer of the objective. My question is that if it is true or not.
...
0
votes
0answers
18 views
Solution of a Quadratic Optimization Problem
Let $\mathbf{A_1}$ and $\mathbf{A_2}$ be two given $N\times N$ hermitian matrices. Then how do I solve the problem,
\begin{align}
...
1
vote
1answer
34 views
Robust feasibility with halfspace?
Consider a convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$, such that for all $x \in \mathbb{R}^n$ we have
$$ a_1^\top x + b_1 \leq f(x) \leq a_2^\top x + b_2 $$
for some given $a_1, a_2 ...
1
vote
1answer
25 views
Explain about convexity in geometry and in optimization.
My question is 'what is a difference between convexity in geometry and optimization?'
0
votes
1answer
21 views
Coding Distributions as a Convex Constraint
In convex optimization, how can we impose a constraint that a variable has certain distribution?
e.g. elements of vector $v$ have power law distribution?
1
vote
1answer
81 views
Are these convex optimization problems equivalent?
Consider the optimization problem
$$ \mathcal{P}_1: \qquad \min_{x \in \mathbb{R}^n} c^\top x \quad \text{sub. to } \ g(x,y_i) \leq 0 \ \ \forall i = 1,2,...,M$$
where $c \in \mathbb{R}^n$, and ...
0
votes
1answer
23 views
A property of the minima of a sum of convex functions, take 2
This is a follow-up to my previous question. Let $g_1(x), \ldots, g_k(x)$ be convex functions from $\mathbb{R}^n$ to $\mathbb{R}$, and lets assume that global minimum of each $g_i$ is unique and is ...
2
votes
1answer
37 views
A property of the minimum of a sum of convex functions
Let $g_1(x), \ldots, g_k(x)$ be convex functions from $\mathbb{R}^n$ to $\mathbb{R}$, and lets assume that global minimum of each $g_i$ is unique and is achieved, denoting $$x_i = \arg \min_{x \in ...
0
votes
1answer
58 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
36 views
Is it a convex function?
Let $f(.)$ be a function. If $f(X)$ is a convex function of $X$, where $X$ is a matrix. Is $f(AXB)$ also a convex function of $X$? ($A$ and $B$ are fixed matrices).
1
vote
1answer
40 views
Convexity of product of elements from two convex set
Given two convex set $X\subseteq \mathbb{R}^N$,$Y\subseteq \mathbb{R}^{N\times N}$
Given a $x\in X$, is the set $\{z|z=yx,\forall y \in Y\}$ convex?
If no, by adding what can force it to be convex?
...
1
vote
1answer
52 views
Hessian of a function that takes matrix arguments
I have a function that that takes a matrix and returns a scalar, $f : \mathbb{R}^{m\times n} \rightarrow \mathbb{R}$. I know how to calculate the derivative of this function with respect to the matrix ...
0
votes
0answers
33 views
Is the correlation function convex or not?
Suppose the function for statistical correlation is a non linear constraint in a non linear programming model:
$$
\frac{\sum_{t=1}^T (p_t - \bar{p})(R_t - \bar{R})}{\sqrt{\sum_{t=1}^T (p_t - ...
0
votes
0answers
26 views
Subgradient and Lipschtz
For a convex function $f:R^n\longrightarrow R$,
the function is G-Lipschitz with any norm x
$\left| f\left(w\right)- f\left(w^{'}\right)\right| \leq G \left\|w-w^{'}\right\|_x$ ,
if and only if
...
0
votes
1answer
75 views
Is this sum of convex and concave functions a convex function?
Is this a convex function in $X$, where all the entries are real and $Y,\beta$ are constants where $X,Y$ are rectangular matrices and $\beta$ is a constant vector and $A,B$ are constant p.s.d ...
2
votes
1answer
70 views
Strictly Convex Function and Well-Separated Minimum
Suppose $\Theta \subset \mathbb{R}^d$ is a convex set, and $f:\Theta \rightarrow \mathbb{R}$ is a strictly convex function that has a minimum at $\theta_0\in\Theta$. Is it true then that $\forall ...
1
vote
1answer
39 views
Distance between a point to a $2d$ ellipse in $3d$ ambient space
Suppose we are working in the 3D Euclidean space. We are given an arbitrary point $p$ and a 2d ellipse:
$$E=\{x:x^TQx\leq1,x^Tq=0\},$$
where $Q$ is a positive definite matrix and $q$ is an ...
0
votes
1answer
43 views
Quasi-Convexity
Can I get the conclusion that the function of matrix $P$ and $Q$
\begin{equation}
\mathrm{tr}\left( PQ\right)
\end{equation}
is a quasi-concave function for $P>0$, and $Q>0$?
It is true for ...
3
votes
2answers
123 views
When finding root, does Newton's method fail if the function is non-differentiable?
According to wikipedia's description, the Newton's method finding a root presumes a differentiable function. Then, will it fail when encountering non-differentiable function? For example, can it find ...
1
vote
0answers
31 views
Is it problematic when using Newton Descent with discontinuous Hessian?
Is there any side effect when applying Newton Descent to a convex function whose Hessian is discontinuous?
0
votes
1answer
37 views
Fenchel conjugate of non smooth function
Is it valid to derive Fenchel conjugate for a non-smooth function? Checking its definition $f^*(y) = sup_{x \in \mathsf{dom}f} (y^Tx - f(x))$, I think this would be OK, but I'm not sure about that.
...
2
votes
1answer
55 views
Convex optimization and linear programming please help! :)
How would I write the following as a standard form LP? Minimizing $\sum_{i=1}^n x_i + c\max(a_i-x_i)$ for $a_i \ge 0$ and what is the optimal value for when $c=n$
How to express minimize $\frac{1}{2} ...
1
vote
1answer
51 views
Some convex optimization questions
Is minimizing number of $\{{i : x_i \ne 0}\}$ subject to $Ax=b$ a convex problem? Why is it computationally hard?
What is polar cone of $\{x \in \mathbb{R}^2:0\le x_1 \le x_2\}$?
Are ...
0
votes
1answer
50 views
Projection: two closed convex sets
I am really struggling with this problem:
$C$ and $D$ are closed, convex subsets of ${R}^n$
with non-empty intersection, i.e. $C \cap D \neq \emptyset $ . Is it true that projection
$p_{C\cap ...
5
votes
0answers
63 views
How to understand convex duality intuitively
Is there an intuitive way to understand the convex duality? If the primal problem is minimization, the dual is maximization over another set of variables - but I would love to have a geometric ...
0
votes
0answers
22 views
How can I reformulate my problem to make it convex?
I would like to find the symmetric positive definite matrix $S\in \mathcal{M}_{m,m}$ that minimizes the function $f(S)=\mathrm{trace}(S)+m^2\mathrm{trace}(S^{-2})$ which has been proven to be convex ...
0
votes
0answers
42 views
Is this function concave on X? $\log \det(I+(P-\text{tr}(X))\cdot X)$
where P-tr(X)>0 and X is a diagonal matrix with elements of (x1,x2,...xm) where xi>0 and xi<1
For this question,I have apply Mathematica8.0 to find the Hessian matrix of -1*Logdet(I+(P-tr(x)X)) ...
0
votes
2answers
71 views
An eigen problem
$K$ is a symmetric positive semidefefinit matrix.
$K1 = 0$ (i.e. The sum of elements in each row is $0$. Or in other words matrix $K$ is centered. From this we conclude the smallest eigenvalue of $K$ ...
3
votes
1answer
102 views
Why is this composition of concave and convex functions concave?
Please forgive my ignorance. I have a quick silly question about a statement given without proof in Convex Optimization by Boyd and Vandenberghe (page 87).
Suppose $\mathbb{R}_+^n$ is the set of ...
2
votes
2answers
49 views
straightforward way to determine if this set is convex?
straightforward way to determine if this set is convex?
$Z=\left\{x\in\mathbb{R}^2:3x_1^4-x_1x_2+x_2^4\le x_2,x_1>2,x_2>2\right\}$
I know I can try by manipulation of linear combination of two ...
0
votes
1answer
55 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 ...
3
votes
2answers
53 views
About the convexity of Ky Fan's norm
As we know, the Ky Fan norm is convex, and so is the Ky Fan k-norm. My question is, does this imply that the difference between them is a non-convex function, since it results from "difference between ...
9
votes
2answers
180 views
On the convexity of element-wise norm 1 of the inverse
Let us define $\|A\|_1$ the element wise norm 1 of a matrix $A \in \mathbb{R}^{n \times m}$ as
$$
\|A\|_1= \sum_{i,j} |A_{i,j}|.
$$
Obviously, this function is convex over $\mathbb{R}^{n \times m}$. ...
1
vote
2answers
32 views
computational strategy for solving convex-concave minmax problem
Assume f(x,y) is convex in $x$ and concave in $y$.
Then \begin{equation}\min_x \max_y f(x,y)\end{equation} is globally solvable, because f is convex in x (max of convex is convex.)
But can we find a ...
2
votes
1answer
34 views
Convex relaxation for the complement of Lorentz cone
Is it possible to obtain a convex relaxation for
$$
\{ (x,t): t \le \|x\|_2\} \in \mathbb{R}^{d+1}
$$
where $x \in \mathbb{R}^d$ and $\|x\|_2$ is the usual Euclidean norm,
by moving to higher ...
0
votes
1answer
31 views
Is $\{x\in\mathbb{R}^4: x\ge 0, \, x_1x_2+x_3x_4\ge\alpha\}$ convex?
Is $\{x\in\mathbb{R}^4: x\ge 0\, \mbox{ and }\, x_1x_2+x_3x_4\ge\alpha\}$, for $\alpha>0$, a convex set?
A related question is this one:
Is $f(x_1,x_2)=x_1x_2$, with $x_1,x_2 \in \mathbb{R}_+$, a ...
0
votes
1answer
32 views
non convex optimisation
\begin{eqnarray}
{\textbf{maximise}} \hspace{2mm} Ar^{-(a+b)} + Br^{-(a+b+c)}-C \nonumber
\end{eqnarray}
such that,
\begin{eqnarray}
c= l(h-m_{0}) \nonumber\\
m_{1} \leq h \leq m_{2} \nonumber\\
...
0
votes
1answer
94 views
Convex Functions: Property Proof
Let $f\colon S\to \mathbb R$ be a $C^1$ function on a convex domain $S \subseteq \mathbb R^n$. Show that if $f$ is convex then $(\nabla f(x) - \nabla f(y)) \cdot (x-y) \ge 0$ for all $x,y \in S$.
...
0
votes
2answers
54 views
A question dealing with the convexity of functions involving the absolute value
Just beginning to learn convex analysis and optimization, I have some inquiries to make with regard to the absolute value function $f(x)= |x|$. This function is clearly convex, but since we know that ...
1
vote
1answer
44 views
Submodularity of the product of two non-negative, monotone increasing submodular functions
I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions
Formally, we have $f$ and $g$ are submodular functions, that is, ...
1
vote
1answer
68 views
directional derivative sublinear of a convex function sublinearity problem to show
How to show the following:
If $f:\mathbb R^d \rightarrow \mathbb R$ is convex
then its directional derivative is sublinear?
Thank you...
