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)

0
votes
2answers
114 views

A fencing problem

So the problem is: I have bought a fence 30 meters long and I need to put it around three of my rectangular fields sides. How long should be each of the field sides, to create the biggest ...
4
votes
1answer
96 views

good approach to solving this nonconvex quadratically-constrained program

I want to find a (local) minimizer $x, y$ to the following optimization problem: $$ \min_{x,y}\ x^T x + a^T x \qquad \mathrm{s.t.} \qquad \begin{array}{r}x^T M_i y + c_i = 0 \\ y \geq 0\end{array}.$$ ...
1
vote
1answer
562 views

Proof that Hessian matrix of Lagrangian function can not be positive definite

This is a homework problem I have a hard time to understand. Any tips would be appreciated to get me in the right direction. Given functions $f: \mathbb{R}^n \to \mathbb{R}$ and $\boldsymbol{g}: ...
1
vote
2answers
598 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' ...
3
votes
1answer
210 views

Optimization with constraint on solution of a linear system

I'm facing this optimization problem: $$\text{minimize} \quad a^T x$$ $$\text{s.t. the solution of $A(x) z + B(x) = 0$ belongs to a convex set $S$}$$ Here $A(x)$ is a linear matrix function of $x$ ...
4
votes
0answers
390 views

An optimization problem involving orthogonal matrices

Let $X\in\mathbb{R}^{3\times 3}$ be an orthogonal matrix. Then $\mathrm{vec}X\in\mathbb{R}^9$ is a 9 by 1 vector formed by stacking the columns of the matrix $X$ on top of one another. Given a matrix ...
1
vote
1answer
203 views

Economic optimisation problem

Here is the question: Consider a car-owning consumer with utility function $$u (x) = x_1x_2 + x_3 (x_4)^2 ,$$ where $x_1$ denotes food consumed, $x_2$ denotes alcohol consumed, $x_3$ denotes kms of ...
1
vote
0answers
46 views

Algorithm for optimizing width length of classes of an ordered list of data points under certain conditions

I have the following problem: I have an ordered list of $n$ data points jiggling around $0$ with no apparent order. The order this list is in should not be affected by the following procedure. I want ...
2
votes
2answers
386 views

Maximization over vectors (seen as column matrices)

I am trying to solve the following question: $$\text{Maximize } f(x_1,x_2,\ldots, x_n)=2\sum\limits_{i=1}^n x_i^t A x_i+\sum\limits_{i=1}^{n-1}\sum\limits_{j>i}^n (x_i^tAx_j+x_j^tAx_i)$$ subject ...
1
vote
1answer
522 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$$ ...
2
votes
1answer
103 views

Vector Theory Question

I am having trouble getting started on this multi-part problem. Could anyone take a look and provide some insight on how I might go about coming to a solution for the first part. Q: Assume for two ...
1
vote
1answer
160 views

Voronoi diagram with different metric functions

Given a metric space $(X,d)$ and finite number of points $(x_i)_{i=1}^n$ the Voronoi diagram (or the Dirichlet cell) $C_i$ is given by $$ C_i = \{x\in X:d(x,x_i)<\min\limits_{j\neq i}d(x,x_j)\}. ...
3
votes
1answer
412 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 ...
0
votes
1answer
131 views

Optimization - Get value of Lagrangian

We know that $f(x) \to \min$ subject to $g(x) = t$ and $h(x) \leq m$ can be written as $f(x) + \lambda g(x)\to\min$ subject to $h(x) \leq m$. How do we get value of lambda so that the two problems ...
2
votes
1answer
159 views

Linear Programming - Single Optimal Solution

Is it correct to state that if a linear objective function is not in parallel with any of the constraints, than there is a single optimal solution at some vertex of the polytope?
0
votes
1answer
126 views

invex functions - optimality functions

For a general convex program, a feasible point is an optimal solution if and only if it lies in a hyperplane whose a normal vector is the gradient to the objective function at this point. Please ...
2
votes
1answer
75 views

Drawing samples from an LP program

Say I have an LP program in standard form: \begin{equation*} \begin{array}{rl} \mathbf{x}^* = \underset{\mathbf{x}}{\text{arg}\;\text{min}} & \mathbf{c}^T\mathbf{x} \\ \mbox{s.t.} ...
2
votes
1answer
234 views

