Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

2
votes
2answers
96 views

not really sure which method to use

let there be $A(2,4,6)$ , $B(6,2,2)$; On the $x$ axis, find a point $P$ such that the sum of it's distances from points $A$ and $B$ would be minimal. I'm not really sure which method I should use ...
0
votes
2answers
136 views

converting from max to min in an optimization function?

I have the following maximization objective function related to a svm Then the author says that: is the same as minimizing: ||w||^2, why is this? and that our final optimization function is: ...
1
vote
0answers
66 views

Condition for maximizer of convex combination to be expansion mapping

I have $\Pi_n:\mathbb R^{n+1}\rightarrow \mathbb R$ and $F_n:\mathbb R^2\rightarrow \mathbb R$ with $$F_n(x,a)=\Pi_n(x,...,x,a)$$ $$f_n(x)=\operatorname{ArgMax}_{a\in\mathbb R}\{F_n(x,a)\} $$ such ...
0
votes
1answer
29 views

Replacing a max constraint in a binary program

For $x \in \{0,1\}$, I want to express $x = 1 \Leftrightarrow \exists k: y_k = 2$ where $y_k \in \{0,1,2\}$, i.e. $x \leq 0.5\max_k\{y_k\}$ using binary decision variables but I can't figure out how ...
1
vote
3answers
29 views

Lagrange Multipliers, maximize $f=xy$ restricted to $g=x^2+y^2=r^2$

So I have to solve the system of equations $$\cases{\nabla f = \lambda \nabla g\\x^2+y^2 = r^2}.$$ Then $y=2\lambda x, x=2\lambda y$. Sorry if this is obvious, but how can I get $x$ and $y$ only as ...
1
vote
1answer
2k views

How to test if a feasible solution is optimal - Complementary Slackness Theorem - Linear Programming

