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

learn more… | top users | synonyms

2
votes
1answer
94 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$
2
votes
1answer
3k views

Convexity of the product of two functions in higher dimensions

Exercise 3.32 page 119 of Convex Optimization is concerned with the proof that if $f:\mathbb{R}\rightarrow\mathbb{R}:x\mapsto f(x)$ and $g:\mathbb{R}\rightarrow\mathbb{R}:x\mapsto g(x)$ are both ...
2
votes
1answer
137 views

Prove or disprove that the given expression is “always” positive

I have previously asked a question and I tried to solve it by my own and it led to the question below: Prove or disprove that ...
2
votes
1answer
194 views

Simple resource for Lagrangian constrained optimization?

Just had an optimization lecture. I understand unconstrained methods like Newton and Gradient descent just fine, as well as the ideas that give rise to them. I don't really understand the ideas that ...
1
vote
0answers
23 views

can we prove that a certain supremum of affine functions is frechet differentiable or at least continuous?

Let $X$ be a Hilbert space. Let $A\colon \operatorname{dom} A\to X$ be linear operator with closed graph (not necessarily bounded). Define $$ g\colon \operatorname{dom}A\to \mathbb{R}:x\mapsto ...
1
vote
1answer
247 views

Maximizing a function by finding derivative

I want to find the value of $\vec{p}$, $p_s$, $p_t$ each of which is a function of the form $f:\mathbb{R}^2 \to \mathbb{R}$ that maximize the following function : $$\begin{align} \int_\mathbb{R^2} ...
0
votes
1answer
49 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 ...
0
votes
2answers
732 views

Derivation of soft thresholding operator

I was going through the derivation of soft threholding at http://dl.dropboxusercontent.com/u/22893361/papers/Soft%20Threshold%20Proof.pdf. It says the three unique solutions for $\operatorname{arg ...
25
votes
4answers
2k views

Please explain the intuition behind the dual problem in optimization.

I've studied convex optimization pretty carefully, but don't feel that I have yet "grokked" the dual problem. Here are some questions I would like to understand more deeply/clearly/simply: 1) How ...
10
votes
4answers
5k views

Difference between supremum and maximum

Referring to this lecture , I want to know what is the difference between supremum and maximum. It looks same as far as the lecture is concerned when it explains pointwise supremum and pointwise ...
17
votes
1answer
384 views

Properties of the Cone of Positive Semidefinite Matrices

The set of positive semidefinite symmetric real matrices form a cone. We can define an order over the set of matrices by saying $X\geq Y$ if and only if $X-Y$ is positive semidefinite. I suspect that ...
5
votes
1answer
210 views

Dual to the dual norm is the original norm (?)

I have the following questions about dual norms : How do you prove that the dual of the dual norm is in fact the original norm? This is what I have so far: If I have $\|y\|_* $ as the norm dual of ...
10
votes
5answers
716 views

Why is convexity more important than quasi-convexity in optimization?

In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
2
votes
2answers
172 views

Optimize a log det function with respect to a matrix, and the saddle point analysis

Suppose I want to to find the local minima of a logdet function $\mathcal{L}$ with respect to a Matrix $\mathbf{A}$, $$ \mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - ...
10
votes
2answers
524 views

If the Minkowski sum of two convex closed sets is a Euclidean ball, then can the two sets be anything other than Euclidean balls?

If for two convex closed sets $S_1$ and $S_2$, the Minkowski sum is a Euclidean ball then can $S_1$ and $S_2$ be anything other than Euclidean balls themselves. I suspect they can be but I haven't ...
3
votes
2answers
373 views

When finding root, does Newton's method fail if the function is non-differentiable?

According to wikipedia's description, the Newton's method finding a root presumes a differentiable function. Then, will it fail when encountering non-differentiable function? For example, can it find ...
3
votes
1answer
4k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
2
votes
0answers
62 views

How to get the minimum and maximum of one convex function?

