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

learn more… | top users | synonyms

0
votes
0answers
25 views

Convex minimization of a linear function

I have the following optimization problem to be solved $R^{k+1}$ = $\text{argmin}_R$ $\frac{1}{2\mu}\left\lvert R - W_{R}^{k}\right\rvert_{F}^{2}$ + $\frac{1}{2}\left\lvert R - ...
0
votes
1answer
43 views

Show that $A^{*}\partial g(A\bar{x})\subseteq \partial(g \circ A)(\bar{x})$

Suppose that $g: Y \rightarrow ]-\infty,+\infty]$ and let $A: X \rightarrow Y$ be a linear operator (i.e., an $m \times n$ matrix if X and Y are $\mathbb{R}^n$ and $\mathbb{R}^m$, respectively). Let ...
3
votes
1answer
35 views

Convex optimization where both the region and function are ugly

I am trying to build a gradient descent algorithm for a convex function over a convex region in high dimension with no closed form. All I can do is: Check whether a point is in the region Evaluate ...
2
votes
0answers
21 views

Why does the dual problem of the SDP become a maximum eigenvalue problem?

This SDP problem with the variable $X \in \mbox{S}^n$ where $\rho \gt 0$ $$\max \mbox{Tr}(AX) - \rho \mbox{1}\lvert X \rvert \mbox{1} \\ \mathrm{subject\; to}\;\mbox{Tr}(X)=1, \\ X \succeq 0 $$ ...
1
vote
2answers
19 views

show that a set is convex

How do I show that the following set is convex: The set $\{\,x\mid x+S_2 \subseteq S_1\,\}$, where $S_1$, $S_2 \subseteq \mathbb{R}^n$ with $S_1$ convex. I understand that I need to express this set ...
1
vote
1answer
40 views

Minimum eigenvalue representation

http://www.eecs.berkeley.edu/~wainwrig/ee227a/SDP_Duality.pdf On the first page of this lecture note on semidefinite programming (13.3) the following is stated: $ \lambda_{\min}=\min_{Y}\, ...
2
votes
1answer
57 views

Consider $(f\Box g) (z)=\inf_{x+y=z}(f(x)+f(y))$

Consider $$(f\Box g) (z)=\inf_{x+y=z}(f(x)+g(y))$$ Find two convex functions $f$ and $g$ from $X$ to $\mathbb{R}$ such that the infimum given above is never a minimum. Can anyone help with finding ...
0
votes
0answers
36 views

How to design a strict constraint term (never violate this constraint) for matrix decomposition

It is a low-rank sparse decomposition problem: $ D= ML + S + \epsilon$, that we know the matrix D can be decompose into 2 part that one part $L$ is low rank, the other part $S$ is sparse, $\epsilon$ ...
0
votes
2answers
44 views

Determine the domain of $(f\oplus g)$ in terms of the domains of $f$ and $g$

I am having trouble understanding convolution and would like some help with the following: Let f and g be functions from $X$ to $]-\infty,+\infty]$. Determine the domain of $(f\oplus g)$ in terms of ...
0
votes
0answers
33 views

Suppose that $f$ and $g$ are functions from $X$ to $ ]-\infty, +\infty ]$

Suppose that $f$ and $g$ are functions from $X$ to $ ]-\infty, +\infty ]$ and that $x\in dom(f+g)$. Show that $\partial f(\bar{x})+\partial g(\bar{x})\subseteq \partial(f+g)(\bar{x})$. Proof: Let ...
0
votes
0answers
16 views

Using the simplex algorithm to measure sensitivity of objective function

Say I use the Simplex algorithm to solve a standard LP problem. I know that the last tableau's reduced cost coefficients tell me how much I need to increase the coefficient of a variable before it ...
0
votes
1answer
45 views

Linear Convex Decomposition

Let $X=\{x_1,x_2,x_3,x_4\}$ be the four vertexes of a square in $\mathbb{R}^2$, and $H$ the convex hull of $X$. Then, in general, the points $y\in H$ that cannot be written in a unique way as a ...
0
votes
3answers
67 views

