Tagged Questions

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

learn more… | top users | synonyms

0
votes
1answer
28 views

Proportion of domain in which convex function is small

Let $K \subseteq \mathbb R^n$ be a compact convex set with volume $V$, and let $f: K \to [0,1]$ be a convex function with domain $K$. Assume that $\min_{x \in K} f(x) = 0$. I claim that, for every ...
0
votes
0answers
23 views

Verifying if the gradient is correct or not

I was following this article to verify if the gradient that I had derived and calculated was correct or not Let say my function if $f(\theta)$. The derivative/gradient wrt $\theta$, $g(\theta)$ ...
0
votes
1answer
16 views

Optimization issues with positive definite constraints

I have an optimization problem where I have to optimize a function f(A) where A is a matrix(sparse). Like A = \begin{array}{cccc} A_1 & A_0 & A_0 & 0 \\ A_0 & A_2 & 0 & A_0 ...
1
vote
0answers
44 views

Issues with quasi Newton method convergence

I have this issue with the convergence of the quasi newton method. I have a convex objective function which I need to minimize wrt some parameters. I generated some synthetic data using a defined ...
0
votes
1answer
283 views

Finite optimal value for a linear program with unbounded feasible region.

I read this problem in CLRST : Show that a linear program can have finite optimal objective value even if the feasible region is not bounded. Now all the cases I could think of where such a thing ...
2
votes
1answer
496 views

Affine sets and affine hull

Mathematically an affine hull can be expressed as $ Aff[C] = \{\theta_1x_1 + \theta_2x_2 .... \theta_nx_n| x_i \in C \ \ \sum_{i=1}^{n}\theta_i = 1 \}$ Intuitively can anyone explain what this ...
0
votes
2answers
59 views

Non-elementwise Matrix Derivatives

Let A,B,C,D,X be matrices. I'd like to perform a Gradient Descent minimization to the loss functin $$ tr[(AXBX^TC-D)^T(AXBX^TC-D)] $$ My question is, how to take the gradient efficiently w.r.t. $B$? ...
1
vote
1answer
573 views

Prove convexity of squared Euclidean norm

I need to prove that the square of the Euclidean norm is convex, so: $||\theta x+(1-\theta)y||^2\leq\theta||x||^2+(1-\theta)||y||^2$. Can I use the triangular inequality (if yes, how?) or should I ...
1
vote
1answer
82 views

strict separation theorem?

Im learning and we have a theorem that says: Let $C$ be a non-empty, convex subset of $\mathbb R^d$ and let $p \in \mathbb R^d$ be a point which is not in the closure of $C$. Then there exists a ...
0
votes
0answers
16 views

Confusion related to a function used for optimization

I have a function $f(x)$, such that at point $x'$, it attains its minimum value, but the gradient at this point $x'$ is not equal to $0$. On the other hand the function $f(x)$ has slightly higher ...
0
votes
0answers
27 views

Confusion related to Newton's method for optimization

I am trying to use Newton's method for optimizing a certain function f. However, I am having some issues. I am using Armijo rule for finding the step size. So my iterations are like this $x_{t+1} = ...
1
vote
1answer
90 views

Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$

$f: R^n \to (-\infty, \infty]$ is a convex function. Prove that $ri (epi f)=\{(x, y): x\in ri (dom f), y >f(x)\}$ I have used definition of convex functions to prove that the right-side is ...
0
votes
0answers
33 views

How fast Interior Point method can be when solving Quadratic Programming problems?

Given the following Quadratic Programming problem: $\;\;\;\;\; \min x^TQx+c^Tx $ s.t. $Ax=b$ $\;\;\;\;\; x\ge0$ where $x\in \mathbb{R}^n$, $Q \in \mathbb{R}^{n \times n}$ is a positive ...
1
vote
2answers
138 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? ...
0
votes
0answers
28 views

||w||=1 constraint in maximizing geometric margin of large-margin classifier.

In a video lecture regarding large-margin classifiers while deriving the primal and dual representations, the professor at the outset mentioned that given a geometric margin as follows: gamma = ...
0
votes
1answer
34 views

Help with a property of a convex function

I'm studying linear and nonlinear programming and on my book I bumped into the following statement: $$\lim_{\alpha \to 0} \displaystyle \frac{f(\textbf{x}+\alpha ...
0
votes
1answer
74 views

