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

learn more… | top users | synonyms

1
vote
2answers
16 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 - ...
-3
votes
0answers
30 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
19 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
21 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. ...
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 ...
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 + ...
0
votes
1answer
733 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
421 views

convex hull function in matlab

Is there anyway to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
4
votes
1answer
356 views

What is the time complexity of conjugate gradient method

I have been trying to figure our the time complexity of conjugate gradient method I have to solve a system of linear equations given by $$ Ax=b $$ where A is sparse and positive definite symmetrix ...
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
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 ...
0
votes
1answer
15 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
2answers
28 views

How do I justify that a second order cone is an intersection of half space

I am studying convex optimization right now, and the text book claims that a second order cone is a collection of intersections of half space $$K_n = \bigcap_{ u:\|u\|_2 \leq 1} \{(x,y) \in R^{n+1 } ...
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 ...
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
2answers
50 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
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
1answer
383 views

proximal operator of infinity norm

What is the proximal operator of $||x||_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
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$ ...
0
votes
0answers
15 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) ...
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 ...
1
vote
1answer
311 views

Generalization of soft threshold operator?

For certain $\ell_1$-regularized optimization problems, a critical computational step is the soft threshold operator: $\mathcal{S}_t(x) = \mathrm{sgn}(x)\circ \mathrm{max}(|x|-t)$ where $\circ$ is ...
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)
0
votes
3answers
446 views

Intuition behind gradient VS curvature

In Newton's method, one computes the gradient of a cost function, (the 'slope') as well as its hessian matrix, (ie, second derivative of the cost function, or 'curvature'). I understand the intuition, ...
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 ...
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 ...
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 ...
4
votes
2answers
256 views

why in Phase I of the simplex method, if artificial variable become nonbasic, it never become basic?

Does anybody has idea how to solve this problem ? "Show that in Phase I of the simplex method, if an articial variable becomes nonbasic, it need never again become basic. Thus, when an articial ...
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 : ...
1
vote
2answers
33 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
37 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 ...
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 ...
1
vote
1answer
85 views

On the convexity of the element-wise norm 1 of a pseudoinverse

Let us define $\|A\|_1$ the element wise norm 1 of a matrix $A \in \mathbb{R}^{n \times m}$ as $$ \|A\|_1= \sum_{i,j} |A_{i,j}|. $$ Obviously, this function is convex over $\mathbb{R}^{n \times m}$. ...
2
votes
1answer
51 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 ...
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
64 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
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 ...
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$. ...
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
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 ...