How to show that $f:\mathbb{R}^n\to\mathbb{R},\quad f(x)=\log\big[\sum_{i=1}^{n}{e^{x_i}}\big]$ is convex on dom$f=\mathbb{R}^n$

for now I've got the following: set $y_i=e^{x_i}\quad\Rightarrow \frac{\partial y_i}{\partial x_i}=y_i\quad \Rightarrow$ $\nabla_x f=\frac{1}{\sum_{i=1}^{n}{y_i}}[y_1\; \dots\; ...
-1
votes
1answer
45 views

Suppose that f : X → ]−∞, +∞] is convex and proper, that x ̄ ∈ dom f and that λ > 0. Show that

Suppose that $f : X → ]−\infty, +\infty]$ is convex and proper, that $\bar{x} \in dom f$, and that $\lambda > 0$. Show that $$\partial^{\infty}(\lambda f)(\bar{x}) = ...
0
votes
0answers
17 views

Singular value decomposition:Canonical Correlation, Reformulation of the objective function

The CCA method aims to find two loading vectors or projections $\alpha$, $\beta$, the linear combinations of variables in $X$ and $Y$, to maximize the correlation between $\alpha ^t X$ and $\beta^t ...
1
vote
0answers
31 views

Proof of Stiemke's Theorem via Dubovitskii–Milyutin

Prove that the system $$\sum_{i=1}^{m} x_i a_i = 0, x_i > 0, i = 1, . . . , m,$$ has no solution if and only if the system $$<a_i , y> ≤ 0, i = 1, . . . , m,$$ not all zero has a solution. ...
0
votes
0answers
18 views

The dual of a cone with every face exposed

Let $C \subseteq \mathbb{R}^n$ be a closed convex cone with the property that every of its faces is exposed, i.e. the intersection of $C$ with a supporting hyperplane. Does then the dual cone $C^*$ in ...
1
vote
1answer
32 views

Assuming that $f$ is convex and continuous from the right at zero show that $∂f(0)$ is empty using the definition of the subdifferential.

Suppose that $$ f(x)= \begin{cases} +\infty,\;\;\;\;\;\;\;if\; x<0\\ 0,\;\;\;\;\;\;\;\;\;\;if\;x=0\\ x\ln(x)\;\;\;\;if\;x>0 \end{cases} $$ Assuming that $f$ is convex and continuous from the ...
0
votes
0answers
113 views

Simplex Method and Unrestricted Variables

I was hoping someone here could explain this issue: say you are working with a set of linear equations in standard form ($a_1 x_1 + a_2 x_2 + a_3 x_3 + \ldots + a_n x_n= c$ where $c$ is the constant), ...
0
votes
0answers
140 views

Projection of hybercube without Fourier-Motzkin Elimination

I am not a mathematician but I do use some tools from geometry in robotics. So, I apologize if what I am writing here is not mathematically consistent but I really do need your help. I have a linear ...
1
vote
1answer
65 views

soft thresholding derivation with two terms

I am trying to minimize the following function $$argmin_x||x-y||^2_2 + ||x-z||_2^2 + \lambda || \frac{x- w}{c}||_1$$ I have been doing it for while but i am not sure how to do it. I have already been ...
0
votes
2answers
84 views

Show that a real-valued function with non-empty subdifferential is convex

Let $f:X \to \mathbb{R}$ be a function such that $\partial f(x)\neq \emptyset$ for all $x \in X$. Show that $f$ is convex. I would appreciate some help with getting started on this problem. Thanks
0
votes
1answer
68 views

Suppose that $f = ι_{\mathbb{R}_+}$. Show that [closed]

Suppose that $f = ι_{\mathbb{R}_+}$. Show that $0$ is in the boundary of dom f and that $∂f(0)$ is nonempty using the definition of the sub differential. Any hints or suggestions is greatly ...
1
vote
1answer
76 views

Examples of tangent cone

In http://users.ece.utexas.edu/~cmcaram/EE381V_2012F/Lecture_2_Scribe_Notes.final.pdf The definition of a tangent cone is defined as the closure of the feasible directions. Definition 9. (Tangent ...
1
vote
3answers
48 views

