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

learn more… | top users | synonyms

0
votes
1answer
11 views

Conic hull of a proper function

Suppose $f$ is a proper function pn $\mathbb{R}^{n}$with $f(0)>0$.Now consider $$ g(x) = \text{inf}\{t: (t,x) \in \text{cl(cone(epi(}f)))\} $$ Can I always say that $\exists y \in \mathbb{R}^{n} : ...
2
votes
1answer
63 views

Difference between maximize $\sum\limits_{k=1}^Kg_k(\mathbf{x})$ and $\sum\limits_{k=1}^{K}\log(1+g_k(\mathbf{x}))$ in convex optimization

I have a problem of the following form: maximize $\;\;\;\,\sum\limits_{k=1}^Kg_k(\mathbf{x})$ subject to: $\;\,\,f_i(\mathbf{x})\leq\,1\,\forall\,i\in\{1, 2, \dotsc, m\}$ ...
0
votes
0answers
55 views

Expressing rank condition of a matrix in terms of its elements

Let $x \in \mathbb{R}^{n}$, define $X = xx^{T}$. I have an optimization problem with some linear constraints and few quadratic constraints, and I have to solve for $x$. Using $X$ as the unknown ...
0
votes
1answer
336 views

Semi-positive definite Hessian matrix and local minimum

Suppose we have a function $F(x)$ defined as \begin{equation} F(x) = \frac{1}{2}x^TAx + b^Tx +c, \end{equation} where \begin{equation} A = \begin{bmatrix} 4 & 2 \\ 2 & 1 \\ ...
0
votes
0answers
24 views

Sparse coding with local sparseness of dictionary

The title is probably pretty unclear, I hope I am able to explain it better here. I am currently working on a problem in the field of sparse coding, that is Principal Component Analysis, Non-negative ...
1
vote
2answers
30 views

Is this a polyhedron?

Is $S$ a polyhedron? $$S=\{x\in\mathbb{R}^n|\|x-x_0\|\le\|x-x_1\|\}$$ where $x_0, x_1$ are given. $S$ is the set of points that are closer to $x_0$ than to $x_1$. I was thinking the ...
0
votes
1answer
22 views

Quadratic Program over Box Constraints