I have this linear program $$\begin{cases} \text{max }z=&5x_1+7x_2-3x_3\\ &2x_1+4x_2-2x_3&\le8\\ &-x_1+x_2+2x_3&\le10\\ &x_1+2x_2-x_3&\le6\\ &x_1,\,x_2,\,x_3\ge0 \end{...
0
votes
1answer
26 views

Update step in gradient descent

Suppose I have a function $f(x)$ for which I want to find minimums. I understand that differentiation with respect to $x$ will give direction $+/-$ in $x$ axis to follow in order to minimize. ...
5
votes
1answer
115 views

decomposition of a natural number

Let's say we have natural numbers $n,k$. Is there an effective way to represent $k$ as $a_1\cdot\ldots\cdot a_n$ such that each $a_i$ is natural and the sum $a_1+\cdots +a_n$ is minimal? It seems not ...
1
vote
1answer
21 views

Solve $\text{Minimize} \max\{|x-a_i|, i=1,..,n\}$

I have to solve $$\text{Minimize} \max\{|x-a_i|, i=1,..,n\}$$ For $a_1 \leq a_2 \leq ...\leq a_n$ My intuition says that this x is a point in the middle of the $a_i's$ but I am not sure that it is ...
0
votes
2answers
35 views

Do we have these kinds of “mean value”?

Let $x_1,\ldots,x_n$ be positive numbers. We want to find a number $x$ such that the sum $$ \sum_{i=1}^n|x-x_i| $$ get its minimal value. I know that such $x$ may be not unique. Nevertheless do we ...
0
votes
3answers
225 views

Optimization with implicit differentiation

I want to find the extrema of a function $F(x,y,z)$ subject to a constraint $g(x,y,z)=c$. This means that implicitely $z=z(x,y)$. So I find $ \frac {\partial F}{\partial x}$ and $ \frac {\partial F}{\...
0
votes
0answers
64 views

Do three valued basis vector elements lead to the fastest discrete Fourier transforms?

When sin() and cos() are approximated to 1, 0 and -1 in the basis vectors in a real or discrete Fourier transform the basis vectors have a lot of elements of zero or in common leading to an algorithm ...
1
vote
0answers
33 views

Minimum of a maximum function

What I'm trying to find is a linear function $y_{fit}$ ($y_{fit}=\beta_1+x\beta_2$) which minimizes the error $S= max(y - y_{fit}) - min(y - y_{fit})$. In other words, I'm looking for a linear ...
0
votes
0answers
117 views

math background for using Total Variation Norm for an L1-regularized optimization problem (Rudin-Osher-Fatemi)

I am working with some geographic data, and I would like to apply total variation denoising in order to sharpen the boundaries of clusters in the data. I also have some C code to run the split bregman ...
2
votes
1answer
168 views

On the Definition of Gateaux Derivative

My question is about two different definitions Gateaux derivative. I have seen the following two definitions but whether they are equivalent or which one is better to use I am not sure about: ...
0
votes
1answer
80 views

Max volume of a cone in a sphere

I have given to compute the maximum volume of a cone inscribed in a sphere of radius $R>0$. My question is give that x-radius of the cone the formula to maximize is $\frac{1}{3} \pi (R^2-x^2)(R+x)$...
0
votes
1answer
28 views

How can I show this ratio is >1 for intervals of x,y

I come here from a substantial application in statistics where I have reason to belive that the following ratio (function) is $$f(X,Y)=\frac{1}{(2XY^2-X^2Y^2+X^2-2X+1)^{\frac{1}{2}}} \ge 1$$ for $X,...
0
votes
2answers
1k views

What is the merit function?

When we use merit function in optimization & why uses this function? if we use merit function the space must be convex or not?
0
votes
1answer
79 views

How to solve this problem efficiently?

I have this problem \begin{align} \min_{\alpha,\beta,X}~&<\alpha \cdot X+\beta \cdot Y,D>-c \cdot (<\alpha \cdot X+\beta \cdot Y,H>)^{1/2}\\ &X,\alpha,\beta>=0\ \end{...
0
votes
1answer
32 views

Covariance Selection with specified sparsity pattern

I am new to semi-definite programming and I am trying to follow through the optimization described in http://cvxopt.org/userguide/spsolvers.html#example-covariance-selection The problem is to ...
1
vote
0answers
31 views

Multi-Objective Approximation Algorithms

Can algorithm approximations be combined in some form for purposes of multi-objective optimization? The study of approximation algorithms is very new to me, but I have been having a lot of difficulty ...
0
votes
1answer
21 views

finding the values of a such that an implicit function g(y)=x has max,min,saddle points along y=0

I've got $$f(x,y)= a\exp(1+xy) + a^2 \sin(x) +1$$ for which I've shown that there exists an implicit function $x=g(y). ( df/dx \neq 0)$ and $df/dx = a y \exp(1+xy) + a^2 \cos x$ now in the ...
1
vote
2answers
109 views

Using differentials to optimize a function

I've read in a paper by Tevian Dray an alternative way to solve optimization problems manipulating "differentials". Here is an example of how it works (next I quote the paper). Consider the ...
0
votes
1answer
56 views

what is the trust region algorithm in optimization?

I see some books that say the trust region work with contour's line .but i can't understand how choose the point with contour's line and sort them? thank you if answer me.
1
vote
1answer
137 views

Derivative of a summation function in order to minimize the function

I'm asked to minimize this function $$f\left(x\right)= \sum_{k=1}^K \left(g\left(w\left(k\right)+\alpha\right)-t\left(k\right)\right)^2$$ with respect only to $\alpha$. Function $g\left(w\left(k\...
0
votes
1answer
90 views

Existence and uniqueness of the minimizer of Moreau-Yosida approximation

Let $f:H\to\mathbb{R}$, where $H$ is a Hilbert space, be a function that is bounded below, convex ($f(tx+(1-t)y)\leq tf(x)+(1-t)f(y) \text{ for all } x,y\in H \text{ and } 0\leq t\leq 1$), and lower ...
1
vote
0answers
64 views

Strictly Concave Function over non-convex set

I have to optimize a function $f$ over a set $S \subset X$. We know that $f$ is non-negative, continuos and strictly concave over $X$. We have that $S$ is compact but not convex. By Extreme Value ...
0
votes
0answers
30 views

Formulating and solving box unloading as graph problem

I have a set of boxes as those pictured below. I can only remove boxes that dosen't have any boxes on top of it. In every "move" I can move any box that is currently available, but I have limitations ...
2
votes
0answers
55 views

Convergence in the distributional sense (mean field games dynamics)

I am trying to go through the papers by Gueant, Lions and Lasry on Mean field games. One of their examples is the Mexican wave (which happens in football stadia). Straight to the point the Lagrangian ...
1
vote
0answers
33 views

Hints on solving a constrained optimization problem

Here's a simple constrained optimization problem ($X,P \in\mathbb{R}^{m\times n}$): $Minimize_{X}~ \|P-X\|_{F}^{2}$ $subject~to~\|X\|_{0}= k$. The optimal $X$ can be got by setting all but the $k$ ...
0
votes
0answers
89 views

Difference between mean-variance and worst-case optimization for normal distribution

I have two optimization problems. 1-) Mean-variance optimization $J_{MV} = J_M - \gamma J_V$, where $J_M$ is mean, $J_V$ is the variance term and $\gamma$ is the weight on variance term. 2-) The ...
7
votes
1answer
208 views

Condition for increase in the optimum of a general function

For a function $f(x,y)$ with the following properties: $f(x,y)$ is strictly increasing as a function of $x$ $f(x,y)$ is strictly decreasing as a function of $y$ $\lim_{x\to\infty}\frac{\partial f(x,...
1
vote
2answers
471 views

Using Lagrange multipliers to find the shortest distance between two straight lines

A problem asks me to use the method of Lagrange multipliers to find the shortest distance between the straight lines $x=y = z$ and $x = -y, z=2$ (It also warns me that using this method is a bit ...
0
votes
1answer
33 views

Gradient of this function

I am to solve an optimization problem as described below: $$ \min f(x) = \frac{1}{2}\left\lVert x - x_{b} \right\rVert^{2}+ \frac{1}{2}\left\lVert \epsilon \right\rVert^{2}$$ with $$ Hx -y = \epsilon ...
0
votes
1answer
33 views

Global Max and Mins

Given $f(x,y) = x^2+y^2-14x-20y$ and restrictions $x≥0,\; 0≤y≤42 \;\text{and}\; y≥x$, I need to find the max and min. By finding partial derivatives and setting them to $0$, I get the min to be -149....
1
vote
3answers
32 views

Global max/min of surfaces

Given $f(x,y)=4x^3+4x^2y+3y^2$ and restrictions $x,y≥0$ and $x+y≤1$, I'm trying to find global max and mins. I found the partial derivative and found the critical point $(0,0)$ by setting those to $0$...
5
votes
3answers
128 views

Find the maximum and minimum of $x^2+2y^2$ if $x^2-xy+2y^2=1$.

Find the maximum and minimum of $x^2+2y^2$ if $x,y\in\mathbb R$ and $$x^2-xy+2y^2=1$$ My attempt: Clearly, since $x^2-x(y)+(2y^2-1)=0$ and $2y^2-y(x)+(x^2-1)=0$, we have that $$\Delta_1=y^2-8y^2+4=...
2
votes
1answer
84 views

absolute extrema problem…

My calc skills are kind of rusty. Was wondering if I could get an assist on this one perhaps? I am looking for the absolute extrema if they exist and all the x values they occur at in the domain. ...
0
votes
0answers
29 views

How to minimize this sparse quadratic function?

There is a problem when I'm reading a paper. Equation: $min_p|p-p^*|^2+\alpha |R(p)|^2 + \beta |D(p)-\delta|^2$, where $p, p^*, R(p), D(p), \delta$ are all $M\times N$ matrices, and $p^*, R(), D(), ...
1
vote
2answers
923 views

How to find max and min of this quadratic form?

So I'm a little confused about how to finish of this homework question and even unsure if my attempt is correct so far. . . " Find an orthonormal basis of matrix A" = $$\begin{pmatrix} 2 & 1 &...
1
vote
0answers
72 views

Basis pursuit denoising

The Lagrangian form of basis pursuit denoising $\min_{w} ||w||_{\ell_{1}} + \lambda ||Aw-x||_{\ell_{2}}^{2}$ can be solved using proximal gradient descent. Proximal methods also can be used to ...
0
votes
1answer
26 views

How do I answer questions that ask to construct examples with some given properties?

Give examples of sets and functions with the following properties: an open set $D_1 \subseteq \mathbb{R}$ and a continous function $f:D_1\rightarrow \mathbb{R}$ such that $f$ has both a maximum and ...
0
votes
2answers
76 views

find travel time given path and velocity field

As I was studying refraction, I began wondering what path would light take when entering a non-homogeneous transparent medium, i.e. a certain material in which the refraction index $n$ varies (...
4
votes
0answers
77 views

Calculation of an expression ($\max_{U}\min_i \sum_j |U_{ij}|^2 |e_i^j|^2$)

There is an orthonormal basis $\{e_i\}(i=1,\ldots,n)$ in $\mathbb{C}^n$, each of them is represented in form of column vectors $$\begin{pmatrix} e_i^1\\ \vdots\\e_i^n\end{pmatrix}.$$ My purpose is to ...
0
votes
2answers
143 views

Methods to translate global constraints to local constraints

Are there any general methods for (global) optimisation which can translate a global optimisation problem to a "local" one? Or in other words, translate global constraints to local constraints. To ...
0
votes
2answers
55 views

How to argue that $f(x,y,z)=-x^2-xy-y^2+4yz-8z^2+2xz$ has a global maximum?

Let $f(x,y,z)=-x^2-xy-y^2+4yz-8z^2+2xz$. I know $f$ has a local maximum at $(0,0,0)$ but how do I argue that this is also the global maximum. The solution provided simply states it is a global ...
0
votes
1answer
200 views

Dictionary learning for sparse coding using ADMM

I'm trying to formulate an ADMM for performing dictionary learning (for sparse coding) on a set of data. Let's assume we have a data matrix of $X \in \mathbb{R}^{M \times N}$, a dictionary of $D \in ...
0
votes
0answers
15 views

How to optimizing a function that takes two different forms in two different regions

a,b,and P are non-negative constants. And $\theta$ is a random variable with distribution function $F(\theta)$ and density function $f(\theta)$. Denote $H(\theta)= {F(\theta)\over f(\theta)}$. No ...
0
votes
0answers
29 views

Moving die on cartesian plane so as to minimize sum of facing face

I have a problem that I have been working on for which I cannot find a solution. Problem: Assume you are on a cartesian plane, and you want to move a die to a specific point. You can move the die up,...
0
votes
1answer
190 views

Code that minimizes the variance of sum of weighted random variables?

I'm trying to implement finding the weight that minimize the variance of the sum of random variables. I followed the formula from this question Minimizing the variance of weighted sum of two random ...