Inequality involving a convex function

Do the points that satisfy an inequality involving a convex function constitute a convex set? Specifically if $x \in \mathbb R^n$ and I have a function $f(x)$ then is the set $\{x \mid f(x) \le 0\}$ ...
0
votes
1answer
27 views

Ordered field, Bounded set, and the containment

I am now in engineering mathematics class and it goes over some basic set theory. Since I haven't had any experience with set theory, three statements leave me confused. Thanks for your help! ...
2
votes
1answer
33 views

Show a function is convex on the given domain

$f(x,y,z)=\frac{(y+2z)^2}{(x-3y)}$,$\quad$ on $\{(x,y,z)\in R^3\mid x-3y>0\}$. I tried to figure out the Hessian matrix of $f(x,y,z)$ to see whether it is positive definite , but it's very ...
0
votes
1answer
41 views

Suppose that f : X → ]−∞, +∞] is convex and proper, that x ̄ ∈ dom f

Suppose that $f : X → ]−∞, +∞]$ is convex and proper, that $x ̄ ∈ dom f$ , and that $λ > 0.$ Show that $$∂(λf)(x ̄) = λ∂f(x ̄).$$ I am looking for a little help with this one. I am a bit unclear ...
0
votes
0answers
19 views

Have I correctly implemented the line search method using gradient descent?

I'm refreshing my memory regarding the line search optimization method on convex functions using gradient descent. Running through the nuts and bolts of some manual calculations, let's say we have a ...
0
votes
0answers
8 views

What kind of dataset should I be testing randomized Kaczmarz algorithm on?

I know that it works best for sparse matrices and a over determined system of linear equations. But, I still find it a bit abstract. I would be glad if someone could point me to some dataset or write ...
0
votes
0answers
32 views

Optimality criterion for unconstrained convex optimization problems

Consider a general convex optimization problem: \begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & f_0(x) \\ & \text{subject to} & & f_i(x) \leq 0, \; i = 1, ...
2
votes
2answers
67 views

Minimum-norm Projection on Convex Sets

The general method of Projection on Convex Sets (POCS) can be used to find a point in the intersection of a number of convex sets i.e. $$ \text{find } x \in \mathbb{R}^N \text{ s.t. } x \in ...
4
votes
2answers
43 views

Geometric Median Problem with a twist

Given two vectors $x, y$ in $\mathbb{R}^n$ and scalar $\alpha$, what is the value of $\alpha$ that minimizes $||\alpha x - y ||_1$? Give an algorithm to find the minimum. I've tried couple of ...
0
votes
2answers
43 views

Subgradient of a composition w/ affine $f$

Let $f:\mathbb{R}^n \to \mathbb{R} \cup \{ \infty \}$ be convex, w/ subgradient at x in its domain $\partial f(x):=\{ d:f(y)\geq f(x)+d^T (y-x),\forall y\in \mathbb{R}^n \}$. Let $h(x'):=f(Ax'+b)$, ...
0
votes
0answers
11 views

Lipschitz Continuity of the Solution Set of LP with a single additional Convex Constraint

Consider the following Linear Program with interval bounds on the decision variables: \begin{equation} \begin{aligned} S(\mathbf b) = \ & \arg \min_{\mathbf x \in \mathbb R^n} && \mathbf ...
0
votes
1answer
49 views

Why proximal gradient instead of plain subgradient methods for LASSO?

I was thinking to solve LASSO via vanilla subgradient methods. But,I have read people suggesting to use Proximal GD. Can somebody highlight why proximal GD instead of vanilla subgradient methods be ...
0
votes
0answers
18 views

Smart penalty term for constant sparsity of matrix columns

I am looking, in an convex optimization problem, for a smart way to write a penalty term $Reg(A)$ (where $A$ is the coefficients matrix of the data $X$ w.r.t. the learned dictionary $D$, $A=D^{T}X$), ...
1
vote
0answers
18 views

Quasiconvexity analog for function with an integer domain.

