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

learn more… | top users | synonyms

2
votes
1answer
39 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
20 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
30 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
36 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
35 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
38 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 $$ ...
6
votes
1answer
87 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
39 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
44 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
49 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
44 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
38 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
43 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
40 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
29 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
42 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
36 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
35 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
40 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
21 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
44 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
46 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
34 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
20 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
31 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
81 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
39 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
21 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
27 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 ...
0
votes
2answers
38 views

Prove $A^TB$ is a positive semi-definite matrix?

$A,B \in R^{m\times n}$ and the singular values of both $A$ and $B$ are between 0 and 1. Is $A^TB$ a positive semi-definite matrix? Please show me the proof:)
0
votes
0answers
22 views

Linear independence of equality constraint gradients in constraint qualifications

I'm, trying to get an intuitive feel for the various constraint qualifications for KKT points. Most of them seem to rely on the linear independence of $\nabla g_i(x^*)$ where $g_i$ are the equality ...
1
vote
1answer
25 views

Difference between tangent cone and this constraint cone

Define the cone $G(\textbf{x} = \{\textbf{p} \in \mathbb{R}^n | \nabla g_i(\textbf{x}^T \textbf{p} \leq 0, i \in I(\textbf{x})\}$ So this is a cone associated with the inequality constraints that is ...
0
votes
0answers
22 views

constraint optimization: sparsity with non zero constraints

I have an obtimization problem in the following form. $\min f(x)\\ s.t \|x_i\|_0\leq\lambda\\ x_i \geq0\\ \sum_i x_i = 1$ where $f(x)$ is convex. What is the easy way to optimize it as I have a ...
2
votes
0answers
66 views

Affine functions as equality constraints in convex optimization problems

I am studying on an introduction to convex optimization problems. When defining a convex optimization problem, we have a convex object function, $f(x)$, a set of convex functions $g_i(x)$ where the ...
0
votes
0answers
13 views

Can the tangent cone contain more than the closure of the cone of feasible directions?

We know that the closure of the cone of feasible directions is contained in the tangent cone, but I'm wondering if it's possible for the tangent cone to consist of more than this closure?
2
votes
1answer
66 views

Is there a nice representation for KKT conditions for matrix constraints?

I have a convex programming problem: $\min \left\lVert J - R \right\rVert _F$ $J,R$ are matrices. $J$ is given for the problem. One of the constraints is: $R = KQ$ Here, $R,K,Q$ are matrices. $K$ ...
1
vote
2answers
44 views

$\,f:[0,1)\to\mathbb R$ is a concave differentiable function st $\,f(0)=0$. Show that $g:[0,1),g(z)=f(zx)/z$, for $x > 0$ is decreasing

Question: Suppose that $f : [0, 1) \to\mathbb R$ is a concave differentiable function such that $\,f(0) = 0$. Show that $g : [0, 1) \to\mathbb R$ defined by $g(z) = f(zx)/z$, for some given $x > ...
0
votes
1answer
46 views

distance between solutions in a convex optimization

Assume that you have the following convex optimization problem: $\min_{M} \|b+A\ M\ v\|_2$ subject to : $\|M\|_{2}<1$ (maximum singular value less than 1) where M is a suare matrix (n by n), A ...
0
votes
1answer
56 views

matrix convex optimization

How to solve the following problem explicitly? I mean closed form solution if possible. $\min_{M} \|M\ a-b\|_2$ subject to : $\|M\|_{\infty}<1$ (maximum singular value) where $M$ is a square ...
0
votes
0answers
104 views

Rank reduction to satisfy Barvinok's upper bound & Rank of a set notation

After reading n times the four first sections of the 4th Chapter of J.Dattorro's book (Convex Optimization & Euclidean Distance Geometry). I am confused between yes or no, every extreme point of ...
2
votes
2answers
32 views

Boundedness of sublevel sets of convex function (Boyd VandenBerghe)

(This is from the book Convex Optimization on p.474 on algorithms for unconstrained minimization) Assumptions The function $f : \mathbb{R}^N \mapsto \mathbb{R}$ is convex and twice-differentiable ...
0
votes
1answer
25 views

Confusion with a proof about the continuity of convex functions

I studying convex analysis and in my book I have the following statement and proof: Lets assume that $f:S\rightarrow \mathbb{R}, \;S\subset \mathbb{R}^n$ is a convex function. Then $f$ is ...
1
vote
1answer
39 views

Optimization with changing objective function

Is there any theory about (convex) optimization where the objective function is allowed to change during the optimization process? I have a problem where the objective function depends on some ...
1
vote
2answers
77 views

Why is any subspace affine?

I am studying 'Convex Optimization' written by Stephen Boyd. I am confused by an assertion in the book(page 27). Any one can tell me why and give an explanation ? Any subspace is affine, and a ...
1
vote
0answers
29 views

Partial concave maximization of subset of variables

Let $f(x_1, \dots, x_N)$ be a concave function in $x_1, \dots, x_N$. For arbitray $n>1$, prove that the (constrained) truncated function defined by $$g(x_1, \dots, x_{n-1}) = \max_{x_n, \dots, x_N ...
1
vote
2answers
52 views

Why does gradient descent make sense?

Suppose I define two functions of $x$ in terms of a convex function $f$ with a unique minimum $x_0$: $$f_1(x) = 1 \times f(x)$$ $$f_2(x) = 2 \times f(x)$$ Suppose I wanted to minimize each of these ...