Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.
1
vote
2answers
76 views
How can I solve Lagrange multiplier equation with multi constraints?
This site is really awesome. :)
I hope that we can share our ideas through this site!
I have an equation as below,
$$ min \ \ w^HRw \ \ subject \ \ to \ \ w^HR_aw=J_a, \ w^HR_bw=J_b$$
If there is ...
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 ...
0
votes
1answer
28 views
Quadratic Functions
Consider the strictly convex quadratic function $f(x) = \frac{1}{2}x^tPx - q^tx + r,$ where $P \in \mathbb{R}^{n \times n}$ is a positive definite matrix, $q \in \mathbb{R}^n$ and $r \in \mathbb{R}.$ ...
0
votes
1answer
26 views
solve non-convex quadratic constrained quadratic programming
$\min_{\beta}\beta^{T} A \beta$
$s.t. \ \beta^{T} C \beta=1\ and\ \beta\geqslant 0$
Here $A,C\in \mathbb{R}^{M\times M}$, $\beta \in \mathbb{R}^{M}$
I saw in one paper saying that it could be ...
0
votes
1answer
20 views
Why does the non-negative matrix factorization problem non-convex?
Supposing $\mathbf{X}\in\mathbb{R}_+^{m\times n}$, $\mathbf{Y}\in\mathbb{R}_+^{m\times r}$, $\mathbf{W}\in\mathbb{R}_+^{r\times n}$, the non-negative matrix factorization problem is defined as:
...
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 ...
1
vote
0answers
19 views
A fundamental question for the linearity of saddle point condition
I have a simple question about the linearity of saddle point condition. We have $$f(h_0,h_1,h_2)=k_1f_0(h_0,h_1)+k_2f_1(h_0,h_2)$$
and we also know that
$$f(\hat{h}_0,h_1,h_2)\leq ...
0
votes
1answer
22 views
Strict convexity condition
I have an if and only if, and I am having trouble with one of the arrows! Here it is:
Let $C \subset \mathbb{R}^n$ such that the interior of $C$, $\operatorname{int} C \neq \emptyset$.
$C$ is ...
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)$ ...
1
vote
0answers
30 views
non-degenerate basic feasible of Polyhydron
I couldn't show this problem. Can somebody help me by this question?
Consider a polyhedron $\{X \in \mathbb{R}^n | AX \leq b, X \geq 0 \}$ and a non-degenerate basic feasible solution $X^*$. We ...
0
votes
0answers
57 views
polyhedra and extreme points
I am stuck with solving this problem, does anybody has idea, how to solve it ?
Let $P$ and $Q$ be polyhedra in $\mathbb{R}^n$. Let $P +Q := \{x+y ~\vert~ x \in P; y \in Q \}$
a) Show that $P + Q$ ...
0
votes
1answer
33 views
How to re-parametrize for quadratic minimization?
Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem:
Minimize $w'S'Sw = \|S w\|^2$ over $w$ subject to
$e^Tw = 1$ and $w \geq 0$
using a solver I ...
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
0answers
82 views
$\{x:Ax\leq 0\}$ contains a subset of type $\{x:A'x=0, ax\leq 0\}$
If $C:=\{x:Ax\leq 0\}\neq\{x:Ax=0\}$, an independent set of rows of $A$ can be chosen, one denoted by $a$ and the others put as rows into a matrix $A'$, such that $\{x:A'x=0,ax\leq 0\}\subseteq C$. ...
1
vote
1answer
62 views
Convex Optimization of quadratic function with inequality constraints
How would I solve the following problem?
$$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$
where A is positive semidefinite and symmetric. Is it possible to ...
0
votes
1answer
29 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
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 ...
4
votes
1answer
53 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
156 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
24 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
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
0answers
23 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
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
49 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
44 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
12 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
46 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
25 views
Explain about convexity in geometry and in optimization.
My question is 'what is a difference between convexity in geometry and optimization?'
1
vote
0answers
21 views
Nesterovs third method - implementation in python [migrated]
I am looking at implementing Nesterov's method for my algorithm being written in python. Can anyone please point me to docs which can help me get started in terms of implementation of this method? I ...
0
votes
1answer
53 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
19 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})$. ...
0
votes
0answers
11 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
24 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
28 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
20 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
20 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
67 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
31 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
42 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
105 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
74 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
58 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
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 ...