(pseudo-/quasi-)convexitiy of ratio between quadratic and affine function

Let $X\subseteq\mathbb{R}^n$. I have the following function $f:X\rightarrow\mathbb{R}$: $$ f({\bf x})= \frac{c_1 + \sum_{i=1}^n a_ix_i +\sum_{i=1}^n b_ix_i^2}{c_2+\sum_{i=1}^n d_i x_i}\enspace.$$ All ...
3
votes
2answers
91 views

why is argmin $\|w\|^2$ equivalent to $\operatorname{argmax} 1/\|w\|$

I was wondering why the maximization of $1/\|w\|$ is equivalent to minimizing the squared norm of $w$. Shouldn't it be equivalent to just minimizing the norm of $w$? This is a very basic optimization ...
2
votes
1answer
50 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$ ...
0
votes
1answer
34 views

Square of 2-norm

This might be silly but I am stuck with the following problem: $ || Y - Z_i/x||^2_2 $ = 2t How would I solve to get $x $ from this equation?
0
votes
1answer
159 views

KKT conditions on minimization problem

I am trying to get an explicit solution to the following problem with the help of KKT conditions. But I am stuck. The problem: $ min_x 1/2 ||y-x||^2_2 + \lambda||x||_1 $ This is what I have done ...
1
vote
0answers
64 views

Strong Duality and Duals of linear programming problem

I have the following problem: $ max_{x,y} \ x + y $ subject to $ 2x + y \leq 1 $ $ x + 3y \leq 3 $ $ x,y \geq 0 $ How to find the dual of this problem using the Lagrangian? I have done the ...
1
vote
1answer
80 views

Dual of this primal optimization problem?

How would one find the dual of the following problem? $min_x 1/2 ||y-x||_2^2 + \lambda||x||_1 $ Can someone please explain to me how to do this since there are no specific constraints?
1
vote
0answers
23 views

Issues related to positive definiteness in a convex optimization problem

I have some issues in a convex optimization problem. My f(X) is a convex function of X where X is a positive definite matrix. X is very sparse and has a handful of non zeros values. Now I only need to ...
0
votes
1answer
63 views

Is this function convex or concave?

I have a function, $f(x_{0},x_{1},......x_{n})=\sum^{n-1}_{i=0}A_{i}r^{-(x_{i}+x_{i+1})}-B$ $A_{i} >0$ for all $i$ and $B>0$ and $1 \leq r \leq 2$ so above function is convex or concave? ...
2
votes
0answers
80 views

Uniqueness of the solution

We know that 1) Minimise of a convex function the unique solution exists 2) Maximise of a concave function the unique solution exists How about 1) Minimise of a strictly convex function? 2) ...
5
votes
1answer
383 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 ...
0
votes
0answers
58 views

Matrix fractional minimization via SOCP

This is Exercise 4.27 in the book Convex Optimization. Express the following problem as an SOCP: $\text{minimize}\quad (Ax+b)^T(I+B\,\textbf{diag}(x)\,B^T)^{-1}(Ax+b)\\ \text{subject to} \quad ...
3
votes
1answer
72 views

What type of convex constraint is defined by SQRT?

Let $A$ be an $n \times n$ positive semidefinite matrix and $\forall k, x_k \in \mathbb{R}^n$. The distance with respect to this matrix is defined as $ \|x_i -x_j\|_A := ...
1
vote
0answers
21 views

Confusion related to interior point method

I was reading this wiki article related to interior point method. I didn't get when they say that it applied Newton's method to get an update for $(x,\lambda)$. How the expression at the end ...
0
votes
1answer
81 views

Maximize Trace with Lyapunov inequality as constraint

Let $C$ be a given symmetric matrix, $A$ be a given Hurwitz matrix and $X$ be a symmetric positive definite matrix. Is the following problem solvable to give unique, optimal $X$? max $tr (CX)$ ...
1
vote
0answers
59 views

Confusion related to fmincon function in matlab

I was reading this help section of matlab's fmincon function that uses interior point algorithm for solving an optimization problem. It says the following optimization problem is replaced by To ...
0
votes
0answers
263 views

Is a linear-fractional function convex?