Linear Programming - Getting a vertex of the polytope

I have a standard basic linear programming problem. Is there a polynomial time algorithm that can return a vertex of the polytope that describes the feasible set of solutions. I know that the ...
2
votes
0answers
86 views

Is my use of Lagrange multipliers correct?

Given $n$ positive values. $x_i \ge 1 (1\le x_i \le n)$. Their sum is $k$. $$ \sum_{i=1}^{n}x_i = k $$ Define the following value: $$ \sum_{i=1}^{n}x_i(x_i-1) $$ Now use Lagrange multipliers to ...
12
votes
7answers
2k views

How to prove the sum of squares is minimum?

Given $n$ positive values. Their sum is $k$. $$ x_1 + x_2 + \cdots + x_n = k $$ The sum of their squares is defined as: $$ x_1^2 + x_2^2 + \cdots + x_n^2 $$ I think that the sum of squares is ...
5
votes
1answer
2k views

simplex method : Entering Variable

In the Simplex method, a variable that enters the basis, cannot depart the basis in the very next iteration. Please explain..why so ?
0
votes
1answer
174 views

Positive semidefinite vector $\bar{x}$ as $\bar{x}>0 :=\bar{x} \lambda \bar{x}^{T}>0$?

$A \lambda A^{T} $ (quadratic form?) is used with matrices to check definiteness. What about with vectors? If I see conditions such as $\bar{x} > 0$, how can I know whether it means $\bar{x}_{i} ...
3
votes
1answer
309 views

Does a maximum entropy probability distribution with KL-divergence constraint not exist?

In my earlier question I asked about a technical aspect of solving a system of equations arising from looking for an entropy-maximizing distribution $p(x)$ continuous on $\mathbb{R}$ and constrained ...
14
votes
2answers
466 views

The Farmyard problem

Problem: There is a farmer who has a $1\text{ mile}\times 1\text{ mile}$ square piece of land. He knows that there is a completely straight pipe underneath some part of his property, but it could ...
3
votes
2answers
952 views

Grad degree that mainly deals with probability/game theory/optimization?

I'm currently working but am going to take classes as a non-degree student to beef up the math part of my background. I've only taken calc 1-3, ODEs, linear algebra, logic, and decision theory so my ...
2
votes
2answers
86 views

is there a solution to the following maximization problem such that $a = b$?

Let $X = (X_1,...,X_n)$ be a vector of $n$ random variables. Consider the following maximization problem: $\max\limits_{a,b} \;\mathrm{Cov}(a\cdot X, b \cdot X)$ under the constraint that $\|a\|_2 = ...
1
vote
1answer
97 views

Derivatives with respect to a symmetric matrix, with an application to maximum likelihood

I am quite unsure about this whole matter of differentiation with respect to a matrix. First, I'd like a good (online hopefully) reference for getting up to speed on the theory - as opposed to a bunch ...
2
votes
1answer
468 views

Optimization benchmarks?

There are so many different optimization algorithms out there, and lots of research going on. However, I have difficulties to find good comparison between them, and all articles / books / papers seem ...
2
votes
1answer
672 views

How to maximize this equation?

I am trying to maximize $P = 20q_a - 2q_a^2 + 16q_b-2q_b^2 – 1/4 (q_a + q_b)^2$, a profit equation, function of two separate quantities of products. I thought that what I need to do is to set both ...
4
votes
2answers
1k views

Minimize a matrix function with constraints

Let $A, X\in\mathbb{R}^{n\times n}$. The scalar objective function is $$J=\mathrm{tr}(AX)$$ If no constraints, let the derivative of $J$ with respect to $X$ be zeros, then we have $$A=0$$ Suppose $A$ ...
5
votes
2answers
82 views

Looking for mathematical optimizations when translating formulae to code

I'm writing an app which translates formulae into executable code. I've been experimenting with fairly obvious optimizations such as factoring (reducing number of multiplications) in order to make the ...
5
votes
2answers
784 views

Least square principles with Lagrange multiplier

I have a function to minimize: $$f(a_1,a_2,a_3,a_4)=\sum_{i=1}^n\left(\sum_{k=1}^3 a_k\ p_i^k -a_4\right)^2$$ subjected to this constraint: $$a_1^2+a_2^2+a_3^2=1$$ and $$a_4\geq0$$ I am trying ...
3
votes
3answers
81 views