Suppose I have a function that is not quasiconvex, as in the graph below, but would be quasiconvex if we cared only about integer points. That is, $f:X \subset \mathbb{Z}\rightarrow \mathbb{R}$ ...
1
vote
1answer
26 views

Karush-Kuhn-Tucker NLP

Consider the nonlinear program Minimize: \begin{align}f(x,y) = \frac{1}{2}x^2 - 10xy + 10y^2\end{align} Subject to: \begin{align}2x +y^2 &\le 5 \implies g_1(x,y)=2x + y^2 -5 \le0 \\ ...
6
votes
1answer
117 views

How is the Lagrangian related to the perturbation function?

Given a convex programming problem $$\begin{align*} \text{minimize} &\quad f(x) &\\ \text{such that} &\quad g_i(x) \leq 0 & i=1\dots k\\ & \quad h_j(x) = 0 & j= k+1\dots n ...
1
vote
0answers
36 views

Closed formula for unconstrained (matrix) optimization problem

Let $M$ be a square matrix of size $n$, $(a_i)_{i\in[1,n]},(b_i)_{i\in[1,n]},y$ vectors of size $n$ and $\lambda$ a real. Is there a closed form for the following problem: $$\arg\min_M ...
0
votes
2answers
54 views

Is always a convex function two times differentiable

Assume that f is twice differentiable, that is, its Hessian or second derivative $\nabla^2f$ exists at each point in dom$f$, which is open. Then f is convex if and only if dom$f$ is convex and its ...
0
votes
0answers
21 views

is the Superellipse function convex or not?

I'm trying to solve an optimization problem and i need to know if the following constraint of Superellipse is convex or not $\left|\frac{x-x_o}{a}\right|^n + \left|\frac{y-y_o}{b} \right|^n \geq 1$ ...
0
votes
0answers
53 views

How to prove the following Taylor expansion for twice differentiable functions

I want to prove the following: Let $f(x)$ be a twice differentiable function. Then, $$\begin{array}{l} \exists t \in \left[0,1 \right ] \; s.t., \\ f\left(y \right ) = f\left(x \right ) + \left(y-x ...
0
votes
0answers
18 views

Holding the constraints of a constrained optimization when transformed into unconstrained optimization

Suppose there is a constrained convex optimization problem as shown below \begin{equation} \begin{aligned} & \min\limits_{\mathbf{x}} & & f(\mathbf{x}) \\ & \text{s.t.} & & ...
2
votes
1answer
30 views

Under what conditions does a convex objective function have a concave value function?

Suppose that $u:\mathbb{R}^{n} \to \mathbb{R}$ is a continuous, (weakly) convex function. Now define the value function $\phi$ to be: $$\phi(p,w) = \max_{x>>0} u(x)$$$$ \text{ subject to: } p ...
0
votes
1answer
39 views

Optimization function convex or not

I need to comment whether my optimization function is convex or non-convex. My optimization function is in the form of $(y-y_{cap})^2$. y is know. $y_{cap}$ comes out of a MATLAB pfile. So, ...
3
votes
0answers
77 views

A complex optimization problem (maximize determinant of matrix)

Background Assume we have a 2 columned matrix ${\bf P}$ and this matrix can be written as $${\bf P}= [ {\bf p_1 \,\,\,\, p_2}]$$ where ${\bf p_1}$ is the first column (vector) of ${\bf P}$ and ${\bf ...
0
votes
0answers
16 views

Let $K$ be a nonempty, closed and convex cone in $X$. Define $k^{\ominus}=N_k(0).$ Show that $k^{\ominus\ominus}=k.$ [duplicate]

Let $K$ be a nonempty, closed and convex cone in $X$. Define $$k^{\ominus}=N_k(0).$$ Show that $k^{\ominus\ominus}=k.$ So, what I think this question is asking me to do is show that the normal cone ...
0
votes
2answers
51 views

Projection of a hyperplane

Let $\alpha$ be a vector in $X$ such that $||\alpha||=1$ and let $\beta\in\mathbb{R}$. Consider the hyperplane $$C= x\in X:\langle a,x\rangle=\beta.$$ Prove that $$P_c(x)=x-(\langle a,x ...