Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

1
vote
1answer
12 views

Weighted Norm Minimization

I have a minimization problem of the form $min (w_1 \|x\|+w_2\|y\|)$ subject to constraints $A_1x=b_1$, $A_2y=b_2$, $0< l_1 \leq x \leq u_1$ and $0< l_2 \leq y \leq u_2$ where ...
0
votes
2answers
50 views

Looking for numerical methods for finding roots of convex vector function ${\bf f}({\bf x})={\bf 0}$

Consider the function ${\bf f}:\mathbb{R}^n\to\mathbb{R}^m$ defined as ${\bf f} = (f_1,f_2,\ldots,f_m)$ where each $f_i:\mathbb{R}^n\to\mathbb{R}$ is twice-continuously differentiable convex in ${\bf ...
0
votes
1answer
21 views

Properties of functions having the form $g(x,t) = t f(\frac{x}{t})$

I have been frequently coming across the function $g(x,t) = t f(\frac{x}{t})$ in my course on convex optimization. A friend of mine mentioned that it is the perspective function, but the book on ...
0
votes
0answers
27 views

low rank approximation using CVX

I try to use CVX toolbox to do "low rank approximation" work. The code is as follows: ...
0
votes
1answer
56 views

Does every strongly convex function has a stationary point?

Say does every differentiable $\mu$-strongly convex function $f:\mathbb{R}^n\mapsto\mathbb{R}$, with $\mu>0$ have a point where its gradient is $0$? If not so which is the minimum you can impose ...
0
votes
0answers
24 views

SOCP or SDP optimization problem

I am studying an optimization problem \begin{equation} \mathbf{w}^* = \text{argmax} \sum_{d=1}^D \log \bigg( \frac{|\mathbf{f}_d^H\mathbf{w}|^2+c_1}{|\mathbf{f}_d^H\mathbf{w}|^2+c_2} \bigg)\\ \\ ...
2
votes
0answers
27 views

proving that the ewma is convex

Hi: I know it's true but I don't know how to prove that exponentially weighted moving average when view ed as a function of $\lambda$, is strictly convex. The exponentially weighted moving average ...
0
votes
0answers
24 views

Using Taylor's theorem and Lagrange form of the reminder to prove the second order condition for convexity

I try to prove the second order condition for convexity. So far' I've done the following: First, I prove second order => convexity: Let $f$ be a function with positive semi-definite Hessian. Using ...
0
votes
1answer
25 views

Geometric interpretation of duality and Slater's condition

I am trying to study about optimization problems, Lagrange duality and related topics. I came across some presentation on the net, which claims to show the geometric interpretation of the duality and ...
0
votes
0answers
48 views

Which is the better way to optimize a function with 3 variables

I have an optimization function depends on 3 parameters a, b, and c. Which is the better way to optimize it? ...
1
vote
0answers
23 views

Property of Newton step for self-concordant convex functions

Suppose $f(x)$ is a convex and self-concordant function minimized at $x^*$. I have two starting points $\tilde{x}_0$ and $\hat{x}_0$ such that $|\hat{x}_0-x^*| \le |\tilde{x}_0 - x^*|$. We also know ...
1
vote
1answer
68 views

Optimization of competitive scenario

Suppose we have a function $f(x_1,x_2)$ with the following properties: Let $x^*=\arg \max_{x_1} f(x_1,x_2=x^*)$ and $x^*=\arg \min_{x_2}f(x_1=x^*,x_2)$. $f(x_1,x_2)$ is concave in $x_1$. ...
2
votes
2answers
38 views

Every concave function that is nonnegative on its domain is log-concave?

This is a statment from Wiki. I'm not sure why this is true: If: $f(\theta x+(1-\theta y) \geq \theta f( x) + (1-\theta)f(y)$ And $f(\cdot) \geq 0$ then: $$f(\theta x+(1-\theta y) \geq f( ...
0
votes
1answer
19 views

Huber penalty function in Linear programming form.

I am trying to solve problem 6.3(b) of Convex optimization by stephen boyd and Vandenberghe. The problem is this Express the following minimization as a QP,LP,SOCP or SDP $$ ...
0
votes
0answers
19 views

What's wrong with the following trace optimization?

I'm reading a paper that has used the augmented Lagrange function for optimization. I've tried to derive one subproblem but got a different answer from that in the paper. Could you help check it ...
0
votes
1answer
24 views

Optimization problem $L(R, PQ) \rightarrow \min$

Suppose we have some $n \times m$ matrix $R$ and we want to find non-negative decomposition on matrices $P$ of dimension $n \times d$ and $d \times m$-matrix $Q$. But since exact decomposition usually ...
3
votes
1answer
43 views

Upper bound on maximum absolute value of all subdeterminants of a matrix

Let $A \in \mathbb{R}^{m \times n}$ and let $\Delta(A)$ be the maximal absolute value of the determinants of the square submatrices of $A$. A simple lower bound would be $$ \Delta(A) \geq ...
2
votes
1answer
38 views

Faster gradient descent convergence by transforming the gradient?

If we modify the gradient descent update for a convex objective function $f(\boldsymbol{\theta})$ from $\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \nabla f(\boldsymbol{\theta}_t)$ to ...
1
vote
1answer
17 views

Is it right for chain rule in trace function?

The objective function is $$ f(X)=\min_X trace(B^TX^TCXBD) $$ we know the following derivatives from Matrix Cookbook, $$ \frac{\delta{trace(B^TX^TCXB)}}{\delta X}=C^TXBB^T+CXBB^T \\ \frac{\delta ...
1
vote
1answer
26 views

What is affine hull of conv(A)

Consider the set $A = \{(1,0),(0,1),(-1,0),(0,-1)\}$. The convex hull of $A$, i.e. $conv(A)$, should look like the following: (This is also a $l_1$-norm unit ball.) My question is what is the ...
0
votes
0answers
33 views

Uniform Sampling over Convex Polytope (not full-dimensional)

I want to simulate a uniform distribution on a convex polytope that is not full-dimensional for optimization purposes (to generate random points on the set I want to minimize over). The polytope is ...
0
votes
0answers
34 views

Relative interior

I'm having trouble solving the following equivalence. Let $A \in K^{m,n}, b \in K^{m}$ and $P := \{x \in K^m | Ax \le b\}$ Show that: a) There exists $x^1, ..., x^m \in P$ such that $A_{j*}x^j < ...
1
vote
1answer
31 views

About the slack variable for hinge-loss SVM

The hinge-loss SVM is defined $$ \min_{w,b} \frac{1}{2}w^T w+\sum_{i=1}^{N}\max\{0,1-y_i(w^Tx_i +b)\} $$ By introducing a slack variable $\xi_i$, the optimization problem is changed to $$ ...
5
votes
1answer
75 views

Constrained Optimizatoin: The Frank-Wolfe Method

A general convex optimization problem is framed as such: $$\min f(x) : x \in \Omega$$ where $\Omega$ is convex. The Frank-Wolfe method seeks a feasible descent direction $d_k$ (i.e. $x_k + d_k \in ...
1
vote
2answers
32 views

Solve matrix equation with some known values, assuming answer is symmetric positive definite

I'd like to solve $\boldsymbol{[K][U]=[F]}$ for $\boldsymbol{[K]}$ assuming that the answer is symmetric positive definite and contains some known values and that $\boldsymbol{[U]}$ and ...
0
votes
0answers
40 views

Can a positive definite kernel produce a kernel matrix which has negative eigenvalues?

(1) I've read that a symmetric matrix is positive definite when its associated eigenvalues are all positive. I am learning SVM lately, and have come to know a $d$th-degree polynomial kernel ...
0
votes
1answer
42 views

What is the correct change of variables to yield convexity in this nonlinear optimization problem?

$$ \text{min. } x/y \\ \text{s.t. } 2\leq x \leq 3 \\ x^2+y/z\leq \sqrt{y} \\ x/y=z^2 \\ x,y,z\geq 0 $$ To transform this problem into a nonlinear convex optimization problem, both the objective ...
1
vote
0answers
41 views

Distributed convex optimization problem

Consider the optimization problem $$ \min_{ x_1, \ldots, x_N } \sum_{i=1}^{N} f_i( x_i ) \\ \text{s.t.: } \sum_{i=1}^{N} x_i \in X, \ x_i \in X_i \ \forall i \in \{1, \ldots, N\} $$ where $f_1, ...
1
vote
1answer
34 views

Why test problems in convex optimization are mostly random?

Very often people who compare performance of different algorithms in convex optimization use randomly generated data. For instance, this often happens in compressed sensing and signal processing. Is ...
0
votes
0answers
36 views

About Intersection of two convex polytope?

the intersection of two convex hull of two polytope P and Q , is it the convex hull of the intersection of P&Q ? Conv(P) ∩ Conv(Q) = conv(P∩Q) ???.
0
votes
0answers
37 views

Learning pipeline for developing own optical flow algorithms

I am really sorry if this question is outside of this resource or too silly I am bachelor of computer science and a programmer in small company. And i am faced with the task of developing own custom ...
0
votes
1answer
26 views

Proof that the intersection of any finite number of convex sets is a convex set

How to prove that the intersection of any finite number of convex sets is a convex set? I have no idea.
0
votes
1answer
40 views

Minimizing a function of a complex variable

Given complex numbers $z_1,z_2,z_3,\ldots,z_n \in \mathbb{C}.$ Does there exist a $z \in \mathbb{C}$, for which the function $$f(z) = \sum_{j=1}^n |z-z_j|$$ achieves a global minimum? If yes, ...
1
vote
1answer
34 views

Toeplitz equality constrained least-square optimization

What is the fastest known algorithm for least-square optimization problem with a linear equality constrain \begin{align*} &\min \|K x - y\|^2 + \mu \|x\|^2\\ \text{s. t. }& Q x = v ...
0
votes
1answer
40 views

Is the optimization problem right?

If we want optimize the following problem $$ \min_x \{a(x)+c(x)\} $$ and we have $$ a = \min_y b(y) $$ then, could we directly optimize the following problem? $$ \min_x \{b(x)+c(x)\} $$
0
votes
1answer
32 views

quadratic constraints

Is it possible to reformulate the following quadratic constraints to conic constraints so that I use an SOCP solver $$ ( x_1^2 + x_2^2 ) - ( y_1^2 + y_2^2 ) \leqslant c $$ ...
1
vote
1answer
37 views

Proving that the solution of a norm constrained optimization is on the boundary of the set

I am trying to solve the following maximization problem $$\max_{||x|| \leq c} x^H A x,$$ where matrix $A$ is hermitian symmetric. I have been told that the argument of the maximum is on the ...
0
votes
0answers
19 views

Is there a unique tilted measure with specified marginals?

Suppose $\mathcal{A},\mathcal{B}$ are finite sets and $\mu_{A,B}(a,b)$ is a probability measure on the product set $\mathcal{A}\times \mathcal{B}$ so that $\mu_{A,B}(a,b)>0$ for each $a\in ...
4
votes
0answers
38 views

How to find accuracy of Matlab's quadprog solver?

I have solved with quadprog from Matlab a strong convex quadratic problem given as $$ f(x) = x^TQx + c^Tx$$ with constrains $$ Cx \leq b.$$ Now the output of quadprog is: Minimum found that ...
0
votes
1answer
25 views

unnecessary constraint in optimization problem

I have some optimization problem (optimizing parameter $\alpha$)with those constraints: $$\alpha_i\ge0$$ $$\sum\limits_i \alpha_i y_i =0$$ and a third constraints: $$w-\sum\limits_i \alpha_i y_i x_i = ...
1
vote
0answers
45 views

Is there any way to transform a non-convex optimization problem into a convex one?

I have an optimization problem which is described as $$\begin{array}{ll} \text{minimize}_x & c^{T}x\\ \text{subject to} & Gx \preceq h\\ & -x^{T}Px - qx - r \leq 0 \end{array} $$ where ...
2
votes
0answers
33 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
1
vote
0answers
18 views

Is there a good textbook/book out there that explains sub gradients thoroughly?

I was interested in learning and understanding sub gradients as much as I could from some good resource. I know what the definition is, but I seem unable to apply the definition to prove basic facts ...
0
votes
1answer
30 views

What is the sub-differential of the separable sum $R(w) = \sum^{d}_{j=1} |w_j|$?

Recall the definition of a sub-differential: $$\partial F(w_0) = \{ v : \forall w, F(w)-F(w_0) \geq v \cdot (w - w_0)\} $$ Intuitively, for any w in the domain of the function one can draw a plane ...
1
vote
1answer
29 views

How does $\in$ behave with simple algebra dealing with sub gradients?

I was trying to understand the following optimization problem: $$argmin_{v \in H} {R(v) + \frac{1}{2}||v - w||^2}$$ Assume $R(v)$ is Convex, proper and semi-continuous with a unique minimizer. ...
0
votes
1answer
22 views

Testing for Convexity

Could somebody please explain the method for answering a question like this?
1
vote
3answers
73 views

Compact set in R that is not convex?

Just need an example. For example, the I know the set [0,1] is compact because it is obviously closed and bounded. But I have no idea how to test for convexity
1
vote
1answer
34 views

Strong convexity on sets?

Consider the definition of convex functions: $$ f(tx+(1-t)y) \le t f(x)+(1-t)f(y) $$ It is easy to show the definition of the convexity on sets with respect to the above definition (Specifically for ...
0
votes
0answers
19 views

A variant of submodularity?

See the definition of submodulation functions: $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) $$ Suppose I make this definition a little stronger: $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B) + A ...
0
votes
1answer
24 views

Subgradient example

Let $f(x_1, x_2)$ be defined as: if $x_1 =0$ then $f(x_1,x_2)=x^2_2$ else $\infty$ The subgradient of $f(x_1,x_2)$ at $(0,0)$ is given as: $\mathbf{R} \times \{0\}$. (The real line crossed with ...