Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.
16
votes
1answer
174 views
Properties of the Cone of Positive Semidefinite Matrices
The set of positive semidefinite symmetric real matrices form a cone. We can define an order over the set of matrices by saying $X\geq Y$ if and only if $X-Y$ is positive semidefinite. I suspect that ...
10
votes
2answers
403 views
If the Minkowski sum of two convex closed sets is a Euclidean ball, then can the two sets be anything other than Euclidean balls?
If for two convex closed sets $S_1$ and $S_2$, the Minkowski sum is a Euclidean ball then can $S_1$ and $S_2$ be anything other than Euclidean balls themselves. I suspect they can be but I haven't ...
10
votes
5answers
433 views
Why is convexity more important than quasi-convexity in optimization?
In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
10
votes
1answer
300 views
A (mathematically) sound investment strategy
It is common wisdom in the investment community that a long-term investor saving for his future would do well to invest in high-risk/high-return assets when he is young, slowly switching his portfolio ...
9
votes
2answers
188 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}$. ...
8
votes
1answer
261 views
invex functions and their usefulness?
An invex function $f$ is a differentiable function from $\Bbb R^n$ to $\Bbb R$ that for some function $\eta : \Bbb R^n \times \Bbb R^n \to \Bbb R^n$ satisfies for all $x, u$, $f(x) - f(u) \geq \eta(x, ...
6
votes
2answers
453 views
Please explain the intuition behind the dual problem in optimization.
I've studied convex optimization pretty carefully, but don't feel that I have yet "grokked" the dual problem. Here are some questions I would like to understand more deeply/clearly/simply:
1) How ...
6
votes
3answers
322 views
Why is the affine hull of the unit circle R^2?
In Boyd's "Convex Optimization" it defines the affine hull of a subset $C$ of $R^n$ as
$$\text{aff} C = \left\{\theta_1 x_1 + \ldots +\theta_k x_k \mid x_1, \ldots x_k \in C, \theta_1 + \ldots ...
6
votes
0answers
107 views
Subgradient of convex minimization duality
$$\min(f_0(x))$$
$$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$
$$f_i : \text{convex};\quad x : \text{variable}$$
It is also considered that $g(y)$ is the optimal value of the problem ...
5
votes
1answer
108 views
a conjecture on norms and convex functions over polytopes
Suppose one has a convex, bounded polytope P $\subset R^n$ and a strictly convex function $f$ defined everywhere on $R^n$. $f$ has a unique minimum; and suppose this minimum occurs somewhere strictly ...
5
votes
1answer
207 views
Minimizing l-infinity norm of complex vector
I have an $n$-dimensional complex vector space, and I want to minimize the $L_\infty$ norm of a point that is constrained to an $m$-dimensional affine subspace. That is,
Given $\mathbf{z} \in ...
5
votes
0answers
226 views
Is this question solvable? $2$ non-linear equations and the proof that the solution is unique (with asymmetric bounty option)
As mentioned in the title I want to show the uniqueness of the solution to $2$ non-linear equations. However, it seems that I can not solve this question with my current mathematical knowledge. More ...
5
votes
0answers
65 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 ...
5
votes
0answers
110 views
Need advice: what should be my next step?
I am dealing with a quite algebraic question and I arrived at some good point. I had $2$ equations with $2$ unknowns and I was able to eleminate one of the variables. My final equation still seems ...
4
votes
2answers
137 views
Is the rising factorial function a convex function?
Let $(x)_p=x(x+1)\dots(x+p-1)$ be the rising factorial function.
My question is: Is $(x)_p$ a convex function or not? And how to proof?
And what is about the falling factorial function ...
4
votes
2answers
101 views
What is the difference between minimum and infimum?
What is the difference between minimum and infimum?
I have a great confusion about this.
4
votes
2answers
95 views
proving this inequality related to conjugate functions
For $x \in \mathbb{R}^n$ let us denote $x_{[i]}$ the $i$th largest component of $x$ s.t
$$
x_{[1]} \geq x_{[2]} \geq x_{[3]}\ge\cdots
$$
The function
$$
f(x)= \sum_{i=1}^r x_{[i]}
$$
is the sum of ...
4
votes
1answer
549 views
How to prove this function is concave?
This is the function:
$\displaystyle f(\vec x) = \log \frac{\exp(x_1)}{\sum_{i=1}^n \exp(x_i)} $
4
votes
1answer
193 views
$L_1$ projection of sum of convex functions onto polytopes
Suppose I have a function $f(x) : \mathbb R^n \to \mathbb R$ that is the sum of a given strictly convex function $g : \mathbb R \to \mathbb R$ in a single variable, i.e. $f(x) = g(x_1) + g(x_2) + ...
4
votes
1answer
293 views
Solving a set of 3 nonlinear equations with constraints
Problem statement:
I am given 3 sets of equations that govern the force $P$, and also the neutral axis, defined by two variables, the radius from the center $r$ and also the rotation degree in ...
4
votes
1answer
159 views
A conjecture of parallelogram inside convex and central symmetric curve
Assume Q is a convex central symmetric curve, whose area is $\displaystyle S$.
The area of the maximum parallelogram inside Q is $\displaystyle S'$.
How to prove the conjecture that $\displaystyle ...
4
votes
1answer
101 views
L1 norm and L2 norm
I was studying the Stephen Boyd's textbook on convex optimization. It says the following:
The amplitude distribution of the optimal residual for the l1-norm approximation problem will tend to have ...
4
votes
1answer
141 views
Convexity of log det X???
In Boyd's book on convex optimization he proves convexity of log det X by proving it to be concave along a line i.e. he proves that the Hessian of the function $g(t) = f(Z+tV)$ is negative therefore ...
4
votes
0answers
74 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 ...
4
votes
0answers
41 views
Primal-Dual pair in SDP
Let's we have a primal model like
$\max~~ x + Z $
$s.t. ~~~Ax + y I - Z \preceq B$
$~~~~~~~~~Z \succeq 0, ~X \geq 0, ~~y ~free$
where $A, B \in {\mathbb R^{n \times n}}$. The capital letters ...
4
votes
0answers
80 views
When can the optimal value of a SDP be achieved?
Looking at semidefinite programs, are there any sufficient conditions for the solvability (i.e. the optimal value can be achieved, that is infimum=minimum)?
Obviously if the problem is unbounded, the ...
4
votes
0answers
134 views
Optimization of relative entropy
Wondering if my following question is an application of information theory:
Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream ...
3
votes
5answers
1k views
Difference between supremum and maximum
Referring to this lecture , I want to know what is the difference between supremum and maximum. It looks same as far as the lecture is concerned when it explains pointwise supremum and pointwise ...
3
votes
3answers
235 views
Prove $ax - x\log(x)$ is convex?
How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function.
Any ideas?
3
votes
1answer
141 views
Does solving the LP dual SOLVE the primal LP?
When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual."
I know that both the primal LP and its dual must have the same optimal objective value ...
3
votes
1answer
311 views
Convexity and Affineness
In reading about convex optimization, the author states that all convex sets are affine. Are affinity and convexity equivalent? If I understand, both definitions incorporate the notion that a set is ...
3
votes
1answer
113 views
Lower bound of a function
Given $x \geq y > 0$ and an integer $n$. We want to minimize the following term $\sum_{i=1}^n (x_i^2 - x_iy_i)$ over $(x_1,\ldots,x_n)$, $(y_1,\ldots,y_n)$ non-negative such that $\sum_{i=1}^n x_i ...
3
votes
2answers
136 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 ...
3
votes
1answer
645 views
prove this is a strongly convex function
The definition of strongly convex from Wikipedia:
It is not necessary for a function to be differentiable in order to be strongly convex. A third definition for a strongly convex function, with ...
3
votes
1answer
53 views
Alternative representation for Perron Frobenius Eigenvalue
While explaining the application of Geometric programming to Minimizing Spectral radius Boyd says that $\lambda_{pf}$ can also be characterized as:
$\operatorname{inf}\{\lambda|\exists{v}>0, ...
3
votes
2answers
136 views
How many points to find a polynomial?
I would like to fit a formula $ax^b + cx^d+ e$ to a set of points. I have two questions.
If my data were perfect, how many points do I need in the worst case to get $a,b,c,d,e$ exactly?
If my data ...
3
votes
2answers
90 views
A standard quadratic minimization problem
Consider the "Complex" Quadratic minimization problem
\begin{align}
\min_{\mathbb{x}\in \mathbb{C}^{N \times 1}}~\mathbf{{x}}^H\mathbf{Q}\mathbf{x}-2~\Re{(\mathbf{x}^H\mathbf{b})}+1
\end{align}
...
3
votes
1answer
180 views
Both convex and concave functions
Let $f$ be a function from $\mathbb{R}^n$ to $\mathbb{R}$, which is convex & concave and continuous with $f(0)=0$.
How to prove that $f(x)=q\cdot x$ for all $x$ in $\mathbb{R}^n$, for a scalar ...
3
votes
3answers
828 views
Easy convex sets question
Question 2.23 out of Boyd and Vanderberghe:
Give an example of two closed convex sets that are disjoint but cannot be strictly separated.
The obvious idea is to take something like unbounded sets ...
3
votes
2answers
142 views
Computing the decay factor for a full rank wide matrix, or finding a unit vector farthest away from a set of spanning unit vectors
Let $A$ be a tall matrix that is not rank-deficient and has normalized columns. That is $A$ is $m\times n$, $m<n$ and rank$(A)=m$, and $||a_i||_2=1$ for all columns $a_i$.
Define ...
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 ...
3
votes
1answer
256 views
Question about the simplex method complexity
So I know that in general the simplex method for linear and convex quadratic programming can require exponential time. But assuming a positive semidefinite quadratic program that is solvable by the ...
3
votes
1answer
962 views
Proof of Hoeffding's inequality
The Hoeffding's inequality is $P(S_n - E[S_n] \geq \epsilon) \leq e^{-2\epsilon^2/k'}$, where $S_n = \sum_{i=1}^{n} X_i$, $X_i$'s are independent bounded random variables, and $k'$ depends on the ...
3
votes
1answer
77 views
Show that any convex function is locally bounded
Show that a convex function $f:\mathbb{R}^n \rightarrow \overline{\mathbb{R}}$ is bounded in a neighborhood of $x\in \text{ri}(\text{dom}(f))$. Showing that it has an upper bound is not difficult ...
3
votes
1answer
29 views
Maximizing a convex function
The following problem is exercise I.6 from Bellman's Dynamic Programming.
Consider the problem of maximizing the function
$$
F(x_{1} , \ldots , x_{N}) = \sum_{i = 1}^{n} \varphi(x_{i}),
$$
subject to ...
3
votes
1answer
65 views
decomposing PSD block matrix into two PSD block matrices
Given $Q = \left( \begin{array}{ccc}
A + B & C \\
C^T & D\end{array} \right) $, where we know that $Q, A, B, D$ are all positive semi-definite, square, but not necessarily equally sized ...
3
votes
1answer
120 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 ...
3
votes
1answer
53 views
Show that $Z=T(2S−I)+I−S$ is firmly nonexpansive
Suppose $T$ and $S$ are firmly nonexpansive mappings from $\mathbb R^n$ to $\mathbb R^n$. Let $I$ be identity operator. I want to show that $Z=T(2S−I)+I−S$ is firmly nonexpansive.
Definition. We say ...
3
votes
1answer
44 views
Convex programming when the problem has an underlying combinatorial structure that's a DAG
I have a nonlinear convex objective function to minimize. The function is defined on a set of variables: $\{ x_1,x_2, \ldots ,x_p \},$ where each $x_i$ is a number associated with a path in the DAG.
...
3
votes
3answers
208 views
simple-looking non-convex optimization problem
I want to solve the following problem:
Maximize $\sum_{i=1}^n\log(1+\lambda_i^2)$ subject to $\lambda_i >0$ and $\sum_{i=1}^n\lambda_i = M$. I was wondering how I could cast it as a convex problem. ...
