Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.
0
votes
3answers
105 views
Confusion regarding convexity of a function
I was reading this lecture on convex functions and I came across this
$f\colon \Bbb R^n\to \Bbb R$ is convex if and only if the function $g\colon \Bbb R\to \Bbb R$, $g(t) = f(x+tv)$, ...
1
vote
2answers
515 views
maximum area of rectangle inscribed in a circle using geometric programming
need to find maximum area of rectangle that can be inscribed in a circle of radius r
but need to use geometric programming of optimization to this
for the maximum area the function is $ xy $ (if x ...
0
votes
2answers
61 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 ...
3
votes
1answer
55 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 ...
3
votes
1answer
80 views
Visualizing SPD cone for $3\times3$ matrices
Can anyone see a good way to visualize the SPD cone for 3x3 symmetric matrices?
I'm interested in something that would highlight it's special structure, like non-smoothness.
Here's one attempt, ...
2
votes
1answer
54 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} ...
2
votes
1answer
47 views
Convexity of Quadratic equation Inequality?
Solving an inequality of the form $x^TAx\geq0$ or $x^TAx\leq0$ is straightforward. I mean we have to check if A is positive semidefinite or negative semidefinite. But what would be the solution to the ...
2
votes
1answer
161 views
A variation of the Assignment Problem
In the following Wikipedia article about the Assignment Problem in the Example section, it says:
Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
2
votes
1answer
264 views
Going in the direction of the gradient
First, a motivating example. Suppose $f(x)$ is convex, differentiable, with a single minimum $x^*$. Then the differential equation $$\dot{x}(t) = -\nabla f(x(t))$$ drives $x(t)$ to $x^*$.
Now my ...
1
vote
1answer
61 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 ...
1
vote
1answer
45 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 ...
1
vote
1answer
50 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 ...
1
vote
1answer
55 views
How to prove this function is quasi-convex/concave?
this is the function:
$$\displaystyle f(a,b) = \frac{b^2}{4(1+a)}$$
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 ...
1
vote
1answer
39 views
linear equivalent min{} constraint
Activities are assigned to venues. Each activity $a_i$ has maximum size $b_i$ and demand $c_i$. Each venue $v_j$ has maximum size $d_j$.
An activity can be assigned to multiple venues, and we need to ...
1
vote
1answer
237 views
Armijo's rule line search
I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13.
The variable is $\beta$ ...
1
vote
1answer
86 views
Gradient of Moreau-Yosida Regularization
Let $f(x):\Re^n\rightarrow \Re$ be a proper and closed convex function. Its Moreau-Yosida regularization is defined as
$F(x)=\min_yf(y)+\frac{1}{2}\|y-x\|_2^2$
$Prox_f(x)=\arg\min_y ...
1
vote
1answer
72 views
Global maxima for concave functions
Let $D$ be a convex set in $\mathbb{R}^n$ and $f: D \to \mathbb{R}$ a concave and $C^1$ function. How do I show that $x^*$ is a global maximum
for $f$ if and only if $f^{(1)}(x^*)y \leq 0$ for all ...
0
votes
1answer
18 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:
...
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 ...
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 ...
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?
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
43 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
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).
0
votes
1answer
55 views
relation between size of matrix and condition number
I have a matrix A of size NxM. Is there any relationship between size of a matrix A with the condition number ? I am computing the pseudo inverse (pinv in matlab ) ...
0
votes
1answer
55 views
Lipschitz constant for optimization of multivariate function
I intend to implement an optimization algorithm which requires the computation of the Lipschitz constant. My function is a multivariate function with more than 50 variables. I am wondering whether ...
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 ...
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
140 views
Global Min-Max Optimization
When is
\begin{equation}
\min_X \max_Y f(X,Y)
\end{equation}
globally solvable? (i.e. we can find global solution for the optimization problem?)
I am not looking for reformulations.
Is it only when ...
0
votes
1answer
122 views
What Stopping Criteria to Use in Projected Gradient Descent
Suppose we want to solve a convex constrained minimization problem. We want to use projected gradient descent. If there was no constraint the stopping condition for a gradient descent algorithm would ...
0
votes
1answer
58 views
Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$
Wikipedia here explains it like this:
I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here:
"If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
0
votes
1answer
68 views
How I can find an optimal solution for a model with concave-convex objective function?
My objective function is sum of three functions, 2 linear functions and a concave function
($1-\exp(x)$); constraints of my model are convex. How can I obtain optimal solution from this problem?
0
votes
1answer
46 views
Convex Optimization
If $q>p>0$ show that the point $(x,y)=(0,0)$ minimizes the function $$f(x,y) = (y-px^2)(y-qx^2)$$ locally on the lines $$y=ht, x=kt$$ through the point (x,y).
0
votes
1answer
139 views
Checking convexity
I know that the function $(\mathbf{a}-\mathbf{b})'(\mathbf{a}-\mathbf{b})$ is convex in $\mathbf{a}$ ($\mathbf{a}$ and $\mathbf{b}$ are vectors, not scalars). Would ...
-1
votes
1answer
77 views
Finding an $O(n \log n)$ time algorithm for an optimization problem
Consider the following optimization problem:
Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ ...
0
votes
0answers
32 views
Upper bound function (for global maximization) for a black box (accuracy) objective function?
If I only know that my objective function takes in the coordinates and outputs a value (accuracy*) in the range [0,1], can I determine an upper bound function? (The lower bound can always be the ...
0
votes
0answers
128 views
what is a quasiconvex function
I want to know what is a quasiconvex function. I went through the wiki article. But still it is not clear to me. Also I referred to this lecture ...
0
votes
0answers
42 views
quasiconcavity of products of functions
Suppose I have two bounded, positive functions on [0,inf], f(x) and g(x), which are respectively concave increasing and convex decreasing. For my particular f and g, I am fairly sure the f(x)g(x) is ...
0
votes
0answers
86 views
Does Frank Wolfe algorithm always converge for concave functions?
I have implemented Frank-Wolfe algorithm in Python on my Ubuntu 11.10 machine.
Does the Frank-Wolfe algorithm always converge for a concave function?
My independent variable is of 20 ...
0
votes
0answers
59 views
Solving PSD matrix in Newton's method
I have functions defined as follows:
$f_1(A) = \sum\|x_i-x_j\|_A = \sum\sqrt{(x_i-x_j)^TA(x_i-x_j)}$ and $f_2(A) = \sum\|x_k-x_l\|^2_A$ where $A$ is a positive semi-definite (PSD) matrix, $x$ are ...
0
votes
0answers
74 views
Convexity and computational complexity
I remember reading and hearing that non-convex optimization problems tend to be harder to solve (in a computational complexity sense) than convex ones.
This made me think of a general, broad question ...
0
votes
0answers
68 views
Convex functions, proof
Please, help me
Prove that $$J:[a,b]\longrightarrow R$$ is convex on [a,b] iff
$$\frac{J(u)-J(v)}{u-v}\leq\frac{J(w)-J(v)}{w-v}\leq\frac{J(w)-J(u)}{w-u}$$
for all $$a\leq v<u<w \leq b$$
0
votes
0answers
127 views
How to find extreme bases of a polyhedron?
Suppose there is a submodular function $f$ over a ground set $V$ with cardinality $|V| = n$.
Let $x \in \mathbb{R}^V$ is a function.
Define $x(S) = \sum_{v \in S} x(v)$
I define a polyhedron in ...
0
votes
0answers
81 views
Please help me find the maxima of this expression
I want to find the value of p which maximizes the given function. p is a function of the form $\mathbb{R}^2 \to \mathbb{R}$. $x \in \mathbb{R}^2$. $\Omega$ is a region in the 2-d plane.
...
0
votes
0answers
88 views
Linear Algebra Simplification Query
Apologies in advance; my linear algebra is not exactly up to scratch, but a program optimisation problem I've come across just feels like theres a better way mathematically rather than ...
