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

learn more… | top users | synonyms

-5
votes
0answers
17 views

Is Frobenius norm of a gram matrix convex [on hold]

Suppose $X \in \mathbb{R}^{m \times n}$ and $S \in \mathbb{R}^{m \times m}$ Is the function $f(X) = ||XX^T - S||^2_{fro}$ convex w.r.t X ? Here, $S$ is a constant matrix. One can think of $XX^T$ as ...
1
vote
0answers
19 views

The optimization problem of soft margin Support Vector Machine: How to interpret?

I try to understand what exactly we are trying to optimize in the case of Support Vector Machine problem, which supports soft margins. The original problem is posed first as, without soft margins ...
0
votes
0answers
34 views

Bounded polyhedrons

Given a bounded polyhedron $P=P(A,b)$ and with $x$ s.t. $Ax<b$, show: $\exists \ \alpha>0 \ \ \ \ \ \text{ s.t.}\ \ \ \alpha^Tx\leq1, \ \ \ \ \forall x \in P $ How I should proceed to prove ...
0
votes
1answer
11 views

Convexity preservation and global optimality

This is a question I've had a tough time getting a good answer to. Consider the problem to minimize $f(x)$. Assume $f$ is differentiable and nice in every way, but we do not know if $f$ is convex. A ...
1
vote
2answers
21 views

Proving Lipshitz continuous over a convex set with Projection Operator

Suppose a problem $$\min_{x \in \mathbb{R}^{n}} f(x)$$ subject to $x \in \Omega$ which is a closed and convex set. If $\nabla f(x)$ is Lipschitz continuous in $\Omega$, then prove that $$e(x) = x - ...
-2
votes
0answers
35 views

Intersection of the closure of epigraph and subgraph of f function

Can you give an example of a function $f:R^p \to\ R$ such that $Grf \neq \overline{epif}\cap\overline{subf}$ where $p\in N$ and $Grf=\{(x,y)\in R^px R \mid f(x)=y \}, epif=\{(x,y)\in R^pxR \mid ...
-1
votes
0answers
21 views

Convex basis and conical basis (how to draw?)

There is a question, I'm struggling with: Find vertices of the following described polyhedron, $P:=P(A,b)=conv(V)+cone(E)$ where $V$ is the set of all vertices of $P$ and $E$ is the set of all ...
0
votes
0answers
41 views

What kind of an optimisation problem am I dealing with? [on hold]

I have a connected graph made up of $x$ vertices. Each vertex has a probability $p$. I want to determine the total probability in traversing as many vertices as possible, Edges have a certain cost to ...
0
votes
0answers
22 views

What does coordinate descent actually do?

We've done a bunch of theoretical stuff in my optimization class, but basically no time for the actual implementation details. I'm trying to get an understanding of coordinate descent, which if I'm ...
0
votes
0answers
25 views

Convex optimization with groups

I am relatively new to convex optimization and am looking to solve a resource allocation problem. I understand, that if my utility function is concave the following problem constitutes "an ...
0
votes
0answers
23 views

Is the ratio trace problem convex?

I have a ratio trace problem described as follows: $\arg\max_{w} trace((w^tAw)*inv(w^tBw))$, where A and B are full rank matrices. This problem can be solved via generalized eigenvalue problem. ...
1
vote
1answer
31 views

Efficient solution for a quadratic + norm objective.

I want to minimize an objective function of the following form: $$ \begin{split} \text{Minimize} \quad & x^T D_x x + y^T D_y y + z^T D_z z + q_x^T x + q_y^T y + ...
2
votes
0answers
17 views

discrete nonlinear convex optimization relaxation over a dense set

Be a discrete nonlinear convex optimization problem $P$ \begin{align} \underset{x\in \mathrm{C}^n}{\mathrm{min}} \ \ \ f(x) \\ Ax=b \\ c \leq x \leq d \end{align} $C$ is a dense in $F$. Is solving ...
0
votes
1answer
16 views

KKT for not convex problems

In my optimization course we learned something about KKT for not konvex problems: $$min \; f(x)$$ $$s.t. \; c(x)=0$$ $$d(x)\geq 0$$ $$f(x): \mathbb{R}^n\rightarrow \mathbb{R}$$ $$c(x): ...
1
vote
0answers
25 views

Minimization using logarithmic barrier function

I'm thinking of the quadratic problem(QP) \begin{align} &\underset{x\in \mathrm{R}^n}{\mathrm{Minimize}}\ \ \ \frac{1}{2}x^\top{}Qx + f^\top{}x\\ &\mathrm{subject\ to}\ \ \ \ a_ix \leq b_i\ ...
0
votes
0answers
27 views

How does this optimization problem satisfy Karush-Kuhn-Tucker Conditions?

I am following Andrew Ng's course notes on Support Vector Machines at: http://cs229.stanford.edu/notes/cs229-notes3.pdf There is something in these notes which I do not understand. SVM's basic ...
3
votes
2answers
51 views

Intuition about gradient

https://en.wikipedia.org/wiki/Gradient Gradient is a vector which we can obtain from any differentable function taking its partial derivatives. From Wiki: "...the gradient points in the direction of ...
0
votes
1answer
31 views

How to prove that a cone is closed?

How to prove a cone $K$ is closed ? I know that $K$ is a set, for a set, if it is not open, then it is closed. But how to prove that it is closed directly ?
1
vote
2answers
97 views

Prove this function is convex

we have $ g: R^n \rightarrow R$ is a concave function and $S$={$x :g(x)> 0$} and $f:S \rightarrow R$ and $f(x)$=$1/g(x)$ so we must show that $f$ is a convex function
0
votes
0answers
17 views

Minimization of a weighted least-squares problem by Lagrange multiplier method

Problem: Let $Y = (y_1, y_2, \dots, y_m) \in \mathbb{R}^{m \times n}$ and $k \in \mathbb{R}^{m}$ satisfy $\sum_{i=1}^{m} k_i =1$ and $k \geq 0$. Show that $x=Yk$ is a minimizer for $h(x) = ...
0
votes
0answers
9 views

direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority? [migrated]

Is there a direct conversion between gradient descent ([1], Alg 1 ) and any of the following algorithms? 1) Weighted Majority: http://onlineprediction.net/?n=Main.WeightedMajorityAlgorithm 2) ...
0
votes
2answers
52 views