Prove that $(2-x)^nx^{n-1}$ decreases with $n$ for $0 <x<1$?

How can I show that: $$(2-x)^nx^{n-1}$$ is decreasing with $n$ when $0<x<1$? I think this is generally true, but specifically I am concerned with $n$ as an integer $\geq 2$ and showing that the ...
1
vote
0answers
29 views

MLE estimation of parameters, converting normalized observations to integers and back

I am fitting a model's parameters to grouped data by maximizing the likelihood equation: $L(\theta)=N!\prod_{i=1}^{G}\frac{p_i(\theta)^{n_i}}{n_i!}$ $\theta$ is the vector of parameters. $n_i$ is ...
2
votes
1answer
59 views

Specific solvable cases of TSP

Did a quick search on polynomial time solvable TSP and found some references such as this one for special cases for the bottleneck TSP. Was wondering if anyone was aware of any references that catalog ...
1
vote
1answer
97 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 ...
2
votes
1answer
429 views

Derivative of function including matrix logarithm

Is the following equation a first order approximation or incorrect for general matrix Lie groups? And what are the higher order terms? $$\frac{\partial}{\partial\mathbf x} (\log(\mathtt ...
10
votes
0answers
370 views

Is the layout of Burning Man's city “grid” optimal?

My intuition is that the layout of Burning Man's city "grid" optimizes for the smallest sum of all distances between any two points on the map. Am I correct? Is the proof obvious? Or is there another ...
2
votes
2answers
404 views

Simplex method: Optimality criterion

I have to show that if for a minimization problem, $z_j - c_j <0$, for all non basic variables then it has a unique optimal solution. The proof says "If we start with a feasible point $x$ ...
0
votes
1answer
164 views

Show $\nabla \bar{x}^{T} M \bar{x} = \lambda ( \nabla \bar{x}^{T} \bar{x} )$

I am trying to prove the sentence ...
1
vote
1answer
169 views

How to normalize distances for use as weight coefficients?

I trade on the FOREX market. Currently I am attempting to use the FLANN library (Fast Library for Approximate Nearest Neighbors) to find N similar situations to the ...
3
votes
3answers
850 views

How do you find the optimal value for this function?

Given $$\sum_{i=1}^n x_i = 1,$$ what values of $x_i$ minimize the sum $$\sum_{i=1}^{n}x_i^2\ ?$$
12
votes
4answers
6k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
5
votes
1answer
348 views

What kinds of optimization problems can be solved by greedy algorithms accurately?

I was wondering what kinds of optimization problems can be solved by greedy algorithms accurately? I don't understand the following quote from Wikipedia: Greedy algorithms can be characterized ...
0
votes
1answer
115 views

Getting linear regression of huge numbers

I'm trying to get a linear regression slope and intercept for a large set of huge numbers. I'm doing this on a computer, but I keep getting overflow errors (attempting to calculate a number too large ...
3
votes
1answer
62 views

Library Branch Circulation Problem - Terminology and References

This is a bit general, but is there a name to this type of problem? It looks like a directed graph traversal problem, but you have multiple paths going on, and timing may be important. You operate ...
3
votes
1answer
2k views

Choosing Pivot differently in maximization Simplex- and minimization Simplex method?

In maximization simplex, the pivot is the smallest element in the column divided by the rightmost corresponding number. I am stumbling with the Example 3 here with solution that choose the pivot with ...
4
votes
1answer
484 views

Unscramble images without trying all permutations

I try to write an algorithm that unscrambles images that were before scrambled by mixing up small blocks: My idea is that in the bottom image there are more "sharp" corners compared to the image ...
6
votes
2answers
187 views

How to solve mixed integer nonlinear programs?

I'm not a math expert so sorry for possible trivial questions. I have written this mixed integer nonlinear program (MINLP): $$ \begin{align} \min & \sum_{i \in ...
2
votes
1answer
303 views

Optimization over union of convex sets

Let's say I would like to minimize a convex function $f(x)$ over a set $C$. $C$ is not convex but a union of a finite number of convex sets $C_i$: $C = C_1 \cup \dots \cup C_m$ where each $C_i$ is ...