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

learn more… | top users | synonyms

0
votes
0answers
6 views

Projection onto convex set defined by $\|\mathbf{t} -\mathbf{W}^T\mathbf{y}\|^2 \leq k$

I want to use the method of Projections Onto Convex Sets, and for the problem at hand I need to find a closed form solution for $\mathbf{P}_C$, the projection onto set $C$, defined as: $$C = \{ ...
0
votes
1answer
37 views

convex hull function in matlab

Is there anyway to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
2
votes
1answer
42 views

Got stuck with this $L^2(-1, 1)$ optimization problem. Any ideas where it comes from?

Statement Let $u(x) \in L^2(-1, 1)$. Solve the following optimization problem: $$ \begin{cases} J(u) = 4 \int_{-1}^{1} \sqrt{|x| (1 - |x|)} u(x) dx + \left(\int_{-1}^1 \sin(3\pi x) u(x) dx\right)^2 ...
0
votes
0answers
14 views

Interpreting constraints in an optimization problem

I am working on an optimization-based image denoising project in which I have three "flavors" of an optimization problem, one constrained and two unconstrained. They are given as follows: ...
1
vote
1answer
19 views

Is a constrained optimization problem equalivant to its Lagrangian form?

For the following problem: $\text{min:}\ f(x)\\ s.t. \ g(x)\leq t$ Is the above problem equalivant to the following problem? $\text{min:}\ f(x) + \lambda g(x) \\ s.t. \ \lambda\geq0$ where $t$ and ...
0
votes
1answer
42 views

What's the solution for $\max_{x\in(0,1]}: \{-1-x\}$

What's the solution for the following optimization problem? Is the constraint set convex? $$\max_{x\in(0,1]}:\{-1-x\}$$
0
votes
1answer
25 views

Convex Subset Projection

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
30 views

Critical points and Convexity?

Function $f(x)$ has no critical points in $M$, can we say $f(x)$ is either convex or concave over $M$?
0
votes
0answers
14 views

Formal definition of convexity for multivariate function?

Let $M\in R^{M\times N}$, a function $f: M\rightarrow R$ is called convex on $M$ if $f\big((1-\lambda)X1+\lambda X2, (1-\lambda)Y1+\lambda Y2\big) \leq (1-\lambda)f(X1,Y1) + \lambda f(X2,Y2)$ For ...
0
votes
1answer
26 views

Underdetermined system with inequality constraints

I have an underdetermined system of equations of the form \begin{equation} Ax = b, \end{equation} where $A \in \mathbf{R}^{m \times n}$ with $m < n$, subject to \begin{equation}0 \preceq x ...
0
votes
0answers
24 views

Duality gap problem

I have checked that the objective function is concave and the constraint functions are convex. Now to find the duality gap, one need to find the optimum of the primal and dual problem, and find the ...
0
votes
0answers
40 views

max and min values on symmetric polytope

Let $-N\leq t \leq N$. Let $A$ be regular $(N-1)$-dimensional simplex with vertices $(t,0, \ldots, 0)\ldots (0, 0,\ldots, t)$ and $B$ be regular $(N-1)$-dimensional simplex with vertices $(t-N+1,1, ...
0
votes
0answers
20 views

No critical points means convex or conave? [closed]

If we don't know whether $f(x)=0$ is convex or concave or not, but we know under certain constraint sets there is no critical points of $f(x)$ inside meaning the solution of $df(x)=0$ is outside the ...
0
votes
2answers
42 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 ...
1
vote
2answers
28 views

Optimization of Product of Different Objective functions (Ex.: Maximize The Product of projections of a complex vector)

Suppose We have this optimization problem which is convex $\mathbf{x}={\arg}\: \underset{\mathbf{x}}\max f_{i}\left (\mathbf{x} \right )$ But the product of different objective function is ...
1
vote
1answer
41 views

Convex Functions and Subsets

Suppose that $f, g: \mathbb R^n \to \mathbb R $ are $C^1$ convex functions. Show that $C = ${$\mathbf x \mid g(\mathbf x) \leq 0$} is a convex subset of $\mathbb R^n$. Show that if $\nabla f(\mathbf ...
0
votes
0answers
22 views

Convex cones and positively homogenous and subadditive functional

Let $V$ be a linear topological space, $K \subsetneq V$ a convex, closed cone with $0 \in K$ and $k \in K \setminus (-K)$. Show that the functional $\varphi : V \to \mathbb R \cup \{ \pm \infty \}$ ...
0
votes
1answer
31 views

Min of concave symmetric function on a convex set

Consider the convex set $$C=\left\{ \mathbf{x}\in \mathbb{R}^N :0\le x_1\le x_2\le\dots\le x_i\le x_{i+1}\le \ldots\le x_N\le \frac 1{N-1}\text{ and } \sum_{k=1}^{N}x_k=1\right\}$$ I need to minimize ...
0
votes
0answers
35 views

Why is pointwise maximum a convex function?

It seems like if you have a family of function $$g = \{a(x), \: b(x), \: c(x), \:d(x)\}$$ $$\text{given} \:\: f(x):= max(g),$$ $$\text{if} \: f(1) = a(1), \: f(2) = b(2), \: f(3) = c(3), \: f(4) = ...
0
votes
1answer
24 views

Why does convexity of a function required the following

What is the significance of the following condition $$\forall x_1, x_2 \in dom(f) , \forall \theta \in [0, 1], f(\theta x - (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$$ and why isn't the ...
0
votes
2answers
44 views

Dual of a Semi Definite Programming Problem

How do I write the dual of the following semi definite programming problem? \begin{align} \max_{\lambda,y_i}~&\lambda \\ &\sum_{i=1}^{L}y_i\mathbf{C}_i-\lambda\mathbf{I}\geq 0 \\ ...
0
votes
1answer
17 views

How do I justify that a second order cone is an intersection of half space

I am studying convex optimization right now, and the text book claims that a second order cone is a collection of intersections of half space $$K_n = \bigcap_{ u:\|u\|_2 \leq 1} \{(x,y) \in R^{n+1 } ...
0
votes
0answers
26 views

Exact Line Search in Projected Gradient Descent

How is exact line search adapted for projected gradient descent in convex optimization? One way I think of is that unconstrained exact line search is run, and the new point is projected into the ...
1
vote
1answer
30 views

Convex Sets and extreme supports

Let the set $S$ in $R^n$ consists of the origin $0$ and $n$ lineary independent vectors $T_1, \ldots, T_n$. Show that $C(S)$, the convex hull of of $S$, is the intersection of its extreme supports, ...
1
vote
1answer
33 views

Derivative of a minimum

The expression, $e=\left(x(t,w)-c_x\right){}^2+\left(y(t,w)-c_y\right){}^2$, has a local minimum with respect to $t$ at some $t_0(w)$. Now what does $t_0'(w)$ look like?! $x,y\in C^2$ with respect to ...
1
vote
1answer
18 views

Impact of constraints on convex optimization

Let me start by saying I know almost nothing about optimization so please bear with me. Basically, I am wondering whether it is possible to solve a problem with two constraints by solving the problem ...
4
votes
0answers
160 views

Properties of the square norm in Banach spaces

Let $X$ be a Banach space with its dual $X^*$. Consider the mapping $f: X\rightarrow \mathbb{R}$ given by $$ f(x)=\frac{1}{2}\|x\|^2. $$ We have know that when $X$ is a real Hilbert space ($X=X^*$) ...
1
vote
1answer
37 views

An application of Separation Theorem

Let $X$ be a Hausdorff locally convex topological vector space. Suppose $X_0 \subset X$ is nonempty convex set, $g:\; X\to \mathbb R^m$ is a convex vector function (each component $g_i(x): X\to ...
0
votes
1answer
39 views

A Simple Algorithm for Imposing Semi-definite Constraints

What is the simplest algorithm to implement, to impose semi-definite constraints? $\min_{X\succeq 0} f(X) $, where $X$ is an $n \times n$ symmetric matrix, and $f$ is a general smooth convex ...
1
vote
1answer
22 views

Confusion related to the convexity of a bunch of functions

I have this confusion related to the convexity of some function.I was reading this paper - www.sigkdd.org/sites/default/files/issues/V14-01-02-Ye.pdf‎. I have this graph consisting of nodes denoted by ...
0
votes
1answer
15 views

Finding the maximum/minimum of a homogeneous function on $R^n$

Suppose that $f:R^n\to R$ is homogeneous. Also, suppose that the $argmin_xf(x)$ is non-empty. Is it true that if there exist $x^*\in R^n$ such that $f(x^*)=0$, then $x^*=argmin_xf(x)$?
1
vote
1answer
27 views

Dual formulation of an SDP problem

Could you help me formulate the dual problem to this SDP? maximize $\frac{1}{2} Tr(GW)$, subject to $ G \ge 0$ (and G symmetric), and $ \forall i$, $ G_{ii} = G_{1i} = G_{i1} $ Note that $G$ and ...
0
votes
1answer
34 views

Convert Semidefinite program forms

How do I convert the following SDP problem (written in the standard inequality form): $$\min c^T x$$ $$\text{s.t. }F(x)\succeq0$$ When $F(x)\equiv F_{0}+\sum_{i=1}^{m}x_{i}F_{i}$ when $F_{i}\in ...
1
vote
1answer
37 views

KKT point of a constrained optimization problem

Min$_{x}~x$ Subject to $x \geq 0$ For this problem, is $(x^{*}, \lambda^{*})=$$(0,0)$ a KKT point ? My try : I formulated corresponding Lagrangian and tried to find out the KKT point(s). ...
0
votes
1answer
26 views

How to realize $\lambda_{max}(X)$ is convex?

How to realize is convex (f is convex) X is symmetric. (S.Boyd's book p.82, Example 3.10) It is easy to undertand like f = x^2 is convex; however, it is a bit hard for me to understand this ...
3
votes
1answer
74 views

How to minimize $\max(x_1, x_2)$ and $x_1^2 + 9x_2^2$ subject to constraints?

My textbook came up with a solution without explanation. I'm looking for a systematic way of solving the following optimization problems and similar ones (by hand), because I'm drawing a blank: ...
0
votes
1answer
30 views

Solving the cost function optimization problem using linear programming

My cost function is in the form $$ \Delta u^T P \Delta u + q^T \Delta u$$How shall I put it in the form of $c^T x$ to be able to solve it using linear programming?
0
votes
1answer
16 views

Unique critical point and psd implies pd and hence strict relative maximum

Let $f(x)$ be of class $C^{(2)}$ on an open set A, $x_0\in A\subseteq R^n$ a critical point. In addition, the hessian matrix of f(x) at $x_0$, $H(x_0)=\{f_{ij}\}|_{x=x_0}$, is positive semi-definite. ...
1
vote
0answers
17 views

restricted set of a convex set

Let $S \subset \mathbb R^n$, $S$ is convex and let $||.||$ be a norm on $\mathbb R^n.$ For $a \ge 0$ we define $S_{-a} =\{ x | B(x,a) \in S\}$, where $B(x,a)$ is the ball (in the norm $||.||)$, ...
1
vote
2answers
29 views

A statement for convex sets

The following statement is true or false? Given a convex set $S$ then for any $y \in S$ and $\theta\in[0,1], \theta \in \mathbb R$ there exist $y_1,y_2 \in S, y_1 \ne y, y_2 \ne y$ such that ...
0
votes
1answer
27 views

Inequality description of Convex hull

Given a finite collection of points $p_1,p_2,\ldots,p_m \in \mathbb{R}^n$, what are the inequalities describing their convex hull $\text{Conv}\{p_1,p_2,\ldots,p_m\}$?
0
votes
1answer
26 views

Convert SOCP from quadratic form to generalized inequality form

I have formulated a Second-order Cone Problem (SOCP) in “quadratic” form with a norm inequality constraint. To use a certain solver (ECOS, to be precise), I need to rewrite it to a form that makes use ...
0
votes
0answers
17 views

Deriving the optimal value for the intercept term in SVM

I was reading andrew ng's machine learning lecture notes on SVM. I came across the following equation (finding the optimal value for the intercept term $b$ in the SVM problem): However, I have no ...
0
votes
0answers
24 views

Mixed Integer Non Linear Problem for Relaxation Approach

I have the following problem. I have meat markets$(\mathcal{T}_1)$ and vegetable markets$(\mathcal{T}_2)$. $(\mathcal{T}_1) \cup (\mathcal{T}_2) = T$ and $(\mathcal{M}) \cap (\mathcal{V}) = ...
0
votes
1answer
32 views

Convex functions -> quasi-convex functions -> … can we weaken the assumptions?

First of all let me say that I'm new to optimization. I realized that quasi-convex functions share with convex functions some nice properties, so I wonder if we can push the weakening a little ...
0
votes
1answer
178 views

How to calc $\min ||J\Delta\tau + D||_*$

How to calculate $$ \min_{\tau} ||J_1 \tau_1 + \cdots + J_p \tau_p + D ||_* $$ where $\tau_1, \cdots, \tau_p \in \mathbb{R}$ $J_1, \cdots, J_p, D \in \mathbb{R}^{m \times n}$ $||\cdot||_*$ is sum ...
3
votes
2answers
57 views

Distribution of the Objective Value and the Variables in an Optimization Program

For random variables $X$ and $Y$, where $X\sim f(X;\theta)$ ($X$ is drawn from some distribution with pdf $f$ which is parametrized by $\theta$ ), $Y=g(X)$; we know that we can find the pdf of $Y$ if ...
1
vote
1answer
20 views

Propertise of a Dual Cone

In Convex Optimization by Boyd (P.51) said that " $y\in K^*$ iff $-y$ is the normal of hyperplane that supports $k$ at the origin ($K^*$ is a dual cone of $K$) " what does it mean geometrically? I ...
0
votes
0answers
21 views

Describing a Dual Cone

1)Does dual cone define just for proper cone or all kinds of cone ? 2)Can someone show me a figure that shows a dual cone of a cone ? In Convex Optimization by Boyd (P.51) said that " $y\in k^*$ iff ...
0
votes
0answers
31 views

Normal vector of a Hyperplane

I'm reading convex optimization by Boyd and I have a problem with normal of a hyperplane how many normal can we assume for a hyperplane at just one point? is it true that we can assume many vectors ...