Parameter optimization using a regression model.

I am working on an optimization problem. I build a regression model to understand the behavior of a system which depends on two variables which are functions of another two variables. My regression ...
0
votes
0answers
13 views

Polar cones' property [duplicate]

I am trying to prove: $A \subseteq B \implies B^\circ \subseteq A^\circ$ where $A^\circ$ is polar cone of $A$ ($A$ convex cone) and $B^\circ$ is polar cone of $B$ ($B$ convex cone)
1
vote
0answers
19 views

Conic hull of outer products

Consider the set of rank-k outer products, defined as $\{XX^T | X \in R^{n\times k}, rankX = k \}$. Describe its connic hull in simple terms. I have found the solution of this exercise but I have ...
1
vote
1answer
28 views

What does 'the level set is bounded' exactly want to tell?

'The level set is bounded.' occurs in many theorems and other places. I think I can understand the definition of 'level set' but I don't know what does 'it's bounded' want to tell me exactly in ...
0
votes
0answers
24 views

Are these functions convex functions?

$f_i(z) = f_i(x,y) = y_i^\alpha - x_i$, where $x,y \in R^n$, $z = (x, y)$, $\alpha \in R$ and $\alpha > 1$, $i = 1, \dots, n$. Are these functions convex functions ? For $f_i$, the gradient is $ ...
0
votes
1answer
35 views

How to show these two problems have equivalent solutions

I have two problems, where $A$ is positive definite: $$\inf \{ x^TAx + b^Tx : 1-x^Tx \ge 0,\ x \in \mathbb R^n\} \ (1)$$ and $$ max_\lambda \ q(\lambda) = -0.25b^T(A+\lambda I)^{-1}b - \lambda : ...
0
votes
0answers
22 views

Property of monotone operator (Positive definite)

I would like to prove this statement: "$F$ is monotone if and only if $\nabla F$ is positive semidefinte." I only know $F$ is monotone with respect to $\Omega$ if and only if ...
1
vote
2answers
34 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and ...
0
votes
1answer
38 views

Find those values 'a' which belongs to the Convex Hull

