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

learn more… | top users | synonyms

0
votes
0answers
14 views

How do I show that expected squared error stochastic optimization problem has a global optimum?

I was interested in showing that minimizing the following had a global optimum: $$ \mathbb{E}_{ (x , y) \sim P_{x,y}}[(\hat{x}(y) - x]$$ where $\hat{x}(y)$ is a linear function i.e. $\hat{x}(y) = ...
0
votes
1answer
28 views

Verifying stationary points - check my answer please - Has a hessian

Can someone check this for me; For $f(x_1,x_2,x_3) = x_1^2 + x_2^2 + x_3^2-x_1x_2+x_2x_3-x_1x_3-x_1+x_2$ the stationary point occurs at $\nabla f(x)^T =\left[ \begin {array}{c} 0\\ 0\\ 0\\ ...
0
votes
1answer
23 views

Why is a local min also a global min for convex functions?

As the title states, for an unconstrained minimizaton problem, of a convex function, why is it that the local minimum is also the global solution?
2
votes
0answers
52 views

the continuity of argmin on convex funtion

Define $$x'=\text{argmin}_{x_1}f(x_1,\lambda),$$ where $f$ is a strictly convex function on $x_1$ and $\lambda$. I would like to ask if there is any theorem about the continuity of $x'$ w.r.t ...
0
votes
0answers
19 views

Optimize log functions over polytopes

Let's consider the following optimization problem min $\sum_{i=1}c_i\log x_n $ subject $Ax\leq b$ ie, it is to optmize a weighted sum of logarithms over a polytope ($Ax\leq b$). Clearly if $c_i$'s ...
0
votes
0answers
35 views

How to prove that convex function has an increasing slope?

A function $f(x)$ in some domain $a\leq x \leq b$ is convex if and only if for any $x_1 < x_2 < x_3$ from domain $[a,b]$, $$\frac{(f(x_2)-f(x_1))}{(x_2-x_1)} \leq ...
0
votes
1answer
25 views

Is this a convex program?

I have a nonlinear optimization problem $\min \sum_{i=1}^n \sum_{j=1}^n y_{i,j}$ subject to $x_i- y_{i,j}x_j\leq 0$ $0\leq x_i\leq 1$ $y_{i,j}>0$ The question is whether this is a convex ...
0
votes
0answers
22 views

Transfrom QP to SOCP

Consider the following QP: $$\min \frac{1}{2}x^TQx+q^Tx+r$$ $$\text{subject to: } Ax \leq b$$ The equivalent SOCP is like the following (from the solution manual): $$\min u$$ ...
0
votes
0answers
27 views

convex function - global minimum

Suppose that $f(x):R^p \rightarrow R$ is a convex function with global minimum, say 0. Let $C=(x: f(x)=0)$, i.e. the set of the global minimum. Suppose that there exist at least one point $y$ such ...
2
votes
1answer
27 views

Does $\log(f(X))$ concave implies $\log(f(X^{-1}))$ convex?

One of my professor claims that $\log f(X)$ concave implies that $\log(f(X^{-1}))$ convex where $X$ is symmetric positive definite matrix. $\log(f(X))$ is a function defined on symmetric positive ...
1
vote
0answers
22 views

Subspace of tangent feasible directions

If $h: \mathbb{R}^3 \to \mathbb{R}^3$ defined by $h(x_1,x_2,x_3) = (x_1^3 - x_2 + x_3^2, x_2,x_1+x_2+x_3)$ I define $V(x)$ as a subspace formed by all directions tangent to some constrained set at ...
1
vote
0answers
29 views

Subdifferential of a convex function

How would I find a convex function $f: \mathbb{R} \to \mathbb{R}$ such that $\partial f(0) = [0,1]$ A subdifferential is just the collection of vectors $w \in \mathbb{R}^n$ such that $f(y) \geq ...
1
vote
0answers
19 views

Why is this set a subset of its polyhedral approximation - contradicting the gradient inequality?

Say we have a set $C:= \{y\in \mathbb{R}^n : g_i(y) \leq 0, \space i=1,...,m\}$ where $g_i : \mathbb{R}^n \to \mathbb{R}$ are convex and differentiable functions, then we have $\tilde C : = \{y: ...
1
vote
0answers
17 views

Convexity Proof with constraints on the gradient

Consider a minimization problem $(P)$ : minimize $f(x)$ subject to $\delta_C(x) \leq 0$ Now assume that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and let $f: \mathbb{R}^n \to \mathbb{R}$ be ...
1
vote
1answer
17 views

Show the following statements are equivalent - convexity

Let $C \subset \mathbb{R}^n$ be a set. Show the following are equivalent: (a) The set $C$ is convex. (b) The function $\delta_C : \mathbb{R}^n \to \mathbb{R} \cup \infty$ defined as: ...
0
votes
0answers
16 views

About the alternating optimization

The problem is defined as follows: $$ min_{A,B,C} f(A,B,C) $$ and the problem couldn't solve by gradient descent or close-form solution. Thus, the usual way is to use the alternating optimization: ...
1
vote
1answer
34 views

Convexity proof - can I get some pointers?

Prove that $C \subset \mathbb{R}^n$ is convex iff $\forall m \in \mathbb{N}$ and every set of $m$ points $\{x_1,...,x_m\} \subset C$ we have that $\sum_{i=1}^m \lambda_i x_i \in C$ Where ...
1
vote
2answers
23 views

How to prove that given log function is convex

How to prove that $log(1+e^{-x})$ is a convex function? [from comment]: I have tried with the basic definition of convex function..... like $f(ax+by) \leq af(x)+bf(y)$... but was not able to solve ...
0
votes
1answer
27 views

Steepest Descent Sequence

How can I compute the first three iterates for the steepest descent sequence $f(x_1,x_2) = \frac{(x_1^2+3x_2^2)}{2}$ beginning at $x_0 = (\frac{\sqrt{3}}{2}, \frac{1}{2 \sqrt{3}})^T$ $\nabla ...
2
votes
1answer
32 views

Constructing a newton sequence

How may I construct the newton sequence for the following: $(1) f(x_1,x_2) = x_1^4 + 2x_1^2x_2^2 + x_2^4$ with $x_0 = (1,1)$ and $x_0 = (1,0)$ $(2) f(t) = t^4 - 32t^2$ and $t_0 = 1$ To find ...
1
vote
0answers
48 views

Is the function $f(A)=-\log(tr(A^{-1}))-\log(\det(A))$ convex?

I am trying to show the following function is convex or not $$f(A)=-\log(\text{trace}(A^{-1}))-\log(\det(A)),$$ where $ A$ is positive definite. I know $\text{trace}(A^{-1}), -\log(\cdot)$ and ...
0
votes
0answers
16 views

Property of probability density function (pdf)

If $X$ is a random variable with a log-concave pdf. And suppose $Z = h(X)$ If $h(X)$ is convex, can we say $Z$ has a log-concave pdf? If $h(X)$ is affine, can we say $Z$ has a log-concave pdf? ...
0
votes
0answers
40 views

Proximal Mapping of Composition with Linear Operator

I've posted this question on math overflow but got no answer, so I think it might not be a research level question so I decided to post it here too. Let $A$ be an orthogonal matrix. It is well known ...
0
votes
0answers
21 views

Dot product - geometrical interpretation in convex analysis

I am studying a theorem on the characterization of solutions in nondifferentiable convex problems. Say that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and $f: \mathbb{R}^n \to ...
5
votes
1answer
73 views

References for hemicontinuity?

Let $X$ be a real vector space, $K\subset X$ be a nonempty and convex set. The mapping $f:X\rightarrow\mathbb{R}$ is said to be hemicontinuous if for every $u,v\in K$, the mapping ...
0
votes
1answer
40 views

Convexity of problem with inverse matrix

I am trying to solve the next problem \begin{aligned} & \underset{P}{\text{maximize}} & & \log \det P \\ & \text{subject to} & & A^T P^{-1} + P^{-1} A \preceq 0 \\ ...
1
vote
0answers
89 views

Conversion into linear program

I have an optimisation problem with decision variables that are multiplied with another (a weighted average is calculated). I'd like to convert it into a linear program. I found this link that ...
1
vote
0answers
39 views

Difficulty in understanding a solution: Constraint minimization of sum of Non-symmetric matrices

I am trying to understand why there is significance difference in the performance of two proposed solutions. Original question (Constraint minimization of sum of Non-symmetric matrices) ...
0
votes
0answers
25 views

convexity of inverse of a matrix

I know that the function $f(X)$ which maps matrix $X$ to $Tr((X)^{-1})$ is convex for symmetric positive definite $X$. This has also been answered in Is the trace of inverse matrix convex? for ...
0
votes
1answer
38 views

Does analytical solution exist for this convex euclidean affine projection problem with non-negativity constraints?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely, $X \in ...
1
vote
1answer
34 views

how to find the solution of this cost function?

I have the following cost function. $J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$ Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars. How can I find W?
0
votes
1answer
30 views

Determining corners of this convex set

Let $N \geq 2$ be an integer. Let $P:= \{ (a_1, \ldots, a_N) \in [0, 1]^N : \sum_n a_n = 2 \}$. Is $P$ the convex hull of $P \cap \{0, 1\}^N$? Edit: This is apparently true, see the beginning of ...
1
vote
0answers
25 views

Fenchel Conjugate of a norm squared

I was wondering if the fenchel conjugate of the $\frac{1}{2}||u||^2$, is the $\frac{1}{2}||u||_*^2$, where $||.||_*$ is the dual norm of $||.||$. This seems to be true for the $\ell_2$ norm. However, ...
0
votes
2answers
94 views

Constraint minimization of sum of Non-symmetric matrices

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \text{min} \hspace{4mm} \big(\lambda_1\left( \mathbf{y}^T V^{(1)}\mathbf{x} \right)^2 + ...
1
vote
1answer
28 views

How do I set a lower bound to the solution's norm in a QP problem

I know that LASSO-regularization can be used to scale into an $L_1$ upper bound for a solution. But what if I want the norm to be within a specific range $[a,b]$? ie. I also want to set a lower bound? ...
2
votes
0answers
30 views

Log concavity/convexity of a determinant

I was wondering if anyone would be able to help me determine whether the following quantity is log concave or not with respect to $\alpha$? $$\left[\det(\textbf Y^\top \textbf P \textbf G \textbf ...
0
votes
1answer
51 views

Proof - extreme point of a convex set

everybody! I am wondering how to prove the following theorem: Let $S \subset \mathbf{R}^{n}$ be a non-empty closed convex set. Then $S$ has at least one extreme point iff $S$ does not contain any ...
0
votes
1answer
34 views

Equality Constraints in Quadratic Programming

Now I am new to the world of primal-dual algorithms and I want to understand the SOCP-Code of Lobo/Vandenberghe/Boyd (primal dual interior point method). Currently I am working through Goldfarb and ...
3
votes
1answer
33 views

How to show $ \sup \inf g(x,y) \leq \inf \sup g(x,y)$?

Came across this little practice exercise, and I couldn't properly convince myself of this relation: Let $X,Y \subset \mathbb{R}^n$ and $g:X\times Y \rightarrow \mathbb{R}$. Show that $$\sup_{y \in ...
1
vote
3answers
38 views

Questions about coerciveness and convexity

I just have a few yes/no questions, and would really appreciate if you could correct me where I am wrong, and for what fundamental flaw I have. 1. Would the set of coercive functions a linear space? ...
0
votes
2answers
21 views

Coerciveness and Positive definiteness relation?

Let $A ∈ \mathbb{R}^{n×n}$ be a symmetric matrix. How can I demonstrate that A is positive definite iff the function $q(x) := x^TAx$ is coercive . I know the eigenvalues of A have to be positive for ...
1
vote
1answer
33 views

Why does the Weierstrass theorem fail if a set is not compact?

By Weierstrass theorem I mean that if $f:\mathbb{R}^n \to \mathbb{R}$ is continuous and $C \subset \mathbb{R}^n$ is compact, then the theorem asserts that a solution $x^*$ of $$ \text{min} _{x\in ...
0
votes
2answers
32 views

Union of 2 convex sets

Let $f : \mathbb{R}^n→ \mathbb{R}_∞$ be convex over the sets A, B which are also convex. $A ∩ B = ∅$ and $A ∪ B$ is convex. Then is $f$ is convex on $A ∪ B$? Why or why not? I am confused ...
1
vote
1answer
33 views

Proving convexity using the Hessian

Suppose I have $f: \mathbb{R}^n \to \mathbb{R}_\infty$ which is twice continuously differentiable, on some convex set C, which is open. How can I prove that $f$ is convex over C, iff the hessian ...
1
vote
1answer
23 views

Problems with vector vector derivative in optimization

I have a loss function of the followoing form: $L(\mathbf{a}) = \|\mathbf{b} - \mathbf{a}\|_2^2$ Where, $\mathbf{a}$ and $\mathbf{b}$ are vectors of dimension $d\times 1$. I need to calculate ...
2
votes
0answers
30 views

Maximin problem as LP?

Consider the following setting. Let $A\in \mathbb{R}^{3 \times m}$ and $B\in \mathbb{R}^{m\times 3}$ be two matrices such that each of their columns must add up to a given $c\in \mathbb{R}$. Denote by ...
1
vote
2answers
25 views

Is f(x)=-log(x) a closed function?

I am reading Convex optimization written by Stephen Boyd. In page 640, there is an example said \begin{equation} f(x)=-log(x) \end{equation} is a closed function. But this function seems does not ...
0
votes
1answer
44 views

Coerciveness of a function - help

I'm trying to show that $$f(x_1,x_2,x_3) = e^{x_1^2 + x_2^2} + (x_1^2 + x_2^2 + 3x_2)^{500}$$ is not coercive, but am struggling to see anything. Any help is appreciated!
1
vote
0answers
23 views

Convexity over a line given a convex interval [duplicate]

Let $f : \mathbb{R}^n \to \mathbb{R}_∞$ be a function. I want to prove that $f$ is convex over the line $L_{v,x_0}$ iff $\psi : \mathbb{R} \to \mathbb{R}_∞$ $\psi(t) := f (x_0 + tv)$, is convex ...
0
votes
0answers
11 views

Subsets being cones

I am trying to self-study convex optimization and still trying to get into the gist of it. There is a question in my text as follows: Let $V$ be the set of sequences whose terms are contained in ...