Condition: $h,f\in \mathbb{C}^{N\times1}, \text{where}f =\hat{f} + e \text{ and } e^H e \leq 1,\ \ \ Q=h^Hff^Hh$. The Lagrangian function of $Q$ is $\mathcal{L} = h^H(\hat{f} + e)(\hat{f} + e)^Hh + ...
1
vote
2answers
652 views

Explain `All polyhedrons are convex sets´

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...
1
vote
1answer
106 views

Convex Combination of Hermitian Matrices

Assume all the matrices I discuss about are $N \times N$. Consider any two hermitian matrices $A_1$ and $A_2$ which are indefinite. The question is, In general, for any $A_1$ and $A_2$, does there ...
0
votes
1answer
179 views

a convex function on a 2 dimensional closed convex set

Let us say I have a closed compact convex set $\mathbb{S}$ on the 2-D plane (eg: a circle). Let any point $p$ in the 2-D plane be represented by $p=(x,y)$. I define the max function over 2-D plane ...
0
votes
1answer
93 views

Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$

Wikipedia here explains it like this: I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here: "If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
5
votes
0answers
141 views

Need advice: what should be my next step?

I am dealing with a quite algebraic question and I arrived at some good point. I had $2$ equations with $2$ unknowns and I was able to eleminate one of the variables. My final equation still seems ...
5
votes
1answer
120 views

a conjecture on norms and convex functions over polytopes

Suppose one has a convex, bounded polytope P $\subset R^n$ and a strictly convex function $f$ defined everywhere on $R^n$. $f$ has a unique minimum; and suppose this minimum occurs somewhere strictly ...
5
votes
0answers
162 views

Optimization of relative entropy

Wondering if my following question is an application of information theory: Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream ...
3
votes
2answers
165 views

How many points to find a polynomial?

I would like to fit a formula $ax^b + cx^d+ e$ to a set of points. I have two questions. If my data were perfect, how many points do I need in the worst case to get $a,b,c,d,e$ exactly? If my data ...
3
votes
1answer
339 views

Both convex and concave functions

Let $f$ be a function from $\mathbb{R}^n$ to $\mathbb{R}$, which is convex & concave and continuous with $f(0)=0$. How to prove that $f(x)=q\cdot x$ for all $x$ in $\mathbb{R}^n$, for a scalar ...
3
votes
1answer
370 views

Question about the simplex method complexity

So I know that in general the simplex method for linear and convex quadratic programming can require exponential time. But assuming a positive semidefinite quadratic program that is solvable by the ...
2
votes
1answer
81 views

Recovering the solution of optimization problem from the dual problem

In the context of (most of the times convex) optimization problems - I understand that I can build a Lagrange dual problem and assuming I know there is strong duality (no gap) I can find the optimum ...
2
votes
1answer
41 views

Minimization of norms

How do I minimize the following? $ min_{z>0} - zt + 1/2\ z\ ||\ Y + X_k\ /\ z\ ||_2^2 $ Also, $X_k^TX_k = 1 \ \ \forall k $ I am given that the answer should be : $ \sqrt{Y^T - 2t} + Y^TX$ ...
2
votes
1answer
869 views

Prove the supremum of the set of affine functions is convex

Let $\langle f_i \rangle _{i \in I}$ be a family of affine functions on a convex and compact set $\Omega \subset \mathbb{R^d}$ such that $f_i = a_i.x +b_i$ for $x \in \Omega$. Prove that f, defined by ...
2
votes
1answer
807 views

Why does a positive definite matrix defines a convex cone?

I've been working on convex optimization and got stuck. What exactly does a positive definite(p.d) matrix represent geometrically ? what kind of vector space it forms ? If I have a p.d matrix which ...
2
votes
3answers
1k views

Trace of a quadratic function, Convexity

Is trace($XX^T$) a convex function of matrix $X$? A linear function of a quadratic should be convex, but I could not prove by definition.
1
vote
1answer
84 views

What is a convex optimisation problem? Objective function convex, domain convex or codomain convex?

My teacher in the course Mat-2.3139 did not want to answer this question because it would take too much time. So what does a convex optimisation problem actually mean? Convex objective function? ...
1
vote
1answer
270 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
1
vote
2answers
63 views

Absract convergence of a suboptimal version of steepest descent

I'm looking for a citable reference to fill in a gap in an intermediate step of a proof which requires convergence of a suboptimal version of steepest descent. The function $f:\bf{R}^n\to\bf{R}^n$ I ...
1
vote
1answer
62 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
1
vote
2answers
63 views

How many methods for smoothing an unsmoothed function?

Which is the simplest one? For example, we smooth $f(x)=|x|$ to $$f(x)=\begin{cases} \frac{x^2}{\epsilon}+\frac{\epsilon}{2} & |x| \le \epsilon\\ |x| & |x|\ge epsilon ...
1
vote
1answer
150 views

Are these convex optimization problems equivalent?

Consider the optimization problem $$ \mathcal{P}_1: \qquad \min_{x \in \mathbb{R}^n} c^\top x \quad \text{sub. to } \ g(x,y_i) \leq 0 \ \ \forall i = 1,2,...,M$$ where $c \in \mathbb{R}^n$, and ...
1
vote
1answer
70 views

Is $ \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 $ convex?

Over at How many points to find a polynomial? it was suggested to minimize $$ f(a,b,c,d,e) = \sum_{1 \le k \le n} (y_k - a x_k^b + c x_k^d + e)^2 .$$ However I don't know if it is possible to find ...
0
votes
2answers
41 views

Minimize Function over Convex Subset

Suppose that C is a closed convex subset of $\mathbb R^n$ and $x \in \mathbb R^n$. The projection of $\mathbf x$ onto C is the closest point $\mathbf y \in C : \mathbf z = \mathbf y$ minimizes ...
0
votes
2answers
50 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
68 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)}$, ...
0
votes
1answer
101 views

Show convexity of the quadratic function

Can someone show this function is convex using the definition (without taking gradient)? $$F(x) = x^TAx + b^Tx + c$$ where $A$ is symmetric positive semi-definite.
0
votes
0answers
29 views

Confusion related to convexity of a quadratic function

Lets say I have the following function of X $f(X) = (AX^TBX)$ I didn't get why matrices A and B need to be psd to make f(X) convex. Clarifications guys
0
votes
1answer
284 views

Pointwise supremum of a convex function collection

In Hoang Tuy, Convex Analysis and Global Optimization, Kluwer, pag. 46, I read: "A positive combination of finitely many proper convex functions on $R^n$ is convex. The upper envelope (pointwise ...
0
votes
0answers
203 views

Gradient Descent with nonlinear constraint on Symmetric positive definite matrix space

I would like to find the stationary point $S_*$ (global minimum) that minimizes the function $f(S)=\mathrm{trace}(S)+m^2\mathrm{trace}(S^{-2})$ which has been proven to be convex in Convexity of ...
0
votes
0answers
72 views

Max Quadratic Expression

Let $A \in \mathbb{R}^{n \times n}$, $A = A^\top$, $B \in \mathbb{R}^{m \times n}$, and $\mathcal{C} \subset \mathbb{R}^n$ be a compact, convex set. For $A$ not negative semidefinite, how to globally ...
0
votes
1answer
98 views

what math topic is this kind of example part of? or what is needed to understand how to solve it? [closed]

we 100000000 sets/locations. each set has, A = % chance of finding a cure (there are many different types of cures) for cancer B = time it takes to extract a cure to caner C = the optimal % chance (IN ...
0
votes
0answers
124 views

MiniMax Theorem

Consider the compact sets $X \in \mathbb{R}^n$, $Y \in \mathbb{R}^m$, $A \in \mathbb{R}^n$, $M \in \mathbb{R}^{n \times m}$. For fixed $(\bar{a},\bar{B}) \in A \times M$, by the MiniMax Theorem we ...