Find those values of 'a' for which (1,a,1) belongs to the convex hull of $$\{(0,0,0), (1,1,2),(2,4,-6), (1,3,8)\}$$ Give me hints as much as you can, I would like to understand the mindset rather ...
2
votes
1answer
61 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate? I have no idea how to start this. Anyone know any books with these kinds of questions (and ...
0
votes
1answer
32 views

Conditions for unique solution of a maximization problem?

Let $S\subseteq \mathbb{R}^2$, $d:=(d_1,d_2) \in S$, and $s:=(s_1,s_2)$ a generic point of $S$. Assume that there exists $s \in S$ such that $s_1>d_1$ and $s_2 >d_2$. Consider the following ...
2
votes
1answer
26 views

Is there Lipschitz property for subdifferential?

I'm trying to bound the quantity $\langle \nabla \Psi(x),\bar{x}-x \rangle$ above, with the bound depending on $\|x-\bar{x}\|$ and perhaps also of $\|x-y\|$ for fixed (but not varying) points $y$. ...
0
votes
0answers
13 views

How to work with difference-of-elements penalty in optimization

I am trying to solve the optimization problem $$\min_{H,S>0} \|W(H+S)-X\|^2_F+Q(H)+\eta\|S G\|_F^2$$ where $X\in\mathbf{R}_+^{m\times T}$, $W\in\mathbf{R}_+^{m\times k}$, ...
2
votes
2answers
65 views

Efficiency of a max-min problem for $\sum_{j=1}^m |b_j-a_j|$ with $a_i$, $b_j$ restricted to convex sets

Consider the following optimization problem: $$\max_{\{a=(a_1,a_2,\ldots,a_m)\in A\}}\min_{\{b:=(b_1,\ldots,b_m)\in B\}} \sum_{j=1}^m |b_j-a_j|.$$ Is computing the optimal value of this problem ...
2
votes
1answer
25 views

What is the solution for this quadratic program?

Given scalars $p_1\geq p_2\geq \cdots \geq p_r > 0$, can we find a solution for following problem? \begin{align} \text{minimize} & & & \sum_{j=1}^{r} p_j (1-t_j)^2 \\ \text{s.t.} \\ ...
1
vote
0answers
33 views

Can we ever have E(argmin(f)) = argmin(E(f))?

Consider a parametric real-valued function $f_{\boldsymbol{\alpha}}:\ \mathbb D^N \rightarrow\mathbb R$ whose parameters $\boldsymbol\alpha$ vary according to some distribution $\psi$, and $\mathbb D$ ...
1
vote
1answer
22 views

Show that scalar-valued function of a matrix is convex

Consider the mapping $$f(X) = g\left(\frac{b}{a^TXa}\right),$$ where $g$ is a convex function, $b$ is a strictly positive scalar, $a$ is a real vector, and $X$ is restricted to be symmetric and ...
1
vote
1answer
22 views

What is the definition of “convex” and “relaxation” concepts in clustering?

I have following text from a paper i am trying to understand: I don't understand what does below sentence refers to as being convex/non-convex The problem is that even though the objectives ...
0
votes
0answers
13 views

reference request for solution to SDP is an extreme point

I'm looking for a reference which establishes that the optimal value for a standard SDP is attained at an extreme point. For instance, this is noted below Theorem 1.2 of ...
0
votes
0answers
19 views

convexity of function built from piecewise linear convex function?

Let $B(x):[0,1] \rightarrow [0,1]$ be piecewise linear increasing convex function with $B(0)=0$ and $B(1)=1$. (Think of the power of the neyman-persron test). Let $E(x)=-log(B(1-e^{-x}))$ a logaritmic ...
0
votes
1answer
29 views

Quadratic Program reformulation

I have the quadratic program $$\max\quad \mu^Tx+r_fx_0-\gamma \sum\limits_{i=1}^n |x_i-y_i|-\frac{\lambda}{2}x^TVx$$ $$\text{s.t. }\quad \mathbb{1}^Tx+x_0=1$$ where $\mu$, $r_f$, $\gamma$, $\lambda$, ...
2
votes
1answer
52 views

Sum of k-largest eigenvalues of a symmetric matrix as an SDP

I found the following statement from a google search. If $S_k(\mathbf{X})$ is the sum of the $k$ largest eigenvalues of a symmetric $m\times m$ matrix $\mathbf{X}$, then,$$S_k(\mathbf{X}) \leq t$$ is ...
1
vote
1answer
22 views

Express this linear optimization problem subject to a circular disk as a semidefinite problem.

I have to express following problem as a semidefinite problem: $ min \, F(x,y) = x + y +1$ subject to (1) $(x,y) \in \mathbb{R}^2 : (x-1)^2+y^2\leq 1$ Only affin equality conditions should be used. ...
0
votes
2answers
42 views

Prove convexity of function over space of positive definite matrices

I want to show that the function $f(X) = -log \ det(X)$ is convex on the space $S$ of positive definite matrices. What I have done: It seems like this problem could be tackled by considering the ...
0
votes
0answers
20 views

Feasible solutions in semidefinite programming - beyond Slater's theorem

Suppose a semidefinite program is given by: \begin{align} \text{Maximize:}&\quad \text{Tr}\left[AX\right],\\ \text{subject to:}&\quad \Phi\left(X\right)=B,\\ &\quad X\geq 0. \end{align} ...
0
votes
1answer
45 views

Type of convex function?

I want a convex function $f:\mathbb{R} \to \mathbb{R}$ with the following property: given points $x,d \in \mathbb{R}$, and $\alpha \in (0,1)$, we have $$f(x + \alpha d) \geq \alpha f(x + d).$$ Is ...
0
votes
1answer
33 views

Distributed Newton methods for large scale problems

I am keen to know about the literature landscape for distributed convex optimization methods which use second order information like the Newton step. This is as such a less evolved area compared to ...
1
vote
1answer
32 views

Analytical solution to the first PCA direction

It is known that the first PCA direction for a dataset of $n$ points is the unit vector with max variance after projecting the points onto this vector. I wonder whether there are some analytical ...
0
votes
2answers
25 views

convexity of piece wise function

I have a piece-wise function defined on the real line. The pieces are connected continuously, and the second derivative of each piece is strictly positive. Does this means that the function is convex? ...