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)

1
vote
1answer
593 views

Does Normal Equation in Linear Regression Have A Unique Solution?

In linear regression under the hypothesis $Y= \theta ^TX$, we want to minimize the mean square $ J(\theta) =\frac{1}{2}\sum \left(y^{(i)}-\theta ^TX^{(i)}\right)^2$, through algebraic deduction we get ...
1
vote
2answers
182 views

Constrained optimization problem

I'm having problems with this assignment: $$\begin{array}{rl} \min & x^3 + 2xyz - z^2 \\ \text{subject to} & x^2 + y^2 + z^2 \leq 1 \\ \end{array}$$ Disregarding the constraint, find all ...
1
vote
1answer
425 views

Projected Gradient for Bounded constraint Problem

For the one-side bounded constraint problem, $\min_x f(x)$ s.t $x\geq0$, I know the projected gradient is given as $\nabla^p f(x) = \nabla f(x)$ if $x>0$ $\nabla^p f(x) = min(0,\nabla ...
1
vote
1answer
842 views

Positivity constraints in optimization

How do you enforce positivity constraints in non-linear optimization (e.g. a constraint $x > 0$)? I remember there being a good reason for why most models use non-negativity constraints.
1
vote
1answer
249 views

How to use Euler-Lagrange equation when obj fn integrated over two parameters?

If I want to find the minimizing function $f(t)$ over a single parameter, like time, then I take the integrand of $$\int_{t}L(t,f(t),f'(t))\:\:\:\:dt$$ and substitute it into the Euler-Lagrange ...
1
vote
1answer
1k views

Two-Phase Method (Linear Programming)

In Linear programming, when is it beneficial to use the Two-Phase Method? Why not just use the Simplex Method? (edit: typo)
1
vote
1answer
263 views

KKT Condition : Always either a Maxima/minima or Saddle?

For a constrained optimization problem, in general the KKT conditions are a necessary but not sufficient condition for a point to be the local maxima/minima of the objective function. Is it always ...
1
vote
2answers
695 views

Max f(x,y,z) = min{x, 5y+2z} subject to x+15y+7z=44

Max f(x,y,z) = min{x, 5y+2z} subject to x+15y+7z=44 As well, $x,y,z \geq 0$ I have guessed that the extrema point will be a point such that x=5y+2z and tried solving for the curve of intersection of ...
1
vote
1answer
1k views

Simple non linear fitting question(Least Squares Fitting--Exponential) [duplicate]

Possible Duplicate: easy to implement method to fit a power function (regression) I have the following simple function: $h = cV^n$ h and V being the variables and $c$ and $n$ are ...
1
vote
1answer
261 views

minimise no. of resistors in circuit

A circuit contains a 1V cell and some identical 1 ohm resistors. A voltage of a/b, where $a\leq b$, is to be made across a voltmeter using the minimum number of resistors in the circuit. The voltage ...
1
vote
2answers
955 views

Optimizing with Absolute Value Objective Function

max : $w = |q^T y|$ subject to $A y \leq b$ $y \geq 0$ Please describe how one could solve the non-linear programming prob. above by using linear programming methods. I tried changing $y$ to $y' ...
1
vote
1answer
900 views

Need help with Lagrange Multipliers

I need to maximize $U = BM$ with constraits: $6B +3M = 60$, $B>0$ and $M>0$. The Lagrange function is $L=U + \lambda (6B+3M-60) + KB + HM$. So $$\partial_{\lambda}L= 6B+3M-60=0$$ ...
1
vote
1answer
101 views

Puzzled by how to determine when a function takes on its maximum (or minimum)

I apologize for the specificity of the my question, but I'm concerned that I'm having trouble grasping an important concept. I'm puzzled by the answer provided for exercise 1.(v) in chapter 7 of ...
1
vote
1answer
132 views

Find the minimum value of $(\frac{x^n}{n} + \frac{1}{x})$ for $n \ge 4$

Find the minimum value of $(\frac{x^n}{n} + \frac{1}{x})$ for $n \ge 4$. One possible approach could be by first writing $$ \left(\frac{x^n}{n} + \frac{1} {x}\right) = \left( \frac{x^n}{n} + ...
1
vote
1answer
235 views

question about Lagrange multiplier

I was reading about the problem of maximizing $x^2+y^2+z^2$ on the intersection of the two surfaces $xyz=1$ and $x^2 + y^2 + 2z^2 = 4$. The author wrote that $\nabla F=a \nabla g+b \nabla h$ (for ...
1
vote
1answer
1k views

a property of log determinant

Let $X$ be a symmetric positive definite matrix, and $D$ be a symmetric matrix satisfying $\operatorname{tr}(X^{-1}DX^{-1}D) < 1$. How to show that $$f(X+D)\le ...
1
vote
1answer
97 views

Please help me find the maxima of this expression

I want to find $p$ which maximizes the given functional. $p$ is a function of the form $\mathbb{R}^2 \to \mathbb{R}$. $\Omega$ is a region in the 2-d plane. $\underset{p}{\sup} \int_\Omega \{ ...
1
vote
1answer
123 views

Basic linear problem solving

I have some LP problem and I'm willing to solve it (this is an exercise from some optimization-related book). Now, Mathematica tells me that the problem is unbounded and I want to make a generic ...
1
vote
1answer
210 views

Combinatorial Optimization Problem (can I/how do I solve this with integer programming?)

Inputs: 1) A set of M x N matrices, {A,B,C...N} containing only integers. 2) A single 1 x N matrix of floats, W (weights). I need to pull one row from each input matrix and sum values for each ...
1
vote
4answers
4k views

Optimisation in two variables - second order conditions

I have a problem understanding second-order conditions at a critical point in finding critical points of two-variable functions. Let's consider $f(x,y)$. The first-order conditions are ...
1
vote
2answers
222 views

Finding $\min_{\mathbf x} (\mathbf y - \mathbf G\mathbf x)^T(\mathbf y - \mathbf G\mathbf x)$

Let $\mathbf G$ be a given $m \times n$ matrix, $\mathbf y$ a given $m \times 1$ column vector and $\mathbf x$ an unknown $n \times 1$ column vector such that $\mathbf x \ge 0$. 1) How do you find ...
1
vote
2answers
54 views

Showing that mean of vectors minimizes the sum of the squared distances.

Let $S=\{x_1,...,x_n\}$ be a set of vectors in $\mathbb{R}^d$. Now we have to pick a vector $\mu$, such that the following expression is minimized: $$ L(\mu)=\sum_{x\in S} ||x-\mu||_2^2. $$ I think ...
1
vote
1answer
26 views

Solving constrained Euler-Lagrange equations with Lagrange Multipliers (Geodesics)

I'm trying to solve a calculus of variations geodesics problem using Lagrange Multipliers, showing that the geodesics of a sphere are the so-called great circles. I am using a constrained Lagrangian ...
1
vote
1answer
27 views

$f(z)=\frac{1}{z^2-2z+2}$ - Maximum modulus principle

Let the function $f(z)=\frac{1}{z^2-2z+2}$. I have to find $\max_{z \in D(0,1)} |f(z)|$, but I already know that the maxixum would be on $\bar{D}-interior(D)$ by the maximum modulus principle. Is ...
1
vote
1answer
31 views

Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
1
vote
1answer
53 views

Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal: $$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$ \begin{cases} \max & 7x_1 ...
1
vote
1answer
27 views

Help with minimizing integral

I want to make a formal argument that for the following optimzation problem $\underset{S}{\operatorname{argmin}} \int_0^D (x(t) - S)^2$ the minimum solution is to set S to the mean of x(t) in the ...
1
vote
1answer
14 views

Chebyshev's approximation understanding

I am reading Boyd's book on convex optimization. Could you assisst me in understanding what this expression means: $$\text{minimize} \ \ \text{max}_{i=1,...,k}|a_i^Tx-b_i|$$ This is what I think ...
1
vote
1answer
32 views

Find the global extrema of $f(x,y)=\sin(xy)$ on $D=[(x,y)| x = [0,\pi], y=[0,1]]$

Find the absolute maximum and absolute minimum of the function: $$f(x,y) = \sin(xy) \text{ on } D=[(x,y)| x = [0,\pi], y=[0,1]]$$ I took the partial derivatives and got: $$\frac{df}{dx} = \cos(xy)y ...
1
vote
1answer
31 views

how to find mininimum $f(x)$ using $\int_{-\infty}^{\infty} f(x)g(x)dx$?

I would like to know the $f(x)$ which minimizes the $\displaystyle\int_{-\infty}^{\infty} f(x)g(x)\,dx$. Actually, this question start from the MMSE (Minimize Mean square error) ...
1
vote
2answers
43 views

Find the Min of P(x,y)

Find the Minimum of the following function : $$P(x,y) = \frac{(x-y)}{(x^4+y^4+6)}.$$ This is a math problem I found in an internet math competition but it is really complex to me !!!
1
vote
1answer
20 views

Trust-region method

The question has to do with the trust-region method for unconstrained optimization. I came across it on p.~392 of Linear and Nonlinear Optimization, by Griva, Nash and Sofer. Let $p(\lambda)$ be ...
1
vote
1answer
26 views

Seems familiar: find $\max \sum_{i=1}^n\sum_{i=1}^n a_{ij}x_iy_j$ s.t. $x_1+\cdots+x_n=y_1+\cdots+y_n=1$

Given $a_{ij}\ge 0$. Find $$\max \sum_{i=1}^n\sum_{j=1}^n a_{ij}x_iy_j$$ s.t. $x_1+\cdots+x_n=y_1+\cdots+y_n=1, x_i\ge 0, y_i\ge 0\ \forall i$.
1
vote
1answer
43 views

Closed form for $L$ in $LL^T=XX^T-Diag(XX^T)$

I want to write $XX^T-Diag(XX^T)$ into $LL^T$. $Diag(XX^T)$ is a diagonal matrix with only diagonal values in $XX^T$ on it. Can I get the closed form solution of $L$? As pointed out, ...
1
vote
1answer
41 views

Existence of unique maximizer in R^n

This sounds like a very basic question, but I have a hard time pinpointing the necessary and sufficient conditions... Let $f : \mathbf{R}^n \to \mathbf{R}$ be a function. I want to prove that there ...
1
vote
1answer
50 views

Required conditions for product of two submodular functions to be submodular?

3.32 of Boyd's Convex Optimization book says: Products and ratios of convex functions. In general the product or ratio of two convex functions is not convex. However, there are some results that ...
1
vote
1answer
43 views

Calculating the minima and maxima of equations involving the trig functions

This is the function given: $$S(x) = \sin^2 x$$ First I calculate the first and second derivatives: \begin{align} \frac{dS}{dx}\; & = 2\cos(x)\sin(x) \\ & = \sin(2x) \\ \frac{d^2S}{dx^2}\; ...
1
vote
1answer
49 views

Determine the optimal number and location of the plants and pipelines in the 7 cities.

There are 7 cities, up to 4 plants to be made in them and up to 18 pipelines to be made connecting them. Determine the optimal amount of plants and pipelines to be made, the optimal locations of the ...
1
vote
1answer
27 views

From Euler-Lagrange equation to time-dependent problem

I am reading this pdf which is about an image denoise model. Essentially, we want to find a function $u$ such that $u$ minimize the following functional: $$F(u) = \lambda \int_\Omega |f-u|^2 \,dx\,dy ...
1
vote
1answer
48 views

Ratio of two submodular functions is submodular?

Say we had 3 submodular functions $f(X)$, $g(X)$ and $h(X)$ is $\frac{f(X)}{g(X). h(X)}$ submodular as well? What can be said about the submodularity of $\frac{f(X)}{g(X)}$ and $f(X).g(X)$? I ...
1
vote
1answer
32 views

Optimization problem, choose n from set where $f(n)$ is maximized and $g(n)$ is minimized

Say I have multiple objects in a set, each with a certain value $f$ and $g$ for each object in the set, and I want to select exactly $N$ of these objects from the set such that the sum of $f $is ...
1
vote
1answer
41 views

Choose which plants to build to maximise profit

What I tried: Let $y_i = 1$ if plant $i$ is to be constructed and $0$ otherwise Let $c_{ij}$ be transportation cost per-unit for whatever the plants produce delivered from plant $i$ to ...
1
vote
2answers
81 views

What if the 'or' is exclusive instead of inclusive?

The context is an integer programming problem on choosing projects to maximise profit. I think (b) i. changes if 'either project 1 or project 3' means 'project 1 xor project 3' rather than 'project 1 ...
1
vote
2answers
43 views

Optimization over linear combinition of min functions

Assume we are given these six variables: $x_{12},x_{21},x_{13},x_{31},x_{23},x_{32}$. Then if, $A_{ij} = min\{x_{ij},x_{ji} \}, B_{ik} = min\{x_{ik} - A_{ij}, x_{ki} \}, C_{jk} = min\{x_{jk} - ...
1
vote
1answer
17 views

Extreme values of a function on a set

I have a function $\ f(x,y,z)=xyz$ on a set $\ M=\{x,y,z:x+y+z=3\} $ and have to find extreme values of the function on set $M$. I made Lagrange's function $$ L(x,y,z,\Lambda) =xyz+\Lambda x+\Lambda ...
1
vote
1answer
26 views

How to find a realisable starting point with the Simplex algorithm?

Let be the following linear program: \begin{equation*} \begin{cases} \max f(x_1,x_2) =3x_1+2x_2\\ 5x_1 + 2x_2 \ge 8\\ x_1 - x_2 \le 1\\ x_1 + x_2 \le 3\\ ...
1
vote
1answer
32 views

Assigning 2 Tasks to each Agent w/ Hungarian Algorithm?

Suppose I have 4 agents and 8 tasks and I would like to assign each agent 2 tasks each. Is there a way to use the Hungarian Algorithm to solve this problem? I worked it out with 2 agents and 4 tasks ...
1
vote
1answer
35 views

Golden Section Search

I've been asked the following question: The golden section method is to be applied to a unimodal function to find the minimum in the domain $[0,2]$. Given we require the error not be greater than ...
1
vote
1answer
20 views

Updating variables in multi variables gradient descent

In gradient descent of a function F($\theta_1$,$\theta_2$), in the update step after doing $\theta_1' \leftarrow \theta_1 - \alpha \frac{\sigma F}{\sigma\theta_1}$ when we update $\theta_2$, do we use ...
1
vote
1answer
26 views

Sum of weighted cosine functions (2)

I had written a question but I did not formulate the problem correctly (sorry). The last question is in this link. I am writing the problem again and I would appreciate any help. Assume $\theta_{ij}$ ...