Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.
0
votes
1answer
41 views
Positive semidefinite Matrix examples query
This might be really dumb question but I've just started dealing with such matrices. I would like to know why $$\begin{bmatrix} 0 & 1 \\ 1 & x \end{bmatrix}$$ cannot be a positive semidefinite ...
2
votes
3answers
173 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 ...
4
votes
1answer
102 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 ...
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 ...
0
votes
1answer
26 views
KKT formulation
How to reformulate the following problem
$$min \frac{1}{2} (x_1-a_1)^2+ \frac{1}{2} (x_2-a_2)^2$$
$$s.t. \mathbf{1}^Tx=1$$
$$ ||x||_2\leq2$$
as the following system of KKT conditions:
$$(1 + ...
0
votes
0answers
26 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
0answers
24 views
“Buzzword” for approximate gradients (that form a positive scalar product with the real gradient)
Let $\vec g(\vec x)\in\mathbb R^N$ be the gradient of a convex function $L: \mathbb R^N\mapsto \mathbb R$ and $\vec h(\vec x)$ such that
$$
\vec h(\vec x)^T\vec g(\vec x) \geq 0\quad\quad \forall \vec ...
1
vote
1answer
74 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
47 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.
...
1
vote
0answers
22 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
51 views
Is the following problem convex?
I think the following problem is convex (due to the results of some simulations), but I am not sure:
$min_x||e^{(Ax)}-b||^2_2$ s.t. x>0
where $A$ is m x n, $x$ is n x 1, and b is m x 1. $A,x,b$ are ...
2
votes
0answers
47 views
Nonlinear optimization of constraint parameter - subdifferential?
Disclaimer: I discovered that the FAQ suggests to post research-level to mathoverflow instead of math.stackexchange. I "moved" the question accordingly, cp. post at mathoverflow. Sorry for the ...
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 ...
0
votes
0answers
13 views
I need a resource for basic convex optimization algorithms.
I'm trying to decide whether or not a certain CS problem can be solved in polynomial time. I've got it reduced down to a basic convex optimization problem, but I can't for the life of me find a good ...
2
votes
2answers
49 views
Analytical Solution to a simple l1 norm problem
Can we solve this simple optimization problem analytically?
$ \min_{w}\dfrac{1}{2}\left(w-c\right)^{2}+\lambda\left|w\right| $
where c is a scalar and w is the scalar optimization variable.
1
vote
1answer
28 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
61 views
Infeasible start Newton's method
I am implementing infeasible start Newton's method from the information in the slides (slide 11 of the link) posted here. It requires us to calculate primal and dual Newton steps, denoted by, $\Delta ...
1
vote
0answers
23 views
Basic questions about convex optimization
I have some basic questions about convex optimization.
From finding sources online, I've seen that many algorithms (for example, Newton's method) describe themselves as $o(\frac{1}{\epsilon})$. ...
1
vote
0answers
14 views
Which methods of function continuation admit polynomial-time convex minimization?
The function $f$ maps the positive integer lattice in $\mathbb{R}^n$ (i.e. the vectors in $\mathbb{R}^n$ whose coordinates are all integers) to $\mathbb{R}$. We know that $f$ is convex.
I want to ...
0
votes
1answer
31 views
Cannot get matlab CVX code to work for life of me. Simple max problem [closed]
{clear all;
close all;
clc;
C = [0.07^2 0.00588 -0.0063; 0.00588 0.12^2 -0.00648; -0.0063 -0.00648 0.18^2];
R = [1.075 1.1 1.2];
I = ones(1,3);
cvx_begin
variables P(3)
maximize(R*P)
...
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 ...
1
vote
0answers
21 views
A question about monotonicity
Is
$$D(y_l)=\int_{-\infty}^{y_l}f_0(y)\mbox{d}y+\int_{y_l}^{y_u}e^{x\ln(1/L(y_l))}L(y)^{x}f_0(y)\mbox{d}y+\frac{1}{L(y_l)}\int_{y_u}^{\infty}f_0(y)\mbox{d}y$$
with
...
0
votes
1answer
23 views
Strict local minimiser
Let $\Omega$ be a convex subset of $R^n$ adm f is a real valued, twice differentiable function. Let $x^*$ to be a point in $\Omega$ and suppose that there exists $c \in R \, c >0$ s.t. for all ...
1
vote
3answers
70 views
What is the dual of this optimization problem?
Consider the points $x_1, \ldots, x_N \in \mathbb{R}^n$, and a (locally bounded, convex) function $f: \mathbb{R}^n \rightarrow \mathbb{R}$.
I am looking for the dual of the following optimization ...
0
votes
0answers
33 views
Facets of the convex hull as solution of an optimization problem?
Given $N$ points $x_1, x_2, ..., x_N \in \mathbb{R}^n$, consider their convex hull $$\mathcal{C} = \text{conv}( \{ x_1, ..., x_n \} ) = \bigcap_{j=1}^{J} \{ x \in \mathbb{R}^n : \ A_j x \leq b_j \} ...
0
votes
0answers
12 views
Confusion related to solving the optimization in linear svm using dual coordinate descent
I have this confusion related to L1 and L2 svm. I was reading this paper
I am attaching the screenshot and the part I didn't understand
The part that I didn't understand how it was derived
I ...
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
0answers
43 views
Formulation of a problem as semidefinite programming
I would appreciate some help with this problem:
$R$ is a positive semidefinite matrix $\in{R}^{n\times n}$, $A \in{R}^{n\times m}$.
I need to formulate this optimization problem as semidefinite ...
2
votes
0answers
125 views
SDP relaxation of non-convex QCQP and duality gap
Short version
Is there a duality gap between a QCQP problem and the SDP problem obtained through lagrangian relaxation?
A paper I'm studying is using this fact, but I cannot achieve the authors' ...
0
votes
0answers
80 views
optimization function: sum of root squares of sum of two quadratic
Full question (same question in jpg, pdf and doc\docx):
https://drive.google.com/folderview?id=0BxFEf1J4iYVeX2l2NlVjUldEUlE&usp=sharing
Hello
I am a graduate student in computer science, making ...
3
votes
1answer
64 views
minimization problem on differential equations - optimal control
I am trying to minimize an time-integral of a linear function with respect to differential equations. The problem is formally defined as follows:
Given $\lambda< \mu_1, \mu_2$ fixed ...
1
vote
1answer
82 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
26 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
41 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
61 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$ ?
...
1
vote
1answer
51 views
Convergence rate when solving L1 regularized optimization via coordinate descent with tiny step?
Wondering if there is an established result for the convergence rate when solving L1 regularized optimization via coordinate descent with tiny step? By "tiny step" I mean the step is always set to a ...
1
vote
1answer
56 views
Strongly convex function
There is a $\sigma$-strongly convex function, $f(x')\ge f(x)+ \langle x'-x,\mu\rangle +\frac{\sigma}{2}\left|x'-x\right|^2$ where $\mu \in \partial f(x)$, $\mu ' \in \partial f(x')$.
How could I get ...
0
votes
1answer
51 views
Closed form solution of a convex optimization problem
Suppose we want to solve the following optimization problem:
\begin{equation*}
\begin{aligned}
& \underset{x,y,z}{\text{minimize}} && x(a-y) \\
& \text{subject to} && ...
0
votes
2answers
44 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?
...
2
votes
3answers
145 views
Deriving the sub-differential of the nuclear norm
Let $f(K)=||K||_*$, the nuclear norm (sum of the singular values) of $K=U\Sigma V^T$. How can one compute the subdifferential $\partial F$. This may be a basic question, I'm trying to work my way ...
0
votes
1answer
45 views
optimal solution
Consider the standard form polyhedron $P = \{x | Ax = b, x ≥
O \}$. Suppose that the matrix $A$ has dimensions $m \times n$ and that its rows are linearly independent. For each one of the following ...
3
votes
1answer
54 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, ...
0
votes
0answers
36 views
Minimize Wire-Cross(optimization)
I want to design a circuit contain some Nodes that has some wires connect each node to other(like a acyclic graph).
My logical circuit layout maybe has some wires which cross other one and my purpose ...
2
votes
1answer
60 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
29 views
Complexity of minimizing $ L_2$ norm subject to linear inequalities
What is the computational complexity of solving a quadratic program of the following form?
min $||x - c||_2^2$ subject to
$Ax \ge b$
[$x,c$ are $n\times 1$, $A$ is $ m \times n$, $b$ is $m ...
0
votes
1answer
33 views
Prove a set in $\mathbb{R}^2$ is convex.
Let $$\Omega = \{(x_1,x_2)\in\mathbb{R}^2:x_1^2-x_2\leq 6\}$$
Prove that $\Omega$ is a convex set from first principles using the convex combination.
edit: Thanks Ewan for that, but I am trying ...
0
votes
0answers
35 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
2answers
64 views
Anyone saw this interesting function before?
Say $\theta\in\Re^n$ and $\theta_i\in(0,1)$ for all $i$. Define
$$
f(\theta) = \frac{1}{n}\sum_i^n\{(1-\theta_i)\log(1-\theta_i)+\theta_i\log\theta_i\}
$$
It is easy to see the minimizer of ...
0
votes
0answers
27 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
...