For example a simple linear-fractional function $f(x) = \frac{a^Tx+b}{c^Tx+d}$ with the domain of $f$ being $\lbrace x|c^Tx+d > 0\rbrace$, where $a, c, x \in \mathbf{R}^n$ and $b,d \in \mathbf{R}$. ...
1
vote
0answers
52 views

Is the following problem convex , quasiconvex, or nonconvex?

I want to get the optimal matrix $W$. But I am not sure whether it can be resolved. Note that $W,\mu,\lambda_{1},\ldots,\lambda_{K} $ are variables, others are fixed. Is it convex or quasiconvex or ...
0
votes
1answer
310 views

How do I prove that the composition of an affine function preserves convexity?

What would be the formal proof that $ f(Ax + b) $ given $ f(x) $ is a convex function ? I got to the point where I expanded $$ f(\lambda(Ax+b) + (1- \lambda)(Ay+b)) = f(A(\lambda x + (1 - \lambda)y) + ...
1
vote
1answer
340 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?
2
votes
0answers
66 views

Maximizing the smallest eigenvalue of a linear combination of matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ ...
3
votes
1answer
398 views

Solving optimization problems using derivatives and critical points

I have a homework question which I have completed 2/3 of; however I am stuck on the last part of the question. The question is: A drug used to treat cancer is effective at low doses with an ...
0
votes
1answer
191 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
1answer
79 views

Confusion related to the calculation of gradient

I am having some confusion related to the calculation of gradient. My function $f(X) = g(X) + \lambda||X||_1$ where g(X) is convex and differentiable. I didn't get how the second expression when ...
0
votes
1answer
75 views

Proximal operator

What is a proximal operator and how would one derive it in general for a function? In particular, if I had a function: $ f(x) = x^TQx + b^Tx + c $ How would I get the proximal operator for this if Q ...
0
votes
1answer
56 views

Confusion over a proof that gradient is perpendicular to the level set

To prove that the vector $\nabla{f}(x_0)$ is orthogonal to the tangent vector to "an arbitrary smooth curve" passing through $x_0$ on the level set determined by $f(x)=f(x_0)$ the following proof is ...
0
votes
1answer
34 views

Confusion related to Armijo's rule

I am having confusion related to Armijo's rule used for line search. Can you give me some links to good tutorials. I want to get the geometric interpretation behind it. I found this one ...
2
votes
0answers
53 views

the objective function $\|F\|_F^2$ is quasiconvex in the optimization?why?

I have read a paper, but I can not understand one optimization thoroughly.Generally, Frobenius norm of one matrix, $\|F\|_F^2$, as the objective function is convex, so we can resolve it not using the ...
0
votes
1answer
83 views

Maximize Trace as standard semidefinite optimization

Let $A$ be a symmetric matrix and $X$ a symmetric positive definite matrix, then the following standard semidefinite optimization problem is convex: min $tr (AX)$ subject to $X>0$ Now I wonder ...
0
votes
1answer
116 views

How to get the closed form solution of a non-convex optimization problem?

I want to know if there is a closed form expression for the optimal objective function? How can I get it, if it does exist? Condition: $h,f\in \mathbb{C}^{N\times1}, \epsilon > 0 $. $\max \ \ ...
0
votes
1answer
490 views

Convex conjugate of $\ell_1$ and $\ell_2$ norm

Given a function $f$, we can define a function $f^{*}$, called the convex conjugate (also known as the Fenchel conjugate) of $f$ as follows: $$ f^*(\vec{z})= \sup_{\vec x \in \mathbb ...
0
votes
1answer
34 views

Proofs regarding convex sets

I need assistance with the following proofs. I am not sure how to prove that one set is contained in another set. Here are the things required to be proven: Let $S$, $S_1$ and $S_2$ be non–empty sets ...
1
vote
0answers
33 views

Is the optimizer of a strongly-convex cost function bounded?

Let f(x) be strongly-convex. Can its minimizer be unbounded? I suspect not. Can we obtain a bound on it in relation to the strong-convexity constant? I believe an equivalent formulation of this ...
3
votes
1answer
579 views

Pointwise infimum of affine functions is concave

So I was just starting on convex optimization and was having a slightly hard time visualizing the lagrangian being always concave because it is the pointwise infimum of a family of affine functions. ...