Consider $f:\mathbb{R}^n \rightarrow \mathbb{R}$ defined as $$ f(x) := x^\top x + c^\top x $$ for some $c \in \mathbb{R}^n$. Define the (compact) "Box" $$X := \{ x \in \mathbb{R}^n \mid x_i \in [ ...
2
votes
1answer
82 views

Is the following objective function jointly convex?

I have the following optimization problem: $$ \begin{aligned} & \underset{\alpha, \gamma}{\text{minimize}} & & \end{aligned} \frac{1}{2} \|y - \sum\limits_{i=1}^{S}\gamma_{i}\cdot ...
7
votes
2answers
298 views

Derivative of nuclear norm

I'm trying to take the derivative of nuclear norm with respect to its argument. nuclear norm is defined in the following way: $$\|x\|_*=\mathrm{tr}(\sqrt{x^Tx})$$ I'm trying to calculate: ...
0
votes
0answers
65 views

KKT conditions for nonsmooth convex problems

What are the KKT conditions for a non-smooth convex function? Is the vanishing gradient of Lagrangian, replaced by $0$ in sub-differential of the Lagrangian, and all other things remain the same? I ...
1
vote
0answers
47 views

Reference table of “tricks” for converting problems to standard LP, QP, SOCP, etc. form?

Where can I find a decent source/reference that which I can use to look up the various standard "tricks" for converting typical problems to standard form in LP, QP, SOCP, etc.? The Charnes-Cooper ...
0
votes
1answer
76 views

Explain the convexity by looking the hessian matrix of a function

The hessian matrix of a function is given by, $$ H = \begin{bmatrix} a & b & c \\[0.3em] b & b & 0\\[0.3em] c & 0 & c \end{bmatrix} $$ where, ...
0
votes
0answers
24 views

As a beginner, I would like to solve convex quadratic maximization problem with a gradient descent variant in probability simplex?

I know the basics of gradient approaches to optimize the function iteratively, but for this case have have a equality constraint as $\sum_{i=1}^Nx_i = 1$ where each $x_i \geq 0$ with the objective ...
1
vote
1answer
68 views

How to find a positive semi-definite linear combination?

Suppose we are given two explicit symmetric matrices $X$ and $Y$ and we'd like to find a non-zero real linear combination $aX+bY$ that is positive semi-definite (if possible). Is there a way to go ...
0
votes
0answers
14 views

NNLS for under determined system

I have system of equations to solve Ax=B under x>=0. I read that Non Negative least Square(NNlS) algorithm proposed by Lawson and Hanson could solve this system for over determined case( number of ...
0
votes
1answer
59 views

How to solve this optimization problem?

Suppose I have the following problem: Maximize: $\quad\quad x_1+x_2+x_3+x_4$ Subject to: $\quad\quad \dfrac{\gamma\;a_1\;x_1}{\gamma\;a_2\;x_4+1}\geq1$, $\quad\quad\quad\quad\;\;\quad\quad ...
1
vote
1answer
54 views

Partial derivative on convex set

If we have a function $f:U \rightarrow R$ ($U \subset R^n$) which is partially differentiable on a convex set U with $\frac{\delta f}{\delta x_1} = 0$ for all $x \in U$. How can we prove that $f$ ...
1
vote
1answer
141 views

Proof of the Moreau decomposition property of proximal operators?

Given the prox operator i.e. $ prox_h (x) = arg min_u (h(u) + 1/2 ||u-x||^2_2) $ the Moreau decomposition property says that $ x = prox_h (x) + prox_{h^*} (x) $ where $h^*$ is the conjugate of ...
0
votes
2answers
39 views

Lagrangian with inequalities

I have a toy question on SVM , where i have to find the weight $w$ by solving the Lagrangian multiplier method by hand . I know Lagrangain with equalities only . Here I have to deal with inequalities ...
0
votes
1answer
36 views

Express a function as difference of convex functions (DC)

is there a way to express the function $$1-\exp \Big( \frac{-\max(0,x)^2}{\alpha} \Big)$$ as the difference of two convex functions (DC)? Thanks
0
votes
1answer
49 views

Minimize $L_2$-norm of $x1-b$ where $x \in R, b \in R^n$

Minimize $L_2$-norm of $x1-b$ where $x \in R, b \in R^n$ $||x1-b||_2 \rightarrow ||x1-b||^2_2=||x1-b||^T||x1-b||$ (squaring $L_2$-norm doesn't change outcome and yields quadratic) ...
1
vote
1answer
19 views

Null space and minimization

Let $x^*\in\text{argmin }f(x)=\text{argmin }\frac{1}{2}\|Ax-b\|^2$ where $A$ is a linear operator. Show that $\text{argmin }f=x^*+\text{Null}(A)$. For $x\in x^*+\text{Null}(A)$ we have ...
0
votes
1answer
52 views

Relax equality into inequality in convex problem

Let $\mathbf{x}, \mathbf{z}, \underline{\mathbf{x}}, \overline{\mathbf{x}} \in \mathbb{R}^{I}$, where the first two are variables and the last two are given data. I have the following problem: ...
1
vote
1answer
42 views

Minimizing difference and individual variables in convex problem

Let's say I have the following optimization problem: $$ \begin{align*} \min_{\mathbf{x},\mathbf{y}} & \sum_i x_i-y_i \\ \mathrm{s.t.} & \{\mathbf{x},\mathbf{y}\} \in ...
0
votes
1answer
33 views

Prove that the intersection of convex sets is convex using the following three points…

I want to prove each point, then, use points (1) and (2) to prove (3). $C_{1} = \lbrace x \in \mathbb{R}^{n} \mid h(x) = 0 \rbrace $ is convex iff $h(x)$ is affine in $C_{1}$ $C_{2} = \lbrace x ...
3
votes
1answer
56 views

Prove that $e^{tx} \le xe^t + 1-x$

Prove that $$e^{tx} \le xe^t + 1-x$$ for $t \ge 1$ and $0 \le x \le 1$ I think I need to use the fact that e is convex? But I can't quite see it. Any help appreciated Thanks.
0
votes
1answer
82 views

Solution to a Quadratic Minimization with Norm Constraint

How do I solve the optimization problem \begin{align} &\min_{\mathbf{x}\in\mathbb{C}^N}\mathbf{x}^H\mathbf{A}\mathbf{x}+2\Re\{\mathbf{b}^H\mathbf{x}\} \\ \mbox{subject to }\\ ...
3
votes
3answers
76 views

Logistic function as “difference of convex functions” (DC)

is there a way to express the logistic function $$\frac{1}{1+\exp(-x)}$$ as the difference of two convex functions? Thanks
1
vote
2answers
171 views

Why is this weighted least squares cost function a function of weights?

Here is a picture from my book regarding weighted least squares: Totally lost here, so I extracted the main nested issues confusing me: First Question: I know that in any LSE we want to minimize ...
1
vote
1answer
37 views

How to obtain primal problem from Lagrangian?

If you're trying to optimize $\min_x f_0(x)$ subject to $f_i(x) \leq 0$ then the Lagrangian would be $$L(x, \lambda) = f_0(x) + \sum_i \lambda_i f_i(x)$$ The dual problem is $\max_\lambda g(y)$ ...
2
votes
1answer
56 views

“Support function of a set” and supremum question.

I have already learned about what a supremum means from wikipedia and from another answer here. However I am not quite sure what 'supremum over a set of functions' means exactly. As an example, my ...
0
votes
2answers
59 views

Inequality involving max is confusing me.

I am trying to understand one line in a derivation here. Simply put, the statement is that: $$ max\{\theta \ f_1(x) + (1-\theta) \ f_1(y) \ , \ \theta \ f_2(x) + (1-\theta) \ f_2(y)\} \leq \theta \ ...
1
vote
1answer
52 views

Examples of affine functions and convex sets

I'm just learning about convexity and affineness, and I've read over some similar questions asked here, but those were more about general properties. I need some help applying those properties to a ...
0
votes
0answers
21 views

Conic Farkas lemma for dual programm

Suppose $C\subset \mathbb{R}^n$ is a regular cone (convex, closed) and $C^*=\{y\in\mathbb{R}^n \mid y^Tx\geq 0\}$ the dual cone and $A\in\mathbb{R}^{m \times n}$. I want to show that 1) There exist ...
1
vote
1answer
34 views

Could anyone give me an example of non-smooth strong convex function? [closed]

Could anyone give me an example of non-smooth strong convex function? I cannot figure out one.
1
vote
1answer
85 views

Confusion related to augmented lagrangian multiplier method

I have this confusion related to the augmented lagrangian multiplier method from this tutorial How come the gradient wrt y is equal to $\rho(Ax^{k+1}-b)$
3
votes
2answers
117 views

Singular Values of Matrix as Optimization Problem

Assume that $A$ is a positive semidefinite symmetric matrix. It is known that $$\max_{||y||\leq1} \quad y^TAy$$ Has an analytical solution which is the maximum eigenvalue of $A$. This isn't hard ...
0
votes
1answer
95 views

SDP formulation of noisy low rank matrix completion (2)

Thank you Michael for the answering my previous question, SDP formulation of noisy low rank matrix completion. It seems that I overlooked the problems in my initial question. I didn't recognize the ...
0
votes
0answers
33 views

Linear least squares with sparse inequality constraints for support function estimation

The initial problem is the following: $$ ||h - h^{0}|| \to min \; \; s.t. Qh \leq 0 $$ where $h^{0} \in \mathbb{R}^{n}$ is known vector and $Q$ is a $m \times n$ matrix. The problem arises in specific ...
0
votes
0answers
45 views

optimization problem in mathmetical finance using convex duality

I'm interested in the application of stochastic processes and stochastic calculus in mathematical finance. In my lecture I often see a certain optimization problem usually of a convex function. ...
0
votes
1answer
32 views

A question on convex

I am thinking about this without solutions. I would like you to give hints. Let $Q$ be a polyhedron with $Q=convex.hull (X)$ for some $X \subset R^n$. Let $E$ be a face of $Q$. Prove that $E \cap X ...
1
vote
1answer
37 views

An equation related to covariance matrix, square root of the matrix, and Euclidean norm.

How can I prove this equation: $${ ({ x }^{ T }\Sigma x) }^{ 1/2 }={ \left\| { \Sigma }^{ 1/2 }x \right\| }_{ 2 }$$ In which $\Sigma $ is a covariance matrix. I tried some numerical examples in ...
0
votes
0answers
82 views

Calculation of the set for the polar tangent cone?

I have the following theorem in my book. Assume that $\tilde{x}$ is a local minimum from a minimization problem and that f(.) is differentible at $\tilde{x}$ Let $T_X(\tilde{x})$ be the tangent cone ...
0
votes
2answers
74 views

Is the geometric-to-arithmetic function convex or concave?

Consider a vector $\mathbf{x} \in \mathbb{R}_{++}^N$. Also consider two functions, $g(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, and $a(\mathbf{x}): \mathbb{R}^N \rightarrow \mathbb{R}$, ...
0
votes
3answers
136 views

Concave function divided by a convex function. What is the result?

Let us say that I have a function $f(x)$ that we know is a concave. And let us also say that we have another function $g(x)$ that is a convex. If I make a new function, $h(x) = \frac{f(x)}{g(x)}$, ...
1
vote
1answer
42 views

How to verify correctness of a Fenchel conjugate derivation

Suppose I derived Fenchel conjugate of a function. My goal is to check if my solution is right. Suppose the steps are not available any more and only the final solution is present. Is there any ...
0
votes
0answers
28 views

Show that the Rosenbrock function is strictly convex for a specific region

So we know that the Rosenbrock function is a test function of sorts, but can anyone prove that a specific region is strictly convex? Rosenbrock eqn: $ f(x_{1},x_{2}) = 100(x_{2} - x_{1}^{2})^{2} + ...
1
vote
1answer
87 views

Tangent Cone is a cone?

I first give two definitions. Def1: A set $S$ is a cone if $x \in S, \lambda \geq 0 \implies \lambda x \in S$. Def2: Let $S$ be any set (we may assume $\mathbb{R}^n$ with the usual Euclidean ...
0
votes
2answers
31 views

is convex hull of intersection equal to intersection of convex hull

is $convexhull(S_1\cap S_2)=convexhull(S_1)\cap convexhull(S_2)$ where $S_1$ and $S_2$ are finite sets.
0
votes
0answers
34 views

Isomorphisms of Convex Cones

A convex cone $C$ is a subsets $C \subseteq V$ of a vector space which is closed under positive linear combinations, i.e. for $\lambda, \mu > 0$ and $u,v \in C$ it is $\lambda u + \mu v \in C$. An ...